1 /*
2 * Copyright 2020 Daniel Silverstone <dsilvers@netsurf-browser.org>
3 * Copyright 2016 Vincent Sanders <vince@netsurf-browser.org>
4 *
5 * This file is part of NetSurf, http://www.netsurf-browser.org/
6 *
7 * NetSurf is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; version 2 of the License.
10 *
11 * NetSurf is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program. If not, see <http://www.gnu.org/licenses/>.
18 */
19
20 /**
21 * \file
22 * Tests for hashmap.
23 *
24 * In part, borrows from the corestrings tests
25 */
26
27 #include "utils/config.h"
28
29 #include <assert.h>
30 #include <stdbool.h>
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <check.h>
35 #include <limits.h>
36
37 #include <libwapcaplet/libwapcaplet.h>
38
39 #include "utils/nsurl.h"
40 #include "utils/corestrings.h"
41 #include "utils/hashmap.h"
42
43 #include "test/malloc_fig.h"
44
45 /* Low level fixtures */
46
47 static void
corestring_create(void)48 corestring_create(void)
49 {
50 ck_assert(corestrings_init() == NSERROR_OK);
51 }
52
53 /**
54 * iterator for any remaining strings in teardown fixture
55 */
56 static void
netsurf_lwc_iterator(lwc_string * str,void * pw)57 netsurf_lwc_iterator(lwc_string *str, void *pw)
58 {
59 fprintf(stderr,
60 "[%3u] %.*s",
61 str->refcnt,
62 (int)lwc_string_length(str),
63 lwc_string_data(str));
64 }
65
66 static void
corestring_teardown(void)67 corestring_teardown(void)
68 {
69 corestrings_fini();
70
71 lwc_iterate_strings(netsurf_lwc_iterator, NULL);
72 }
73
74 /* Infra */
75
76 static ssize_t keys;
77 static ssize_t values;
78
79 typedef struct {
80 nsurl *key;
81 } hashmap_test_value_t;
82
83 static void *
key_clone(void * key)84 key_clone(void *key)
85 {
86 /* Pretend cloning costs memory so that it can fail for
87 * testing error return pathways
88 */
89 void *temp = malloc(1);
90 if (temp == NULL) return NULL;
91 free(temp);
92 /* In reality we just ref the nsurl */
93 keys++;
94 return nsurl_ref((nsurl *)key);
95 }
96
97 static void
key_destroy(void * key)98 key_destroy(void *key)
99 {
100 keys--;
101 nsurl_unref((nsurl *)key);
102 }
103
104 static uint32_t
key_hash(void * key)105 key_hash(void *key)
106 {
107 /* Deliberately bad hash.
108 * returns 0, 1, 2, or 3 to force bucket chaining
109 */
110 return nsurl_hash((nsurl *)key) & 3;
111 }
112
113 static bool
key_eq(void * key1,void * key2)114 key_eq(void *key1, void *key2)
115 {
116 return nsurl_compare((nsurl *)key1, (nsurl*)key2, NSURL_COMPLETE);
117 }
118
119 static void *
value_alloc(void * key)120 value_alloc(void *key)
121 {
122 hashmap_test_value_t *ret = malloc(sizeof(hashmap_test_value_t));
123
124 if (ret == NULL)
125 return NULL;
126
127 ret->key = (nsurl *)key;
128
129 values++;
130
131 return ret;
132 }
133
134 static void
value_destroy(void * value)135 value_destroy(void *value)
136 {
137 hashmap_test_value_t *val = value;
138
139 /* Do nothing for now */
140
141 free(val);
142 values--;
143 }
144
145 static hashmap_parameters_t test_params = {
146 .key_clone = key_clone,
147 .key_hash = key_hash,
148 .key_eq = key_eq,
149 .key_destroy = key_destroy,
150 .value_alloc = value_alloc,
151 .value_destroy = value_destroy,
152 };
153
154 /* Iteration helpers */
155
156 static size_t iteration_counter = 0;
157 static size_t iteration_stop = 0;
158 static char iteration_ctx = 0;
159
160 static bool
hashmap_test_iterator_cb(void * key,void * value,void * ctx)161 hashmap_test_iterator_cb(void *key, void *value, void *ctx)
162 {
163 ck_assert(ctx == &iteration_ctx);
164 iteration_counter++;
165 return iteration_counter == iteration_stop;
166 }
167
168 /* Fixtures for basic tests */
169
170 static hashmap_t *test_hashmap = NULL;
171
172 static void
basic_fixture_create(void)173 basic_fixture_create(void)
174 {
175 corestring_create();
176
177 test_hashmap = hashmap_create(&test_params);
178
179 ck_assert(test_hashmap != NULL);
180 ck_assert_int_eq(keys, 0);
181 ck_assert_int_eq(values, 0);
182 }
183
184 static void
basic_fixture_teardown(void)185 basic_fixture_teardown(void)
186 {
187 hashmap_destroy(test_hashmap);
188 test_hashmap = NULL;
189
190 ck_assert_int_eq(keys, 0);
191 ck_assert_int_eq(values, 0);
192
193 corestring_teardown();
194 }
195
196 /* basic api tests */
197
START_TEST(empty_hashmap_create_destroy)198 START_TEST(empty_hashmap_create_destroy)
199 {
200 ck_assert_int_eq(hashmap_count(test_hashmap), 0);
201 }
202 END_TEST
203
START_TEST(check_not_present)204 START_TEST(check_not_present)
205 {
206 /* We're checking for a key which should not be present */
207 ck_assert(hashmap_lookup(test_hashmap, corestring_nsurl_about_blank) == NULL);
208 }
209 END_TEST
210
START_TEST(insert_works)211 START_TEST(insert_works)
212 {
213 hashmap_test_value_t *value = hashmap_insert(test_hashmap, corestring_nsurl_about_blank);
214 ck_assert(value != NULL);
215 ck_assert(value->key == corestring_nsurl_about_blank);
216 ck_assert_int_eq(hashmap_count(test_hashmap), 1);
217 }
218 END_TEST
219
START_TEST(remove_not_present)220 START_TEST(remove_not_present)
221 {
222 ck_assert(hashmap_remove(test_hashmap, corestring_nsurl_about_blank) == false);
223 }
224 END_TEST
225
START_TEST(insert_then_remove)226 START_TEST(insert_then_remove)
227 {
228 hashmap_test_value_t *value = hashmap_insert(test_hashmap, corestring_nsurl_about_blank);
229 ck_assert(value != NULL);
230 ck_assert(value->key == corestring_nsurl_about_blank);
231 ck_assert_int_eq(keys, 1);
232 ck_assert_int_eq(values, 1);
233 ck_assert_int_eq(hashmap_count(test_hashmap), 1);
234 ck_assert(hashmap_remove(test_hashmap, corestring_nsurl_about_blank) == true);
235 ck_assert_int_eq(keys, 0);
236 ck_assert_int_eq(values, 0);
237 ck_assert_int_eq(hashmap_count(test_hashmap), 0);
238 }
239 END_TEST
240
START_TEST(insert_then_lookup)241 START_TEST(insert_then_lookup)
242 {
243 hashmap_test_value_t *value = hashmap_insert(test_hashmap, corestring_nsurl_about_blank);
244 ck_assert(value != NULL);
245 ck_assert(value->key == corestring_nsurl_about_blank);
246 ck_assert(hashmap_lookup(test_hashmap, corestring_nsurl_about_blank) == value);
247 }
248 END_TEST
249
START_TEST(iterate_empty)250 START_TEST(iterate_empty)
251 {
252 iteration_stop = iteration_counter = 0;
253 ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, &iteration_ctx) == false);
254 ck_assert_int_eq(iteration_counter, 0);
255 }
256 END_TEST
257
START_TEST(iterate_one)258 START_TEST(iterate_one)
259 {
260 iteration_stop = iteration_counter = 0;
261 hashmap_test_value_t *value = hashmap_insert(test_hashmap, corestring_nsurl_about_blank);
262 ck_assert(value != NULL);
263 ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, &iteration_ctx) == false);
264 ck_assert_int_eq(iteration_counter, 1);
265 }
266 END_TEST
267
START_TEST(iterate_one_and_stop)268 START_TEST(iterate_one_and_stop)
269 {
270 iteration_stop = 1;
271 iteration_counter = 0;
272 hashmap_test_value_t *value = hashmap_insert(test_hashmap, corestring_nsurl_about_blank);
273 ck_assert(value != NULL);
274 ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, &iteration_ctx) == true);
275 ck_assert_int_eq(iteration_counter, 1);
276 }
277 END_TEST
278
basic_api_case_create(void)279 static TCase *basic_api_case_create(void)
280 {
281 TCase *tc;
282 tc = tcase_create("Basic API");
283
284 tcase_add_unchecked_fixture(tc,
285 basic_fixture_create,
286 basic_fixture_teardown);
287
288 tcase_add_test(tc, empty_hashmap_create_destroy);
289 tcase_add_test(tc, check_not_present);
290 tcase_add_test(tc, insert_works);
291 tcase_add_test(tc, remove_not_present);
292 tcase_add_test(tc, insert_then_remove);
293 tcase_add_test(tc, insert_then_lookup);
294
295 tcase_add_test(tc, iterate_empty);
296 tcase_add_test(tc, iterate_one);
297 tcase_add_test(tc, iterate_one_and_stop);
298
299 return tc;
300 }
301
302 /* Chain verification test suite */
303
304 typedef struct {
305 const char *url;
306 nsurl *nsurl;
307 } case_pair;
308
309 /* The hobbled hash has only 4 values
310 * By having at least 12 test cases, we can be confident that
311 * at worst they'll all be on one chain, but at best there'll
312 * be four chains of 3 entries which means we should be able
313 * to validate prevptr and next in all cases.
314 */
315 static case_pair chain_pairs[] = {
316 { "https://www.google.com/", NULL },
317 { "https://www.google.co.uk/", NULL },
318 { "https://www.netsurf-browser.org/", NULL },
319 { "http://www.google.com/", NULL },
320 { "http://www.google.co.uk/", NULL },
321 { "http://www.netsurf-browser.org/", NULL },
322 { "file:///tmp/test.html", NULL },
323 { "file:///tmp/inner.html", NULL },
324 { "about:blank", NULL },
325 { "about:welcome", NULL },
326 { "about:testament", NULL },
327 { "resources:default.css", NULL },
328 { NULL, NULL }
329 };
330
331 static void
chain_fixture_create(void)332 chain_fixture_create(void)
333 {
334 case_pair *chain_case = chain_pairs;
335 basic_fixture_create();
336
337 while (chain_case->url != NULL) {
338 ck_assert(nsurl_create(chain_case->url, &chain_case->nsurl) == NSERROR_OK);
339 chain_case++;
340 }
341
342 }
343
344 static void
chain_fixture_teardown(void)345 chain_fixture_teardown(void)
346 {
347 case_pair *chain_case = chain_pairs;
348
349 while (chain_case->url != NULL) {
350 nsurl_unref(chain_case->nsurl);
351 chain_case->nsurl = NULL;
352 chain_case++;
353 }
354
355 basic_fixture_teardown();
356 }
357
START_TEST(chain_add_remove_all)358 START_TEST(chain_add_remove_all)
359 {
360 case_pair *chain_case;
361
362 for (chain_case = chain_pairs;
363 chain_case->url != NULL;
364 chain_case++) {
365 ck_assert(hashmap_lookup(test_hashmap, chain_case->nsurl) == NULL);
366 ck_assert(hashmap_insert(test_hashmap, chain_case->nsurl) != NULL);
367 ck_assert(hashmap_lookup(test_hashmap, chain_case->nsurl) != NULL);
368 ck_assert(hashmap_remove(test_hashmap, chain_case->nsurl) == true);
369 }
370
371 ck_assert_int_eq(keys, 0);
372 ck_assert_int_eq(values, 0);
373 }
374 END_TEST
375
START_TEST(chain_add_all_remove_all)376 START_TEST(chain_add_all_remove_all)
377 {
378 case_pair *chain_case;
379
380 for (chain_case = chain_pairs;
381 chain_case->url != NULL;
382 chain_case++) {
383 ck_assert(hashmap_lookup(test_hashmap, chain_case->nsurl) == NULL);
384 ck_assert(hashmap_insert(test_hashmap, chain_case->nsurl) != NULL);
385 }
386
387 for (chain_case = chain_pairs;
388 chain_case->url != NULL;
389 chain_case++) {
390 ck_assert(hashmap_remove(test_hashmap, chain_case->nsurl) == true);
391 }
392
393 ck_assert_int_eq(keys, 0);
394 ck_assert_int_eq(values, 0);
395 }
396 END_TEST
397
START_TEST(chain_add_all_twice_remove_all)398 START_TEST(chain_add_all_twice_remove_all)
399 {
400 case_pair *chain_case;
401
402 for (chain_case = chain_pairs;
403 chain_case->url != NULL;
404 chain_case++) {
405 ck_assert(hashmap_lookup(test_hashmap, chain_case->nsurl) == NULL);
406 ck_assert(hashmap_insert(test_hashmap, chain_case->nsurl) != NULL);
407 }
408
409 for (chain_case = chain_pairs;
410 chain_case->url != NULL;
411 chain_case++) {
412 ck_assert(hashmap_lookup(test_hashmap, chain_case->nsurl) != NULL);
413 ck_assert(hashmap_insert(test_hashmap, chain_case->nsurl) != NULL);
414 }
415
416 for (chain_case = chain_pairs;
417 chain_case->url != NULL;
418 chain_case++) {
419 ck_assert(hashmap_remove(test_hashmap, chain_case->nsurl) == true);
420 }
421
422 ck_assert_int_eq(keys, 0);
423 ck_assert_int_eq(values, 0);
424 }
425 END_TEST
426
START_TEST(chain_add_all_twice_remove_all_iterate)427 START_TEST(chain_add_all_twice_remove_all_iterate)
428 {
429 case_pair *chain_case;
430 size_t chain_count = 0;
431
432 for (chain_case = chain_pairs;
433 chain_case->url != NULL;
434 chain_case++) {
435 ck_assert(hashmap_lookup(test_hashmap, chain_case->nsurl) == NULL);
436 ck_assert(hashmap_insert(test_hashmap, chain_case->nsurl) != NULL);
437 chain_count++;
438 }
439
440 iteration_counter = 0;
441 iteration_stop = 0;
442 ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, &iteration_ctx) == false);
443 ck_assert_int_eq(iteration_counter, chain_count);
444
445 for (chain_case = chain_pairs;
446 chain_case->url != NULL;
447 chain_case++) {
448 ck_assert(hashmap_lookup(test_hashmap, chain_case->nsurl) != NULL);
449 ck_assert(hashmap_insert(test_hashmap, chain_case->nsurl) != NULL);
450 }
451
452 iteration_counter = 0;
453 iteration_stop = 0;
454 ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, &iteration_ctx) == false);
455 ck_assert_int_eq(iteration_counter, chain_count);
456 ck_assert_int_eq(hashmap_count(test_hashmap), chain_count);
457
458 iteration_counter = 0;
459 iteration_stop = chain_count;
460 ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, &iteration_ctx) == true);
461 ck_assert_int_eq(iteration_counter, chain_count);
462
463 for (chain_case = chain_pairs;
464 chain_case->url != NULL;
465 chain_case++) {
466 ck_assert(hashmap_remove(test_hashmap, chain_case->nsurl) == true);
467 }
468
469 iteration_counter = 0;
470 iteration_stop = chain_count;
471 ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, &iteration_ctx) == false);
472 ck_assert_int_eq(iteration_counter, 0);
473
474 ck_assert_int_eq(keys, 0);
475 ck_assert_int_eq(values, 0);
476 ck_assert_int_eq(hashmap_count(test_hashmap), 0);
477 }
478 END_TEST
479
480 #define CHAIN_TEST_MALLOC_COUNT_MAX 60
481
START_TEST(chain_add_all_remove_all_alloc)482 START_TEST(chain_add_all_remove_all_alloc)
483 {
484 bool failed = false;
485 case_pair *chain_case;
486
487 malloc_limit(_i);
488
489 for (chain_case = chain_pairs;
490 chain_case->url != NULL;
491 chain_case++) {
492 if (hashmap_insert(test_hashmap, chain_case->nsurl) == NULL) {
493 failed = true;
494 }
495 }
496
497 for (chain_case = chain_pairs;
498 chain_case->url != NULL;
499 chain_case++) {
500 if (hashmap_insert(test_hashmap, chain_case->nsurl) == NULL) {
501 failed = true;
502 }
503 }
504
505 for (chain_case = chain_pairs;
506 chain_case->url != NULL;
507 chain_case++) {
508 hashmap_remove(test_hashmap, chain_case->nsurl);
509 }
510
511 malloc_limit(UINT_MAX);
512
513 ck_assert_int_eq(keys, 0);
514 ck_assert_int_eq(values, 0);
515
516 if (_i < CHAIN_TEST_MALLOC_COUNT_MAX) {
517 ck_assert(failed);
518 } else {
519 ck_assert(!failed);
520 }
521
522 }
523 END_TEST
524
chain_case_create(void)525 static TCase *chain_case_create(void)
526 {
527 TCase *tc;
528 tc = tcase_create("Bucket Chain tests");
529
530 tcase_add_unchecked_fixture(tc,
531 chain_fixture_create,
532 chain_fixture_teardown);
533
534 tcase_add_test(tc, chain_add_remove_all);
535 tcase_add_test(tc, chain_add_all_remove_all);
536 tcase_add_test(tc, chain_add_all_twice_remove_all);
537 tcase_add_test(tc, chain_add_all_twice_remove_all_iterate);
538
539 tcase_add_loop_test(tc, chain_add_all_remove_all_alloc, 0, CHAIN_TEST_MALLOC_COUNT_MAX + 1);
540
541 return tc;
542 }
543
544 /*
545 * hashmap test suite creation
546 */
hashmap_suite_create(void)547 static Suite *hashmap_suite_create(void)
548 {
549 Suite *s;
550 s = suite_create("Hashmap");
551
552 suite_add_tcase(s, basic_api_case_create());
553 suite_add_tcase(s, chain_case_create());
554
555 return s;
556 }
557
main(int argc,char ** argv)558 int main(int argc, char **argv)
559 {
560 int number_failed;
561 SRunner *sr;
562
563 sr = srunner_create(hashmap_suite_create());
564
565 srunner_run_all(sr, CK_ENV);
566
567 number_failed = srunner_ntests_failed(sr);
568 srunner_free(sr);
569
570 return (number_failed == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
571 }
572