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

a version of hash map implemented in container_multihashmap.c but with uint32_t as keys More...

#include "platform.h"
#include "gnunet_container_lib.h"
Include dependency graph for container_multihashmap32.c:

Go to the source code of this file.

Data Structures

union  MapEntry
 Entry in the map. More...
 
struct  GNUNET_CONTAINER_MultiHashMap32
 Internal representation of the hash map. More...
 
struct  GNUNET_CONTAINER_MultiHashMap32Iterator
 Cursor into a multihashmap. More...
 

Macros

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

Functions

struct GNUNET_CONTAINER_MultiHashMap32GNUNET_CONTAINER_multihashmap32_create (unsigned int len)
 Create a multi hash map. More...
 
void GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 *map)
 Destroy a hash map. More...
 
static unsigned int idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, const uint32_t key)
 Compute the index of the bucket for the given key. More...
 
unsigned int GNUNET_CONTAINER_multihashmap32_size (const struct GNUNET_CONTAINER_MultiHashMap32 *map)
 Get the number of key-value pairs in the map. More...
 
void * GNUNET_CONTAINER_multihashmap32_get (const struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key)
 Given a key find a value in the map matching the key. More...
 
int GNUNET_CONTAINER_multihashmap32_iterate (struct GNUNET_CONTAINER_MultiHashMap32 *map, GNUNET_CONTAINER_MulitHashMapIterator32Callback it, void *it_cls)
 Iterate over all entries in the map. More...
 
static void update_next_cache (struct GNUNET_CONTAINER_MultiHashMap32 *map, const struct MapEntry *me)
 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...
 
int GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key, const void *value)
 Remove the given key-value pair from the map. More...
 
int GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key)
 Remove all entries for the given key from the map. More...
 
int GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key)
 Check if the map contains any value under the given key (including values that are NULL). More...
 
int GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key, const void *value)
 Check if the map contains the given value under the given key. More...
 
static void grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
 Grow the given map to a more appropriate size. More...
 
int GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
 Store a key-value pair in the map. More...
 
int GNUNET_CONTAINER_multihashmap32_get_multiple (struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key, GNUNET_CONTAINER_MulitHashMapIterator32Callback it, void *it_cls)
 Iterate over all entries in the map that match a particular key. More...
 
struct GNUNET_CONTAINER_MultiHashMap32IteratorGNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map)
 Create an iterator for a multihashmap. More...
 
int GNUNET_CONTAINER_multihashmap32_iterator_next (struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter, uint32_t *key, const void **value)
 Retrieve the next element from the hash map at the iterator's position. More...
 
void GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
 Destroy a multihashmap iterator. More...
 

Detailed Description

a version of hash map implemented in container_multihashmap.c but with uint32_t as keys

Author
Christian Grothoff
Sree Harsha Totakura

Definition in file container_multihashmap32.c.

Macro Definition Documentation

◆ LOG

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

Definition at line 31 of file container_multihashmap32.c.

◆ NEXT_CACHE_SIZE

#define NEXT_CACHE_SIZE   16

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

Should be totally excessive, but if violated we die.

Definition at line 41 of file container_multihashmap32.c.

Referenced by GNUNET_CONTAINER_multihashmap32_get_multiple(), and GNUNET_CONTAINER_multihashmap32_iterate().

Function Documentation

◆ idx_of()

static unsigned int idx_of ( const struct GNUNET_CONTAINER_MultiHashMap32 m,
const uint32_t  key 
)
static

Compute the index of the bucket for the given key.

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

Definition at line 191 of file container_multihashmap32.c.

References GNUNET_assert, and GNUNET_CONTAINER_MultiHashMap32::map_length.

Referenced by GNUNET_CONTAINER_multihashmap32_contains(), GNUNET_CONTAINER_multihashmap32_contains_value(), GNUNET_CONTAINER_multihashmap32_get(), GNUNET_CONTAINER_multihashmap32_get_multiple(), GNUNET_CONTAINER_multihashmap32_put(), GNUNET_CONTAINER_multihashmap32_remove(), GNUNET_CONTAINER_multihashmap32_remove_all(), and grow().

192 {
193  GNUNET_assert (NULL != m);
194  return ((unsigned int) key) % m->map_length;
195 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct GNUNET_HashCode key
The key used in the DHT.
unsigned int map_length
Length of the map array.
Here is the caller graph for this function:

◆ update_next_cache()

static void update_next_cache ( struct GNUNET_CONTAINER_MultiHashMap32 map,
const struct MapEntry me 
)
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 294 of file container_multihashmap32.c.

References MapEntry::next, GNUNET_CONTAINER_MultiHashMap32::next_cache, and GNUNET_CONTAINER_MultiHashMap32::next_cache_off.

Referenced by GNUNET_CONTAINER_multihashmap32_remove(), and GNUNET_CONTAINER_multihashmap32_remove_all().

296 {
297  for (unsigned int i = 0; i < map->next_cache_off; i++)
298  if (map->next_cache[i] == me)
299  map->next_cache[i] = me->next;
300 }
struct MapEntry * next_cache[16]
Map entries indicating iteration positions currently in use by GNUNET_CONTAINER_multihashmap_get_mult...
struct MapEntry * 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.
Here is the caller graph for this function:

◆ grow()

static void grow ( struct GNUNET_CONTAINER_MultiHashMap32 map)
static

Grow the given map to a more appropriate size.

Parameters
mapthe hash map to grow

Definition at line 462 of file container_multihashmap32.c.

References e, GNUNET_free, GNUNET_malloc_large, idx_of(), MapEntry::key, GNUNET_CONTAINER_MultiHashMap32::map, GNUNET_CONTAINER_MultiHashMap32::map_length, GNUNET_CONTAINER_MultiHashMap32::modification_counter, and MapEntry::next.

Referenced by GNUNET_CONTAINER_multihashmap32_put().

463 {
464  struct MapEntry **old_map;
465  struct MapEntry **new_map;
466  struct MapEntry *e;
467  unsigned int old_len;
468  unsigned int new_len;
469  unsigned int idx;
470 
471  old_map = map->map;
472  old_len = map->map_length;
473  new_len = old_len * 2;
474  if (0 == new_len) /* 2^31 * 2 == 0 */
475  new_len = old_len; /* never use 0 */
476  if (new_len == old_len)
477  return; /* nothing changed */
478  new_map = GNUNET_malloc_large (new_len * sizeof(struct MapEntry *));
479  if (NULL == new_map)
480  return; /* grow not possible */
481  map->modification_counter++;
482  map->map_length = new_len;
483  map->map = new_map;
484  for (unsigned int i = 0; i < old_len; i++)
485  {
486  while (NULL != (e = old_map[i]))
487  {
488  old_map[i] = e->next;
489  idx = idx_of (map, e->key);
490  e->next = new_map[idx];
491  new_map[idx] = e;
492  }
493  }
494  GNUNET_free (old_map);
495 }
struct MapEntry ** map
All of our buckets.
uint32_t key
Key for the entry.
static struct Experiment * e
#define GNUNET_malloc_large(size)
Wrapper around malloc.
Entry in the map.
unsigned int map_length
Length of the map array.
unsigned int modification_counter
Counts the destructive modifications (grow, remove) to the map, so that iterators can check if they a...
struct MapEntry * next
If there is a hash collision, we create a linked list.
static unsigned int idx_of(const struct GNUNET_CONTAINER_MultiHashMap32 *m, const uint32_t key)
Compute the index of the bucket for the given key.
#define GNUNET_free(ptr)
Wrapper around free.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ GNUNET_CONTAINER_multihashmap32_iterator_create()

struct GNUNET_CONTAINER_MultiHashMap32Iterator* GNUNET_CONTAINER_multihashmap32_iterator_create ( const struct GNUNET_CONTAINER_MultiHashMap32 map)

Create an iterator for a multihashmap.

Create an iterator for a 32-bit multihashmap.

The iterator can be used to retrieve all the elements in the multihashmap one by one, without having to handle all elements at once (in contrast to GNUNET_CONTAINER_multihashmap_iterate()). Note that the iterator can not be used anymore if elements have been removed from 'map' after the creation of the iterator, or 'map' has been destroyed. Adding elements to 'map' may result in skipped or repeated elements.

Parameters
mapthe map to create an iterator for
Returns
an iterator over the given multihashmap map

Definition at line 608 of file container_multihashmap32.c.

References GNUNET_new, GNUNET_CONTAINER_MultiHashMap32::map, map, GNUNET_CONTAINER_MultiHashMap32Iterator::map, GNUNET_CONTAINER_MultiHashMap32Iterator::me, GNUNET_CONTAINER_MultiHashMap32::modification_counter, and GNUNET_CONTAINER_MultiHashMap32Iterator::modification_counter.

610 {
612 
614  iter->map = map;
616  iter->me = map->map[0];
617  return iter;
618 }
struct MapEntry ** map
All of our buckets.
struct MapEntry * me
Position in the bucket idx.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
unsigned int modification_counter
Modification counter as observed on the map when the iterator was created.
static struct GNUNET_CONTAINER_MultiPeerMap * map
Handle to the map used to store old latency values for peers.
unsigned int modification_counter
Counts the destructive modifications (grow, remove) to the map, so that iterators can check if they a...
const struct GNUNET_CONTAINER_MultiHashMap32 * map
Map that we are iterating over.

◆ GNUNET_CONTAINER_multihashmap32_iterator_next()

int GNUNET_CONTAINER_multihashmap32_iterator_next ( struct GNUNET_CONTAINER_MultiHashMap32Iterator iter,
uint32_t *  key,
const void **  value 
)

Retrieve the next element from the hash map at the iterator's position.

If there are no elements left, GNUNET_NO is returned, and 'key' and 'value' are not modified. This operation is only allowed if no elements have been removed from the multihashmap since the creation of 'iter', and the map has not been destroyed. Adding elements may result in repeating or skipping elements.

Parameters
iterthe iterator to get the next element from
keypointer to store the key in, can be NULL
valuepointer to store the value in, can be NULL
Returns
GNUNET_YES we returned an element, GNUNET_NO if we are out of elements

Definition at line 636 of file container_multihashmap32.c.

References GNUNET_assert, GNUNET_NO, GNUNET_YES, GNUNET_CONTAINER_MultiHashMap32Iterator::idx, MapEntry::key, GNUNET_CONTAINER_MultiHashMap32::map, GNUNET_CONTAINER_MultiHashMap32Iterator::map, GNUNET_CONTAINER_MultiHashMap32::map_length, GNUNET_CONTAINER_MultiHashMap32Iterator::me, GNUNET_CONTAINER_MultiHashMap32::modification_counter, GNUNET_CONTAINER_MultiHashMap32Iterator::modification_counter, MapEntry::next, and MapEntry::value.

640 {
641  /* make sure the map has not been modified */
643 
644  /* look for the next entry, skipping empty buckets */
645  while (1)
646  {
647  if (iter->idx >= iter->map->map_length)
648  return GNUNET_NO;
649  if (NULL != iter->me)
650  {
651  if (NULL != key)
652  *key = iter->me->key;
653  if (NULL != value)
654  *value = iter->me->value;
655  iter->me = iter->me->next;
656  return GNUNET_YES;
657  }
658  iter->idx += 1;
659  if (iter->idx < iter->map->map_length)
660  iter->me = iter->map->map[iter->idx];
661  }
662 }
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct MapEntry ** map
All of our buckets.
uint32_t key
Key for the entry.
#define GNUNET_NO
Definition: gnunet_common.h:78
struct MapEntry * me
Position in the bucket idx.
unsigned int modification_counter
Modification counter as observed on the map when the iterator was created.
static char * value
Value of the record to add/remove.
void * value
Value of the entry.
struct GNUNET_HashCode key
The key used in the DHT.
unsigned int map_length
Length of the map array.
unsigned int modification_counter
Counts the destructive modifications (grow, remove) to the map, so that iterators can check if they a...
#define GNUNET_YES
Definition: gnunet_common.h:77
struct MapEntry * next
If there is a hash collision, we create a linked list.
unsigned int idx
Current bucket index.
const struct GNUNET_CONTAINER_MultiHashMap32 * map
Map that we are iterating over.

◆ GNUNET_CONTAINER_multihashmap32_iterator_destroy()

void GNUNET_CONTAINER_multihashmap32_iterator_destroy ( struct GNUNET_CONTAINER_MultiHashMapIterator iter)

Destroy a multihashmap iterator.

Destroy a 32-bit multihashmap iterator.

Parameters
iterthe iterator to destroy

Definition at line 671 of file container_multihashmap32.c.

References GNUNET_free.

673 {
674  GNUNET_free (iter);
675 }
#define GNUNET_free(ptr)
Wrapper around free.