Mercurial > hg > ucx / file comparison

comparison: test/map_tests.c

test/map_tests.c

changeset 390
d345541018fa
parent 374
be77fb2da242
equal deleted inserted replaced
389:92e482410453 390:d345541018fa
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2017 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 */
28
29 #include "map_tests.h"
30 #include <ucx/utils.h>
31
32 UCX_TEST(test_ucx_map_new) {
33 UcxMap *map = ucx_map_new(16);
34 UCX_TEST_BEGIN
35 UCX_TEST_ASSERT(map->size == 16, "wrong size");
36 UCX_TEST_ASSERT(map->map != NULL, "failed");
37
38 UCX_TEST_END
39 ucx_map_free(map);
40 }
41
42 UCX_TEST(test_ucx_key) {
43 UcxKey key = ucx_key("This is a text.", 15);
44 UCX_TEST_BEGIN
45 UCX_TEST_ASSERT(strncmp((const char*)key.data, "This is a text.", 15) == 0,
46 "failed");
47 UCX_TEST_ASSERT(key.len == 15, "failed");
48 UCX_TEST_ASSERT(key.hash == 1261186027, "hash failed");
49
50 UCX_TEST_END
51 }
52
53 UCX_TEST(test_ucx_map_put) {
54
55 UcxMap *map = ucx_map_new(4);
56
57 int td[5];
58 td[0] = 10; td[1] = 42; td[2] = 70; td[3] = 11200; td[4] = 80000;
59
60 UCX_TEST_BEGIN
61 ucx_map_cstr_put(map, "Key2", &td[2]); /* 3.2 */
62 ucx_map_cstr_put(map, "Key0", &td[0]); /* 0.0 */
63 ucx_map_cstr_put(map, "Key1", &td[1]); /* 3.0 */
64 ucx_map_cstr_put(map, "KeY3", &td[3]); /* 3.1 */
65 ucx_map_cstr_put(map, "KEY4", &td[4]); /* 1.0 */
66
67 UCX_TEST_ASSERT(*((int*)map->map[0]->data) == td[0], "failed Key0");
68 UCX_TEST_ASSERT(*((int*)map->map[1]->data) == td[4], "failed KEY4");
69 UCX_TEST_ASSERT(*((int*)map->map[3]->data) == td[1], "failed Key1");
70
71 UCX_TEST_ASSERT(map->map[3]->next != NULL, "no list at slot 3");
72 UCX_TEST_ASSERT(map->map[3]->next->next != NULL, "list corrupt at slot 3");
73 UCX_TEST_ASSERT(*((int*)map->map[3]->next->data) == td[3],
74 "failed KeY3")
75 UCX_TEST_ASSERT(*((int*)map->map[3]->next->next->data) == td[2],
76 "failed KeY2");
77
78 UCX_TEST_ASSERT(map->map[0]->next == NULL, "slot 0 not terminated");
79 UCX_TEST_ASSERT(map->map[1]->next == NULL, "slot 1 not terminated");
80 UCX_TEST_ASSERT(map->map[2] == NULL, "slot 2 not empty");
81 UCX_TEST_ASSERT(map->map[3]->next->next->next == NULL,
82 "slot 3 not terminated")
83
84 ucx_map_cstr_put(map, "KeY3", &td[4]); /* replace 3.1 */
85
86 UCX_TEST_ASSERT(*((int*)map->map[3]->data) == td[1],
87 "overwrite failed")
88 UCX_TEST_ASSERT(*((int*)map->map[3]->next->data) == td[4],
89 "overwrite failed");
90 UCX_TEST_ASSERT(*((int*)map->map[3]->next->next->data) == td[2],
91 "overwrite failed")
92 UCX_TEST_ASSERT(map->map[3]->next->next->next == NULL, "overwrite failed");
93
94 UCX_TEST_END
95 ucx_map_free(map);
96 }
97
98 UCX_TEST(test_ucx_map_get) {
99 UcxMap *map = ucx_map_new(4);
100
101 int td[5];
102 td[0] = 10; td[1] = 42; td[2] = 70; td[3] = 11200; td[4] = 80000;
103
104 ucx_map_cstr_put(map, "Key2", &td[2]);
105 ucx_map_cstr_put(map, "Key0", &td[0]);
106 ucx_map_cstr_put(map, "Key1", &td[1]);
107 ucx_map_cstr_put(map, "KeY3", &td[3]);
108 ucx_map_cstr_put(map, "KEY4", &td[4]);
109 UCX_TEST_BEGIN
110
111 td[0] = *((int*)ucx_map_cstr_get(map, "Key0"));
112 td[1] = *((int*)ucx_map_cstr_get(map, "Key1"));
113 td[2] = *((int*)ucx_map_cstr_get(map, "Key2"));
114 td[3] = *((int*)ucx_map_cstr_get(map, "KeY3"));
115 td[4] = *((int*)ucx_map_cstr_get(map, "KEY4"));
116 UCX_TEST_ASSERT(td[0] == 10, "failed key 0");
117 UCX_TEST_ASSERT(td[1] == 42, "failed key 1");
118 UCX_TEST_ASSERT(td[2] == 70, "failed key 2");
119 UCX_TEST_ASSERT(td[3] == 11200, "failed key 3");
120 UCX_TEST_ASSERT(td[4] == 80000, "failed key 4");
121
122 UCX_TEST_ASSERT(map->count == 5, "expected 5 remaining values");
123 UCX_TEST_ASSERT(ucx_map_cstr_get(map, "Key0") != NULL, "element removed");
124
125 UCX_TEST_END
126 ucx_map_free(map);
127 }
128
129 UCX_TEST(test_ucx_map_remove) {
130 UcxMap *map = ucx_map_new(4);
131
132 int td[5];
133 td[0] = 10; td[1] = 42; td[2] = 70; td[3] = 11200; td[4] = 80000;
134
135 ucx_map_cstr_put(map, "Key2", &td[2]); /* 0 */
136 ucx_map_cstr_put(map, "Key0", &td[0]); /* 0 */
137 ucx_map_cstr_put(map, "Key1", &td[1]); /* 3 */
138 ucx_map_cstr_put(map, "KeY3", &td[3]); /* 2 */
139 ucx_map_cstr_put(map, "KEY4", &td[4]); /* 0 */
140 UCX_TEST_BEGIN
141
142 td[0] = *((int*)ucx_map_cstr_remove(map, "Key0"));
143 td[1] = *((int*)ucx_map_cstr_get(map, "Key1"));
144 td[2] = *((int*)ucx_map_cstr_remove(map, "Key2"));
145 td[3] = *((int*)ucx_map_cstr_get(map, "KeY3"));
146 td[4] = *((int*)ucx_map_cstr_get(map, "KEY4"));
147 UCX_TEST_ASSERT(td[0] == 10, "failed key 0");
148 UCX_TEST_ASSERT(td[1] == 42, "failed key 1");
149 UCX_TEST_ASSERT(td[2] == 70, "failed key 2");
150 UCX_TEST_ASSERT(td[3] == 11200, "failed key 3");
151 UCX_TEST_ASSERT(td[4] == 80000, "failed key 4");
152
153 UCX_TEST_ASSERT(map->count == 3, "expected 3 remaining values");
154 UCX_TEST_ASSERT(ucx_map_cstr_get(map, "Key0")==NULL, "element not removed");
155 UCX_TEST_ASSERT(ucx_map_cstr_get(map, "Key1")!=NULL, "element removed");
156 UCX_TEST_ASSERT(ucx_map_cstr_get(map, "Key2")==NULL, "element not removed");
157 UCX_TEST_ASSERT(ucx_map_cstr_get(map, "KeY3")!=NULL, "element removed");
158 UCX_TEST_ASSERT(ucx_map_cstr_get(map, "KEY4")!=NULL, "element removed");
159
160 UCX_TEST_ASSERT(ucx_map_cstr_remove(map, "Key2") == NULL,
161 "subsequent remove call shall return NULL");
162
163 UCX_TEST_END
164 ucx_map_free(map);
165 }
166
167 UCX_TEST(test_ucx_map_clear) {
168 UcxMap *map = ucx_map_new(4);
169
170 int value = 42;
171
172 ucx_map_cstr_put(map, "Key0", &value);
173 ucx_map_cstr_put(map, "Key1", &value);
174 ucx_map_cstr_put(map, "Key2", &value);
175 ucx_map_cstr_put(map, "Key3", &value);
176 ucx_map_cstr_put(map, "Key4", &value);
177 ucx_map_cstr_put(map, "Key5", &value);
178 ucx_map_cstr_put(map, "Key6", &value);
179 UCX_TEST_BEGIN
180
181 ucx_map_clear(map);
182
183 UCX_TEST_ASSERT(map->count == 0, "map has not been cleared");
184 UCX_TEST_ASSERT(map->size == 4, "map size has changed unexpectedly");
185
186 UCX_TEST_ASSERT(ucx_map_cstr_get(map, "Key0")==NULL, "element not removed");
187 UCX_TEST_ASSERT(ucx_map_cstr_get(map, "Key1")==NULL, "element not removed");
188 UCX_TEST_ASSERT(ucx_map_cstr_get(map, "Key2")==NULL, "element not removed");
189 UCX_TEST_ASSERT(ucx_map_cstr_get(map, "Key3")==NULL, "element not removed");
190 UCX_TEST_ASSERT(ucx_map_cstr_get(map, "Key4")==NULL, "element not removed");
191 UCX_TEST_ASSERT(ucx_map_cstr_get(map, "Key5")==NULL, "element not removed");
192 UCX_TEST_ASSERT(ucx_map_cstr_get(map, "Key6")==NULL, "element not removed");
193
194 UCX_TEST_END
195 ucx_map_free(map);
196 }
197
198 UCX_TEST_SUBROUTINE(test_ucx_map_itersrt, UcxMap *map) {
199 int v1 = 10;
200 int v2 = 15;
201 int v3 = 7;
202 int v4 = 9;
203
204 ucx_map_cstr_put(map, "v1", &v1);
205 ucx_map_cstr_put(map, "v2", &v2);
206 ucx_map_cstr_put(map, "v3", &v3);
207 ucx_map_cstr_put(map, "v4", &v4);
208
209 UcxMapIterator i = ucx_map_iterator(map);
210 int check = 0;
211 int hit = 0;
212
213 void* v;
214 UCX_MAP_FOREACH(key, v, i) {
215 check += *((int*)v);
216 hit++;
217 }
218
219 UCX_TEST_ASSERT(hit == 4, "test1: wrong number of hits");
220 UCX_TEST_ASSERT(check == v1+v2+v3+v4, "test1: wrong result");
221 }
222
223 UCX_TEST(test_ucx_map_iterator) {
224 UcxMap *map = ucx_map_new(16);
225 UCX_TEST_BEGIN
226 UCX_TEST_CALL_SUBROUTINE(test_ucx_map_itersrt, map)
227 UCX_TEST_END
228 ucx_map_free(map);
229 }
230
231 UCX_TEST(test_ucx_map_iterator_chain) {
232 UcxMap *map = ucx_map_new(1);
233 UCX_TEST_BEGIN
234 UCX_TEST_CALL_SUBROUTINE(test_ucx_map_itersrt, map)
235 UCX_TEST_END
236 ucx_map_free(map);
237 }
238
239 UCX_TEST(test_ucx_map_clone) {
240 UcxMap *map = ucx_map_new(4);
241
242 ucx_map_cstr_put(map, "key1", (void*)"value1");
243 ucx_map_cstr_put(map, "key2", (void*)"value2");
244 ucx_map_cstr_put(map, "key3", (void*)"value3");
245
246 UcxMap *clone = ucx_map_clone(map, NULL, NULL);
247
248 const char *v1 = (const char *) ucx_map_cstr_get(map, "key1");
249 const char *v2 = (const char *) ucx_map_cstr_get(map, "key2");
250 const char *v3 = (const char *) ucx_map_cstr_get(map, "key3");
251
252 UCX_TEST_BEGIN
253
254 UCX_TEST_ASSERT(v1 != NULL, "failed key 1");
255 UCX_TEST_ASSERT(v2 != NULL, "failed key 2");
256 UCX_TEST_ASSERT(v3 != NULL, "failed key 3");
257
258 const char *c1 = (const char *) ucx_map_cstr_get(clone, "key1");
259 const char *c2 = (const char *) ucx_map_cstr_get(clone, "key2");
260 const char *c3 = (const char *) ucx_map_cstr_get(clone, "key3");
261
262 UCX_TEST_ASSERT(c1 != NULL, "failed key 1 (clone)");
263 UCX_TEST_ASSERT(c2 != NULL, "failed key 2 (clone)");
264 UCX_TEST_ASSERT(c3 != NULL, "failed key 3 (clone)");
265
266 UCX_TEST_ASSERT(strcmp(c1, v1) == 0, "value error for key1");
267 UCX_TEST_ASSERT(strcmp(c2, v2) == 0, "value error for key2");
268 UCX_TEST_ASSERT(strcmp(c3, v3) == 0, "value error for key3");
269
270 UCX_TEST_END
271
272 ucx_map_free(map);
273 ucx_map_free(clone);
274 }
275
276 UCX_TEST(test_ucx_map_rehash) {
277 UcxMap *map = ucx_map_new(4);
278
279 char keys[10][5];
280 char values[10][7];
281 for (int i = 0 ; i < 10 ; i++) {
282 strcpy(keys[i], "key");
283 keys[i][3] = 48+i; keys[i][4] = 0;
284 strcpy(values[i], "value");
285 values[i][5] = 48+i; values[i][6] = 0;
286
287 ucx_map_cstr_put(map, keys[i], values[i]);
288 }
289
290 ucx_map_rehash(map);
291
292 UCX_TEST_BEGIN
293 UCX_TEST_ASSERT(map->size == 25, "new capacity shall be 2.5 * count");
294 UCX_TEST_ASSERT(map->count == 10, "new map element count incorrect");
295 for (int i = 0 ; i < 10 ; i++) {
296 const char *value = (const char *) ucx_map_cstr_get(map, keys[i]);
297 UCX_TEST_ASSERT(value != NULL, "new map is missing old keys");
298 UCX_TEST_ASSERT(strncmp(value, values[i], 6) == 0,
299 "new map contains incorrect values");
300 }
301 ucx_map_rehash(map);
302 UCX_TEST_ASSERT(map->size == 25,
303 "subsequent rehashing call shall not change size");
304 UCX_TEST_END
305
306 ucx_map_free(map);
307 }
308
309 UCX_TEST(test_ucx_map_union) {
310 int td[5];
311 size_t intlen = sizeof(int);
312 td[0] = 10; td[1] = 42; td[2] = 47; td[3] = 1337; td[4] = 9000;
313
314 UcxMap *first = ucx_map_new(4);
315 UcxMap *second = ucx_map_new(4);
316
317 ucx_map_cstr_put(first, "key0", &td[0]);
318 ucx_map_cstr_put(first, "key1", &td[1]);
319 ucx_map_cstr_put(second, "key2", &td[2]);
320 ucx_map_cstr_put(second, "key0", &td[3]);
321 ucx_map_cstr_put(second, "key3", &td[4]);
322
323 UcxMap *result = ucx_map_union(first, second, ucx_memcpy, &intlen);
324
325 UCX_TEST_BEGIN
326
327 int* r;
328 UCX_TEST_ASSERT(result->count == 4,
329 "result has incorrect number of elements");
330
331 r = (int*)ucx_map_cstr_get(result, "key0");
332 UCX_TEST_ASSERT(!!r, "key0 is not present");
333 UCX_TEST_ASSERT(*r == td[3], "key0 has not been overwritten");
334 r = (int*)ucx_map_cstr_get(result, "key1");
335 UCX_TEST_ASSERT(!!r, "key1 is not present");
336 UCX_TEST_ASSERT(*r == td[1], "key1 contains wrong data");
337 r = (int*)ucx_map_cstr_get(result, "key2");
338 UCX_TEST_ASSERT(!!r, "key2 is not present");
339 UCX_TEST_ASSERT(*r == td[2], "key2 contains wrong data");
340 r = (int*)ucx_map_cstr_get(result, "key3");
341 UCX_TEST_ASSERT(!!r, "key3 is not present");
342 UCX_TEST_ASSERT(*r == td[4], "key3 contains wrong data");
343
344 UCX_TEST_END
345
346 ucx_map_free_content(result, NULL);
347 ucx_map_free(result);
348 ucx_map_free(second);
349 ucx_map_free(first);
350 }
351
352 UCX_TEST(test_ucx_map_intersection) {
353 int td[5];
354 size_t intlen = sizeof(int);
355 td[0] = 10; td[1] = 42; td[2] = 47; td[3] = 1337; td[4] = 9000;
356
357 UcxMap *first = ucx_map_new(4);
358 UcxMap *second = ucx_map_new(4);
359
360 ucx_map_cstr_put(first, "key0", &td[0]);
361 ucx_map_cstr_put(first, "key1", &td[1]);
362 ucx_map_cstr_put(first, "key4", &td[3]);
363 ucx_map_cstr_put(second, "key2", &td[2]);
364 ucx_map_cstr_put(second, "key0", &td[3]);
365 ucx_map_cstr_put(second, "key3", &td[4]);
366 ucx_map_cstr_put(second, "key4", &td[4]);
367
368 UcxMap *result = ucx_map_intersection(first, second,
369 ucx_memcpy, &intlen);
370
371 UCX_TEST_BEGIN
372
373 int* r;
374 UCX_TEST_ASSERT(result->count == 2,
375 "result has incorrect number of elements");
376
377 r = (int*)ucx_map_cstr_get(result, "key0");
378 UCX_TEST_ASSERT(!!r, "key0 is not present");
379 UCX_TEST_ASSERT(*r == td[0], "key0 has not original data");
380 r = (int*)ucx_map_cstr_get(result, "key4");
381 UCX_TEST_ASSERT(!!r, "key4 is not present");
382 UCX_TEST_ASSERT(*r == td[3], "key4 has not original data");
383
384 UCX_TEST_END
385
386 ucx_map_free_content(result, NULL);
387 ucx_map_free(result);
388 ucx_map_free(second);
389 ucx_map_free(first);
390 }
391
392
393 UCX_TEST(test_ucx_map_difference) {
394 int td[5];
395 size_t intlen = sizeof(int);
396 td[0] = 10; td[1] = 42; td[2] = 47; td[3] = 1337; td[4] = 9000;
397
398 UcxMap *first = ucx_map_new(4);
399 UcxMap *second = ucx_map_new(4);
400
401 ucx_map_cstr_put(first, "key0", &td[0]);
402 ucx_map_cstr_put(first, "key1", &td[1]);
403 ucx_map_cstr_put(first, "key2", &td[2]);
404 ucx_map_cstr_put(first, "key4", &td[3]);
405 ucx_map_cstr_put(second, "key0", &td[3]);
406 ucx_map_cstr_put(second, "key3", &td[4]);
407 ucx_map_cstr_put(second, "key4", &td[4]);
408
409 UcxMap *result = ucx_map_difference(first, second, ucx_memcpy, &intlen);
410
411 UCX_TEST_BEGIN
412
413 int* r;
414 UCX_TEST_ASSERT(result->count == 2,
415 "result has incorrect number of elements");
416
417 r = (int*)ucx_map_cstr_get(result, "key1");
418 UCX_TEST_ASSERT(!!r, "key1 is not present");
419 UCX_TEST_ASSERT(*r == td[1], "key1 has incorrect data");
420 r = (int*)ucx_map_cstr_get(result, "key2");
421 UCX_TEST_ASSERT(!!r, "key2 is not present");
422 UCX_TEST_ASSERT(*r == td[2], "key2 has incorrect data");
423
424 UCX_TEST_END
425
426 ucx_map_free_content(result, NULL);
427 ucx_map_free(result);
428 ucx_map_free(second);
429 ucx_map_free(first);
430 }
431

Mercurial Repository: ucx

mercurial