X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Futil%2Fcontainer_multihashmap.c;h=46379b34efe2d8a62f029863423a1c98715ac7d4;hb=93fba12ad8159dc6b683f9e7ce9f0528a11047f5;hp=a23f96798374d37d9b2a710a7efe1c8a092efb69;hpb=dbb1cc93b76cae5145847da04d83851d460325b1;p=oweals%2Fgnunet.git diff --git a/src/util/container_multihashmap.c b/src/util/container_multihashmap.c index a23f96798..46379b34e 100644 --- a/src/util/container_multihashmap.c +++ b/src/util/container_multihashmap.c @@ -1,10 +1,10 @@ /* This file is part of GNUnet. - (C) 2008, 2012 Christian Grothoff (and other contributing authors) + Copyright (C) 2008, 2012 Christian Grothoff (and other contributing authors) GNUnet is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published - by the Free Software Foundation; either version 2, or (at your + by the Free Software Foundation; either version 3, or (at your option) any later version. GNUnet is distributed in the hope that it will be useful, but @@ -24,9 +24,7 @@ */ #include "platform.h" -#include "gnunet_common.h" #include "gnunet_container_lib.h" -#include "gnunet_crypto_lib.h" #define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__) @@ -69,7 +67,7 @@ struct SmallMapEntry * If there is a hash collision, we create a linked list. */ struct SmallMapEntry *next; - + /** * Key for the entry. */ @@ -100,7 +98,6 @@ union MapEntry */ struct GNUNET_CONTAINER_MultiHashMap { - /** * All of our buckets. */ @@ -117,10 +114,45 @@ struct GNUNET_CONTAINER_MultiHashMap 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; + + /** + * Counts the destructive modifications (grow, remove) + * to the map, so that iterators can check if they are still valid. + */ + unsigned int modification_counter; +}; + + +/** + * Cursor into a multihashmap. + * Allows to enumerate elements asynchronously. + */ +struct GNUNET_CONTAINER_MultiHashMapIterator +{ + /** + * Position in the bucket 'idx' + */ + union MapEntry me; + + /** + * Current bucket index. + */ + unsigned int idx; + + /** + * Modification counter as observed on the map when the iterator + * was created. + */ + unsigned int modification_counter; + + /** + * Map that we are iterating over. + */ + const struct GNUNET_CONTAINER_MultiHashMap *map; }; @@ -128,12 +160,12 @@ struct GNUNET_CONTAINER_MultiHashMap * Create a multi hash map. * * @param len initial size (map will grow as needed) - * @param do_not_copy_keys GNUNET_NO is always safe and should be used by default; - * GNUNET_YES means that on 'put', the 'key' does not have - * to be copied as the destination of the pointer is + * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default; + * #GNUNET_YES means that on 'put', the 'key' does not have + * to be copied as the destination of the pointer is * guaranteed to be life as long as the value is stored in - * the hashmap. This can significantly reduce memory - * consumption, but of course is also a recipie for + * the hashmap. This can significantly reduce memory + * consumption, but of course is also a recipie for * heap corruption if the assumption is not true. Only * use this if (1) memory use is important in this case and * (2) you have triple-checked that the invariant holds @@ -146,7 +178,7 @@ GNUNET_CONTAINER_multihashmap_create (unsigned int len, struct GNUNET_CONTAINER_MultiHashMap *map; GNUNET_assert (len > 0); - map = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_MultiHashMap)); + map = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap); map->map = GNUNET_malloc (len * sizeof (union MapEntry)); map->map_length = len; map->use_small_entries = do_not_copy_keys; @@ -243,8 +275,8 @@ GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap * key-value pairs with value NULL */ void * -GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap - *map, const struct GNUNET_HashCode *key) +GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap *map, + const struct GNUNET_HashCode *key) { union MapEntry me; @@ -274,9 +306,9 @@ GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap * * @param map the map * @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 + * #GNUNET_SYSERR if it aborted iteration */ int GNUNET_CONTAINER_multihashmap_iterate (const struct @@ -299,7 +331,7 @@ GNUNET_CONTAINER_multihashmap_iterate (const struct struct SmallMapEntry *sme; struct SmallMapEntry *nxt; - nxt = me.sme; + nxt = me.sme; while (NULL != (sme = nxt)) { nxt = sme->next; @@ -316,7 +348,7 @@ GNUNET_CONTAINER_multihashmap_iterate (const struct struct BigMapEntry *bme; struct BigMapEntry *nxt; - nxt = me.bme; + nxt = me.bme; while (NULL != (bme = nxt)) { nxt = bme->next; @@ -342,21 +374,23 @@ GNUNET_CONTAINER_multihashmap_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_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map, - const struct GNUNET_HashCode *key, - void *value) + const struct GNUNET_HashCode *key, + const void *value) { union MapEntry me; 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; @@ -412,18 +446,20 @@ GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map, * @return number of values removed */ int -GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap - *map, const struct GNUNET_HashCode *key) +GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap *map, + const struct GNUNET_HashCode *key) { union MapEntry me; unsigned int i; int ret; + map->modification_counter++; + ret = 0; i = idx_of (map, key); me = map->map[i]; if (map->use_small_entries) - { + { struct SmallMapEntry *sme; struct SmallMapEntry *p; @@ -443,7 +479,7 @@ GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap sme = map->map[i].sme; else sme = p->next; - ret++; + ret++; } else { @@ -486,14 +522,57 @@ GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap } +/** + * Callback used to remove all entries from the map. + * + * @param cls the `struct GNUNET_CONTAINER_MultiHashMap` + * @param key the key + * @param value the value + * @return #GNUNET_OK (continue to iterate) + */ +static int +remove_all (void *cls, + const struct GNUNET_HashCode *key, + void *value) +{ + struct GNUNET_CONTAINER_MultiHashMap *map = cls; + + GNUNET_CONTAINER_multihashmap_remove (map, + key, + value); + return GNUNET_OK; +} + + +/** + * @ingroup hashmap + * Remove all entries from the map. + * Note that the values would not be "freed". + * + * @param map the map + * @return number of values removed + */ +unsigned int +GNUNET_CONTAINER_multihashmap_clear (struct GNUNET_CONTAINER_MultiHashMap *map) +{ + unsigned int ret; + + ret = map->size; + GNUNET_CONTAINER_multihashmap_iterate (map, + &remove_all, + map); + return ret; +} + + /** * Check if the map contains any value under the given * key (including values that are NULL). * * @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_multihashmap_contains (const struct @@ -530,8 +609,8 @@ GNUNET_CONTAINER_multihashmap_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_multihashmap_contains_value (const struct @@ -579,6 +658,8 @@ grow (struct GNUNET_CONTAINER_MultiHashMap *map) unsigned int idx; unsigned int i; + map->modification_counter++; + old_map = map->map; old_len = map->map_length; new_len = old_len * 2; @@ -604,7 +685,7 @@ grow (struct GNUNET_CONTAINER_MultiHashMap *map) struct BigMapEntry *bme; while (NULL != (bme = old_map[i].bme)) - { + { old_map[i].bme = bme->next; idx = idx_of (map, &bme->key); bme->next = new_map[idx].bme; @@ -623,14 +704,14 @@ grow (struct GNUNET_CONTAINER_MultiHashMap *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 GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, - const struct GNUNET_HashCode *key, + const struct GNUNET_HashCode *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt) { @@ -646,7 +727,7 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, { struct SmallMapEntry *sme; - for (sme = me.sme; NULL != sme; sme = sme->next) + for (sme = me.sme; NULL != sme; sme = sme->next) if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) { if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) @@ -659,7 +740,7 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, { struct BigMapEntry *bme; - for (bme = me.bme; NULL != bme; bme = bme->next) + for (bme = me.bme; NULL != bme; bme = bme->next) if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) { if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) @@ -677,8 +758,8 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, if (map->use_small_entries) { struct SmallMapEntry *sme; - - sme = GNUNET_malloc (sizeof (struct SmallMapEntry)); + + sme = GNUNET_new (struct SmallMapEntry); sme->key = key; sme->value = value; sme->next = map->map[i].sme; @@ -687,8 +768,8 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, else { struct BigMapEntry *bme; - - bme = GNUNET_malloc (sizeof (struct BigMapEntry)); + + bme = GNUNET_new (struct BigMapEntry); bme->key = *key; bme->value = value; bme->next = map->map[i].bme; @@ -707,7 +788,7 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map, * @param it function to call on each entry * @param it_cls extra argument to it * @return the number of key value pairs processed, - * GNUNET_SYSERR if it aborted iteration + * #GNUNET_SYSERR if it aborted iteration */ int GNUNET_CONTAINER_multihashmap_get_multiple (const struct @@ -723,9 +804,9 @@ GNUNET_CONTAINER_multihashmap_get_multiple (const struct me = map->map[idx_of (map, key)]; if (map->use_small_entries) { - struct SmallMapEntry *sme; + struct SmallMapEntry *sme; struct SmallMapEntry *nxt; - + nxt = me.sme; while (NULL != (sme = nxt)) { @@ -739,9 +820,9 @@ GNUNET_CONTAINER_multihashmap_get_multiple (const struct } else { - struct BigMapEntry *bme; + struct BigMapEntry *bme; struct BigMapEntry *nxt; - + nxt = me.bme; while (NULL != (bme = nxt)) { @@ -757,4 +838,173 @@ GNUNET_CONTAINER_multihashmap_get_multiple (const struct } +/** + * @ingroup hashmap + * Call @a it on a random value from the map, or not at all + * if the map is empty. Note that this function has linear + * complexity (in the size of the map). + * + * @param map the map + * @param it function to call on a random entry + * @param it_cls extra argument to @a it + * @return the number of key value pairs processed, zero or one. + */ +unsigned int +GNUNET_CONTAINER_multihashmap_get_random (const struct GNUNET_CONTAINER_MultiHashMap *map, + GNUNET_CONTAINER_HashMapIterator it, + 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++) + { + me = map->map[idx]; + if (map->use_small_entries) + { + struct SmallMapEntry *sme; + struct SmallMapEntry *nxt; + + nxt = me.sme; + while (NULL != (sme = nxt)) + { + nxt = sme->next; + if (0 == off) + { + if (GNUNET_OK != it (it_cls, + sme->key, + sme->value)) + return GNUNET_SYSERR; + return 1; + } + off--; + } + } + else + { + struct BigMapEntry *bme; + struct BigMapEntry *nxt; + + nxt = me.bme; + while (NULL != (bme = nxt)) + { + nxt = bme->next; + if (0 == off) + { + if (GNUNET_OK != it (it_cls, + &bme->key, bme->value)) + return GNUNET_SYSERR; + return 1; + } + off--; + } + } + } + GNUNET_break (0); + return GNUNET_SYSERR; +} + + +/** + * Create an iterator for a multihashmap. + * The iterator can be used to retrieve all the elements in the multihashmap + * one by one, without having to handle all elements at once (in contrast to + * GNUNET_CONTAINER_multihashmap_iterate()). Note that the iterator can not be + * used anymore if elements have been removed from 'map' after the creation of + * the iterator, or 'map' has been destroyed. Adding elements to 'map' may + * result in skipped or repeated elements. + * + * @param map the map to create an iterator for + * @return an iterator over the given multihashmap 'map' + */ +struct GNUNET_CONTAINER_MultiHashMapIterator * +GNUNET_CONTAINER_multihashmap_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap *map) +{ + struct GNUNET_CONTAINER_MultiHashMapIterator *iter; + + iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMapIterator); + iter->map = map; + iter->modification_counter = map->modification_counter; + iter->me = map->map[0]; + return iter; +} + + +/** + * Retrieve the next element from the hash map at the iterator's position. + * If there are no elements left, GNUNET_NO is returned, and 'key' and 'value' + * are not modified. + * This operation is only allowed if no elements have been removed from the + * multihashmap since the creation of 'iter', and the map has not been destroyed. + * Adding elements may result in repeating or skipping elements. + * + * @param iter the iterator to get the next element from + * @param key pointer to store the key in, can be NULL + * @param value pointer to store the value in, can be NULL + * @return #GNUNET_YES we returned an element, + * #GNUNET_NO if we are out of elements + */ +int +GNUNET_CONTAINER_multihashmap_iterator_next (struct GNUNET_CONTAINER_MultiHashMapIterator *iter, + struct GNUNET_HashCode *key, + const void **value) +{ + /* make sure the map has not been modified */ + GNUNET_assert (iter->modification_counter == iter->map->modification_counter); + + /* look for the next entry, skipping empty buckets */ + while (1) + { + if (iter->idx >= iter->map->map_length) + return GNUNET_NO; + if (GNUNET_YES == iter->map->use_small_entries) + { + if (NULL != iter->me.sme) + { + if (NULL != key) + *key = *iter->me.sme->key; + if (NULL != value) + *value = iter->me.sme->value; + iter->me.sme = iter->me.sme->next; + return GNUNET_YES; + } + } + else + { + if (NULL != iter->me.bme) + { + if (NULL != key) + *key = iter->me.bme->key; + if (NULL != value) + *value = iter->me.bme->value; + iter->me.bme = iter->me.bme->next; + return GNUNET_YES; + } + } + iter->idx += 1; + if (iter->idx < iter->map->map_length) + iter->me = iter->map->map[iter->idx]; + } +} + + +/** + * Destroy a multihashmap iterator. + * + * @param iter the iterator to destroy + */ +void +GNUNET_CONTAINER_multihashmap_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter) +{ + GNUNET_free (iter); +} + + /* end of container_multihashmap.c */