2 This file is part of GNUnet.
3 Copyright (C) 2008 GNUnet e.V.
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.
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.
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/>.
18 SPDX-License-Identifier: AGPL3.0-or-later
21 * @file util/container_multihashmap32.c
22 * @brief a version of hash map implemented in container_multihashmap.c but with
24 * @author Christian Grothoff
25 * @author Sree Harsha Totakura
29 #include "gnunet_container_lib.h"
31 #define LOG(kind, ...) \
32 GNUNET_log_from (kind, "util-container-multihashmap32", __VA_ARGS__)
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.
41 #define NEXT_CACHE_SIZE 16
44 * An entry in the hash map.
59 * If there is a hash collision, we create a linked list.
61 struct MapEntry *next;
65 * Internal representation of the hash map.
67 struct GNUNET_CONTAINER_MultiHashMap32
72 struct MapEntry **map;
75 * Number of entries in the map.
80 * Length of the @e map array.
82 unsigned int map_length;
85 * Counts the destructive modifications (grow, remove)
86 * to the map, so that iterators can check if they are still valid.
88 unsigned int modification_counter;
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.
95 struct MapEntry *next_cache[NEXT_CACHE_SIZE];
98 * Offset of @e next_cache entries in use, must be smaller
99 * than #NEXT_CACHE_SIZE.
101 unsigned int next_cache_off;
106 * Cursor into a multihashmap.
107 * Allows to enumerate elements asynchronously.
109 struct GNUNET_CONTAINER_MultiHashMap32Iterator
112 * Position in the bucket @e idx
117 * Current bucket index.
122 * Modification counter as observed on the map when the iterator
125 unsigned int modification_counter;
128 * Map that we are iterating over.
130 const struct GNUNET_CONTAINER_MultiHashMap32 *map;
135 * Create a multi hash map.
137 * @param len initial size (map will grow as needed)
138 * @return NULL on error
140 struct GNUNET_CONTAINER_MultiHashMap32 *
141 GNUNET_CONTAINER_multihashmap32_create (unsigned int len)
143 struct GNUNET_CONTAINER_MultiHashMap32 *ret;
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)
153 ret->map_length = len;
159 * Destroy a hash map. Will not free any values
160 * stored in the hash map!
165 GNUNET_CONTAINER_multihashmap32_destroy (
166 struct GNUNET_CONTAINER_MultiHashMap32 *map)
170 for (unsigned int i = 0; i < map->map_length; i++)
172 while (NULL != (e = map->map[i]))
174 map->map[i] = e->next;
178 GNUNET_free (map->map);
184 * Compute the index of the bucket for the given key.
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"
191 idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, const uint32_t key)
193 GNUNET_assert (NULL != m);
194 return ((unsigned int) key) % m->map_length;
199 * Get the number of key-value pairs in the map.
202 * @return the number of key value pairs
205 GNUNET_CONTAINER_multihashmap32_size (
206 const struct GNUNET_CONTAINER_MultiHashMap32 *map)
213 * Given a key find a value in the map matching the key.
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
223 GNUNET_CONTAINER_multihashmap32_get (
224 const struct GNUNET_CONTAINER_MultiHashMap32 *map,
229 e = map->map[idx_of (map, key)];
241 * Iterate over all entries in 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
250 GNUNET_CONTAINER_multihashmap32_iterate (
251 struct GNUNET_CONTAINER_MultiHashMap32 *map,
252 GNUNET_CONTAINER_MulitHashMapIterator32Callback it,
256 struct MapEntry **ce;
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++)
267 while (NULL != (e = *ce))
272 if (GNUNET_OK != it (it_cls, e->key, e->value))
274 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
275 return GNUNET_SYSERR;
281 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
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.
290 * @param map the map to check
291 * @param bme the entry that is about to be free'd
294 update_next_cache (struct GNUNET_CONTAINER_MultiHashMap32 *map,
295 const struct MapEntry *me)
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;
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
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
315 GNUNET_CONTAINER_multihashmap32_remove (
316 struct GNUNET_CONTAINER_MultiHashMap32 *map,
324 map->modification_counter++;
326 i = idx_of (map, key);
331 if ((key == e->key) && (value == e->value))
334 map->map[i] = e->next;
337 update_next_cache (map, e);
350 * Remove all entries for the given key from the map.
351 * Note that the values would not be "freed".
354 * @param key identifies values to be removed
355 * @return number of values removed
358 GNUNET_CONTAINER_multihashmap32_remove_all (
359 struct GNUNET_CONTAINER_MultiHashMap32 *map,
367 map->modification_counter++;
370 i = idx_of (map, key);
378 map->map[i] = e->next;
381 update_next_cache (map, e);
401 * Check if the map contains any value under the given
402 * key (including values that are NULL).
405 * @param key the key to test if a value exists for it
406 * @return #GNUNET_YES if such a value exists,
410 GNUNET_CONTAINER_multihashmap32_contains (
411 const struct GNUNET_CONTAINER_MultiHashMap32 *map,
416 e = map->map[idx_of (map, key)];
428 * Check if the map contains the given value under the given
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,
438 GNUNET_CONTAINER_multihashmap32_contains_value (
439 const struct GNUNET_CONTAINER_MultiHashMap32 *map,
445 e = map->map[idx_of (map, key)];
448 if ((key == e->key) && (e->value == value))
457 * Grow the given map to a more appropriate size.
459 * @param map the hash map to grow
462 grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
464 struct MapEntry **old_map;
465 struct MapEntry **new_map;
467 unsigned int old_len;
468 unsigned int new_len;
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 *));
480 return; /* grow not possible */
481 map->modification_counter++;
482 map->map_length = new_len;
484 for (unsigned int i = 0; i < old_len; i++)
486 while (NULL != (e = old_map[i]))
488 old_map[i] = e->next;
489 idx = idx_of (map, e->key);
490 e->next = new_map[idx];
494 GNUNET_free (old_map);
499 * Store a key-value pair in 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
511 GNUNET_CONTAINER_multihashmap32_put (
512 struct GNUNET_CONTAINER_MultiHashMap32 *map,
515 enum GNUNET_CONTAINER_MultiHashMapOption opt)
520 i = idx_of (map, key);
521 if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
522 (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
529 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
530 return GNUNET_SYSERR;
537 if (map->size / 3 >= map->map_length / 4)
540 i = idx_of (map, key);
542 e = GNUNET_new (struct MapEntry);
545 e->next = map->map[i];
553 * Iterate over all entries in the map that match a particular key.
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
563 GNUNET_CONTAINER_multihashmap32_get_multiple (
564 struct GNUNET_CONTAINER_MultiHashMap32 *map,
566 GNUNET_CONTAINER_MulitHashMapIterator32Callback it,
571 struct MapEntry **ce;
574 ce = &map->next_cache[map->next_cache_off];
575 GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
577 *ce = map->map[idx_of (map, key)];
578 while (NULL != (e = *ce))
583 if ((NULL != it) && (GNUNET_OK != it (it_cls, key, e->value)))
585 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
586 return GNUNET_SYSERR;
590 GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
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.
604 * @param map the map to create an iterator for
605 * @return an iterator over the given multihashmap @a map
607 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
608 GNUNET_CONTAINER_multihashmap32_iterator_create (
609 const struct GNUNET_CONTAINER_MultiHashMap32 *map)
611 struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter;
613 iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32Iterator);
615 iter->modification_counter = map->modification_counter;
616 iter->me = map->map[0];
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'
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.
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
636 GNUNET_CONTAINER_multihashmap32_iterator_next (
637 struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
641 /* make sure the map has not been modified */
642 GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
644 /* look for the next entry, skipping empty buckets */
647 if (iter->idx >= iter->map->map_length)
649 if (NULL != iter->me)
652 *key = iter->me->key;
654 *value = iter->me->value;
655 iter->me = iter->me->next;
659 if (iter->idx < iter->map->map_length)
660 iter->me = iter->map->map[iter->idx];
666 * Destroy a multihashmap iterator.
668 * @param iter the iterator to destroy
671 GNUNET_CONTAINER_multihashmap32_iterator_destroy (
672 struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
678 /* end of container_multihashmap.c */