Refactor all 'vector' functions into common code

All the operations on the 'git_index_entry' array and the
'git_tree_entry' array have been refactored into common code in the
src/vector.c file.

The new vector methods support:
	- insertion:	O(1) (avg)
	- deletion:		O(n)
	- searching:	O(logn)
	- sorting:		O(logn)
	- r. access:	O(1)

Signed-off-by: Vicent Marti <tanoku@gmail.com>

8 files changed, 331 insertions, 214 deletions

diff --git a/src/index.c b/src/index.c
index bb8cddd85..488a60abe 100644
--- a/src/index.c
+++ b/src/index.c
@@ -99,6 +99,23 @@ static int read_tree(git_index *index, const char *buffer, size_t buffer_size);
 static git_index_tree *read_tree_internal(const char **, const char *, git_index_tree *);
 
 
+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);
+
+	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);
+
+	return strcmp(entry_a->path, entry_b->path);
+}
+
+
 static int index_initialize(git_index **index_out, git_repository *owner, const char *index_path)
 {
 	git_index *index;
@@ -119,6 +136,8 @@ static int index_initialize(git_index **index_out, git_repository *owner, const
 
 	index->repository = owner;
 
+	git_vector_init(&index->entries, 32, index_cmp, index_srch);
+
 	/* Check if index file is stored on disk already */
 	if (gitfo_exists(index->index_file_path) == 0)
 		index->on_disk = 1;
@@ -146,10 +165,14 @@ void git_index_clear(git_index *index)
 
 	assert(index);
 
-	for (i = 0; i < index->entry_count; ++i)
-		free(index->entries[i].path);
+	for (i = 0; i < index->entries.length; ++i) {
+		git_index_entry *e;
+		e = git_vector_get(&index->entries, i);
+		free(e->path);
+		free(e);
+	}
 
-	index->entry_count = 0;
+	git_vector_clear(&index->entries);
 	index->last_modified = 0;
 	index->sorted = 1;
 
@@ -163,8 +186,8 @@ void git_index_free(git_index *index)
 		return;
 
 	git_index_clear(index);
-	free(index->entries);
-	index->entries = NULL;
+	git_vector_free(&index->entries);
+
 	free(index->index_file_path);
 	free(index);
 }
@@ -241,13 +264,14 @@ int git_index_write(git_index *index)
 unsigned int git_index_entrycount(git_index *index)
 {
 	assert(index);
-	return index->entry_count;
+	return index->entries.length;
 }
 
 git_index_entry *git_index_get(git_index *index, int n)
 {
 	assert(index);
-	return (n >= 0 && (unsigned int)n < index->entry_count) ? &index->entries[n] : NULL;
+	git_index__sort(index);
+	return git_vector_get(&index->entries, (unsigned int)n);
 }
 
 int git_index_add(git_index *index, const char *rel_path, int stage)
@@ -297,31 +321,15 @@ int git_index_add(git_index *index, const char *rel_path, int stage)
 
 void git_index__sort(git_index *index)
 {
-	git_index_entry pivot;
-	int i, j;
-
-	if (index->sorted)
-		return;
-
-	for (i = 1; i < (int)index->entry_count; ++i) {
-
-		memcpy(&pivot, &index->entries[i], sizeof(git_index_entry));
-		j = i - 1;
-
-		while (j >= 0 && strcmp(pivot.path, index->entries[j].path) < 0) {
-			memcpy(&index->entries[j + 1], &index->entries[j], sizeof(git_index_entry));
-			j = j - 1;
-		}
-
-		memcpy(&index->entries[j + 1], &pivot, sizeof(git_index_entry));
+	if (index->sorted == 0) {
+		git_vector_sort(&index->entries);
+		index->sorted = 1;
 	}
-
-	index->sorted = 1;
 }
 
 int git_index_insert(git_index *index, const git_index_entry *source_entry)
 {
-	git_index_entry *offset;
+	git_index_entry *entry;
 	size_t path_length;
 	int position;
 
@@ -330,107 +338,63 @@ int git_index_insert(git_index *index, const git_index_entry *source_entry)
 	if (source_entry->path == NULL)
 		return GIT_EMISSINGOBJDATA;
 
-	position = git_index_find(index, source_entry->path);
-
-	if (position == GIT_ENOTFOUND) {
-
-		/* Resize the entries array */
-		if (index->entry_count + 1 > index->entries_size) {
-			git_index_entry *new_entries;
-			size_t new_size;
-
-			new_size = (unsigned int)(index->entries_size * 1.5f);
-			if (new_size < 8)
-				new_size = 8;
-
-			if ((new_entries = git__malloc(new_size * sizeof(git_index_entry))) == NULL)
-				return GIT_ENOMEM;
-
-			memcpy(new_entries, index->entries, index->entry_count * sizeof(git_index_entry));
-			free(index->entries);
-
-			index->entries_size = new_size;
-			index->entries = new_entries;
-		}
-
-		offset = &index->entries[index->entry_count];
-		index->entry_count++;
-		index->sorted = 0;
-
-	} else {
-		offset = &index->entries[position];
-		free(offset->path);
-	}
+	entry = git__malloc(sizeof(git_index_entry));
+	if (entry == NULL)
+		return GIT_ENOMEM;
 
-	memcpy(offset, source_entry, sizeof(git_index_entry));
+	memcpy(entry, source_entry, sizeof(git_index_entry));
 
 	/* duplicate the path string so we own it */
-	offset->path = git__strdup(offset->path);
-	if (offset->path == NULL)
+	entry->path = git__strdup(entry->path);
+	if (entry->path == NULL)
 		return GIT_ENOMEM;
 
 	/* make sure that the path length flag is correct */
-	path_length = strlen(offset->path);
+	path_length = strlen(entry->path);
 
-	offset->flags &= ~GIT_IDXENTRY_NAMEMASK;
+	entry->flags &= ~GIT_IDXENTRY_NAMEMASK;
 
 	if (path_length < GIT_IDXENTRY_NAMEMASK)
-		offset->flags |= path_length & GIT_IDXENTRY_NAMEMASK;
+		entry->flags |= path_length & GIT_IDXENTRY_NAMEMASK;
 	else
-		offset->flags |= GIT_IDXENTRY_NAMEMASK;;
+		entry->flags |= GIT_IDXENTRY_NAMEMASK;;
 
-	/* TODO: force the extended index entry flag? */
 
-	assert(offset->path);
-
-	return GIT_SUCCESS;
-}
+	/* look if an entry with this path already exists */
+	position = git_index_find(index, source_entry->path);
 
-int git_index_remove(git_index *index, int position)
-{
-	git_index_entry *offset;
-	size_t copy_size;
+	/* if no entry exists, add the entry at the end;
+	 * the index is no longer sorted */
+	if (position == GIT_ENOTFOUND) {
+		if (git_vector_insert(&index->entries, entry) < 0)
+			return GIT_ENOMEM;
 
-	assert(index);
+		index->sorted = 0;
 
-	if (position < 0 || (unsigned int)position > index->entry_count)
-		return GIT_ENOTFOUND;
+	/* if a previous entry exists, replace it */
+	} else {
+		git_index_entry **entry_array = (git_index_entry **)index->entries.contents;
 
-	offset = &index->entries[position];
-	index->entry_count--;
-	copy_size = (index->entry_count - position) * sizeof(git_index_entry);
+		free(entry_array[position]->path);
+		free(entry_array[position]);
 
-	memcpy(offset, offset + sizeof(git_index_entry), copy_size);
+		entry_array[position] = entry;
+	}
 
 	return GIT_SUCCESS;
 }
 
-int git_index_find(git_index *index, const char *path)
+int git_index_remove(git_index *index, int position)
 {
-	int low = 0, high = index->entry_count;
-
-	if (!index->sorted)
-		git_index__sort(index);
-
-	while (low < high) {
-		int mid = (low + high) >> 1;
-		int cmp = strcmp(path, index->entries[mid].path);
-
-		if (cmp < 0)
-			high = mid;
-
-		else if (cmp == 0) {
-
-			while (mid > 0 && strcmp(path, index->entries[mid - 1].path) == 0)
-				mid--;
-
-			return mid;
-
-		} else
-			low = mid + 1;
-	}
+	assert(index);
+	git_index__sort(index);
+	return git_vector_remove(&index->entries, (unsigned int)position);
+}
 
-	return GIT_ENOTFOUND; /* NOT FOUND */
+int git_index_find(git_index *index, const char *path)
+{
+	git_index__sort(index);
+	return git_vector_search(&index->entries, path);
 }
 
 void git_index_tree__free(git_index_tree *tree)
@@ -659,29 +623,30 @@ int git_index__parse(git_index *index, const char *buffer, size_t buffer_size)
 
 	seek_forward(INDEX_HEADER_SIZE);
 
-	index->entry_count = header.entry_count;
-
-	/* If there is already a entires array, reuse it if it can hold all the
-	 * entries. If not, free and reallocate */
-	if (index->entry_count > index->entries_size) {
-		free(index->entries);
-		index->entries_size = (uint32_t)(index->entry_count * 1.3f);
-		index->entries = git__malloc(index->entries_size * sizeof(git_index_entry));
-	}
+	git_vector_clear(&index->entries);
 
 	/* Parse all the entries */
-	for (i = 0; i < index->entry_count && buffer_size > INDEX_FOOTER_SIZE; ++i) {
+	for (i = 0; i < header.entry_count && buffer_size > INDEX_FOOTER_SIZE; ++i) {
 		size_t entry_size;
-		entry_size = read_entry(&index->entries[i], buffer, buffer_size);
+		git_index_entry *entry;
+
+		entry = git__malloc(sizeof(git_index_entry));
+		if (entry == NULL)
+			return GIT_ENOMEM;
+
+		entry_size = read_entry(entry, buffer, buffer_size);
 
 		/* 0 bytes read means an object corruption */
 		if (entry_size == 0)
 			return GIT_EOBJCORRUPTED;
 
+		if (git_vector_insert(&index->entries, entry) < 0)
+			return GIT_ENOMEM;
+
 		seek_forward(entry_size);
 	}
 
-	if (i != index->entry_count)
+	if (i != header.entry_count)
 		return GIT_EOBJCORRUPTED;
 
 	/* There's still space for some extensions! */
@@ -746,13 +711,13 @@ int git_index__write(git_index *index, git_filelock *file)
 	WRITE_BYTES(INDEX_HEADER_SIG, 4);
 
 	WRITE_WORD(INDEX_VERSION_NUMBER);
-	WRITE_WORD(index->entry_count);
+	WRITE_WORD(index->entries.length);
 
-	for (i = 0; i < index->entry_count; ++i) {
+	for (i = 0; i < index->entries.length; ++i) {
 		git_index_entry *entry;
 		size_t path_length, padding;
 
-		entry = &index->entries[i];
+		entry = git_vector_get(&index->entries, i);
 		path_length = strlen(entry->path);
 
 		WRITE_WORD(entry->ctime.seconds);
diff --git a/src/index.h b/src/index.h
index 658404953..f548c7b68 100644
--- a/src/index.h
+++ b/src/index.h
@@ -3,6 +3,7 @@
 
 #include "fileops.h"
 #include "filelock.h"
+#include "vector.h"
 #include "git/odb.h"
 #include "git/index.h"
 
@@ -24,11 +25,8 @@ struct git_index {
 	char *index_file_path;
 
 	time_t last_modified;
+	git_vector entries;
 
-	git_index_entry *entries;
-	unsigned int entries_size;
-
-	unsigned int entry_count;
 	unsigned int sorted:1,
 				 on_disk:1;
 
diff --git a/src/tree.c b/src/tree.c
index 9dd407d7e..2eeba7235 100644
--- a/src/tree.c
+++ b/src/tree.c
@@ -29,27 +29,7 @@
 #include "tree.h"
 #include "git/repository.h"
 
-static int resize_tree_array(git_tree *tree)
-{
-	git_tree_entry **new_entries;
-
-	tree->array_size *= 2; 
-	if (tree->array_size == 0)
-		tree->array_size = 8;
-
-	new_entries = git__malloc(tree->array_size * sizeof(git_tree_entry *));
-	if (new_entries == NULL)
-		return GIT_ENOMEM;
-
-	memcpy(new_entries, tree->entries, tree->entry_count * sizeof(git_tree_entry *));
-
-	free(tree->entries);
-	tree->entries = new_entries;
-
-	return GIT_SUCCESS;
-}
-
-int entry_cmp(const void *key, const void *array_member)
+int entry_search_cmp(const void *key, const void *array_member)
 {
 	const char *filename = (const char *)key;
 	const git_tree_entry *entry = *(const git_tree_entry **)(array_member);
@@ -65,24 +45,22 @@ int entry_sort_cmp(const void *a, const void *b)
 	return strcmp(entry_a->filename, entry_b->filename);
 }
 
-static void entry_resort(git_tree *tree)
-{
-	qsort(tree->entries, tree->entry_count, sizeof(git_tree_entry *), entry_sort_cmp);
-}
-
 static void free_tree_entries(git_tree *tree)
 {
-	size_t i;
+	unsigned int i;
 
 	if (tree == NULL)
 		return;
 
-	for (i = 0; i < tree->entry_count; ++i) {
-		free(tree->entries[i]->filename);
-		free(tree->entries[i]);
+	for (i = 0; i < tree->entries.length; ++i) {
+		git_tree_entry *e;
+		e = git_vector_get(&tree->entries, i);
+
+		free(e->filename);
+		free(e);
 	}
 
-	free(tree->entries);
+	git_vector_free(&tree->entries);
 }
 
 
@@ -112,7 +90,7 @@ void git_tree_entry_set_name(git_tree_entry *entry, const char *name)
 
 	free(entry->filename);
 	entry->filename = git__strdup(name);
-	entry_resort(entry->owner);
+	git_vector_sort(&entry->owner->entries);
 	entry->owner->object.modified = 1;
 }
 
@@ -149,28 +127,27 @@ int git_tree_entry_2object(git_object **object_out, git_tree_entry *entry)
 
 git_tree_entry *git_tree_entry_byname(git_tree *tree, const char *filename)
 {
-	git_tree_entry **found;
+	int idx;
 
 	assert(tree && filename);
 
-	found = bsearch(filename, tree->entries, tree->entry_count, sizeof(git_tree_entry *), entry_cmp);
-	return found ? *found : NULL;
+	idx = git_vector_search(&tree->entries, filename);
+	if (idx == GIT_ENOTFOUND)
+		return NULL;
+
+	return git_vector_get(&tree->entries, idx);
 }
 
 git_tree_entry *git_tree_entry_byindex(git_tree *tree, int idx)
 {
 	assert(tree);
-
-	if (tree->entries == NULL)
-		return NULL;
-
-	return (idx >= 0 && idx < (int)tree->entry_count) ? tree->entries[idx] : NULL;
+	return git_vector_get(&tree->entries, (unsigned int)idx);
 }
 
 size_t git_tree_entrycount(git_tree *tree)
 {
 	assert(tree);
-	return tree->entry_count;
+	return tree->entries.length;
 }
 
 int git_tree_add_entry(git_tree *tree, const git_oid *id, const char *filename, int attributes)
@@ -179,10 +156,6 @@ int git_tree_add_entry(git_tree *tree, const git_oid *id, const char *filename,
 
 	assert(tree && id && filename);
 
-	if (tree->entry_count >= tree->array_size)
-		if (resize_tree_array(tree) < 0)
-			return GIT_ENOMEM;
-
 	if ((entry = git__malloc(sizeof(git_tree_entry))) == NULL)
 		return GIT_ENOMEM;
 
@@ -193,8 +166,10 @@ int git_tree_add_entry(git_tree *tree, const git_oid *id, const char *filename,
 	entry->attr = attributes;
 	entry->owner = tree;
 
-	tree->entries[tree->entry_count++] = entry;
-	entry_resort(tree);
+	if (git_vector_insert(&tree->entries, entry) < 0)
+		return GIT_ENOMEM;
+
+	git_vector_sort(&tree->entries);
 
 	tree->object.modified = 1;
 	return GIT_SUCCESS;
@@ -206,32 +181,28 @@ int git_tree_remove_entry_byindex(git_tree *tree, int idx)
 
 	assert(tree);
 
-	if (idx < 0 || idx >= (int)tree->entry_count)
+	remove_ptr = git_vector_get(&tree->entries, (unsigned int)idx);
+	if (remove_ptr == NULL)
 		return GIT_ENOTFOUND;
 
-	remove_ptr = tree->entries[idx];
-	tree->entries[idx] = tree->entries[--tree->entry_count];
-
 	free(remove_ptr->filename);
 	free(remove_ptr);
-	entry_resort(tree);
 
 	tree->object.modified = 1;
-	return GIT_SUCCESS;
+
+	return git_vector_remove(&tree->entries, (unsigned int)idx);
 }
 
 int git_tree_remove_entry_byname(git_tree *tree, const char *filename)
 {
-	git_tree_entry **entry_ptr;
 	int idx;
 
 	assert(tree && filename);
 
-	entry_ptr = bsearch(filename, tree->entries, tree->entry_count, sizeof(git_tree_entry *), entry_cmp);
-	if (entry_ptr == NULL)
+	idx = git_vector_search(&tree->entries, filename);
+	if (idx == GIT_ENOTFOUND)
 		return GIT_ENOTFOUND;
 
-	idx = (int)(entry_ptr - tree->entries);
 	return git_tree_remove_entry_byindex(tree, idx);
 }
 
@@ -242,14 +213,15 @@ int git_tree__writeback(git_tree *tree, git_odb_source *src)
 
 	assert(tree && src);
 
-	if (tree->entries == NULL)
+	if (tree->entries.length == 0)
 		return GIT_EMISSINGOBJDATA;
 
-	entry_resort(tree);
+	git_vector_sort(&tree->entries);
 
-	for (i = 0; i < tree->entry_count; ++i) {
+	for (i = 0; i < tree->entries.length; ++i) {
 		git_tree_entry *entry;
-		entry = tree->entries[i];
+
+		entry = git_vector_get(&tree->entries, i);
 	
 		sprintf(filemode, "%06o ", entry->attr);
 
@@ -265,31 +237,26 @@ int git_tree__writeback(git_tree *tree, git_odb_source *src)
 static int tree_parse_buffer(git_tree *tree, char *buffer, char *buffer_end)
 {
 	static const size_t avg_entry_size = 40;
+	unsigned int expected_size;
 	int error = 0;
 
-	free_tree_entries(tree);
-
-	tree->entry_count = 0;
-	tree->array_size = (tree->object.source.raw.len / avg_entry_size) + 1;
-	tree->entries = git__malloc(tree->array_size * sizeof(git_tree_entry *));
+	expected_size = (tree->object.source.raw.len / avg_entry_size) + 1;
 
-	if (tree->entries == NULL)
+	free_tree_entries(tree);
+	if (git_vector_init(&tree->entries, expected_size, entry_sort_cmp, entry_search_cmp) < 0)
 		return GIT_ENOMEM;
 
 	while (buffer < buffer_end) {
 		git_tree_entry *entry;
 
-		if (tree->entry_count >= tree->array_size)
-			if (resize_tree_array(tree) < 0)
-				return GIT_ENOMEM;
-
 		entry = git__malloc(sizeof(git_tree_entry));
 		if (entry == NULL) {
 			error = GIT_ENOMEM;
 			break;
 		}
 
-		tree->entries[tree->entry_count++] = entry;
+		if (git_vector_insert(&tree->entries, entry) < 0)
+			return GIT_ENOMEM;
 
 		entry->owner = tree;
 		entry->attr = strtol(buffer, &buffer, 8);
diff --git a/src/tree.h b/src/tree.h
index db1c19ffe..84d02222f 100644
--- a/src/tree.h
+++ b/src/tree.h
@@ -3,6 +3,7 @@
 
 #include <git/tree.h>
 #include "repository.h"
+#include "vector.h"
 
 struct git_tree_entry {
 	unsigned int attr;
@@ -14,10 +15,7 @@ struct git_tree_entry {
 
 struct git_tree {
 	git_object object;
-
-	git_tree_entry **entries;
-	size_t entry_count;
-	size_t array_size;
+	git_vector entries;
 };
 
 void git_tree__free(git_tree *tree);
diff --git a/src/vector.c b/src/vector.c
new file mode 100644
index 000000000..3f76df207
--- /dev/null
+++ b/src/vector.c
@@ -0,0 +1,146 @@
+/*
+ * This file is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License, version 2,
+ * as published by the Free Software Foundation.
+ *
+ * In addition to the permissions in the GNU General Public License,
+ * the authors give you unlimited permission to link the compiled
+ * version of this file into combinations with other programs,
+ * and to distribute those combinations without any restriction
+ * coming from the use of this file.  (The General Public License
+ * restrictions do apply in other respects; for example, they cover
+ * modification of the file, and distribution when not linked into
+ * a combined executable.)
+ *
+ * This file is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; see the file COPYING.  If not, write to
+ * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#include "common.h"
+#include "repository.h"
+#include "vector.h"
+
+static const double resize_factor = 1.75;
+static const int minimum_size = 8;
+
+static int resize_vector(git_vector *v)
+{
+	void **new_contents;
+
+	v->_alloc_size *= resize_factor; 
+	if (v->_alloc_size == 0)
+		v->_alloc_size = minimum_size;
+
+	new_contents = git__malloc(v->_alloc_size * sizeof(void *));
+	if (new_contents == NULL)
+		return GIT_ENOMEM;
+
+	memcpy(new_contents, v->contents, v->length * sizeof(void *));
+
+	free(v->contents);
+	v->contents = new_contents;
+
+	return GIT_SUCCESS;
+}
+
+
+void git_vector_free(git_vector *v)
+{
+	assert(v);
+	free(v->contents);
+}
+
+int git_vector_init(git_vector *v, unsigned int initial_size, git_vector_cmp cmp, git_vector_srch srch)
+{
+	assert(v);
+
+	memset(v, 0x0, sizeof(git_vector));
+
+	if (initial_size == 0)
+		initial_size = minimum_size;
+
+	v->_alloc_size = initial_size;
+	v->_cmp = cmp;
+	v->_srch = srch;
+	
+	v->length = 0;
+
+	v->contents = git__malloc(v->_alloc_size * sizeof(void *));
+	if (v->contents == NULL)
+		return GIT_ENOMEM;
+
+	return GIT_SUCCESS;
+}
+
+int git_vector_insert(git_vector *v, void *element)
+{
+	assert(v);
+
+	if (v->length >= v->_alloc_size) {
+		if (resize_vector(v) < 0)
+			return GIT_ENOMEM;
+	}
+
+	v->contents[v->length++] = element;
+
+	return GIT_SUCCESS;
+}
+
+void *git_vector_get(git_vector *v, unsigned int position)
+{
+	assert(v);
+	return (position < v->length) ? v->contents[position] : NULL;
+}
+
+void git_vector_sort(git_vector *v)
+{
+	assert(v);
+
+	if (v->_cmp != NULL)
+		qsort(v->contents, v->length, sizeof(void *), v->_cmp);
+}
+
+int git_vector_search(git_vector *v, const void *key)
+{
+	void **find;
+
+	if (v->_srch == NULL)
+		return GIT_ENOTFOUND;
+
+	find = bsearch(key, v->contents, v->length, sizeof(void *), v->_srch);
+	if (find == NULL)
+		return GIT_ENOTFOUND;
+
+	return (int)(find - v->contents);
+}
+
+int git_vector_remove(git_vector *v, unsigned int idx)
+{
+	unsigned int i;
+
+	assert(v);
+
+	if (idx >= v->length || v->length == 0)
+		return GIT_ENOTFOUND;
+
+	for (i = idx; i < v->length; ++i)
+		v->contents[i] = v->contents[i + 1];
+
+	v->length--;
+	return GIT_SUCCESS;
+}
+
+void git_vector_clear(git_vector *v)
+{
+	assert(v);
+	v->length = 0;
+}
+
+
diff --git a/src/vector.h b/src/vector.h
new file mode 100644
index 000000000..8239abade
--- /dev/null
+++ b/src/vector.h
@@ -0,0 +1,32 @@
+#ifndef INCLUDE_vector_h__
+#define INCLUDE_vector_h__
+
+#include "git/common.h"
+
+
+typedef int (*git_vector_cmp)(const void *, const void *);
+typedef int (*git_vector_srch)(const void *, const void *);
+
+typedef struct git_vector {
+	unsigned int _alloc_size;
+	git_vector_cmp _cmp;
+	git_vector_srch _srch;
+
+	void **contents;
+	unsigned int length;
+} git_vector;
+
+
+int git_vector_init(git_vector *v, unsigned int initial_size, git_vector_cmp cmp, git_vector_srch srch);
+void git_vector_free(git_vector *v);
+void git_vector_clear(git_vector *v);
+
+int git_vector_search(git_vector *v, const void *key);
+void git_vector_sort(git_vector *v);
+
+void *git_vector_get(git_vector *v, unsigned int position);
+
+int git_vector_insert(git_vector *v, void *element);
+int git_vector_remove(git_vector *v, unsigned int idx);
+
+#endif
diff --git a/tests/t0601-read.c b/tests/t0601-read.c
index 615674509..6ddb5fba8 100644
--- a/tests/t0601-read.c
+++ b/tests/t0601-read.c
@@ -35,7 +35,7 @@ BEGIN_TEST(index_loadempty_test)
 	must_pass(git_index_read(index));
 
 	must_be_true(index->on_disk == 0);
-	must_be_true(index->entry_count == 0);
+	must_be_true(git_index_entrycount(index) == 0);
 	must_be_true(index->sorted);
 
 	git_index_free(index);
@@ -44,6 +44,7 @@ END_TEST
 BEGIN_TEST(index_load_test)
 	git_index *index;
 	unsigned int i;
+	git_index_entry **entries;
 
 	must_pass(git_index_open_bare(&index, TEST_INDEX_PATH));
 	must_be_true(index->on_disk);
@@ -51,11 +52,13 @@ BEGIN_TEST(index_load_test)
 	must_pass(git_index_read(index));
 
 	must_be_true(index->on_disk);
-	must_be_true(index->entry_count == TEST_INDEX_ENTRY_COUNT);
+	must_be_true(git_index_entrycount(index) == TEST_INDEX_ENTRY_COUNT);
 	must_be_true(index->sorted);
 
+	entries = (git_index_entry **)index->entries.contents;
+
 	for (i = 0; i < ARRAY_SIZE(TEST_ENTRIES); ++i) {
-		git_index_entry *e = &index->entries[TEST_ENTRIES[i].index];
+		git_index_entry *e = entries[TEST_ENTRIES[i].index];
 
 		must_be_true(strcmp(e->path, TEST_ENTRIES[i].path) == 0);
 		must_be_true(e->mtime.seconds == TEST_ENTRIES[i].mtime);
@@ -74,7 +77,7 @@ BEGIN_TEST(index2_load_test)
 	must_pass(git_index_read(index));
 
 	must_be_true(index->on_disk);
-	must_be_true(index->entry_count == TEST_INDEX2_ENTRY_COUNT);
+	must_be_true(git_index_entrycount(index) == TEST_INDEX2_ENTRY_COUNT);
 	must_be_true(index->sorted);
 	must_be_true(index->tree != NULL);
 
diff --git a/tests/t0603-sort.c b/tests/t0603-sort.c
index d47c93c77..35f7f8753 100644
--- a/tests/t0603-sort.c
+++ b/tests/t0603-sort.c
@@ -7,26 +7,32 @@
 
 #define TEST_INDEX_PATH "../t0600-objects/index"
 
+/*
 void print_entries(git_index *index)
 {
 	unsigned int i;
 
-	for (i = 0; i < index->entry_count; ++i)
+	for (i = 0; i < index->entries.length; ++i)
 		printf("%d: %s\n", i, index->entries[i].path);
 }
+*/
 
 void randomize_entries(git_index *index)
 {
 	unsigned int i, j;
-	git_index_entry tmp;
+	git_index_entry *tmp;
+	git_index_entry **entries;
+
+	entries = (git_index_entry **)index->entries.contents;
 
 	srand((unsigned int)time(NULL));
 
-	for (i = 0; i < index->entry_count; ++i) {
-		j = rand() % index->entry_count;
-		memcpy(&tmp, &index->entries[j], sizeof(git_index_entry));
-		memcpy(&index->entries[j], &index->entries[i], sizeof(git_index_entry));
-		memcpy(&index->entries[i], &tmp, sizeof(git_index_entry));
+	for (i = 0; i < index->entries.length; ++i) {
+		j = rand() % index->entries.length;
+
+		tmp = entries[j];
+		entries[j] = entries[i];
+		entries[i] = tmp;
 	}
 
 	index->sorted = 0;
@@ -35,6 +41,9 @@ void randomize_entries(git_index *index)
 BEGIN_TEST(index_sort_test)
 	git_index *index;
 	unsigned int i;
+	git_index_entry **entries;
+
+	entries = (git_index_entry **)index->entries.contents;
 
 	must_pass(git_index_open_bare(&index, TEST_INDEX_PATH));
 	must_pass(git_index_read(index));
@@ -44,9 +53,8 @@ BEGIN_TEST(index_sort_test)
 	git_index__sort(index);
 	must_be_true(index->sorted);
 
-	for (i = 1; i < index->entry_count; ++i)
-		must_be_true(strcmp(index->entries[i - 1].path,
-					index->entries[i].path) < 0);
+	for (i = 1; i < index->entries.length; ++i)
+		must_be_true(strcmp(entries[i - 1]->path, entries[i]->path) < 0);
 
 	git_index_free(index);
 END_TEST