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

Functions
struct GNUNET_CONTAINER_MultiHashMap32 *	GNUNET_CONTAINER_multihashmap32_create (unsigned int len)
	Create a multi hash map.
void	GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 *map)
	Destroy a hash map.
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.
unsigned int	GNUNET_CONTAINER_multihashmap32_size (const struct GNUNET_CONTAINER_MultiHashMap32 *map)
	Get the number of key-value pairs in the map.
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.
int	GNUNET_CONTAINER_multihashmap32_iterate (struct GNUNET_CONTAINER_MultiHashMap32 *map, GNUNET_CONTAINER_MultiHashMapIterator32Callback it, void *it_cls)
	Iterate over all entries in the map.
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.
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.
int	GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key)
	Remove all entries for the given key from the map.
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).
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.
static void	grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
	Grow the given map to a more appropriate size.
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.
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.
struct GNUNET_CONTAINER_MultiHashMap32Iterator *	GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map)
	Create an iterator for a multihashmap.
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.
void	GNUNET_CONTAINER_multihashmap32_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
	Destroy a multihashmap iterator.

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.

{
  uint32_t key;
 
  void *value;
 
  struct MapEntry *next;
};
 
struct GNUNET_CONTAINER_MultiHashMap32
{
  struct MapEntry **map;
 
  unsigned int size;
 
  unsigned int map_length;
 
  unsigned int modification_counter;
 
  struct MapEntry *next_cache[NEXT_CACHE_SIZE];
 
  unsigned int next_cache_off;
};
 
 
struct GNUNET_CONTAINER_MultiHashMap32Iterator
{
  struct MapEntry *me;
 
  unsigned int idx;
 
  unsigned int modification_counter;
 
  const struct GNUNET_CONTAINER_MultiHashMap32 *map;
};
 
 
struct GNUNET_CONTAINER_MultiHashMap32 *
GNUNET_CONTAINER_multihashmap32_create (unsigned int len)
{
  struct GNUNET_CONTAINER_MultiHashMap32 *ret;
 
  GNUNET_assert (len > 0);
  ret = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32);
  ret->map = GNUNET_malloc_large (len * sizeof(struct MapEntry *));
  if (NULL == ret->map)
  {
    GNUNET_free (ret);
    return NULL;
  }
  ret->map_length = len;
  return ret;
}
 
 
void
GNUNET_CONTAINER_multihashmap32_destroy (
  struct GNUNET_CONTAINER_MultiHashMap32 *map)
{
  struct MapEntry *e;
 
  for (unsigned int i = 0; i < map->map_length; i++)
  {
    while (NULL != (e = map->map[i]))
    {
      map->map[i] = e->next;
      GNUNET_free (e);
    }
  }
  GNUNET_free (map->map);
  GNUNET_free (map);
}
 
 
static unsigned int
idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m, const uint32_t key)
{
  GNUNET_assert (NULL != m);
  return ((unsigned int) key) % m->map_length;
}
 
 
unsigned int
GNUNET_CONTAINER_multihashmap32_size (
  const struct GNUNET_CONTAINER_MultiHashMap32 *map)
{
  return map->size;
}
 
 
void *
GNUNET_CONTAINER_multihashmap32_get (
  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
  uint32_t key)
{
  struct MapEntry *e;
 
  e = map->map[idx_of (map, key)];
  while (NULL != e)
  {
    if (key == e->key)
      return e->value;
    e = e->next;
  }
  return NULL;
}
 
 
int
GNUNET_CONTAINER_multihashmap32_iterate (
  struct GNUNET_CONTAINER_MultiHashMap32 *map,
  GNUNET_CONTAINER_MultiHashMapIterator32Callback it,
  void *it_cls)
{
  int count;
  struct MapEntry **ce;
 
  count = 0;
  GNUNET_assert (NULL != map);
  ce = &map->next_cache[map->next_cache_off];
  GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
  for (unsigned int i = 0; i < map->map_length; i++)
  {
    struct MapEntry *e;
 
    *ce = map->map[i];
    while (NULL != (e = *ce))
    {
      *ce = e->next;
      if (NULL != it)
      {
        if (GNUNET_OK != it (it_cls, e->key, e->value))
        {
          GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
          return GNUNET_SYSERR;
        }
      }
      count++;
    }
  }
  GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
  return count;
}
 
 
static void
update_next_cache (struct GNUNET_CONTAINER_MultiHashMap32 *map,
                   const struct MapEntry *me)
{
  for (unsigned int i = 0; i < map->next_cache_off; i++)
    if (map->next_cache[i] == me)
      map->next_cache[i] = me->next;
}
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multihashmap32_remove (
  struct GNUNET_CONTAINER_MultiHashMap32 *map,
  uint32_t key,
  const void *value)
{
  struct MapEntry *e;
  struct MapEntry *p;
  unsigned int i;
 
  map->modification_counter++;
 
  i = idx_of (map, key);
  p = NULL;
  e = map->map[i];
  while (e != NULL)
  {
    if ((key == e->key) && (value == e->value))
    {
      if (p == NULL)
        map->map[i] = e->next;
      else
        p->next = e->next;
      update_next_cache (map, e);
      GNUNET_free (e);
      map->size--;
      return GNUNET_YES;
    }
    p = e;
    e = e->next;
  }
  return GNUNET_NO;
}
 
 
int
GNUNET_CONTAINER_multihashmap32_remove_all (
  struct GNUNET_CONTAINER_MultiHashMap32 *map,
  uint32_t key)
{
  struct MapEntry *e;
  struct MapEntry *p;
  unsigned int i;
  int ret;
 
  map->modification_counter++;
 
  ret = 0;
  i = idx_of (map, key);
  p = NULL;
  e = map->map[i];
  while (e != NULL)
  {
    if (key == e->key)
    {
      if (p == NULL)
        map->map[i] = e->next;
      else
        p->next = e->next;
      update_next_cache (map, e);
      GNUNET_free (e);
      map->size--;
      if (p == NULL)
        e = map->map[i];
      else
        e = p->next;
      ret++;
    }
    else
    {
      p = e;
      e = e->next;
    }
  }
  return ret;
}
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multihashmap32_contains (
  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
  uint32_t key)
{
  struct MapEntry *e;
 
  e = map->map[idx_of (map, key)];
  while (e != NULL)
  {
    if (key == e->key)
      return GNUNET_YES;
    e = e->next;
  }
  return GNUNET_NO;
}
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multihashmap32_contains_value (
  const struct GNUNET_CONTAINER_MultiHashMap32 *map,
  uint32_t key,
  const void *value)
{
  struct MapEntry *e;
 
  e = map->map[idx_of (map, key)];
  while (e != NULL)
  {
    if ((key == e->key) && (e->value == value))
      return GNUNET_YES;
    e = e->next;
  }
  return GNUNET_NO;
}
 
 
static void
grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
{
  struct MapEntry **old_map;
  struct MapEntry **new_map;
  struct MapEntry *e;
  unsigned int old_len;
  unsigned int new_len;
  unsigned int idx;
 
  old_map = map->map;
  old_len = map->map_length;
  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(struct 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++)
  {
    while (NULL != (e = old_map[i]))
    {
      old_map[i] = e->next;
      idx = idx_of (map, e->key);
      e->next = new_map[idx];
      new_map[idx] = e;
    }
  }
  GNUNET_free (old_map);
}
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multihashmap32_put (
  struct GNUNET_CONTAINER_MultiHashMap32 *map,
  uint32_t key,
  void *value,
  enum GNUNET_CONTAINER_MultiHashMapOption opt)
{
  struct MapEntry *e;
  unsigned int i;
 
  i = idx_of (map, key);
  if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
      (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
  {
    e = map->map[i];
    while (e != NULL)
    {
      if (key == e->key)
      {
        if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
          return GNUNET_SYSERR;
        e->value = value;
        return GNUNET_NO;
      }
      e = e->next;
    }
  }
  if (map->size / 3 >= map->map_length / 4)
  {
    grow (map);
    i = idx_of (map, key);
  }
  e = GNUNET_new (struct MapEntry);
  e->key = key;
  e->value = value;
  e->next = map->map[i];
  map->map[i] = e;
  map->size++;
  return GNUNET_OK;
}
 
 
int
GNUNET_CONTAINER_multihashmap32_get_multiple (
  struct GNUNET_CONTAINER_MultiHashMap32 *map,
  uint32_t key,
  GNUNET_CONTAINER_MultiHashMapIterator32Callback it,
  void *it_cls)
{
  int count;
  struct MapEntry *e;
  struct MapEntry **ce;
 
  count = 0;
  ce = &map->next_cache[map->next_cache_off];
  GNUNET_assert (++map->next_cache_off < NEXT_CACHE_SIZE);
 
  *ce = map->map[idx_of (map, key)];
  while (NULL != (e = *ce))
  {
    *ce = e->next;
    if (key != e->key)
      continue;
    if ((NULL != it) && (GNUNET_OK != it (it_cls, key, e->value)))
    {
      GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
      return GNUNET_SYSERR;
    }
    count++;
  }
  GNUNET_assert (--map->next_cache_off < NEXT_CACHE_SIZE);
  return count;
}
 
 
struct GNUNET_CONTAINER_MultiHashMap32Iterator *
GNUNET_CONTAINER_multihashmap32_iterator_create (
  const struct GNUNET_CONTAINER_MultiHashMap32 *map)
{
  struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter;
 
  iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32Iterator);
  iter->map = map;
  iter->modification_counter = map->modification_counter;
  iter->me = map->map[0];
  return iter;
}
 
 
enum GNUNET_GenericReturnValue
GNUNET_CONTAINER_multihashmap32_iterator_next (
  struct GNUNET_CONTAINER_MultiHashMap32Iterator *iter,
  uint32_t *key,
  const void **value)
{
  /* make sure the map has not been modified */
  GNUNET_assert (iter->modification_counter == iter->map->modification_counter);
 
  /* look for the next entry, skipping empty buckets */
  while (1)
  {
    if (iter->idx >= iter->map->map_length)
      return GNUNET_NO;
    if (NULL != iter->me)
    {
      if (NULL != key)
        *key = iter->me->key;
      if (NULL != value)
        *value = iter->me->value;
      iter->me = iter->me->next;
      return GNUNET_YES;
    }
    iter->idx += 1;
    if (iter->idx < iter->map->map_length)
      iter->me = iter->map->map[iter->idx];
  }
}
 
 
void
GNUNET_CONTAINER_multihashmap32_iterator_destroy (
  struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
{
  GNUNET_free (iter);
}
 
 
/* end of container_multihashmap.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

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

Returns

offset into the "map" array of "m"

Definition at line 192 of file container_multihashmap32.c.

{
  GNUNET_assert (NULL != m);
  return ((unsigned int) key) % m->map_length;
}

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

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

Definition at line 270 of file container_multihashmap32.c.

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

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

map	the hash map to grow

Definition at line 400 of file container_multihashmap32.c.

{
  struct MapEntry **old_map;
  struct MapEntry **new_map;
  struct MapEntry *e;
  unsigned int old_len;
  unsigned int new_len;
  unsigned int idx;
 
  old_map = map->map;
  old_len = map->map_length;
  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(struct 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++)
  {
    while (NULL != (e = old_map[i]))
    {
      old_map[i] = e->next;
      idx = idx_of (map, e->key);
      e->next = new_map[idx];
      new_map[idx] = e;
    }
  }
  GNUNET_free (old_map);
}

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: