GNUnet 0.22.1
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_util_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_MultiHashMapIterator32Callback 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 me, 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_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...
 
enum GNUNET_GenericReturnValue 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...
 
enum GNUNET_GenericReturnValue 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...
 
enum GNUNET_GenericReturnValue 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_MultiHashMapIterator32Callback 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...
 
enum GNUNET_GenericReturnValue 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 32 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 42 of file container_multihashmap32.c.

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 192 of file container_multihashmap32.c.

193{
194 GNUNET_assert (NULL != m);
195 return ((unsigned int) key) % m->map_length;
196}
static struct GNUNET_ARM_MonitorHandle * m
Monitor connection with ARM.
Definition: gnunet-arm.c:103
struct GNUNET_HashCode key
The key used in the DHT.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.

References GNUNET_assert, key, and m.

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().

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 me, 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
methe entry that is about to be free'd

Definition at line 270 of file container_multihashmap32.c.

272{
273 for (unsigned int i = 0; i < map->next_cache_off; i++)
274 if (map->next_cache[i] == me)
275 map->next_cache[i] = me->next;
276}
static GNUNET_NETWORK_STRUCT_END struct GNUNET_PeerIdentity me
Our own peer identity.
static struct GNUNET_CONTAINER_MultiPeerMap * map
Peermap of PeerIdentities to "struct PeerEntry" (for fast lookup).
Definition: peer.c:63
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...

References map, me, GNUNET_CONTAINER_MultiPeerMap::next_cache, and GNUNET_CONTAINER_MultiPeerMap::next_cache_off.

Referenced by GNUNET_CONTAINER_multihashmap32_remove(), and GNUNET_CONTAINER_multihashmap32_remove_all().

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 400 of file container_multihashmap32.c.

401{
402 struct MapEntry **old_map;
403 struct MapEntry **new_map;
404 struct MapEntry *e;
405 unsigned int old_len;
406 unsigned int new_len;
407 unsigned int idx;
408
409 old_map = map->map;
410 old_len = map->map_length;
411 new_len = old_len * 2;
412 if (0 == new_len) /* 2^31 * 2 == 0 */
413 new_len = old_len; /* never use 0 */
414 if (new_len == old_len)
415 return; /* nothing changed */
416 new_map = GNUNET_malloc_large (new_len * sizeof(struct MapEntry *));
417 if (NULL == new_map)
418 return; /* grow not possible */
420 map->map_length = new_len;
421 map->map = new_map;
422 for (unsigned int i = 0; i < old_len; i++)
423 {
424 while (NULL != (e = old_map[i]))
425 {
426 old_map[i] = e->next;
427 idx = idx_of (map, e->key);
428 e->next = new_map[idx];
429 new_map[idx] = e;
430 }
431 }
432 GNUNET_free (old_map);
433}
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_malloc_large(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
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...
union MapEntry * map
All of our buckets.
Entry in the map.
uint32_t key
Key for the entry.
struct MapEntry * next
If there is a hash collision, we create a linked list.

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

Referenced by GNUNET_CONTAINER_multihashmap32_put().

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