1 /*
2 * Copyright (c) 2011, Collabora Ltd.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 * * Redistributions of source code must retain the above
9 * copyright notice, this list of conditions and the
10 * following disclaimer.
11 * * Redistributions in binary form must reproduce the
12 * above copyright notice, this list of conditions and
13 * the following disclaimer in the documentation and/or
14 * other materials provided with the distribution.
15 * * The names of contributors to this software may not be
16 * used to endorse or promote products derived from this
17 * software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
22 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
23 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
24 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
25 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
26 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
27 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
28 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
29 * THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
30 * DAMAGE.
31 *
32 * Author: Stef Walter <stefw@collabora.co.uk>
33 */
34
35 #include "config.h"
36 #include "test.h"
37
38 #include <assert.h>
39 #include <stdlib.h>
40 #include <stdio.h>
41 #include <string.h>
42
43 #include "dict.h"
44
45 static void
test_create(void)46 test_create (void)
47 {
48 p11_dict *map;
49
50 map = p11_dict_new (p11_dict_direct_hash, p11_dict_direct_equal, NULL, NULL);
51 assert_ptr_not_null (map);
52 p11_dict_free (map);
53 }
54
55 static void
test_free_null(void)56 test_free_null (void)
57 {
58 p11_dict_free (NULL);
59 }
60
61 typedef struct {
62 int value;
63 bool freed;
64 } Key;
65
66 static unsigned int
key_hash(const void * ptr)67 key_hash (const void *ptr)
68 {
69 const Key *k = ptr;
70 assert (!k->freed);
71 return p11_dict_intptr_hash (&k->value);
72 }
73
74 static bool
key_equal(const void * one,const void * two)75 key_equal (const void *one,
76 const void *two)
77 {
78 const Key *k1 = one;
79 const Key *k2 = two;
80 assert (!k1->freed);
81 assert (!k2->freed);
82 return p11_dict_intptr_equal (&k1->value, &k2->value);
83 }
84
85 static void
key_destroy(void * data)86 key_destroy (void *data)
87 {
88 Key *k = data;
89 assert (!k->freed);
90 k->freed = true;
91 }
92
93 static void
value_destroy(void * data)94 value_destroy (void *data)
95 {
96 int *value = data;
97 *value = 2;
98 }
99
100 static void
test_free_destroys(void)101 test_free_destroys (void)
102 {
103 p11_dict *map;
104 Key key = { 8, 0 };
105 int value = 0;
106
107 map = p11_dict_new (key_hash, key_equal, key_destroy, value_destroy);
108 assert_ptr_not_null (map);
109 if (!p11_dict_set (map, &key, &value))
110 assert_not_reached ();
111 p11_dict_free (map);
112
113 assert_num_eq (true, key.freed);
114 assert_num_eq (2, value);
115 }
116
117 static void
test_iterate(void)118 test_iterate (void)
119 {
120 p11_dict *map;
121 p11_dictiter iter;
122 int key = 1;
123 int value = 2;
124 void *pkey;
125 void *pvalue;
126 int ret;
127
128 map = p11_dict_new (p11_dict_direct_hash, p11_dict_direct_equal, NULL, NULL);
129 assert_ptr_not_null (map);
130 if (!p11_dict_set (map, &key, &value))
131 assert_not_reached ();
132
133 p11_dict_iterate (map, &iter);
134
135 ret = p11_dict_next (&iter, &pkey, &pvalue);
136 assert_num_eq (1, ret);
137 assert_ptr_eq (pkey, &key);
138 assert_ptr_eq (pvalue, &value);
139
140 ret = p11_dict_next (&iter, &pkey, &pvalue);
141 assert_num_eq (0, ret);
142
143 p11_dict_free (map);
144 }
145
146 static int
compar_strings(const void * one,const void * two)147 compar_strings (const void *one,
148 const void *two)
149 {
150 char **p1 = (char **)one;
151 char **p2 = (char **)two;
152 return strcmp (*p1, *p2);
153 }
154
155 static void
test_iterate_remove(void)156 test_iterate_remove (void)
157 {
158 p11_dict *map;
159 p11_dictiter iter;
160 char *keys[] = { "111", "222", "333" };
161 char *values[] = { "444", "555", "666" };
162 void *okeys[3];
163 void *ovalues[3];
164 bool ret;
165 int i;
166
167 map = p11_dict_new (p11_dict_str_hash, p11_dict_str_equal, NULL, NULL);
168 assert_ptr_not_null (map);
169
170 for (i = 0; i < 3; i++) {
171 if (!p11_dict_set (map, keys[i], values[i]))
172 assert_not_reached ();
173 }
174
175 p11_dict_iterate (map, &iter);
176
177 ret = p11_dict_next (&iter, &okeys[0], &ovalues[0]);
178 assert_num_eq (true, ret);
179
180 ret = p11_dict_next (&iter, &okeys[1], &ovalues[1]);
181 assert_num_eq (true, ret);
182 if (!p11_dict_remove (map, okeys[1]))
183 assert_not_reached ();
184
185 ret = p11_dict_next (&iter, &okeys[2], &ovalues[2]);
186 assert_num_eq (true, ret);
187
188 ret = p11_dict_next (&iter, NULL, NULL);
189 assert_num_eq (false, ret);
190
191 assert_num_eq (2, p11_dict_size (map));
192 p11_dict_free (map);
193
194 qsort (okeys, 3, sizeof (void *), compar_strings);
195 qsort (ovalues, 3, sizeof (void *), compar_strings);
196
197 for (i = 0; i < 3; i++) {
198 assert_str_eq (keys[i], okeys[i]);
199 assert_ptr_eq (keys[i], okeys[i]);
200 assert_str_eq (values[i], ovalues[i]);
201 assert_ptr_eq (values[i], ovalues[i]);
202 }
203 }
204
205 static void
test_set_get(void)206 test_set_get (void)
207 {
208 char *key = "KEY";
209 char *value = "VALUE";
210 char *check;
211 p11_dict *map;
212
213 map = p11_dict_new (p11_dict_str_hash, p11_dict_str_equal, NULL, NULL);
214 p11_dict_set (map, key, value);
215 check = p11_dict_get (map, key);
216 assert_ptr_eq (check, value);
217
218 p11_dict_free (map);
219 }
220
221 static void
test_set_get_remove(void)222 test_set_get_remove (void)
223 {
224 char *key = "KEY";
225 char *value = "VALUE";
226 char *check;
227 p11_dict *map;
228 bool ret;
229
230 map = p11_dict_new (p11_dict_str_hash, p11_dict_str_equal, NULL, NULL);
231
232 if (!p11_dict_set (map, key, value))
233 assert_not_reached ();
234
235 check = p11_dict_get (map, key);
236 assert_ptr_eq (check, value);
237
238 ret = p11_dict_remove (map, key);
239 assert_num_eq (true, ret);
240 ret = p11_dict_remove (map, key);
241 assert_num_eq (false, ret);
242
243 check = p11_dict_get (map, key);
244 assert (check == NULL);
245
246 p11_dict_free (map);
247 }
248
249 static void
test_set_clear(void)250 test_set_clear (void)
251 {
252 char *key = "KEY";
253 char *value = "VALUE";
254 char *check;
255 p11_dict *map;
256
257 map = p11_dict_new (p11_dict_direct_hash, p11_dict_direct_equal, NULL, NULL);
258
259 if (!p11_dict_set (map, key, value))
260 assert_not_reached ();
261
262 p11_dict_clear (map);
263
264 check = p11_dict_get (map, key);
265 assert (check == NULL);
266
267 p11_dict_free (map);
268 }
269
270 static void
test_remove_destroys(void)271 test_remove_destroys (void)
272 {
273 p11_dict *map;
274 Key key = { 8, 0 };
275 int value = 0;
276 bool ret;
277
278 map = p11_dict_new (key_hash, key_equal, key_destroy, value_destroy);
279 assert_ptr_not_null (map);
280 if (!p11_dict_set (map, &key, &value))
281 assert_not_reached ();
282
283 ret = p11_dict_remove (map, &key);
284 assert_num_eq (true, ret);
285 assert_num_eq (true, key.freed);
286 assert_num_eq (2, value);
287
288 /* should not be destroyed again */
289 key.freed = false;
290 value = 0;
291
292 ret = p11_dict_remove (map, &key);
293 assert_num_eq (false, ret);
294 assert_num_eq (false, key.freed);
295 assert_num_eq (0, value);
296
297 /* should not be destroyed again */
298 key.freed = false;
299 value = 0;
300
301 p11_dict_free (map);
302
303 assert_num_eq (false, key.freed);
304 assert_num_eq (0, value);
305 }
306
307 static void
test_set_destroys(void)308 test_set_destroys (void)
309 {
310 p11_dict *map;
311 Key key = { 8, 0 };
312 Key key2 = { 8, 0 };
313 int value, value2;
314 bool ret;
315
316 map = p11_dict_new (key_hash, key_equal, key_destroy, value_destroy);
317 assert_ptr_not_null (map);
318 if (!p11_dict_set (map, &key, &value))
319 assert_not_reached ();
320
321 key.freed = key2.freed = false;
322 value = value2 = 0;
323
324 /* Setting same key and value, should not be destroyed */
325 ret = p11_dict_set (map, &key, &value);
326 assert_num_eq (true, ret);
327 assert_num_eq (false, key.freed);
328 assert_num_eq (false, key2.freed);
329 assert_num_eq (0, value);
330 assert_num_eq (0, value2);
331
332 key.freed = key2.freed = false;
333 value = value2 = 0;
334
335 /* Setting a new key same value, key should be destroyed */
336 ret = p11_dict_set (map, &key2, &value);
337 assert_num_eq (true, ret);
338 assert_num_eq (true, key.freed);
339 assert_num_eq (false, key2.freed);
340 assert_num_eq (0, value);
341 assert_num_eq (0, value2);
342
343 key.freed = key2.freed = false;
344 value = value2 = 0;
345
346 /* Setting same key, new value, value should be destroyed */
347 ret = p11_dict_set (map, &key2, &value2);
348 assert_num_eq (true, ret);
349 assert_num_eq (false, key.freed);
350 assert_num_eq (false, key2.freed);
351 assert_num_eq (2, value);
352 assert_num_eq (0, value2);
353
354 key.freed = key2.freed = false;
355 value = value2 = 0;
356
357 /* Setting new key new value, both should be destroyed */
358 ret = p11_dict_set (map, &key, &value);
359 assert_num_eq (true, ret);
360 assert_num_eq (false, key.freed);
361 assert_num_eq (true, key2.freed);
362 assert_num_eq (0, value);
363 assert_num_eq (2, value2);
364
365 key.freed = key2.freed = false;
366 value = value2 = 0;
367
368 p11_dict_free (map);
369 assert_num_eq (true, key.freed);
370 assert_num_eq (2, value);
371 assert_num_eq (false, key2.freed);
372 assert_num_eq (0, value2);
373 }
374
375
376 static void
test_clear_destroys(void)377 test_clear_destroys (void)
378 {
379 p11_dict *map;
380 Key key = { 18, 0 };
381 int value = 0;
382
383 map = p11_dict_new (key_hash, key_equal, key_destroy, value_destroy);
384 assert_ptr_not_null (map);
385 if (!p11_dict_set (map, &key, &value))
386 assert_not_reached ();
387
388 p11_dict_clear (map);
389 assert_num_eq (true, key.freed);
390 assert_num_eq (2, value);
391
392 /* should not be destroyed again */
393 key.freed = false;
394 value = 0;
395
396 p11_dict_clear (map);
397 assert_num_eq (false, key.freed);
398 assert_num_eq (0, value);
399
400 /* should not be destroyed again */
401 key.freed = false;
402 value = 0;
403
404 p11_dict_free (map);
405
406 assert_num_eq (false, key.freed);
407 assert_num_eq (0, value);
408 }
409
410 static unsigned int
test_hash_intptr_with_collisions(const void * data)411 test_hash_intptr_with_collisions (const void *data)
412 {
413 /* lots and lots of collisions, only returns 100 values */
414 return (unsigned int)(*((int*)data) % 100);
415 }
416
417 static void
test_hash_add_check_lots_and_collisions(void)418 test_hash_add_check_lots_and_collisions (void)
419 {
420 p11_dict *map;
421 int *value;
422 int i;
423
424 map = p11_dict_new (test_hash_intptr_with_collisions,
425 p11_dict_intptr_equal, NULL, free);
426
427 for (i = 0; i < 20000; ++i) {
428 value = malloc (sizeof (int));
429 assert (value != NULL);
430 *value = i;
431 if (!p11_dict_set (map, value, value))
432 assert_not_reached ();
433 }
434
435 for (i = 0; i < 20000; ++i) {
436 value = p11_dict_get (map, &i);
437 assert_ptr_not_null (value);
438 assert_num_eq (i, *value);
439 }
440
441 p11_dict_free (map);
442 }
443
444 static void
test_hash_count(void)445 test_hash_count (void)
446 {
447 p11_dict *map;
448 int *value;
449 int i;
450 bool ret;
451
452 map = p11_dict_new (p11_dict_intptr_hash, p11_dict_intptr_equal, NULL, free);
453
454 assert_num_eq (0, p11_dict_size (map));
455
456 for (i = 0; i < 20000; ++i) {
457 value = malloc (sizeof (int));
458 assert (value != NULL);
459 *value = i;
460 if (!p11_dict_set (map, value, value))
461 assert_not_reached ();
462 assert_num_eq (i + 1, p11_dict_size (map));
463 }
464
465 for (i = 0; i < 20000; ++i) {
466 ret = p11_dict_remove (map, &i);
467 assert_num_eq (true, ret);
468 assert_num_eq (20000 - (i + 1), p11_dict_size (map));
469 }
470
471 p11_dict_clear (map);
472 assert_num_eq (0, p11_dict_size (map));
473
474 p11_dict_free (map);
475 }
476
477 static void
test_hash_ulongptr(void)478 test_hash_ulongptr (void)
479 {
480 p11_dict *map;
481 unsigned long *value;
482 unsigned long i;
483
484 map = p11_dict_new (p11_dict_ulongptr_hash, p11_dict_ulongptr_equal, NULL, free);
485
486 for (i = 0; i < 20000; ++i) {
487 value = malloc (sizeof (unsigned long));
488 assert (value != NULL);
489 *value = i;
490 if (!p11_dict_set (map, value, value))
491 assert_not_reached ();
492 }
493
494 for (i = 0; i < 20000; ++i) {
495 value = p11_dict_get (map, &i);
496 assert_ptr_not_null (value);
497 assert_num_eq (i, *value);
498 }
499
500 p11_dict_free (map);
501 }
502
503 int
main(int argc,char * argv[])504 main (int argc,
505 char *argv[])
506 {
507 p11_test (test_create, "/dict/create");
508 p11_test (test_set_get, "/dict/set-get");
509 p11_test (test_set_get_remove, "/dict/set-get-remove");
510 p11_test (test_remove_destroys, "/dict/remove-destroys");
511 p11_test (test_set_clear, "/dict/set-clear");
512 p11_test (test_set_destroys, "/dict/set-destroys");
513 p11_test (test_clear_destroys, "/dict/clear-destroys");
514 p11_test (test_free_null, "/dict/free-null");
515 p11_test (test_free_destroys, "/dict/free-destroys");
516 p11_test (test_iterate, "/dict/iterate");
517 p11_test (test_iterate_remove, "/dict/iterate-remove");
518 p11_test (test_hash_add_check_lots_and_collisions, "/dict/add-check-lots-and-collisions");
519 p11_test (test_hash_count, "/dict/count");
520 p11_test (test_hash_ulongptr, "/dict/ulongptr");
521 return p11_test_run (argc, argv);
522 }
523