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

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

#include "platform.h"
#include "gnunet_container_lib.h"
Include dependency graph for container_multihashmap.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_MultiHashMap
 Internal representation of the hash map. More...
 
struct  GNUNET_CONTAINER_MultiHashMapIterator
 Cursor into a multihashmap. More...
 

Macros

#define LOG(kind, ...)   GNUNET_log_from (kind, "util-container-multihashmap", __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_MultiHashMapGNUNET_CONTAINER_multihashmap_create (unsigned int len, int do_not_copy_keys)
 Create a multi hash map. More...
 
void GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap *map)
 Destroy a hash map. More...
 
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. More...
 
unsigned int GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap *map)
 Get the number of key-value pairs in the map. More...
 
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. More...
 
int GNUNET_CONTAINER_multihashmap_iterate (struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
 Iterate over all entries in the map. More...
 
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 the map's next_cache. More...
 
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 the map's next_cache. More...
 
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. More...
 
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. More...
 
static int remove_all (void *cls, const struct GNUNET_HashCode *key, void *value)
 Callback used to remove all entries from the map. More...
 
unsigned int GNUNET_CONTAINER_multihashmap_clear (struct GNUNET_CONTAINER_MultiHashMap *map)
 Remove all entries from the map. More...
 
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). More...
 
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. More...
 
static void grow (struct GNUNET_CONTAINER_MultiHashMap *map)
 Grow the given map to a more appropriate size. More...
 
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. More...
 
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. More...
 
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. More...
 
struct GNUNET_CONTAINER_MultiHashMapIteratorGNUNET_CONTAINER_multihashmap_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap *map)
 Create an iterator for a multihashmap. More...
 
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. More...
 
void GNUNET_CONTAINER_multihashmap_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
 Destroy a multihashmap iterator. More...
 

Detailed Description

hash map where the same key may be present multiple times

Author
Christian Grothoff

Definition in file container_multihashmap.c.

Macro Definition Documentation

◆ LOG

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

Definition at line 29 of file container_multihashmap.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_multihashmap.c.

Referenced by GNUNET_CONTAINER_multihashmap_get_multiple(), and GNUNET_CONTAINER_multihashmap_iterate().

Function Documentation

◆ idx_of()

static unsigned int idx_of ( const struct GNUNET_CONTAINER_MultiHashMap map,
const struct GNUNET_HashCode 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 284 of file container_multihashmap.c.

References GNUNET_assert, and GNUNET_CONTAINER_MultiHashMap::map_length.

Referenced by GNUNET_CONTAINER_multihashmap_contains(), GNUNET_CONTAINER_multihashmap_contains_value(), GNUNET_CONTAINER_multihashmap_get(), GNUNET_CONTAINER_multihashmap_get_multiple(), GNUNET_CONTAINER_multihashmap_put(), GNUNET_CONTAINER_multihashmap_remove(), GNUNET_CONTAINER_multihashmap_remove_all(), and grow().

286 {
287  GNUNET_assert (map != NULL);
288  return (*(unsigned int *) key) % map->map_length;
289 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
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_MultiHashMap 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 424 of file container_multihashmap.c.

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

Referenced by GNUNET_CONTAINER_multihashmap_remove(), and GNUNET_CONTAINER_multihashmap_remove_all().

426 {
427  for (unsigned int i = 0; i < map->next_cache_off; i++)
428  if (map->next_cache[i].bme == bme)
429  map->next_cache[i].bme = bme->next;
430 }
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 * next
If there is a hash collision, we create a linked list.
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_MultiHashMap 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 441 of file container_multihashmap.c.

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

Referenced by GNUNET_CONTAINER_multihashmap_remove(), and GNUNET_CONTAINER_multihashmap_remove_all().

443 {
444  for (unsigned int i = 0; i < map->next_cache_off; i++)
445  if (map->next_cache[i].sme == sme)
446  map->next_cache[i].sme = sme->next;
447 }
struct SmallMapEntry * 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.
struct SmallMapEntry * sme
Variant used if map entries only contain a pointer to the key.
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:

◆ remove_all()

static int remove_all ( void *  cls,
const struct GNUNET_HashCode key,
void *  value 
)
static

Callback used to remove all entries from the map.

Parameters
clsthe struct GNUNET_CONTAINER_MultiHashMap
keythe key
valuethe value
Returns
GNUNET_OK (continue to iterate)

Definition at line 616 of file container_multihashmap.c.

References GNUNET_assert, GNUNET_CONTAINER_multihashmap_remove(), GNUNET_OK, GNUNET_YES, and map.

Referenced by GNUNET_CONTAINER_multihashmap_clear().

617 {
618  struct GNUNET_CONTAINER_MultiHashMap *map = cls;
619 
622  return GNUNET_OK;
623 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:75
Internal representation of the hash map.
static struct GNUNET_CONTAINER_MultiPeerMap * map
Handle to the map used to store old latency values for peers.
static char * value
Value of the record to add/remove.
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.
#define GNUNET_YES
Definition: gnunet_common.h:77
Here is the call graph for this function:
Here is the caller graph for this function:

◆ grow()

static void grow ( struct GNUNET_CONTAINER_MultiHashMap map)
static

Grow the given map to a more appropriate size.

Parameters
mapthe hash map to grow

Definition at line 727 of file container_multihashmap.c.

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

Referenced by GNUNET_CONTAINER_multihashmap_put().

728 {
729  union MapEntry *old_map;
730  union MapEntry *new_map;
731  unsigned int old_len;
732  unsigned int new_len;
733  unsigned int idx;
734 
735  old_map = map->map;
736  old_len = map->map_length;
737  GNUNET_assert (0 != old_len);
738  new_len = old_len * 2;
739  if (0 == new_len) /* 2^31 * 2 == 0 */
740  new_len = old_len; /* never use 0 */
741  if (new_len == old_len)
742  return; /* nothing changed */
743  new_map = GNUNET_malloc_large (new_len * sizeof(union MapEntry));
744  if (NULL == new_map)
745  return; /* grow not possible */
746  map->modification_counter++;
747  map->map_length = new_len;
748  map->map = new_map;
749  for (unsigned int i = 0; i < old_len; i++)
750  {
751  if (map->use_small_entries)
752  {
753  struct SmallMapEntry *sme;
754 
755  while (NULL != (sme = old_map[i].sme))
756  {
757  old_map[i].sme = sme->next;
758  idx = idx_of (map, sme->key);
759  sme->next = new_map[idx].sme;
760  new_map[idx].sme = sme;
761  }
762  }
763  else
764  {
765  struct BigMapEntry *bme;
766 
767  while (NULL != (bme = old_map[i].bme))
768  {
769  old_map[i].bme = bme->next;
770  idx = idx_of (map, &bme->key);
771  bme->next = new_map[idx].bme;
772  new_map[idx].bme = bme;
773  }
774  }
775  }
776  GNUNET_free (old_map);
777 }
union MapEntry * map
All of our buckets.
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...
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
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.
unsigned int map_length
Length of the "map" array.
Entry in the map.
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...
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.
An entry in the hash map with just a pointer to the key.
An entry in the hash map with the full key.
struct BigMapEntry * bme
Variant used if map entries contain the full key.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function: