X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=lib%2Fhmap.c;h=6bc5ea74bd79482897a353d5ad8361a7f360fe0c;hb=a23aab1fc2f66b63ba9b7e4b9c9a8f6d58c367d0;hp=d66cf271a27e492f3b030d0aeabdeffb241d49f2;hpb=63e60b866ffee6895e1772da2c48591ab2767aa7;p=openvswitch

diff --git a/lib/hmap.c b/lib/hmap.c
index d66cf271..6bc5ea74 100644
--- a/lib/hmap.c
+++ b/lib/hmap.c
@@ -18,7 +18,9 @@
 #include "hmap.h"
 #include <assert.h>
 #include <stdint.h>
+#include <string.h>
 #include "coverage.h"
+#include "random.h"
 #include "util.h"
 
 /* Initializes 'hmap' as an empty hash table. */
@@ -41,6 +43,22 @@ hmap_destroy(struct hmap *hmap)
     }
 }
 
+/* Removes all node from 'hmap', leaving it ready to accept more nodes.  Does
+ * not free memory allocated for 'hmap'.
+ *
+ * This function is appropriate when 'hmap' will soon have about as many
+ * elements as it before.  If 'hmap' will likely have fewer elements than
+ * before, use hmap_destroy() followed by hmap_clear() to save memory and
+ * iteration time. */
+void
+hmap_clear(struct hmap *hmap)
+{
+    if (hmap->n > 0) {
+        hmap->n = 0;
+        memset(hmap->buckets, 0, (hmap->mask + 1) * sizeof *hmap->buckets);
+    }
+}
+
 /* Exchanges hash maps 'a' and 'b'. */
 void
 hmap_swap(struct hmap *a, struct hmap *b)
@@ -48,11 +66,17 @@ hmap_swap(struct hmap *a, struct hmap *b)
     struct hmap tmp = *a;
     *a = *b;
     *b = tmp;
-    if (a->buckets == &b->one) {
-        a->buckets = &a->one;
-    }
-    if (b->buckets == &a->one) {
-        b->buckets = &b->one;
+    hmap_moved(a);
+    hmap_moved(b);
+}
+
+/* Adjusts 'hmap' to compensate for having moved position in memory (e.g. due
+ * to realloc()). */
+void
+hmap_moved(struct hmap *hmap)
+{
+    if (!hmap->mask) {
+        hmap->buckets = &hmap->one;
     }
 }
 
@@ -157,3 +181,35 @@ hmap_node_moved(struct hmap *hmap,
     *bucket = node;
 }
 
+/* Chooses and returns a randomly selected node from 'hmap', which must not be
+ * empty.
+ *
+ * I wouldn't depend on this algorithm to be fair, since I haven't analyzed it.
+ * But it does at least ensure that any node in 'hmap' can be chosen. */
+struct hmap_node *
+hmap_random_node(const struct hmap *hmap)
+{
+    struct hmap_node *bucket, *node;
+    size_t n, i;
+
+    /* Choose a random non-empty bucket. */
+    for (i = random_uint32(); ; i++) {
+        bucket = hmap->buckets[i & hmap->mask];
+        if (bucket) {
+            break;
+        }
+    }
+
+    /* Count nodes in bucket. */
+    n = 0;
+    for (node = bucket; node; node = node->next) {
+        n++;
+    }
+
+    /* Choose random node from bucket. */
+    i = random_range(n);
+    for (node = bucket; i-- > 0; node = node->next) {
+        continue;
+    }
+    return node;
+}