GNUnet  0.11.x
Data Structures | Macros | Functions
container_multiuuidmap.c File Reference

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

#include "platform.h"
#include "gnunet_util_lib.h"
Include dependency graph for container_multiuuidmap.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_MultiUuidmap
 Internal representation of the hash map. More...
 
struct  GNUNET_CONTAINER_MultiUuidmapIterator
 Cursor into a multiuuidmap. More...
 

Macros

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

Functions

struct GNUNET_CONTAINER_MultiUuidmapGNUNET_CONTAINER_multiuuidmap_create (unsigned int len, int do_not_copy_keys)
 Create a multi hash map. More...
 
void GNUNET_CONTAINER_multiuuidmap_destroy (struct GNUNET_CONTAINER_MultiUuidmap *map)
 Destroy a hash map. More...
 
static unsigned int idx_of (const struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key)
 Compute the index of the bucket for the given key. More...
 
unsigned int GNUNET_CONTAINER_multiuuidmap_size (const struct GNUNET_CONTAINER_MultiUuidmap *map)
 Get the number of key-value pairs in the map. More...
 
void * GNUNET_CONTAINER_multiuuidmap_get (const struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key)
 Given a key find a value in the map matching the key. More...
 
int GNUNET_CONTAINER_multiuuidmap_iterate (struct GNUNET_CONTAINER_MultiUuidmap *map, GNUNET_CONTAINER_MultiUuidmapIteratorCallback it, void *it_cls)
 Iterate over all entries in the map. More...
 
static void update_next_cache_bme (struct GNUNET_CONTAINER_MultiUuidmap *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_MultiUuidmap *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...
 
int GNUNET_CONTAINER_multiuuidmap_remove (struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key, const void *value)
 Remove the given key-value pair from the map. More...
 
int GNUNET_CONTAINER_multiuuidmap_remove_all (struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key)
 Remove all entries for the given key from the map. More...
 
int GNUNET_CONTAINER_multiuuidmap_contains (const struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key)
 Check if the map contains any value under the given key (including values that are NULL). More...
 
int GNUNET_CONTAINER_multiuuidmap_contains_value (const struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key, const void *value)
 Check if the map contains the given value under the given key. More...
 
static void grow (struct GNUNET_CONTAINER_MultiUuidmap *map)
 Grow the given map to a more appropriate size. More...
 
int GNUNET_CONTAINER_multiuuidmap_put (struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
 Store a key-value pair in the map. More...
 
int GNUNET_CONTAINER_multiuuidmap_get_multiple (struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key, GNUNET_CONTAINER_MultiUuidmapIteratorCallback it, void *it_cls)
 Iterate over all entries in the map that match a particular key. More...
 
unsigned int GNUNET_CONTAINER_multiuuidmap_get_random (const struct GNUNET_CONTAINER_MultiUuidmap *map, GNUNET_CONTAINER_MultiUuidmapIteratorCallback 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_MultiUuidmapIteratorGNUNET_CONTAINER_multiuuidmap_iterator_create (const struct GNUNET_CONTAINER_MultiUuidmap *map)
 Create an iterator for a multiuuidmap. More...
 
int GNUNET_CONTAINER_multiuuidmap_iterator_next (struct GNUNET_CONTAINER_MultiUuidmapIterator *iter, struct GNUNET_Uuid *key, const void **value)
 Retrieve the next element from the hash map at the iterator's position. More...
 
void GNUNET_CONTAINER_multiuuidmap_iterator_destroy (struct GNUNET_CONTAINER_MultiUuidmapIterator *iter)
 Destroy a multiuuidmap iterator. More...
 

Detailed Description

hash map for UUIDs where the same key may be present multiple times

Author
Christian Grothoff

Definition in file container_multiuuidmap.c.

Macro Definition Documentation

◆ LOG

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

Definition at line 29 of file container_multiuuidmap.c.

◆ NEXT_CACHE_SIZE

#define NEXT_CACHE_SIZE   16

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

Should be totally excessive, but if violated we die.

Definition at line 38 of file container_multiuuidmap.c.

Referenced by GNUNET_CONTAINER_multiuuidmap_get_multiple(), and GNUNET_CONTAINER_multiuuidmap_iterate().

Function Documentation

◆ idx_of()

static unsigned int idx_of ( const struct GNUNET_CONTAINER_MultiUuidmap map,
const struct GNUNET_Uuid 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 268 of file container_multiuuidmap.c.

References GNUNET_assert, GNUNET_memcpy, and GNUNET_CONTAINER_MultiUuidmap::map_length.

Referenced by GNUNET_CONTAINER_multiuuidmap_contains(), GNUNET_CONTAINER_multiuuidmap_contains_value(), GNUNET_CONTAINER_multiuuidmap_get(), GNUNET_CONTAINER_multiuuidmap_get_multiple(), GNUNET_CONTAINER_multiuuidmap_put(), GNUNET_CONTAINER_multiuuidmap_remove(), GNUNET_CONTAINER_multiuuidmap_remove_all(), and grow().

270 {
271  unsigned int kx;
272 
273  GNUNET_assert (NULL != map);
274  GNUNET_memcpy (&kx, key, sizeof(kx));
275  return kx % map->map_length;
276 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
unsigned int map_length
Length of the "map" array.
Here is the caller graph for this function:

◆ update_next_cache_bme()

static void update_next_cache_bme ( struct GNUNET_CONTAINER_MultiUuidmap 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 404 of file container_multiuuidmap.c.

References MapEntry::bme, BigMapEntry::next, GNUNET_CONTAINER_MultiUuidmap::next_cache, and GNUNET_CONTAINER_MultiUuidmap::next_cache_off.

Referenced by GNUNET_CONTAINER_multiuuidmap_remove(), and GNUNET_CONTAINER_multiuuidmap_remove_all().

406 {
407  for (unsigned int i = 0; i < map->next_cache_off; i++)
408  if (map->next_cache[i].bme == bme)
409  map->next_cache[i].bme = bme->next;
410 }
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.
Here is the caller graph for this function:

◆ update_next_cache_sme()

static void update_next_cache_sme ( struct GNUNET_CONTAINER_MultiUuidmap 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 421 of file container_multiuuidmap.c.

References SmallMapEntry::next, GNUNET_CONTAINER_MultiUuidmap::next_cache, GNUNET_CONTAINER_MultiUuidmap::next_cache_off, and MapEntry::sme.

Referenced by GNUNET_CONTAINER_multiuuidmap_remove(), and GNUNET_CONTAINER_multiuuidmap_remove_all().

423 {
424  for (unsigned int i = 0; i < map->next_cache_off; i++)
425  if (map->next_cache[i].sme == sme)
426  map->next_cache[i].sme = sme->next;
427 }
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.
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...
Here is the caller graph for this function:

◆ grow()

static void grow ( struct GNUNET_CONTAINER_MultiUuidmap map)
static

Grow the given map to a more appropriate size.

Parameters
mapthe hash map to grow

Definition at line 658 of file container_multiuuidmap.c.

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

Referenced by GNUNET_CONTAINER_multiuuidmap_put().

659 {
660  union MapEntry *old_map;
661  union MapEntry *new_map;
662  unsigned int old_len;
663  unsigned int new_len;
664  unsigned int idx;
665 
666  old_map = map->map;
667  old_len = map->map_length;
668  new_len = old_len * 2;
669  if (0 == new_len) /* 2^31 * 2 == 0 */
670  new_len = old_len; /* never use 0 */
671  if (new_len == old_len)
672  return; /* nothing changed */
673  new_map = GNUNET_malloc_large (new_len * sizeof(union MapEntry));
674  if (NULL == new_map)
675  return; /* grow not possible */
676  map->modification_counter++;
677  map->map_length = new_len;
678  map->map = new_map;
679  for (unsigned int i = 0; i < old_len; i++)
680  {
681  if (map->use_small_entries)
682  {
683  struct SmallMapEntry *sme;
684 
685  while (NULL != (sme = old_map[i].sme))
686  {
687  old_map[i].sme = sme->next;
688  idx = idx_of (map, sme->key);
689  sme->next = new_map[idx].sme;
690  new_map[idx].sme = sme;
691  }
692  }
693  else
694  {
695  struct BigMapEntry *bme;
696 
697  while (NULL != (bme = old_map[i].bme))
698  {
699  old_map[i].bme = bme->next;
700  idx = idx_of (map, &bme->key);
701  bme->next = new_map[idx].bme;
702  new_map[idx].bme = bme;
703  }
704  }
705  }
706  GNUNET_free (old_map);
707 }
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.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
struct BigMapEntry * next
If there is a hash collision, we create a linked list.
Entry in the map.
unsigned int modification_counter
Counts the destructive modifications (grow, remove) to the map, so that iterators can check if they a...
An entry in the hash map with just a pointer to the key.
static unsigned int idx_of(const struct GNUNET_CONTAINER_MultiUuidmap *map, const struct GNUNET_Uuid *key)
Compute the index of the bucket for the given key.
int use_small_entries
GNUNET_NO if the map entries are of type &#39;struct BigMapEntry&#39;, GNUNET_YES if the map entries are of t...
An entry in the hash map with the full key.
struct BigMapEntry * bme
Variant used if map entries contain the full key.
unsigned int map_length
Length of the "map" array.
union MapEntry * map
All of our buckets.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function: