backupfile: Fix module dependencies.
[gnulib.git] / tests / test-array_map.c
blobb26592969ab45d08f17181c1e01f6ee7f9273492
1 /* Test of map data type implementation.
2 Copyright (C) 2006-2019 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2018.
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
18 #include <config.h>
20 #include "gl_array_map.h"
22 #include <stdlib.h>
23 #include <string.h>
25 #include "gl_xlist.h"
26 #include "gl_array_list.h"
27 #include "macros.h"
29 static const char *objects[30] =
31 "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o",
32 "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "<", ">", "[", "]"
35 #define SIZE_BITS (sizeof (size_t) * CHAR_BIT)
37 static bool
38 string_equals (const void *x1, const void *x2)
40 const char *s1 = x1;
41 const char *s2 = x2;
42 return strcmp (s1, s2) == 0;
45 /* A hash function for NUL-terminated char* strings using
46 the method described by Bruno Haible.
47 See https://www.haible.de/bruno/hashfunc.html. */
48 static size_t
49 string_hash (const void *x)
51 const char *s = x;
52 size_t h = 0;
54 for (; *s; s++)
55 h = *s + ((h << 9) | (h >> (SIZE_BITS - 9)));
57 return h;
60 #define RANDOM(n) (rand () % (n))
61 #define RANDOM_OBJECT() objects[RANDOM (SIZEOF (objects))]
63 struct pair
65 const void *key;
66 const void *value;
69 static int
70 cmp_pairs_in_array (const void *pairptr1, const void *pairptr2)
72 const void *key1 = ((struct pair const *)pairptr1)->key;
73 const void *key2 = ((struct pair const *)pairptr2)->key;
74 return strcmp ((const char *) key1, (const char *) key2);
77 static void
78 check_equals (gl_map_t map1, gl_list_t keys, gl_list_t values)
80 size_t n = gl_map_size (map1);
81 struct pair *pairs_of_map1 = XNMALLOC (n, struct pair);
83 gl_map_iterator_t iter1;
84 const void *key1;
85 const void *value1;
86 size_t i;
88 ASSERT (gl_list_size (keys) == n);
89 ASSERT (gl_list_size (values) == n);
90 iter1 = gl_map_iterator (map1);
91 for (i = 0; i < n; i++)
93 ASSERT (gl_map_iterator_next (&iter1, &key1, &value1));
94 pairs_of_map1[i].key = key1;
95 pairs_of_map1[i].value = value1;
97 ASSERT (!gl_map_iterator_next (&iter1, &key1, &value1));
98 gl_map_iterator_free (&iter1);
100 if (n > 0)
101 qsort (pairs_of_map1, n, sizeof (struct pair), cmp_pairs_in_array);
102 for (i = 0; i < n; i++)
104 ASSERT (pairs_of_map1[i].key == gl_list_get_at (keys, i));
105 ASSERT (pairs_of_map1[i].value == gl_list_get_at (values, i));
107 free (pairs_of_map1);
110 static void
111 check_all (gl_map_t map1, gl_list_t keys, gl_list_t values)
113 check_equals (map1, keys, values);
117 main (int argc, char *argv[])
119 gl_map_t map1;
120 gl_list_t keys;
121 gl_list_t values;
123 /* Allow the user to provide a non-default random seed on the command line. */
124 if (argc > 1)
125 srand (atoi (argv[1]));
128 size_t initial_size = RANDOM (20);
129 size_t i;
130 unsigned int repeat;
132 /* Create map1. */
133 map1 = gl_map_nx_create_empty (GL_ARRAY_MAP,
134 string_equals, string_hash, NULL, NULL);
135 ASSERT (map1 != NULL);
137 /* Create keys and values. */
138 keys = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, false);
139 values = gl_list_create_empty (GL_ARRAY_LIST, NULL, NULL, NULL, false);
141 check_all (map1, keys, values);
143 /* Initialize them. */
144 for (i = 0; i < initial_size; i++)
146 const char *key = RANDOM_OBJECT ();
147 const char *value = RANDOM_OBJECT ();
148 bool added = gl_map_nx_put (map1, key, value);
149 size_t index = gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
150 ASSERT (added == (index == (size_t)(-1)));
151 if (added)
153 gl_sortedlist_add (keys, (gl_listelement_compar_fn)strcmp, key);
154 index = gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
155 gl_list_add_at (values, index, value);
157 else
158 gl_list_set_at (values, index, value);
159 check_all (map1, keys, values);
162 for (repeat = 0; repeat < 100000; repeat++)
164 unsigned int operation = RANDOM (3);
165 switch (operation)
167 case 0:
169 const char *key = RANDOM_OBJECT ();
170 const void *ret = gl_map_get (map1, key);
171 size_t index =
172 gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
173 ASSERT (ret
174 == (index != (size_t)(-1) ? gl_list_get_at (values, index) : NULL));
176 break;
177 case 1:
179 const char *key = RANDOM_OBJECT ();
180 const char *value = RANDOM_OBJECT ();
181 bool added = gl_map_nx_put (map1, key, value);
182 size_t index =
183 gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
184 ASSERT (added == (index == (size_t)(-1)));
185 if (added)
187 gl_sortedlist_add (keys, (gl_listelement_compar_fn)strcmp, key);
188 index = gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
189 gl_list_add_at (values, index, value);
191 else
192 gl_list_set_at (values, index, value);
194 break;
195 case 2:
197 const char *key = RANDOM_OBJECT ();
198 bool removed = gl_map_remove (map1, key);
199 size_t index =
200 gl_sortedlist_indexof (keys, (gl_listelement_compar_fn)strcmp, key);
201 ASSERT (removed == (index != (size_t)(-1)));
202 if (removed)
204 gl_list_remove_at (keys, index);
205 gl_list_remove_at (values, index);
208 break;
210 check_all (map1, keys, values);
213 gl_map_free (map1);
214 gl_list_free (keys);
215 gl_list_free (values);
218 return 0;