Commit 476c42acc554e7b3f79c945c2a461d4e25dde41c
2011-07-02T00:41:49
vector: implement git_vector_uniq() The routine remove duplictes from the vector. Only the last added element of elements with equal keys remains in the vector. Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
diff --git a/src/vector.c b/src/vector.c
index 8d09350..2fc051f 100644
--- a/src/vector.c
+++ b/src/vector.c
@@ -162,6 +162,26 @@ int git_vector_remove(git_vector *v, unsigned int idx)
return GIT_SUCCESS;
}
+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)
{
assert(v);
diff --git a/src/vector.h b/src/vector.h
index 256452e..76778ba 100644
--- a/src/vector.h
+++ b/src/vector.h
@@ -32,5 +32,5 @@ GIT_INLINE(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);
-
+void git_vector_uniq(git_vector *v);
#endif
diff --git a/tests/t00-core.c b/tests/t00-core.c
index ba5188a..661f925 100644
--- a/tests/t00-core.c
+++ b/tests/t00-core.c
@@ -73,6 +73,28 @@ BEGIN_TEST(vector1, "don't read past array bounds on remove()")
git_vector_free(&x);
END_TEST
+static int test_cmp(const void *a, const void *b)
+{
+ int n1 = *(int *)a;
+ int n2 = *(int *)b;
+
+ return n1 - n2;
+}
+
+BEGIN_TEST(vector2, "remove duplicates")
+ git_vector x;
+ must_pass(git_vector_init(&x, 5, test_cmp));
+ must_pass(git_vector_insert(&x, (void *) 0xdeadbeef));
+ must_pass(git_vector_insert(&x, (void *) 0xcafebabe));
+ must_pass(git_vector_insert(&x, (void *) 0xcafebabe));
+ must_pass(git_vector_insert(&x, (void *) 0xdeadbeef));
+ must_pass(git_vector_insert(&x, (void *) 0xcafebabe));
+ must_be_true(x.length == 5);
+ git_vector_uniq(&x);
+ must_be_true(x.length == 2);
+ git_vector_free(&x);
+END_TEST
+
BEGIN_TEST(path0, "get the dirname of a path")
char dir[64], *dir2;
@@ -480,6 +502,7 @@ BEGIN_SUITE(core)
ADD_TEST(vector0);
ADD_TEST(vector1);
+ ADD_TEST(vector2);
ADD_TEST(path0);
ADD_TEST(path1);