diff options
Diffstat (limited to 'src/util/container_multihashmap.c')
-rw-r--r-- | src/util/container_multihashmap.c | 1098 |
1 files changed, 0 insertions, 1098 deletions
diff --git a/src/util/container_multihashmap.c b/src/util/container_multihashmap.c deleted file mode 100644 index 08893d81f..000000000 --- a/src/util/container_multihashmap.c +++ /dev/null | |||
@@ -1,1098 +0,0 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | Copyright (C) 2008, 2012 GNUnet e.V. | ||
4 | |||
5 | GNUnet is free software: you can redistribute it and/or modify it | ||
6 | under the terms of the GNU Affero General Public License as published | ||
7 | by the Free Software Foundation, either version 3 of the License, | ||
8 | or (at your option) any later version. | ||
9 | |||
10 | GNUnet is distributed in the hope that it will be useful, but | ||
11 | WITHOUT ANY WARRANTY; without even the implied warranty of | ||
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
13 | Affero General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU Affero General Public License | ||
16 | along with this program. If not, see <http://www.gnu.org/licenses/>. | ||
17 | |||
18 | SPDX-License-Identifier: AGPL3.0-or-later | ||
19 | */ | ||
20 | /** | ||
21 | * @file util/container_multihashmap.c | ||
22 | * @brief hash map where the same key may be present multiple times | ||
23 | * @author Christian Grothoff | ||
24 | */ | ||
25 | |||
26 | #include "platform.h" | ||
27 | #include "gnunet_container_lib.h" | ||
28 | |||
29 | #define LOG(kind, ...) \ | ||
30 | GNUNET_log_from (kind, "util-container-multihashmap", __VA_ARGS__) | ||
31 | |||
32 | /** | ||
33 | * Maximum recursion depth for callbacks of | ||
34 | * #GNUNET_CONTAINER_multihashmap_get_multiple() themselves s | ||
35 | * again calling #GNUNET_CONTAINER_multihashmap_get_multiple(). | ||
36 | * Should be totally excessive, but if violated we die. | ||
37 | */ | ||
38 | #define NEXT_CACHE_SIZE 16 | ||
39 | |||
40 | |||
41 | /** | ||
42 | * An entry in the hash map with the full key. | ||
43 | */ | ||
44 | struct BigMapEntry | ||
45 | { | ||
46 | /** | ||
47 | * Value of the entry. | ||
48 | */ | ||
49 | void *value; | ||
50 | |||
51 | /** | ||
52 | * If there is a hash collision, we create a linked list. | ||
53 | */ | ||
54 | struct BigMapEntry *next; | ||
55 | |||
56 | /** | ||
57 | * Key for the entry. | ||
58 | */ | ||
59 | struct GNUNET_HashCode key; | ||
60 | }; | ||
61 | |||
62 | |||
63 | /** | ||
64 | * An entry in the hash map with just a pointer to the key. | ||
65 | */ | ||
66 | struct SmallMapEntry | ||
67 | { | ||
68 | /** | ||
69 | * Value of the entry. | ||
70 | */ | ||
71 | void *value; | ||
72 | |||
73 | /** | ||
74 | * If there is a hash collision, we create a linked list. | ||
75 | */ | ||
76 | struct SmallMapEntry *next; | ||
77 | |||
78 | /** | ||
79 | * Key for the entry. | ||
80 | */ | ||
81 | const struct GNUNET_HashCode *key; | ||
82 | }; | ||
83 | |||
84 | |||
85 | /** | ||
86 | * Entry in the map. | ||
87 | */ | ||
88 | union MapEntry | ||
89 | { | ||
90 | /** | ||
91 | * Variant used if map entries only contain a pointer to the key. | ||
92 | */ | ||
93 | struct SmallMapEntry *sme; | ||
94 | |||
95 | /** | ||
96 | * Variant used if map entries contain the full key. | ||
97 | */ | ||
98 | struct BigMapEntry *bme; | ||
99 | }; | ||
100 | |||
101 | |||
102 | /** | ||
103 | * Internal representation of the hash map. | ||
104 | */ | ||
105 | struct GNUNET_CONTAINER_MultiHashMap | ||
106 | { | ||
107 | /** | ||
108 | * All of our buckets. | ||
109 | */ | ||
110 | union MapEntry *map; | ||
111 | |||
112 | /** | ||
113 | * Number of entries in the map. | ||
114 | */ | ||
115 | unsigned int size; | ||
116 | |||
117 | /** | ||
118 | * Length of the "map" array. | ||
119 | */ | ||
120 | unsigned int map_length; | ||
121 | |||
122 | /** | ||
123 | * #GNUNET_NO if the map entries are of type 'struct BigMapEntry', | ||
124 | * #GNUNET_YES if the map entries are of type 'struct SmallMapEntry'. | ||
125 | */ | ||
126 | int use_small_entries; | ||
127 | |||
128 | /** | ||
129 | * Counts the destructive modifications (grow, remove) | ||
130 | * to the map, so that iterators can check if they are still valid. | ||
131 | */ | ||
132 | unsigned int modification_counter; | ||
133 | |||
134 | /** | ||
135 | * Map entries indicating iteration positions currently | ||
136 | * in use by #GNUNET_CONTAINER_multihashmap_get_multiple(). | ||
137 | * Only used up to @e next_cache_off. | ||
138 | */ | ||
139 | union MapEntry next_cache[NEXT_CACHE_SIZE]; | ||
140 | |||
141 | /** | ||
142 | * Offset of @e next_cache entries in use, must be smaller | ||
143 | * than #NEXT_CACHE_SIZE. | ||
144 | */ | ||
145 | unsigned int next_cache_off; | ||
146 | }; | ||
147 | |||
148 | |||
149 | /** | ||
150 | * Cursor into a multihashmap. | ||
151 | * Allows to enumerate elements asynchronously. | ||
152 | */ | ||
153 | struct GNUNET_CONTAINER_MultiHashMapIterator | ||
154 | { | ||
155 | /** | ||
156 | * Position in the bucket @e idx | ||
157 | */ | ||
158 | union MapEntry me; | ||
159 | |||
160 | /** | ||
161 | * Current bucket index. | ||
162 | */ | ||
163 | unsigned int idx; | ||
164 | |||
165 | /** | ||
166 | * Modification counter as observed on the map when the iterator | ||
167 | * was created. | ||
168 | */ | ||
169 | unsigned int modification_counter; | ||
170 | |||
171 | /** | ||
172 | * Map that we are iterating over. | ||
173 | */ | ||
174 | const struct GNUNET_CONTAINER_MultiHashMap *map; | ||
175 | }; | ||
176 | |||
177 | |||
178 | /** | ||
179 | * Create a multi hash map. | ||
180 | * | ||
181 | * @param len initial size (map will grow as needed) | ||
182 | * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default; | ||
183 | * #GNUNET_YES means that on 'put', the 'key' does not have | ||
184 | * to be copied as the destination of the pointer is | ||
185 | * guaranteed to be life as long as the value is stored in | ||
186 | * the hashmap. This can significantly reduce memory | ||
187 | * consumption, but of course is also a recipe for | ||
188 | * heap corruption if the assumption is not true. Only | ||
189 | * use this if (1) memory use is important in this case and | ||
190 | * (2) you have triple-checked that the invariant holds | ||
191 | * @return NULL on error | ||
192 | */ | ||
193 | struct GNUNET_CONTAINER_MultiHashMap * | ||
194 | GNUNET_CONTAINER_multihashmap_create (unsigned int len, int do_not_copy_keys) | ||
195 | { | ||
196 | struct GNUNET_CONTAINER_MultiHashMap *hm; | ||
197 | |||
198 | GNUNET_assert (len > 0); | ||
199 | hm = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap); | ||
200 | if (len * sizeof(union MapEntry) > GNUNET_MAX_MALLOC_CHECKED) | ||
201 | { | ||
202 | size_t s; | ||
203 | /* application *explicitly* requested very large map, hopefully | ||
204 | it checks the return value... */ | ||
205 | s = len * sizeof(union MapEntry); | ||
206 | if ((s / sizeof(union MapEntry)) != len) | ||
207 | return NULL; /* integer overflow on multiplication */ | ||
208 | if (NULL == (hm->map = GNUNET_malloc_large (s))) | ||
209 | { | ||
210 | /* out of memory */ | ||
211 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, | ||
212 | "Out of memory allocating large hash map (%u entries)\n", | ||
213 | len); | ||
214 | GNUNET_free (hm); | ||
215 | return NULL; | ||
216 | } | ||
217 | } | ||
218 | else | ||
219 | { | ||
220 | hm->map = GNUNET_new_array (len, union MapEntry); | ||
221 | } | ||
222 | hm->map_length = len; | ||
223 | hm->use_small_entries = do_not_copy_keys; | ||
224 | return hm; | ||
225 | } | ||
226 | |||
227 | |||
228 | /** | ||
229 | * Destroy a hash map. Will not free any values stored in the hash | ||
230 | * map! | ||
231 | * | ||
232 | * @param map the map | ||
233 | */ | ||
234 | void | ||
235 | GNUNET_CONTAINER_multihashmap_destroy ( | ||
236 | struct GNUNET_CONTAINER_MultiHashMap *map) | ||
237 | { | ||
238 | GNUNET_assert (0 == map->next_cache_off); | ||
239 | for (unsigned int i = 0; i < map->map_length; i++) | ||
240 | { | ||
241 | union MapEntry me; | ||
242 | |||
243 | me = map->map[i]; | ||
244 | if (map->use_small_entries) | ||
245 | { | ||
246 | struct SmallMapEntry *sme; | ||
247 | struct SmallMapEntry *nxt; | ||
248 | |||
249 | nxt = me.sme; | ||
250 | while (NULL != (sme = nxt)) | ||
251 | { | ||
252 | nxt = sme->next; | ||
253 | GNUNET_free (sme); | ||
254 | } | ||
255 | me.sme = NULL; | ||
256 | } | ||
257 | else | ||
258 | { | ||
259 | struct BigMapEntry *bme; | ||
260 | struct BigMapEntry *nxt; | ||
261 | |||
262 | nxt = me.bme; | ||
263 | while (NULL != (bme = nxt)) | ||
264 | { | ||
265 | nxt = bme->next; | ||
266 | GNUNET_free (bme); | ||
267 | } | ||
268 | me.bme = NULL; | ||
269 | } | ||
270 | } | ||
271 | GNUNET_free (map->map); | ||
272 | GNUNET_free (map); | ||
273 | } | ||
274 | |||
275 | |||
276 | /** | ||
277 | * Compute the index of the bucket for the given key. | ||
278 | * | ||
279 | * @param map hash map for which to compute the index | ||
280 | * @param key what key should the index be computed for | ||
281 | * @return offset into the "map" array of "map" | ||
282 | */ | ||
283 | static unsigned int | ||
284 | idx_of (const struct GNUNET_CONTAINER_MultiHashMap *map, | ||
285 | const struct GNUNET_HashCode *key) | ||
286 | { | ||
287 | GNUNET_assert (map != NULL); | ||
288 | return (*(unsigned int *) key) % map->map_length; | ||
289 | } | ||
290 | |||
291 | |||
292 | /** | ||
293 | * Get the number of key-value pairs in the map. | ||
294 | * | ||
295 | * @param map the map | ||
296 | * @return the number of key value pairs | ||
297 | */ | ||
298 | unsigned int | ||
299 | GNUNET_CONTAINER_multihashmap_size ( | ||
300 | const struct GNUNET_CONTAINER_MultiHashMap *map) | ||
301 | { | ||
302 | return map->size; | ||
303 | } | ||
304 | |||
305 | |||
306 | /** | ||
307 | * Given a key find a value in the map matching the key. | ||
308 | * | ||
309 | * @param map the map | ||
310 | * @param key what to look for | ||
311 | * @return NULL if no value was found; note that | ||
312 | * this is indistinguishable from values that just | ||
313 | * happen to be NULL; use "contains" to test for | ||
314 | * key-value pairs with value NULL | ||
315 | */ | ||
316 | void * | ||
317 | GNUNET_CONTAINER_multihashmap_get ( | ||
318 | const struct GNUNET_CONTAINER_MultiHashMap *map, | ||
319 | const struct GNUNET_HashCode *key) | ||
320 | { | ||
321 | union MapEntry me; | ||
322 | |||
323 | me = map->map[idx_of (map, key)]; | ||
324 | if (map->use_small_entries) | ||
325 | { | ||
326 | struct SmallMapEntry *sme; | ||
327 | |||
328 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
329 | if (0 == GNUNET_memcmp (key, sme->key)) | ||
330 | return sme->value; | ||
331 | } | ||
332 | else | ||
333 | { | ||
334 | struct BigMapEntry *bme; | ||
335 | |||
336 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
337 | if (0 == GNUNET_memcmp (key, &bme->key)) | ||
338 | return bme->value; | ||
339 | } | ||
340 | return NULL; | ||
341 | } | ||
342 | |||
343 | |||
344 | /** | ||
345 | * Iterate over all entries in the map. | ||
346 | * | ||
347 | * @param map the map | ||
348 | * @param it function to call on each entry | ||
349 | * @param it_cls extra argument to @a it | ||
350 | * @return the number of key value pairs processed, | ||
351 | * #GNUNET_SYSERR if it aborted iteration | ||
352 | */ | ||
353 | int | ||
354 | GNUNET_CONTAINER_multihashmap_iterate ( | ||
355 | struct GNUNET_CONTAINER_MultiHashMap *map, | ||
356 | GNUNET_CONTAINER_MulitHashMapIteratorCallback it, | ||
357 | void *it_cls) | ||
358 | { | ||
359 | int count; | ||
360 | union MapEntry me; | ||
361 | union MapEntry *ce; | ||
362 | struct GNUNET_HashCode kc; | ||
363 | |||
364 | GNUNET_assert (NULL != map); | ||
365 | ce = &map->next_cache[map->next_cache_off]; | ||
366 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); | ||
367 | count = 0; | ||
368 | for (unsigned i = 0; i < map->map_length; i++) | ||
369 | { | ||
370 | me = map->map[i]; | ||
371 | if (map->use_small_entries) | ||
372 | { | ||
373 | struct SmallMapEntry *sme; | ||
374 | |||
375 | ce->sme = me.sme; | ||
376 | while (NULL != (sme = ce->sme)) | ||
377 | { | ||
378 | ce->sme = sme->next; | ||
379 | if (NULL != it) | ||
380 | { | ||
381 | if (GNUNET_OK != it (it_cls, sme->key, sme->value)) | ||
382 | { | ||
383 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
384 | return GNUNET_SYSERR; | ||
385 | } | ||
386 | } | ||
387 | count++; | ||
388 | } | ||
389 | } | ||
390 | else | ||
391 | { | ||
392 | struct BigMapEntry *bme; | ||
393 | |||
394 | ce->bme = me.bme; | ||
395 | while (NULL != (bme = ce->bme)) | ||
396 | { | ||
397 | ce->bme = bme->next; | ||
398 | if (NULL != it) | ||
399 | { | ||
400 | kc = bme->key; | ||
401 | if (GNUNET_OK != it (it_cls, &kc, bme->value)) | ||
402 | { | ||
403 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
404 | return GNUNET_SYSERR; | ||
405 | } | ||
406 | } | ||
407 | count++; | ||
408 | } | ||
409 | } | ||
410 | } | ||
411 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
412 | return count; | ||
413 | } | ||
414 | |||
415 | |||
416 | /** | ||
417 | * We are about to free() the @a bme, make sure it is not in | ||
418 | * the list of next values for any iterator in the @a map's next_cache. | ||
419 | * | ||
420 | * @param map the map to check | ||
421 | * @param bme the entry that is about to be free'd | ||
422 | */ | ||
423 | static void | ||
424 | update_next_cache_bme (struct GNUNET_CONTAINER_MultiHashMap *map, | ||
425 | const struct BigMapEntry *bme) | ||
426 | { | ||
427 | for (unsigned int i = 0; i < map->next_cache_off; i++) | ||
428 | if (map->next_cache[i].bme == bme) | ||
429 | map->next_cache[i].bme = bme->next; | ||
430 | } | ||
431 | |||
432 | |||
433 | /** | ||
434 | * We are about to free() the @a sme, make sure it is not in | ||
435 | * the list of next values for any iterator in the @a map's next_cache. | ||
436 | * | ||
437 | * @param map the map to check | ||
438 | * @param sme the entry that is about to be free'd | ||
439 | */ | ||
440 | static void | ||
441 | update_next_cache_sme (struct GNUNET_CONTAINER_MultiHashMap *map, | ||
442 | const struct SmallMapEntry *sme) | ||
443 | { | ||
444 | for (unsigned int i = 0; i < map->next_cache_off; i++) | ||
445 | if (map->next_cache[i].sme == sme) | ||
446 | map->next_cache[i].sme = sme->next; | ||
447 | } | ||
448 | |||
449 | |||
450 | /** | ||
451 | * Remove the given key-value pair from the map. Note that if the | ||
452 | * key-value pair is in the map multiple times, only one of the pairs | ||
453 | * will be removed. | ||
454 | * | ||
455 | * @param map the map | ||
456 | * @param key key of the key-value pair | ||
457 | * @param value value of the key-value pair | ||
458 | * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair | ||
459 | * is not in the map | ||
460 | */ | ||
461 | int | ||
462 | GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map, | ||
463 | const struct GNUNET_HashCode *key, | ||
464 | const void *value) | ||
465 | { | ||
466 | union MapEntry me; | ||
467 | unsigned int i; | ||
468 | |||
469 | map->modification_counter++; | ||
470 | |||
471 | i = idx_of (map, key); | ||
472 | me = map->map[i]; | ||
473 | if (map->use_small_entries) | ||
474 | { | ||
475 | struct SmallMapEntry *p; | ||
476 | |||
477 | p = NULL; | ||
478 | for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) | ||
479 | { | ||
480 | if ((0 == GNUNET_memcmp (key, sme->key)) && (value == sme->value)) | ||
481 | { | ||
482 | if (NULL == p) | ||
483 | map->map[i].sme = sme->next; | ||
484 | else | ||
485 | p->next = sme->next; | ||
486 | update_next_cache_sme (map, sme); | ||
487 | GNUNET_free (sme); | ||
488 | map->size--; | ||
489 | return GNUNET_YES; | ||
490 | } | ||
491 | p = sme; | ||
492 | } | ||
493 | } | ||
494 | else | ||
495 | { | ||
496 | struct BigMapEntry *p; | ||
497 | |||
498 | p = NULL; | ||
499 | for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) | ||
500 | { | ||
501 | if ((0 == GNUNET_memcmp (key, &bme->key)) && (value == bme->value)) | ||
502 | { | ||
503 | if (NULL == p) | ||
504 | map->map[i].bme = bme->next; | ||
505 | else | ||
506 | p->next = bme->next; | ||
507 | update_next_cache_bme (map, bme); | ||
508 | GNUNET_free (bme); | ||
509 | map->size--; | ||
510 | return GNUNET_YES; | ||
511 | } | ||
512 | p = bme; | ||
513 | } | ||
514 | } | ||
515 | return GNUNET_NO; | ||
516 | } | ||
517 | |||
518 | |||
519 | /** | ||
520 | * Remove all entries for the given key from the map. | ||
521 | * Note that the values would not be "freed". | ||
522 | * | ||
523 | * @param map the map | ||
524 | * @param key identifies values to be removed | ||
525 | * @return number of values removed | ||
526 | */ | ||
527 | int | ||
528 | GNUNET_CONTAINER_multihashmap_remove_all ( | ||
529 | struct GNUNET_CONTAINER_MultiHashMap *map, | ||
530 | const struct GNUNET_HashCode *key) | ||
531 | { | ||
532 | union MapEntry me; | ||
533 | unsigned int i; | ||
534 | int ret; | ||
535 | |||
536 | map->modification_counter++; | ||
537 | |||
538 | ret = 0; | ||
539 | i = idx_of (map, key); | ||
540 | me = map->map[i]; | ||
541 | if (map->use_small_entries) | ||
542 | { | ||
543 | struct SmallMapEntry *sme; | ||
544 | struct SmallMapEntry *p; | ||
545 | |||
546 | p = NULL; | ||
547 | sme = me.sme; | ||
548 | while (NULL != sme) | ||
549 | { | ||
550 | if (0 == GNUNET_memcmp (key, sme->key)) | ||
551 | { | ||
552 | if (NULL == p) | ||
553 | map->map[i].sme = sme->next; | ||
554 | else | ||
555 | p->next = sme->next; | ||
556 | update_next_cache_sme (map, sme); | ||
557 | GNUNET_free (sme); | ||
558 | map->size--; | ||
559 | if (NULL == p) | ||
560 | sme = map->map[i].sme; | ||
561 | else | ||
562 | sme = p->next; | ||
563 | ret++; | ||
564 | } | ||
565 | else | ||
566 | { | ||
567 | p = sme; | ||
568 | sme = sme->next; | ||
569 | } | ||
570 | } | ||
571 | } | ||
572 | else | ||
573 | { | ||
574 | struct BigMapEntry *bme; | ||
575 | struct BigMapEntry *p; | ||
576 | |||
577 | p = NULL; | ||
578 | bme = me.bme; | ||
579 | while (NULL != bme) | ||
580 | { | ||
581 | if (0 == GNUNET_memcmp (key, &bme->key)) | ||
582 | { | ||
583 | if (NULL == p) | ||
584 | map->map[i].bme = bme->next; | ||
585 | else | ||
586 | p->next = bme->next; | ||
587 | update_next_cache_bme (map, bme); | ||
588 | GNUNET_free (bme); | ||
589 | map->size--; | ||
590 | if (NULL == p) | ||
591 | bme = map->map[i].bme; | ||
592 | else | ||
593 | bme = p->next; | ||
594 | ret++; | ||
595 | } | ||
596 | else | ||
597 | { | ||
598 | p = bme; | ||
599 | bme = bme->next; | ||
600 | } | ||
601 | } | ||
602 | } | ||
603 | return ret; | ||
604 | } | ||
605 | |||
606 | |||
607 | /** | ||
608 | * Callback used to remove all entries from the map. | ||
609 | * | ||
610 | * @param cls the `struct GNUNET_CONTAINER_MultiHashMap` | ||
611 | * @param key the key | ||
612 | * @param value the value | ||
613 | * @return #GNUNET_OK (continue to iterate) | ||
614 | */ | ||
615 | static int | ||
616 | remove_all (void *cls, const struct GNUNET_HashCode *key, void *value) | ||
617 | { | ||
618 | struct GNUNET_CONTAINER_MultiHashMap *map = cls; | ||
619 | |||
620 | GNUNET_assert (GNUNET_YES == | ||
621 | GNUNET_CONTAINER_multihashmap_remove (map, key, value)); | ||
622 | return GNUNET_OK; | ||
623 | } | ||
624 | |||
625 | |||
626 | /** | ||
627 | * @ingroup hashmap | ||
628 | * Remove all entries from the map. | ||
629 | * Note that the values would not be "freed". | ||
630 | * | ||
631 | * @param map the map | ||
632 | * @return number of values removed | ||
633 | */ | ||
634 | unsigned int | ||
635 | GNUNET_CONTAINER_multihashmap_clear (struct GNUNET_CONTAINER_MultiHashMap *map) | ||
636 | { | ||
637 | unsigned int ret; | ||
638 | |||
639 | ret = map->size; | ||
640 | GNUNET_CONTAINER_multihashmap_iterate (map, &remove_all, map); | ||
641 | return ret; | ||
642 | } | ||
643 | |||
644 | |||
645 | /** | ||
646 | * Check if the map contains any value under the given | ||
647 | * key (including values that are NULL). | ||
648 | * | ||
649 | * @param map the map | ||
650 | * @param key the key to test if a value exists for it | ||
651 | * @return #GNUNET_YES if such a value exists, | ||
652 | * #GNUNET_NO if not | ||
653 | */ | ||
654 | int | ||
655 | GNUNET_CONTAINER_multihashmap_contains ( | ||
656 | const struct GNUNET_CONTAINER_MultiHashMap *map, | ||
657 | const struct GNUNET_HashCode *key) | ||
658 | { | ||
659 | union MapEntry me; | ||
660 | |||
661 | me = map->map[idx_of (map, key)]; | ||
662 | if (map->use_small_entries) | ||
663 | { | ||
664 | struct SmallMapEntry *sme; | ||
665 | |||
666 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
667 | if (0 == GNUNET_memcmp (key, sme->key)) | ||
668 | return GNUNET_YES; | ||
669 | } | ||
670 | else | ||
671 | { | ||
672 | struct BigMapEntry *bme; | ||
673 | |||
674 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
675 | if (0 == GNUNET_memcmp (key, &bme->key)) | ||
676 | return GNUNET_YES; | ||
677 | } | ||
678 | return GNUNET_NO; | ||
679 | } | ||
680 | |||
681 | |||
682 | /** | ||
683 | * Check if the map contains the given value under the given | ||
684 | * key. | ||
685 | * | ||
686 | * @param map the map | ||
687 | * @param key the key to test if a value exists for it | ||
688 | * @param value value to test for | ||
689 | * @return #GNUNET_YES if such a value exists, | ||
690 | * #GNUNET_NO if not | ||
691 | */ | ||
692 | int | ||
693 | GNUNET_CONTAINER_multihashmap_contains_value ( | ||
694 | const struct GNUNET_CONTAINER_MultiHashMap *map, | ||
695 | const struct GNUNET_HashCode *key, | ||
696 | const void *value) | ||
697 | { | ||
698 | union MapEntry me; | ||
699 | |||
700 | me = map->map[idx_of (map, key)]; | ||
701 | if (map->use_small_entries) | ||
702 | { | ||
703 | struct SmallMapEntry *sme; | ||
704 | |||
705 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
706 | if ((0 == GNUNET_memcmp (key, sme->key)) && (sme->value == value)) | ||
707 | return GNUNET_YES; | ||
708 | } | ||
709 | else | ||
710 | { | ||
711 | struct BigMapEntry *bme; | ||
712 | |||
713 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
714 | if ((0 == GNUNET_memcmp (key, &bme->key)) && (bme->value == value)) | ||
715 | return GNUNET_YES; | ||
716 | } | ||
717 | return GNUNET_NO; | ||
718 | } | ||
719 | |||
720 | |||
721 | /** | ||
722 | * Grow the given map to a more appropriate size. | ||
723 | * | ||
724 | * @param map the hash map to grow | ||
725 | */ | ||
726 | static void | ||
727 | grow (struct GNUNET_CONTAINER_MultiHashMap *map) | ||
728 | { | ||
729 | union MapEntry *old_map; | ||
730 | union MapEntry *new_map; | ||
731 | unsigned int old_len; | ||
732 | unsigned int new_len; | ||
733 | unsigned int idx; | ||
734 | |||
735 | old_map = map->map; | ||
736 | old_len = map->map_length; | ||
737 | GNUNET_assert (0 != old_len); | ||
738 | new_len = old_len * 2; | ||
739 | if (0 == new_len) /* 2^31 * 2 == 0 */ | ||
740 | new_len = old_len; /* never use 0 */ | ||
741 | if (new_len == old_len) | ||
742 | return; /* nothing changed */ | ||
743 | new_map = GNUNET_malloc_large (new_len * sizeof(union MapEntry)); | ||
744 | if (NULL == new_map) | ||
745 | return; /* grow not possible */ | ||
746 | map->modification_counter++; | ||
747 | map->map_length = new_len; | ||
748 | map->map = new_map; | ||
749 | for (unsigned int i = 0; i < old_len; i++) | ||
750 | { | ||
751 | if (map->use_small_entries) | ||
752 | { | ||
753 | struct SmallMapEntry *sme; | ||
754 | |||
755 | while (NULL != (sme = old_map[i].sme)) | ||
756 | { | ||
757 | old_map[i].sme = sme->next; | ||
758 | idx = idx_of (map, sme->key); | ||
759 | sme->next = new_map[idx].sme; | ||
760 | new_map[idx].sme = sme; | ||
761 | } | ||
762 | } | ||
763 | else | ||
764 | { | ||
765 | struct BigMapEntry *bme; | ||
766 | |||
767 | while (NULL != (bme = old_map[i].bme)) | ||
768 | { | ||
769 | old_map[i].bme = bme->next; | ||
770 | idx = idx_of (map, &bme->key); | ||
771 | bme->next = new_map[idx].bme; | ||
772 | new_map[idx].bme = bme; | ||
773 | } | ||
774 | } | ||
775 | } | ||
776 | GNUNET_free (old_map); | ||
777 | } | ||
778 | |||
779 | |||
780 | /** | ||
781 | * Store a key-value pair in the map. | ||
782 | * | ||
783 | * @param map the map | ||
784 | * @param key key to use | ||
785 | * @param value value to use | ||
786 | * @param opt options for put | ||
787 | * @return #GNUNET_OK on success, | ||
788 | * #GNUNET_NO if a value was replaced (with REPLACE) | ||
789 | * #GNUNET_SYSERR if UNIQUE_ONLY was the option and the | ||
790 | * value already exists | ||
791 | */ | ||
792 | int | ||
793 | GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, | ||
794 | const struct GNUNET_HashCode *key, | ||
795 | void *value, | ||
796 | enum GNUNET_CONTAINER_MultiHashMapOption opt) | ||
797 | { | ||
798 | union MapEntry me; | ||
799 | unsigned int i; | ||
800 | |||
801 | i = idx_of (map, key); | ||
802 | if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) && | ||
803 | (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST)) | ||
804 | { | ||
805 | me = map->map[i]; | ||
806 | if (map->use_small_entries) | ||
807 | { | ||
808 | struct SmallMapEntry *sme; | ||
809 | |||
810 | for (sme = me.sme; NULL != sme; sme = sme->next) | ||
811 | if (0 == GNUNET_memcmp (key, sme->key)) | ||
812 | { | ||
813 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) | ||
814 | return GNUNET_SYSERR; | ||
815 | sme->value = value; | ||
816 | return GNUNET_NO; | ||
817 | } | ||
818 | } | ||
819 | else | ||
820 | { | ||
821 | struct BigMapEntry *bme; | ||
822 | |||
823 | for (bme = me.bme; NULL != bme; bme = bme->next) | ||
824 | if (0 == GNUNET_memcmp (key, &bme->key)) | ||
825 | { | ||
826 | if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) | ||
827 | return GNUNET_SYSERR; | ||
828 | bme->value = value; | ||
829 | return GNUNET_NO; | ||
830 | } | ||
831 | } | ||
832 | } | ||
833 | if (map->size / 3 >= map->map_length / 4) | ||
834 | { | ||
835 | grow (map); | ||
836 | i = idx_of (map, key); | ||
837 | } | ||
838 | if (map->use_small_entries) | ||
839 | { | ||
840 | struct SmallMapEntry *sme; | ||
841 | |||
842 | sme = GNUNET_new (struct SmallMapEntry); | ||
843 | sme->key = key; | ||
844 | sme->value = value; | ||
845 | sme->next = map->map[i].sme; | ||
846 | map->map[i].sme = sme; | ||
847 | } | ||
848 | else | ||
849 | { | ||
850 | struct BigMapEntry *bme; | ||
851 | |||
852 | bme = GNUNET_new (struct BigMapEntry); | ||
853 | bme->key = *key; | ||
854 | bme->value = value; | ||
855 | bme->next = map->map[i].bme; | ||
856 | map->map[i].bme = bme; | ||
857 | } | ||
858 | map->size++; | ||
859 | return GNUNET_OK; | ||
860 | } | ||
861 | |||
862 | |||
863 | /** | ||
864 | * Iterate over all entries in the map that match a particular key. | ||
865 | * | ||
866 | * @param map the map | ||
867 | * @param key key that the entries must correspond to | ||
868 | * @param it function to call on each entry | ||
869 | * @param it_cls extra argument to it | ||
870 | * @return the number of key value pairs processed, | ||
871 | * #GNUNET_SYSERR if it aborted iteration | ||
872 | */ | ||
873 | int | ||
874 | GNUNET_CONTAINER_multihashmap_get_multiple ( | ||
875 | struct GNUNET_CONTAINER_MultiHashMap *map, | ||
876 | const struct GNUNET_HashCode *key, | ||
877 | GNUNET_CONTAINER_MulitHashMapIteratorCallback it, | ||
878 | void *it_cls) | ||
879 | { | ||
880 | int count; | ||
881 | union MapEntry *me; | ||
882 | union MapEntry *ce; | ||
883 | |||
884 | ce = &map->next_cache[map->next_cache_off]; | ||
885 | GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); | ||
886 | count = 0; | ||
887 | me = &map->map[idx_of (map, key)]; | ||
888 | if (map->use_small_entries) | ||
889 | { | ||
890 | struct SmallMapEntry *sme; | ||
891 | |||
892 | ce->sme = me->sme; | ||
893 | while (NULL != (sme = ce->sme)) | ||
894 | { | ||
895 | ce->sme = sme->next; | ||
896 | if (0 != GNUNET_memcmp (key, sme->key)) | ||
897 | continue; | ||
898 | if ((NULL != it) && (GNUNET_OK != it (it_cls, key, sme->value))) | ||
899 | { | ||
900 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
901 | return GNUNET_SYSERR; | ||
902 | } | ||
903 | count++; | ||
904 | } | ||
905 | } | ||
906 | else | ||
907 | { | ||
908 | struct BigMapEntry *bme; | ||
909 | |||
910 | ce->bme = me->bme; | ||
911 | while (NULL != (bme = ce->bme)) | ||
912 | { | ||
913 | ce->bme = bme->next; | ||
914 | if (0 != GNUNET_memcmp (key, &bme->key)) | ||
915 | continue; | ||
916 | if ((NULL != it) && (GNUNET_OK != it (it_cls, key, bme->value))) | ||
917 | { | ||
918 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
919 | return GNUNET_SYSERR; | ||
920 | } | ||
921 | count++; | ||
922 | } | ||
923 | } | ||
924 | GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); | ||
925 | return count; | ||
926 | } | ||
927 | |||
928 | |||
929 | /** | ||
930 | * @ingroup hashmap | ||
931 | * Call @a it on a random value from the map, or not at all | ||
932 | * if the map is empty. Note that this function has linear | ||
933 | * complexity (in the size of the map). | ||
934 | * | ||
935 | * @param map the map | ||
936 | * @param it function to call on a random entry | ||
937 | * @param it_cls extra argument to @a it | ||
938 | * @return the number of key value pairs processed, zero or one. | ||
939 | */ | ||
940 | unsigned int | ||
941 | GNUNET_CONTAINER_multihashmap_get_random ( | ||
942 | const struct GNUNET_CONTAINER_MultiHashMap *map, | ||
943 | GNUNET_CONTAINER_MulitHashMapIteratorCallback it, | ||
944 | void *it_cls) | ||
945 | { | ||
946 | unsigned int off; | ||
947 | unsigned int idx; | ||
948 | union MapEntry me; | ||
949 | |||
950 | if (0 == map->size) | ||
951 | return 0; | ||
952 | if (NULL == it) | ||
953 | return 1; | ||
954 | off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, map->size); | ||
955 | for (idx = 0; idx < map->map_length; idx++) | ||
956 | { | ||
957 | me = map->map[idx]; | ||
958 | if (map->use_small_entries) | ||
959 | { | ||
960 | struct SmallMapEntry *sme; | ||
961 | struct SmallMapEntry *nxt; | ||
962 | |||
963 | nxt = me.sme; | ||
964 | while (NULL != (sme = nxt)) | ||
965 | { | ||
966 | nxt = sme->next; | ||
967 | if (0 == off) | ||
968 | { | ||
969 | if (GNUNET_OK != it (it_cls, sme->key, sme->value)) | ||
970 | return GNUNET_SYSERR; | ||
971 | return 1; | ||
972 | } | ||
973 | off--; | ||
974 | } | ||
975 | } | ||
976 | else | ||
977 | { | ||
978 | struct BigMapEntry *bme; | ||
979 | struct BigMapEntry *nxt; | ||
980 | |||
981 | nxt = me.bme; | ||
982 | while (NULL != (bme = nxt)) | ||
983 | { | ||
984 | nxt = bme->next; | ||
985 | if (0 == off) | ||
986 | { | ||
987 | if (GNUNET_OK != it (it_cls, &bme->key, bme->value)) | ||
988 | return GNUNET_SYSERR; | ||
989 | return 1; | ||
990 | } | ||
991 | off--; | ||
992 | } | ||
993 | } | ||
994 | } | ||
995 | GNUNET_break (0); | ||
996 | return GNUNET_SYSERR; | ||
997 | } | ||
998 | |||
999 | |||
1000 | /** | ||
1001 | * Create an iterator for a multihashmap. | ||
1002 | * The iterator can be used to retrieve all the elements in the multihashmap | ||
1003 | * one by one, without having to handle all elements at once (in contrast to | ||
1004 | * GNUNET_CONTAINER_multihashmap_iterate()). Note that the iterator can not be | ||
1005 | * used anymore if elements have been removed from 'map' after the creation of | ||
1006 | * the iterator, or 'map' has been destroyed. Adding elements to 'map' may | ||
1007 | * result in skipped or repeated elements. | ||
1008 | * | ||
1009 | * @param map the map to create an iterator for | ||
1010 | * @return an iterator over the given multihashmap 'map' | ||
1011 | */ | ||
1012 | struct GNUNET_CONTAINER_MultiHashMapIterator * | ||
1013 | GNUNET_CONTAINER_multihashmap_iterator_create ( | ||
1014 | const struct GNUNET_CONTAINER_MultiHashMap *map) | ||
1015 | { | ||
1016 | struct GNUNET_CONTAINER_MultiHashMapIterator *iter; | ||
1017 | |||
1018 | iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMapIterator); | ||
1019 | iter->map = map; | ||
1020 | iter->modification_counter = map->modification_counter; | ||
1021 | iter->me = map->map[0]; | ||
1022 | return iter; | ||
1023 | } | ||
1024 | |||
1025 | |||
1026 | /** | ||
1027 | * Retrieve the next element from the hash map at the iterator's position. | ||
1028 | * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value' | ||
1029 | * are not modified. | ||
1030 | * This operation is only allowed if no elements have been removed from the | ||
1031 | * multihashmap since the creation of 'iter', and the map has not been destroyed. | ||
1032 | * Adding elements may result in repeating or skipping elements. | ||
1033 | * | ||
1034 | * @param iter the iterator to get the next element from | ||
1035 | * @param key pointer to store the key in, can be NULL | ||
1036 | * @param value pointer to store the value in, can be NULL | ||
1037 | * @return #GNUNET_YES we returned an element, | ||
1038 | * #GNUNET_NO if we are out of elements | ||
1039 | */ | ||
1040 | int | ||
1041 | GNUNET_CONTAINER_multihashmap_iterator_next ( | ||
1042 | struct GNUNET_CONTAINER_MultiHashMapIterator *iter, | ||
1043 | struct GNUNET_HashCode *key, | ||
1044 | const void **value) | ||
1045 | { | ||
1046 | /* make sure the map has not been modified */ | ||
1047 | GNUNET_assert (iter->modification_counter == iter->map->modification_counter); | ||
1048 | |||
1049 | /* look for the next entry, skipping empty buckets */ | ||
1050 | while (1) | ||
1051 | { | ||
1052 | if (iter->idx >= iter->map->map_length) | ||
1053 | return GNUNET_NO; | ||
1054 | if (GNUNET_YES == iter->map->use_small_entries) | ||
1055 | { | ||
1056 | if (NULL != iter->me.sme) | ||
1057 | { | ||
1058 | if (NULL != key) | ||
1059 | *key = *iter->me.sme->key; | ||
1060 | if (NULL != value) | ||
1061 | *value = iter->me.sme->value; | ||
1062 | iter->me.sme = iter->me.sme->next; | ||
1063 | return GNUNET_YES; | ||
1064 | } | ||
1065 | } | ||
1066 | else | ||
1067 | { | ||
1068 | if (NULL != iter->me.bme) | ||
1069 | { | ||
1070 | if (NULL != key) | ||
1071 | *key = iter->me.bme->key; | ||
1072 | if (NULL != value) | ||
1073 | *value = iter->me.bme->value; | ||
1074 | iter->me.bme = iter->me.bme->next; | ||
1075 | return GNUNET_YES; | ||
1076 | } | ||
1077 | } | ||
1078 | iter->idx += 1; | ||
1079 | if (iter->idx < iter->map->map_length) | ||
1080 | iter->me = iter->map->map[iter->idx]; | ||
1081 | } | ||
1082 | } | ||
1083 | |||
1084 | |||
1085 | /** | ||
1086 | * Destroy a multihashmap iterator. | ||
1087 | * | ||
1088 | * @param iter the iterator to destroy | ||
1089 | */ | ||
1090 | void | ||
1091 | GNUNET_CONTAINER_multihashmap_iterator_destroy ( | ||
1092 | struct GNUNET_CONTAINER_MultiHashMapIterator *iter) | ||
1093 | { | ||
1094 | GNUNET_free (iter); | ||
1095 | } | ||
1096 | |||
1097 | |||
1098 | /* end of container_multihashmap.c */ | ||