29 #define LOG(kind, ...) \ 30 GNUNET_log_from (kind, "util-container-multihashmap", __VA_ARGS__) 38 #define NEXT_CACHE_SIZE 16 206 if ((s /
sizeof(
union MapEntry)) != len)
212 "Out of memory allocating large hash map (%u entries)\n",
239 for (
unsigned int i = 0; i < map->
map_length; i++)
250 while (NULL != (sme = nxt))
263 while (NULL != (bme = nxt))
288 return (*(
unsigned int *) key) % map->
map_length;
328 for (sme = me.sme; NULL != sme; sme = sme->
next)
336 for (bme = me.bme; NULL != bme; bme = bme->
next)
368 for (
unsigned i = 0; i < map->
map_length; i++)
376 while (NULL != (sme = ce->
sme))
395 while (NULL != (bme = ce->
bme))
480 if ((0 ==
GNUNET_memcmp (key, sme->key)) && (value == sme->value))
501 if ((0 ==
GNUNET_memcmp (key, &bme->key)) && (value == bme->value))
666 for (sme = me.sme; NULL != sme; sme = sme->
next)
674 for (bme = me.bme; NULL != bme; bme = bme->
next)
705 for (sme = me.sme; NULL != sme; sme = sme->
next)
713 for (bme = me.bme; NULL != bme; bme = bme->
next)
731 unsigned int old_len;
732 unsigned int new_len;
738 new_len = old_len * 2;
741 if (new_len == old_len)
749 for (
unsigned int i = 0; i < old_len; i++)
755 while (NULL != (sme = old_map[i].sme))
758 idx =
idx_of (map, sme->key);
759 sme->next = new_map[idx].
sme;
760 new_map[idx].
sme = sme;
767 while (NULL != (bme = old_map[i].bme))
770 idx =
idx_of (map, &bme->key);
771 bme->next = new_map[idx].
bme;
772 new_map[idx].
bme = bme;
810 for (sme = me.
sme; NULL != sme; sme = sme->
next)
823 for (bme = me.
bme; NULL != bme; bme = bme->
next)
893 while (NULL != (sme = ce->
sme))
911 while (NULL != (bme = ce->
bme))
964 while (NULL != (sme = nxt))
982 while (NULL != (bme = nxt))
1021 iter->
me = map->
map[0];
1056 if (NULL != iter->
me.
sme)
1068 if (NULL != iter->
me.
bme)
int(* GNUNET_CONTAINER_MulitHashMapIteratorCallback)(void *cls, const struct GNUNET_HashCode *key, void *value)
Iterator over hash map entries.
union MapEntry * map
All of our buckets.
void GNUNET_CONTAINER_multihashmap_iterator_destroy(struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
Destroy a multihashmap iterator.
static GNUNET_NETWORK_STRUCT_END struct GNUNET_PeerIdentity me
Our own peer identity.
int GNUNET_CONTAINER_multihashmap_iterator_next(struct GNUNET_CONTAINER_MultiHashMapIterator *iter, struct GNUNET_HashCode *key, const void **value)
Retrieve the next element from the hash map at the iterator's position.
unsigned int size
Number of entries in the map.
union MapEntry me
Position in the bucket idx.
GNUNET_CONTAINER_MultiHashMapOption
Options for storing values in the HashMap.
struct SmallMapEntry * next
If there is a hash collision, we create a linked list.
unsigned int modification_counter
Counts the destructive modifications (grow, remove) to the map, so that iterators can check if they a...
unsigned int GNUNET_CONTAINER_multihashmap_size(const struct GNUNET_CONTAINER_MultiHashMap *map)
Get the number of key-value pairs in the map.
const struct GNUNET_CONTAINER_MultiHashMap * map
Map that we are iterating over.
void * value
Value of the entry.
static int remove_all(void *cls, const struct GNUNET_HashCode *key, void *value)
Callback used to remove all entries from the map.
struct GNUNET_CONTAINER_MultiHashMapIterator * GNUNET_CONTAINER_multihashmap_iterator_create(const struct GNUNET_CONTAINER_MultiHashMap *map)
Create an iterator for a multihashmap.
unsigned int next_cache_off
Offset of next_cache entries in use, must be smaller than NEXT_CACHE_SIZE.
uint32_t GNUNET_CRYPTO_random_u32(enum GNUNET_CRYPTO_Quality mode, uint32_t i)
Produce a random value.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
static int ret
Return value of the commandline.
const struct GNUNET_HashCode * key
Key for the entry.
void * value
Value of the entry.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
int GNUNET_CONTAINER_multihashmap_remove_all(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key)
Remove all entries for the given key from the map.
struct SmallMapEntry * sme
Variant used if map entries only contain a pointer to the key.
int GNUNET_CONTAINER_multihashmap_contains(const struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key)
Check if the map contains any value under the given key (including values that are NULL)...
#define GNUNET_malloc_large(size)
Wrapper around malloc.
Internal representation of the hash map.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
union MapEntry next_cache[16]
Map entries indicating iteration positions currently in use by GNUNET_CONTAINER_multihashmap_get_mult...
struct BigMapEntry * next
If there is a hash collision, we create a linked list.
static struct GNUNET_CONTAINER_MultiPeerMap * map
Handle to the map used to store old latency values for peers.
void * GNUNET_CONTAINER_multihashmap_get(const struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key)
Given a key find a value in the map matching the key.
static void update_next_cache_sme(struct GNUNET_CONTAINER_MultiHashMap *map, const struct SmallMapEntry *sme)
We are about to free() the sme, make sure it is not in the list of next values for any iterator in th...
static struct GNUNET_OS_Process * p
Helper process we started.
, ' bother checking if a value already exists (faster than GNUNET_CONTAINER_MULTIHASHMAPOPTION_...
#define NEXT_CACHE_SIZE
Maximum recursion depth for callbacks of GNUNET_CONTAINER_multihashmap_get_multiple() themselves s ag...
unsigned int map_length
Length of the "map" array.
unsigned int GNUNET_CONTAINER_multihashmap_clear(struct GNUNET_CONTAINER_MultiHashMap *map)
Remove all entries from the map.
void GNUNET_CONTAINER_multihashmap_destroy(struct GNUNET_CONTAINER_MultiHashMap *map)
Destroy a hash map.
unsigned int GNUNET_CONTAINER_multihashmap_get_random(const struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Call it on a random value from the map, or not at all if the map is empty.
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
int GNUNET_CONTAINER_multihashmap_remove(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, const void *value)
Remove the given key-value pair from the map.
unsigned int idx
Current bucket index.
static void update_next_cache_bme(struct GNUNET_CONTAINER_MultiHashMap *map, const struct BigMapEntry *bme)
We are about to free() the bme, make sure it is not in the list of next values for any iterator in th...
There must only be one value per key; storing a value should fail if a value under the same key alrea...
int use_small_entries
GNUNET_NO if the map entries are of type 'struct BigMapEntry', GNUNET_YES if the map entries are of t...
int GNUNET_CONTAINER_multihashmap_contains_value(const struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, const void *value)
Check if the map contains the given value under the given key.
Cursor into a multihashmap.
int GNUNET_CONTAINER_multihashmap_put(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
static void grow(struct GNUNET_CONTAINER_MultiHashMap *map)
Grow the given map to a more appropriate size.
#define GNUNET_MAX_MALLOC_CHECKED
Maximum allocation with GNUNET_malloc macro.
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
static unsigned int idx_of(const struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key)
Compute the index of the bucket for the given key.
Allow multiple values with the same key.
An entry in the hash map with just a pointer to the key.
int GNUNET_CONTAINER_multihashmap_get_multiple(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map that match a particular key.
#define GNUNET_log(kind,...)
An entry in the hash map with the full key.
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
unsigned int modification_counter
Modification counter as observed on the map when the iterator was created.
struct BigMapEntry * bme
Variant used if map entries contain the full key.
int GNUNET_CONTAINER_multihashmap_iterate(struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map.
#define GNUNET_free(ptr)
Wrapper around free.
struct GNUNET_HashCode key
Key for the entry.
uint16_t len
length of data (which is always a uint32_t, but presumably this can be used to specify that fewer byt...