[GNUnet-SVN] r28533 - in gnunet/src: include util

[gnunet]

Author: dold
Date: 2013-08-12 16:33:26 +0200 (Mon, 12 Aug 2013)
New Revision: 28533

Modified:
   gnunet/src/include/gnunet_container_lib.h
   gnunet/src/util/container_multihashmap.c
Log:
- external iterator for multihashmap


Modified: gnunet/src/include/gnunet_container_lib.h
===================================================================
--- gnunet/src/include/gnunet_container_lib.h   2013-08-12 14:12:49 UTC (rev 
28532)
+++ gnunet/src/include/gnunet_container_lib.h   2013-08-12 14:33:26 UTC (rev 
28533)
@@ -490,6 +490,12 @@
 struct GNUNET_CONTAINER_MultiHashMap;
 
 /**
+ * Opaque handle to an iterator over
+ * a multihashmap.
+ */
+struct GNUNET_CONTAINER_MultiHashMapIterator;
+
+/**
  * Options for storing values in the HashMap.
  */
 enum GNUNET_CONTAINER_MultiHashMapOption
@@ -691,6 +697,50 @@
 
 
 /**
+ * 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);
+
+
+/**
+ * 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, void 
**value);
+
+
+/**
+ * Destroy a multihashmap iterator.
+ *
+ * @param iter the iterator to destroy
+ */
+void
+GNUNET_CONTAINER_multihashmap_iterator_destroy (struct 
GNUNET_CONTAINER_MultiHashMapIterator *iter);
+
+
+/**
  * Iterate over all entries in the map that match a particular key.
  *
  * @param map the map

Modified: gnunet/src/util/container_multihashmap.c
===================================================================
--- gnunet/src/util/container_multihashmap.c    2013-08-12 14:12:49 UTC (rev 
28532)
+++ gnunet/src/util/container_multihashmap.c    2013-08-12 14:33:26 UTC (rev 
28533)
@@ -100,7 +100,6 @@
  */
 struct GNUNET_CONTAINER_MultiHashMap
 {
-
   /**
    * All of our buckets.
    */
@@ -121,10 +120,45 @@
    * 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)
@@ -353,6 +387,8 @@
   union MapEntry me;
   unsigned int i;
 
+  map->modification_counter++;
+
   i = idx_of (map, key);
   me = map->map[i];
   if (map->use_small_entries)
@@ -419,6 +455,8 @@
   unsigned int i;
   int ret;
 
+  map->modification_counter++;
+
   ret = 0;
   i = idx_of (map, key);
   me = map->map[i];
@@ -579,6 +617,8 @@
   unsigned int idx;
   unsigned int i;
 
+  map->modification_counter++;
+
   old_map = map->map;
   old_len = map->map_length;
   new_len = old_len * 2;
@@ -757,4 +797,96 @@
 }
 
 
+/**
+ * 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, void 
**value)
+{
+  /* make sure nobody modified the map */
+  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++;
+  }
+}
+
+
+/**
+ * Destroy a multihashmap iterator.
+ *
+ * @param iter the iterator to destroy
+ */
+void
+GNUNET_CONTAINER_multihashmap_enumerator_destroy (struct 
GNUNET_CONTAINER_MultiHashMapIterator *iter)
+{
+  GNUNET_free (iter);
+}
+
+
 /* end of container_multihashmap.c */