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, 3 insertions, 3 deletions

diff --git a/src/vector.c b/src/vector.c
index 2fc051f0c..0b83b8b0d 100644
--- a/src/vector.c
+++ b/src/vector.c
@@ -94,7 +94,7 @@ void git_vector_sort(git_vector *v)
 	if (v->sorted || v->_cmp == NULL)
 		return;
 
-	git__msort(v->contents, v->length, sizeof(void *), v->_cmp);
+	git__tsort(v->contents, v->length, v->_cmp);
 	v->sorted = 1;
 }
 
@@ -110,7 +110,7 @@ int git_vector_bsearch2(git_vector *v, git_vector_cmp key_lookup, const void *ke
 
 	git_vector_sort(v);
 
-	find = bsearch(key, v->contents, v->length, sizeof(void *), key_lookup);
+	find = git__bsearch(key, v->contents, v->length, key_lookup);
 	if (find != NULL)
 		return (int)(find - v->contents);
 
@@ -174,7 +174,7 @@ void git_vector_uniq(git_vector *v)
 	cmp = v->_cmp ? v->_cmp : strict_comparison;
 
 	for (i = 0, j = 1 ; j < v->length; ++j)
-		if (!cmp(v->contents + i, v->contents + j))
+		if (!cmp(v->contents[i], v->contents[j]))
 			v->contents[i] = v->contents[j];
 		else
 			v->contents[++i] = v->contents[j];