1 files changed, 101 insertions, 58 deletions

diff --git a/src/util/container_multihashmap32.c b/src/util/container_multihashmap32.c
index daf5059b6..016dbabcc 100644
--- a/src/util/container_multihashmap32.c
+++ b/src/util/container_multihashmap32.c
@@ -28,6 +28,15 @@
 
 #define LOG(kind,...) GNUNET_log_from (kind, "util-container-multihashmap32", __VA_ARGS__)
 
+
+/**
+ * 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.
+ */
+#define NEXT_CACHE_SIZE 16
+
 /**
  * An entry in the hash map.
  */
@@ -68,7 +77,7 @@ struct GNUNET_CONTAINER_MultiHashMap32
   unsigned int size;
 
   /**
-   * Length of the "map" array.
+   * Length of the @e map array.
    */
   unsigned int map_length;
 
@@ -77,6 +86,19 @@ struct GNUNET_CONTAINER_MultiHashMap32
    * to the map, so that iterators can check if they are still valid.
    */
   unsigned int modification_counter;
+
+  /**
+   * Map entries indicating iteration positions currently
+   * in use by #GNUNET_CONTAINER_multihashmap_get_multiple().
+   * Only used up to @e next_cache_off.
+   */
+  struct MapEntry *next_cache[NEXT_CACHE_SIZE];
+
+  /**
+   * Offset of @e next_cache entries in use, must be smaller
+   * than #NEXT_CACHE_SIZE.
+   */
+  unsigned int next_cache_off;
 };
 
 
@@ -87,7 +109,7 @@ struct GNUNET_CONTAINER_MultiHashMap32
 struct GNUNET_CONTAINER_MultiHashMap32Iterator
 {
   /**
-   * Position in the bucket 'idx'
+   * Position in the bucket @e idx
    */
   struct MapEntry *me;
 
@@ -122,7 +144,8 @@ GNUNET_CONTAINER_multihashmap32_create (unsigned int len)
 
   GNUNET_assert (len > 0);
   ret = GNUNET_new (struct GNUNET_CONTAINER_MultiHashMap32);
-  ret->map = GNUNET_malloc (len * sizeof (struct MapEntry *));
+  ret->map = GNUNET_new_array (len,
+                               struct MapEntry *);
   ret->map_length = len;
   return ret;
 }
@@ -135,13 +158,11 @@ GNUNET_CONTAINER_multihashmap32_create (unsigned int len)
  * @param map the map
  */
 void
-GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32
-                                         *map)
+GNUNET_CONTAINER_multihashmap32_destroy (struct GNUNET_CONTAINER_MultiHashMap32 *map)
 {
-  unsigned int i;
   struct MapEntry *e;
 
-  for (i = 0; i < map->map_length; i++)
+  for (unsigned int i = 0; i < map->map_length; i++)
   {
     while (NULL != (e = map->map[i]))
     {
@@ -165,7 +186,7 @@ static unsigned int
 idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m,
         const uint32_t key)
 {
-  GNUNET_assert (m != NULL);
+  GNUNET_assert (NULL != m);
   return ((unsigned int) key) % m->map_length;
 }
 
@@ -177,8 +198,7 @@ idx_of (const struct GNUNET_CONTAINER_MultiHashMap32 *m,
  * @return the number of key value pairs
  */
 unsigned int
-GNUNET_CONTAINER_multihashmap32_size (const struct
-                                      GNUNET_CONTAINER_MultiHashMap32 *map)
+GNUNET_CONTAINER_multihashmap32_size (const struct GNUNET_CONTAINER_MultiHashMap32 *map)
 {
   return map->size;
 }
@@ -195,14 +215,13 @@ GNUNET_CONTAINER_multihashmap32_size (const struct
  *   key-value pairs with value NULL
  */
 void *
-GNUNET_CONTAINER_multihashmap32_get (const struct
-                                     GNUNET_CONTAINER_MultiHashMap32 *map,
+GNUNET_CONTAINER_multihashmap32_get (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
                                      uint32_t key)
 {
   struct MapEntry *e;
 
   e = map->map[idx_of (map, key)];
-  while (e != NULL)
+  while (NULL != e)
   {
     if (key == e->key)
       return e->value;
@@ -222,27 +241,30 @@ GNUNET_CONTAINER_multihashmap32_get (const struct
  *         #GNUNET_SYSERR if it aborted iteration
  */
 int
-GNUNET_CONTAINER_multihashmap32_iterate (const struct
-                                         GNUNET_CONTAINER_MultiHashMap32 *map,
-                                         GNUNET_CONTAINER_HashMapIterator32 it,
+GNUNET_CONTAINER_multihashmap32_iterate (struct GNUNET_CONTAINER_MultiHashMap32 *map,
+                                         GNUNET_CONTAINER_HashMapIterator32 it,
                                          void *it_cls)
 {
   int count;
-  unsigned int i;
-  struct MapEntry *e;
-  struct MapEntry *n;
+  struct MapEntry **ce;
 
   count = 0;
   GNUNET_assert (NULL != map);
-  for (i = 0; i < map->map_length; i++)
+  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++)
   {
-    n = map->map[i];
-    while (NULL != (e = n))
+    struct MapEntry *e;
+
+    *ce = map->map[i];
+    while (NULL != (e = *ce))
     {
-      n = e->next;
+      *ce = e->next;
       if (NULL != it)
       {
-        if (GNUNET_OK != it (it_cls, e->key, e->value))
+        if (GNUNET_OK != it (it_cls,
+                             e->key,
+                             e->value))
           return GNUNET_SYSERR;
       }
       count++;
@@ -253,6 +275,23 @@ GNUNET_CONTAINER_multihashmap32_iterate (const struct
 
 
 /**
+ * We are about to free() the @a bme, make sure it is not in
+ * the list of next values for any iterator in the @a map's next_cache.
+ *
+ * @param map the map to check
+ * @param bme the entry that is about to be free'd
+ */
+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;
+}
+
+
+/**
  * Remove the given key-value pair from the map.  Note that if the
  * key-value pair is in the map multiple times, only one of the pairs
  * will be removed.
@@ -260,13 +299,13 @@ GNUNET_CONTAINER_multihashmap32_iterate (const struct
  * @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_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32
-                                        *map,
-                                        uint32_t key, const void *value)
+GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32 *map,
+                                        uint32_t key,
+                                        const void *value)
 {
   struct MapEntry *e;
   struct MapEntry *p;
@@ -285,6 +324,8 @@ GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32
         map->map[i] = e->next;
       else
         p->next = e->next;
+      update_next_cache (map,
+                         e);
       GNUNET_free (e);
       map->size--;
       return GNUNET_YES;
@@ -305,9 +346,7 @@ GNUNET_CONTAINER_multihashmap32_remove (struct GNUNET_CONTAINER_MultiHashMap32
  * @return number of values removed
  */
 int
-GNUNET_CONTAINER_multihashmap32_remove_all (struct
-                                            GNUNET_CONTAINER_MultiHashMap32
-                                            *map,
+GNUNET_CONTAINER_multihashmap32_remove_all (struct GNUNET_CONTAINER_MultiHashMap32 *map,
                                             uint32_t key)
 {
   struct MapEntry *e;
@@ -329,6 +368,8 @@ GNUNET_CONTAINER_multihashmap32_remove_all (struct
         map->map[i] = e->next;
       else
         p->next = e->next;
+      update_next_cache (map,
+                         e);
       GNUNET_free (e);
       map->size--;
       if (p == NULL)
@@ -353,12 +394,11 @@ GNUNET_CONTAINER_multihashmap32_remove_all (struct
  *
  * @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_multihashmap32_contains (const struct
-                                          GNUNET_CONTAINER_MultiHashMap32 *map,
+GNUNET_CONTAINER_multihashmap32_contains (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
                                           uint32_t key)
 {
   struct MapEntry *e;
@@ -381,13 +421,11 @@ GNUNET_CONTAINER_multihashmap32_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
- * @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_multihashmap32_contains_value (const struct
-                                                GNUNET_CONTAINER_MultiHashMap32
-                                                *map,
+GNUNET_CONTAINER_multihashmap32_contains_value (const struct GNUNET_CONTAINER_MultiHashMap32 *map,
                                                 uint32_t key,
                                                 const void *value)
 {
@@ -418,17 +456,17 @@ grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
   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;
-  new_map = GNUNET_malloc (sizeof (struct MapEntry *) * new_len);
+  new_map = GNUNET_new_array (new_len,
+                              struct MapEntry *);
   map->map_length = new_len;
   map->map = new_map;
-  for (i = 0; i < old_len; i++)
+  for (unsigned int i = 0; i < old_len; i++)
   {
     while (NULL != (e = old_map[i]))
     {
@@ -449,9 +487,9 @@ grow (struct GNUNET_CONTAINER_MultiHashMap32 *map)
  * @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
@@ -501,29 +539,34 @@ GNUNET_CONTAINER_multihashmap32_put (struct GNUNET_CONTAINER_MultiHashMap32
  * @param map the map
  * @param key key that the entries must correspond to
  * @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,
  *         GNUNET_SYSERR if it aborted iteration
  */
 int
-GNUNET_CONTAINER_multihashmap32_get_multiple (const struct
-                                              GNUNET_CONTAINER_MultiHashMap32
-                                              *map, uint32_t key,
-                                              GNUNET_CONTAINER_HashMapIterator32
-                                              it, void *it_cls)
+GNUNET_CONTAINER_multihashmap32_get_multiple (struct GNUNET_CONTAINER_MultiHashMap32 *map,
+                                              uint32_t key,
+                                              GNUNET_CONTAINER_HashMapIterator32 it,
+                                              void *it_cls)
 {
   int count;
   struct MapEntry *e;
-  struct MapEntry *n;
+  struct MapEntry **ce;
 
   count = 0;
-  n = map->map[idx_of (map, key)];
-  while (NULL != (e = n))
+  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))
   {
-    n = e->next;
+    *ce = e->next;
     if (key != e->key)
       continue;
-    if ((it != NULL) && (GNUNET_OK != it (it_cls, key, e->value)))
+    if ( (NULL != it) &&
+         (GNUNET_OK != it (it_cls,
+                           key,
+                           e->value)) )
       return GNUNET_SYSERR;
     count++;
   }
@@ -541,7 +584,7 @@ GNUNET_CONTAINER_multihashmap32_get_multiple (const struct
  * result in skipped or repeated elements.
  *
  * @param map the map to create an iterator for
- * @return an iterator over the given multihashmap 'map'
+ * @return an iterator over the given multihashmap @a map
  */
 struct GNUNET_CONTAINER_MultiHashMap32Iterator *
 GNUNET_CONTAINER_multihashmap32_iterator_create (const struct GNUNET_CONTAINER_MultiHashMap32 *map)