This source file includes following definitions.
- entry_value
- hash_element
- compare_element
- free_element
- make_element
- test_hamt_create
- proc
- test_general
- true_processor
- element_count
- find_values_processor
- find_values
- insert_values
- replace_values
- remove_values
- test_functional_update
- test_destructive_update
- test_iterator
- main
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 #include <config.h>
20
21 #include "hamt.h"
22 #include "macros.h"
23 #include "xalloc.h"
24
25 typedef struct
26 {
27 Hamt_entry entry;
28 int val;
29 } Element;
30
31 static int
32 entry_value (const void *elt)
33 {
34 return ((Element *) elt)->val;
35 }
36
37 static size_t
38 hash_element (const void *elt)
39 {
40 return entry_value (elt) & ~3;
41
42 }
43
44 static bool
45 compare_element (const void *elt1, const void *elt2)
46 {
47 return entry_value (elt1) == entry_value (elt2);
48 }
49
50 static void
51 free_element (Hamt_entry *elt)
52 {
53 free (elt);
54 }
55
56 static Hamt_entry *
57 make_element (int n)
58 {
59 Element *elt = XMALLOC (Element);
60 elt->val = n;
61 return hamt_element (&elt->entry);
62 }
63
64 static Hamt *
65 test_hamt_create (void)
66 {
67 return hamt_create (hash_element, compare_element, free_element);
68 }
69
70
71 static int sum = 0;
72 static int flag;
73
74 static bool
75 proc (Hamt_entry *elt, void *data)
76 {
77 if (data == &flag)
78 {
79 sum += entry_value (elt);
80 return true;
81 }
82 if (sum > 0)
83 {
84 sum = 0;
85 return true;
86 }
87 return false;
88 }
89
90 static void
91 test_general (void)
92 {
93 Hamt *hamt = test_hamt_create ();
94
95 Hamt_entry *x5 = make_element (5);
96 Hamt_entry *p = x5;
97 Hamt *hamt1 = hamt_insert (hamt, &p);
98 ASSERT (hamt1 != hamt);
99 ASSERT (hamt_lookup (hamt, x5) == NULL);
100 ASSERT (hamt_lookup (hamt1, x5) == x5);
101 hamt_free (hamt);
102
103 Hamt_entry *y5 = make_element (5);
104 p = y5;
105 Hamt *hamt2 = hamt_insert (hamt1, &p);
106 ASSERT (hamt2 == hamt1);
107 ASSERT (p == x5);
108 ASSERT (hamt_lookup (hamt1, y5) == x5);
109
110 p = y5;
111 hamt = hamt_replace (hamt1, &p);
112 ASSERT (p == x5);
113 ASSERT (hamt_lookup (hamt, y5) == y5);
114 hamt_free (hamt);
115 y5 = make_element (5);
116
117 Hamt_entry *z37 = make_element (37);
118 p = z37;
119 hamt2 = hamt_insert (hamt1, &p);
120 ASSERT (hamt2 != hamt1);
121 ASSERT (p == z37);
122 ASSERT (hamt_lookup (hamt1, z37) == NULL);
123 ASSERT (hamt_lookup (hamt2, z37) == z37);
124 hamt_free (hamt1);
125
126 ASSERT (hamt_lookup (hamt2, x5) == x5);
127 ASSERT (hamt_lookup (hamt2, z37) == z37);
128
129 ASSERT (hamt_do_while (hamt2, proc, &flag) == 2);
130 ASSERT (sum == 42);
131 ASSERT (hamt_do_while (hamt2, proc, NULL) == 1);
132 ASSERT (sum == 0);
133
134 p = y5;
135 hamt1 = hamt_remove (hamt2, &p);
136 ASSERT (hamt1 != hamt2);
137 ASSERT (p == x5);
138
139 ASSERT (hamt_lookup (hamt1, x5) == NULL);
140 ASSERT (hamt_lookup (hamt2, x5) == x5);
141
142 hamt_free (hamt1);
143 Hamt_entry *x4 = make_element (4);
144 hamt1 = hamt_insert (hamt2, &x4);
145 hamt_free (hamt2);
146 Hamt_entry *x6 = make_element (6);
147 hamt2 = hamt_insert (hamt1, &x6);
148 hamt_free (hamt1);
149 ASSERT (hamt_do_while (hamt2, proc, &flag) == 4);
150 ASSERT (sum == 52);
151
152 hamt1 = hamt_remove (hamt2, &x4);
153 sum = 0;
154 ASSERT (hamt_do_while (hamt2, proc, &flag) == 4);
155 ASSERT (sum == 52);
156 sum = 0;
157 ASSERT (hamt_do_while (hamt1, proc, &flag) == 3);
158 ASSERT (sum == 48);
159
160 hamt_free (hamt1);
161 hamt_free (hamt2);
162 free_element (y5);
163 }
164
165 static bool
166 true_processor (_GL_ATTRIBUTE_MAYBE_UNUSED Hamt_entry *elt,
167 _GL_ATTRIBUTE_MAYBE_UNUSED void *data)
168 {
169 return true;
170 }
171
172 static size_t
173 element_count (Hamt *hamt)
174 {
175 return hamt_do_while (hamt, true_processor, NULL);
176 }
177
178 struct find_values_context
179 {
180 size_t n;
181 int *elts;
182 bool *found;
183 };
184
185 static bool
186 find_values_processor (Hamt_entry *entry, void *data)
187 {
188 struct find_values_context *ctx = data;
189 int val = entry_value (entry);
190 for (size_t i = 0; i < ctx->n; ++i)
191 if (ctx->elts [i] == val && !ctx->found [i])
192 {
193 ctx->found [i] = true;
194 return true;
195 }
196 return false;
197 }
198
199 static bool
200 find_values (Hamt *hamt, size_t n, int *elts)
201 {
202 bool *found = XCALLOC (n, bool);
203 struct find_values_context ctx = {n, elts, found};
204 bool res = hamt_do_while (hamt, find_values_processor, &ctx) == n;
205 free (found);
206 return res;
207 }
208
209 static size_t
210 insert_values (Hamt **hamt, size_t n, int *elts, bool destructive)
211 {
212 size_t cnt = 0;
213 for (size_t i = 0; i < n; ++i)
214 {
215 Hamt_entry *p = make_element (elts [i]);
216 Hamt_entry *q = p;
217 if (destructive)
218 {
219 if (hamt_insert_x (*hamt, &p))
220 ++cnt;
221 else
222 free_element (q);
223 }
224 else
225 {
226 Hamt *new_hamt = hamt_insert (*hamt, &p);
227 if (new_hamt != *hamt)
228 {
229 hamt_free (*hamt);
230 *hamt = new_hamt;
231 ++cnt;
232 }
233 else
234 {
235 free_element (q);
236 }
237 }
238 }
239 return cnt;
240 }
241
242 static size_t
243 replace_values (Hamt **hamt, size_t n, int *elts, bool destructive)
244 {
245 size_t cnt = 0;
246 for (size_t i = 0; i < n; ++i)
247 {
248 Hamt_entry *p = make_element (elts [i]);
249 if (destructive)
250 {
251 if (hamt_replace_x (*hamt, p))
252 ++cnt;
253 }
254 else
255 {
256 Hamt *new_hamt = hamt_replace (*hamt, &p);
257 hamt_free (*hamt);
258 *hamt = new_hamt;
259 if (p != NULL)
260 ++cnt;
261 }
262 }
263 return cnt;
264 }
265
266 static size_t
267 remove_values (Hamt **hamt, size_t n, int *elts, bool destructive)
268 {
269 size_t cnt = 0;
270 for (size_t i = 0; i < n; ++i)
271 {
272 Hamt_entry *p = make_element (elts [i]);
273 Hamt_entry *q = p;
274 if (destructive)
275 {
276 if (hamt_remove_x (*hamt, p))
277 ++cnt;
278 }
279 else
280 {
281 Hamt *new_hamt = hamt_remove (*hamt, &p);
282 if (new_hamt != *hamt)
283 {
284 hamt_free (*hamt);
285 *hamt = new_hamt;
286 ++cnt;
287 }
288 }
289 free (q);
290 }
291 return cnt;
292 }
293
294 static int val_array1 [10] = {1, 2, 3, 4, 33, 34, 35, 36, 1024, 1025};
295 static int val_array2 [10] = {1, 2, 34, 36, 1025, 32768, 32769, 32770, 32771,
296 32772};
297
298 static void
299 test_functional_update (void)
300 {
301 Hamt *hamt = test_hamt_create ();
302
303 ASSERT (insert_values (&hamt, 10, val_array1, false) == 10);
304 ASSERT (element_count (hamt) == 10);
305 ASSERT (find_values (hamt, 10, val_array1));
306 ASSERT (insert_values (&hamt, 10, val_array2, false) == 5);
307 ASSERT (element_count (hamt) == 15);
308 ASSERT (remove_values (&hamt, 10, val_array1, false) == 10);
309 ASSERT (element_count (hamt) == 5);
310 ASSERT (remove_values (&hamt, 10, val_array2, false) == 5);
311 ASSERT (element_count (hamt) == 0);
312
313 ASSERT (replace_values (&hamt, 10, val_array1, false) == 0);
314 ASSERT (element_count (hamt) == 10);
315 ASSERT (find_values (hamt, 10, val_array1));
316 ASSERT (replace_values (&hamt, 10, val_array2, false) == 5);
317 ASSERT (element_count (hamt) == 15);
318
319 hamt_free (hamt);
320 }
321
322 static void
323 test_destructive_update (void)
324 {
325 Hamt *hamt = test_hamt_create ();
326
327 ASSERT (insert_values (&hamt, 10, val_array1, true) == 10);
328 ASSERT (element_count (hamt) == 10);
329 ASSERT (find_values (hamt, 10, val_array1));
330 ASSERT (insert_values (&hamt, 10, val_array2, true) == 5);
331 ASSERT (element_count (hamt) == 15);
332 ASSERT (remove_values (&hamt, 10, val_array1, true) == 10);
333 ASSERT (element_count (hamt) == 5);
334 ASSERT (remove_values (&hamt, 10, val_array2, true) == 5);
335 ASSERT (element_count (hamt) == 0);
336
337 ASSERT (replace_values (&hamt, 10, val_array1, true) == 0);
338 ASSERT (element_count (hamt) == 10);
339 ASSERT (find_values (hamt, 10, val_array1));
340 ASSERT (replace_values (&hamt, 10, val_array2, true) == 5);
341 ASSERT (element_count (hamt) == 15);
342
343 hamt_free (hamt);
344 }
345
346 static void
347 test_iterator (void)
348 {
349 Hamt *hamt = test_hamt_create ();
350 ASSERT (insert_values (&hamt, 10, val_array1, true) == 10);
351 Hamt_iterator iter [1] = {hamt_iterator (hamt)};
352 size_t cnt = 0;
353 bool found [10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
354 Hamt_entry *p;
355 while (hamt_iterator_next (iter, &p))
356 {
357 for (size_t i = 0; i < 10; ++i)
358 if (val_array1 [i] == entry_value (p))
359 {
360 ASSERT (!found [i]);
361 found [i] = true;
362 ++cnt;
363 break;
364 }
365 }
366 ASSERT (cnt == 10);
367 hamt_iterator_free (iter);
368 hamt_free (hamt);
369 }
370
371 int
372 main (void)
373 {
374 test_general ();
375 test_functional_update ();
376 test_destructive_update ();
377 test_iterator ();
378 }