path: root/src/util/container_multihashmap.c

/*
     This file is part of GNUnet.
     Copyright (C) 2008, 2012 GNUnet e.V.

     GNUnet is free software: you can redistribute it and/or modify it
     under the terms of the GNU Affero General Public License as published
     by the Free Software Foundation, either version 3 of the License,
     or (at your option) any later version.

     GNUnet is distributed in the hope that it will be useful, but
     WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     Affero General Public License for more details.
    
     You should have received a copy of the GNU Affero General Public License
     along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/
/**
 * @file util/container_multihashmap.c
 * @brief hash map where the same key may be present multiple times
 * @author Christian Grothoff
 */

#include "platform.h"
#include "gnunet_container_lib.h"

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

/**
 * An entry in the hash map with the full key.
 */
struct BigMapEntry
{

  /**
   * Value of the entry.
   */
  void *value;

  /**
   * If there is a hash collision, we create a linked list.
   */
  struct BigMapEntry *next;

  /**
   * Key for the entry.
   */
  struct GNUNET_HashCode key;

};


/**
 * An entry in the hash map with just a pointer to the key.
 */
struct SmallMapEntry
{

  /**
   * Value of the entry.
   */
  void *value;

  /**
   * If there is a hash collision, we create a linked list.
   */
  struct SmallMapEntry *next;

  /**
   * Key for the entry.
   */
  const struct GNUNET_HashCode *key;

};


/**
 * Entry in the map.
 */
union MapEntry
{
  /**
   * Variant used if map entries only contain a pointer to the key.
   */
  struct SmallMapEntry *sme;

  /**
   * Variant used if map entries contain the full key.
   */
  struct BigMapEntry *bme;
};


/**
 * Internal representation of the hash map.
 */
struct GNUNET_CONTAINER_MultiHashMap
{
  /**
   * All of our buckets.
   */
  union MapEntry *map;

  /**
   * Number of entries in the map.
   */
  unsigned int size;

  /**
   * Length of the "map" array.
   */
  unsigned int map_length;

  /**
   * #GNUNET_NO if the map entries are of type 'struct BigMapEntry',
   * #GNUNET_YES if the map entries are of type 'struct SmallMapEntry'.
   */
  int use_small_entries;

  /**
   * Counts the destructive modifications (grow, remove)
   * to the map, so that iterators can check if they are still valid.
   */
  unsigned int modification_counter;
};


/**
 * Cursor into a multihashmap.
 * Allows to enumerate elements asynchronously.
 */
struct GNUNET_CONTAINER_MultiHashMapIterator
{
  /**
   * Position in the bucket 'idx'
   */
  union MapEntry me;

  /**
   * Current bucket index.
   */
  unsigned int idx;

  /**
   * Modification counter as observed on the map when the iterator
   * was created.
   */
  unsigned int modification_counter;

  /**
   * Map that we are iterating over.
   */
  const struct GNUNET_CONTAINER_MultiHashMap *map;
};


/**
 * Create a multi hash map.
 *
 * @param len initial size (map will grow as needed)
 * @param do_not_copy_keys #GNUNET_NO is always safe and should be used by default;
 *                         #GNUNET_YES means that on 'put', the 'key' does not have
 *                         to be copied as the destination of the pointer is
 *                         guaranteed to be life as long as the value is stored in
 *                         the hashmap.  This can significantly reduce memory
 *                         consumption, but of course is also a recipie for
 *                         heap corruption if the assumption is not true.  Only
 *                         use this if (1) memory use is important in this case and
 *                         (2) you have triple-checked that the invariant holds
 * @return NULL on error
 */
struct GNUNET_CONTAINER_MultiHashMap *
GNUNET_CONTAINER_multihashmap_create (unsigned int len,
				      int do_not_copy_keys)
{
  struct GNUNET_CONTAINER_MultiHashMap *hm;

  GNUNET_assert (len > 0);
  hm = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap);
  if (len * sizeof (union MapEntry) > GNUNET_MAX_MALLOC_CHECKED)
  {
    size_t s;
    /* application *explicitly* requested very large map, hopefully
       it checks the return value... */
    s = len * sizeof (union MapEntry);
    if ( (s / sizeof (union MapEntry)) != len)
      return NULL; /* integer overflow on multiplication */
    if (NULL == (hm->map = GNUNET_malloc_large (s)))
    {
      /* out of memory */
      GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
                  "Out of memory allocating large hash map (%u entries)\n",
                  len);
      GNUNET_free (hm);
      return NULL;
    }
  }
  else
  {
    hm->map = GNUNET_new_array (len,
                                union MapEntry);
  }
  hm->map_length = len;
  hm->use_small_entries = do_not_copy_keys;
  return hm;
}


/**
 * Destroy a hash map.  Will not free any values
 * stored in the hash map!
 *
 * @param map the map
 */
void
GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap
                                       *map)
{
  for (unsigned int i = 0; i < map->map_length; i++)
  {
    union MapEntry me;

    me = map->map[i];
    if (map->use_small_entries)
    {
      struct SmallMapEntry *sme;
      struct SmallMapEntry *nxt;

      nxt = me.sme;
      while (NULL != (sme = nxt))
      {
	nxt = sme->next;
	GNUNET_free (sme);
      }
      me.sme = NULL;
    }
    else
    {
      struct BigMapEntry *bme;
      struct BigMapEntry *nxt;

      nxt = me.bme;
      while (NULL != (bme = nxt))
      {
	nxt = bme->next;
	GNUNET_free (bme);
      }
      me