|
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.
|
|
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>
|
|
|
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>
|
|
|
932d1baf
|
2011-06-30T19:52:34
|
|
cleanup: remove trailing spaces
Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
|
|
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>
|
|
|
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>
|
|
|
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>
|
|
|
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>
|
|
|
da7c3c71
|
2011-02-27T22:07:39
|
|
Fix warnings in vector.c
Signed-off-by: Vicent Marti <tanoku@gmail.com>
|
|
|
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>
|
|
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.
|
|
|
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>
|
|
|
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>
|