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/include/gnunet_container_lib.h | 17 +-- src/util/container_multihashmap.c | 210 +++++++++++++++++++------- src/util/container_multihashmap32.c | 159 ++++++++++++-------- src/util/container_multipeermap.c | 282 +++++++++++++++++++++++------------ src/util/container_multishortmap.c | 286 +++++++++++++++++++++++------------- 5 files changed, 634 insertions(+), 320 deletions(-) (limited to 'src') diff --git a/src/include/gnunet_container_lib.h b/src/include/gnunet_container_lib.h index 2de65b2f1..bd9ce7bb2 100644 --- a/src/include/gnunet_container_lib.h +++ b/src/include/gnunet_container_lib.h @@ -928,7 +928,7 @@ GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap * * #GNUNET_SYSERR if it aborted iteration */ int -GNUNET_CONTAINER_multihashmap_iterate (const struct GNUNET_CONTAINER_MultiHashMap *map, +GNUNET_CONTAINER_multihashmap_iterate (struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_HashMapIterator it, void *it_cls); @@ -993,7 +993,7 @@ GNUNET_CONTAINER_multihashmap_iterator_destroy (struct GNUNET_CONTAINER_MultiHas * #GNUNET_SYSERR if it aborted iteration */ int -GNUNET_CONTAINER_multihashmap_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap *map, +GNUNET_CONTAINER_multihashmap_get_multiple (struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, GNUNET_CONTAINER_HashMapIterator it, void *it_cls); @@ -1194,7 +1194,7 @@ GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap * * #GNUNET_SYSERR if it aborted iteration */ int -GNUNET_CONTAINER_multipeermap_iterate (const struct GNUNET_CONTAINER_MultiPeerMap *map, +GNUNET_CONTAINER_multipeermap_iterate (struct GNUNET_CONTAINER_MultiPeerMap *map, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls); @@ -1260,7 +1260,7 @@ GNUNET_CONTAINER_multipeermap_iterator_destroy (struct GNUNET_CONTAINER_MultiPee * #GNUNET_SYSERR if it aborted iteration */ int -GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiPeerMap *map, +GNUNET_CONTAINER_multipeermap_get_multiple (struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls); @@ -1461,7 +1461,7 @@ GNUNET_CONTAINER_multishortmap_size (const struct GNUNET_CONTAINER_MultiShortmap * #GNUNET_SYSERR if it aborted iteration */ int -GNUNET_CONTAINER_multishortmap_iterate (const struct GNUNET_CONTAINER_MultiShortmap *map, +GNUNET_CONTAINER_multishortmap_iterate (struct GNUNET_CONTAINER_MultiShortmap *map, GNUNET_CONTAINER_ShortmapIterator it, void *it_cls); @@ -1529,7 +1529,7 @@ GNUNET_CONTAINER_multishortmap_iterator_destroy (struct GNUNET_CONTAINER_MultiSh * #GNUNET_SYSERR if it aborted iteration */ int -GNUNET_CONTAINER_multishortmap_get_multiple (const struct GNUNET_CONTAINER_MultiShortmap *map, +GNUNET_CONTAINER_multishortmap_get_multiple (struct GNUNET_CONTAINER_MultiShortmap *map, const struct GNUNET_ShortHashCode *key, GNUNET_CONTAINER_ShortmapIterator it, void *it_cls); @@ -1648,8 +1648,7 @@ 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_multihashmap32_iterate (struct GNUNET_CONTAINER_MultiHashMap32 *map, GNUNET_CONTAINER_HashMapIterator32 it, void *it_cls); @@ -1750,7 +1749,7 @@ GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 *map * #GNUNET_SYSERR if it aborted iteration */ int -GNUNET_CONTAINER_multihashmap32_get_multiple (const struct GNUNET_CONTAINER_MultiHashMap32 *map, +GNUNET_CONTAINER_multihashmap32_get_multiple (struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key, GNUNET_CONTAINER_HashMapIterator32 it, void *it_cls); diff --git a/src/util/container_multihashmap.c b/src/util/container_multihashmap.c index 1811f861f..e344c2aec 100644 --- a/src/util/container_multihashmap.c +++ b/src/util/container_multihashmap.c @@ -26,6 +26,15 @@ #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multihashmap", __VA_ARGS__) +/** + * Maximum recursion depth for callbacks of + * #GNUNET_CONTAINER_multihashmap_get_multiple() themselve s + * 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 with the full key. */ @@ -122,6 +131,19 @@ struct GNUNET_CONTAINER_MultiHashMap * 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. + */ + union 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; }; @@ -132,7 +154,7 @@ struct GNUNET_CONTAINER_MultiHashMap struct GNUNET_CONTAINER_MultiHashMapIterator { /** - * Position in the bucket 'idx' + * Position in the bucket @e idx */ union MapEntry me; @@ -207,15 +229,15 @@ GNUNET_CONTAINER_multihashmap_create (unsigned int len, /** - * Destroy a hash map. Will not free any values - * stored in the hash map! + * Destroy a hash map. Will not free any values stored in the hash + * map! * * @param map the map */ void -GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap - *map) +GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap *map) { + GNUNET_assert (0 == map->next_cache_off); for (unsigned int i = 0; i < map->map_length; i++) { union MapEntry me; @@ -304,7 +326,9 @@ GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap *m struct SmallMapEntry *sme; for (sme = me.sme; NULL != sme; sme = sme->next) - if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) + if (0 == memcmp (key, + sme->key, + sizeof (struct GNUNET_HashCode))) return sme->value; } else @@ -312,7 +336,9 @@ GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap *m struct BigMapEntry *bme; for (bme = me.bme; NULL != bme; bme = bme->next) - if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) + if (0 == memcmp (key, + &bme->key, + sizeof (struct GNUNET_HashCode))) return bme->value; } return NULL; @@ -329,34 +355,39 @@ GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap *m * #GNUNET_SYSERR if it aborted iteration */ int -GNUNET_CONTAINER_multihashmap_iterate (const struct - GNUNET_CONTAINER_MultiHashMap *map, +GNUNET_CONTAINER_multihashmap_iterate (struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_HashMapIterator it, void *it_cls) { int count; - unsigned int i; union MapEntry me; + union MapEntry *ce; struct GNUNET_HashCode kc; - 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); + count = 0; + for (unsigned i = 0; i < map->map_length; i++) { me = map->map[i]; if (map->use_small_entries) { struct SmallMapEntry *sme; - struct SmallMapEntry *nxt; - nxt = me.sme; - while (NULL != (sme = nxt)) + ce->sme = me.sme; + while (NULL != (sme = ce->sme)) { - nxt = sme->next; + ce->sme = sme->next; if (NULL != it) { - if (GNUNET_OK != it (it_cls, sme->key, sme->value)) + if (GNUNET_OK != it (it_cls, + sme->key, + sme->value)) + { + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return GNUNET_SYSERR; + } } count++; } @@ -364,26 +395,65 @@ GNUNET_CONTAINER_multihashmap_iterate (const struct else { struct BigMapEntry *bme; - struct BigMapEntry *nxt; - nxt = me.bme; - while (NULL != (bme = nxt)) + ce->bme = me.bme; + while (NULL != (bme = ce->bme)) { - nxt = bme->next; + ce->bme = bme->next; if (NULL != it) { kc = bme->key; - if (GNUNET_OK != it (it_cls, &kc, bme->value)) + if (GNUNET_OK != it (it_cls, + &kc, + bme->value)) + { + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return GNUNET_SYSERR; + } } count++; } } } + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return count; } +/** + * 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_bme (struct GNUNET_CONTAINER_MultiHashMap *map, + const struct BigMapEntry *bme) +{ + for (unsigned int i=0;inext_cache_off;i++) + if (map->next_cache[i].bme == bme) + map->next_cache[i].bme = bme->next; +} + + +/** + * We are about to free() the @a sme, 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 sme the entry that is about to be free'd + */ +static void +update_next_cache_sme (struct GNUNET_CONTAINER_MultiHashMap *map, + const struct SmallMapEntry *sme) +{ + for (unsigned int i=0;inext_cache_off;i++) + if (map->next_cache[i].sme == sme) + map->next_cache[i].sme = sme->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 @@ -409,19 +479,22 @@ GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map, me = map->map[i]; if (map->use_small_entries) { - struct SmallMapEntry *sme; struct SmallMapEntry *p; p = NULL; - for (sme = me.sme; NULL != sme; sme = sme->next) + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) { - if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) && - (value == sme->value)) + if ( (0 == memcmp (key, + sme->key, + sizeof (struct GNUNET_HashCode))) && + (value == sme->value) ) { if (NULL == p) map->map[i].sme = sme->next; else p->next = sme->next; + update_next_cache_sme (map, + sme); GNUNET_free (sme); map->size--; return GNUNET_YES; @@ -431,19 +504,22 @@ GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map, } else { - struct BigMapEntry *bme; struct BigMapEntry *p; p = NULL; - for (bme = me.bme; NULL != bme; bme = bme->next) + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) { - if ((0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) && - (value == bme->value)) + if ( (0 == memcmp (key, + &bme->key, + sizeof (struct GNUNET_HashCode))) && + (value == bme->value) ) { if (NULL == p) map->map[i].bme = bme->next; else p->next = bme->next; + update_next_cache_bme (map, + bme); GNUNET_free (bme); map->size--; return GNUNET_YES; @@ -485,12 +561,16 @@ GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap * sme = me.sme; while (NULL != sme) { - if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) + if (0 == memcmp (key, + sme->key, + sizeof (struct GNUNET_HashCode))) { if (NULL == p) map->map[i].sme = sme->next; else p->next = sme->next; + update_next_cache_sme (map, + sme); GNUNET_free (sme); map->size--; if (NULL == p) @@ -515,12 +595,16 @@ GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap * bme = me.bme; while (NULL != bme) { - if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) + if (0 == memcmp (key, + &bme->key, + sizeof (struct GNUNET_HashCode))) { if (NULL == p) map->map[i].bme = bme->next; else p->next = bme->next; + update_next_cache_bme (map, + bme); GNUNET_free (bme); map->size--; if (NULL == p) @@ -631,9 +715,8 @@ GNUNET_CONTAINER_multihashmap_contains (const struct * #GNUNET_NO if not */ int -GNUNET_CONTAINER_multihashmap_contains_value (const struct - GNUNET_CONTAINER_MultiHashMap - *map, const struct GNUNET_HashCode *key, +GNUNET_CONTAINER_multihashmap_contains_value (const struct GNUNET_CONTAINER_MultiHashMap *map, + const struct GNUNET_HashCode *key, const void *value) { union MapEntry me; @@ -644,7 +727,9 @@ GNUNET_CONTAINER_multihashmap_contains_value (const struct struct SmallMapEntry *sme; for (sme = me.sme; NULL != sme; sme = sme->next) - if ( (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) && + if ( (0 == memcmp (key, + sme->key, + sizeof (struct GNUNET_HashCode))) && (sme->value == value) ) return GNUNET_YES; } @@ -653,7 +738,9 @@ GNUNET_CONTAINER_multihashmap_contains_value (const struct struct BigMapEntry *bme; for (bme = me.bme; NULL != bme; bme = bme->next) - if ( (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) && + if ( (0 == memcmp (key, + &bme->key, + sizeof (struct GNUNET_HashCode))) && (bme->value == value) ) return GNUNET_YES; } @@ -814,49 +901,66 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, * #GNUNET_SYSERR if it aborted iteration */ int -GNUNET_CONTAINER_multihashmap_get_multiple (const struct - GNUNET_CONTAINER_MultiHashMap *map, +GNUNET_CONTAINER_multihashmap_get_multiple (struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, GNUNET_CONTAINER_HashMapIterator it, void *it_cls) { int count; - union MapEntry me; + union MapEntry *me; + union MapEntry *ce; + ce = &map->next_cache[map->next_cache_off]; + GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); count = 0; - me = map->map[idx_of (map, key)]; + me = &map->map[idx_of (map, key)]; if (map->use_small_entries) { struct SmallMapEntry *sme; - struct SmallMapEntry *nxt; - nxt = me.sme; - while (NULL != (sme = nxt)) + ce->sme = me->sme; + while (NULL != (sme = ce->sme)) { - nxt = sme->next; - if (0 != memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) + ce->sme = sme->next; + if (0 != memcmp (key, + sme->key, + sizeof (struct GNUNET_HashCode))) continue; - if ((it != NULL) && (GNUNET_OK != it (it_cls, key, sme->value))) + if ( (NULL != it) && + (GNUNET_OK != it (it_cls, + key, + sme->value))) + { + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return GNUNET_SYSERR; + } count++; } } else { struct BigMapEntry *bme; - struct BigMapEntry *nxt; - nxt = me.bme; - while (NULL != (bme = nxt)) + ce->bme = me->bme; + while (NULL != (bme = ce->bme)) { - nxt = bme->next; - if (0 != memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) + ce->bme = bme->next; + if (0 != memcmp (key, + &bme->key, + sizeof (struct GNUNET_HashCode))) continue; - if ((it != NULL) && (GNUNET_OK != it (it_cls, key, bme->value))) + if ( (NULL != it) && + (GNUNET_OK != it (it_cls, + key, + bme->value))) + { + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return GNUNET_SYSERR; + } count++; } } + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return count; } 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) diff --git a/src/util/container_multipeermap.c b/src/util/container_multipeermap.c index ede2fd8b7..67d6e1684 100644 --- a/src/util/container_multipeermap.c +++ b/src/util/container_multipeermap.c @@ -26,6 +26,14 @@ #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multipeermap", __VA_ARGS__) +/** + * Maximum recursion depth for callbacks of + * #GNUNET_CONTAINER_multihashmap_get_multiple() themselve s + * 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 with the full key. */ @@ -112,8 +120,8 @@ struct GNUNET_CONTAINER_MultiPeerMap unsigned int map_length; /** - * GNUNET_NO if the map entries are of type 'struct BigMapEntry', - * GNUNET_YES if the map entries are of type 'struct SmallMapEntry'. + * #GNUNET_NO if the map entries are of type 'struct BigMapEntry', + * #GNUNET_YES if the map entries are of type 'struct SmallMapEntry'. */ int use_small_entries; @@ -122,6 +130,19 @@ struct GNUNET_CONTAINER_MultiPeerMap * 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. + */ + union 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; }; @@ -177,7 +198,8 @@ GNUNET_CONTAINER_multipeermap_create (unsigned int len, GNUNET_assert (len > 0); map = GNUNET_new (struct GNUNET_CONTAINER_MultiPeerMap); - map->map = GNUNET_malloc (len * sizeof (union MapEntry)); + map->map = GNUNET_new_array (len, + union MapEntry); map->map_length = len; map->use_small_entries = do_not_copy_keys; return map; @@ -191,14 +213,13 @@ GNUNET_CONTAINER_multipeermap_create (unsigned int len, * @param map the map */ void -GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap - *map) +GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap *map) { - unsigned int i; - union MapEntry me; - - for (i = 0; i < map->map_length; i++) + GNUNET_assert (0 == map->next_cache_off); + for (unsigned int i = 0; i < map->map_length; i++) { + union MapEntry me; + me = map->map[i]; if (map->use_small_entries) { @@ -246,7 +267,9 @@ idx_of (const struct GNUNET_CONTAINER_MultiPeerMap *map, unsigned int kx; GNUNET_assert (NULL != map); - GNUNET_memcpy (&kx, key, sizeof (kx)); + GNUNET_memcpy (&kx, + key, + sizeof (kx)); return kx % map->map_length; } @@ -258,8 +281,7 @@ idx_of (const struct GNUNET_CONTAINER_MultiPeerMap *map, * @return the number of key value pairs */ unsigned int -GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap - *map) +GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap *map) { return map->size; } @@ -276,26 +298,26 @@ GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap * key-value pairs with value NULL */ void * -GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap - *map, const struct GNUNET_PeerIdentity *key) +GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap *map, + const struct GNUNET_PeerIdentity *key) { union MapEntry me; me = map->map[idx_of (map, key)]; if (map->use_small_entries) { - struct SmallMapEntry *sme; - - for (sme = me.sme; NULL != sme; sme = sme->next) - if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) + if (0 == memcmp (key, + sme->key, + sizeof (struct GNUNET_PeerIdentity))) return sme->value; } else { - struct BigMapEntry *bme; - - for (bme = me.bme; NULL != bme; bme = bme->next) - if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) + if (0 == memcmp (key, + &bme->key, + sizeof (struct GNUNET_PeerIdentity))) return bme->value; } return NULL; @@ -312,34 +334,39 @@ GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap * #GNUNET_SYSERR if it aborted iteration */ int -GNUNET_CONTAINER_multipeermap_iterate (const struct - GNUNET_CONTAINER_MultiPeerMap *map, +GNUNET_CONTAINER_multipeermap_iterate (struct GNUNET_CONTAINER_MultiPeerMap *map, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls) { int count; - unsigned int i; union MapEntry me; + union MapEntry *ce; struct GNUNET_PeerIdentity kc; 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++) { me = map->map[i]; if (map->use_small_entries) { struct SmallMapEntry *sme; - struct SmallMapEntry *nxt; - nxt = me.sme; - while (NULL != (sme = nxt)) + ce->sme = me.sme; + while (NULL != (sme = ce->sme)) { - nxt = sme->next; + ce->sme = sme->next; if (NULL != it) { - if (GNUNET_OK != it (it_cls, sme->key, sme->value)) + if (GNUNET_OK != it (it_cls, + sme->key, + sme->value)) + { + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return GNUNET_SYSERR; + } } count++; } @@ -347,26 +374,65 @@ GNUNET_CONTAINER_multipeermap_iterate (const struct else { struct BigMapEntry *bme; - struct BigMapEntry *nxt; - nxt = me.bme; - while (NULL != (bme = nxt)) + ce->bme = me.bme; + while (NULL != (bme = ce->bme)) { - nxt = bme->next; + ce->bme = bme->next; if (NULL != it) { kc = bme->key; - if (GNUNET_OK != it (it_cls, &kc, bme->value)) + if (GNUNET_OK != it (it_cls, + &kc, + bme->value)) + { + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return GNUNET_SYSERR; + } } count++; } } } + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return count; } +/** + * 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_bme (struct GNUNET_CONTAINER_MultiPeerMap *map, + const struct BigMapEntry *bme) +{ + for (unsigned int i=0;inext_cache_off;i++) + if (map->next_cache[i].bme == bme) + map->next_cache[i].bme = bme->next; +} + + +/** + * We are about to free() the @a sme, 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 sme the entry that is about to be free'd + */ +static void +update_next_cache_sme (struct GNUNET_CONTAINER_MultiPeerMap *map, + const struct SmallMapEntry *sme) +{ + for (unsigned int i=0;inext_cache_off;i++) + if (map->next_cache[i].sme == sme) + map->next_cache[i].sme = sme->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 @@ -375,7 +441,7 @@ GNUNET_CONTAINER_multipeermap_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 @@ -387,16 +453,13 @@ GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, unsigned int i; map->modification_counter++; - i = idx_of (map, key); me = map->map[i]; if (map->use_small_entries) { - struct SmallMapEntry *sme; - struct SmallMapEntry *p; + struct SmallMapEntry *p = NULL; - p = NULL; - for (sme = me.sme; NULL != sme; sme = sme->next) + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) { if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) && (value == sme->value)) @@ -405,6 +468,8 @@ GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, map->map[i].sme = sme->next; else p->next = sme->next; + update_next_cache_sme (map, + sme); GNUNET_free (sme); map->size--; return GNUNET_YES; @@ -414,19 +479,21 @@ GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, } else { - struct BigMapEntry *bme; - struct BigMapEntry *p; + struct BigMapEntry *p = NULL; - p = NULL; - for (bme = me.bme; NULL != bme; bme = bme->next) + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) { - if ((0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) && + if ((0 == memcmp (key, + &bme->key, + sizeof (struct GNUNET_PeerIdentity))) && (value == bme->value)) { if (NULL == p) map->map[i].bme = bme->next; else - p->next = bme->next; + p->next = bme->next; + update_next_cache_bme (map, + bme); GNUNET_free (bme); map->size--; return GNUNET_YES; @@ -447,8 +514,8 @@ GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, * @return number of values removed */ int -GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap - *map, const struct GNUNET_PeerIdentity *key) +GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap *map, + const struct GNUNET_PeerIdentity *key) { union MapEntry me; unsigned int i; @@ -468,12 +535,16 @@ GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap sme = me.sme; while (NULL != sme) { - if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) + if (0 == memcmp (key, + sme->key, + sizeof (struct GNUNET_PeerIdentity))) { if (NULL == p) map->map[i].sme = sme->next; else p->next = sme->next; + update_next_cache_sme (map, + sme); GNUNET_free (sme); map->size--; if (NULL == p) @@ -498,12 +569,16 @@ GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap bme = me.bme; while (NULL != bme) { - if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) + if (0 == memcmp (key, + &bme->key, + sizeof (struct GNUNET_PeerIdentity))) { if (NULL == p) map->map[i].bme = bme->next; else p->next = bme->next; + update_next_cache_bme (map, + bme); GNUNET_free (bme); map->size--; if (NULL == p) @@ -529,12 +604,11 @@ GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap * * @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_multipeermap_contains (const struct - GNUNET_CONTAINER_MultiPeerMap *map, +GNUNET_CONTAINER_multipeermap_contains (const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key) { union MapEntry me; @@ -542,17 +616,13 @@ GNUNET_CONTAINER_multipeermap_contains (const struct me = map->map[idx_of (map, key)]; if (map->use_small_entries) { - struct SmallMapEntry *sme; - - for (sme = me.sme; NULL != sme; sme = sme->next) + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) return GNUNET_YES; } else { - struct BigMapEntry *bme; - - for (bme = me.bme; NULL != bme; bme = bme->next) + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) return GNUNET_YES; } @@ -567,13 +637,12 @@ GNUNET_CONTAINER_multipeermap_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_multipeermap_contains_value (const struct - GNUNET_CONTAINER_MultiPeerMap - *map, const struct GNUNET_PeerIdentity *key, +GNUNET_CONTAINER_multipeermap_contains_value (const struct GNUNET_CONTAINER_MultiPeerMap *map, + const struct GNUNET_PeerIdentity *key, const void *value) { union MapEntry me; @@ -581,19 +650,19 @@ GNUNET_CONTAINER_multipeermap_contains_value (const struct me = map->map[idx_of (map, key)]; if (map->use_small_entries) { - struct SmallMapEntry *sme; - - for (sme = me.sme; NULL != sme; sme = sme->next) - if ( (0 == memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) && + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) + if ( (0 == memcmp (key, + sme->key, + sizeof (struct GNUNET_PeerIdentity))) && (sme->value == value) ) return GNUNET_YES; } else { - struct BigMapEntry *bme; - - for (bme = me.bme; NULL != bme; bme = bme->next) - if ( (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) && + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) + if ( (0 == memcmp (key, + &bme->key, + sizeof (struct GNUNET_PeerIdentity))) && (bme->value == value) ) return GNUNET_YES; } @@ -621,7 +690,8 @@ grow (struct GNUNET_CONTAINER_MultiPeerMap *map) old_map = map->map; old_len = map->map_length; new_len = old_len * 2; - new_map = GNUNET_malloc (sizeof (union MapEntry) * new_len); + new_map = GNUNET_new_array (new_len, + union MapEntry); map->map_length = new_len; map->map = new_map; for (i = 0; i < old_len; i++) @@ -664,7 +734,7 @@ grow (struct GNUNET_CONTAINER_MultiPeerMap *map) * @param opt options for put * @return #GNUNET_OK on success, * #GNUNET_NO if a value was replaced (with REPLACE) - * #GNUNET_SYSERR if GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the + * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the * value already exists */ int @@ -749,48 +819,66 @@ GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map, * #GNUNET_SYSERR if it aborted iteration */ int -GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiPeerMap *map, +GNUNET_CONTAINER_multipeermap_get_multiple (struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls) { int count; union MapEntry me; - + union MapEntry *ce; + + ce = &map->next_cache[map->next_cache_off]; + GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); count = 0; me = map->map[idx_of (map, key)]; if (map->use_small_entries) { struct SmallMapEntry *sme; - struct SmallMapEntry *nxt; - nxt = me.sme; - while (NULL != (sme = nxt)) + ce->sme = me.sme; + while (NULL != (sme = ce->sme)) { - nxt = sme->next; - if (0 != memcmp (key, sme->key, sizeof (struct GNUNET_PeerIdentity))) + ce->sme = sme->next; + if (0 != memcmp (key, + sme->key, + sizeof (struct GNUNET_PeerIdentity))) continue; - if ((it != NULL) && (GNUNET_OK != it (it_cls, key, sme->value))) + if ( (NULL != it) && + (GNUNET_OK != it (it_cls, + key, + sme->value))) + { + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return GNUNET_SYSERR; + } count++; } } else { struct BigMapEntry *bme; - struct BigMapEntry *nxt; - nxt = me.bme; - while (NULL != (bme = nxt)) + ce->bme = me.bme; + while (NULL != (bme = ce->bme)) { - nxt = bme->next; - if (0 != memcmp (key, &bme->key, sizeof (struct GNUNET_PeerIdentity))) + ce->bme = bme->next; + if (0 != memcmp (key, + &bme->key, + sizeof (struct GNUNET_PeerIdentity))) continue; - if ((it != NULL) && (GNUNET_OK != it (it_cls, key, bme->value))) + if ( (NULL != it) && + (GNUNET_OK != it (it_cls, + key, + bme->value))) + { + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return GNUNET_SYSERR; + } count++; } } + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return count; } @@ -812,16 +900,15 @@ GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPee void *it_cls) { unsigned int off; - unsigned int idx; union MapEntry me; - + if (0 == map->size) return 0; if (NULL == it) return 1; off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, map->size); - for (idx = 0; idx < map->map_length; idx++) + for (unsigned int idx = 0; idx < map->map_length; idx++) { me = map->map[idx]; if (map->use_small_entries) @@ -856,9 +943,10 @@ GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPee if (0 == off) { if (GNUNET_OK != it (it_cls, - &bme->key, bme->value)) - return GNUNET_SYSERR; - return 1; + &bme->key, + bme->value)) + return GNUNET_SYSERR; + return 1; } off--; } diff --git a/src/util/container_multishortmap.c b/src/util/container_multishortmap.c index f815b6238..050fd21f9 100644 --- a/src/util/container_multishortmap.c +++ b/src/util/container_multishortmap.c @@ -26,6 +26,15 @@ #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multishortmap", __VA_ARGS__) +/** + * Maximum recursion depth for callbacks of + * #GNUNET_CONTAINER_multihashmap_get_multiple() themselve s + * 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 with the full key. */ @@ -112,8 +121,8 @@ struct GNUNET_CONTAINER_MultiShortmap unsigned int map_length; /** - * GNUNET_NO if the map entries are of type 'struct BigMapEntry', - * GNUNET_YES if the map entries are of type 'struct SmallMapEntry'. + * #GNUNET_NO if the map entries are of type 'struct BigMapEntry', + * #GNUNET_YES if the map entries are of type 'struct SmallMapEntry'. */ int use_small_entries; @@ -122,6 +131,20 @@ struct GNUNET_CONTAINER_MultiShortmap * 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. + */ + union 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; + }; @@ -177,7 +200,8 @@ GNUNET_CONTAINER_multishortmap_create (unsigned int len, GNUNET_assert (len > 0); map = GNUNET_new (struct GNUNET_CONTAINER_MultiShortmap); - map->map = GNUNET_malloc (len * sizeof (union MapEntry)); + map->map = GNUNET_new_array (len, + union MapEntry); map->map_length = len; map->use_small_entries = do_not_copy_keys; return map; @@ -191,14 +215,13 @@ GNUNET_CONTAINER_multishortmap_create (unsigned int len, * @param map the map */ void -GNUNET_CONTAINER_multishortmap_destroy (struct GNUNET_CONTAINER_MultiShortmap - *map) +GNUNET_CONTAINER_multishortmap_destroy (struct GNUNET_CONTAINER_MultiShortmap *map) { - unsigned int i; - union MapEntry me; - - for (i = 0; i < map->map_length; i++) + GNUNET_assert (0 == map->next_cache_off); + for (unsigned int i = 0; i < map->map_length; i++) { + union MapEntry me; + me = map->map[i]; if (map->use_small_entries) { @@ -283,18 +306,18 @@ GNUNET_CONTAINER_multishortmap_get (const struct GNUNET_CONTAINER_MultiShortmap me = map->map[idx_of (map, key)]; if (map->use_small_entries) { - struct SmallMapEntry *sme; - - for (sme = me.sme; NULL != sme; sme = sme->next) - if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode))) + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) + if (0 == memcmp (key, + sme->key, + sizeof (struct GNUNET_ShortHashCode))) return sme->value; } else { - struct BigMapEntry *bme; - - for (bme = me.bme; NULL != bme; bme = bme->next) - if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode))) + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) + if (0 == memcmp (key, + &bme->key, + sizeof (struct GNUNET_ShortHashCode))) return bme->value; } return NULL; @@ -311,33 +334,37 @@ GNUNET_CONTAINER_multishortmap_get (const struct GNUNET_CONTAINER_MultiShortmap * #GNUNET_SYSERR if it aborted iteration */ int -GNUNET_CONTAINER_multishortmap_iterate (const struct GNUNET_CONTAINER_MultiShortmap *map, - GNUNET_CONTAINER_ShortmapIterator it, - void *it_cls) +GNUNET_CONTAINER_multishortmap_iterate (struct GNUNET_CONTAINER_MultiShortmap *map, + GNUNET_CONTAINER_ShortmapIterator it, + void *it_cls) { int count; - unsigned int i; union MapEntry me; + union MapEntry *ce; struct GNUNET_ShortHashCode kc; 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++) { me = map->map[i]; if (map->use_small_entries) { struct SmallMapEntry *sme; - struct SmallMapEntry *nxt; - - nxt = me.sme; - while (NULL != (sme = nxt)) + + ce->sme = me.sme; + while (NULL != (sme = ce->sme)) { - nxt = sme->next; - if (NULL != it) + ce->sme = sme->next; + if ( (NULL != it) && + (GNUNET_OK != it (it_cls, + sme->key, + sme->value)) ) { - if (GNUNET_OK != it (it_cls, sme->key, sme->value)) - return GNUNET_SYSERR; + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); + return GNUNET_SYSERR; } count++; } @@ -345,26 +372,65 @@ GNUNET_CONTAINER_multishortmap_iterate (const struct GNUNET_CONTAINER_MultiShort else { struct BigMapEntry *bme; - struct BigMapEntry *nxt; - nxt = me.bme; - while (NULL != (bme = nxt)) + ce->bme = me.bme; + while (NULL != (bme = ce->bme)) { - nxt = bme->next; + ce->bme = bme->next; if (NULL != it) { kc = bme->key; - if (GNUNET_OK != it (it_cls, &kc, bme->value)) + if (GNUNET_OK != it (it_cls, + &kc, + bme->value)) + { + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return GNUNET_SYSERR; + } } count++; } } } + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return count; } +/** + * 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_bme (struct GNUNET_CONTAINER_MultiShortmap *map, + const struct BigMapEntry *bme) +{ + for (unsigned int i=0;inext_cache_off;i++) + if (map->next_cache[i].bme == bme) + map->next_cache[i].bme = bme->next; +} + + +/** + * We are about to free() the @a sme, 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 sme the entry that is about to be free'd + */ +static void +update_next_cache_sme (struct GNUNET_CONTAINER_MultiShortmap *map, + const struct SmallMapEntry *sme) +{ + for (unsigned int i=0;inext_cache_off;i++) + if (map->next_cache[i].sme == sme) + map->next_cache[i].sme = sme->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 @@ -385,24 +451,25 @@ GNUNET_CONTAINER_multishortmap_remove (struct GNUNET_CONTAINER_MultiShortmap *ma unsigned int i; map->modification_counter++; - i = idx_of (map, key); me = map->map[i]; if (map->use_small_entries) { - struct SmallMapEntry *sme; - struct SmallMapEntry *p; - - p = NULL; - for (sme = me.sme; NULL != sme; sme = sme->next) + struct SmallMapEntry *p = NULL; + + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) { - if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode))) && + if ((0 == memcmp (key, + sme->key, + sizeof (struct GNUNET_ShortHashCode))) && (value == sme->value)) { if (NULL == p) map->map[i].sme = sme->next; else p->next = sme->next; + update_next_cache_sme (map, + sme); GNUNET_free (sme); map->size--; return GNUNET_YES; @@ -412,19 +479,21 @@ GNUNET_CONTAINER_multishortmap_remove (struct GNUNET_CONTAINER_MultiShortmap *ma } else { - struct BigMapEntry *bme; - struct BigMapEntry *p; - - p = NULL; - for (bme = me.bme; NULL != bme; bme = bme->next) + struct BigMapEntry *p = NULL; + + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) { - if ((0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode))) && + if ((0 == memcmp (key, + &bme->key, + sizeof (struct GNUNET_ShortHashCode))) && (value == bme->value)) { if (NULL == p) map->map[i].bme = bme->next; else p->next = bme->next; + update_next_cache_bme (map, + bme); GNUNET_free (bme); map->size--; return GNUNET_YES; @@ -472,6 +541,8 @@ GNUNET_CONTAINER_multishortmap_remove_all (struct GNUNET_CONTAINER_MultiShortmap map->map[i].sme = sme->next; else p->next = sme->next; + update_next_cache_sme (map, + sme); GNUNET_free (sme); map->size--; if (NULL == p) @@ -502,6 +573,8 @@ GNUNET_CONTAINER_multishortmap_remove_all (struct GNUNET_CONTAINER_MultiShortmap map->map[i].bme = bme->next; else p->next = bme->next; + update_next_cache_bme (map, + bme); GNUNET_free (bme); map->size--; if (NULL == p) @@ -539,18 +612,18 @@ GNUNET_CONTAINER_multishortmap_contains (const struct GNUNET_CONTAINER_MultiShor me = map->map[idx_of (map, key)]; if (map->use_small_entries) { - struct SmallMapEntry *sme; - - for (sme = me.sme; NULL != sme; sme = sme->next) - if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode))) + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) + if (0 == memcmp (key, + sme->key, + sizeof (struct GNUNET_ShortHashCode))) return GNUNET_YES; } else { - struct BigMapEntry *bme; - - for (bme = me.bme; NULL != bme; bme = bme->next) - if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode))) + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) + if (0 == memcmp (key, + &bme->key, + sizeof (struct GNUNET_ShortHashCode))) return GNUNET_YES; } return GNUNET_NO; @@ -577,19 +650,19 @@ GNUNET_CONTAINER_multishortmap_contains_value (const struct GNUNET_CONTAINER_Mul me = map->map[idx_of (map, key)]; if (map->use_small_entries) { - struct SmallMapEntry *sme; - - for (sme = me.sme; NULL != sme; sme = sme->next) - if ( (0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode))) && + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) + if ( (0 == memcmp (key, + sme->key, + sizeof (struct GNUNET_ShortHashCode))) && (sme->value == value) ) return GNUNET_YES; } else { - struct BigMapEntry *bme; - - for (bme = me.bme; NULL != bme; bme = bme->next) - if ( (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode))) && + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) + if ( (0 == memcmp (key, + &bme->key, + sizeof (struct GNUNET_ShortHashCode))) && (bme->value == value) ) return GNUNET_YES; } @@ -610,17 +683,17 @@ grow (struct GNUNET_CONTAINER_MultiShortmap *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 (union MapEntry) * new_len); + new_map = GNUNET_new_array (new_len, + union 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++) { if (map->use_small_entries) { @@ -660,7 +733,7 @@ grow (struct GNUNET_CONTAINER_MultiShortmap *map) * @param opt options for put * @return #GNUNET_OK on success, * #GNUNET_NO if a value was replaced (with REPLACE) - * #GNUNET_SYSERR if GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the + * #GNUNET_SYSERR if #GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY was the option and the * value already exists */ int @@ -679,10 +752,10 @@ GNUNET_CONTAINER_multishortmap_put (struct GNUNET_CONTAINER_MultiShortmap *map, me = map->map[i]; if (map->use_small_entries) { - struct SmallMapEntry *sme; - - for (sme = me.sme; NULL != sme; sme = sme->next) - if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode))) + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) + if (0 == memcmp (key, + sme->key, + sizeof (struct GNUNET_ShortHashCode))) { if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) return GNUNET_SYSERR; @@ -692,10 +765,10 @@ GNUNET_CONTAINER_multishortmap_put (struct GNUNET_CONTAINER_MultiShortmap *map, } else { - struct BigMapEntry *bme; - - for (bme = me.bme; NULL != bme; bme = bme->next) - if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode))) + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) + if (0 == memcmp (key, + &bme->key, + sizeof (struct GNUNET_ShortHashCode))) { if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) return GNUNET_SYSERR; @@ -745,48 +818,66 @@ GNUNET_CONTAINER_multishortmap_put (struct GNUNET_CONTAINER_MultiShortmap *map, * #GNUNET_SYSERR if it aborted iteration */ int -GNUNET_CONTAINER_multishortmap_get_multiple (const struct GNUNET_CONTAINER_MultiShortmap *map, +GNUNET_CONTAINER_multishortmap_get_multiple (struct GNUNET_CONTAINER_MultiShortmap *map, const struct GNUNET_ShortHashCode *key, GNUNET_CONTAINER_ShortmapIterator it, void *it_cls) { int count; union MapEntry me; + union MapEntry *ce; + ce = &map->next_cache[map->next_cache_off]; + GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE); count = 0; me = map->map[idx_of (map, key)]; if (map->use_small_entries) { struct SmallMapEntry *sme; - struct SmallMapEntry *nxt; - nxt = me.sme; - while (NULL != (sme = nxt)) + ce->sme = me.sme; + while (NULL != (sme = ce->sme)) { - nxt = sme->next; - if (0 != memcmp (key, sme->key, sizeof (struct GNUNET_ShortHashCode))) + ce->sme = sme->next; + if (0 != memcmp (key, + sme->key, + sizeof (struct GNUNET_ShortHashCode))) continue; - if ((it != NULL) && (GNUNET_OK != it (it_cls, key, sme->value))) + if ( (NULL != it) && + (GNUNET_OK != it (it_cls, + key, + sme->value)) ) + { + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return GNUNET_SYSERR; + } count++; } } else { struct BigMapEntry *bme; - struct BigMapEntry *nxt; - nxt = me.bme; - while (NULL != (bme = nxt)) + ce->bme = me.bme; + while (NULL != (bme = ce->bme)) { - nxt = bme->next; - if (0 != memcmp (key, &bme->key, sizeof (struct GNUNET_ShortHashCode))) + ce->bme = bme->next; + if (0 != memcmp (key, + &bme->key, + sizeof (struct GNUNET_ShortHashCode))) continue; - if ((it != NULL) && (GNUNET_OK != it (it_cls, key, bme->value))) + if ( (NULL != it) && + (GNUNET_OK != it (it_cls, + key, + bme->value)) ) + { + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return GNUNET_SYSERR; + } count++; } } + GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE); return count; } @@ -808,7 +899,6 @@ GNUNET_CONTAINER_multishortmap_get_random (const struct GNUNET_CONTAINER_MultiSh void *it_cls) { unsigned int off; - unsigned int idx; union MapEntry me; if (0 == map->size) @@ -817,18 +907,13 @@ GNUNET_CONTAINER_multishortmap_get_random (const struct GNUNET_CONTAINER_MultiSh return 1; off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, map->size); - for (idx = 0; idx < map->map_length; idx++) + for (unsigned int idx = 0; idx < map->map_length; idx++) { me = map->map[idx]; if (map->use_small_entries) { - struct SmallMapEntry *sme; - struct SmallMapEntry *nxt; - - nxt = me.sme; - while (NULL != (sme = nxt)) + for (struct SmallMapEntry *sme = me.sme; NULL != sme; sme = sme->next) { - nxt = sme->next; if (0 == off) { if (GNUNET_OK != it (it_cls, @@ -842,13 +927,8 @@ GNUNET_CONTAINER_multishortmap_get_random (const struct GNUNET_CONTAINER_MultiSh } else { - struct BigMapEntry *bme; - struct BigMapEntry *nxt; - - nxt = me.bme; - while (NULL != (bme = nxt)) + for (struct BigMapEntry *bme = me.bme; NULL != bme; bme = bme->next) { - nxt = bme->next; if (0 == off) { if (GNUNET_OK != it (it_cls, -- cgit v1.2.3