array: Add array_bsearch function
[strongswan.git] / src / libstrongswan / tests / suites / test_array.c
1 /*
2 * Copyright (C) 2014 Tobias Brunner
3 * Hochschule fuer Technik Rapperswil
4 *
5 * Copyright (C) 2013 Martin Willi
6 * Copyright (C) 2013 revosec AG
7 *
8 * This program is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation; either version 2 of the License, or (at your
11 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 * for more details.
17 */
18
19 #include "test_suite.h"
20
21 #include <collections/array.h>
22
23 START_TEST(test_append_ptr)
24 {
25 array_t *array;
26 uintptr_t x;
27 int i;
28
29 array = array_create(0, 0);
30
31 for (i = 0; i < 4; i++)
32 {
33 ck_assert_int_eq(array_count(array), 0);
34
35 array_insert(array, ARRAY_HEAD, (void*)(uintptr_t)3);
36 array_insert(array, ARRAY_TAIL, (void*)(uintptr_t)4);
37 ck_assert_int_eq(array_count(array), 2);
38
39 /* 3, 4 */
40
41 ck_assert(array_get(array, ARRAY_HEAD, &x));
42 ck_assert_int_eq(x, 3);
43 ck_assert(array_get(array, 1, &x));
44 ck_assert_int_eq(x, 4);
45 ck_assert(array_get(array, ARRAY_TAIL, &x));
46 ck_assert_int_eq(x, 4);
47 ck_assert(!array_get(array, 3, &x));
48
49 array_insert(array, ARRAY_HEAD, (void*)(uintptr_t)1);
50 array_insert(array, 1, (void*)(uintptr_t)2);
51 ck_assert_int_eq(array_count(array), 4);
52
53 /* 1, 2, 3, 4 */
54
55 array_insert(array, ARRAY_TAIL, (void*)(uintptr_t)5);
56 array_insert(array, ARRAY_HEAD, (void*)(uintptr_t)0);
57 ck_assert_int_eq(array_count(array), 6);
58
59 /* 0, 1, 2, 3, 4, 5 */
60
61 ck_assert(array_remove(array, ARRAY_TAIL, &x));
62 ck_assert_int_eq(x, 5);
63 ck_assert(array_remove(array, 4, &x));
64 ck_assert_int_eq(x, 4);
65
66 if (i < 3)
67 {
68 array_compress(array);
69 }
70
71 /* 0, 1, 2, 3 */
72
73 ck_assert(array_remove(array, 1, &x));
74 ck_assert_int_eq(x, 1);
75 ck_assert(array_remove(array, ARRAY_HEAD, &x));
76 ck_assert_int_eq(x, 0);
77
78 if (i < 2)
79 {
80 array_compress(array);
81 }
82
83 /* 2, 3 */
84
85 ck_assert(array_remove(array, ARRAY_TAIL, &x));
86 ck_assert_int_eq(x, 3);
87 ck_assert(array_remove(array, ARRAY_TAIL, &x));
88 ck_assert_int_eq(x, 2);
89
90 if (i < 1)
91 {
92 array_compress(array);
93 }
94
95 ck_assert_int_eq(array_count(array), 0);
96
97 ck_assert(array_remove(array, ARRAY_HEAD, NULL) == FALSE);
98 ck_assert(array_remove(array, ARRAY_TAIL, NULL) == FALSE);
99 }
100
101 array_destroy(array);
102 }
103 END_TEST
104
105 START_TEST(test_append_obj)
106 {
107 array_t *array;
108 int i, x, y[6] = {0, 1, 2, 3, 4, 5};
109
110 array = array_create(sizeof(y[0]), 0);
111
112 for (i = 0; i < 4; i++)
113 {
114 ck_assert_int_eq(array_count(array), 0);
115
116 array_insert(array, ARRAY_HEAD, &y[3]);
117 array_insert(array, ARRAY_TAIL, &y[4]);
118 ck_assert_int_eq(array_count(array), 2);;
119
120 /* 3, 4 */
121
122 ck_assert(array_get(array, ARRAY_HEAD, &x));
123 ck_assert_int_eq(x, 3);
124 ck_assert(array_get(array, 1, &x));
125 ck_assert_int_eq(x, 4);
126 ck_assert(array_get(array, ARRAY_TAIL, &x));
127 ck_assert_int_eq(x, 4);
128 ck_assert(!array_get(array, 3, &x));
129
130 array_insert(array, ARRAY_HEAD, &y[1]);
131 array_insert(array, 1, &y[2]);
132 ck_assert_int_eq(array_count(array), 4);
133
134 /* 1, 2, 3, 4 */
135
136 array_insert(array, ARRAY_TAIL, &y[5]);
137 array_insert(array, ARRAY_HEAD, &y[0]);
138 ck_assert_int_eq(array_count(array), 6);
139
140 /* 0, 1, 2, 3, 4, 5 */
141
142 ck_assert(array_remove(array, ARRAY_TAIL, &x));
143 ck_assert_int_eq(x, 5);
144 ck_assert(array_remove(array, 4, &x));
145 ck_assert_int_eq(x, 4);
146
147 if (i < 3)
148 {
149 array_compress(array);
150 }
151
152 /* 0, 1, 2, 3 */
153
154 ck_assert(array_remove(array, ARRAY_HEAD, &x));
155 ck_assert_int_eq(x, 0);
156 ck_assert(array_remove(array, ARRAY_HEAD, &x));
157 ck_assert_int_eq(x, 1);
158
159 if (i < 2)
160 {
161 array_compress(array);
162 }
163
164 /* 2, 3 */
165
166 ck_assert(array_remove(array, ARRAY_TAIL, &x));
167 ck_assert_int_eq(x, 3);
168 ck_assert(array_remove(array, ARRAY_HEAD, &x));
169 ck_assert_int_eq(x, 2);
170
171 if (i < 1)
172 {
173 array_compress(array);
174 }
175
176 ck_assert_int_eq(array_count(array), 0);
177
178 ck_assert(array_remove(array, ARRAY_HEAD, NULL) == FALSE);
179 ck_assert(array_remove(array, ARRAY_TAIL, NULL) == FALSE);
180 }
181
182 array_destroy(array);
183 }
184 END_TEST
185
186 START_TEST(test_enumerate)
187 {
188 array_t *array;
189 int i, *x, y[6] = {0, 1, 2, 3, 4, 5};
190 enumerator_t *enumerator;
191
192 array = array_create(sizeof(y[0]), 0);
193
194 array_insert(array, ARRAY_TAIL, &y[0]);
195 array_insert(array, ARRAY_TAIL, &y[1]);
196 array_insert(array, ARRAY_TAIL, &y[2]);
197 array_insert(array, ARRAY_TAIL, &y[3]);
198 array_insert(array, ARRAY_TAIL, &y[4]);
199 array_insert(array, ARRAY_TAIL, &y[5]);
200
201 ck_assert_int_eq(array_count(array), 6);
202
203 /* 0, 1, 2, 3, 4, 5 */
204
205 i = 0;
206 enumerator = array_create_enumerator(array);
207 while (enumerator->enumerate(enumerator, &x))
208 {
209 ck_assert_int_eq(*x, y[i]);
210 i++;
211 }
212 enumerator->destroy(enumerator);
213 ck_assert_int_eq(i, 6);
214
215 i = 0;
216 enumerator = array_create_enumerator(array);
217 while (enumerator->enumerate(enumerator, &x))
218 {
219 ck_assert_int_eq(*x, y[i]);
220 if (i == 0 || i == 3 || i == 5)
221 {
222 array_remove_at(array, enumerator);
223 }
224 i++;
225 }
226 enumerator->destroy(enumerator);
227 ck_assert_int_eq(i, 6);
228 ck_assert_int_eq(array_count(array), 3);
229
230 /* 1, 2, 4 */
231
232 i = 0;
233 enumerator = array_create_enumerator(array);
234 while (enumerator->enumerate(enumerator, &x))
235 {
236 switch (i++)
237 {
238 case 0:
239 ck_assert_int_eq(*x, y[1]);
240 break;
241 case 1:
242 ck_assert_int_eq(*x, y[2]);
243 break;
244 case 2:
245 ck_assert_int_eq(*x, y[4]);
246 break;
247 default:
248 ck_assert(0);
249 }
250 }
251 enumerator->destroy(enumerator);
252
253 array_compress(array);
254
255 i = 0;
256 enumerator = array_create_enumerator(array);
257 while (enumerator->enumerate(enumerator, &x))
258 {
259 switch (i++)
260 {
261 case 0:
262 ck_assert_int_eq(*x, y[1]);
263 break;
264 case 1:
265 ck_assert_int_eq(*x, y[2]);
266 break;
267 case 2:
268 ck_assert_int_eq(*x, y[4]);
269 break;
270 default:
271 ck_assert(0);
272 }
273 }
274 enumerator->destroy(enumerator);
275
276 array_destroy(array);
277 }
278 END_TEST
279
280 static int comp_obj(const void *a, const void *b, void *arg)
281 {
282 ck_assert_str_eq(arg, "arg");
283 return *(int*)a - *(int*)b;
284 }
285
286 START_TEST(test_sort_obj)
287 {
288 array_t *array;
289 int x[][3] = {
290 {1, 2, 3},
291 {1, 3, 2},
292 {2, 1, 3},
293 {2, 3, 1},
294 {3, 1, 2},
295 {3, 2, 1},
296 };
297 char *arg = "arg";
298 int i, v;
299
300 for (i = 0; i < countof(x); i++)
301 {
302 array = array_create(sizeof(x[i][0]), 0);
303 array_insert(array, ARRAY_TAIL, &x[i][0]);
304 array_insert(array, ARRAY_TAIL, &x[i][1]);
305 array_insert(array, ARRAY_TAIL, &x[i][2]);
306
307 array_sort(array, comp_obj, arg);
308
309 ck_assert(array_get(array, 0, &v));
310 ck_assert_int_eq(v, 1);
311 ck_assert(array_get(array, 1, &v));
312 ck_assert_int_eq(v, 2);
313 ck_assert(array_get(array, 2, &v));
314 ck_assert_int_eq(v, 3);
315
316 array_destroy(array);
317 }
318 }
319 END_TEST
320
321 static int comp_ptr(const void *a, const void *b, void *arg)
322 {
323 ck_assert_str_eq(arg, "arg");
324 return strcmp(a, b);
325 }
326
327 START_TEST(test_sort_ptr)
328 {
329 array_t *array;
330 char *x[][3] = {
331 {"a", "b", "c"},
332 {"a", "c", "b"},
333 {"b", "a", "c"},
334 {"b", "c", "a"},
335 {"c", "a", "b"},
336 {"c", "b", "a"},
337 };
338 char *v, *arg = "arg";
339 int i;
340
341 for (i = 0; i < countof(x); i++)
342 {
343 array = array_create(0, 0);
344 array_insert(array, ARRAY_TAIL, x[i][0]);
345 array_insert(array, ARRAY_TAIL, x[i][1]);
346 array_insert(array, ARRAY_TAIL, x[i][2]);
347
348 array_sort(array, comp_ptr, arg);
349
350 ck_assert(array_get(array, 0, &v));
351 ck_assert_str_eq(v, "a");
352 ck_assert(array_get(array, 1, &v));
353 ck_assert_str_eq(v, "b");
354 ck_assert(array_get(array, 2, &v));
355 ck_assert_str_eq(v, "c");
356
357 array_destroy(array);
358 }
359 }
360 END_TEST
361
362 static int comp_search_obj(const void *a, const void *b)
363 {
364 return *(int*)a - *(int*)b;
365 }
366
367 START_TEST(test_bsearch_obj)
368 {
369 array_t *array;
370 int x[] = { 3, 2, 1 };
371 int k, v;
372
373 array = array_create(sizeof(x[0]), 0);
374 array_insert(array, ARRAY_TAIL, &x[0]);
375 array_insert(array, ARRAY_TAIL, &x[1]);
376 array_insert(array, ARRAY_TAIL, &x[2]);
377
378 array_sort(array, (void*)comp_search_obj, NULL);
379
380 k = 0;
381 ck_assert_int_eq(array_bsearch(array, &k, comp_search_obj, &v), -1);
382 for (k = 1; k < 4; k++)
383 {
384 ck_assert_int_eq(array_bsearch(array, &k, comp_search_obj, &v), k-1);
385 ck_assert_int_eq(v, k);
386 }
387 k = 4;
388 ck_assert_int_eq(array_bsearch(array, &k, comp_search_obj, &v), -1);
389 array_destroy(array);
390 }
391 END_TEST
392
393 static int comp_search_ptr(const void *a, const void *b)
394 {
395 return strcmp(a, b);
396 }
397
398 START_TEST(test_bsearch_ptr)
399 {
400 array_t *array;
401 char *x[] = {"c", "b", "a"};
402 char *v;
403
404 array = array_create(0, 0);
405 array_insert(array, ARRAY_TAIL, x[0]);
406 array_insert(array, ARRAY_TAIL, x[1]);
407 array_insert(array, ARRAY_TAIL, x[2]);
408
409 array_sort(array, (void*)comp_search_ptr, NULL);
410
411 ck_assert_int_eq(array_bsearch(array, "abc", comp_search_ptr, &v), -1);
412 ck_assert_int_eq(array_bsearch(array, "a", comp_search_ptr, &v), 0);
413 ck_assert_str_eq(v, "a");
414 ck_assert_int_eq(array_bsearch(array, "b", comp_search_ptr, &v), 1);
415 ck_assert_str_eq(v, "b");
416 ck_assert_int_eq(array_bsearch(array, "c", comp_search_ptr, &v), 2);
417 ck_assert_str_eq(v, "c");
418
419 array_destroy(array);
420 }
421 END_TEST
422
423 static void invoke(void *data, int idx, void *user)
424 {
425 int *y = user, *x = data;
426
427 ck_assert(idx < 3);
428
429 ck_assert_int_eq(y[idx], *x);
430 y[idx] = 0;
431 }
432
433 START_TEST(test_invoke)
434 {
435 array_t *array;
436 int y[] = {1, 2, 3};
437
438 array = array_create(sizeof(y[0]), 0);
439
440 array_insert(array, ARRAY_TAIL, &y[0]);
441 array_insert(array, ARRAY_TAIL, &y[1]);
442 array_insert(array, ARRAY_TAIL, &y[2]);
443
444 array_invoke(array, invoke, y);
445
446 ck_assert_int_eq(y[0], 0);
447 ck_assert_int_eq(y[0], 0);
448 ck_assert_int_eq(y[0], 0);
449
450 array_destroy(array);
451 }
452 END_TEST
453
454 typedef struct obj_t obj_t;
455
456 struct obj_t {
457 void (*fun)(obj_t *obj);
458 int x;
459 int *counter;
460 };
461
462 static void fun(obj_t *obj)
463 {
464 ck_assert(obj->x == (*obj->counter)++);
465 }
466
467 START_TEST(test_invoke_offset)
468 {
469 array_t *array;
470 obj_t objs[5];
471 int i, counter = 0;
472
473 array = array_create(0, 0);
474
475 for (i = 0; i < countof(objs); i++)
476 {
477 objs[i].x = i;
478 objs[i].counter = &counter;
479 objs[i].fun = fun;
480
481 array_insert(array, ARRAY_TAIL, &objs[i]);
482 }
483
484 ck_assert_int_eq(countof(objs), array_count(array));
485
486 array_invoke_offset(array, offsetof(obj_t, fun));
487
488 ck_assert_int_eq(counter, countof(objs));
489
490 array_destroy(array);
491 }
492 END_TEST
493
494 Suite *array_suite_create()
495 {
496 Suite *s;
497 TCase *tc;
498
499 s = suite_create("array");
500
501 tc = tcase_create("add/get/remove ptr");
502 tcase_add_test(tc, test_append_ptr);
503 suite_add_tcase(s, tc);
504
505 tc = tcase_create("add/get/remove obj");
506 tcase_add_test(tc, test_append_obj);
507 suite_add_tcase(s, tc);
508
509 tc = tcase_create("enumerate");
510 tcase_add_test(tc, test_enumerate);
511 suite_add_tcase(s, tc);
512
513 tc = tcase_create("sort");
514 tcase_add_test(tc, test_sort_obj);
515 tcase_add_test(tc, test_sort_ptr);
516 suite_add_tcase(s, tc);
517
518 tc = tcase_create("bsearch");
519 tcase_add_test(tc, test_bsearch_obj);
520 tcase_add_test(tc, test_bsearch_ptr);
521 suite_add_tcase(s, tc);
522
523 tc = tcase_create("invoke");
524 tcase_add_test(tc, test_invoke);
525 suite_add_tcase(s, tc);
526
527 tc = tcase_create("invoke offset");
528 tcase_add_test(tc, test_invoke_offset);
529 suite_add_tcase(s, tc);
530
531 return s;
532 }