GNUnet 0.21.0
container_multipeermap.c File Reference

hash map where the same key may be present multiple times More...

#include "platform.h"
#include "gnunet_util_lib.h"
Include dependency graph for container_multipeermap.c:

Go to the source code of this file.

Data Structures

struct  BigMapEntry
 An entry in the hash map with the full key. More...
 
struct  SmallMapEntry
 An entry in the hash map with just a pointer to the key. More...
 
union  MapEntry
 Entry in the map. More...
 
struct  GNUNET_CONTAINER_MultiPeerMap
 Internal representation of the hash map. More...
 
struct  GNUNET_CONTAINER_MultiPeerMapIterator
 Cursor into a multipeermap. More...
 

Macros

#define LOG(kind, ...)    GNUNET_log_from (kind, "util-container-multipeermap", __VA_ARGS__)
 
#define NEXT_CACHE_SIZE   16
 Maximum recursion depth for callbacks of GNUNET_CONTAINER_multihashmap_get_multiple() themselves s again calling GNUNET_CONTAINER_multihashmap_get_multiple(). More...
 

Functions

struct GNUNET_CONTAINER_MultiPeerMapGNUNET_CONTAINER_multipeermap_create (unsigned int len, int do_not_copy_keys)
 Create a multi peer map (hash map for public keys of peers). More...
 
void GNUNET_CONTAINER_multipeermap_destroy (struct GNUNET_CONTAINER_MultiPeerMap *map)
 Destroy a hash map. More...
 
static unsigned int idx_of (const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
 Compute the index of the bucket for the given key. More...
 
unsigned int GNUNET_CONTAINER_multipeermap_size (const struct GNUNET_CONTAINER_MultiPeerMap *map)
 Get the number of key-value pairs in the map. More...
 
void * GNUNET_CONTAINER_multipeermap_get (const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
 Given a key find a value in the map matching the key. More...
 
int GNUNET_CONTAINER_multipeermap_iterate (struct GNUNET_CONTAINER_MultiPeerMap *map, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls)
 Iterate over all entries in the map. More...
 
static void update_next_cache_bme (struct GNUNET_CONTAINER_MultiPeerMap *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 the map's next_cache. More...
 
static void update_next_cache_sme (struct GNUNET_CONTAINER_MultiPeerMap *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 the map's next_cache. More...
 
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multipeermap_remove (struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, const void *value)
 Remove the given key-value pair from the map. More...
 
int GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
 Remove all entries for the given key from the map. More...
 
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multipeermap_contains (const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
 Check if the map contains any value under the given key (including values that are NULL). More...
 
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multipeermap_contains_value (const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, const void *value)
 Check if the map contains the given value under the given key. More...
 
static void grow (struct GNUNET_CONTAINER_MultiPeerMap *map)
 Grow the given map to a more appropriate size. More...
 
int GNUNET_CONTAINER_multipeermap_put (struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
 Store a key-value pair in the map. More...
 
int GNUNET_CONTAINER_multipeermap_get_multiple (struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls)
 Iterate over all entries in the map that match a particular key. More...
 
unsigned int GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPeerMap *map, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls)
 Call it on a random value from the map, or not at all if the map is empty. More...
 
struct GNUNET_CONTAINER_MultiPeerMapIteratorGNUNET_CONTAINER_multipeermap_iterator_create (const struct GNUNET_CONTAINER_MultiPeerMap *map)
 Create an iterator for a multihashmap. More...
 
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multipeermap_iterator_next (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter, struct GNUNET_PeerIdentity *key, const void **value)
 Retrieve the next element from the hash map at the iterator's position. More...
 
void GNUNET_CONTAINER_multipeermap_iterator_destroy (struct GNUNET_CONTAINER_MultiPeerMapIterator *iter)
 Destroy a multipeermap iterator. More...
 

Detailed Description

hash map where the same key may be present multiple times

Author
Christian Grothoff

Definition in file container_multipeermap.c.

Macro Definition Documentation

◆ LOG

#define LOG (   kind,
  ... 
)     GNUNET_log_from (kind, "util-container-multipeermap", __VA_ARGS__)

Definition at line 30 of file container_multipeermap.c.

◆ NEXT_CACHE_SIZE

#define NEXT_CACHE_SIZE   16

Maximum recursion depth for callbacks of GNUNET_CONTAINER_multihashmap_get_multiple() themselves s again calling GNUNET_CONTAINER_multihashmap_get_multiple().

Should be totally excessive, but if violated we die.

Definition at line 39 of file container_multipeermap.c.

Function Documentation

◆ idx_of()

static unsigned int idx_of ( const struct GNUNET_CONTAINER_MultiPeerMap map,
const struct GNUNET_PeerIdentity key 
)
static

Compute the index of the bucket for the given key.

Parameters
maphash map for which to compute the index
keywhat key should the index be computed for
Returns
offset into the "map" array of "map"

Definition at line 248 of file container_multipeermap.c.

250{
251 unsigned int kx;
252
253 GNUNET_assert (NULL != map);
254 GNUNET_memcpy (&kx, key, sizeof(kx));
255 return kx % map->map_length;
256}
struct GNUNET_HashCode key
The key used in the DHT.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
static struct GNUNET_CONTAINER_MultiPeerMap * map
Peermap of PeerIdentities to "struct PeerEntry" (for fast lookup).
Definition: peer.c:63
unsigned int map_length
Length of the "map" array.

References GNUNET_assert, GNUNET_memcpy, key, map, and GNUNET_CONTAINER_MultiPeerMap::map_length.

Referenced by GNUNET_CONTAINER_multipeermap_contains(), GNUNET_CONTAINER_multipeermap_contains_value(), GNUNET_CONTAINER_multipeermap_get(), GNUNET_CONTAINER_multipeermap_get_multiple(), GNUNET_CONTAINER_multipeermap_put(), GNUNET_CONTAINER_multipeermap_remove(), GNUNET_CONTAINER_multipeermap_remove_all(), and grow().

Here is the caller graph for this function:

◆ update_next_cache_bme()

static void update_next_cache_bme ( struct GNUNET_CONTAINER_MultiPeerMap map,
const struct BigMapEntry bme 
)
static

We are about to free() the bme, make sure it is not in the list of next values for any iterator in the map's next_cache.

Parameters
mapthe map to check
bmethe entry that is about to be free'd

Definition at line 362 of file container_multipeermap.c.

364{
365 for (unsigned int i = 0; i < map->next_cache_off; i++)
366 if (map->next_cache[i].bme == bme)
367 map->next_cache[i].bme = bme->next;
368}
struct BigMapEntry * next
If there is a hash collision, we create a linked list.
unsigned int next_cache_off
Offset of next_cache entries in use, must be smaller than NEXT_CACHE_SIZE.
union MapEntry next_cache[16]
Map entries indicating iteration positions currently in use by GNUNET_CONTAINER_multihashmap_get_mult...
struct BigMapEntry * bme
Variant used if map entries contain the full key.

References MapEntry::bme, map, BigMapEntry::next, GNUNET_CONTAINER_MultiPeerMap::next_cache, and GNUNET_CONTAINER_MultiPeerMap::next_cache_off.

Referenced by GNUNET_CONTAINER_multipeermap_remove(), and GNUNET_CONTAINER_multipeermap_remove_all().

Here is the caller graph for this function:

◆ update_next_cache_sme()

static void update_next_cache_sme ( struct GNUNET_CONTAINER_MultiPeerMap map,
const struct SmallMapEntry sme 
)
static

We are about to free() the sme, make sure it is not in the list of next values for any iterator in the map's next_cache.

Parameters
mapthe map to check
smethe entry that is about to be free'd

Definition at line 379 of file container_multipeermap.c.

381{
382 for (unsigned int i = 0; i < map->next_cache_off; i++)
383 if (map->next_cache[i].sme == sme)
384 map->next_cache[i].sme = sme->next;
385}
struct SmallMapEntry * next
If there is a hash collision, we create a linked list.
struct SmallMapEntry * sme
Variant used if map entries only contain a pointer to the key.

References map, SmallMapEntry::next, GNUNET_CONTAINER_MultiPeerMap::next_cache, GNUNET_CONTAINER_MultiPeerMap::next_cache_off, and MapEntry::sme.

Referenced by GNUNET_CONTAINER_multipeermap_remove(), and GNUNET_CONTAINER_multipeermap_remove_all().

Here is the caller graph for this function:

◆ grow()

static void grow ( struct GNUNET_CONTAINER_MultiPeerMap map)
static

Grow the given map to a more appropriate size.

Parameters
mapthe hash map to grow

Definition at line 578 of file container_multipeermap.c.

579{
580 union MapEntry *old_map;
581 union MapEntry *new_map;
582 unsigned int old_len;
583 unsigned int new_len;
584 unsigned int idx;
585
586 old_map = map->map;
587 old_len = map->map_length;
588 GNUNET_assert (0 != old_len);
589 new_len = old_len * 2;
590 if (0 == new_len) /* 2^31 * 2 == 0 */
591 new_len = old_len; /* never use 0 */
592 if (new_len == old_len)
593 return; /* nothing changed */
594 new_map = GNUNET_malloc_large (new_len * sizeof(union MapEntry));
595 if (NULL == new_map)
596 return; /* grow not possible */
598 map->map_length = new_len;
599 map->map = new_map;
600 for (unsigned int i = 0; i < old_len; i++)
601 {
603 {
604 struct SmallMapEntry *sme;
605
606 while (NULL != (sme = old_map[i].sme))
607 {
608 old_map[i].sme = sme->next;
609 idx = idx_of (map, sme->key);
610 sme->next = new_map[idx].sme;
611 new_map[idx].sme = sme;
612 }
613 }
614 else
615 {
616 struct BigMapEntry *bme;
617
618 while (NULL != (bme = old_map[i].bme))
619 {
620 old_map[i].bme = bme->next;
621 idx = idx_of (map, &bme->key);
622 bme->next = new_map[idx].bme;
623 new_map[idx].bme = bme;
624 }
625 }
626 }
627 GNUNET_free (old_map);
628}
static unsigned int idx_of(const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
Compute the index of the bucket for the given key.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
An entry in the hash map with the full key.
unsigned int modification_counter
Counts the destructive modifications (grow, remove) to the map, so that iterators can check if they a...
union MapEntry * map
All of our buckets.
int use_small_entries
GNUNET_NO if the map entries are of type 'struct BigMapEntry', GNUNET_YES if the map entries are of t...
An entry in the hash map with just a pointer to the key.
Entry in the map.

References MapEntry::bme, GNUNET_assert, GNUNET_free, GNUNET_malloc_large, idx_of(), BigMapEntry::key, SmallMapEntry::key, GNUNET_CONTAINER_MultiPeerMap::map, map, GNUNET_CONTAINER_MultiPeerMap::map_length, GNUNET_CONTAINER_MultiPeerMap::modification_counter, BigMapEntry::next, SmallMapEntry::next, MapEntry::sme, and GNUNET_CONTAINER_MultiPeerMap::use_small_entries.

Referenced by GNUNET_CONTAINER_multipeermap_put().

Here is the call graph for this function:
Here is the caller graph for this function: