From 3c7d8978fadc492c68061aea11c18478b30b42b6 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Thu, 1 Nov 2018 17:59:34 +0100 Subject: fix #5465 --- src/util/container_multihashmap32.c | 159 +++++++++++++++++++++++------------- 1 file changed, 101 insertions(+), 58 deletions(-) (limited to 'src/util/container_multihashmap32.c') diff --git a/src/util/container_multihashmap32.c b/src/util/container_multihashmap32.c index daf5059b6..016dbabcc 100644 --- a/src/util/container_multihashmap32.c +++ b/src/util/container_multihashmap32.c @@ -28,6 +28,15 @@ #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multihashmap32", __VA_ARGS__) + +/** + * Maximum recursion depth for callbacks of + * #GNUNET_CONTAINER_multihashmap_get_multiple() themselves + * again calling #GNUNET_CONTAINER_multihashmap_get_multiple(). + * Should be totally excessive, but if violated we die. + */ +#define NEXT_CACHE_SIZE 16 + /** * An entry in the hash map. */ @@ -68,7 +77,7 @@ struct GNUNET_CONTAINER_MultiHashMap32 unsigned int size; /** - * Length of the "map" array. + * Length of the @e map array. */ unsigned int map_length; @@ -77,6 +86,19 @@ struct GNUNET_CONTAINER_MultiHashMap32 * to the map, so that iterators can check if they are still valid. */ unsigned int modification_counter; + + /** + * Map entries indicating iteration positions currently + * in use by #GNUNET_CONTAINER_multihashmap_get_multiple(). + * Only used up to @e next_cache_off. + */ + struct MapEntry *next_cache[NEXT_CACHE_SIZE]; + + /** + * Offset of @e next_cache entries in use, must be smaller + * than #NEXT_CACHE_SIZE. + */ + unsigned int next_cache_off; }; @@ -87,7 +109,7 @@ struct GNUNET_CONTAINER_MultiHashMap32 struct GNUNET_CONTAINER_MultiHashMap32Iterator { /** - * Position in the bucket 'idx' + * Position in the bucket @e idx */ struct MapEntry *me; @@ -122,7 +144,8 @@ GNUNET_CONTAINER_multihashmap32_create (unsigned int len) GNUNET_assert (len > 0); ret = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32); - ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *)); + ret->map = GNUNET_new_array (len, + struct MapEntry *); ret->map_length = len; return ret; } @@ -135,13 +158,11 @@ GNUNET_CONTAINER_multihashmap32_create (unsigned int len) * @param map the map */ void -GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 - *map) +GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 *map) { - unsigned int i; struct MapEntry *e; - for (i = 0; i < map->map_length; i++) + for (unsigned int i = 0; i < map->map_length; i++) { while (NULL != (e = map->map[i])) { @@ -165,7 +186,7 @@ static unsigned int idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, const uint32_t key) { - GNUNET_assert (m != NULL); + GNUNET_assert (NULL != m); return ((unsigned int) key) % m->map_length; } @@ -177,8 +198,7 @@ idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, * @return the number of key value pairs */ unsigned int -GNUNET_CONTAINER_multihashmap32_size (const struct - GNUNET_CONTAINER_MultiHashMap32 *map) +GNUNET_CONTAINER_multihashmap32_size (const struct GNUNET_CONTAINER_MultiHashMap32 *map) { return map->size; } @@ -195,14 +215,13 @@ GNUNET_CONTAINER_multihashmap32_size (const struct * key-value pairs with value NULL */ void * -GNUNET_CONTAINER_multihashmap32_get (const struct - GNUNET_CONTAINER_MultiHashMap32 *map, +GNUNET_CONTAINER_multihashmap32_get (const struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key) { struct MapEntry *e; e = map->map[idx_of (map, key)]; - while (e != NULL) + while (NULL != e) { if (key == e->key) return e->value; @@ -222,27 +241,30 @@ GNUNET_CONTAINER_multihashmap32_get (const struct * #GNUNET_SYSERR if it aborted iteration */ int -GNUNET_CONTAINER_multihashmap32_iterate (const struct - GNUNET_CONTAINER_MultiHashMap32 *map, - GNUNET_CONTAINER_HashMapIterator32 it, +GNUNET_CONTAINER_multihashmap32_iterate (struct GNUNET_CONTAINER_MultiHashMap32 *map, + GNUNET_CONTAINER_HashMapIterator32 it, void *it_cls) { int count; - unsigned int i; - struct MapEntry *e; - struct MapEntry *n; + struct MapEntry **ce; count = 0; GNUNET_assert (NULL != map); - for (i = 0; i < map->map_length; i++) + ce = &map->next_cache[map->next_cache_off]; + GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); + for (unsigned int i = 0; i < map->map_length; i++) { - n = map->map[i]; - while (NULL != (e = n)) + struct MapEntry *e; + + *ce = map->map[i]; + while (NULL != (e = *ce)) { - n = e->next; + *ce = e->next; if (NULL != it) { - if (GNUNET_OK != it (it_cls, e->key, e->value)) + if (GNUNET_OK != it (it_cls, + e->key, + e->value)) return GNUNET_SYSERR; } count++; @@ -252,6 +274,23 @@ GNUNET_CONTAINER_multihashmap32_iterate (const struct } +/** + * We are about to free() the @a bme, make sure it is not in + * the list of next values for any iterator in the @a map's next_cache. + * + * @param map the map to check + * @param bme the entry that is about to be free'd + */ +static void +update_next_cache (struct GNUNET_CONTAINER_MultiHashMap32 *map, + const struct MapEntry *me) +{ + for (unsigned int i=0;inext_cache_off;i++) + if (map->next_cache[i] == me) + map->next_cache[i] = me->next; +} + + /** * Remove the given key-value pair from the map. Note that if the * key-value pair is in the map multiple times, only one of the pairs @@ -260,13 +299,13 @@ GNUNET_CONTAINER_multihashmap32_iterate (const struct * @param map the map * @param key key of the key-value pair * @param value value of the key-value pair - * @return GNUNET_YES on success, GNUNET_NO if the key-value pair + * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair * is not in the map */ int -GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 - *map, - uint32_t key, const void *value) +GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map, + uint32_t key, + const void *value) { struct MapEntry *e; struct MapEntry *p; @@ -285,6 +324,8 @@ GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 map->map[i] = e->next; else p->next = e->next; + update_next_cache (map, + e); GNUNET_free (e); map->size--; return GNUNET_YES; @@ -305,9 +346,7 @@ GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 * @return number of values removed */ int -GNUNET_CONTAINER_multihashmap32_remove_all (struct - GNUNET_CONTAINER_MultiHashMap32 - *map, +GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key) { struct MapEntry *e; @@ -329,6 +368,8 @@ GNUNET_CONTAINER_multihashmap32_remove_all (struct map->map[i] = e->next; else p->next = e->next; + update_next_cache (map, + e); GNUNET_free (e); map->size--; if (p == NULL) @@ -353,12 +394,11 @@ GNUNET_CONTAINER_multihashmap32_remove_all (struct * * @param map the map * @param key the key to test if a value exists for it - * @return GNUNET_YES if such a value exists, - * GNUNET_NO if not + * @return #GNUNET_YES if such a value exists, + * #GNUNET_NO if not */ int -GNUNET_CONTAINER_multihashmap32_contains (const struct - GNUNET_CONTAINER_MultiHashMap32 *map, +GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key) { struct MapEntry *e; @@ -381,13 +421,11 @@ GNUNET_CONTAINER_multihashmap32_contains (const struct * @param map the map * @param key the key to test if a value exists for it * @param value value to test for - * @return GNUNET_YES if such a value exists, - * GNUNET_NO if not + * @return #GNUNET_YES if such a value exists, + * #GNUNET_NO if not */ int -GNUNET_CONTAINER_multihashmap32_contains_value (const struct - GNUNET_CONTAINER_MultiHashMap32 - *map, +GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key, const void *value) { @@ -418,17 +456,17 @@ grow (struct GNUNET_CONTAINER_MultiHashMap32 *map) unsigned int old_len; unsigned int new_len; unsigned int idx; - unsigned int i; map->modification_counter++; old_map = map->map; old_len = map->map_length; new_len = old_len * 2; - new_map = GNUNET_malloc (sizeof (struct MapEntry *) * new_len); + new_map = GNUNET_new_array (new_len, + struct MapEntry *); map->map_length = new_len; map->map = new_map; - for (i = 0; i < old_len; i++) + for (unsigned int i = 0; i < old_len; i++) { while (NULL != (e = old_map[i])) { @@ -449,9 +487,9 @@ grow (struct GNUNET_CONTAINER_MultiHashMap32 *map) * @param key key to use * @param value value to use * @param opt options for put - * @return GNUNET_OK on success, - * GNUNET_NO if a value was replaced (with REPLACE) - * GNUNET_SYSERR if UNIQUE_ONLY was the option and the + * @return #GNUNET_OK on success, + * #GNUNET_NO if a value was replaced (with REPLACE) + * #GNUNET_SYSERR if UNIQUE_ONLY was the option and the * value already exists */ int @@ -501,29 +539,34 @@ GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 * @param map the map * @param key key that the entries must correspond to * @param it function to call on each entry - * @param it_cls extra argument to it + * @param it_cls extra argument to @a it * @return the number of key value pairs processed, * GNUNET_SYSERR if it aborted iteration */ int -GNUNET_CONTAINER_multihashmap32_get_multiple (const struct - GNUNET_CONTAINER_MultiHashMap32 - *map, uint32_t key, - GNUNET_CONTAINER_HashMapIterator32 - it, void *it_cls) +GNUNET_CONTAINER_multihashmap32_get_multiple (struct GNUNET_CONTAINER_MultiHashMap32 *map, + uint32_t key, + GNUNET_CONTAINER_HashMapIterator32 it, + void *it_cls) { int count; struct MapEntry *e; - struct MapEntry *n; + struct MapEntry **ce; count = 0; - n = map->map[idx_of (map, key)]; - while (NULL != (e = n)) + ce = &map->next_cache[map->next_cache_off]; + GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); + + *ce = map->map[idx_of (map, key)]; + while (NULL != (e = *ce)) { - n = e->next; + *ce = e->next; if (key != e->key) continue; - if ((it != NULL) && (GNUNET_OK != it (it_cls, key, e->value))) + if ( (NULL != it) && + (GNUNET_OK != it (it_cls, + key, + e->value)) ) return GNUNET_SYSERR; count++; } @@ -541,7 +584,7 @@ GNUNET_CONTAINER_multihashmap32_get_multiple (const struct * result in skipped or repeated elements. * * @param map the map to create an iterator for - * @return an iterator over the given multihashmap 'map' + * @return an iterator over the given multihashmap @a map */ struct GNUNET_CONTAINER_MultiHashMap32Iterator * GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map) -- cgit v1.2.3