diff options
| author | Vicent Marti <tanoku@gmail.com> | 2011-07-07 01:46:20 +0200 |
|---|---|---|
| committer | Vicent Marti <tanoku@gmail.com> | 2011-07-07 02:54:07 +0200 |
| commit | de18f276683a5cf3d85d001f6521e52c8c802e60 (patch) | |
| tree | 01db449c1fa2d11568aca66bf4a5ef9d1a5c60f3 /src/odb_pack.c | |
| parent | c63aa494595a6d6e6d97cfa1bbc1741a0b2e0cc6 (diff) | |
| download | libgit2-de18f276683a5cf3d85d001f6521e52c8c802e60.tar.gz | |
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.
Diffstat (limited to 'src/odb_pack.c')
| -rw-r--r-- | src/odb_pack.c | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/src/odb_pack.c b/src/odb_pack.c index 44604ef91..20b0f1e4d 100644 --- a/src/odb_pack.c +++ b/src/odb_pack.c @@ -699,8 +699,8 @@ static int pack_index_open(struct pack_file *p) static int packfile_sort__cb(const void *a_, const void *b_) { - struct pack_file *a = *((struct pack_file **)a_); - struct pack_file *b = *((struct pack_file **)b_); + struct pack_file *a = (struct pack_file *)a_; + struct pack_file *b = (struct pack_file *)b_; int st; /* |