1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2007, 2008, 2009, 2010, 2012, 2014 Free Software Foundation, Inc.
3
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
16
17 /* This is a test program for the stringi_map_* routines defined in
18 stringi-map.c. This test program aims to be as comprehensive as possible.
19 "gcov -a -b" should report almost complete coverage of lines, blocks and
20 branches in stringi-map.c, except that one branch caused by hash collision
21 is not exercised because our hash function has so few collisions. "valgrind
22 --leak-check=yes --show-reachable=yes" should give a clean report. */
23
24 #ifdef HAVE_CONFIG_H
25 #include <config.h>
26 #endif
27
28 #include "libpspp/stringi-map.h"
29
30 #include <assert.h>
31 #include <ctype.h>
32 #include <limits.h>
33 #include <stdbool.h>
34 #include <stddef.h>
35 #include <stdint.h>
36 #include <stdio.h>
37 #include <stdlib.h>
38 #include <string.h>
39
40 #include "libpspp/hash-functions.h"
41 #include "libpspp/compiler.h"
42 #include "libpspp/i18n.h"
43 #include "libpspp/str.h"
44 #include "libpspp/string-set.h"
45 #include "libpspp/stringi-set.h"
46
47 /* Exit with a failure code.
48 (Place a breakpoint on this function while debugging.) */
49 static void
check_die(void)50 check_die (void)
51 {
52 exit (EXIT_FAILURE);
53 }
54
55 /* If OK is not true, prints a message about failure on the
56 current source file and the given LINE and terminates. */
57 static void
check_func(bool ok,int line)58 check_func (bool ok, int line)
59 {
60 if (!ok)
61 {
62 fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
63 check_die ();
64 }
65 }
66
67 /* Verifies that EXPR evaluates to true.
68 If not, prints a message citing the calling line number and
69 terminates. */
70 #define check(EXPR) check_func ((EXPR), __LINE__)
71
72 /* Prints a message about memory exhaustion and exits with a
73 failure code. */
74 static void
xalloc_die(void)75 xalloc_die (void)
76 {
77 printf ("virtual memory exhausted\n");
78 exit (EXIT_FAILURE);
79 }
80
81 static void *xmalloc (size_t n) MALLOC_LIKE;
82 static void *xnmalloc (size_t n, size_t m) MALLOC_LIKE;
83 static void *xmemdup (const void *p, size_t n) MALLOC_LIKE;
84
85 /* Allocates and returns N bytes of memory. */
86 static void *
xmalloc(size_t n)87 xmalloc (size_t n)
88 {
89 if (n != 0)
90 {
91 void *p = malloc (n);
92 if (p == NULL)
93 xalloc_die ();
94
95 return p;
96 }
97 else
98 return NULL;
99 }
100
101 static void *
xmemdup(const void * p,size_t n)102 xmemdup (const void *p, size_t n)
103 {
104 void *q = xmalloc (n);
105 memcpy (q, p, n);
106 return q;
107 }
108
109 /* Clone STRING. */
110 static char *
xstrdup(const char * string)111 xstrdup (const char *string)
112 {
113 return xmemdup (string, strlen (string) + 1);
114 }
115
116 /* Allocates and returns N * M bytes of memory. */
117 static void *
xnmalloc(size_t n,size_t m)118 xnmalloc (size_t n, size_t m)
119 {
120 if ((size_t) -1 / m <= n)
121 xalloc_die ();
122 return xmalloc (n * m);
123 }
124
125 /* Support routines. */
126
127 enum {
128 IDX_BITS = 10,
129 MAX_IDX = 1 << IDX_BITS,
130 KEY_MASK = (MAX_IDX - 1),
131 KEY_SHIFT = 0,
132 VALUE_MASK = (MAX_IDX - 1) << IDX_BITS,
133 VALUE_SHIFT = IDX_BITS
134 };
135
136 static char *string_table[MAX_IDX];
137
138 static const char *
get_string(int idx)139 get_string (int idx)
140 {
141 char **s;
142
143 assert (idx >= 0 && idx < MAX_IDX);
144 s = &string_table[idx];
145 if (*s == NULL)
146 {
147 *s = xmalloc (16);
148 str_format_26adic (idx + 1, true, *s, 16);
149 }
150 return *s;
151 }
152
153 static void
free_strings(void)154 free_strings (void)
155 {
156 int i;
157
158 for (i = 0; i < MAX_IDX; i++)
159 free (string_table[i]);
160 }
161
162 static const char *
make_key(int value)163 make_key (int value)
164 {
165 return get_string ((value & KEY_MASK) >> KEY_SHIFT);
166 }
167
168 static const char *
make_value(int value)169 make_value (int value)
170 {
171 return get_string ((value & VALUE_MASK) >> VALUE_SHIFT);
172 }
173
174 static int
random_value(unsigned int seed,int basis)175 random_value (unsigned int seed, int basis)
176 {
177 return hash_int (seed, basis) & VALUE_MASK;
178 }
179
180 /* Swaps *A and *B. */
181 static void
swap(int * a,int * b)182 swap (int *a, int *b)
183 {
184 int t = *a;
185 *a = *b;
186 *b = t;
187 }
188
189 /* Reverses the order of the CNT integers starting at VALUES. */
190 static void
reverse(int * values,size_t cnt)191 reverse (int *values, size_t cnt)
192 {
193 size_t i = 0;
194 size_t j = cnt;
195
196 while (j > i)
197 swap (&values[i++], &values[--j]);
198 }
199
200 /* Arranges the CNT elements in VALUES into the lexicographically next greater
201 permutation. Returns true if successful. If VALUES is already the
202 lexicographically greatest permutation of its elements (i.e. ordered from
203 greatest to smallest), arranges them into the lexicographically least
204 permutation (i.e. ordered from smallest to largest) and returns false.
205
206 Comparisons among elements of VALUES consider only the bits in KEY_MASK. */
207 static bool
next_permutation(int * values,size_t cnt)208 next_permutation (int *values, size_t cnt)
209 {
210 if (cnt > 0)
211 {
212 size_t i = cnt - 1;
213 while (i != 0)
214 {
215 i--;
216 if ((values[i] & KEY_MASK) < (values[i + 1] & KEY_MASK))
217 {
218 size_t j;
219 for (j = cnt - 1;
220 (values[i] & KEY_MASK) >= (values[j] & KEY_MASK);
221 j--)
222 continue;
223 swap (values + i, values + j);
224 reverse (values + (i + 1), cnt - (i + 1));
225 return true;
226 }
227 }
228
229 reverse (values, cnt);
230 }
231
232 return false;
233 }
234
235 /* Returns N!. */
236 static unsigned int
factorial(unsigned int n)237 factorial (unsigned int n)
238 {
239 unsigned int value = 1;
240 while (n > 1)
241 value *= n--;
242 return value;
243 }
244
245 /* Randomly shuffles the CNT elements in ARRAY, each of which is
246 SIZE bytes in size. */
247 static void
random_shuffle(void * array_,size_t cnt,size_t size)248 random_shuffle (void *array_, size_t cnt, size_t size)
249 {
250 char *array = array_;
251 char *tmp = xmalloc (size);
252 size_t i;
253
254 for (i = 0; i < cnt; i++)
255 {
256 size_t j = rand () % (cnt - i) + i;
257 if (i != j)
258 {
259 memcpy (tmp, array + j * size, size);
260 memcpy (array + j * size, array + i * size, size);
261 memcpy (array + i * size, tmp, size);
262 }
263 }
264
265 free (tmp);
266 }
267
268 /* Checks that MAP has (KEY, VALUE) as a pair. */
269 static void
check_map_contains(struct stringi_map * map,const char * key,const char * value)270 check_map_contains (struct stringi_map *map,
271 const char *key, const char *value)
272 {
273 struct stringi_map_node *node;
274 const char *found_value;
275
276 check (stringi_map_contains (map, key));
277
278 node = stringi_map_find_node (map, key);
279 check (node != NULL);
280 check (!utf8_strcasecmp (key, stringi_map_node_get_key (node)));
281 check (!strcmp (value, stringi_map_node_get_value (node)));
282
283 check (node == stringi_map_insert (map, key, "012"));
284 check (!strcmp (value, stringi_map_node_get_value (node)));
285
286 check (node == stringi_map_insert_nocopy (map, xstrdup (key),
287 xstrdup ("345")));
288 check (!strcmp (value, stringi_map_node_get_value (node)));
289
290 found_value = stringi_map_find (map, key);
291 check (found_value == stringi_map_node_get_value (node));
292 check (found_value != NULL);
293 check (!strcmp (found_value, value));
294 }
295
296 /* Checks that MAP contains the CNT strings in DATA, that its structure is
297 correct, and that certain operations on MAP produce the expected results. */
298 static void
check_stringi_map(struct stringi_map * map,const int data[],size_t cnt)299 check_stringi_map (struct stringi_map *map, const int data[], size_t cnt)
300 {
301 size_t i;
302
303 check (stringi_map_is_empty (map) == (cnt == 0));
304 check (stringi_map_count (map) == cnt);
305
306 for (i = 0; i < cnt; i++)
307 {
308 const char *key = make_key (data[i]);
309 const char *value = make_value (data[i]);
310 char copy[16];
311 char *p;
312
313 check_map_contains (map, key, value);
314
315 strcpy (copy, key);
316 for (p = copy; *p != '\0'; p++)
317 {
318 assert (isupper (*p));
319 *p = tolower (*p);
320 check_map_contains (map, copy, value);
321 }
322 }
323
324 check (!stringi_map_contains (map, "xxx"));
325 check (stringi_map_find (map, "0") == NULL);
326 check (stringi_map_find_node (map, "") == NULL);
327 check (!stringi_map_delete (map, "xyz"));
328
329 if (cnt == 0)
330 check (stringi_map_first (map) == NULL);
331 else
332 {
333 const struct stringi_map_node *node;
334 int *data_copy;
335 int left;
336
337 data_copy = xmemdup (data, cnt * sizeof *data);
338 left = cnt;
339 for (node = stringi_map_first (map), i = 0; i < cnt;
340 node = stringi_map_next (map, node), i++)
341 {
342 const char *key = stringi_map_node_get_key (node);
343 const char *value = stringi_map_node_get_value (node);
344 size_t j;
345
346 for (j = 0; j < left; j++)
347 if (!strcmp (key, make_key (data_copy[j]))
348 || !strcmp (value, make_value (data_copy[j])))
349 {
350 data_copy[j] = data_copy[--left];
351 goto next;
352 }
353 check_die ();
354
355 next: ;
356 }
357 check (node == NULL);
358 free (data_copy);
359 }
360 }
361
362 /* Inserts the CNT strings from 0 to CNT - 1 (inclusive) into a map in the
363 order specified by INSERTIONS, then deletes them in the order specified by
364 DELETIONS, checking the map's contents for correctness after each
365 operation. */
366 static void
test_insert_delete(const int insertions[],const int deletions[],size_t cnt)367 test_insert_delete (const int insertions[],
368 const int deletions[],
369 size_t cnt)
370 {
371 struct stringi_map map;
372 size_t i;
373
374 stringi_map_init (&map);
375 check_stringi_map (&map, NULL, 0);
376 for (i = 0; i < cnt; i++)
377 {
378 check (stringi_map_insert (&map, make_key (insertions[i]),
379 make_value (insertions[i])));
380 check_stringi_map (&map, insertions, i + 1);
381 }
382 for (i = 0; i < cnt; i++)
383 {
384 check (stringi_map_delete (&map, make_key (deletions[i])));
385 check_stringi_map (&map, deletions + i + 1, cnt - i - 1);
386 }
387 stringi_map_destroy (&map);
388 }
389
390 /* Inserts strings into a map in each possible order, then removes them in each
391 possible order, up to a specified maximum size. */
392 static void
test_insert_any_remove_any(void)393 test_insert_any_remove_any (void)
394 {
395 const int basis = 0;
396 const int max_elems = 5;
397 int cnt;
398
399 for (cnt = 0; cnt <= max_elems; cnt++)
400 {
401 int *insertions, *deletions;
402 unsigned int ins_perm_cnt;
403 int i;
404
405 insertions = xnmalloc (cnt, sizeof *insertions);
406 deletions = xnmalloc (cnt, sizeof *deletions);
407 for (i = 0; i < cnt; i++)
408 insertions[i] = i | random_value (i, basis);
409
410 for (ins_perm_cnt = 0;
411 ins_perm_cnt == 0 || next_permutation (insertions, cnt);
412 ins_perm_cnt++)
413 {
414 unsigned int del_perm_cnt;
415 int i;
416
417 for (i = 0; i < cnt; i++)
418 deletions[i] = i | random_value (i, basis);
419
420 for (del_perm_cnt = 0;
421 del_perm_cnt == 0 || next_permutation (deletions, cnt);
422 del_perm_cnt++)
423 test_insert_delete (insertions, deletions, cnt);
424
425 check (del_perm_cnt == factorial (cnt));
426 }
427 check (ins_perm_cnt == factorial (cnt));
428
429 free (insertions);
430 free (deletions);
431 }
432 }
433
434 /* Inserts strings into a map in each possible order, then removes them in the
435 same order, up to a specified maximum size. */
436 static void
test_insert_any_remove_same(void)437 test_insert_any_remove_same (void)
438 {
439 const int max_elems = 7;
440 int cnt;
441
442 for (cnt = 0; cnt <= max_elems; cnt++)
443 {
444 int *values;
445 unsigned int permutation_cnt;
446 int i;
447
448 values = xnmalloc (cnt, sizeof *values);
449 for (i = 0; i < cnt; i++)
450 values[i] = i | random_value (i, 1);
451
452 for (permutation_cnt = 0;
453 permutation_cnt == 0 || next_permutation (values, cnt);
454 permutation_cnt++)
455 test_insert_delete (values, values, cnt);
456 check (permutation_cnt == factorial (cnt));
457
458 free (values);
459 }
460 }
461
462 /* Inserts strings into a map in each possible order, then
463 removes them in reverse order, up to a specified maximum
464 size. */
465 static void
test_insert_any_remove_reverse(void)466 test_insert_any_remove_reverse (void)
467 {
468 const int max_elems = 7;
469 int cnt;
470
471 for (cnt = 0; cnt <= max_elems; cnt++)
472 {
473 int *insertions, *deletions;
474 unsigned int permutation_cnt;
475 int i;
476
477 insertions = xnmalloc (cnt, sizeof *insertions);
478 deletions = xnmalloc (cnt, sizeof *deletions);
479 for (i = 0; i < cnt; i++)
480 insertions[i] = i | random_value (i, 2);
481
482 for (permutation_cnt = 0;
483 permutation_cnt == 0 || next_permutation (insertions, cnt);
484 permutation_cnt++)
485 {
486 memcpy (deletions, insertions, sizeof *insertions * cnt);
487 reverse (deletions, cnt);
488
489 test_insert_delete (insertions, deletions, cnt);
490 }
491 check (permutation_cnt == factorial (cnt));
492
493 free (insertions);
494 free (deletions);
495 }
496 }
497
498 /* Inserts and removes strings in a map, in random order. */
499 static void
test_random_sequence(void)500 test_random_sequence (void)
501 {
502 const int basis = 3;
503 const int max_elems = 64;
504 const int max_trials = 8;
505 int cnt;
506
507 for (cnt = 0; cnt <= max_elems; cnt += 2)
508 {
509 int *insertions, *deletions;
510 int trial;
511 int i;
512
513 insertions = xnmalloc (cnt, sizeof *insertions);
514 deletions = xnmalloc (cnt, sizeof *deletions);
515 for (i = 0; i < cnt; i++)
516 insertions[i] = i | random_value (i, basis);
517 for (i = 0; i < cnt; i++)
518 deletions[i] = i | random_value (i, basis);
519
520 for (trial = 0; trial < max_trials; trial++)
521 {
522 random_shuffle (insertions, cnt, sizeof *insertions);
523 random_shuffle (deletions, cnt, sizeof *deletions);
524
525 test_insert_delete (insertions, deletions, cnt);
526 }
527
528 free (insertions);
529 free (deletions);
530 }
531 }
532
533 /* Inserts strings into a map in ascending order, then delete in ascending
534 order. */
535 static void
test_insert_ordered(void)536 test_insert_ordered (void)
537 {
538 const int max_elems = 64;
539 int *values;
540 struct stringi_map map;
541 int i;
542
543 stringi_map_init (&map);
544 values = xnmalloc (max_elems, sizeof *values);
545 for (i = 0; i < max_elems; i++)
546 {
547 values[i] = i | random_value (i, 4);
548 stringi_map_insert_nocopy (&map, xstrdup (make_key (values[i])),
549 xstrdup (make_value (values[i])));
550 check_stringi_map (&map, values, i + 1);
551 }
552 for (i = 0; i < max_elems; i++)
553 {
554 stringi_map_delete (&map, make_key (i));
555 check_stringi_map (&map, values + i + 1, max_elems - i - 1);
556 }
557 stringi_map_destroy (&map);
558 free (values);
559 }
560
561 /* Inserts and replaces strings in a map, in random order. */
562 static void
test_replace(void)563 test_replace (void)
564 {
565 const int basis = 15;
566 enum { MAX_ELEMS = 16 };
567 const int max_trials = 8;
568 int cnt;
569
570 for (cnt = 0; cnt <= MAX_ELEMS; cnt++)
571 {
572 int insertions[MAX_ELEMS];
573 int trial;
574 int i;
575
576 for (i = 0; i < cnt; i++)
577 insertions[i] = (i / 2) | random_value (i, basis);
578
579 for (trial = 0; trial < max_trials; trial++)
580 {
581 struct stringi_map map;
582 int data[MAX_ELEMS];
583 int n_data;
584
585 /* Insert with replacement in random order. */
586 n_data = 0;
587 stringi_map_init (&map);
588 random_shuffle (insertions, cnt, sizeof *insertions);
589 for (i = 0; i < cnt; i++)
590 {
591 const char *key = make_key (insertions[i]);
592 const char *value = make_value (insertions[i]);
593 int j;
594
595 for (j = 0; j < n_data; j++)
596 if ((data[j] & KEY_MASK) == (insertions[i] & KEY_MASK))
597 {
598 data[j] = insertions[i];
599 goto found;
600 }
601 data[n_data++] = insertions[i];
602 found:
603
604 if (i % 2)
605 stringi_map_replace (&map, key, value);
606 else
607 stringi_map_replace_nocopy (&map,
608 xstrdup (key), xstrdup (value));
609 check_stringi_map (&map, data, n_data);
610 }
611
612 /* Delete in original order. */
613 for (i = 0; i < cnt; i++)
614 {
615 const char *expected_value;
616 char *value;
617 int j;
618
619 expected_value = NULL;
620 for (j = 0; j < n_data; j++)
621 if ((data[j] & KEY_MASK) == (insertions[i] & KEY_MASK))
622 {
623 expected_value = make_value (data[j]);
624 data[j] = data[--n_data];
625 break;
626 }
627
628 value = stringi_map_find_and_delete (&map,
629 make_key (insertions[i]));
630 check ((value != NULL) == (expected_value != NULL));
631 check (value == NULL || !strcmp (value, expected_value));
632 free (value);
633 }
634 assert (stringi_map_is_empty (&map));
635
636 stringi_map_destroy (&map);
637 }
638 }
639 }
640
641 static void
make_patterned_map(struct stringi_map * map,unsigned int pattern,int basis,int insertions[],int * np)642 make_patterned_map (struct stringi_map *map, unsigned int pattern, int basis,
643 int insertions[], int *np)
644 {
645 int n;
646 int i;
647
648 stringi_map_init (map);
649
650 n = 0;
651 for (i = 0; pattern != 0; i++)
652 if (pattern & (1u << i))
653 {
654 pattern &= pattern - 1;
655 insertions[n] = i | random_value (i, basis);
656 check (stringi_map_insert (map, make_key (insertions[n]),
657 make_value (insertions[n])));
658 n++;
659 }
660 check_stringi_map (map, insertions, n);
661
662 *np = n;
663 }
664
665 static void
for_each_map(void (* cb)(struct stringi_map *,int data[],int n),int basis)666 for_each_map (void (*cb)(struct stringi_map *, int data[], int n),
667 int basis)
668 {
669 enum { MAX_ELEMS = 5 };
670 unsigned int pattern;
671
672 for (pattern = 0; pattern < (1u << MAX_ELEMS); pattern++)
673 {
674 int data[MAX_ELEMS];
675 struct stringi_map map;
676 int n;
677
678 make_patterned_map (&map, pattern, basis, data, &n);
679 (*cb) (&map, data, n);
680 stringi_map_destroy (&map);
681 }
682 }
683
684 static void
for_each_pair_of_maps(void (* cb)(struct stringi_map * a,int a_data[],int n_a,struct stringi_map * b,int b_data[],int n_b),int a_basis,int b_basis)685 for_each_pair_of_maps (
686 void (*cb)(struct stringi_map *a, int a_data[], int n_a,
687 struct stringi_map *b, int b_data[], int n_b),
688 int a_basis, int b_basis)
689 {
690 enum { MAX_ELEMS = 5 };
691 unsigned int a_pattern, b_pattern;
692
693 for (a_pattern = 0; a_pattern < (1u << MAX_ELEMS); a_pattern++)
694 for (b_pattern = 0; b_pattern < (1u << MAX_ELEMS); b_pattern++)
695 {
696 int a_data[MAX_ELEMS], b_data[MAX_ELEMS];
697 struct stringi_map a_map, b_map;
698 int n_a, n_b;
699
700 make_patterned_map (&a_map, a_pattern, a_basis, a_data, &n_a);
701 make_patterned_map (&b_map, b_pattern, b_basis, b_data, &n_b);
702 (*cb) (&a_map, a_data, n_a, &b_map, b_data, n_b);
703 stringi_map_destroy (&a_map);
704 stringi_map_destroy (&b_map);
705 }
706 }
707
708 static void
clear_cb(struct stringi_map * map,int data[]UNUSED,int n UNUSED)709 clear_cb (struct stringi_map *map, int data[] UNUSED, int n UNUSED)
710 {
711 stringi_map_clear (map);
712 check_stringi_map (map, NULL, 0);
713 }
714
715 static void
test_clear(void)716 test_clear (void)
717 {
718 for_each_map (clear_cb, 5);
719 }
720
721 static void
clone_cb(struct stringi_map * map,int data[],int n)722 clone_cb (struct stringi_map *map, int data[], int n)
723 {
724 struct stringi_map clone;
725
726 stringi_map_clone (&clone, map);
727 check_stringi_map (&clone, data, n);
728 stringi_map_destroy (&clone);
729 }
730
731 static void
test_clone(void)732 test_clone (void)
733 {
734 for_each_map (clone_cb, 6);
735 }
736
737 static void
node_swap_value_cb(struct stringi_map * map,int data[],int n)738 node_swap_value_cb (struct stringi_map *map, int data[], int n)
739 {
740 int i;
741
742 for (i = 0; i < n; i++)
743 {
744 const char *value = make_value (data[i]);
745 struct stringi_map_node *node;
746 char *old_value;
747
748 node = stringi_map_find_node (map, make_key (data[i]));
749 check (node != NULL);
750 check (!strcmp (stringi_map_node_get_value (node), value));
751 data[i] = (data[i] & KEY_MASK) | random_value (i, 15);
752 old_value = stringi_map_node_swap_value (node, make_value (data[i]));
753 check (old_value != NULL);
754 check (!strcmp (value, old_value));
755 free (old_value);
756 }
757 }
758
759 static void
test_node_swap_value(void)760 test_node_swap_value (void)
761 {
762 for_each_map (node_swap_value_cb, 14);
763 }
764
765 static void
swap_cb(struct stringi_map * a,int a_data[],int n_a,struct stringi_map * b,int b_data[],int n_b)766 swap_cb (struct stringi_map *a, int a_data[], int n_a,
767 struct stringi_map *b, int b_data[], int n_b)
768 {
769 stringi_map_swap (a, b);
770 check_stringi_map (a, b_data, n_b);
771 check_stringi_map (b, a_data, n_a);
772 }
773
774 static void
test_swap(void)775 test_swap (void)
776 {
777 for_each_pair_of_maps (swap_cb, 7, 8);
778 }
779
780 static void
insert_map_cb(struct stringi_map * a,int a_data[],int n_a,struct stringi_map * b,int b_data[],int n_b)781 insert_map_cb (struct stringi_map *a, int a_data[], int n_a,
782 struct stringi_map *b, int b_data[], int n_b)
783 {
784 int i, j;
785
786 stringi_map_insert_map (a, b);
787
788 for (i = 0; i < n_b; i++)
789 {
790 for (j = 0; j < n_a; j++)
791 if ((b_data[i] & KEY_MASK) == (a_data[j] & KEY_MASK))
792 goto found;
793 a_data[n_a++] = b_data[i];
794 found:;
795 }
796 check_stringi_map (a, a_data, n_a);
797 check_stringi_map (b, b_data, n_b);
798 }
799
800 static void
test_insert_map(void)801 test_insert_map (void)
802 {
803 for_each_pair_of_maps (insert_map_cb, 91, 10);
804 }
805
806 static void
replace_map_cb(struct stringi_map * a,int a_data[],int n_a,struct stringi_map * b,int b_data[],int n_b)807 replace_map_cb (struct stringi_map *a, int a_data[], int n_a,
808 struct stringi_map *b, int b_data[], int n_b)
809 {
810 int i, j;
811
812 stringi_map_replace_map (a, b);
813
814 for (i = 0; i < n_b; i++)
815 {
816 for (j = 0; j < n_a; j++)
817 if ((b_data[i] & KEY_MASK) == (a_data[j] & KEY_MASK))
818 {
819 a_data[j] = (a_data[j] & KEY_MASK) | (b_data[i] & VALUE_MASK);
820 goto found;
821 }
822 a_data[n_a++] = b_data[i];
823 found:;
824 }
825 check_stringi_map (a, a_data, n_a);
826 check_stringi_map (b, b_data, n_b);
827 }
828
829 static void
test_replace_map(void)830 test_replace_map (void)
831 {
832 for_each_pair_of_maps (replace_map_cb, 11, 12);
833 }
834
835 static void
check_iset(struct stringi_set * set,const int * data,int n_data,int mask,int shift)836 check_iset (struct stringi_set *set, const int *data, int n_data,
837 int mask, int shift)
838 {
839 int *unique;
840 int n_unique;
841 int i;
842
843 n_unique = 0;
844 unique = xmalloc (n_data * sizeof *unique);
845 for (i = 0; i < n_data; i++)
846 {
847 int idx = (data[i] & mask) >> shift;
848 int j;
849
850 for (j = 0; j < n_unique; j++)
851 if (unique[j] == idx)
852 goto found;
853 unique[n_unique++] = idx;
854 found:;
855 }
856
857 check (stringi_set_count (set) == n_unique);
858 for (i = 0; i < n_unique; i++)
859 check (stringi_set_contains (set, get_string (unique[i])));
860 stringi_set_destroy (set);
861 free (unique);
862 }
863
864 static void
check_set(struct string_set * set,const int * data,int n_data,int mask,int shift)865 check_set (struct string_set *set, const int *data, int n_data,
866 int mask, int shift)
867 {
868 int *unique;
869 int n_unique;
870 int i;
871
872 n_unique = 0;
873 unique = xmalloc (n_data * sizeof *unique);
874 for (i = 0; i < n_data; i++)
875 {
876 int idx = (data[i] & mask) >> shift;
877 int j;
878
879 for (j = 0; j < n_unique; j++)
880 if (unique[j] == idx)
881 goto found;
882 unique[n_unique++] = idx;
883 found:;
884 }
885
886 check (string_set_count (set) == n_unique);
887 for (i = 0; i < n_unique; i++)
888 check (string_set_contains (set, get_string (unique[i])));
889 string_set_destroy (set);
890 free (unique);
891 }
892
893 static void
get_keys_and_values_cb(struct stringi_map * map,int data[],int n)894 get_keys_and_values_cb (struct stringi_map *map, int data[], int n)
895 {
896 struct stringi_set keys;
897 struct string_set values;
898
899 stringi_set_init (&keys);
900 string_set_init (&values);
901 stringi_map_get_keys (map, &keys);
902 stringi_map_get_values (map, &values);
903 check_iset (&keys, data, n, KEY_MASK, KEY_SHIFT);
904 check_set (&values, data, n, VALUE_MASK, VALUE_SHIFT);
905 }
906
907 static void
test_get_keys_and_values(void)908 test_get_keys_and_values (void)
909 {
910 for_each_map (get_keys_and_values_cb, 13);
911 }
912
913 static void
test_destroy_null(void)914 test_destroy_null (void)
915 {
916 stringi_map_destroy (NULL);
917 }
918
919 /* Main program. */
920
921 struct test
922 {
923 const char *name;
924 const char *description;
925 void (*function) (void);
926 };
927
928 static const struct test tests[] =
929 {
930 {
931 "insert-any-remove-any",
932 "insert any order, delete any order",
933 test_insert_any_remove_any
934 },
935 {
936 "insert-any-remove-same",
937 "insert any order, delete same order",
938 test_insert_any_remove_same
939 },
940 {
941 "insert-any-remove-reverse",
942 "insert any order, delete reverse order",
943 test_insert_any_remove_reverse
944 },
945 {
946 "random-sequence",
947 "insert and delete in random sequence",
948 test_random_sequence
949 },
950 {
951 "replace",
952 "insert and replace in random sequence",
953 test_replace
954 },
955 {
956 "insert-ordered",
957 "insert in ascending order",
958 test_insert_ordered
959 },
960 {
961 "clear",
962 "clear",
963 test_clear
964 },
965 {
966 "clone",
967 "clone",
968 test_clone
969 },
970 {
971 "swap",
972 "swap",
973 test_swap
974 },
975 {
976 "node-swap-value",
977 "node_swap_value",
978 test_node_swap_value
979 },
980 {
981 "insert-map",
982 "insert_map",
983 test_insert_map
984 },
985 {
986 "replace-map",
987 "replace_map",
988 test_replace_map
989 },
990 {
991 "get-keys-and-values",
992 "get keys and values",
993 test_get_keys_and_values
994 },
995 {
996 "destroy-null",
997 "destroying null table",
998 test_destroy_null
999 },
1000 };
1001
1002 enum { N_TESTS = sizeof tests / sizeof *tests };
1003
1004 int
main(int argc,char * argv[])1005 main (int argc, char *argv[])
1006 {
1007 int i;
1008
1009 if (argc != 2)
1010 {
1011 fprintf (stderr, "exactly one argument required; use --help for help\n");
1012 return EXIT_FAILURE;
1013 }
1014 else if (!strcmp (argv[1], "--help"))
1015 {
1016 printf ("%s: test case-insensitive string map library\n"
1017 "usage: %s TEST-NAME\n"
1018 "where TEST-NAME is one of the following:\n",
1019 argv[0], argv[0]);
1020 for (i = 0; i < N_TESTS; i++)
1021 printf (" %s\n %s\n", tests[i].name, tests[i].description);
1022 return 0;
1023 }
1024 else
1025 {
1026 for (i = 0; i < N_TESTS; i++)
1027 if (!strcmp (argv[1], tests[i].name))
1028 {
1029 tests[i].function ();
1030 free_strings ();
1031 return 0;
1032 }
1033
1034 fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
1035 return EXIT_FAILURE;
1036 }
1037 }
1038