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.

1 files changed, 6 insertions, 6 deletions

diff --git a/src/index.c b/src/index.c
index dd33db92a..353c30025 100644
--- a/src/index.c
+++ b/src/index.c
@@ -109,15 +109,15 @@ static int write_index(git_index *index, git_filebuf *file);
 int index_srch(const void *key, const void *array_member)
 {
 	const char *filename = (const char *)key;
-	const git_index_entry *entry = *(const git_index_entry **)(array_member);
+	const git_index_entry *entry = (const git_index_entry *)(array_member);
 
 	return strcmp(filename, entry->path);
 }
 
 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_b = *(const git_index_entry **)(b);
+	const git_index_entry *entry_a = (const git_index_entry *)(a);
+	const git_index_entry *entry_b = (const git_index_entry *)(b);
 
 	return strcmp(entry_a->path, entry_b->path);
 }
@@ -125,15 +125,15 @@ int index_cmp(const void *a, const void *b)
 int unmerged_srch(const void *key, const void *array_member)
 {
 	const char *path = (const char *) key;
-	const git_index_entry_unmerged *entry = *(const git_index_entry_unmerged **) (array_member);
+	const git_index_entry_unmerged *entry = (const git_index_entry_unmerged *)(array_member);
 
 	return strcmp(path, entry->path);
 }
 
 int unmerged_cmp(const void *a, const void *b)
 {
-	const git_index_entry_unmerged *info_a = *(const git_index_entry_unmerged **)(a);
-	const git_index_entry_unmerged *info_b = *(const git_index_entry_unmerged **)(b);
+	const git_index_entry_unmerged *info_a = (const git_index_entry_unmerged *)(a);
+	const git_index_entry_unmerged *info_b = (const git_index_entry_unmerged *)(b);
 
 	return strcmp(info_a->path, info_b->path);
 }