src/vector.c


Log

Author Commit Date CI Message
Patrick Steinhardt 0c7f49dd 2017-06-30T13:39:01 Make sure to always include "common.h" first Next to including several files, our "common.h" header also declares various macros which are then used throughout the project. As such, we have to make sure to always include this file first in all implementation files. Otherwise, we might encounter problems or even silent behavioural differences due to macros or defines not being defined as they should be. So in fact, our header and implementation files should make sure to always include "common.h" first. This commit does so by establishing a common include pattern. Header files inside of "src" will now always include "common.h" as its first other file, separated by a newline from all the other includes to make it stand out as special. There are two cases for the implementation files. If they do have a matching header file, they will always include this one first, leading to "common.h" being transitively included as first file. If they do not have a matching header file, they instead include "common.h" as first file themselves. This fixes the outlined problems and will become our standard practice for header and source files inside of the "src/" from now on.
Patrick Steinhardt f47db3c7 2017-02-02T16:02:57 vector: do not reverse a vector if it is empty The code reversing a vector initially determines the rear-pointer by simply subtracting 1 from the vector's length. Obviously, this fails if the vector is empty, in which case we have an integer overflow. Fix the issue by returning early if the vector is empty.
Carlos Martín Nieto 0bd43371 2016-09-23T12:42:33 vector, pqueue: add git_vector_reverse and git_pqueue_reverse This is a convenience function to reverse the contents of a vector and a pqueue in-place. The pqueue function is useful in the case where we're treating it as a LIFO queue.
Edward Thomson 53571f2f 2015-11-21T15:16:01 vector: more sensible names for `grow_at`/`shrink_at`
Edward Thomson e564fc65 2015-09-25T12:41:15 git_vector_grow/shrink: correct shrink, and tests
Edward Thomson 7cb904ba 2014-04-01T23:58:59 Introduce git_apply_patch The beginnings of patch application from an existing (diff-created) git_patch object: applies the hunks of a git_patch to a buffer.
Vicent Marti d7d46cfb 2015-12-16T17:00:25 index: Preallocate the entries vector with size hint
Edward Thomson f1453c59 2015-02-12T12:19:37 Make our overflow check look more like gcc/clang's Make our overflow checking look more like gcc and clang's, so that we can substitute it out with the compiler instrinsics on platforms that support it. This means dropping the ability to pass `NULL` as an out parameter. As a result, the macros also get updated to reflect this as well.
Edward Thomson 3603cb09 2015-02-10T23:13:49 git__*allocarray: safer realloc and malloc Introduce git__reallocarray that checks the product of the number of elements and element size for overflow before allocation. Also introduce git__mallocarray that behaves like calloc, but without the `c`. (It does not zero memory, for those truly worried about every cycle.)
Edward Thomson 392702ee 2015-02-09T23:41:13 allocations: test for overflow of requested size Introduce some helper macros to test integer overflow from arithmetic and set error message appropriately.
Russell Belfer 3b4c401a 2014-02-10T13:20:08 Decouple index iterator sort from index This makes the index iterator honor the GIT_ITERATOR_IGNORE_CASE and GIT_ITERATOR_DONT_IGNORE_CASE flags without modifying the index data itself. To take advantage of this, I had to export a number of the internal index entry comparison functions. I also wrote some new tests to exercise the capability.
Russell Belfer c67fd4c9 2014-02-07T11:20:36 Some vector utility tweaks This is just laying some groundwork for internal index changes that I'm working on.
Vicent Marti 52056db9 2014-04-06T16:22:29 Merge pull request #2250 from jacquesg/vector-leak Don't lose our elements when calling git_vector_set()
Jacques Germishuys 4998009a 2014-04-06T15:06:46 Don't lose our elements when calling git_vector_set()
Russell Belfer aa78c9ba 2014-04-01T10:22:51 Minor submodule cache locking improvements This improvement the management of the lock around submodule cache updates slightly, using the lock to make sure that foreach can safely make a snapshot of all existing submodules and making sure that git_submodule_add_setup also grabs a lock before inserting the new submodule. Cache initialization / refresh should already have been holding the lock correctly as it adds submodules.
Russell Belfer 882c7742 2014-02-04T10:01:37 Convert pqueue to just be a git_vector This updates the git_pqueue to simply be a set of specialized init/insert/pop functions on a git_vector. To preserve the pqueue feature of having a fixed size heap, I converted the "sorted" field in git_vectors to a more general "flags" field so that pqueue could mix in it's own flag. This had a bunch of ramifications because a number of places were directly looking at the vector "sorted" field - I added a couple new git_vector helpers (is_sorted, set_sorted) so the specific representation of this information could be abstracted.
Edward Thomson 39c2302a 2014-01-14T11:19:57 unnecessary include
Russell Belfer 9cfce273 2013-12-12T12:11:38 Cleanups, renames, and leak fixes This renames git_vector_free_all to the better git_vector_free_deep and also contains a couple of memory leak fixes based on valgrind checks. The fixes are specifically: failure to free global dir path variables when not compiled with threading on and failure to free filters from the filter registry that had not be initialized fully.
Russell Belfer 25e0b157 2013-12-06T15:07:57 Remove converting user error to GIT_EUSER This changes the behavior of callbacks so that the callback error code is not converted into GIT_EUSER and instead we propagate the return value through to the caller. Instead of using the giterr_capture and giterr_restore functions, we now rely on all functions to pass back the return value from a callback. To avoid having a return value with no error message, the user can call the public giterr_set_str or some such function to set an error message. There is a new helper 'giterr_set_callback' that functions can invoke after making a callback which ensures that some error message was set in case the callback did not set one. In places where the sign of the callback return value is meaningful (e.g. positive to skip, negative to abort), only the negative values are returned back to the caller, obviously, since the other values allow for continuing the loop. The hardest parts of this were in the checkout code where positive return values were overloaded as meaningful values for checkout. I fixed this by adding an output parameter to many of the internal checkout functions and removing the overload. This added some code, but it is probably a better implementation. There is some funkiness in the network code where user provided callbacks could be returning a positive or a negative value and we want to rely on that to cancel the loop. There are still a couple places where an user error might get turned into GIT_EUSER there, I think, though none exercised by the tests.
Russell Belfer fcd324c6 2013-12-06T15:04:31 Add git_vector_free_all There are a lot of places that we call git__free on each item in a vector and then call git_vector_free on the vector itself. This just wraps that up into one convenient helper function.
nulltoken 191adce8 2013-08-27T20:00:28 vector: Teach git_vector_uniq() to free while deduplicating
Russell Belfer e26b14c0 2013-04-26T15:35:47 Update diff handling of untracked directories When diff encounters an untracked directory, there was a shortcut that it took which is not compatible with core git. This makes the default behavior no longer take that shortcut and instead look inside the untracked directory to see if there are any untracked files within it. If there are not, then the directory is treated as an ignore directory instead of an untracked directory. This has implications for the git_status APIs.
Philip Kelley 590365db 2013-01-29T16:49:12 Now with no multiply
Philip Kelley 11d9f6b3 2013-01-27T14:17:07 Vector improvements and their fallout
Edward Thomson 359fc2d2 2013-01-08T17:07:25 update copyrights
Russell Belfer a8122b5d 2012-11-21T15:39:03 Fix warnings on Win64 build
Russell Belfer 16248ee2 2012-11-21T11:03:07 Fix up some missing consts in tree & index This fixes some missed places where we can apply const-ness to various public APIs. There are still some index and tree APIs that cannot take const pointers because we sort our `git_vectors` lazily and so we can't reliably bsearch the index and tree content without applying a `git_vector_sort()` first. This also fixes some missed places where size_t can be used and where const can be applied to a couple internal functions.
Vicent Martí 1362a983 2012-11-02T10:00:28 Merge pull request #1014 from arrbee/diff-rename-detection Initial implementation of diff rename detection
Russell Belfer db106d01 2012-10-30T09:40:50 Move rename detection into new file This improves the naming for the rename related functionality moving it to be called `git_diff_find_similar()` and renaming all the associated constants, etc. to make more sense. I also moved the new code (plus the existing `git_diff_merge`) into a new file `diff_tform.c` where I can put new functions related to manipulating git diff lists. This also updates the implementation significantly from the last revision fixing some ordering issues (where break-rewrite needs to be handled prior to copy and rename detection) and improving config option handling.
Edward Thomson f45ec1a0 2012-10-29T20:04:21 index refactoring
Philip Kelley ec40b7f9 2012-09-17T15:42:41 Support for core.ignorecase
nulltoken b8457baa 2012-07-24T07:57:58 portability: Improve x86/amd64 compatibility
Vicent Martí 904b67e6 2012-05-18T01:48:50 errors: Rename error codes
Vicent Martí e172cf08 2012-05-18T01:21:06 errors: Rename the generic return codes
Russell Belfer 41a82592 2012-05-15T14:17:39 Ranged iterators and rewritten git_status_file The goal of this work is to rewrite git_status_file to use the same underlying code as git_status_foreach. This is done in 3 phases: 1. Extend iterators to allow ranged iteration with start and end prefixes for the range of file names to be covered. 2. Improve diff so that when there is a pathspec and there is a common non-wildcard prefix of the pathspec, it will use ranged iterators to minimize excess iteration. 3. Rewrite git_status_file to call git_status_foreach_ext with a pathspec that covers just the one file being checked. Since ranged iterators underlie the status & diff implementation, this is actually fairly efficient. The workdir iterator does end up loading the contents of all the directories down to the single file, which should ideally be avoided, but it is pretty good.
Russell Belfer 44ef8b1b 2012-04-13T13:00:10 Fix warnings on 64-bit windows builds This fixes all the warnings on win64 except those in deps, which come from the regex code.
Russell Belfer ae9e29fd 2012-03-06T16:14:31 Migrating diff to new error handling Ended up migrating a bunch of upstream functions as well including vector, attr_file, and odb in order to get this to work right.
Russell Belfer 74fa4bfa 2012-02-28T16:14:47 Update diff to use iterators This is a major reorganization of the diff code. This changes the diff functions to use the iterators for traversing the content. This allowed a lot of code to be simplified. Also, this moved the functions relating to outputting a diff into a new file (diff_output.c). This includes a number of other changes - adding utility functions, extending iterators, etc. plus more tests for the diff code. This also takes the example diff.c program much further in terms of emulating git-diff command line options.
Russell Belfer 0534641d 2012-02-22T15:15:35 Fix iterators based on pull request feedback This update addresses all of the feedback in pull request #570. The biggest change was to create actual linked list stacks for storing the tree and workdir iterator state. This cleaned up the code a ton. Additionally, all of the static functions had their 'git_' prefix removed, and a lot of other unnecessary changes were removed from the original patch.
Russell Belfer b6c93aef 2012-02-21T14:46:24 Uniform iterators for trees, index, and workdir This create a new git_iterator type of object that provides a uniform interface for iterating over the index, an arbitrary tree, or the working directory of a repository. As part of this, git ignore support was extended to support push and pop of directory-based ignore files as the working directory is being traversed (so the array of ignores does not have to be recreated at each directory during traveral). There are a number of other small utility functions in buffer, path, vector, and fileops that are included in this patch that made the iterator implementation cleaner.
schu 5e0de328 2012-02-13T17:10:24 Update Copyright header Signed-off-by: schu <schu-github@schulog.org>
Russell Belfer bd370b14 2011-12-30T15:00:14 Improved gitattributes macro implementation This updates to implementation of gitattribute macros to be much more similar to core git (albeit not 100%) and to handle expansion of macros within macros, etc. It also cleans up the refcounting usage with macros to be much cleaner. Also, this adds a new vector function `git_vector_insert_sorted()` which allows you to maintain a sorted list as you go. In order to write that function, this changes the function `git__bsearch()` to take a somewhat different set of parameters, although the core functionality is still the same.
Russell Belfer ee1f0b1a 2011-12-16T10:56:43 Add APIs for git attributes This adds APIs for querying git attributes. In addition to the new API in include/git2/attr.h, most of the action is in src/attr_file.[hc] which contains utilities for dealing with a single attributes file, and src/attr.[hc] which contains the implementation of the APIs that merge all applicable attributes files.
Vicent Marti 3286c408 2011-10-28T14:51:13 global: Properly use `git__` memory wrappers Ensure that all memory related functions (malloc, calloc, strdup, free, etc) are using their respective `git__` wrappers.
Vicent Marti bb742ede 2011-09-19T01:54:32 Cleanup legal data 1. The license header is technically not valid if it doesn't have a copyright signature. 2. The COPYING file has been updated with the different licenses used in the project. 3. The full GPLv2 header in each file annoys me.
Vicent Marti de18f276 2011-07-07T01:46:20 vector: Timsort all of the things Drop the GLibc implementation of Merge Sort and replace it with Timsort. The algorithm has been tuned to work on arrays of pointers (void **), so there's no longer a need to abstract the byte-width of each element in the array. All the comparison callbacks now take pointers-to-elements, not pointers-to-pointers, so there's now one less level of dereferencing. E.g. int index_cmp(const void *a, const void *b) { - const git_index_entry *entry_a = *(const git_index_entry **)(a); + const git_index_entry *entry_a = (const git_index_entry *)(a); The result is up to a 40% speed-up when sorting vectors. Memory usage remains lineal. A new `bsearch` implementation has been added, whose callback also supplies pointer-to-elements, to uniform the Vector API again.
Kirill A. Shutemov 476c42ac 2011-07-02T00:41:49 vector: implement git_vector_uniq() The routine remove duplictes from the vector. Only the last added element of elements with equal keys remains in the vector. Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
Kirill A. Shutemov 0b0a6b11 2011-07-01T00:48:37 vector, index: use git__msort() for vector sorting Index operation use git_vector_sort() to sort index entries. Since index support adding duplicates (two or more entries with the same path), it's important to preserve order of elements. Preserving order of elements allows to make decisions based on order. For example it's possible to implement function witch removes all duplicates except last added. Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
Kirill A. Shutemov 932d1baf 2011-06-30T19:52:34 cleanup: remove trailing spaces Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
schu 86f5fa78 2011-05-11T14:00:38 Move vector.c to the new error handling Remove "redundant" check for v->_cmp in wrapper function git_vector_bsearch(). Signed-off-by: schu <schu-github@schulog.org>
Vicent Marti 3c41c635 2011-03-03T21:58:37 Fix compilation in MSVC MSVC cannot substract void pointers. Go figure. Signed-off-by: Vicent Marti <tanoku@gmail.com>
Vicent Marti 48c27f86 2011-02-28T16:51:17 Implement reference counting for git_objects All `git_object` instances looked up from the repository are reference counted. User is expected to use the new `git_object_close` when an object is no longer needed to force freeing it. Signed-off-by: Vicent Marti <tanoku@gmail.com>
Vicent Marti 86d7e1ca 2011-02-28T12:46:13 Fix searching in git_vector We now store only one sorting callback that does entry comparison. This is used when sorting the entries using a quicksort, and when looking for a specific entry with the new search methods. The following search methods now exist: git_vector_search(vector, entry) git_vector_search2(vector, custom_search_callback, key) git_vector_bsearch(vector, entry) git_vector_bsearch2(vector, custom_search_callback, key) The sorting state of the vector is now stored internally. Signed-off-by: Vicent Marti <tanoku@gmail.com>
Vicent Marti da7c3c71 2011-02-27T22:07:39 Fix warnings in vector.c Signed-off-by: Vicent Marti <tanoku@gmail.com>
Vicent Marti 86194b24 2011-02-18T21:57:53 Split packed from unpacked references These two reference types are now stored separately to eventually allow the removal/renaming of loose references and rewriting of the refs packfile. Signed-off-by: Vicent Marti <tanoku@gmail.com>
Alex Budovski a17777d1 2011-01-07T11:35:43 Fixed two buffer handling errors in vector.c - remove() would read one-past array bounds. - resize() would fail if the initial size was 1, because it multiplied by 1.75 and truncated the resulting value. The buffer would always remain at size 1, but elements would repeatedly be appended (via insert()) causing a crash.
Vicent Marti a44fc1d4 2010-12-06T23:13:00 Fix type-conversion warnings The types in the git_index_entry struct are now system-defaults, and get truncated to uint32_t's when written back on the index. Signed-off-by: Vicent Marti <tanoku@gmail.com>
Vicent Marti c4034e63 2010-12-02T04:31:54 Refactor all 'vector' functions into common code All the operations on the 'git_index_entry' array and the 'git_tree_entry' array have been refactored into common code in the src/vector.c file. The new vector methods support: - insertion: O(1) (avg) - deletion: O(n) - searching: O(logn) - sorting: O(logn) - r. access: O(1) Signed-off-by: Vicent Marti <tanoku@gmail.com>