diff options
| -rw-r--r-- | src/include/gnunet_container_lib.h | 21 | ||||
| -rw-r--r-- | src/util/container_multihashmap.c | 3 | ||||
| -rw-r--r-- | src/util/container_multipeermap.c | 78 |
3 files changed, 97 insertions, 5 deletions
diff --git a/src/include/gnunet_container_lib.h b/src/include/gnunet_container_lib.h index 1ecf4f52ac..d8886c5041 100644 --- a/src/include/gnunet_container_lib.h +++ b/src/include/gnunet_container_lib.h @@ -1,6 +1,6 @@ /* This file is part of GNUnet. - Copyright (C) 2001-2013 Christian Grothoff (and other contributing authors) + Copyright (C) 2001-2015 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 @@ -857,7 +857,8 @@ GNUNET_CONTAINER_multihashmap_get_multiple (const struct GNUNET_CONTAINER_MultiH /** * @ingroup hashmap * Call @a it on a random value from the map, or not at all - * if the map is empty. + * 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 @@ -1115,6 +1116,22 @@ GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiP void *it_cls); +/** + * @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_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPeerMap *map, + GNUNET_CONTAINER_PeerMapIterator it, + void *it_cls); + /* Version of multihashmap with 32 bit keys */ diff --git a/src/util/container_multihashmap.c b/src/util/container_multihashmap.c index 80545176d9..df6dd5704a 100644 --- a/src/util/container_multihashmap.c +++ b/src/util/container_multihashmap.c @@ -841,7 +841,8 @@ 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. + * 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 diff --git a/src/util/container_multipeermap.c b/src/util/container_multipeermap.c index bed9e6042a..15517b92a8 100644 --- a/src/util/container_multipeermap.c +++ b/src/util/container_multipeermap.c @@ -482,7 +482,7 @@ GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap sme = map->map[i].sme; else sme = p->next; - ret++; + ret++; } else { @@ -645,7 +645,7 @@ grow (struct GNUNET_CONTAINER_MultiPeerMap *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; @@ -798,6 +798,80 @@ GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiP /** + * @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_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPeerMap *map, + GNUNET_CONTAINER_PeerMapIterator 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 multipeermap. * The iterator can be used to retrieve all the elements in the multipeermap * one by one, without having to handle all elements at once (in contrast to |