aboutsummaryrefslogtreecommitdiff
path: root/src/util/container_multihashmap32.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/util/container_multihashmap32.c')
-rw-r--r--src/util/container_multihashmap32.c678
1 files changed, 0 insertions, 678 deletions
diff --git a/src/util/container_multihashmap32.c b/src/util/container_multihashmap32.c
deleted file mode 100644
index f349a5f80..000000000
--- a/src/util/container_multihashmap32.c
+++ /dev/null
@@ -1,678 +0,0 @@
1/*
2 This file is part of GNUnet.
3 Copyright (C) 2008 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_multihashmap32.c
22 * @brief a version of hash map implemented in container_multihashmap.c but with
23 * uint32_t as keys
24 * @author Christian Grothoff
25 * @author Sree Harsha Totakura
26 */
27
28#include "platform.h"
29#include "gnunet_container_lib.h"
30
31#define LOG(kind, ...) \
32 GNUNET_log_from (kind, "util-container-multihashmap32", __VA_ARGS__)
33
34
35/**
36 * Maximum recursion depth for callbacks of
37 * #GNUNET_CONTAINER_multihashmap_get_multiple() themselves
38 * again calling #GNUNET_CONTAINER_multihashmap_get_multiple().
39 * Should be totally excessive, but if violated we die.
40 */
41#define NEXT_CACHE_SIZE 16
42
43/**
44 * An entry in the hash map.
45 */
46struct MapEntry
47{
48 /**
49 * Key for the entry.
50 */
51 uint32_t key;
52
53 /**
54 * Value of the entry.
55 */
56 void *value;
57
58 /**
59 * If there is a hash collision, we create a linked list.
60 */
61 struct MapEntry *next;
62};
63
64/**
65 * Internal representation of the hash map.
66 */
67struct GNUNET_CONTAINER_MultiHashMap32
68{
69 /**
70 * All of our buckets.
71 */
72 struct MapEntry **map;
73
74 /**
75 * Number of entries in the map.
76 */
77 unsigned int size;
78
79 /**
80 * Length of the @e map array.
81 */
82 unsigned int map_length;
83
84 /**
85 * Counts the destructive modifications (grow, remove)
86 * to the map, so that iterators can check if they are still valid.
87 */
88 unsigned int modification_counter;
89
90 /**
91 * Map entries indicating iteration positions currently
92 * in use by #GNUNET_CONTAINER_multihashmap_get_multiple().
93 * Only used up to @e next_cache_off.
94 */
95 struct MapEntry *next_cache[NEXT_CACHE_SIZE];
96
97 /**
98 * Offset of @e next_cache entries in use, must be smaller
99 * than #NEXT_CACHE_SIZE.
100 */
101 unsigned int next_cache_off;
102};
103
104
105/**
106 * Cursor into a multihashmap.
107 * Allows to enumerate elements asynchronously.
108 */
109struct GNUNET_CONTAINER_MultiHashMap32Iterator
110{
111 /**
112 * Position in the bucket @e idx
113 */
114 struct MapEntry *me;
115
116 /**
117 * Current bucket index.
118 */
119 unsigned int idx;
120
121 /**
122 * Modification counter as observed on the map when the iterator
123 * was created.
124 */
125 unsigned int modification_counter;
126
127 /**
128 * Map that we are iterating over.
129 */
130 const struct GNUNET_CONTAINER_MultiHashMap32 *map;
131};
132
133
134/**
135 * Create a multi hash map.
136 *
137 * @param len initial size (map will grow as needed)
138 * @return NULL on error
139 */
140struct GNUNET_CONTAINER_MultiHashMap32 *
141GNUNET_CONTAINER_multihashmap32_create (unsigned int len)
142{
143 struct GNUNET_CONTAINER_MultiHashMap32 *ret;
144
145 GNUNET_assert (len > 0);
146 ret = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32);
147 ret->map = GNUNET_malloc_large (len * sizeof(struct MapEntry *));
148 if (NULL == ret->map)
149 {
150 GNUNET_free (ret);
151 return NULL;
152 }
153 ret->map_length = len;
154 return ret;
155}
156
157
158/**
159 * Destroy a hash map. Will not free any values
160 * stored in the hash map!
161 *
162 * @param map the map
163 */
164void
165GNUNET_CONTAINER_multihashmap32_destroy (
166 struct GNUNET_CONTAINER_MultiHashMap32 *map)
167{
168 struct MapEntry *e;
169
170 for (unsigned int i = 0; i < map->map_length; i++)
171 {
172 while (NULL != (e = map->map[i]))
173 {
174 map->map[i] = e->next;
175 GNUNET_free (e);
176 }
177 }
178 GNUNET_free (map->map);
179 GNUNET_free (map);
180}
181
182
183/**
184 * Compute the index of the bucket for the given key.
185 *
186 * @param m hash map for which to compute the index
187 * @param key what key should the index be computed for
188 * @return offset into the "map" array of "m"
189 */
190static unsigned int
191idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, const uint32_t key)
192{
193 GNUNET_assert (NULL != m);
194 return ((unsigned int) key) % m->map_length;
195}
196
197
198/**
199 * Get the number of key-value pairs in the map.
200 *
201 * @param map the map
202 * @return the number of key value pairs
203 */
204unsigned int
205GNUNET_CONTAINER_multihashmap32_size (
206 const struct GNUNET_CONTAINER_MultiHashMap32 *map)
207{
208 return map->size;
209}
210
211
212/**
213 * Given a key find a value in the map matching the key.
214 *
215 * @param map the map
216 * @param key what to look for
217 * @return NULL if no value was found; note that
218 * this is indistinguishable from values that just
219 * happen to be NULL; use "contains" to test for
220 * key-value pairs with value NULL
221 */
222void *
223GNUNET_CONTAINER_multihashmap32_get (
224 const struct GNUNET_CONTAINER_MultiHashMap32 *map,
225 uint32_t key)
226{
227 struct MapEntry *e;
228
229 e = map->map[idx_of (map, key)];
230 while (NULL != e)
231 {
232 if (key == e->key)
233 return e->value;
234 e = e->next;
235 }
236 return NULL;
237}
238
239
240/**
241 * Iterate over all entries in the map.
242 *
243 * @param map the map
244 * @param it function to call on each entry
245 * @param it_cls extra argument to @a it
246 * @return the number of key value pairs processed,
247 * #GNUNET_SYSERR if it aborted iteration
248 */
249int
250GNUNET_CONTAINER_multihashmap32_iterate (
251 struct GNUNET_CONTAINER_MultiHashMap32 *map,
252 GNUNET_CONTAINER_MulitHashMapIterator32Callback it,
253 void *it_cls)
254{
255 int count;
256 struct MapEntry **ce;
257
258 count = 0;
259 GNUNET_assert (NULL != map);
260 ce = &map->next_cache[map->next_cache_off];
261 GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
262 for (unsigned int i = 0; i < map->map_length; i++)
263 {
264 struct MapEntry *e;
265
266 *ce = map->map[i];
267 while (NULL != (e = *ce))
268 {
269 *ce = e->next;
270 if (NULL != it)
271 {
272 if (GNUNET_OK != it (it_cls, e->key, e->value))
273 {
274 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
275 return GNUNET_SYSERR;
276 }
277 }
278 count++;
279 }
280 }
281 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
282 return count;
283}
284
285
286/**
287 * We are about to free() the @a bme, make sure it is not in
288 * the list of next values for any iterator in the @a map's next_cache.
289 *
290 * @param map the map to check
291 * @param bme the entry that is about to be free'd
292 */
293static void
294update_next_cache (struct GNUNET_CONTAINER_MultiHashMap32 *map,
295 const struct MapEntry *me)
296{
297 for (unsigned int i = 0; i < map->next_cache_off; i++)
298 if (map->next_cache[i] == me)
299 map->next_cache[i] = me->next;
300}
301
302
303/**
304 * Remove the given key-value pair from the map. Note that if the
305 * key-value pair is in the map multiple times, only one of the pairs
306 * will be removed.
307 *
308 * @param map the map
309 * @param key key of the key-value pair
310 * @param value value of the key-value pair
311 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
312 * is not in the map
313 */
314int
315GNUNET_CONTAINER_multihashmap32_remove (
316 struct GNUNET_CONTAINER_MultiHashMap32 *map,
317 uint32_t key,
318 const void *value)
319{
320 struct MapEntry *e;
321 struct MapEntry *p;
322 unsigned int i;
323
324 map->modification_counter++;
325
326 i = idx_of (map, key);
327 p = NULL;
328 e = map->map[i];
329 while (e != NULL)
330 {
331 if ((key == e->key) && (value == e->value))
332 {
333 if (p == NULL)
334 map->map[i] = e->next;
335 else
336 p->next = e->next;
337 update_next_cache (map, e);
338 GNUNET_free (e);
339 map->size--;
340 return GNUNET_YES;
341 }
342 p = e;
343 e = e->next;
344 }
345 return GNUNET_NO;
346}
347
348
349/**
350 * Remove all entries for the given key from the map.
351 * Note that the values would not be "freed".
352 *
353 * @param map the map
354 * @param key identifies values to be removed
355 * @return number of values removed
356 */
357int
358GNUNET_CONTAINER_multihashmap32_remove_all (
359 struct GNUNET_CONTAINER_MultiHashMap32 *map,
360 uint32_t key)
361{
362 struct MapEntry *e;
363 struct MapEntry *p;
364 unsigned int i;
365 int ret;
366
367 map->modification_counter++;
368
369 ret = 0;
370 i = idx_of (map, key);
371 p = NULL;
372 e = map->map[i];
373 while (e != NULL)
374 {
375 if (key == e->key)
376 {
377 if (p == NULL)
378 map->map[i] = e->next;
379 else
380 p->next = e->next;
381 update_next_cache (map, e);
382 GNUNET_free (e);
383 map->size--;
384 if (p == NULL)
385 e = map->map[i];
386 else
387 e = p->next;
388 ret++;
389 }
390 else
391 {
392 p = e;
393 e = e->next;
394 }
395 }
396 return ret;
397}
398
399
400/**
401 * Check if the map contains any value under the given
402 * key (including values that are NULL).
403 *
404 * @param map the map
405 * @param key the key to test if a value exists for it
406 * @return #GNUNET_YES if such a value exists,
407 * #GNUNET_NO if not
408 */
409int
410GNUNET_CONTAINER_multihashmap32_contains (
411 const struct GNUNET_CONTAINER_MultiHashMap32 *map,
412 uint32_t key)
413{
414 struct MapEntry *e;
415
416 e = map->map[idx_of (map, key)];
417 while (e != NULL)
418 {
419 if (key == e->key)
420 return GNUNET_YES;
421 e = e->next;
422 }
423 return GNUNET_NO;
424}
425
426
427/**
428 * Check if the map contains the given value under the given
429 * key.
430 *
431 * @param map the map
432 * @param key the key to test if a value exists for it
433 * @param value value to test for
434 * @return #GNUNET_YES if such a value exists,
435 * #GNUNET_NO if not
436 */
437int
438GNUNET_CONTAINER_multihashmap32_contains_value (
439 const struct GNUNET_CONTAINER_MultiHashMap32 *map,
440 uint32_t key,
441 const void *value)
442{
443 struct MapEntry *e;
444
445 e = map->map[idx_of (map, key)];
446 while (e != NULL)
447 {
448 if ((key == e->key) && (e->value == value))
449 return GNUNET_YES;
450 e = e->next;
451 }
452 return GNUNET_NO;
453}
454
455
456/**
457 * Grow the given map to a more appropriate size.
458 *
459 * @param map the hash map to grow
460 */
461static void
462grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
463{
464 struct MapEntry **old_map;
465 struct MapEntry **new_map;
466 struct MapEntry *e;
467 unsigned int old_len;
468 unsigned int new_len;
469 unsigned int idx;
470
471 old_map = map->map;
472 old_len = map->map_length;
473 new_len = old_len * 2;
474 if (0 == new_len) /* 2^31 * 2 == 0 */
475 new_len = old_len; /* never use 0 */
476 if (new_len == old_len)
477 return; /* nothing changed */
478 new_map = GNUNET_malloc_large (new_len * sizeof(struct MapEntry *));
479 if (NULL == new_map)
480 return; /* grow not possible */
481 map->modification_counter++;
482 map->map_length = new_len;
483 map->map = new_map;
484 for (unsigned int i = 0; i < old_len; i++)
485 {
486 while (NULL != (e = old_map[i]))
487 {
488 old_map[i] = e->next;
489 idx = idx_of (map, e->key);
490 e->next = new_map[idx];
491 new_map[idx] = e;
492 }
493 }
494 GNUNET_free (old_map);
495}
496
497
498/**
499 * Store a key-value pair in the map.
500 *
501 * @param map the map
502 * @param key key to use
503 * @param value value to use
504 * @param opt options for put
505 * @return #GNUNET_OK on success,
506 * #GNUNET_NO if a value was replaced (with REPLACE)
507 * #GNUNET_SYSERR if UNIQUE_ONLY was the option and the
508 * value already exists
509 */
510int
511GNUNET_CONTAINER_multihashmap32_put (
512 struct GNUNET_CONTAINER_MultiHashMap32 *map,
513 uint32_t key,
514 void *value,
515 enum GNUNET_CONTAINER_MultiHashMapOption opt)
516{
517 struct MapEntry *e;
518 unsigned int i;
519
520 i = idx_of (map, key);
521 if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
522 (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
523 {
524 e = map->map[i];
525 while (e != NULL)
526 {
527 if (key == e->key)
528 {
529 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
530 return GNUNET_SYSERR;
531 e->value = value;
532 return GNUNET_NO;
533 }
534 e = e->next;
535 }
536 }
537 if (map->size / 3 >= map->map_length / 4)
538 {
539 grow (map);
540 i = idx_of (map, key);
541 }
542 e = GNUNET_new (struct MapEntry);
543 e->key = key;
544 e->value = value;
545 e->next = map->map[i];
546 map->map[i] = e;
547 map->size++;
548 return GNUNET_OK;
549}
550
551
552/**
553 * Iterate over all entries in the map that match a particular key.
554 *
555 * @param map the map
556 * @param key key that the entries must correspond to
557 * @param it function to call on each entry
558 * @param it_cls extra argument to @a it
559 * @return the number of key value pairs processed,
560 * GNUNET_SYSERR if it aborted iteration
561 */
562int
563GNUNET_CONTAINER_multihashmap32_get_multiple (
564 struct GNUNET_CONTAINER_MultiHashMap32 *map,
565 uint32_t key,
566 GNUNET_CONTAINER_MulitHashMapIterator32Callback it,
567 void *it_cls)
568{
569 int count;
570 struct MapEntry *e;
571 struct MapEntry **ce;
572
573 count = 0;
574 ce = &map->next_cache[map->next_cache_off];
575 GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
576
577 *ce = map->map[idx_of (map, key)];
578 while (NULL != (e = *ce))
579 {
580 *ce = e->next;
581 if (key != e->key)
582 continue;
583 if ((NULL != it) && (GNUNET_OK != it (it_cls, key, e->value)))
584 {
585 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
586 return GNUNET_SYSERR;
587 }
588 count++;
589 }
590 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
591 return count;
592}
593
594
595/**
596 * Create an iterator for a multihashmap.
597 * The iterator can be used to retrieve all the elements in the multihashmap
598 * one by one, without having to handle all elements at once (in contrast to
599 * GNUNET_CONTAINER_multihashmap_iterate()). Note that the iterator can not be
600 * used anymore if elements have been removed from 'map' after the creation of
601 * the iterator, or 'map' has been destroyed. Adding elements to 'map' may
602 * result in skipped or repeated elements.
603 *
604 * @param map the map to create an iterator for
605 * @return an iterator over the given multihashmap @a map
606 */
607struct GNUNET_CONTAINER_MultiHashMap32Iterator *
608GNUNET_CONTAINER_multihashmap32_iterator_create (
609 const struct GNUNET_CONTAINER_MultiHashMap32 *map)
610{
611 struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter;
612
613 iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32Iterator);
614 iter->map = map;
615 iter->modification_counter = map->modification_counter;
616 iter->me = map->map[0];
617 return iter;
618}
619
620
621/**
622 * Retrieve the next element from the hash map at the iterator's position.
623 * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
624 * are not modified.
625 * This operation is only allowed if no elements have been removed from the
626 * multihashmap since the creation of 'iter', and the map has not been destroyed.
627 * Adding elements may result in repeating or skipping elements.
628 *
629 * @param iter the iterator to get the next element from
630 * @param key pointer to store the key in, can be NULL
631 * @param value pointer to store the value in, can be NULL
632 * @return #GNUNET_YES we returned an element,
633 * #GNUNET_NO if we are out of elements
634 */
635int
636GNUNET_CONTAINER_multihashmap32_iterator_next (
637 struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
638 uint32_t *key,
639 const void **value)
640{
641 /* make sure the map has not been modified */
642 GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
643
644 /* look for the next entry, skipping empty buckets */
645 while (1)
646 {
647 if (iter->idx >= iter->map->map_length)
648 return GNUNET_NO;
649 if (NULL != iter->me)
650 {
651 if (NULL != key)
652 *key = iter->me->key;
653 if (NULL != value)
654 *value = iter->me->value;
655 iter->me = iter->me->next;
656 return GNUNET_YES;
657 }
658 iter->idx += 1;
659 if (iter->idx < iter->map->map_length)
660 iter->me = iter->map->map[iter->idx];
661 }
662}
663
664
665/**
666 * Destroy a multihashmap iterator.
667 *
668 * @param iter the iterator to destroy
669 */
670void
671GNUNET_CONTAINER_multihashmap32_iterator_destroy (
672 struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
673{
674 GNUNET_free (iter);
675}
676
677
678/* end of container_multihashmap.c */
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-24 04:50:41 +0000