]> git.proxmox.com Git - libgit2.git/commit
vector: Timsort all of the things
authorVicent Marti <tanoku@gmail.com>
Wed, 6 Jul 2011 23:46:20 +0000 (01:46 +0200)
committerVicent Marti <tanoku@gmail.com>
Thu, 7 Jul 2011 00:54:07 +0000 (02:54 +0200)
commitde18f276683a5cf3d85d001f6521e52c8c802e60
tree01db449c1fa2d11568aca66bf4a5ef9d1a5c60f3
parentc63aa494595a6d6e6d97cfa1bbc1741a0b2e0cc6
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.
src/config.c
src/index.c
src/odb.c
src/odb_pack.c
src/refs.c
src/tree.c
src/tsort.c [new file with mode: 0644]
src/util.c
src/util.h
src/vector.c
tests/t00-core.c