From a49b0f351926cf4376a58937a94e37426e3ae167 Mon Sep 17 00:00:00 2001
From: Christian Grothoff <christian@grothoff.org>
Date: Thu, 30 Apr 2015 07:29:31 +0000
Subject: [PATCH] adding GNUNET_CONTAINER_multipeermap_get_random

---
 src/include/gnunet_container_lib.h | 21 +++++++-
 src/util/container_multihashmap.c  |  3 +-
 src/util/container_multipeermap.c  | 78 +++++++++++++++++++++++++++++-
 3 files changed, 97 insertions(+), 5 deletions(-)

diff --git a/src/include/gnunet_container_lib.h b/src/include/gnunet_container_lib.h
index 1ecf4f52a..d8886c504 100644
--- a/src/include/gnunet_container_lib.h
+++ b/src/include/gnunet_container_lib.h
@@ -1,6 +1,6 @@
 /*
      This file is part of GNUnet.
-     Copyright (C) 2001-2013 Christian Grothoff (and other contributing authors)
+     Copyright (C) 2001-2015 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
@@ -857,7 +857,8 @@ GNUNET_CONTAINER_multihashmap_get_multiple (const struct GNUNET_CONTAINER_MultiH
 /**
  * @ingroup hashmap
  * Call @a it on a random value from the map, or not at all
- * if the map is empty.
+ * if the map is empty.  Note that this function has linear
+ * complexity (in the size of the map).
  *
  * @param map the map
  * @param it function to call on a random entry
@@ -1115,6 +1116,22 @@ GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiP
                                             void *it_cls);
 
 
+/**
+ * @ingroup hashmap
+ * Call @a it on a random value from the map, or not at all
+ * if the map is empty.  Note that this function has linear
+ * complexity (in the size of the map).
+ *
+ * @param map the map
+ * @param it function to call on a random entry
+ * @param it_cls extra argument to @a it
+ * @return the number of key value pairs processed, zero or one.
+ */
+unsigned int
+GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPeerMap *map,
+                                          GNUNET_CONTAINER_PeerMapIterator it,
+                                          void *it_cls);
+
 
 /* Version of multihashmap with 32 bit keys */
 
diff --git a/src/util/container_multihashmap.c b/src/util/container_multihashmap.c
index 80545176d..df6dd5704 100644
--- a/src/util/container_multihashmap.c
+++ b/src/util/container_multihashmap.c
@@ -841,7 +841,8 @@ GNUNET_CONTAINER_multihashmap_get_multiple (const struct
 /**
  * @ingroup hashmap
  * Call @a it on a random value from the map, or not at all
- * if the map is empty.
+ * if the map is empty. Note that this function has linear
+ * complexity (in the size of the map).
  *
  * @param map the map
  * @param it function to call on a random entry
diff --git a/src/util/container_multipeermap.c b/src/util/container_multipeermap.c
index bed9e6042..15517b92a 100644
--- a/src/util/container_multipeermap.c
+++ b/src/util/container_multipeermap.c
@@ -482,7 +482,7 @@ GNUNET_CONTAINER_multipeermap_remove_all (struct GNUNET_CONTAINER_MultiPeerMap
 	  sme = map->map[i].sme;
 	else
 	  sme = p->next;
-	ret++;	
+	ret++;
       }
       else
       {
@@ -645,7 +645,7 @@ grow (struct GNUNET_CONTAINER_MultiPeerMap *map)
       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;
@@ -797,6 +797,80 @@ GNUNET_CONTAINER_multipeermap_get_multiple (const struct GNUNET_CONTAINER_MultiP
 }
 
 
+/**
+ * @ingroup hashmap
+ * Call @a it on a random value from the map, or not at all
+ * if the map is empty.  Note that this function has linear
+ * complexity (in the size of the map).
+ *
+ * @param map the map
+ * @param it function to call on a random entry
+ * @param it_cls extra argument to @a it
+ * @return the number of key value pairs processed, zero or one.
+ */
+unsigned int
+GNUNET_CONTAINER_multipeermap_get_random (const struct GNUNET_CONTAINER_MultiPeerMap *map,
+                                          GNUNET_CONTAINER_PeerMapIterator it,
+                                          void *it_cls)
+{
+  unsigned int off;
+  unsigned int idx;
+  union MapEntry me;
+
+  if (0 == map->size)
+    return 0;
+  if (NULL == it)
+    return 1;
+  off = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
+                                  map->size);
+  for (idx = 0; idx < map->map_length; idx++)
+  {
+    me = map->map[idx];
+    if (map->use_small_entries)
+    {
+      struct SmallMapEntry *sme;
+      struct SmallMapEntry *nxt;
+
+      nxt = me.sme;
+      while (NULL != (sme = nxt))
+      {
+        nxt = sme->next;
+        if (0 == off)
+        {
+          if (GNUNET_OK != it (it_cls,
+                               sme->key,
+                               sme->value))
+            return GNUNET_SYSERR;
+          return 1;
+        }
+        off--;
+      }
+    }
+    else
+    {
+      struct BigMapEntry *bme;
+      struct BigMapEntry *nxt;
+
+      nxt = me.bme;
+      while (NULL != (bme = nxt))
+      {
+        nxt = bme->next;
+        if (0 == off)
+        {
+          if (GNUNET_OK != it (it_cls,
+                               &bme->key, bme->value))
+            return GNUNET_SYSERR;
+          return 1;
+        }
+        off--;
+      }
+    }
+  }
+  GNUNET_break (0);
+  return GNUNET_SYSERR;
+}
+
+
 /**
  * Create an iterator for a multipeermap.
  * The iterator can be used to retrieve all the elements in the multipeermap
-- 
2.25.1