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:

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_MultiPeerMap *	GNUNET_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_MultiPeerMapIterator *	GNUNET_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

map	hash map for which to compute the index
key	what key should the index be computed for

Returns: offset into the "map" array of "map"

Definition at line 248 of file container_multipeermap.c.

{
  unsigned int kx;
 
  GNUNET_assert (NULL != map);
  GNUNET_memcpy (&kx, key, sizeof(kx));
  return kx % map->map_length;
}

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

map	the map to check
bme	the entry that is about to be free'd

Definition at line 362 of file container_multipeermap.c.

{
  for (unsigned int i = 0; i < map->next_cache_off; i++)
    if (map->next_cache[i].bme == bme)
      map->next_cache[i].bme = bme->next;
}

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

map	the map to check
sme	the entry that is about to be free'd

Definition at line 379 of file container_multipeermap.c.

{
  for (unsigned int i = 0; i < map->next_cache_off; i++)
    if (map->next_cache[i].sme == sme)
      map->next_cache[i].sme = sme->next;
}

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

map	the hash map to grow

Definition at line 578 of file container_multipeermap.c.

{
  union MapEntry *old_map;
  union MapEntry *new_map;
  unsigned int old_len;
  unsigned int new_len;
  unsigned int idx;
 
  old_map = map->map;
  old_len = map->map_length;
  GNUNET_assert (0 != old_len);
  new_len = old_len * 2;
  if (0 == new_len) /* 2^31 * 2 == 0 */
    new_len = old_len; /* never use 0 */
  if (new_len == old_len)
    return; /* nothing changed */
  new_map = GNUNET_malloc_large (new_len * sizeof(union MapEntry));
  if (NULL == new_map)
    return; /* grow not possible */
  map->modification_counter++;
  map->map_length = new_len;
  map->map = new_map;
  for (unsigned int i = 0; i < old_len; i++)
  {
    if (map->use_small_entries)
    {
      struct SmallMapEntry *sme;
 
      while (NULL != (sme = old_map[i].sme))
      {
        old_map[i].sme = sme->next;
        idx = idx_of (map, sme->key);
        sme->next = new_map[idx].sme;
        new_map[idx].sme = sme;
      }
    }
    else
    {
      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;
        new_map[idx].bme = bme;
      }
    }
  }
  GNUNET_free (old_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:

Data Structures

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ LOG

◆ NEXT_CACHE_SIZE

Function Documentation

◆ idx_of()

◆ update_next_cache_bme()

◆ update_next_cache_sme()

◆ grow()