Merge remote-tracking branch 'source/development' into update-test

Merging main libgit2!
Conflicts:
	CMakeLists.txt
	src/unix/map.c

1 files changed, 110 insertions, 55 deletions

diff --git a/src/vector.c b/src/vector.c
index 1ddc26e3e..6f9aacccf 100644
--- a/src/vector.c
+++ b/src/vector.c
@@ -1,26 +1,8 @@
 /*
- * 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.
+ * Copyright (C) 2009-2012 the libgit2 contributors
  *
- * 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.
+ * This file is part of libgit2, distributed under the GNU GPL v2 with
+ * a Linking Exception. For full terms see the included COPYING file.
  */
 
 #include "common.h"
@@ -28,7 +10,7 @@
 #include "vector.h"
 
 static const double resize_factor = 1.75;
-static const size_t minimum_size = 8;
+static const unsigned int minimum_size = 8;
 
 static int resize_vector(git_vector *v)
 {
@@ -36,18 +18,21 @@ static int resize_vector(git_vector *v)
 	if (v->_alloc_size < minimum_size)
 		v->_alloc_size = minimum_size;
 
-	v->contents = realloc(v->contents, v->_alloc_size * sizeof(void *));
-	if (v->contents == NULL)
-		return GIT_ENOMEM;
+	v->contents = git__realloc(v->contents, v->_alloc_size * sizeof(void *));
+	GITERR_CHECK_ALLOC(v->contents);
 
-	return GIT_SUCCESS;
+	return 0;
 }
 
-
 void git_vector_free(git_vector *v)
 {
 	assert(v);
-	free(v->contents);
+
+	git__free(v->contents);
+	v->contents = NULL;
+
+	v->length = 0;
+	v->_alloc_size = 0;
 }
 
 int git_vector_init(git_vector *v, unsigned int initial_size, git_vector_cmp cmp)
@@ -61,30 +46,63 @@ int git_vector_init(git_vector *v, unsigned int initial_size, git_vector_cmp cmp
 
 	v->_alloc_size = initial_size;
 	v->_cmp = cmp;
-	
+
 	v->length = 0;
 	v->sorted = 1;
 
 	v->contents = git__malloc(v->_alloc_size * sizeof(void *));
-	if (v->contents == NULL)
-		return GIT_ENOMEM;
+	GITERR_CHECK_ALLOC(v->contents);
 
-	return GIT_SUCCESS;
+	return 0;
 }
 
 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;
-	}
+	if (v->length >= v->_alloc_size &&
+		resize_vector(v) < 0)
+		return -1;
 
 	v->contents[v->length++] = element;
 	v->sorted = 0;
 
-	return GIT_SUCCESS;
+	return 0;
+}
+
+int git_vector_insert_sorted(
+	git_vector *v, void *element, int (*on_dup)(void **old, void *new))
+{
+	int result;
+	size_t pos;
+
+	assert(v && v->_cmp);
+
+	if (!v->sorted)
+		git_vector_sort(v);
+
+	if (v->length >= v->_alloc_size &&
+		resize_vector(v) < 0)
+		return -1;
+
+	/* If we find the element and have a duplicate handler callback,
+	 * invoke it.  If it returns non-zero, then cancel insert, otherwise
+	 * proceed with normal insert.
+	 */
+	if (git__bsearch(v->contents, v->length, element, v->_cmp, &pos) >= 0 &&
+		on_dup != NULL &&
+		(result = on_dup(&v->contents[pos], element)) < 0)
+		return result;
+
+	/* shift elements to the right */
+	if (pos < v->length) {
+		memmove(v->contents + pos + 1, v->contents + pos,
+		        (v->length - pos) * sizeof(void *));
+	}
+
+	v->contents[pos] = element;
+	v->length++;
+	return 0;
 }
 
 void git_vector_sort(git_vector *v)
@@ -94,30 +112,36 @@ void git_vector_sort(git_vector *v)
 	if (v->sorted || v->_cmp == NULL)
 		return;
 
-	qsort(v->contents, v->length, sizeof(void *), v->_cmp);
+	git__tsort(v->contents, v->length, v->_cmp);
 	v->sorted = 1;
 }
 
-int git_vector_bsearch2(git_vector *v, git_vector_cmp key_lookup, const void *key)
+int git_vector_bsearch3(
+	unsigned int *at_pos,
+	git_vector *v,
+	git_vector_cmp key_lookup,
+	const void *key)
 {
-	void **find;
+	int rval;
+	size_t pos;
 
 	assert(v && key && key_lookup);
 
 	/* need comparison function to sort the vector */
-	if (v->_cmp == NULL)
-		return git__throw(GIT_ENOTFOUND, "Can't sort vector. No comparison function set");
+	assert(v->_cmp != NULL);
 
 	git_vector_sort(v);
 
-	find = bsearch(key, v->contents, v->length, sizeof(void *), key_lookup);
-	if (find != NULL)
-		return (int)(find - v->contents);
+	rval = git__bsearch(v->contents, v->length, key, key_lookup, &pos);
 
-	return git__throw(GIT_ENOTFOUND, "Can't find element");
+	if (at_pos != NULL)
+		*at_pos = (unsigned int)pos;
+
+	return (rval >= 0) ? (int)pos : GIT_ENOTFOUND;
 }
 
-int git_vector_search2(git_vector *v, git_vector_cmp key_lookup, const void *key)
+int git_vector_search2(
+	git_vector *v, git_vector_cmp key_lookup, const void *key)
 {
 	unsigned int i;
 
@@ -128,7 +152,7 @@ int git_vector_search2(git_vector *v, git_vector_cmp key_lookup, const void *key
 			return i;
 	}
 
-	return git__throw(GIT_ENOTFOUND, "Can't find element");
+	return GIT_ENOTFOUND;
 }
 
 static int strict_comparison(const void *a, const void *b)
@@ -141,11 +165,6 @@ int git_vector_search(git_vector *v, const void *entry)
 	return git_vector_search2(v, v->_cmp ? v->_cmp : strict_comparison, entry);
 }
 
-int git_vector_bsearch(git_vector *v, const void *key)
-{
-	return git_vector_bsearch2(v, v->_cmp, key);
-}
-
 int git_vector_remove(git_vector *v, unsigned int idx)
 {
 	unsigned int i;
@@ -153,13 +172,39 @@ int git_vector_remove(git_vector *v, unsigned int idx)
 	assert(v);
 
 	if (idx >= v->length || v->length == 0)
-		return git__throw(GIT_ENOTFOUND, "Can't remove element. Index out of bounds");
+		return GIT_ENOTFOUND;
 
 	for (i = idx; i < v->length - 1; ++i)
 		v->contents[i] = v->contents[i + 1];
 
 	v->length--;
-	return GIT_SUCCESS;
+	return 0;
+}
+
+void git_vector_pop(git_vector *v)
+{
+	if (v->length > 0)
+		v->length--;
+}
+
+void git_vector_uniq(git_vector *v)
+{
+	git_vector_cmp cmp;
+	unsigned int i, j;
+
+	if (v->length <= 1)
+		return;
+
+	git_vector_sort(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]))
+			v->contents[i] = v->contents[j];
+		else
+			v->contents[++i] = v->contents[j];
+
+	v->length -= j - i - 1;
 }
 
 void git_vector_clear(git_vector *v)
@@ -169,4 +214,14 @@ void git_vector_clear(git_vector *v)
 	v->sorted = 1;
 }
 
+void git_vector_swap(git_vector *a, git_vector *b)
+{
+	git_vector t;
+
+	if (!a || !b || a == b)
+		return;
 
+	memcpy(&t, a, sizeof(t));
+	memcpy(a, b, sizeof(t));
+	memcpy(b, &t, sizeof(t));
+}