Wed, 07 Aug 2019 21:14:58 +0200
ucx_array_sort() uses qsort_r(), if available
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2019 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
29 #include "array_tests.h"
30 #include <ucx/utils.h>
32 UCX_TEST(test_ucx_array_free) {
33 UcxArray array = ucx_array_new(16, sizeof(int));
35 UCX_TEST_BEGIN
36 ucx_array_free(&array);
37 UCX_TEST_ASSERT(array.data == NULL, "data pointer not NULL after free");
38 UCX_TEST_ASSERT(array.size == 0, "size not zero after free");
39 UCX_TEST_ASSERT(array.capacity == 0, "capacity not zero after free");
40 UCX_TEST_ASSERT(array.allocator == ucx_default_allocator(),
41 "allocator corrupted during free");
42 UCX_TEST_END
43 }
45 UCX_TEST(test_ucx_array_new) {
46 UcxArray array = ucx_array_new(16, 47);
48 UCX_TEST_BEGIN
49 UCX_TEST_ASSERT(array.data, "no memory allocated");
50 UCX_TEST_ASSERT(array.size == 0, "size not initially zero");
51 UCX_TEST_ASSERT(array.capacity == 16, "capacity not as requested");
52 UCX_TEST_ASSERT(array.elemsize == 47, "element size not as requested");
53 UCX_TEST_ASSERT(array.allocator == ucx_default_allocator(),
54 "array not using the default allocator");
55 UCX_TEST_END
56 ucx_array_free(&array);
57 }
59 UCX_TEST(test_ucx_array_append) {
60 UcxArray array = ucx_array_new(16, sizeof(int));
61 int *elements;
63 int x = 42;
64 ucx_array_append(&array, &x);
65 UCX_TEST_BEGIN
67 elements = array.data;
68 UCX_TEST_ASSERT(elements[0] == 42, "failed");
70 x = 13;
71 ucx_array_append(&array, &x);
73 elements = array.data;
74 UCX_TEST_ASSERT(array.size == 2, "incorrect size after append");
75 UCX_TEST_ASSERT(elements[1] == 13, "failed");
76 UCX_TEST_ASSERT(elements[0] == 42,
77 "append corrupted previously inserted data");
79 ucx_array_append(&array, NULL);
81 elements = array.data;
82 UCX_TEST_ASSERT(array.size == 3, "incorrect size after NULL append");
83 UCX_TEST_ASSERT(elements[2] == 0, "element is not zeroed");
84 UCX_TEST_ASSERT(elements[0] == 42,
85 "NULL append corrupted previously inserted data");
86 UCX_TEST_ASSERT(elements[1] == 13,
87 "NULL append corrupted previously inserted data");
89 UCX_TEST_END
91 ucx_array_free(&array);
92 }
94 UCX_TEST(test_ucx_array_prepend) {
95 int *elems;
96 UcxArray array = ucx_array_new(16, sizeof(int));
98 int x = 42;
99 ucx_array_prepend(&array, &x);
100 UCX_TEST_BEGIN
102 elems = array.data;
103 UCX_TEST_ASSERT(elems[0] == 42, "failed");
105 x = 13;
106 ucx_array_prepend(&array, &x);
108 elems = array.data;
109 UCX_TEST_ASSERT(array.size == 2, "incorrect size after prepend");
110 UCX_TEST_ASSERT(elems[0] == 13, "failed");
111 UCX_TEST_ASSERT(elems[1] == 42,
112 "prepend corrupted previously inserted data");
114 ucx_array_prepend(&array, NULL);
116 elems = array.data;
117 UCX_TEST_ASSERT(array.size == 3, "incorrect size after NULL prepend");
118 UCX_TEST_ASSERT(elems[0] == 0, "element is not zeroed");
119 UCX_TEST_ASSERT(elems[1] == 13,
120 "NULL prepend corrupted previously inserted data");
121 UCX_TEST_ASSERT(elems[2] == 42,
122 "NULL prepend corrupted previously inserted data");
124 UCX_TEST_END
126 ucx_array_free(&array);
127 }
129 UCX_TEST(test_ucx_array_set) {
130 int *elems;
131 UcxArray array = ucx_array_new(16, sizeof(int));
134 int x = 42;
136 UCX_TEST_BEGIN
138 ucx_array_set(&array, 7, &x);
140 elems = array.data;
141 UCX_TEST_ASSERT(elems[7] == 42, "failed");
142 UCX_TEST_ASSERT(array.size >= 8, "array not resized on set");
143 UCX_TEST_ASSERT(array.capacity == 16, "capacity changed unnecessarily");
145 x = 13;
146 ucx_array_set(&array, 27, &x);
148 elems = array.data;
149 UCX_TEST_ASSERT(elems[27] == 13, "failed");
150 UCX_TEST_ASSERT(array.size == 28, "array not resized on set");
151 UCX_TEST_ASSERT(array.capacity == 28, "capacity not grown");
153 ucx_array_set(&array, 7, NULL);
155 elems = array.data;
156 UCX_TEST_ASSERT(elems[7] == 0, "not zeroed on NULL set");
158 UCX_TEST_END
160 ucx_array_free(&array);
161 }
163 UCX_TEST(test_ucx_array_equals) {
164 UcxArray a1 = ucx_array_new(16, sizeof(int));
165 UcxArray a2 = ucx_array_new(16, sizeof(int));
166 UcxArray a3 = ucx_array_new(16, sizeof(long int));
167 UcxArray a4 = ucx_array_new(16, sizeof(int));
169 int *intelems;
170 long int *longintelems;
172 a1.size = 5;
173 intelems = a1.data;
174 intelems[0] = 47;
175 intelems[1] = 11;
176 intelems[2] = 0;
177 intelems[3] = 8;
178 intelems[4] = 15;
179 a2.size = 5;
180 intelems = a2.data;
181 intelems[0] = 47;
182 intelems[1] = 11;
183 intelems[2] = 0;
184 intelems[3] = 8;
185 intelems[4] = 15;
186 a3.size = 5;
187 longintelems = a3.data;
188 longintelems[0] = 47;
189 longintelems[1] = 11;
190 longintelems[2] = 0;
191 longintelems[3] = 8;
192 longintelems[4] = 15;
193 a4.size = 5;
194 intelems = a4.data;
195 intelems[0] = 47;
196 intelems[1] = 11;
197 intelems[2] = -6;
198 intelems[3] = 8;
199 intelems[4] = 15;
201 UCX_TEST_BEGIN
203 UCX_TEST_ASSERT(ucx_array_equals(a1, a2, ucx_cmp_int, NULL), "failed");
204 UCX_TEST_ASSERT(!ucx_array_equals(a1, a4, ucx_cmp_int, NULL), "failed");
205 UCX_TEST_ASSERT(!ucx_array_equals(a4, a1, ucx_cmp_int, NULL), "failed");
206 UCX_TEST_ASSERT(!ucx_array_equals(a1, a3, ucx_cmp_int, NULL),
207 "comparing arrays of different element size shall fail");
208 UCX_TEST_ASSERT(!ucx_array_equals(a3, a1, ucx_cmp_int, NULL),
209 "comparing arrays of different element size shall fail");
211 UCX_TEST_ASSERT(ucx_array_equals(a1, a2, NULL, NULL),
212 "compare using memcmp() failed");
213 UCX_TEST_ASSERT(!ucx_array_equals(a1, a4, NULL, NULL),
214 "compare using memcmp() failed");
216 UCX_TEST_END
217 ucx_array_free(&a1);
218 ucx_array_free(&a2);
219 ucx_array_free(&a3);
220 ucx_array_free(&a4);
221 }
223 UCX_TEST(test_ucx_array_concat) {
224 UcxArray a1 = ucx_array_new(16, sizeof(int));
225 UcxArray a2 = ucx_array_new(16, sizeof(int));
226 int *elems;
228 a1.size = 2;
229 elems = a1.data;
230 elems[0] = 47;
231 elems[1] = 11;
232 a2.size = 3;
233 elems = a2.data;
234 elems[0] = 0;
235 elems[1] = 8;
236 elems[2] = 15;
238 UCX_TEST_BEGIN
240 UCX_TEST_ASSERT(!ucx_array_concat(&a1, &a2), "failed");
241 UCX_TEST_ASSERT(a1.size == 5, "failed");
242 elems = a1.data;
243 UCX_TEST_ASSERT(elems[0] == 47, "failed");
244 UCX_TEST_ASSERT(elems[1] == 11, "failed");
245 UCX_TEST_ASSERT(elems[2] == 0, "failed");
246 UCX_TEST_ASSERT(elems[3] == 8, "failed");
247 UCX_TEST_ASSERT(elems[4] == 15, "failed");
249 a1.elemsize *= 2;
250 UCX_TEST_ASSERT(ucx_array_concat(&a1, &a2),
251 "arrays of different element size must not be concatenated");
252 UCX_TEST_ASSERT(a1.size == 5,
253 "arrays of different element size must not be concatenated");
255 UCX_TEST_END
256 ucx_array_free(&a1);
257 ucx_array_free(&a2);
258 }
260 UCX_TEST(test_ucx_array_at) {
261 UcxArray array = ucx_array_new(16, sizeof(int));
263 int x = 42;
264 ucx_array_append(&array, &x);
265 x = 13;
266 ucx_array_append(&array, &x);
267 x = 5;
268 ucx_array_append(&array, &x);
270 UCX_TEST_BEGIN
272 UCX_TEST_ASSERT(*(int*)ucx_array_at(array, 1) == 13, "failed");
273 *(int*)ucx_array_at(array, 1) = 80;
274 UCX_TEST_ASSERT(*(int*)ucx_array_at(array, 1) == 80, "assignment failed");
276 UCX_TEST_ASSERT(*(int*)ucx_array_at(array, 0) == 42, "corrupted data");
277 UCX_TEST_ASSERT(*(int*)ucx_array_at(array, 2) == 5, "corrupted data");
279 UCX_TEST_END
281 ucx_array_free(&array);
282 }
284 UCX_TEST(test_ucx_array_find) {
285 UcxArray array = ucx_array_new(16, sizeof(int));
286 int *elems;
288 array.size = 5;
289 elems = array.data;
290 elems[0] = 47;
291 elems[1] = 11;
292 elems[2] = 0;
293 elems[3] = 8;
294 elems[4] = 15;
296 int x = 8;
297 int y = 90;
299 UCX_TEST_BEGIN
301 UCX_TEST_ASSERT(ucx_array_find(array,(void*)&x,ucx_cmp_int,NULL) == 3,
302 "doesn't find element");
303 UCX_TEST_ASSERT(ucx_array_find(array,(void*)&y,ucx_cmp_int,NULL) == 5,
304 "finds non-existing element");
306 UCX_TEST_ASSERT(ucx_array_find(array,(void*)&x,NULL,NULL) == 3,
307 "failed using memcmp()");
308 UCX_TEST_ASSERT(ucx_array_find(array,(void*)&y,NULL,NULL) == 5,
309 "failed using memcmp()");
311 UCX_TEST_END
312 ucx_array_free(&array);
313 }
315 UCX_TEST(test_ucx_array_contains) {
316 UcxArray array = ucx_array_new(16, sizeof(int));
317 int *elems;
319 array.size = 5;
320 elems = array.data;
321 elems[0] = 47;
322 elems[1] = 11;
323 elems[2] = 0;
324 elems[3] = 8;
325 elems[4] = 15;
327 int x = 8;
328 int y = 90;
330 UCX_TEST_BEGIN
332 UCX_TEST_ASSERT(ucx_array_contains(array,(void*)&x,ucx_cmp_int,NULL),
333 "false negative");
334 UCX_TEST_ASSERT(!ucx_array_contains(array,(void*)&y,ucx_cmp_int,NULL),
335 "false positive");
337 UCX_TEST_ASSERT(ucx_array_contains(array,(void*)&x,NULL,NULL),
338 "false negative using memcmp()");
339 UCX_TEST_ASSERT(!ucx_array_contains(array,(void*)&y,NULL,NULL),
340 "false positive using memcmp()");
342 UCX_TEST_END
343 ucx_array_free(&array);
344 }
346 UCX_TEST(test_ucx_array_remove) {
347 UcxArray array = ucx_array_new(16, sizeof(int));
348 int *elems;
350 array.size = 5;
351 elems = array.data;
352 elems[0] = 47;
353 elems[1] = 11;
354 elems[2] = 0;
355 elems[3] = 8;
356 elems[4] = 15;
358 UCX_TEST_BEGIN
360 ucx_array_remove(&array, 2);
361 elems = array.data;
362 UCX_TEST_ASSERT(
363 elems[0] == 47 &&
364 elems[1] == 11 &&
365 elems[2] == 8 &&
366 elems[3] == 15,
367 "wrong contents after remove");
368 UCX_TEST_ASSERT(array.size == 4, "wrong size after remove");
370 ucx_array_remove_fast(&array, 1);
371 elems = array.data;
372 UCX_TEST_ASSERT(
373 elems[0] == 47 &&
374 elems[1] == 15 &&
375 elems[2] == 8,
376 "wrong contents after fast remove");
377 UCX_TEST_ASSERT(array.size == 3, "wrong size after fast remove");
379 UCX_TEST_END
380 ucx_array_free(&array);
381 }
383 UCX_TEST(test_ucx_array_clone) {
384 UcxArray array = ucx_array_new(16, sizeof(int));
385 int *elems;
387 array.size = 5;
388 elems = array.data;
389 elems[0] = 47;
390 elems[1] = 11;
391 elems[2] = 0;
392 elems[3] = 8;
393 elems[4] = 15;
395 UcxArray copy = ucx_array_clone(array);
396 UCX_TEST_BEGIN
398 UCX_TEST_ASSERT(array.data != copy.data, "no true copy");
399 UCX_TEST_ASSERT(array.size == copy.size, "size mismatch");
400 UCX_TEST_ASSERT(array.capacity == copy.capacity, "capacity mismatch");
401 UCX_TEST_ASSERT(array.elemsize == copy.elemsize, "element size mismatch");
402 UCX_TEST_ASSERT(array.allocator == copy.allocator, "allocator mismatch");
403 UCX_TEST_ASSERT(ucx_array_equals(array, copy, ucx_cmp_int, NULL), "failed");
405 UCX_TEST_END
407 ucx_array_free(&array);
408 ucx_array_free(©);
409 }
411 static int ucx_cmp_int_reverse(const void* x, const void* y, void* data) {
412 return -ucx_cmp_int(x,y,data);
413 }
415 UCX_TEST(test_ucx_array_sort) {
416 int *elems;
418 UcxArray array = ucx_array_new(16, sizeof(int));
419 array.size = 5;
420 elems = array.data;
421 elems[0] = 47;
422 elems[1] = 11;
423 elems[2] = 0;
424 elems[3] = 8;
425 elems[4] = 15;
427 UcxArray expected = ucx_array_new(16, sizeof(int));
428 expected.size = 5;
429 elems = expected.data;
430 elems[0] = 0;
431 elems[1] = 8;
432 elems[2] = 11;
433 elems[3] = 15;
434 elems[4] = 47;
436 UcxArray expectedrev = ucx_array_new(16, sizeof(int));
437 expectedrev.size = 5;
438 elems = expectedrev.data;
439 elems[0] = 47;
440 elems[1] = 15;
441 elems[2] = 11;
442 elems[3] = 8;
443 elems[4] = 0;
446 UCX_TEST_BEGIN
447 void* original_ptr = array.data;
448 ucx_array_sort(array, ucx_cmp_int, NULL);
449 UCX_TEST_ASSERT(ucx_array_equals(array, expected, NULL, NULL), "failed");
450 UCX_TEST_ASSERT(array.size == 5, "size corrupted");
451 UCX_TEST_ASSERT(array.data == original_ptr, "shall not reallocate");
453 ucx_array_sort(array, ucx_cmp_int_reverse, NULL);
454 UCX_TEST_ASSERT(ucx_array_equals(array, expectedrev, NULL, NULL), "failed");
456 ucx_array_reserve(&array, 32);
457 ucx_array_reserve(&expected, 32);
458 array.size = expected.size = 32;
459 for (size_t i = 0 ; i < 32 ; i++) {
460 ((int*)array.data)[i]= ((i%2==0)?-1:1) * ((int) i);
461 ((int*)expected.data)[i] = (-30+2*i) - (i > 15 ? 1 : 0);
462 }
464 /* dummy third argument to trigger a possible fallback for qsort_s */
465 ucx_array_sort(array, ucx_cmp_int, array.data);
466 UCX_TEST_ASSERT(ucx_array_equals(array, expected, NULL, NULL),
467 "failed for bigger arrays");
468 UCX_TEST_END
470 ucx_array_free(&expected);
471 ucx_array_free(&array);
472 }
474 UCX_TEST(test_ucx_array_autogrow) {
475 int *elems;
476 UcxArray array = ucx_array_new(4, sizeof(int));
477 array.size = 3;
478 elems = array.data;
479 elems[0] = 47;
480 elems[1] = 11;
481 int x = 5;
483 UCX_TEST_BEGIN
485 void* oldptr = array.data;
487 ucx_array_append(&array, &x);
488 UCX_TEST_ASSERT(array.capacity == 4 && array.data == oldptr,
489 "array should not grow too early");
490 ucx_array_append(&array, &x);
491 elems = array.data;
492 UCX_TEST_ASSERT(array.capacity == 8, "array did not grow");
493 UCX_TEST_ASSERT(array.size == 5, "incorrect size after grow");
494 UCX_TEST_ASSERT(elems[3] == 5 && elems[4] == 5, "corrupt data");
496 UCX_TEST_END
497 ucx_array_free(&array);
498 }
500 UCX_TEST(test_ucx_array_shrink) {
501 UcxArray array = ucx_array_new(16, sizeof(int));
502 array.size = 4;
504 UCX_TEST_BEGIN
505 UCX_TEST_ASSERT(!ucx_array_shrink(&array), "failed");
506 UCX_TEST_ASSERT(array.capacity == 4, "incorrect capacity after shrink");
507 UCX_TEST_END
508 ucx_array_free(&array);
509 }
511 UCX_TEST(test_ucx_array_resize) {
512 UcxArray array = ucx_array_new(16, sizeof(int));
513 array.size = 8;
515 UCX_TEST_BEGIN
517 UCX_TEST_ASSERT(!ucx_array_resize(&array, 32), "failed");
518 UCX_TEST_ASSERT(array.capacity == 32, "incorrect capacity after resize");
519 UCX_TEST_ASSERT(array.size == 8, "incorrect size after resize");
521 UCX_TEST_ASSERT(!ucx_array_resize(&array, 4), "failed");
522 UCX_TEST_ASSERT(array.capacity == 4, "incorrect capacity after resize");
523 UCX_TEST_ASSERT(array.size == 4, "incorrect size after resize");
525 UCX_TEST_END
526 ucx_array_free(&array);
527 }
529 UCX_TEST(test_ucx_array_reserve) {
530 UcxArray array = ucx_array_new(16, sizeof(int));
532 UCX_TEST_BEGIN
534 UCX_TEST_ASSERT(!ucx_array_reserve(&array, 4), "failed");
535 UCX_TEST_ASSERT(array.capacity == 16, "reserve shall not shrink");
537 UCX_TEST_ASSERT(!ucx_array_resize(&array, 32), "failed");
538 UCX_TEST_ASSERT(array.capacity == 32, "incorrect capacity after reserve");
540 UCX_TEST_END
541 ucx_array_free(&array);
542 }