#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)
}
}
+/* 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)
*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;
+}