-fix

[oweals/gnunet.git] / src / util / container_multihashmap.c

diff --git a/src/util/container_multihashmap.c b/src/util/container_multihashmap.c
index ada98251cc5b5967c69a5ab3cd9a7dbaf63d1844..567ee12516dde93f97081103944d4c614856f25c 100644 (file)
--- a/src/util/container_multihashmap.c
+++ b/src/util/container_multihashmap.c
@@ -1,10 +1,10 @@
 /*
      This file is part of GNUnet.
 /*
      This file is part of GNUnet.

-     (C) 2008 Christian Grothoff (and other contributing authors)
+     (C) 2008, 2012 Christian Grothoff (and other contributing authors)

 
      GNUnet is free software; you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published
 
      GNUnet is free software; you can redistribute it and/or modify
      it under the terms of the GNU General Public License as published

-     by the Free Software Foundation; either version 2, or (at your
+     by the Free Software Foundation; either version 3, or (at your

      option) any later version.
 
      GNUnet is distributed in the hope that it will be useful, but
      option) any later version.
 
      GNUnet is distributed in the hope that it will be useful, but


@@ -24,23 +24,40 @@
  */
 
 #include "platform.h"
  */
 
 #include "platform.h"

-#include "gnunet_common.h"
-#include "gnunet_container_lib.h"
-#include "gnunet_crypto_lib.h"
+#include "gnunet_util_lib.h"

 
 #define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
 
 /**
 
 #define LOG(kind,...) GNUNET_log_from (kind, "util", __VA_ARGS__)
 
 /**

- * An entry in the hash map.
+ * An entry in the hash map with the full key.

  */
  */

-struct MapEntry
+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;
 
   /**
    * 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.
    */
   /**
    * Value of the entry.
    */


@@ -49,20 +66,42 @@ struct MapEntry
   /**
    * If there is a hash collision, we create a linked list.
    */
   /**
    * If there is a hash collision, we create a linked list.
    */

-  struct MapEntry *next;
+  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
 {
 /**
  * Internal representation of the hash map.
  */
 struct GNUNET_CONTAINER_MultiHashMap
 {

-

   /**
    * All of our buckets.
    */
   /**
    * All of our buckets.
    */

-  struct MapEntry **map;
+  union MapEntry *map;

 
   /**
    * Number of entries in the map.
 
   /**
    * Number of entries in the map.


@@ -73,6 +112,47 @@ struct GNUNET_CONTAINER_MultiHashMap
    * Length of the "map" array.
    */
   unsigned int map_length;
    * 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;

 };
 
 
 };
 
 


@@ -80,18 +160,29 @@ struct GNUNET_CONTAINER_MultiHashMap
  * Create a multi hash map.
  *
  * @param len initial size (map will grow as needed)
  * 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 *
  * @return NULL on error
  */
 struct GNUNET_CONTAINER_MultiHashMap *

-GNUNET_CONTAINER_multihashmap_create (unsigned int len)
+GNUNET_CONTAINER_multihashmap_create (unsigned int len,
+                                     int do_not_copy_keys)

 {
 {

-  struct GNUNET_CONTAINER_MultiHashMap *ret;
+  struct GNUNET_CONTAINER_MultiHashMap *map;

 
   GNUNET_assert (len > 0);
 
   GNUNET_assert (len > 0);

-  ret = GNUNET_malloc (sizeof (struct GNUNET_CONTAINER_MultiHashMap));
-  ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *));
-  ret->map_length = len;
-  return ret;
+  map = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap);
+  map->map = GNUNET_malloc (len * sizeof (union MapEntry));
+  map->map_length = len;
+  map->use_small_entries = do_not_copy_keys;
+  return map;

 }
 
 
 }
 
 


@@ -106,14 +197,36 @@ GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap
                                        *map)
 {
   unsigned int i;
                                        *map)
 {
   unsigned int i;

-  struct MapEntry *e;
+  union MapEntry me;

 
   for (i = 0; i < map->map_length; i++)
   {
 
   for (i = 0; i < map->map_length; i++)
   {

-    while (NULL != (e = map->map[i]))
+    me = map->map[i];
+    if (map->use_small_entries)

     {
     {

-      map->map[i] = e->next;
-      GNUNET_free (e);
+      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.bme = NULL;

     }
   }
   GNUNET_free (map->map);
     }
   }
   GNUNET_free (map->map);


@@ -124,16 +237,16 @@ GNUNET_CONTAINER_multihashmap_destroy (struct GNUNET_CONTAINER_MultiHashMap
 /**
  * Compute the index of the bucket for the given key.
  *
 /**
  * Compute the index of the bucket for the given key.
  *

- * @param m hash map for which to compute the index
+ * @param map hash map for which to compute the index

  * @param key what key should the index be computed for
  * @param key what key should the index be computed for

- * @return offset into the "map" array of "m"
+ * @return offset into the "map" array of "map"

  */
 static unsigned int
  */
 static unsigned int

-idx_of (const struct GNUNET_CONTAINER_MultiHashMap *m,
-        const struct GNUNET_HashCode * key)
+idx_of (const struct GNUNET_CONTAINER_MultiHashMap *map,
+        const struct GNUNET_HashCode *key)

 {
 {

-  GNUNET_assert (m != NULL);
-  return (*(unsigned int *) key) % m->map_length;
+  GNUNET_assert (map != NULL);
+  return (*(unsigned int *) key) % map->map_length;

 }
 
 
 }
 
 


@@ -163,16 +276,26 @@ GNUNET_CONTAINER_multihashmap_size (const struct GNUNET_CONTAINER_MultiHashMap
  */
 void *
 GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap
  */
 void *
 GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap

-                                   *map, const struct GNUNET_HashCode * key)
+                                   *map, const struct GNUNET_HashCode *key)

 {
 {

-  struct MapEntry *e;
+  union MapEntry me;
+
+  me = map->map[idx_of (map, key)];
+  if (map->use_small_entries)
+  {
+    struct SmallMapEntry *sme;

 
 

-  e = map->map[idx_of (map, key)];
-  while (e != NULL)
+    for (sme = me.sme; NULL != sme; sme = sme->next)
+      if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode)))
+       return sme->value;
+  }
+  else

   {
   {

-    if (0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode)))
-      return e->value;
-    e = e->next;
+    struct BigMapEntry *bme;
+
+    for (bme = me.bme; NULL != bme; bme = bme->next)
+      if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode)))
+       return bme->value;

   }
   return NULL;
 }
   }
   return NULL;
 }


@@ -183,9 +306,9 @@ GNUNET_CONTAINER_multihashmap_get (const struct GNUNET_CONTAINER_MultiHashMap
  *
  * @param map the map
  * @param it function to call on each entry
  *
  * @param map the map
  * @param it function to call on each entry

- * @param it_cls extra argument to it
+ * @param it_cls extra argument to @a it

  * @return the number of key value pairs processed,
  * @return the number of key value pairs processed,

- *         GNUNET_SYSERR if it aborted iteration
+ *         #GNUNET_SYSERR if it aborted iteration

  */
 int
 GNUNET_CONTAINER_multihashmap_iterate (const struct
  */
 int
 GNUNET_CONTAINER_multihashmap_iterate (const struct


@@ -195,25 +318,48 @@ GNUNET_CONTAINER_multihashmap_iterate (const struct
 {
   int count;
   unsigned int i;
 {
   int count;
   unsigned int i;

-  struct MapEntry *e;
-  struct MapEntry *n;
+  union MapEntry me;

   struct GNUNET_HashCode kc;
 
   count = 0;
   struct GNUNET_HashCode kc;
 
   count = 0;

-  GNUNET_assert (map != NULL);
+  GNUNET_assert (NULL != map);

   for (i = 0; i < map->map_length; i++)
   {
   for (i = 0; i < map->map_length; i++)
   {

-    n = map->map[i];
-    while (NULL != (e = n))
+    me = map->map[i];
+    if (map->use_small_entries)

     {
     {

-      n = e->next;
-      if (NULL != it)
+      struct SmallMapEntry *sme;
+      struct SmallMapEntry *nxt;
+
+      nxt = me.sme;
+      while (NULL != (sme = nxt))

       {
       {

-        kc = e->key;
-        if (GNUNET_OK != it (it_cls, &kc, e->value))
-          return GNUNET_SYSERR;
+       nxt = sme->next;
+       if (NULL != it)
+       {
+         if (GNUNET_OK != it (it_cls, sme->key, sme->value))
+           return GNUNET_SYSERR;
+       }
+       count++;
+      }
+    }
+    else
+    {
+      struct BigMapEntry *bme;
+      struct BigMapEntry *nxt;
+
+      nxt = me.bme;
+      while (NULL != (bme = nxt))
+      {
+       nxt = bme->next;
+       if (NULL != it)
+       {
+         kc = bme->key;
+         if (GNUNET_OK != it (it_cls, &kc, bme->value))
+           return GNUNET_SYSERR;
+       }
+       count++;

       }
       }

-      count++;

     }
   }
   return count;
     }
   }
   return count;


@@ -228,35 +374,64 @@ GNUNET_CONTAINER_multihashmap_iterate (const struct
  * @param map the map
  * @param key key of the key-value pair
  * @param value value of the key-value pair
  * @param map the map
  * @param key key of the key-value pair
  * @param value value of the key-value pair

- * @return GNUNET_YES on success, GNUNET_NO if the key-value pair
+ * @return #GNUNET_YES on success, #GNUNET_NO if the key-value pair

  *  is not in the map
  */
 int
 GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,
  *  is not in the map
  */
 int
 GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,

-                                      const struct GNUNET_HashCode * key, void *value)
+                                      const struct GNUNET_HashCode *key,
+                                     const void *value)

 {
 {

-  struct MapEntry *e;
-  struct MapEntry *p;
+  union MapEntry me;

   unsigned int i;
 
   unsigned int i;
 

+  map->modification_counter++;
+

   i = idx_of (map, key);
   i = idx_of (map, key);

-  p = NULL;
-  e = map->map[i];
-  while (e != NULL)
+  me = map->map[i];
+  if (map->use_small_entries)

   {
   {

-    if ((0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode))) &&
-        (value == e->value))
+    struct SmallMapEntry *sme;
+    struct SmallMapEntry *p;
+
+    p = NULL;
+    for (sme = me.sme; NULL != sme; sme = sme->next)

     {
     {

-      if (p == NULL)
-        map->map[i] = e->next;
-      else
-        p->next = e->next;
-      GNUNET_free (e);
-      map->size--;
-      return GNUNET_YES;
+      if ((0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) &&
+         (value == sme->value))
+      {
+       if (NULL == p)
+         map->map[i].sme = sme->next;
+       else
+         p->next = sme->next;
+       GNUNET_free (sme);
+       map->size--;
+       return GNUNET_YES;
+      }
+      p = sme;
+    }
+  }
+  else
+  {
+    struct BigMapEntry *bme;
+    struct BigMapEntry *p;
+
+    p = NULL;
+    for (bme = me.bme; NULL != bme; bme = bme->next)
+    {
+      if ((0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) &&
+         (value == bme->value))
+      {
+       if (NULL == p)
+         map->map[i].bme = bme->next;
+       else
+         p->next = bme->next;
+       GNUNET_free (bme);
+       map->size--;
+       return GNUNET_YES;
+      }
+      p = bme;

     }
     }

-    p = e;
-    e = e->next;

   }
   return GNUNET_NO;
 }
   }
   return GNUNET_NO;
 }


@@ -272,37 +447,75 @@ GNUNET_CONTAINER_multihashmap_remove (struct GNUNET_CONTAINER_MultiHashMap *map,
  */
 int
 GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap
  */
 int
 GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap

-                                          *map, const struct GNUNET_HashCode * key)
+                                          *map, const struct GNUNET_HashCode *key)

 {
 {

-  struct MapEntry *e;
-  struct MapEntry *p;
+  union MapEntry me;

   unsigned int i;
   int ret;
 
   unsigned int i;
   int ret;
 

+  map->modification_counter++;
+

   ret = 0;
   i = idx_of (map, key);
   ret = 0;
   i = idx_of (map, key);

-  p = NULL;
-  e = map->map[i];
-  while (e != NULL)
+  me = map->map[i];
+  if (map->use_small_entries)

   {
   {

-    if (0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode)))
+    struct SmallMapEntry *sme;
+    struct SmallMapEntry *p;
+
+    p = NULL;
+    sme = me.sme;
+    while (NULL != sme)

     {
     {

-      if (p == NULL)
-        map->map[i] = e->next;
-      else
-        p->next = e->next;
-      GNUNET_free (e);
-      map->size--;
-      if (p == NULL)
-        e = map->map[i];
+      if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode)))
+      {
+       if (NULL == p)
+         map->map[i].sme = sme->next;
+       else
+         p->next = sme->next;
+       GNUNET_free (sme);
+       map->size--;
+       if (NULL == p)
+         sme = map->map[i].sme;
+       else
+         sme = p->next;
+       ret++;
+      }

       else
       else

-        e = p->next;
-      ret++;
+      {
+       p = sme;
+       sme = sme->next;
+      }

     }
     }

-    else
+  }
+  else
+  {
+    struct BigMapEntry *bme;
+    struct BigMapEntry *p;
+
+    p = NULL;
+    bme = me.bme;
+    while (NULL != bme)

     {
     {

-      p = e;
-      e = e->next;
+      if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode)))
+      {
+       if (NULL == p)
+         map->map[i].bme = bme->next;
+       else
+         p->next = bme->next;
+       GNUNET_free (bme);
+       map->size--;
+       if (NULL == p)
+         bme = map->map[i].bme;
+       else
+         bme = p->next;
+       ret++;
+      }
+      else
+      {
+       p = bme;
+       bme = bme->next;
+      }

     }
   }
   return ret;
     }
   }
   return ret;


@@ -315,22 +528,32 @@ GNUNET_CONTAINER_multihashmap_remove_all (struct GNUNET_CONTAINER_MultiHashMap
  *
  * @param map the map
  * @param key the key to test if a value exists for it
  *
  * @param map the map
  * @param key the key to test if a value exists for it

- * @return GNUNET_YES if such a value exists,
- *         GNUNET_NO if not
+ * @return #GNUNET_YES if such a value exists,
+ *         #GNUNET_NO if not

  */
 int
 GNUNET_CONTAINER_multihashmap_contains (const struct
                                         GNUNET_CONTAINER_MultiHashMap *map,
  */
 int
 GNUNET_CONTAINER_multihashmap_contains (const struct
                                         GNUNET_CONTAINER_MultiHashMap *map,

-                                        const struct GNUNET_HashCode * key)
+                                        const struct GNUNET_HashCode *key)

 {
 {

-  struct MapEntry *e;
+  union MapEntry me;

 
 

-  e = map->map[idx_of (map, key)];
-  while (e != NULL)
+  me = map->map[idx_of (map, key)];
+  if (map->use_small_entries)

   {
   {

-    if (0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode)))
-      return GNUNET_YES;
-    e = e->next;
+    struct SmallMapEntry *sme;
+
+    for (sme = me.sme; NULL != sme; sme = sme->next)
+      if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode)))
+       return GNUNET_YES;
+  }
+  else
+  {
+    struct BigMapEntry *bme;
+
+    for (bme = me.bme; NULL != bme; bme = bme->next)
+      if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode)))
+       return GNUNET_YES;

   }
   return GNUNET_NO;
 }
   }
   return GNUNET_NO;
 }


@@ -343,24 +566,35 @@ GNUNET_CONTAINER_multihashmap_contains (const struct
  * @param map the map
  * @param key the key to test if a value exists for it
  * @param value value to test for
  * @param map the map
  * @param key the key to test if a value exists for it
  * @param value value to test for

- * @return GNUNET_YES if such a value exists,
- *         GNUNET_NO if not
+ * @return #GNUNET_YES if such a value exists,
+ *         #GNUNET_NO if not

  */
 int
 GNUNET_CONTAINER_multihashmap_contains_value (const struct
                                               GNUNET_CONTAINER_MultiHashMap
  */
 int
 GNUNET_CONTAINER_multihashmap_contains_value (const struct
                                               GNUNET_CONTAINER_MultiHashMap

-                                              *map, const struct GNUNET_HashCode * key,
+                                              *map, const struct GNUNET_HashCode *key,

                                               const void *value)
 {
                                               const void *value)
 {

-  struct MapEntry *e;
+  union MapEntry me;
+
+  me = map->map[idx_of (map, key)];
+  if (map->use_small_entries)
+  {
+    struct SmallMapEntry *sme;

 
 

-  e = map->map[idx_of (map, key)];
-  while (e != NULL)
+    for (sme = me.sme; NULL != sme; sme = sme->next)
+      if ( (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode))) &&
+          (sme->value == value) )
+       return GNUNET_YES;
+  }
+  else

   {
   {

-    if ((0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode))) &&
-        (e->value == value))
-      return GNUNET_YES;
-    e = e->next;
+    struct BigMapEntry *bme;
+
+    for (bme = me.bme; NULL != bme; bme = bme->next)
+      if ( (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode))) &&
+          (bme->value == value) )
+       return GNUNET_YES;

   }
   return GNUNET_NO;
 }
   }
   return GNUNET_NO;
 }


@@ -374,28 +608,46 @@ GNUNET_CONTAINER_multihashmap_contains_value (const struct
 static void
 grow (struct GNUNET_CONTAINER_MultiHashMap *map)
 {
 static void
 grow (struct GNUNET_CONTAINER_MultiHashMap *map)
 {

-  struct MapEntry **old_map;
-  struct MapEntry **new_map;
-  struct MapEntry *e;
+  union MapEntry *old_map;
+  union MapEntry *new_map;

   unsigned int old_len;
   unsigned int new_len;
   unsigned int idx;
   unsigned int i;
 
   unsigned int old_len;
   unsigned int new_len;
   unsigned int idx;
   unsigned int i;
 

+  map->modification_counter++;
+

   old_map = map->map;
   old_len = map->map_length;
   new_len = old_len * 2;
   old_map = map->map;
   old_len = map->map_length;
   new_len = old_len * 2;

-  new_map = GNUNET_malloc (sizeof (struct MapEntry *) * new_len);
+  new_map = GNUNET_malloc (sizeof (union MapEntry) * new_len);

   map->map_length = new_len;
   map->map = new_map;
   for (i = 0; i < old_len; i++)
   {
   map->map_length = new_len;
   map->map = new_map;
   for (i = 0; i < old_len; i++)
   {

-    while (NULL != (e = old_map[i]))
+    if (map->use_small_entries)
+    {
+      struct SmallMapEntry *sme;
+
+      while (NULL != (sme = old_map[i].sme))
+      {
+       old_map[i].sme = sme->next;
+       idx = idx_of (map, sme->key);
+       sme->next = new_map[idx].sme;
+       new_map[idx].sme = sme;
+      }
+    }
+    else

     {
     {

-      old_map[i] = e->next;
-      idx = idx_of (map, &e->key);
-      e->next = new_map[idx];
-      new_map[idx] = e;
+      struct BigMapEntry *bme;
+
+      while (NULL != (bme = old_map[i].bme))
+      {
+       old_map[i].bme = bme->next;
+       idx = idx_of (map, &bme->key);
+       bme->next = new_map[idx].bme;
+       new_map[idx].bme = bme;
+      }

     }
   }
   GNUNET_free (old_map);
     }
   }
   GNUNET_free (old_map);


@@ -409,34 +661,50 @@ grow (struct GNUNET_CONTAINER_MultiHashMap *map)
  * @param key key to use
  * @param value value to use
  * @param opt options for put
  * @param key key to use
  * @param value value to use
  * @param opt options for put

- * @return GNUNET_OK on success,
- *         GNUNET_NO if a value was replaced (with REPLACE)
- *         GNUNET_SYSERR if UNIQUE_ONLY was the option and the
+ * @return #GNUNET_OK on success,
+ *         #GNUNET_NO if a value was replaced (with REPLACE)
+ *         #GNUNET_SYSERR if UNIQUE_ONLY was the option and the

  *                       value already exists
  */
 int
 GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
  *                       value already exists
  */
 int
 GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,

-                                   const struct GNUNET_HashCode * key, void *value,
+                                   const struct GNUNET_HashCode *key,
+                                  void *value,

                                    enum GNUNET_CONTAINER_MultiHashMapOption opt)
 {
                                    enum GNUNET_CONTAINER_MultiHashMapOption opt)
 {

-  struct MapEntry *e;
+  union MapEntry me;

   unsigned int i;
 
   i = idx_of (map, key);
   if ((opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) &&
       (opt != GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
   {
   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)
+    me = map->map[i];
+    if (map->use_small_entries)

     {
     {

-      if (0 == memcmp (key, &e->key, sizeof (struct GNUNET_HashCode)))
-      {
-        if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
-          return GNUNET_SYSERR;
-        e->value = value;
-        return GNUNET_NO;
-      }
-      e = e->next;
+      struct SmallMapEntry *sme;
+
+      for (sme = me.sme; NULL != sme; sme = sme->next)
+       if (0 == memcmp (key, sme->key, sizeof (struct GNUNET_HashCode)))
+       {
+         if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
+           return GNUNET_SYSERR;
+         sme->value = value;
+         return GNUNET_NO;
+       }
+    }
+    else
+    {
+      struct BigMapEntry *bme;
+
+      for (bme = me.bme; NULL != bme; bme = bme->next)
+       if (0 == memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode)))
+       {
+         if (opt == GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)
+           return GNUNET_SYSERR;
+         bme->value = value;
+         return GNUNET_NO;
+       }

     }
   }
   if (map->size / 3 >= map->map_length / 4)
     }
   }
   if (map->size / 3 >= map->map_length / 4)


@@ -444,11 +712,26 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
     grow (map);
     i = idx_of (map, key);
   }
     grow (map);
     i = idx_of (map, key);
   }

-  e = GNUNET_malloc (sizeof (struct MapEntry));
-  e->key = *key;
-  e->value = value;
-  e->next = map->map[i];
-  map->map[i] = e;
+  if (map->use_small_entries)
+  {
+    struct SmallMapEntry *sme;
+
+    sme = GNUNET_new (struct SmallMapEntry);
+    sme->key = key;
+    sme->value = value;
+    sme->next = map->map[i].sme;
+    map->map[i].sme = sme;
+  }
+  else
+  {
+    struct BigMapEntry *bme;
+
+    bme = GNUNET_new (struct BigMapEntry);
+    bme->key = *key;
+    bme->value = value;
+    bme->next = map->map[i].bme;
+    map->map[i].bme = bme;
+  }

   map->size++;
   return GNUNET_OK;
 }
   map->size++;
   return GNUNET_OK;
 }


@@ -462,32 +745,149 @@ GNUNET_CONTAINER_multihashmap_put (struct GNUNET_CONTAINER_MultiHashMap *map,
  * @param it function to call on each entry
  * @param it_cls extra argument to it
  * @return the number of key value pairs processed,
  * @param it function to call on each entry
  * @param it_cls extra argument to it
  * @return the number of key value pairs processed,

- *         GNUNET_SYSERR if it aborted iteration
+ *         #GNUNET_SYSERR if it aborted iteration

  */
 int
 GNUNET_CONTAINER_multihashmap_get_multiple (const struct
                                             GNUNET_CONTAINER_MultiHashMap *map,
  */
 int
 GNUNET_CONTAINER_multihashmap_get_multiple (const struct
                                             GNUNET_CONTAINER_MultiHashMap *map,

-                                            const struct GNUNET_HashCode * key,
+                                            const struct GNUNET_HashCode *key,

                                             GNUNET_CONTAINER_HashMapIterator it,
                                             void *it_cls)
 {
   int count;
                                             GNUNET_CONTAINER_HashMapIterator it,
                                             void *it_cls)
 {
   int count;

-  struct MapEntry *e;
-  struct MapEntry *n;
+  union MapEntry me;

 
   count = 0;
 
   count = 0;

-  n = map->map[idx_of (map, key)];
-  while (NULL != (e = n))
+  me = map->map[idx_of (map, key)];
+  if (map->use_small_entries)

   {
   {

-    n = e->next;
-    if (0 != memcmp (key, &e->key, sizeof (struct GNUNET_HashCode)))
-      continue;
-    if ((it != NULL) && (GNUNET_OK != it (it_cls, key, e->value)))
-      return GNUNET_SYSERR;
-    count++;
+    struct SmallMapEntry *sme;
+    struct SmallMapEntry *nxt;
+
+    nxt = me.sme;
+    while (NULL != (sme = nxt))
+    {
+      nxt = sme->next;
+      if (0 != memcmp (key, sme->key, sizeof (struct GNUNET_HashCode)))
+       continue;
+      if ((it != NULL) && (GNUNET_OK != it (it_cls, key, sme->value)))
+       return GNUNET_SYSERR;
+      count++;
+    }
+  }
+  else
+  {
+    struct BigMapEntry *bme;
+    struct BigMapEntry *nxt;
+
+    nxt = me.bme;
+    while (NULL != (bme = nxt))
+    {
+      nxt = bme->next;
+      if (0 != memcmp (key, &bme->key, sizeof (struct GNUNET_HashCode)))
+       continue;
+      if ((it != NULL) && (GNUNET_OK != it (it_cls, key, bme->value)))
+       return GNUNET_SYSERR;
+      count++;
+    }

   }
   return count;
 }
 
 
   }
   return count;
 }
 
 

+/**
+ * Create an iterator for a 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.
+ *
+ * @param map the map to create an iterator for
+ * @return an iterator over the given multihashmap 'map'
+ */
+struct GNUNET_CONTAINER_MultiHashMapIterator *
+GNUNET_CONTAINER_multihashmap_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap *map)
+{
+  struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
+
+  iter = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMapIterator);
+  iter->map = map;
+  iter->modification_counter = map->modification_counter;
+  iter->me = map->map[0];
+  return iter;
+}
+
+
+/**
+ * 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.
+ *
+ * @param iter the iterator to get the next element from
+ * @param key pointer to store the key in, can be NULL
+ * @param value pointer to store the value in, can be NULL
+ * @return #GNUNET_YES we returned an element,
+ *         #GNUNET_NO if we are out of elements
+ */
+int
+GNUNET_CONTAINER_multihashmap_iterator_next (struct GNUNET_CONTAINER_MultiHashMapIterator *iter,
+                                             struct GNUNET_HashCode *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 (GNUNET_YES == iter->map->use_small_entries)
+    {
+      if (NULL != iter->me.sme)
+      {
+        if (NULL != key)
+          *key = *iter->me.sme->key;
+        if (NULL != value)
+          *value = iter->me.sme->value;
+        iter->me.sme = iter->me.sme->next;
+        return GNUNET_YES;
+      }
+    }
+    else
+    {
+      if (NULL != iter->me.bme)
+      {
+        if (NULL != key)
+          *key = iter->me.bme->key;
+        if (NULL != value)
+          *value = iter->me.bme->value;
+        iter->me.bme = iter->me.bme->next;
+        return GNUNET_YES;
+      }
+    }
+    iter->idx += 1;
+    if (iter->idx < iter->map->map_length)
+      iter->me = iter->map->map[iter->idx];
+  }
+}
+
+
+/**
+ * Destroy a multihashmap iterator.
+ *
+ * @param iter the iterator to destroy
+ */
+void
+GNUNET_CONTAINER_multihashmap_iterator_destroy (struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
+{
+  GNUNET_free (iter);
+}
+
+

 /* end of container_multihashmap.c */
 /* end of container_multihashmap.c */