/*
- * Copyright (c) 2008, 2009 Nicira Networks.
+ * Copyright (c) 2008, 2009, 2010 Nicira Networks.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
#include <assert.h>
#include <stdint.h>
#include "coverage.h"
+#include "random.h"
#include "util.h"
/* Initializes 'hmap' as an empty hash table. */
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;
}
}
resize(hmap, new_mask);
}
}
+
+/* Adjusts 'hmap' to compensate for 'old_node' having moved position in memory
+ * to 'node' (e.g. due to realloc()). */
+void
+hmap_node_moved(struct hmap *hmap,
+ struct hmap_node *old_node, struct hmap_node *node)
+{
+ struct hmap_node **bucket = &hmap->buckets[node->hash & hmap->mask];
+ while (*bucket != old_node) {
+ bucket = &(*bucket)->next;
+ }
+ *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;
+}