]>
Commit | Line | Data |
---|---|---|
3fd1520c | 1 | #include "clar_libgit2.h" |
f1558d9b VM |
2 | #include "vector.h" |
3 | ||
4 | /* initial size of 1 would cause writing past array bounds */ | |
5 | void test_core_vector__0(void) | |
6 | { | |
7 | git_vector x; | |
8 | int i; | |
9 | git_vector_init(&x, 1, NULL); | |
10 | for (i = 0; i < 10; ++i) { | |
11 | git_vector_insert(&x, (void*) 0xabc); | |
12 | } | |
13 | git_vector_free(&x); | |
14 | } | |
15 | ||
16 | ||
17 | /* don't read past array bounds on remove() */ | |
18 | void test_core_vector__1(void) | |
19 | { | |
20 | git_vector x; | |
21 | // make initial capacity exact for our insertions. | |
22 | git_vector_init(&x, 3, NULL); | |
23 | git_vector_insert(&x, (void*) 0xabc); | |
24 | git_vector_insert(&x, (void*) 0xdef); | |
25 | git_vector_insert(&x, (void*) 0x123); | |
26 | ||
87d9869f | 27 | git_vector_remove(&x, 0); // used to read past array bounds. |
f1558d9b VM |
28 | git_vector_free(&x); |
29 | } | |
30 | ||
31 | ||
32 | static int test_cmp(const void *a, const void *b) | |
33 | { | |
34 | return *(const int *)a - *(const int *)b; | |
35 | } | |
36 | ||
37 | /* remove duplicates */ | |
38 | void test_core_vector__2(void) | |
39 | { | |
40 | git_vector x; | |
41 | int *ptrs[2]; | |
42 | ||
43 | ptrs[0] = git__malloc(sizeof(int)); | |
44 | ptrs[1] = git__malloc(sizeof(int)); | |
45 | ||
46 | *ptrs[0] = 2; | |
47 | *ptrs[1] = 1; | |
48 | ||
49 | cl_git_pass(git_vector_init(&x, 5, test_cmp)); | |
50 | cl_git_pass(git_vector_insert(&x, ptrs[0])); | |
51 | cl_git_pass(git_vector_insert(&x, ptrs[1])); | |
52 | cl_git_pass(git_vector_insert(&x, ptrs[1])); | |
53 | cl_git_pass(git_vector_insert(&x, ptrs[0])); | |
54 | cl_git_pass(git_vector_insert(&x, ptrs[1])); | |
55 | cl_assert(x.length == 5); | |
56 | ||
191adce8 | 57 | git_vector_uniq(&x, NULL); |
f1558d9b VM |
58 | cl_assert(x.length == 2); |
59 | ||
60 | git_vector_free(&x); | |
61 | ||
3286c408 VM |
62 | git__free(ptrs[0]); |
63 | git__free(ptrs[1]); | |
f1558d9b VM |
64 | } |
65 | ||
66 | ||
bd370b14 RB |
67 | static int compare_them(const void *a, const void *b) |
68 | { | |
69 | return (int)((long)a - (long)b); | |
70 | } | |
71 | ||
72 | /* insert_sorted */ | |
73 | void test_core_vector__3(void) | |
74 | { | |
75 | git_vector x; | |
76 | long i; | |
77 | git_vector_init(&x, 1, &compare_them); | |
78 | ||
79 | for (i = 0; i < 10; i += 2) { | |
80 | git_vector_insert_sorted(&x, (void*)(i + 1), NULL); | |
81 | } | |
82 | ||
83 | for (i = 9; i > 0; i -= 2) { | |
84 | git_vector_insert_sorted(&x, (void*)(i + 1), NULL); | |
85 | } | |
86 | ||
87 | cl_assert(x.length == 10); | |
88 | for (i = 0; i < 10; ++i) { | |
89 | cl_assert(git_vector_get(&x, i) == (void*)(i + 1)); | |
90 | } | |
91 | ||
92 | git_vector_free(&x); | |
93 | } | |
94 | ||
95 | /* insert_sorted with duplicates */ | |
96 | void test_core_vector__4(void) | |
97 | { | |
98 | git_vector x; | |
99 | long i; | |
100 | git_vector_init(&x, 1, &compare_them); | |
101 | ||
102 | for (i = 0; i < 10; i += 2) { | |
103 | git_vector_insert_sorted(&x, (void*)(i + 1), NULL); | |
104 | } | |
105 | ||
106 | for (i = 9; i > 0; i -= 2) { | |
107 | git_vector_insert_sorted(&x, (void*)(i + 1), NULL); | |
108 | } | |
109 | ||
110 | for (i = 0; i < 10; i += 2) { | |
111 | git_vector_insert_sorted(&x, (void*)(i + 1), NULL); | |
112 | } | |
113 | ||
114 | for (i = 9; i > 0; i -= 2) { | |
115 | git_vector_insert_sorted(&x, (void*)(i + 1), NULL); | |
116 | } | |
117 | ||
118 | cl_assert(x.length == 20); | |
119 | for (i = 0; i < 20; ++i) { | |
120 | cl_assert(git_vector_get(&x, i) == (void*)(i / 2 + 1)); | |
121 | } | |
122 | ||
123 | git_vector_free(&x); | |
124 | } | |
125 | ||
126 | typedef struct { | |
127 | int content; | |
128 | int count; | |
129 | } my_struct; | |
130 | ||
131 | static int _struct_count = 0; | |
132 | ||
133 | static int compare_structs(const void *a, const void *b) | |
134 | { | |
135 | return ((const my_struct *)a)->content - | |
136 | ((const my_struct *)b)->content; | |
137 | } | |
138 | ||
139 | static int merge_structs(void **old_raw, void *new) | |
140 | { | |
141 | my_struct *old = *(my_struct **)old_raw; | |
142 | cl_assert(((my_struct *)old)->content == ((my_struct *)new)->content); | |
143 | ((my_struct *)old)->count += 1; | |
144 | git__free(new); | |
145 | _struct_count--; | |
146 | return GIT_EEXISTS; | |
147 | } | |
148 | ||
149 | static my_struct *alloc_struct(int value) | |
150 | { | |
151 | my_struct *st = git__malloc(sizeof(my_struct)); | |
152 | st->content = value; | |
153 | st->count = 0; | |
154 | _struct_count++; | |
155 | return st; | |
156 | } | |
157 | ||
158 | /* insert_sorted with duplicates and special handling */ | |
159 | void test_core_vector__5(void) | |
160 | { | |
161 | git_vector x; | |
162 | int i; | |
163 | ||
164 | git_vector_init(&x, 1, &compare_structs); | |
165 | ||
166 | for (i = 0; i < 10; i += 2) | |
167 | git_vector_insert_sorted(&x, alloc_struct(i), &merge_structs); | |
168 | ||
169 | for (i = 9; i > 0; i -= 2) | |
170 | git_vector_insert_sorted(&x, alloc_struct(i), &merge_structs); | |
171 | ||
172 | cl_assert(x.length == 10); | |
173 | cl_assert(_struct_count == 10); | |
174 | ||
175 | for (i = 0; i < 10; i += 2) | |
176 | git_vector_insert_sorted(&x, alloc_struct(i), &merge_structs); | |
177 | ||
178 | for (i = 9; i > 0; i -= 2) | |
179 | git_vector_insert_sorted(&x, alloc_struct(i), &merge_structs); | |
180 | ||
181 | cl_assert(x.length == 10); | |
182 | cl_assert(_struct_count == 10); | |
183 | ||
184 | for (i = 0; i < 10; ++i) { | |
185 | cl_assert(((my_struct *)git_vector_get(&x, i))->content == i); | |
186 | git__free(git_vector_get(&x, i)); | |
187 | _struct_count--; | |
188 | } | |
189 | ||
190 | git_vector_free(&x); | |
191 | } | |
f45ec1a0 | 192 | |
c67fd4c9 | 193 | static int remove_ones(const git_vector *v, size_t idx, void *p) |
f45ec1a0 | 194 | { |
c67fd4c9 | 195 | GIT_UNUSED(p); |
f45ec1a0 ET |
196 | return (git_vector_get(v, idx) == (void *)0x001); |
197 | } | |
198 | ||
199 | /* Test removal based on callback */ | |
200 | void test_core_vector__remove_matching(void) | |
201 | { | |
202 | git_vector x; | |
203 | size_t i; | |
204 | void *compare; | |
205 | ||
206 | git_vector_init(&x, 1, NULL); | |
207 | git_vector_insert(&x, (void*) 0x001); | |
208 | ||
209 | cl_assert(x.length == 1); | |
c67fd4c9 | 210 | git_vector_remove_matching(&x, remove_ones, NULL); |
f45ec1a0 ET |
211 | cl_assert(x.length == 0); |
212 | ||
213 | git_vector_insert(&x, (void*) 0x001); | |
214 | git_vector_insert(&x, (void*) 0x001); | |
215 | git_vector_insert(&x, (void*) 0x001); | |
216 | ||
217 | cl_assert(x.length == 3); | |
c67fd4c9 | 218 | git_vector_remove_matching(&x, remove_ones, NULL); |
f45ec1a0 ET |
219 | cl_assert(x.length == 0); |
220 | ||
221 | git_vector_insert(&x, (void*) 0x002); | |
222 | git_vector_insert(&x, (void*) 0x001); | |
223 | git_vector_insert(&x, (void*) 0x002); | |
224 | git_vector_insert(&x, (void*) 0x001); | |
225 | ||
226 | cl_assert(x.length == 4); | |
c67fd4c9 | 227 | git_vector_remove_matching(&x, remove_ones, NULL); |
f45ec1a0 ET |
228 | cl_assert(x.length == 2); |
229 | ||
230 | git_vector_foreach(&x, i, compare) { | |
231 | cl_assert(compare != (void *)0x001); | |
232 | } | |
233 | ||
234 | git_vector_clear(&x); | |
235 | ||
236 | git_vector_insert(&x, (void*) 0x001); | |
237 | git_vector_insert(&x, (void*) 0x002); | |
238 | git_vector_insert(&x, (void*) 0x002); | |
239 | git_vector_insert(&x, (void*) 0x001); | |
240 | ||
241 | cl_assert(x.length == 4); | |
c67fd4c9 | 242 | git_vector_remove_matching(&x, remove_ones, NULL); |
f45ec1a0 ET |
243 | cl_assert(x.length == 2); |
244 | ||
245 | git_vector_foreach(&x, i, compare) { | |
246 | cl_assert(compare != (void *)0x001); | |
247 | } | |
248 | ||
249 | git_vector_clear(&x); | |
250 | ||
251 | git_vector_insert(&x, (void*) 0x002); | |
252 | git_vector_insert(&x, (void*) 0x001); | |
253 | git_vector_insert(&x, (void*) 0x002); | |
254 | git_vector_insert(&x, (void*) 0x001); | |
255 | ||
256 | cl_assert(x.length == 4); | |
c67fd4c9 | 257 | git_vector_remove_matching(&x, remove_ones, NULL); |
f45ec1a0 ET |
258 | cl_assert(x.length == 2); |
259 | ||
260 | git_vector_foreach(&x, i, compare) { | |
261 | cl_assert(compare != (void *)0x001); | |
262 | } | |
263 | ||
264 | git_vector_clear(&x); | |
265 | ||
266 | git_vector_insert(&x, (void*) 0x002); | |
267 | git_vector_insert(&x, (void*) 0x003); | |
268 | git_vector_insert(&x, (void*) 0x002); | |
269 | git_vector_insert(&x, (void*) 0x003); | |
270 | ||
271 | cl_assert(x.length == 4); | |
c67fd4c9 | 272 | git_vector_remove_matching(&x, remove_ones, NULL); |
f45ec1a0 ET |
273 | cl_assert(x.length == 4); |
274 | ||
275 | git_vector_free(&x); | |
276 | } | |
e564fc65 ET |
277 | |
278 | static void assert_vector(git_vector *x, void *expected[], size_t len) | |
279 | { | |
280 | size_t i; | |
281 | ||
282 | cl_assert_equal_i(len, x->length); | |
283 | ||
284 | for (i = 0; i < len; i++) | |
285 | cl_assert(expected[i] == x->contents[i]); | |
286 | } | |
287 | ||
288 | void test_core_vector__grow_and_shrink(void) | |
289 | { | |
290 | git_vector x = GIT_VECTOR_INIT; | |
291 | void *expected1[] = { | |
292 | (void *)0x02, (void *)0x03, (void *)0x04, (void *)0x05, | |
293 | (void *)0x06, (void *)0x07, (void *)0x08, (void *)0x09, | |
294 | (void *)0x0a | |
295 | }; | |
296 | void *expected2[] = { | |
297 | (void *)0x02, (void *)0x04, (void *)0x05, (void *)0x06, | |
298 | (void *)0x07, (void *)0x08, (void *)0x09, (void *)0x0a | |
299 | }; | |
300 | void *expected3[] = { | |
301 | (void *)0x02, (void *)0x04, (void *)0x05, (void *)0x06, | |
302 | (void *)0x0a | |
303 | }; | |
304 | void *expected4[] = { | |
305 | (void *)0x02, (void *)0x04, (void *)0x05 | |
306 | }; | |
307 | void *expected5[] = { | |
308 | (void *)0x00, (void *)0x00, (void *)0x02, (void *)0x04, | |
309 | (void *)0x05 | |
310 | }; | |
311 | void *expected6[] = { | |
312 | (void *)0x00, (void *)0x00, (void *)0x02, (void *)0x04, | |
313 | (void *)0x05, (void *)0x00 | |
314 | }; | |
315 | void *expected7[] = { | |
316 | (void *)0x00, (void *)0x00, (void *)0x02, (void *)0x04, | |
317 | (void *)0x00, (void *)0x00, (void *)0x00, (void *)0x05, | |
318 | (void *)0x00 | |
319 | }; | |
320 | void *expected8[] = { | |
321 | (void *)0x04, (void *)0x00, (void *)0x00, (void *)0x00, | |
322 | (void *)0x05, (void *)0x00 | |
323 | }; | |
324 | void *expected9[] = { | |
325 | (void *)0x04, (void *)0x00, (void *)0x05, (void *)0x00 | |
326 | }; | |
327 | void *expectedA[] = { (void *)0x04, (void *)0x00 }; | |
328 | void *expectedB[] = { (void *)0x04 }; | |
329 | ||
330 | git_vector_insert(&x, (void *)0x01); | |
331 | git_vector_insert(&x, (void *)0x02); | |
332 | git_vector_insert(&x, (void *)0x03); | |
333 | git_vector_insert(&x, (void *)0x04); | |
334 | git_vector_insert(&x, (void *)0x05); | |
335 | git_vector_insert(&x, (void *)0x06); | |
336 | git_vector_insert(&x, (void *)0x07); | |
337 | git_vector_insert(&x, (void *)0x08); | |
338 | git_vector_insert(&x, (void *)0x09); | |
339 | git_vector_insert(&x, (void *)0x0a); | |
340 | ||
53571f2f | 341 | git_vector_remove_range(&x, 0, 1); |
e564fc65 ET |
342 | assert_vector(&x, expected1, ARRAY_SIZE(expected1)); |
343 | ||
53571f2f | 344 | git_vector_remove_range(&x, 1, 1); |
e564fc65 ET |
345 | assert_vector(&x, expected2, ARRAY_SIZE(expected2)); |
346 | ||
53571f2f | 347 | git_vector_remove_range(&x, 4, 3); |
e564fc65 ET |
348 | assert_vector(&x, expected3, ARRAY_SIZE(expected3)); |
349 | ||
53571f2f | 350 | git_vector_remove_range(&x, 3, 2); |
e564fc65 ET |
351 | assert_vector(&x, expected4, ARRAY_SIZE(expected4)); |
352 | ||
53571f2f | 353 | git_vector_insert_null(&x, 0, 2); |
e564fc65 ET |
354 | assert_vector(&x, expected5, ARRAY_SIZE(expected5)); |
355 | ||
53571f2f | 356 | git_vector_insert_null(&x, 5, 1); |
e564fc65 ET |
357 | assert_vector(&x, expected6, ARRAY_SIZE(expected6)); |
358 | ||
53571f2f | 359 | git_vector_insert_null(&x, 4, 3); |
e564fc65 ET |
360 | assert_vector(&x, expected7, ARRAY_SIZE(expected7)); |
361 | ||
53571f2f | 362 | git_vector_remove_range(&x, 0, 3); |
e564fc65 ET |
363 | assert_vector(&x, expected8, ARRAY_SIZE(expected8)); |
364 | ||
53571f2f | 365 | git_vector_remove_range(&x, 1, 2); |
e564fc65 ET |
366 | assert_vector(&x, expected9, ARRAY_SIZE(expected9)); |
367 | ||
53571f2f | 368 | git_vector_remove_range(&x, 2, 2); |
e564fc65 ET |
369 | assert_vector(&x, expectedA, ARRAY_SIZE(expectedA)); |
370 | ||
53571f2f | 371 | git_vector_remove_range(&x, 1, 1); |
e564fc65 ET |
372 | assert_vector(&x, expectedB, ARRAY_SIZE(expectedB)); |
373 | ||
53571f2f | 374 | git_vector_remove_range(&x, 0, 1); |
e564fc65 ET |
375 | assert_vector(&x, NULL, 0); |
376 | ||
377 | git_vector_free(&x); | |
378 | } | |
0bd43371 CMN |
379 | |
380 | void test_core_vector__reverse(void) | |
381 | { | |
382 | git_vector v = GIT_VECTOR_INIT; | |
383 | size_t i; | |
384 | ||
385 | void *in1[] = {(void *) 0x0, (void *) 0x1, (void *) 0x2, (void *) 0x3}; | |
386 | void *out1[] = {(void *) 0x3, (void *) 0x2, (void *) 0x1, (void *) 0x0}; | |
387 | ||
388 | void *in2[] = {(void *) 0x0, (void *) 0x1, (void *) 0x2, (void *) 0x3, (void *) 0x4}; | |
389 | void *out2[] = {(void *) 0x4, (void *) 0x3, (void *) 0x2, (void *) 0x1, (void *) 0x0}; | |
390 | ||
391 | for (i = 0; i < 4; i++) | |
392 | cl_git_pass(git_vector_insert(&v, in1[i])); | |
393 | ||
394 | git_vector_reverse(&v); | |
395 | ||
396 | for (i = 0; i < 4; i++) | |
397 | cl_assert_equal_p(out1[i], git_vector_get(&v, i)); | |
398 | ||
399 | git_vector_clear(&v); | |
400 | for (i = 0; i < 5; i++) | |
401 | cl_git_pass(git_vector_insert(&v, in2[i])); | |
402 | ||
403 | git_vector_reverse(&v); | |
404 | ||
405 | for (i = 0; i < 5; i++) | |
406 | cl_assert_equal_p(out2[i], git_vector_get(&v, i)); | |
61ad9bcd PS |
407 | |
408 | git_vector_free(&v); | |
0bd43371 | 409 | } |