]>
Commit | Line | Data |
---|---|---|
064af421 BP |
1 | /* A non-exhaustive test for some of the functions and macros declared in |
2 | * hmap.h. */ | |
3 | ||
4 | #include <config.h> | |
5 | #include "hmap.h" | |
6 | #include <string.h> | |
7 | #include "hash.h" | |
8 | #include "util.h" | |
9 | ||
10 | #undef NDEBUG | |
11 | #include <assert.h> | |
12 | ||
13 | /* Sample hmap element. */ | |
14 | struct element { | |
15 | int value; | |
16 | struct hmap_node node; | |
17 | }; | |
18 | ||
19 | typedef size_t hash_func(int value); | |
20 | ||
21 | static int | |
22 | compare_ints(const void *a_, const void *b_) | |
23 | { | |
24 | const int *a = a_; | |
25 | const int *b = b_; | |
26 | return *a < *b ? -1 : *a > *b; | |
27 | } | |
28 | ||
29 | /* Verifies that 'hmap' contains exactly the 'n' values in 'values'. */ | |
30 | static void | |
31 | check_hmap(struct hmap *hmap, const int values[], size_t n, | |
32 | hash_func *hash) | |
33 | { | |
34 | int *sort_values, *hmap_values; | |
35 | struct element *e; | |
36 | size_t i; | |
37 | ||
38 | /* Check that all the values are there in iteration. */ | |
39 | sort_values = xmalloc(sizeof *sort_values * n); | |
40 | hmap_values = xmalloc(sizeof *sort_values * n); | |
41 | ||
42 | i = 0; | |
43 | HMAP_FOR_EACH (e, struct element, node, hmap) { | |
44 | assert(i < n); | |
45 | hmap_values[i++] = e->value; | |
46 | } | |
47 | assert(i == n); | |
48 | ||
49 | memcpy(sort_values, values, sizeof *sort_values * n); | |
50 | qsort(sort_values, n, sizeof *sort_values, compare_ints); | |
51 | qsort(hmap_values, n, sizeof *hmap_values, compare_ints); | |
52 | ||
53 | for (i = 0; i < n; i++) { | |
54 | assert(sort_values[i] == hmap_values[i]); | |
55 | } | |
56 | ||
57 | free(hmap_values); | |
58 | free(sort_values); | |
59 | ||
60 | /* Check that all the values are there in lookup. */ | |
61 | for (i = 0; i < n; i++) { | |
62 | size_t count = 0; | |
63 | ||
64 | HMAP_FOR_EACH_WITH_HASH (e, struct element, node, | |
65 | hash(values[i]), hmap) { | |
66 | count += e->value == values[i]; | |
67 | } | |
68 | assert(count == 1); | |
69 | } | |
70 | ||
71 | /* Check counters. */ | |
72 | assert(hmap_is_empty(hmap) == !n); | |
73 | assert(hmap_count(hmap) == n); | |
74 | } | |
75 | ||
76 | /* Puts the 'n' values in 'values' into 'elements', and then puts those | |
77 | * elements into 'hmap'. */ | |
78 | static void | |
79 | make_hmap(struct hmap *hmap, struct element elements[], | |
80 | int values[], size_t n, hash_func *hash) | |
81 | { | |
82 | size_t i; | |
83 | ||
84 | hmap_init(hmap); | |
85 | for (i = 0; i < n; i++) { | |
86 | elements[i].value = i; | |
87 | hmap_insert(hmap, &elements[i].node, hash(elements[i].value)); | |
88 | values[i] = i; | |
89 | } | |
90 | } | |
91 | ||
92 | static void | |
93 | shuffle(int *p, size_t n) | |
94 | { | |
95 | for (; n > 1; n--, p++) { | |
96 | int *q = &p[rand() % n]; | |
97 | int tmp = *p; | |
98 | *p = *q; | |
99 | *q = tmp; | |
100 | } | |
101 | } | |
102 | ||
103 | #if 0 | |
104 | /* Prints the values in 'hmap', plus 'name' as a title. */ | |
105 | static void | |
106 | print_hmap(const char *name, struct hmap *hmap) | |
107 | { | |
108 | struct element *e; | |
109 | ||
110 | printf("%s:", name); | |
111 | HMAP_FOR_EACH (e, struct element, node, hmap) { | |
112 | printf(" %d(%zu)", e->value, e->node.hash & hmap->mask); | |
113 | } | |
114 | printf("\n"); | |
115 | } | |
116 | ||
117 | /* Prints the 'n' values in 'values', plus 'name' as a title. */ | |
118 | static void | |
119 | print_ints(const char *name, const int *values, size_t n) | |
120 | { | |
121 | size_t i; | |
122 | ||
123 | printf("%s:", name); | |
124 | for (i = 0; i < n; i++) { | |
125 | printf(" %d", values[i]); | |
126 | } | |
127 | printf("\n"); | |
128 | } | |
129 | #endif | |
130 | ||
131 | static size_t | |
132 | identity_hash(int value) | |
133 | { | |
134 | return value; | |
135 | } | |
136 | ||
137 | static size_t | |
138 | good_hash(int value) | |
139 | { | |
140 | return hash_int(value, 0x1234abcd); | |
141 | } | |
142 | ||
143 | static size_t | |
144 | constant_hash(int value UNUSED) | |
145 | { | |
146 | return 123; | |
147 | } | |
148 | ||
149 | /* Tests basic hmap insertion and deletion. */ | |
150 | static void | |
151 | test_hmap_insert_delete(hash_func *hash) | |
152 | { | |
153 | enum { N_ELEMS = 100 }; | |
154 | ||
155 | struct element elements[N_ELEMS]; | |
156 | int values[N_ELEMS]; | |
157 | struct hmap hmap; | |
158 | size_t i; | |
159 | ||
160 | hmap_init(&hmap); | |
161 | for (i = 0; i < N_ELEMS; i++) { | |
162 | elements[i].value = i; | |
163 | hmap_insert(&hmap, &elements[i].node, hash(i)); | |
164 | values[i] = i; | |
165 | check_hmap(&hmap, values, i + 1, hash); | |
166 | } | |
167 | shuffle(values, N_ELEMS); | |
168 | for (i = 0; i < N_ELEMS; i++) { | |
169 | hmap_remove(&hmap, &elements[values[i]].node); | |
170 | check_hmap(&hmap, values + (i + 1), N_ELEMS - (i + 1), hash); | |
171 | } | |
172 | hmap_destroy(&hmap); | |
173 | } | |
174 | ||
175 | /* Tests basic hmap_reserve() and hmap_shrink(). */ | |
176 | static void | |
177 | test_hmap_reserve_shrink(hash_func *hash) | |
178 | { | |
179 | enum { N_ELEMS = 32 }; | |
180 | ||
181 | size_t i; | |
182 | ||
183 | for (i = 0; i < N_ELEMS; i++) { | |
184 | struct element elements[N_ELEMS]; | |
185 | int values[N_ELEMS]; | |
186 | struct hmap hmap; | |
187 | size_t j; | |
188 | ||
189 | hmap_init(&hmap); | |
190 | hmap_reserve(&hmap, i); | |
191 | for (j = 0; j < N_ELEMS; j++) { | |
192 | elements[j].value = j; | |
193 | hmap_insert(&hmap, &elements[j].node, hash(j)); | |
194 | values[j] = j; | |
195 | check_hmap(&hmap, values, j + 1, hash); | |
196 | } | |
197 | shuffle(values, N_ELEMS); | |
198 | for (j = 0; j < N_ELEMS; j++) { | |
199 | hmap_remove(&hmap, &elements[values[j]].node); | |
200 | hmap_shrink(&hmap); | |
201 | check_hmap(&hmap, values + (j + 1), N_ELEMS - (j + 1), hash); | |
202 | } | |
203 | hmap_destroy(&hmap); | |
204 | } | |
205 | } | |
206 | ||
207 | /* Tests that HMAP_FOR_EACH_SAFE properly allows for deletion of the current | |
208 | * element of a hmap. */ | |
209 | static void | |
210 | test_hmap_for_each_safe(hash_func *hash) | |
211 | { | |
212 | enum { MAX_ELEMS = 10 }; | |
213 | size_t n; | |
214 | unsigned long int pattern; | |
215 | ||
216 | for (n = 0; n <= MAX_ELEMS; n++) { | |
217 | for (pattern = 0; pattern < 1ul << n; pattern++) { | |
218 | struct element elements[MAX_ELEMS]; | |
219 | int values[MAX_ELEMS]; | |
220 | struct hmap hmap; | |
221 | struct element *e, *next; | |
222 | size_t n_remaining; | |
223 | int i; | |
224 | ||
225 | make_hmap(&hmap, elements, values, n, hash); | |
226 | ||
227 | i = 0; | |
228 | n_remaining = n; | |
229 | HMAP_FOR_EACH_SAFE (e, next, struct element, node, &hmap) { | |
230 | assert(i < n); | |
231 | if (pattern & (1ul << e->value)) { | |
232 | size_t j; | |
233 | hmap_remove(&hmap, &e->node); | |
234 | for (j = 0; ; j++) { | |
235 | assert(j < n_remaining); | |
236 | if (values[j] == e->value) { | |
237 | values[j] = values[--n_remaining]; | |
238 | break; | |
239 | } | |
240 | } | |
241 | } | |
242 | check_hmap(&hmap, values, n_remaining, hash); | |
243 | i++; | |
244 | } | |
245 | assert(i == n); | |
246 | ||
247 | for (i = 0; i < n; i++) { | |
248 | if (pattern & (1ul << i)) { | |
249 | n_remaining++; | |
250 | } | |
251 | } | |
252 | assert(n == n_remaining); | |
253 | ||
254 | hmap_destroy(&hmap); | |
255 | } | |
256 | } | |
257 | } | |
258 | ||
259 | static void | |
260 | run_test(void (*function)(hash_func *)) | |
261 | { | |
262 | hash_func *hash_funcs[] = { identity_hash, good_hash, constant_hash }; | |
263 | size_t i; | |
264 | ||
265 | for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) { | |
266 | function(hash_funcs[i]); | |
267 | printf("."); | |
268 | fflush(stdout); | |
269 | } | |
270 | } | |
271 | ||
272 | int | |
273 | main(void) | |
274 | { | |
275 | run_test(test_hmap_insert_delete); | |
276 | run_test(test_hmap_for_each_safe); | |
277 | run_test(test_hmap_reserve_shrink); | |
278 | printf("\n"); | |
279 | return 0; | |
280 | } | |
281 |