Line data Source code
1 : /*
2 : * hashmap.c
3 : * Patater GUI Kit
4 : *
5 : * Created by Jaeden Amero on 2019-05-04.
6 : * Copyright 2019. SPDX-License-Identifier: AGPL-3.0-or-later
7 : */
8 :
9 : #include "guikit/hash.h"
10 : #include "guikit/hashmap.h"
11 : #include "ptest/test.h"
12 :
13 : /* Mock hash */
14 56 : void hash64(u32 out[], const char *buf, size_t len)
15 : {
16 56 : if (len == sizeof("magic_key") - 1 && memcmp(buf, "magic_key", len) == 0)
17 : {
18 3 : out[0] = 0xA;
19 3 : return;
20 : }
21 53 : else if (len == sizeof("dead_key") - 1
22 1 : && memcmp(buf, "dead_key", len) == 0)
23 : {
24 1 : out[0] = 0xB;
25 1 : return;
26 : }
27 52 : else if (len == sizeof("costarring") - 1
28 7 : && memcmp(buf, "costarring", len) == 0)
29 : {
30 6 : out[0] = 0xC; /* collides with liquid */
31 6 : out[1] = 0x1;
32 6 : return;
33 : }
34 46 : else if (len == sizeof("liquid") - 1 && memcmp(buf, "liquid", len) == 0)
35 : {
36 3 : out[0] = 0xC; /* collides with costarring */
37 3 : out[1] = 0x2;
38 3 : return;
39 : }
40 43 : else if (len == sizeof("declinate") - 1
41 29 : && memcmp(buf, "declinate", len) == 0)
42 : {
43 16 : out[0] = 0xD; /* collides with macallums */
44 16 : out[1] = 0x1;
45 16 : return;
46 : }
47 27 : else if (len == sizeof("macallums") - 1
48 13 : && memcmp(buf, "macallums", len) == 0)
49 : {
50 12 : out[0] = 0xD; /* collides with declinate */
51 12 : out[1] = 0x2;
52 12 : return;
53 : }
54 15 : else if (len == sizeof("nacallumz") - 1
55 1 : && memcmp(buf, "nacallumz", len) == 0)
56 : {
57 1 : out[0] = 0xE;
58 1 : return;
59 : }
60 14 : else if (len == sizeof("parcel") - 1 && memcmp(buf, "parcel", len) == 0)
61 : {
62 1 : out[0] = 0xF;
63 1 : return;
64 : }
65 13 : else if (len == sizeof("frogman") - 1 && memcmp(buf, "frogman", len) == 0)
66 : {
67 2 : out[0] = 0x1;
68 2 : return;
69 : }
70 11 : else if (len == sizeof("badegg") - 1 && memcmp(buf, "badegg", len) == 0)
71 : {
72 1 : out[0] = 0x2;
73 1 : return;
74 : }
75 10 : else if (len == sizeof("triple_collision_1") - 1
76 7 : && memcmp(buf, "triple_collision_1", len) == 0)
77 : {
78 2 : out[0] = 0x3;
79 2 : out[1] = 0x1;
80 2 : return;
81 : }
82 8 : else if (len == sizeof("triple_collision_2") - 1
83 5 : && memcmp(buf, "triple_collision_2", len) == 0)
84 : {
85 3 : out[0] = 0x3;
86 3 : out[1] = 0x2;
87 3 : return;
88 : }
89 5 : else if (len == sizeof("triple_collision_3") - 1
90 2 : && memcmp(buf, "triple_collision_3", len) == 0)
91 : {
92 2 : out[0] = 0x3;
93 2 : out[1] = 0x3;
94 2 : return;
95 : }
96 :
97 3 : out[0] = 0xFFFFFFFFUL;
98 3 : out[1] = 0xFFFFFFFFUL;
99 : }
100 :
101 1 : static int hashmap_test_get_nonexistent(void)
102 : {
103 : struct hashmap *hashmap;
104 1 : u32 key[2];
105 : ptrdiff_t value;
106 :
107 : /* Get non-existent from empty */
108 1 : hashmap = hashmap_alloc();
109 1 : hash64(key, "magic_key", sizeof("magic_key") - 1);
110 1 : value = hashmap_get(hashmap, key);
111 1 : TEST_EQ(value, 0);
112 1 : hashmap_free(hashmap);
113 :
114 : /* Get non-existent from non-collision bucket */
115 1 : hashmap = hashmap_alloc();
116 1 : hash64(key, "dead_key", sizeof("dead_key") - 1);
117 1 : hashmap_put(hashmap, key, 0xdeadbeefUL);
118 1 : hash64(key, "magic_key", sizeof("magic_key") - 1);
119 1 : value = hashmap_get(hashmap, key);
120 1 : TEST_EQ(value, 0);
121 1 : hashmap_free(hashmap);
122 :
123 : /* Get non-existent key from a bucket with a collision in it, where our
124 : * non-existent key has a different key length. */
125 : /* "costarring" collides with "liquid", which are each of different length.
126 : * https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed/145633#145633
127 : */
128 1 : hashmap = hashmap_alloc();
129 1 : hash64(key, "costarring", sizeof("costarring") - 1);
130 1 : hashmap_put(hashmap, key, 0x02UL);
131 1 : hash64(key, "liquid", sizeof("liquid") - 1);
132 1 : hashmap_put(hashmap, key, 0x03UL);
133 1 : hash64(key, "magic_key", sizeof("magic_key") - 1);
134 1 : value = hashmap_get(hashmap, key);
135 1 : TEST_EQ(value, 0);
136 1 : hashmap_free(hashmap);
137 :
138 : /* Get non-existent key from a bucket with a collision in it, where our key
139 : * has the same length as one of the colliding keys, but is a different key
140 : * key. */
141 : /* "declinate" collides with "macallums", which are both the same length.
142 : * https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed/145633#145633
143 : */
144 1 : hashmap = hashmap_alloc();
145 1 : hash64(key, "declinate", sizeof("declinate") - 1);
146 1 : hashmap_put(hashmap, key, 0x02UL);
147 1 : hash64(key, "macallums", sizeof("macallums") - 1);
148 1 : hashmap_put(hashmap, key, 0x03UL);
149 1 : hash64(key, "nacallumz", sizeof("nacallumz") - 1);
150 1 : value = hashmap_get(hashmap, key);
151 1 : TEST_EQ(value, 0);
152 1 : hashmap_free(hashmap);
153 :
154 : /* Get non-existent key from a bucket with a colliding key, where our key
155 : * collides, but has a different length. */
156 1 : hashmap = hashmap_alloc();
157 1 : hash64(key, "costarring", sizeof("costarring") - 1);
158 1 : hashmap_put(hashmap, key, 0x02UL);
159 1 : hash64(key, "liquid", sizeof("liquid") - 1);
160 1 : value = hashmap_get(hashmap, key);
161 1 : TEST_EQ(value, 0);
162 1 : hashmap_free(hashmap);
163 :
164 : /* Get non-existent key from a bucket with a colliding key, where our key
165 : * collides, and has the same length, but is a different key. */
166 1 : hashmap = hashmap_alloc();
167 1 : hash64(key, "declinate", sizeof("declinate") - 1);
168 1 : hashmap_put(hashmap, key, 0x02UL);
169 1 : hash64(key, "macallums", sizeof("macallums") - 1);
170 1 : value = hashmap_get(hashmap, key);
171 1 : TEST_EQ(value, 0);
172 1 : hashmap_free(hashmap);
173 :
174 1 : return 0;
175 : }
176 :
177 1 : static int hashmap_test_get_existent(void)
178 : {
179 : struct hashmap *hashmap;
180 1 : u32 key[2];
181 : ptrdiff_t value;
182 :
183 : /* Get from non-collision bucket */
184 1 : hashmap = hashmap_alloc();
185 1 : hash64(key, "parcel", sizeof("parcel") - 1);
186 1 : hashmap_put(hashmap, key, 0x04UL);
187 1 : value = hashmap_get(hashmap, key);
188 1 : TEST_EQ(value, 0x00000004UL);
189 1 : hashmap_free(hashmap);
190 :
191 : /* Get from collision bucket first */
192 1 : hashmap = hashmap_alloc();
193 1 : hash64(key, "macallums", sizeof("macallums") - 1);
194 1 : hashmap_put(hashmap, key, 0x05UL);
195 1 : hash64(key, "declinate", sizeof("declinate") - 1);
196 1 : hashmap_put(hashmap, key, 0x06UL);
197 1 : hash64(key, "macallums", sizeof("macallums") - 1);
198 1 : value = hashmap_get(hashmap, key);
199 1 : TEST_EQ(value, 0x00000005UL);
200 1 : hashmap_free(hashmap);
201 :
202 : /* Get from collision bucket last */
203 1 : hashmap = hashmap_alloc();
204 1 : hash64(key, "declinate", sizeof("declinate") - 1);
205 1 : hashmap_put(hashmap, key, 0x07UL);
206 1 : hash64(key, "macallums", sizeof("macallums") - 1);
207 1 : hashmap_put(hashmap, key, 0x08UL);
208 1 : value = hashmap_get(hashmap, key);
209 1 : TEST_EQ(value, 0x00000008UL);
210 1 : hashmap_free(hashmap);
211 :
212 1 : return 0;
213 : }
214 :
215 1 : static int hashmap_test_put(void)
216 : {
217 : struct hashmap *hashmap;
218 1 : u32 key[2];
219 : ptrdiff_t set_value;
220 : ptrdiff_t set_value1;
221 : ptrdiff_t set_value2;
222 : ptrdiff_t set_value3;
223 : ptrdiff_t got_value;
224 : ptrdiff_t got_value1;
225 : ptrdiff_t got_value2;
226 : ptrdiff_t got_value3;
227 :
228 : /* Put when non-existent. */
229 1 : hashmap = hashmap_alloc();
230 1 : TEST_EQU(hashmap_length(hashmap), 0);
231 1 : TEST_EQU(hashmap_num_collisions(hashmap), 0);
232 1 : set_value = 0x00000008UL;
233 1 : hash64(key, "frogman", sizeof("frogman") - 1);
234 1 : hashmap_put(hashmap, key, set_value);
235 1 : got_value = hashmap_get(hashmap, key);
236 1 : TEST_EQU(hashmap_length(hashmap), 1);
237 1 : TEST_EQU(hashmap_num_collisions(hashmap), 0);
238 1 : TEST_EQU(got_value, set_value);
239 1 : hashmap_free(hashmap);
240 :
241 : /* Put when non-existent in collision bucket, diff key len. */
242 1 : hashmap = hashmap_alloc();
243 1 : set_value = 0x00000009UL;
244 1 : set_value2 = 0xbabebeefUL;
245 1 : hash64(key, "costarring", sizeof("costarring") - 1);
246 1 : hashmap_put(hashmap, key, set_value2);
247 1 : hash64(key, "liquid", sizeof("liquid") - 1);
248 1 : hashmap_put(hashmap, key, set_value);
249 1 : TEST_EQU(hashmap_length(hashmap), 2);
250 1 : TEST_EQU(hashmap_num_collisions(hashmap), 1);
251 1 : got_value = hashmap_get(hashmap, key);
252 1 : hash64(key, "costarring", sizeof("costarring") - 1);
253 1 : got_value2 = hashmap_get(hashmap, key);
254 1 : TEST_EQU(got_value2, set_value2);
255 1 : TEST_EQU(got_value, set_value);
256 1 : hashmap_free(hashmap);
257 :
258 : /* Put when non-existent in collision bucket, diff key. */
259 1 : hashmap = hashmap_alloc();
260 1 : set_value = 0x0000000aUL;
261 1 : set_value2 = 0x50f7beefUL;
262 1 : hash64(key, "declinate", sizeof("declinate") - 1);
263 1 : hashmap_put(hashmap, key, set_value2);
264 1 : hash64(key, "macallums", sizeof("macallums") - 1);
265 1 : hashmap_put(hashmap, key, set_value);
266 1 : TEST_EQU(hashmap_length(hashmap), 2);
267 1 : TEST_EQU(hashmap_num_collisions(hashmap), 1);
268 1 : got_value = hashmap_get(hashmap, key);
269 1 : hash64(key, "declinate", sizeof("declinate") - 1);
270 1 : got_value2 = hashmap_get(hashmap, key);
271 1 : TEST_EQU(got_value2, set_value2);
272 1 : TEST_EQU(got_value, set_value);
273 1 : hashmap_free(hashmap);
274 :
275 : /* Put when existent in non-collision bucket. */
276 1 : hashmap = hashmap_alloc();
277 1 : set_value = 0x0000000bUL;
278 1 : hash64(key, "frogman", sizeof("frogman") - 1);
279 1 : hashmap_put(hashmap, key, 0xf00dfaceUL);
280 1 : hashmap_put(hashmap, key, set_value);
281 1 : TEST_EQU(hashmap_length(hashmap), 1);
282 1 : TEST_EQU(hashmap_num_collisions(hashmap), 0);
283 1 : got_value = hashmap_get(hashmap, key);
284 1 : TEST_EQU(got_value, set_value);
285 1 : hashmap_free(hashmap);
286 :
287 : /* Put when existent in collision bucket at front. */
288 1 : hashmap = hashmap_alloc();
289 1 : set_value = 0x0000000cUL;
290 1 : set_value2 = 0xc001d00dUL;
291 1 : hash64(key, "macallums", sizeof("macallums") - 1);
292 1 : hashmap_put(hashmap, key, 0xf00dfaceUL);
293 1 : hash64(key, "declinate", sizeof("declinate") - 1);
294 1 : hashmap_put(hashmap, key, set_value2);
295 1 : hash64(key, "macallums", sizeof("macallums") - 1);
296 1 : hashmap_put(hashmap, key, set_value);
297 1 : TEST_EQU(hashmap_length(hashmap), 2);
298 1 : TEST_EQU(hashmap_num_collisions(hashmap), 1);
299 1 : got_value = hashmap_get(hashmap, key);
300 1 : hash64(key, "declinate", sizeof("declinate") - 1);
301 1 : got_value2 = hashmap_get(hashmap, key);
302 1 : TEST_EQU(got_value, set_value);
303 1 : TEST_EQU(got_value2, set_value2);
304 1 : hashmap_free(hashmap);
305 :
306 : /* Put when existent in collision bucket at back. */
307 1 : hashmap = hashmap_alloc();
308 1 : set_value = 0x0000000dUL;
309 1 : set_value2 = 0xc001d00dUL;
310 1 : hash64(key, "declinate", sizeof("declinate") - 1);
311 1 : hashmap_put(hashmap, key, set_value2);
312 1 : hash64(key, "macallums", sizeof("macallums") - 1);
313 1 : hashmap_put(hashmap, key, 0xf00dfaceUL);
314 1 : hashmap_put(hashmap, key, set_value);
315 1 : TEST_EQU(hashmap_length(hashmap), 2);
316 1 : TEST_EQU(hashmap_num_collisions(hashmap), 1);
317 1 : got_value = hashmap_get(hashmap, key);
318 1 : hash64(key, "declinate", sizeof("declinate") - 1);
319 1 : got_value2 = hashmap_get(hashmap, key);
320 1 : TEST_EQU(got_value, set_value);
321 1 : TEST_EQU(got_value2, set_value2);
322 1 : hashmap_free(hashmap);
323 :
324 : /* Put when existent in collision bucket in middle. */
325 1 : hashmap = hashmap_alloc();
326 1 : set_value = 0x0000000dUL;
327 1 : set_value1 = 0xf00dfaceUL;
328 1 : set_value2 = 0xc001d00dUL;
329 1 : set_value3 = 0x5a5aa5a5UL;
330 1 : hash64(key, "triple_collision_1", sizeof("triple_collision_1") - 1);
331 1 : hashmap_put(hashmap, key, set_value1);
332 1 : hash64(key, "triple_collision_2", sizeof("triple_collision_2") - 1);
333 1 : hashmap_put(hashmap, key, set_value2);
334 1 : hash64(key, "triple_collision_3", sizeof("triple_collision_3") - 1);
335 1 : hashmap_put(hashmap, key, set_value3);
336 1 : TEST_EQU(hashmap_length(hashmap), 3);
337 1 : TEST_EQU(hashmap_num_collisions(hashmap), 2);
338 1 : hash64(key, "triple_collision_2", sizeof("triple_collision_2") - 1);
339 1 : hashmap_put(hashmap, key, set_value);
340 1 : hash64(key, "triple_collision_1", sizeof("triple_collision_1") - 1);
341 1 : got_value1 = hashmap_get(hashmap, key);
342 1 : hash64(key, "triple_collision_2", sizeof("triple_collision_2") - 1);
343 1 : got_value = hashmap_get(hashmap, key);
344 1 : hash64(key, "triple_collision_3", sizeof("triple_collision_3") - 1);
345 1 : got_value3 = hashmap_get(hashmap, key);
346 1 : TEST_EQU(got_value1, set_value1);
347 1 : TEST_EQU(got_value, set_value);
348 1 : TEST_EQU(got_value3, set_value3);
349 1 : hashmap_free(hashmap);
350 :
351 1 : return 0;
352 : }
353 :
354 1 : static int hashmap_test_del(void)
355 : {
356 : struct hashmap *hashmap;
357 1 : u32 key[2];
358 : ptrdiff_t set_value;
359 : ptrdiff_t set_value2;
360 : ptrdiff_t got_value;
361 : ptrdiff_t got_value2;
362 :
363 : /* Remove when non-existent. */
364 1 : hashmap = hashmap_alloc();
365 1 : TEST_EQU(hashmap_length(hashmap), 0);
366 1 : TEST_EQU(hashmap_num_collisions(hashmap), 0);
367 1 : hash64(key, "badegg", sizeof("badegg") );
368 1 : hashmap_del(hashmap, key);
369 1 : TEST_EQU(hashmap_length(hashmap), 0);
370 1 : hashmap_free(hashmap);
371 :
372 : /* Remove when non-existent in collision bucket, diff key len. */
373 : /* There is only one entry in the bucket, but it's not the key we want to
374 : * remove. It collides with the key we want to remove, but because it's not
375 : * the same we test that it isn't removed. */
376 1 : hashmap = hashmap_alloc();
377 1 : set_value = 0xbabebeefUL;
378 1 : hash64(key, "costarring", sizeof("costarring") - 1);
379 1 : hashmap_put(hashmap, key, set_value);
380 1 : hash64(key, "liquid", sizeof("liquid") );
381 1 : hashmap_del(hashmap, key);
382 1 : TEST_EQU(hashmap_length(hashmap), 1);
383 1 : hash64(key, "costarring", sizeof("costarring") - 1);
384 1 : got_value = hashmap_get(hashmap, key);
385 1 : TEST_EQU(got_value, set_value);
386 1 : hashmap_free(hashmap);
387 :
388 : /* Remove when non-existent in collision bucket, diff key. */
389 1 : hashmap = hashmap_alloc();
390 1 : set_value = 0x50f7beefUL;
391 1 : hash64(key, "declinate", sizeof("declinate") - 1);
392 1 : hashmap_put(hashmap, key, set_value);
393 1 : hash64(key, "macallums", sizeof("macallums") );
394 1 : hashmap_del(hashmap, key);
395 1 : TEST_EQU(hashmap_length(hashmap), 1);
396 1 : hash64(key, "declinate", sizeof("declinate") - 1);
397 1 : got_value = hashmap_get(hashmap, key);
398 1 : TEST_EQU(got_value, set_value);
399 1 : hashmap_free(hashmap);
400 :
401 : /* Remove when existent in non-collision bucket. */
402 1 : hashmap = hashmap_alloc();
403 1 : set_value = 0xf00dfaceUL;
404 1 : hash64(key, "badegg", sizeof("badegg") - 1);
405 1 : hashmap_put(hashmap, key, set_value);
406 1 : hashmap_del(hashmap, key);
407 1 : TEST_EQU(hashmap_length(hashmap), 0);
408 1 : hashmap_free(hashmap);
409 :
410 : /* Remove when existent in collision bucket at front. */
411 1 : hashmap = hashmap_alloc();
412 1 : set_value = 0xf00dfaceUL;
413 1 : set_value2 = 0xc001d00dUL;
414 1 : hash64(key, "macallums", sizeof("macallums") - 1);
415 1 : hashmap_put(hashmap, key, set_value);
416 1 : hash64(key, "declinate", sizeof("declinate") - 1);
417 1 : hashmap_put(hashmap, key, set_value2);
418 1 : hash64(key, "macallums", sizeof("macallums") - 1);
419 1 : hashmap_del(hashmap, key);
420 1 : TEST_EQU(hashmap_length(hashmap), 1);
421 1 : TEST_EQU(hashmap_num_collisions(hashmap), 1);
422 1 : hash64(key, "declinate", sizeof("declinate") - 1);
423 1 : got_value2 = hashmap_get(hashmap, key);
424 1 : TEST_EQU(got_value2, set_value2);
425 1 : hashmap_free(hashmap);
426 :
427 : /* Remove when existent in collision bucket at back. */
428 1 : hashmap = hashmap_alloc();
429 1 : set_value = 0xf00dfaceUL;
430 1 : set_value2 = 0xc001d00dUL;
431 1 : hash64(key, "declinate", sizeof("declinate") - 1);
432 1 : hashmap_put(hashmap, key, set_value2);
433 1 : hash64(key, "macallums", sizeof("macallums") - 1);
434 1 : hashmap_put(hashmap, key, set_value);
435 1 : hashmap_del(hashmap, key);
436 1 : TEST_EQU(hashmap_length(hashmap), 1);
437 1 : TEST_EQU(hashmap_num_collisions(hashmap), 1);
438 1 : hash64(key, "declinate", sizeof("declinate") - 1);
439 1 : got_value2 = hashmap_get(hashmap, key);
440 1 : TEST_EQU(got_value2, set_value2);
441 1 : hashmap_free(hashmap);
442 :
443 1 : return 0;
444 : }
445 :
446 1 : static int hashmap_test_grows_when_more_added(void)
447 : {
448 : struct hashmap *hashmap;
449 1 : u32 key[2];
450 : ptrdiff_t value;
451 :
452 :
453 : /* Add 4 items and we expect the map to grow to be able to hold 16 items,
454 : * given it starts as being able to hold 8. */
455 1 : hashmap = hashmap_alloc();
456 1 : TEST_EQU(hashmap_capacity(hashmap), 8);
457 :
458 1 : key[0] = 0x0;
459 1 : key[1] = 0xA;
460 1 : value = 0;
461 1 : hashmap_put(hashmap, key, value);
462 1 : TEST_EQU(hashmap_length(hashmap), 1);
463 1 : TEST_EQU(hashmap_capacity(hashmap), 8);
464 :
465 1 : key[0] = 0x1;
466 1 : key[1] = 0xA;
467 1 : value = 1;
468 1 : hashmap_put(hashmap, key, value);
469 1 : TEST_EQU(hashmap_length(hashmap), 2);
470 1 : TEST_EQU(hashmap_capacity(hashmap), 8);
471 :
472 1 : key[0] = 0x2;
473 1 : key[1] = 0xA;
474 1 : value = 2;
475 1 : hashmap_put(hashmap, key, value);
476 1 : TEST_EQU(hashmap_length(hashmap), 3);
477 1 : TEST_EQU(hashmap_capacity(hashmap), 8);
478 :
479 1 : key[0] = 0x3;
480 1 : key[1] = 0xA;
481 1 : value = 3;
482 1 : hashmap_put(hashmap, key, value);
483 1 : TEST_EQU(hashmap_length(hashmap), 4);
484 1 : TEST_EQU(hashmap_capacity(hashmap), 8);
485 :
486 1 : key[0] = 0x4;
487 1 : key[1] = 0xA;
488 1 : value = 4;
489 1 : hashmap_put(hashmap, key, value);
490 1 : TEST_EQU(hashmap_length(hashmap), 5);
491 1 : TEST_EQU(hashmap_capacity(hashmap), 16);
492 1 : hashmap_free(hashmap);
493 :
494 1 : return 0;
495 : }
496 :
497 1 : static int hashmap_test_grows_and_is_accessible(void)
498 : {
499 : struct hashmap *hashmap;
500 1 : u32 key[2];
501 : ptrdiff_t value;
502 :
503 :
504 : /* Add 9 items, one more than the original capacity, and verify we can read
505 : * each value back out. */
506 1 : hashmap = hashmap_alloc();
507 1 : TEST_EQU(hashmap_capacity(hashmap), 8);
508 :
509 1 : key[0] = 0x0;
510 1 : key[1] = 0xA;
511 1 : value = 0;
512 1 : hashmap_put(hashmap, key, value);
513 :
514 1 : key[0] = 0x1;
515 1 : key[1] = 0xA;
516 1 : value = 1;
517 1 : hashmap_put(hashmap, key, value);
518 :
519 1 : key[0] = 0x2;
520 1 : key[1] = 0xA;
521 1 : value = 2;
522 1 : hashmap_put(hashmap, key, value);
523 :
524 1 : key[0] = 0x3;
525 1 : key[1] = 0xA;
526 1 : value = 3;
527 1 : hashmap_put(hashmap, key, value);
528 :
529 1 : key[0] = 0x4;
530 1 : key[1] = 0xA;
531 1 : value = 4;
532 1 : hashmap_put(hashmap, key, value);
533 :
534 1 : key[0] = 0x5;
535 1 : key[1] = 0xA;
536 1 : value = 5;
537 1 : hashmap_put(hashmap, key, value);
538 :
539 1 : key[0] = 0x6;
540 1 : key[1] = 0xA;
541 1 : value = 6;
542 1 : hashmap_put(hashmap, key, value);
543 :
544 1 : key[0] = 0x7;
545 1 : key[1] = 0xA;
546 1 : value = 7;
547 1 : hashmap_put(hashmap, key, value);
548 :
549 : /* Ensure there is enough room for the 9th entry. */
550 1 : TEST_GE(hashmap_capacity(hashmap), 9);
551 :
552 : /* Add the 9th entry. */
553 1 : key[0] = 0x8;
554 1 : key[1] = 0xA;
555 1 : value = 8;
556 1 : hashmap_put(hashmap, key, value);
557 1 : TEST_EQ(hashmap_length(hashmap), 9);
558 :
559 : /* Ensure all keys we added are present. */
560 1 : key[0] = 0x0;
561 1 : key[1] = 0xA;
562 1 : value = hashmap_get(hashmap, key);
563 1 : TEST_EQ(value, 0);
564 :
565 1 : key[0] = 0x1;
566 1 : key[1] = 0xA;
567 1 : value = hashmap_get(hashmap, key);
568 1 : TEST_EQ(value, 1);
569 :
570 1 : key[0] = 0x2;
571 1 : key[1] = 0xA;
572 1 : value = hashmap_get(hashmap, key);
573 1 : TEST_EQ(value, 2);
574 :
575 1 : key[0] = 0x3;
576 1 : key[1] = 0xA;
577 1 : value = hashmap_get(hashmap, key);
578 1 : TEST_EQ(value, 3);
579 :
580 1 : key[0] = 0x4;
581 1 : key[1] = 0xA;
582 1 : value = hashmap_get(hashmap, key);
583 1 : TEST_EQ(value, 4);
584 :
585 1 : key[0] = 0x5;
586 1 : key[1] = 0xA;
587 1 : value = hashmap_get(hashmap, key);
588 1 : TEST_EQ(value, 5);
589 :
590 1 : key[0] = 0x6;
591 1 : key[1] = 0xA;
592 1 : value = hashmap_get(hashmap, key);
593 1 : TEST_EQ(value, 6);
594 :
595 1 : key[0] = 0x7;
596 1 : key[1] = 0xA;
597 1 : value = hashmap_get(hashmap, key);
598 1 : TEST_EQ(value, 7);
599 :
600 1 : key[0] = 0x8;
601 1 : key[1] = 0xA;
602 1 : value = hashmap_get(hashmap, key);
603 1 : TEST_EQ(value, 8);
604 :
605 1 : hashmap_free(hashmap);
606 :
607 1 : return 0;
608 : }
609 :
610 : const test_fn tests[] =
611 : {
612 : hashmap_test_get_nonexistent,
613 : hashmap_test_get_existent,
614 : hashmap_test_put,
615 : hashmap_test_del,
616 : hashmap_test_grows_when_more_added,
617 : hashmap_test_grows_and_is_accessible,
618 : 0
619 : };
|
