git_vector_grow/shrink: correct shrink, and tests

2 files changed, 117 insertions, 14 deletions

diff --git a/src/vector.c b/src/vector.c
index 368467692..5ad8a738c 100644
--- a/src/vector.c
+++ b/src/vector.c
@@ -7,6 +7,7 @@
 
 #include "common.h"
 #include "vector.h"
+#include "integer.h"
 
 /* In elements, not bytes */
 #define MIN_ALLOCSIZE	8
@@ -332,17 +333,16 @@ int git_vector_resize_to(git_vector *v, size_t new_length)
 
 int git_vector_grow_at(git_vector *v, size_t idx, size_t grow_len)
 {
-	size_t new_length = v->length + grow_len;
-	size_t new_idx = idx + grow_len;
+	size_t new_length;
 
-	assert(grow_len > 0);
-	assert (idx <= v->length);
+	assert(grow_len > 0 && idx <= v->length);
 
-	if (new_length < v->length ||
-		(new_length > v->_alloc_size && resize_vector(v, new_length) < 0))
+	GITERR_CHECK_ALLOC_ADD(&new_length, v->length, grow_len);
+
+	if (new_length > v->_alloc_size && resize_vector(v, new_length) < 0)
 		return -1;
 
-	memmove(&v->contents[new_idx], &v->contents[idx],
+	memmove(&v->contents[idx + grow_len], &v->contents[idx],
 		sizeof(void *) * (v->length - idx));
 	memset(&v->contents[idx], 0, sizeof(void *) * grow_len);
 
@@ -353,17 +353,18 @@ int git_vector_grow_at(git_vector *v, size_t idx, size_t grow_len)
 int git_vector_shrink_at(git_vector *v, size_t idx, size_t shrink_len)
 {
 	size_t new_length = v->length - shrink_len;
-	size_t end_idx = idx + shrink_len;
+	size_t end_idx = 0;
+	
+	assert(shrink_len > 0);
 
-	assert(shrink_len > 0 && shrink_len <= v->length);
-	assert(idx <= v->length);
+	if (git__add_sizet_overflow(&end_idx, idx, shrink_len))
+		assert(0);
 
-	if (new_length > v->length)
-		return -1;
+	assert(end_idx <= v->length);
 
-	if (idx > v->length)
+	if (end_idx < v->length)
 		memmove(&v->contents[idx], &v->contents[end_idx],
-			sizeof(void *) * (v->length - idx));
+			sizeof(void *) * (v->length - end_idx));
 
 	memset(&v->contents[new_length], 0, sizeof(void *) * shrink_len);
 
diff --git a/tests/core/vector.c b/tests/core/vector.c
index 66f90b82b..abc641a2c 100644
--- a/tests/core/vector.c
+++ b/tests/core/vector.c
@@ -274,3 +274,105 @@ void test_core_vector__remove_matching(void)
 
 	git_vector_free(&x);
 }
+
+static void assert_vector(git_vector *x, void *expected[], size_t len)
+{
+	size_t i;
+
+	cl_assert_equal_i(len, x->length);
+
+	for (i = 0; i < len; i++)
+		cl_assert(expected[i] == x->contents[i]);
+}
+
+void test_core_vector__grow_and_shrink(void)
+{
+	git_vector x = GIT_VECTOR_INIT;
+	void *expected1[] = {
+		(void *)0x02, (void *)0x03, (void *)0x04, (void *)0x05,
+		(void *)0x06, (void *)0x07, (void *)0x08, (void *)0x09,
+		(void *)0x0a
+	};
+	void *expected2[] = {
+		(void *)0x02, (void *)0x04, (void *)0x05, (void *)0x06,
+		(void *)0x07, (void *)0x08, (void *)0x09, (void *)0x0a
+	};
+	void *expected3[] = {
+		(void *)0x02, (void *)0x04, (void *)0x05, (void *)0x06,
+		(void *)0x0a
+	};
+	void *expected4[] = {
+		(void *)0x02, (void *)0x04, (void *)0x05
+	};
+	void *expected5[] = {
+		(void *)0x00, (void *)0x00, (void *)0x02, (void *)0x04,
+		(void *)0x05
+	};
+	void *expected6[] = {
+		(void *)0x00, (void *)0x00, (void *)0x02, (void *)0x04,
+		(void *)0x05, (void *)0x00
+	};
+	void *expected7[] = {
+		(void *)0x00, (void *)0x00, (void *)0x02, (void *)0x04,
+		(void *)0x00, (void *)0x00, (void *)0x00, (void *)0x05,
+		(void *)0x00
+	};
+	void *expected8[] = {
+		(void *)0x04, (void *)0x00, (void *)0x00, (void *)0x00,
+		(void *)0x05, (void *)0x00
+	};
+	void *expected9[] = {
+		(void *)0x04, (void *)0x00, (void *)0x05, (void *)0x00
+	};
+	void *expectedA[] = { (void *)0x04, (void *)0x00 };
+	void *expectedB[] = { (void *)0x04 };
+
+	git_vector_insert(&x, (void *)0x01);
+	git_vector_insert(&x, (void *)0x02);
+	git_vector_insert(&x, (void *)0x03);
+	git_vector_insert(&x, (void *)0x04);
+	git_vector_insert(&x, (void *)0x05);
+	git_vector_insert(&x, (void *)0x06);
+	git_vector_insert(&x, (void *)0x07);
+	git_vector_insert(&x, (void *)0x08);
+	git_vector_insert(&x, (void *)0x09);
+	git_vector_insert(&x, (void *)0x0a);
+
+	git_vector_shrink_at(&x, 0, 1);
+	assert_vector(&x, expected1, ARRAY_SIZE(expected1));
+
+	git_vector_shrink_at(&x, 1, 1);
+	assert_vector(&x, expected2, ARRAY_SIZE(expected2));
+
+	git_vector_shrink_at(&x, 4, 3);
+	assert_vector(&x, expected3, ARRAY_SIZE(expected3));
+
+	git_vector_shrink_at(&x, 3, 2);
+	assert_vector(&x, expected4, ARRAY_SIZE(expected4));
+
+	git_vector_grow_at(&x, 0, 2);
+	assert_vector(&x, expected5, ARRAY_SIZE(expected5));
+
+	git_vector_grow_at(&x, 5, 1);
+	assert_vector(&x, expected6, ARRAY_SIZE(expected6));
+
+	git_vector_grow_at(&x, 4, 3);
+	assert_vector(&x, expected7, ARRAY_SIZE(expected7));
+
+	git_vector_shrink_at(&x, 0, 3);
+	assert_vector(&x, expected8, ARRAY_SIZE(expected8));
+
+	git_vector_shrink_at(&x, 1, 2);
+	assert_vector(&x, expected9, ARRAY_SIZE(expected9));
+
+	git_vector_shrink_at(&x, 2, 2);
+	assert_vector(&x, expectedA, ARRAY_SIZE(expectedA));
+
+	git_vector_shrink_at(&x, 1, 1);
+	assert_vector(&x, expectedB, ARRAY_SIZE(expectedB));
+
+	git_vector_shrink_at(&x, 0, 1);
+	assert_vector(&x, NULL, 0);
+
+	git_vector_free(&x);
+}