]>
git.proxmox.com Git - libgit2.git/blob - tests/core/vector.c
a7e1a03257c68617e8be1ace39d67674ec308501
3 #include "clar_libgit2.h"
6 /* initial size of 1 would cause writing past array bounds */
7 void test_core_vector__0(void)
11 git_vector_init(&x
, 1, NULL
);
12 for (i
= 0; i
< 10; ++i
) {
13 git_vector_insert(&x
, (void*) 0xabc);
19 /* don't read past array bounds on remove() */
20 void test_core_vector__1(void)
23 /* make initial capacity exact for our insertions. */
24 git_vector_init(&x
, 3, NULL
);
25 git_vector_insert(&x
, (void*) 0xabc);
26 git_vector_insert(&x
, (void*) 0xdef);
27 git_vector_insert(&x
, (void*) 0x123);
29 git_vector_remove(&x
, 0); /* used to read past array bounds. */
34 static int test_cmp(const void *a
, const void *b
)
36 return *(const int *)a
- *(const int *)b
;
39 /* remove duplicates */
40 void test_core_vector__2(void)
45 ptrs
[0] = git__malloc(sizeof(int));
46 ptrs
[1] = git__malloc(sizeof(int));
51 cl_git_pass(git_vector_init(&x
, 5, test_cmp
));
52 cl_git_pass(git_vector_insert(&x
, ptrs
[0]));
53 cl_git_pass(git_vector_insert(&x
, ptrs
[1]));
54 cl_git_pass(git_vector_insert(&x
, ptrs
[1]));
55 cl_git_pass(git_vector_insert(&x
, ptrs
[0]));
56 cl_git_pass(git_vector_insert(&x
, ptrs
[1]));
57 cl_assert(x
.length
== 5);
59 git_vector_uniq(&x
, NULL
);
60 cl_assert(x
.length
== 2);
69 static int compare_them(const void *a
, const void *b
)
71 return (int)((intptr_t)a
- (intptr_t)b
);
75 void test_core_vector__3(void)
79 git_vector_init(&x
, 1, &compare_them
);
81 for (i
= 0; i
< 10; i
+= 2) {
82 git_vector_insert_sorted(&x
, (void*)(i
+ 1), NULL
);
85 for (i
= 9; i
> 0; i
-= 2) {
86 git_vector_insert_sorted(&x
, (void*)(i
+ 1), NULL
);
89 cl_assert(x
.length
== 10);
90 for (i
= 0; i
< 10; ++i
) {
91 cl_assert(git_vector_get(&x
, i
) == (void*)(i
+ 1));
97 /* insert_sorted with duplicates */
98 void test_core_vector__4(void)
102 git_vector_init(&x
, 1, &compare_them
);
104 for (i
= 0; i
< 10; i
+= 2) {
105 git_vector_insert_sorted(&x
, (void*)(i
+ 1), NULL
);
108 for (i
= 9; i
> 0; i
-= 2) {
109 git_vector_insert_sorted(&x
, (void*)(i
+ 1), NULL
);
112 for (i
= 0; i
< 10; i
+= 2) {
113 git_vector_insert_sorted(&x
, (void*)(i
+ 1), NULL
);
116 for (i
= 9; i
> 0; i
-= 2) {
117 git_vector_insert_sorted(&x
, (void*)(i
+ 1), NULL
);
120 cl_assert(x
.length
== 20);
121 for (i
= 0; i
< 20; ++i
) {
122 cl_assert(git_vector_get(&x
, i
) == (void*)(i
/ 2 + 1));
133 static int _struct_count
= 0;
135 static int compare_structs(const void *a
, const void *b
)
137 return ((const my_struct
*)a
)->content
-
138 ((const my_struct
*)b
)->content
;
141 static int merge_structs(void **old_raw
, void *new)
143 my_struct
*old
= *(my_struct
**)old_raw
;
144 cl_assert(((my_struct
*)old
)->content
== ((my_struct
*)new)->content
);
145 ((my_struct
*)old
)->count
+= 1;
151 static my_struct
*alloc_struct(int value
)
153 my_struct
*st
= git__malloc(sizeof(my_struct
));
160 /* insert_sorted with duplicates and special handling */
161 void test_core_vector__5(void)
166 git_vector_init(&x
, 1, &compare_structs
);
168 for (i
= 0; i
< 10; i
+= 2)
169 git_vector_insert_sorted(&x
, alloc_struct(i
), &merge_structs
);
171 for (i
= 9; i
> 0; i
-= 2)
172 git_vector_insert_sorted(&x
, alloc_struct(i
), &merge_structs
);
174 cl_assert(x
.length
== 10);
175 cl_assert(_struct_count
== 10);
177 for (i
= 0; i
< 10; i
+= 2)
178 git_vector_insert_sorted(&x
, alloc_struct(i
), &merge_structs
);
180 for (i
= 9; i
> 0; i
-= 2)
181 git_vector_insert_sorted(&x
, alloc_struct(i
), &merge_structs
);
183 cl_assert(x
.length
== 10);
184 cl_assert(_struct_count
== 10);
186 for (i
= 0; i
< 10; ++i
) {
187 cl_assert(((my_struct
*)git_vector_get(&x
, i
))->content
== i
);
188 git__free(git_vector_get(&x
, i
));
195 static int remove_ones(const git_vector
*v
, size_t idx
, void *p
)
198 return (git_vector_get(v
, idx
) == (void *)0x001);
201 /* Test removal based on callback */
202 void test_core_vector__remove_matching(void)
208 git_vector_init(&x
, 1, NULL
);
209 git_vector_insert(&x
, (void*) 0x001);
211 cl_assert(x
.length
== 1);
212 git_vector_remove_matching(&x
, remove_ones
, NULL
);
213 cl_assert(x
.length
== 0);
215 git_vector_insert(&x
, (void*) 0x001);
216 git_vector_insert(&x
, (void*) 0x001);
217 git_vector_insert(&x
, (void*) 0x001);
219 cl_assert(x
.length
== 3);
220 git_vector_remove_matching(&x
, remove_ones
, NULL
);
221 cl_assert(x
.length
== 0);
223 git_vector_insert(&x
, (void*) 0x002);
224 git_vector_insert(&x
, (void*) 0x001);
225 git_vector_insert(&x
, (void*) 0x002);
226 git_vector_insert(&x
, (void*) 0x001);
228 cl_assert(x
.length
== 4);
229 git_vector_remove_matching(&x
, remove_ones
, NULL
);
230 cl_assert(x
.length
== 2);
232 git_vector_foreach(&x
, i
, compare
) {
233 cl_assert(compare
!= (void *)0x001);
236 git_vector_clear(&x
);
238 git_vector_insert(&x
, (void*) 0x001);
239 git_vector_insert(&x
, (void*) 0x002);
240 git_vector_insert(&x
, (void*) 0x002);
241 git_vector_insert(&x
, (void*) 0x001);
243 cl_assert(x
.length
== 4);
244 git_vector_remove_matching(&x
, remove_ones
, NULL
);
245 cl_assert(x
.length
== 2);
247 git_vector_foreach(&x
, i
, compare
) {
248 cl_assert(compare
!= (void *)0x001);
251 git_vector_clear(&x
);
253 git_vector_insert(&x
, (void*) 0x002);
254 git_vector_insert(&x
, (void*) 0x001);
255 git_vector_insert(&x
, (void*) 0x002);
256 git_vector_insert(&x
, (void*) 0x001);
258 cl_assert(x
.length
== 4);
259 git_vector_remove_matching(&x
, remove_ones
, NULL
);
260 cl_assert(x
.length
== 2);
262 git_vector_foreach(&x
, i
, compare
) {
263 cl_assert(compare
!= (void *)0x001);
266 git_vector_clear(&x
);
268 git_vector_insert(&x
, (void*) 0x002);
269 git_vector_insert(&x
, (void*) 0x003);
270 git_vector_insert(&x
, (void*) 0x002);
271 git_vector_insert(&x
, (void*) 0x003);
273 cl_assert(x
.length
== 4);
274 git_vector_remove_matching(&x
, remove_ones
, NULL
);
275 cl_assert(x
.length
== 4);
280 static void assert_vector(git_vector
*x
, void *expected
[], size_t len
)
284 cl_assert_equal_i(len
, x
->length
);
286 for (i
= 0; i
< len
; i
++)
287 cl_assert(expected
[i
] == x
->contents
[i
]);
290 void test_core_vector__grow_and_shrink(void)
292 git_vector x
= GIT_VECTOR_INIT
;
293 void *expected1
[] = {
294 (void *)0x02, (void *)0x03, (void *)0x04, (void *)0x05,
295 (void *)0x06, (void *)0x07, (void *)0x08, (void *)0x09,
298 void *expected2
[] = {
299 (void *)0x02, (void *)0x04, (void *)0x05, (void *)0x06,
300 (void *)0x07, (void *)0x08, (void *)0x09, (void *)0x0a
302 void *expected3
[] = {
303 (void *)0x02, (void *)0x04, (void *)0x05, (void *)0x06,
306 void *expected4
[] = {
307 (void *)0x02, (void *)0x04, (void *)0x05
309 void *expected5
[] = {
310 (void *)0x00, (void *)0x00, (void *)0x02, (void *)0x04,
313 void *expected6
[] = {
314 (void *)0x00, (void *)0x00, (void *)0x02, (void *)0x04,
315 (void *)0x05, (void *)0x00
317 void *expected7
[] = {
318 (void *)0x00, (void *)0x00, (void *)0x02, (void *)0x04,
319 (void *)0x00, (void *)0x00, (void *)0x00, (void *)0x05,
322 void *expected8
[] = {
323 (void *)0x04, (void *)0x00, (void *)0x00, (void *)0x00,
324 (void *)0x05, (void *)0x00
326 void *expected9
[] = {
327 (void *)0x04, (void *)0x00, (void *)0x05, (void *)0x00
329 void *expectedA
[] = { (void *)0x04, (void *)0x00 };
330 void *expectedB
[] = { (void *)0x04 };
332 git_vector_insert(&x
, (void *)0x01);
333 git_vector_insert(&x
, (void *)0x02);
334 git_vector_insert(&x
, (void *)0x03);
335 git_vector_insert(&x
, (void *)0x04);
336 git_vector_insert(&x
, (void *)0x05);
337 git_vector_insert(&x
, (void *)0x06);
338 git_vector_insert(&x
, (void *)0x07);
339 git_vector_insert(&x
, (void *)0x08);
340 git_vector_insert(&x
, (void *)0x09);
341 git_vector_insert(&x
, (void *)0x0a);
343 git_vector_remove_range(&x
, 0, 1);
344 assert_vector(&x
, expected1
, ARRAY_SIZE(expected1
));
346 git_vector_remove_range(&x
, 1, 1);
347 assert_vector(&x
, expected2
, ARRAY_SIZE(expected2
));
349 git_vector_remove_range(&x
, 4, 3);
350 assert_vector(&x
, expected3
, ARRAY_SIZE(expected3
));
352 git_vector_remove_range(&x
, 3, 2);
353 assert_vector(&x
, expected4
, ARRAY_SIZE(expected4
));
355 git_vector_insert_null(&x
, 0, 2);
356 assert_vector(&x
, expected5
, ARRAY_SIZE(expected5
));
358 git_vector_insert_null(&x
, 5, 1);
359 assert_vector(&x
, expected6
, ARRAY_SIZE(expected6
));
361 git_vector_insert_null(&x
, 4, 3);
362 assert_vector(&x
, expected7
, ARRAY_SIZE(expected7
));
364 git_vector_remove_range(&x
, 0, 3);
365 assert_vector(&x
, expected8
, ARRAY_SIZE(expected8
));
367 git_vector_remove_range(&x
, 1, 2);
368 assert_vector(&x
, expected9
, ARRAY_SIZE(expected9
));
370 git_vector_remove_range(&x
, 2, 2);
371 assert_vector(&x
, expectedA
, ARRAY_SIZE(expectedA
));
373 git_vector_remove_range(&x
, 1, 1);
374 assert_vector(&x
, expectedB
, ARRAY_SIZE(expectedB
));
376 git_vector_remove_range(&x
, 0, 1);
377 assert_vector(&x
, NULL
, 0);
382 void test_core_vector__reverse(void)
384 git_vector v
= GIT_VECTOR_INIT
;
387 void *in1
[] = {(void *) 0x0, (void *) 0x1, (void *) 0x2, (void *) 0x3};
388 void *out1
[] = {(void *) 0x3, (void *) 0x2, (void *) 0x1, (void *) 0x0};
390 void *in2
[] = {(void *) 0x0, (void *) 0x1, (void *) 0x2, (void *) 0x3, (void *) 0x4};
391 void *out2
[] = {(void *) 0x4, (void *) 0x3, (void *) 0x2, (void *) 0x1, (void *) 0x0};
393 for (i
= 0; i
< 4; i
++)
394 cl_git_pass(git_vector_insert(&v
, in1
[i
]));
396 git_vector_reverse(&v
);
398 for (i
= 0; i
< 4; i
++)
399 cl_assert_equal_p(out1
[i
], git_vector_get(&v
, i
));
401 git_vector_clear(&v
);
402 for (i
= 0; i
< 5; i
++)
403 cl_git_pass(git_vector_insert(&v
, in2
[i
]));
405 git_vector_reverse(&v
);
407 for (i
= 0; i
< 5; i
++)
408 cl_assert_equal_p(out2
[i
], git_vector_get(&v
, i
));
413 void test_core_vector__dup_empty_vector(void)
415 git_vector v
= GIT_VECTOR_INIT
;
416 git_vector dup
= GIT_VECTOR_INIT
;
419 cl_assert_equal_i(0, v
.length
);
421 cl_git_pass(git_vector_dup(&dup
, &v
, v
._cmp
));
422 cl_assert_equal_i(0, dup
._alloc_size
);
423 cl_assert_equal_i(0, dup
.length
);
425 cl_git_pass(git_vector_insert(&dup
, &dummy
));
426 cl_assert_equal_i(8, dup
._alloc_size
);
427 cl_assert_equal_i(1, dup
.length
);
429 git_vector_free(&dup
);