X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Futil%2Fcontainer_multipeermap.c;h=363e2b27c4467889c32318ab360823143b6879ec;hb=572ed5a20edf2e273ae377473b52bfee98eca24e;hp=6519f6c84111a523dc85dcd620db6203842eba57;hpb=c886c53017f31d76c22f5ed55df61719b71ef87a;p=oweals%2Fgnunet.git diff --git a/src/util/container_multipeermap.c b/src/util/container_multipeermap.c index 6519f6c84..363e2b27c 100644 --- a/src/util/container_multipeermap.c +++ b/src/util/container_multipeermap.c @@ -1,6 +1,6 @@ /* 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 @@ -14,8 +14,8 @@ You should have received a copy of the GNU General Public License along with GNUnet; see the file COPYING. If not, write to the - Free Software Foundation, Inc., 59 Temple Place - Suite 330, - Boston, MA 02111-1307, USA. + Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, + Boston, MA 02110-1301, USA. */ /** * @file util/container_multipeermap.c @@ -24,9 +24,7 @@ */ #include "platform.h" -#include "gnunet_common.h" -#include "gnunet_container_lib.h" -#include "gnunet_crypto_lib.h" +#include "gnunet_util_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. */ @@ -164,10 +162,10 @@ struct GNUNET_CONTAINER_MultiPeerMapIterator * @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 + * 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 @@ -247,8 +245,11 @@ static unsigned int idx_of (const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key) { - GNUNET_assert (map != NULL); - return (*(unsigned int *) key) % map->map_length; + unsigned int kx; + + GNUNET_assert (NULL != map); + memcpy (&kx, key, sizeof (kx)); + return kx % map->map_length; } @@ -333,7 +334,7 @@ GNUNET_CONTAINER_multipeermap_iterate (const struct struct SmallMapEntry *sme; struct SmallMapEntry *nxt; - nxt = me.sme; + nxt = me.sme; while (NULL != (sme = nxt)) { nxt = sme->next; @@ -350,7 +351,7 @@ GNUNET_CONTAINER_multipeermap_iterate (const struct struct BigMapEntry *bme; struct BigMapEntry *nxt; - nxt = me.bme; + nxt = me.bme; while (NULL != (bme = nxt)) { nxt = bme->next; @@ -381,7 +382,7 @@ GNUNET_CONTAINER_multipeermap_iterate (const struct */ int GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, - const struct GNUNET_PeerIdentity *key, + const struct GNUNET_PeerIdentity *key, const void *value) { union MapEntry me; @@ -392,7 +393,7 @@ GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, i = idx_of (map, key); me = map->map[i]; if (map->use_small_entries) - { + { struct SmallMapEntry *sme; struct SmallMapEntry *p; @@ -461,7 +462,7 @@ GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap i = idx_of (map, key); me = map->map[i]; if (map->use_small_entries) - { + { struct SmallMapEntry *sme; struct SmallMapEntry *p; @@ -481,7 +482,7 @@ GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap sme = map->map[i].sme; else sme = p->next; - ret++; + ret++; } else { @@ -644,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; @@ -670,7 +671,7 @@ grow (struct GNUNET_CONTAINER_MultiPeerMap *map) */ int GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map, - const struct GNUNET_PeerIdentity *key, + const struct GNUNET_PeerIdentity *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt) { @@ -686,7 +687,7 @@ GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *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_PeerIdentity))) { if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) @@ -699,7 +700,7 @@ GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *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_PeerIdentity))) { if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY) @@ -717,7 +718,7 @@ GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map, if (map->use_small_entries) { struct SmallMapEntry *sme; - + sme = GNUNET_new (struct SmallMapEntry); sme->key = key; sme->value = value; @@ -727,7 +728,7 @@ GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map, else { struct BigMapEntry *bme; - + bme = GNUNET_new (struct BigMapEntry); bme->key = *key; bme->value = value; @@ -762,9 +763,9 @@ GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiP 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)) { @@ -778,9 +779,9 @@ GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiP } else { - struct BigMapEntry *bme; + struct BigMapEntry *bme; struct BigMapEntry *nxt; - + nxt = me.bme; while (NULL != (bme = nxt)) { @@ -796,6 +797,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