coverage: Make the coverage counters catalog program-specific.

[sliver-openvswitch.git] / lib / hmap.c

diff --git a/lib/hmap.c b/lib/hmap.c
index d66cf27..6b850fd 100644 (file)
--- a/lib/hmap.c
+++ b/lib/hmap.c
@@ -18,9 +18,16 @@
 #include "hmap.h"
 #include <assert.h>
 #include <stdint.h>
+#include <string.h>
 #include "coverage.h"
+#include "random.h"
 #include "util.h"
 
+COVERAGE_DEFINE(hmap_pathological);
+COVERAGE_DEFINE(hmap_expand);
+COVERAGE_DEFINE(hmap_shrink);
+COVERAGE_DEFINE(hmap_reserve);
+
 /* Initializes 'hmap' as an empty hash table. */
 void
 hmap_init(struct hmap *hmap)
@@ -41,6 +48,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 +71,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 +186,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;
+}