src/vector.c


Log

Author Commit Date CI Message
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 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 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 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>