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/util.h | |
| 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/util.h')
| -rw-r--r-- | src/util.h | 5 |
1 files changed, 3 insertions, 2 deletions
diff --git a/src/util.h b/src/util.h index c9ca4dec0..410ebfb26 100644 --- a/src/util.h +++ b/src/util.h @@ -118,7 +118,8 @@ extern int git__fnmatch(const char *pattern, const char *name, int flags); } \ } while (0) -extern int git__msort(void *b, size_t n, size_t s, - int (*cmp)(const void *, const void *)); +extern int git__tsort(void **b, size_t n, int (*cmp)(const void *, const void *)); +extern void **git__bsearch(const void *key, void **base, size_t nmemb, + int (*compar)(const void *, const void *)); #endif /* INCLUDE_util_h__ */ |