2 This file is part of GNUnet.
3 Copyright (C) 2008, 2012 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_multihashmap.c
22 * @brief hash map where the same key may be present multiple times
23 * @author Christian Grothoff
27 #include "gnunet_container_lib.h"
29 #define LOG(kind, ...) \
30 GNUNET_log_from(kind, "util-container-multihashmap", __VA_ARGS__)
33 * Maximum recursion depth for callbacks of
34 * #GNUNET_CONTAINER_multihashmap_get_multiple() themselve s
35 * again calling #GNUNET_CONTAINER_multihashmap_get_multiple().
36 * Should be totally excessive, but if violated we die.
38 #define NEXT_CACHE_SIZE 16
42 * An entry in the hash map with the full key.
51 * If there is a hash collision, we create a linked list.
53 struct BigMapEntry *next;
58 struct GNUNET_HashCode key;
63 * An entry in the hash map with just a pointer to the key.
65 struct SmallMapEntry {
72 * If there is a hash collision, we create a linked list.
74 struct SmallMapEntry *next;
79 const struct GNUNET_HashCode *key;
88 * Variant used if map entries only contain a pointer to the key.
90 struct SmallMapEntry *sme;
93 * Variant used if map entries contain the full key.
95 struct BigMapEntry *bme;
100 * Internal representation of the hash map.
102 struct GNUNET_CONTAINER_MultiHashMap {
104 * All of our buckets.
109 * Number of entries in the map.
114 * Length of the "map" array.
116 unsigned int map_length;
119 * #GNUNET_NO if the map entries are of type 'struct BigMapEntry',
120 * #GNUNET_YES if the map entries are of type 'struct SmallMapEntry'.
122 int use_small_entries;
125 * Counts the destructive modifications (grow, remove)
126 * to the map, so that iterators can check if they are still valid.
128 unsigned int modification_counter;
131 * Map entries indicating iteration positions currently
132 * in use by #GNUNET_CONTAINER_multihashmap_get_multiple().
133 * Only used up to @e next_cache_off.
135 union MapEntry next_cache[NEXT_CACHE_SIZE];
138 * Offset of @e next_cache entries in use, must be smaller
139 * than #NEXT_CACHE_SIZE.
141 unsigned int next_cache_off;
146 * Cursor into a multihashmap.
147 * Allows to enumerate elements asynchronously.
149 struct GNUNET_CONTAINER_MultiHashMapIterator {
151 * Position in the bucket @e idx
156 * Current bucket index.
161 * Modification counter as observed on the map when the iterator
164 unsigned int modification_counter;
167 * Map that we are iterating over.
169 const struct GNUNET_CONTAINER_MultiHashMap *map;
174 * Create a multi hash map.
176 * @param len initial size (map will grow as needed)
177 * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
178 * #GNUNET_YES means that on 'put', the 'key' does not have
179 * to be copied as the destination of the pointer is
180 * guaranteed to be life as long as the value is stored in
181 * the hashmap. This can significantly reduce memory
182 * consumption, but of course is also a recipie for
183 * heap corruption if the assumption is not true. Only
184 * use this if (1) memory use is important in this case and
185 * (2) you have triple-checked that the invariant holds
186 * @return NULL on error
188 struct GNUNET_CONTAINER_MultiHashMap *
189 GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
191 struct GNUNET_CONTAINER_MultiHashMap *hm;
193 GNUNET_assert(len > 0);
194 hm = GNUNET_new(struct GNUNET_CONTAINER_MultiHashMap);
195 if (len * sizeof(union MapEntry) > GNUNET_MAX_MALLOC_CHECKED)
198 /* application *explicitly* requested very large map, hopefully
199 it checks the return value... */
200 s = len * sizeof(union MapEntry);
201 if ((s / sizeof(union MapEntry)) != len)
202 return NULL; /* integer overflow on multiplication */
203 if (NULL == (hm->map = GNUNET_malloc_large(s)))
206 GNUNET_log(GNUNET_ERROR_TYPE_WARNING,
207 "Out of memory allocating large hash map (%u entries)\n",
215 hm->map = GNUNET_new_array(len, union MapEntry);
217 hm->map_length = len;
218 hm->use_small_entries = do_not_copy_keys;
224 * Destroy a hash map. Will not free any values stored in the hash
230 GNUNET_CONTAINER_multihashmap_destroy(
231 struct GNUNET_CONTAINER_MultiHashMap *map)
233 GNUNET_assert(0 == map->next_cache_off);
234 for (unsigned int i = 0; i < map->map_length; i++)
239 if (map->use_small_entries)
241 struct SmallMapEntry *sme;
242 struct SmallMapEntry *nxt;
245 while (NULL != (sme = nxt))
254 struct BigMapEntry *bme;
255 struct BigMapEntry *nxt;
258 while (NULL != (bme = nxt))
266 GNUNET_free(map->map);
272 * Compute the index of the bucket for the given key.
274 * @param map hash map for which to compute the index
275 * @param key what key should the index be computed for
276 * @return offset into the "map" array of "map"
279 idx_of(const struct GNUNET_CONTAINER_MultiHashMap *map,
280 const struct GNUNET_HashCode *key)
282 GNUNET_assert(map != NULL);
283 return (*(unsigned int *)key) % map->map_length;
288 * Get the number of key-value pairs in the map.
291 * @return the number of key value pairs
294 GNUNET_CONTAINER_multihashmap_size(
295 const struct GNUNET_CONTAINER_MultiHashMap *map)
302 * Given a key find a value in the map matching the key.
305 * @param key what to look for
306 * @return NULL if no value was found; note that
307 * this is indistinguishable from values that just
308 * happen to be NULL; use "contains" to test for
309 * key-value pairs with value NULL
312 GNUNET_CONTAINER_multihashmap_get(
313 const struct GNUNET_CONTAINER_MultiHashMap *map,
314 const struct GNUNET_HashCode *key)
318 me = map->map[idx_of(map, key)];
319 if (map->use_small_entries)
321 struct SmallMapEntry *sme;
323 for (sme = me.sme; NULL != sme; sme = sme->next)
324 if (0 == GNUNET_memcmp(key, sme->key))
329 struct BigMapEntry *bme;
331 for (bme = me.bme; NULL != bme; bme = bme->next)
332 if (0 == GNUNET_memcmp(key, &bme->key))
340 * Iterate over all entries in the map.
343 * @param it function to call on each entry
344 * @param it_cls extra argument to @a it
345 * @return the number of key value pairs processed,
346 * #GNUNET_SYSERR if it aborted iteration
349 GNUNET_CONTAINER_multihashmap_iterate(
350 struct GNUNET_CONTAINER_MultiHashMap *map,
351 GNUNET_CONTAINER_MulitHashMapIteratorCallback it,
357 struct GNUNET_HashCode kc;
359 GNUNET_assert(NULL != map);
360 ce = &map->next_cache[map->next_cache_off];
361 GNUNET_assert(++map->next_cache_off < NEXT_CACHE_SIZE);
363 for (unsigned i = 0; i < map->map_length; i++)
366 if (map->use_small_entries)
368 struct SmallMapEntry *sme;
371 while (NULL != (sme = ce->sme))
376 if (GNUNET_OK != it(it_cls, sme->key, sme->value))
378 GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE);
379 return GNUNET_SYSERR;
387 struct BigMapEntry *bme;
390 while (NULL != (bme = ce->bme))
396 if (GNUNET_OK != it(it_cls, &kc, bme->value))
398 GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE);
399 return GNUNET_SYSERR;
406 GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE);
412 * We are about to free() the @a bme, make sure it is not in
413 * the list of next values for any iterator in the @a map's next_cache.
415 * @param map the map to check
416 * @param bme the entry that is about to be free'd
419 update_next_cache_bme(struct GNUNET_CONTAINER_MultiHashMap *map,
420 const struct BigMapEntry *bme)
422 for (unsigned int i = 0; i < map->next_cache_off; i++)
423 if (map->next_cache[i].bme == bme)
424 map->next_cache[i].bme = bme->next;
429 * We are about to free() the @a sme, make sure it is not in
430 * the list of next values for any iterator in the @a map's next_cache.
432 * @param map the map to check
433 * @param sme the entry that is about to be free'd
436 update_next_cache_sme(struct GNUNET_CONTAINER_MultiHashMap *map,
437 const struct SmallMapEntry *sme)
439 for (unsigned int i = 0; i < map->next_cache_off; i++)
440 if (map->next_cache[i].sme == sme)
441 map->next_cache[i].sme = sme->next;
446 * Remove the given key-value pair from the map. Note that if the
447 * key-value pair is in the map multiple times, only one of the pairs
451 * @param key key of the key-value pair
452 * @param value value of the key-value pair
453 * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair
457 GNUNET_CONTAINER_multihashmap_remove(struct GNUNET_CONTAINER_MultiHashMap *map,
458 const struct GNUNET_HashCode *key,
464 map->modification_counter++;
466 i = idx_of(map, key);
468 if (map->use_small_entries)
470 struct SmallMapEntry *p;
473 for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next)
475 if ((0 == GNUNET_memcmp(key, sme->key)) && (value == sme->value))
478 map->map[i].sme = sme->next;
481 update_next_cache_sme(map, sme);
491 struct BigMapEntry *p;
494 for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next)
496 if ((0 == GNUNET_memcmp(key, &bme->key)) && (value == bme->value))
499 map->map[i].bme = bme->next;
502 update_next_cache_bme(map, bme);
515 * Remove all entries for the given key from the map.
516 * Note that the values would not be "freed".
519 * @param key identifies values to be removed
520 * @return number of values removed
523 GNUNET_CONTAINER_multihashmap_remove_all(
524 struct GNUNET_CONTAINER_MultiHashMap *map,
525 const struct GNUNET_HashCode *key)
531 map->modification_counter++;
534 i = idx_of(map, key);
536 if (map->use_small_entries)
538 struct SmallMapEntry *sme;
539 struct SmallMapEntry *p;
545 if (0 == GNUNET_memcmp(key, sme->key))
548 map->map[i].sme = sme->next;
551 update_next_cache_sme(map, sme);
555 sme = map->map[i].sme;
569 struct BigMapEntry *bme;
570 struct BigMapEntry *p;
576 if (0 == GNUNET_memcmp(key, &bme->key))
579 map->map[i].bme = bme->next;
582 update_next_cache_bme(map, bme);
586 bme = map->map[i].bme;
603 * Callback used to remove all entries from the map.
605 * @param cls the `struct GNUNET_CONTAINER_MultiHashMap`
607 * @param value the value
608 * @return #GNUNET_OK (continue to iterate)
611 remove_all(void *cls, const struct GNUNET_HashCode *key, void *value)
613 struct GNUNET_CONTAINER_MultiHashMap *map = cls;
615 GNUNET_assert(GNUNET_YES ==
616 GNUNET_CONTAINER_multihashmap_remove(map, key, value));
623 * Remove all entries from the map.
624 * Note that the values would not be "freed".
627 * @return number of values removed
630 GNUNET_CONTAINER_multihashmap_clear(struct GNUNET_CONTAINER_MultiHashMap *map)
635 GNUNET_CONTAINER_multihashmap_iterate(map, &remove_all, map);
641 * Check if the map contains any value under the given
642 * key (including values that are NULL).
645 * @param key the key to test if a value exists for it
646 * @return #GNUNET_YES if such a value exists,
650 GNUNET_CONTAINER_multihashmap_contains(
651 const struct GNUNET_CONTAINER_MultiHashMap *map,
652 const struct GNUNET_HashCode *key)
656 me = map->map[idx_of(map, key)];
657 if (map->use_small_entries)
659 struct SmallMapEntry *sme;
661 for (sme = me.sme; NULL != sme; sme = sme->next)
662 if (0 == GNUNET_memcmp(key, sme->key))
667 struct BigMapEntry *bme;
669 for (bme = me.bme; NULL != bme; bme = bme->next)
670 if (0 == GNUNET_memcmp(key, &bme->key))
678 * Check if the map contains the given value under the given
682 * @param key the key to test if a value exists for it
683 * @param value value to test for
684 * @return #GNUNET_YES if such a value exists,
688 GNUNET_CONTAINER_multihashmap_contains_value(
689 const struct GNUNET_CONTAINER_MultiHashMap *map,
690 const struct GNUNET_HashCode *key,
695 me = map->map[idx_of(map, key)];
696 if (map->use_small_entries)
698 struct SmallMapEntry *sme;
700 for (sme = me.sme; NULL != sme; sme = sme->next)
701 if ((0 == GNUNET_memcmp(key, sme->key)) && (sme->value == value))
706 struct BigMapEntry *bme;
708 for (bme = me.bme; NULL != bme; bme = bme->next)
709 if ((0 == GNUNET_memcmp(key, &bme->key)) && (bme->value == value))
717 * Grow the given map to a more appropriate size.
719 * @param map the hash map to grow
722 grow(struct GNUNET_CONTAINER_MultiHashMap *map)
724 union MapEntry *old_map;
725 union MapEntry *new_map;
726 unsigned int old_len;
727 unsigned int new_len;
731 old_len = map->map_length;
732 GNUNET_assert(0 != old_len);
733 new_len = old_len * 2;
734 if (0 == new_len) /* 2^31 * 2 == 0 */
735 new_len = old_len; /* never use 0 */
736 if (new_len == old_len)
737 return; /* nothing changed */
738 new_map = GNUNET_malloc_large(new_len * sizeof(union MapEntry));
740 return; /* grow not possible */
741 map->modification_counter++;
742 map->map_length = new_len;
744 for (unsigned int i = 0; i < old_len; i++)
746 if (map->use_small_entries)
748 struct SmallMapEntry *sme;
750 while (NULL != (sme = old_map[i].sme))
752 old_map[i].sme = sme->next;
753 idx = idx_of(map, sme->key);
754 sme->next = new_map[idx].sme;
755 new_map[idx].sme = sme;
760 struct BigMapEntry *bme;
762 while (NULL != (bme = old_map[i].bme))
764 old_map[i].bme = bme->next;
765 idx = idx_of(map, &bme->key);
766 bme->next = new_map[idx].bme;
767 new_map[idx].bme = bme;
771 GNUNET_free(old_map);
776 * Store a key-value pair in the map.
779 * @param key key to use
780 * @param value value to use
781 * @param opt options for put
782 * @return #GNUNET_OK on success,
783 * #GNUNET_NO if a value was replaced (with REPLACE)
784 * #GNUNET_SYSERR if UNIQUE_ONLY was the option and the
785 * value already exists
788 GNUNET_CONTAINER_multihashmap_put(struct GNUNET_CONTAINER_MultiHashMap *map,
789 const struct GNUNET_HashCode *key,
791 enum GNUNET_CONTAINER_MultiHashMapOption opt)
796 i = idx_of(map, key);
797 if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
798 (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
801 if (map->use_small_entries)
803 struct SmallMapEntry *sme;
805 for (sme = me.sme; NULL != sme; sme = sme->next)
806 if (0 == GNUNET_memcmp(key, sme->key))
808 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
809 return GNUNET_SYSERR;
816 struct BigMapEntry *bme;
818 for (bme = me.bme; NULL != bme; bme = bme->next)
819 if (0 == GNUNET_memcmp(key, &bme->key))
821 if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
822 return GNUNET_SYSERR;
828 if (map->size / 3 >= map->map_length / 4)
831 i = idx_of(map, key);
833 if (map->use_small_entries)
835 struct SmallMapEntry *sme;
837 sme = GNUNET_new(struct SmallMapEntry);
840 sme->next = map->map[i].sme;
841 map->map[i].sme = sme;
845 struct BigMapEntry *bme;
847 bme = GNUNET_new(struct BigMapEntry);
850 bme->next = map->map[i].bme;
851 map->map[i].bme = bme;
859 * Iterate over all entries in the map that match a particular key.
862 * @param key key that the entries must correspond to
863 * @param it function to call on each entry
864 * @param it_cls extra argument to it
865 * @return the number of key value pairs processed,
866 * #GNUNET_SYSERR if it aborted iteration
869 GNUNET_CONTAINER_multihashmap_get_multiple(
870 struct GNUNET_CONTAINER_MultiHashMap *map,
871 const struct GNUNET_HashCode *key,
872 GNUNET_CONTAINER_MulitHashMapIteratorCallback it,
879 ce = &map->next_cache[map->next_cache_off];
880 GNUNET_assert(++map->next_cache_off < NEXT_CACHE_SIZE);
882 me = &map->map[idx_of(map, key)];
883 if (map->use_small_entries)
885 struct SmallMapEntry *sme;
888 while (NULL != (sme = ce->sme))
891 if (0 != GNUNET_memcmp(key, sme->key))
893 if ((NULL != it) && (GNUNET_OK != it(it_cls, key, sme->value)))
895 GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE);
896 return GNUNET_SYSERR;
903 struct BigMapEntry *bme;
906 while (NULL != (bme = ce->bme))
909 if (0 != GNUNET_memcmp(key, &bme->key))
911 if ((NULL != it) && (GNUNET_OK != it(it_cls, key, bme->value)))
913 GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE);
914 return GNUNET_SYSERR;
919 GNUNET_assert(--map->next_cache_off < NEXT_CACHE_SIZE);
926 * Call @a it on a random value from the map, or not at all
927 * if the map is empty. Note that this function has linear
928 * complexity (in the size of the map).
931 * @param it function to call on a random entry
932 * @param it_cls extra argument to @a it
933 * @return the number of key value pairs processed, zero or one.
936 GNUNET_CONTAINER_multihashmap_get_random(
937 const struct GNUNET_CONTAINER_MultiHashMap *map,
938 GNUNET_CONTAINER_MulitHashMapIteratorCallback it,
949 off = GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_NONCE, map->size);
950 for (idx = 0; idx < map->map_length; idx++)
953 if (map->use_small_entries)
955 struct SmallMapEntry *sme;
956 struct SmallMapEntry *nxt;
959 while (NULL != (sme = nxt))
964 if (GNUNET_OK != it(it_cls, sme->key, sme->value))
965 return GNUNET_SYSERR;
973 struct BigMapEntry *bme;
974 struct BigMapEntry *nxt;
977 while (NULL != (bme = nxt))
982 if (GNUNET_OK != it(it_cls, &bme->key, bme->value))
983 return GNUNET_SYSERR;
991 return GNUNET_SYSERR;
996 * Create an iterator for a multihashmap.
997 * The iterator can be used to retrieve all the elements in the multihashmap
998 * one by one, without having to handle all elements at once (in contrast to
999 * GNUNET_CONTAINER_multihashmap_iterate()). Note that the iterator can not be
1000 * used anymore if elements have been removed from 'map' after the creation of
1001 * the iterator, or 'map' has been destroyed. Adding elements to 'map' may
1002 * result in skipped or repeated elements.
1004 * @param map the map to create an iterator for
1005 * @return an iterator over the given multihashmap 'map'
1007 struct GNUNET_CONTAINER_MultiHashMapIterator *
1008 GNUNET_CONTAINER_multihashmap_iterator_create(
1009 const struct GNUNET_CONTAINER_MultiHashMap *map)
1011 struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
1013 iter = GNUNET_new(struct GNUNET_CONTAINER_MultiHashMapIterator);
1015 iter->modification_counter = map->modification_counter;
1016 iter->me = map->map[0];
1022 * Retrieve the next element from the hash map at the iterator's position.
1023 * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value'
1025 * This operation is only allowed if no elements have been removed from the
1026 * multihashmap since the creation of 'iter', and the map has not been destroyed.
1027 * Adding elements may result in repeating or skipping elements.
1029 * @param iter the iterator to get the next element from
1030 * @param key pointer to store the key in, can be NULL
1031 * @param value pointer to store the value in, can be NULL
1032 * @return #GNUNET_YES we returned an element,
1033 * #GNUNET_NO if we are out of elements
1036 GNUNET_CONTAINER_multihashmap_iterator_next(
1037 struct GNUNET_CONTAINER_MultiHashMapIterator *iter,
1038 struct GNUNET_HashCode *key,
1041 /* make sure the map has not been modified */
1042 GNUNET_assert(iter->modification_counter == iter->map->modification_counter);
1044 /* look for the next entry, skipping empty buckets */
1047 if (iter->idx >= iter->map->map_length)
1049 if (GNUNET_YES == iter->map->use_small_entries)
1051 if (NULL != iter->me.sme)
1054 *key = *iter->me.sme->key;
1056 *value = iter->me.sme->value;
1057 iter->me.sme = iter->me.sme->next;
1063 if (NULL != iter->me.bme)
1066 *key = iter->me.bme->key;
1068 *value = iter->me.bme->value;
1069 iter->me.bme = iter->me.bme->next;
1074 if (iter->idx < iter->map->map_length)
1075 iter->me = iter->map->map[iter->idx];
1081 * Destroy a multihashmap iterator.
1083 * @param iter the iterator to destroy
1086 GNUNET_CONTAINER_multihashmap_iterator_destroy(
1087 struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
1093 /* end of container_multihashmap.c */