[ovs-dev] [PATCH] hindex: New data structure for hashed multimaps.
Ben Pfaff
blp at nicira.com
Mon Jun 17 20:57:18 UTC 2013
Signed-off-by: Ben Pfaff <blp at nicira.com>
---
lib/automake.mk | 4 +-
lib/hindex.c | 324 +++++++++++++++++++++++++++++++++++++++++++++++++++
lib/hindex.h | 165 ++++++++++++++++++++++++++
tests/automake.mk | 5 +
tests/library.at | 5 +
tests/test-hindex.c | 319 ++++++++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 821 insertions(+), 1 deletions(-)
create mode 100644 lib/hindex.c
create mode 100644 lib/hindex.h
create mode 100644 tests/test-hindex.c
diff --git a/lib/automake.mk b/lib/automake.mk
index bcaa1f8..64e4e5c 100644
--- a/lib/automake.mk
+++ b/lib/automake.mk
@@ -1,4 +1,4 @@
-# Copyright (C) 2009, 2010, 2011, 2012 Nicira, Inc.
+# Copyright (C) 2009, 2010, 2011, 2012, 2013 Nicira, Inc.
#
# Copying and distribution of this file, with or without modification,
# are permitted in any medium without royalty provided the copyright
@@ -57,6 +57,8 @@ lib_libopenvswitch_a_SOURCES = \
lib/flow.h \
lib/hash.c \
lib/hash.h \
+ lib/hindex.c \
+ lib/hindex.h \
lib/hmap.c \
lib/hmap.h \
lib/hmapx.c \
diff --git a/lib/hindex.c b/lib/hindex.c
new file mode 100644
index 0000000..dc0f1b7
--- /dev/null
+++ b/lib/hindex.c
@@ -0,0 +1,324 @@
+/*
+ * Copyright (c) 2013 Nicira, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <config.h>
+#include "hindex.h"
+#include "coverage.h"
+
+static bool hindex_node_is_body(const struct hindex_node *);
+static bool hindex_node_is_head(const struct hindex_node *);
+static void hindex_resize(struct hindex *, size_t new_mask);
+static size_t hindex_calc_mask(size_t capacity);
+
+COVERAGE_DEFINE(hindex_pathological);
+COVERAGE_DEFINE(hindex_expand);
+COVERAGE_DEFINE(hindex_shrink);
+COVERAGE_DEFINE(hindex_reserve);
+
+/* Initializes 'hindex' as an empty hash index. */
+void
+hindex_init(struct hindex *hindex)
+{
+ hindex->buckets = &hindex->one;
+ hindex->one = NULL;
+ hindex->mask = 0;
+ hindex->n_unique = 0;
+}
+
+/* Frees memory reserved by 'hindex'. It is the client's responsibility to
+ * free the nodes themselves, if necessary. */
+void
+hindex_destroy(struct hindex *hindex)
+{
+ if (hindex && hindex->buckets != &hindex->one) {
+ free(hindex->buckets);
+ }
+}
+
+/* Removes all node from 'hindex', leaving it ready to accept more nodes. Does
+ * not free memory allocated for 'hindex'.
+ *
+ * This function is appropriate when 'hindex' will soon have about as many
+ * elements as it before. If 'hindex' will likely have fewer elements than
+ * before, use hindex_destroy() followed by hindex_clear() to save memory and
+ * iteration time. */
+void
+hindex_clear(struct hindex *hindex)
+{
+ if (hindex->n_unique > 0) {
+ hindex->n_unique = 0;
+ memset(hindex->buckets, 0,
+ (hindex->mask + 1) * sizeof *hindex->buckets);
+ }
+}
+
+/* Exchanges hash indexes 'a' and 'b'. */
+void
+hindex_swap(struct hindex *a, struct hindex *b)
+{
+ struct hindex tmp = *a;
+ *a = *b;
+ *b = tmp;
+ hindex_moved(a);
+ hindex_moved(b);
+}
+
+/* Adjusts 'hindex' to compensate for having moved position in memory (e.g. due
+ * to realloc()). */
+void
+hindex_moved(struct hindex *hindex)
+{
+ if (!hindex->mask) {
+ hindex->buckets = &hindex->one;
+ }
+}
+
+/* Expands 'hindex', if necessary, to optimize the performance of searches. */
+void
+hindex_expand(struct hindex *hindex)
+{
+ size_t new_mask = hindex_calc_mask(hindex->n_unique);
+ if (new_mask > hindex->mask) {
+ COVERAGE_INC(hindex_expand);
+ hindex_resize(hindex, new_mask);
+ }
+}
+
+/* Shrinks 'hindex', if necessary, to optimize the performance of iteration. */
+void
+hindex_shrink(struct hindex *hindex)
+{
+ size_t new_mask = hindex_calc_mask(hindex->n_unique);
+ if (new_mask < hindex->mask) {
+ COVERAGE_INC(hindex_shrink);
+ hindex_resize(hindex, new_mask);
+ }
+}
+
+/* Expands 'hindex', if necessary, to optimize the performance of searches when
+ * it has up to 'n' unique hashes. (But iteration will be slow in a hash index
+ * whose allocated capacity is much higher than its current number of
+ * nodes.) */
+void
+hindex_reserve(struct hindex *hindex, size_t n)
+{
+ size_t new_mask = hindex_calc_mask(n);
+ if (new_mask > hindex->mask) {
+ COVERAGE_INC(hindex_reserve);
+ hindex_resize(hindex, new_mask);
+ }
+}
+
+/* Inserts 'node', with the given 'hash', into 'hindex'. Never automatically
+ * expands 'hindex' (use hindex_insert() instead if you want that). */
+void
+hindex_insert_fast(struct hindex *hindex,
+ struct hindex_node *node, size_t hash)
+{
+ struct hindex_node *head = hindex_node_with_hash(hindex, hash);
+ if (head) {
+ /* 'head' is an existing head with hash == 'hash'.
+ * Insert 'node' as a body node just below 'head'. */
+ node->s = head->s;
+ node->d = head;
+ if (node->s) {
+ node->s->d = node;
+ }
+ head->s = node;
+ } else {
+ /* No existing node has hash 'hash'. Insert 'node' as a new head in
+ * its bucket. */
+ struct hindex_node **bucket = &hindex->buckets[hash & hindex->mask];
+ node->s = NULL;
+ node->d = *bucket;
+ *bucket = node;
+ hindex->n_unique++;
+ }
+ node->hash = hash;
+}
+
+/* Inserts 'node', with the given 'hash', into 'hindex', and expands 'hindex'
+ * if necessary to optimize search performance. */
+void
+hindex_insert(struct hindex *hindex, struct hindex_node *node, size_t hash)
+{
+ hindex_insert_fast(hindex, node, hash);
+ if (hindex->n_unique / 2 > hindex->mask) {
+ hindex_expand(hindex);
+ }
+}
+
+/* Removes 'node' from 'hindex'. Does not shrink the hash index; call
+ * hindex_shrink() directly if desired. */
+void
+hindex_remove(struct hindex *hindex, struct hindex_node *node)
+{
+ if (!hindex_node_is_head(node)) {
+ node->d->s = node->s;
+ if (node->s) {
+ node->s->d = node->d;
+ }
+ } else {
+ struct hindex_node **head;
+
+ for (head = &hindex->buckets[node->hash & hindex->mask];
+ (*head)->hash != node->hash;
+ head = &(*head)->d)
+ {
+ continue;
+ }
+
+ if (node->s) {
+ *head = node->s;
+ node->s->d = node->d;
+ } else {
+ *head = node->d;
+ hindex->n_unique--;
+ }
+ }
+}
+
+/* Helper functions. */
+
+/* Returns true if 'node', which must be inserted into an hindex, is a "body"
+ * node, that is, it is not reachable from a bucket by following zero or more
+ * 'd' pointers. Returns false otherwise. */
+static bool
+hindex_node_is_body(const struct hindex_node *node)
+{
+ return node->d && node->d->hash == node->hash;
+}
+
+/* Returns true if 'node', which must be inserted into an hindex, is a "head"
+ * node, that is, if it is reachable from a bucket by following zero or more
+ * 'd' pointers. Returns false if 'node' is a body node (and therefore one
+ * must follow at least one 's' pointer to reach it). */
+static bool
+hindex_node_is_head(const struct hindex_node *node)
+{
+ return !hindex_node_is_body(node);
+}
+
+/* Reallocates 'hindex''s array of buckets to use bitwise mask 'new_mask'. */
+static void
+hindex_resize(struct hindex *hindex, size_t new_mask)
+{
+ struct hindex tmp;
+ size_t i;
+
+ ovs_assert(is_pow2(new_mask + 1));
+ ovs_assert(new_mask != SIZE_MAX);
+
+ hindex_init(&tmp);
+ if (new_mask) {
+ tmp.buckets = xmalloc(sizeof *tmp.buckets * (new_mask + 1));
+ tmp.mask = new_mask;
+ for (i = 0; i <= tmp.mask; i++) {
+ tmp.buckets[i] = NULL;
+ }
+ }
+ for (i = 0; i <= hindex->mask; i++) {
+ struct hindex_node *node, *next;
+ int count;
+
+ count = 0;
+ for (node = hindex->buckets[i]; node; node = next) {
+ struct hindex_node **head = &tmp.buckets[node->hash & tmp.mask];
+
+ next = node->d;
+ node->d = *head;
+ *head = node;
+ count++;
+ }
+ if (count > 5) {
+ COVERAGE_INC(hindex_pathological);
+ }
+ }
+ tmp.n_unique = hindex->n_unique;
+ hindex_swap(hindex, &tmp);
+ hindex_destroy(&tmp);
+}
+
+/* Returns the bitwise mask to use in struct hindex to support 'capacity'
+ * hindex_nodes with unique hashes. */
+static size_t
+hindex_calc_mask(size_t capacity)
+{
+ size_t mask = capacity / 2;
+ mask |= mask >> 1;
+ mask |= mask >> 2;
+ mask |= mask >> 4;
+ mask |= mask >> 8;
+ mask |= mask >> 16;
+#if SIZE_MAX > UINT32_MAX
+ mask |= mask >> 32;
+#endif
+
+ /* If we need to dynamically allocate buckets we might as well allocate at
+ * least 4 of them. */
+ mask |= (mask & 1) << 1;
+
+ return mask;
+}
+
+/* Returns the head node in 'hindex' with the given 'hash', or a null pointer
+ * if no nodes have that hash value. */
+struct hindex_node *
+hindex_node_with_hash(const struct hindex *hindex, size_t hash)
+{
+ struct hindex_node *node = hindex->buckets[hash & hindex->mask];
+
+ while (node && node->hash != hash) {
+ node = node->d;
+ }
+ return node;
+}
+
+static struct hindex_node *
+hindex_next__(const struct hindex *hindex, size_t start)
+{
+ size_t i;
+ for (i = start; i <= hindex->mask; i++) {
+ struct hindex_node *node = hindex->buckets[i];
+ if (node) {
+ return node;
+ }
+ }
+ return NULL;
+}
+
+/* Returns the first node in 'hindex', in arbitrary order, or a null pointer if
+ * 'hindex' is empty. */
+struct hindex_node *
+hindex_first(const struct hindex *hindex)
+{
+ return hindex_next__(hindex, 0);
+}
+
+/* Returns the next node in 'hindex' following 'node', in arbitrary order, or a
+ * null pointer if 'node' is the last node in 'hindex'.
+ *
+ * If the hash index has been reallocated since 'node' was visited, some nodes
+ * may be skipped or visited twice. (Removing 'node' from the hash index does
+ * not prevent calling this function, since node->next is preserved, although
+ * freeing 'node' of course does.) */
+struct hindex_node *
+hindex_next(const struct hindex *hindex, const struct hindex_node *node)
+{
+ return (node->s ? node->s
+ : node->d && node->d->hash != node->hash ? node->d
+ : hindex_next__(hindex, (node->hash & hindex->mask) + 1));
+}
diff --git a/lib/hindex.h b/lib/hindex.h
new file mode 100644
index 0000000..8511056
--- /dev/null
+++ b/lib/hindex.h
@@ -0,0 +1,165 @@
+/*
+ * Copyright (c) 2013 Nicira, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef HINDEX_H
+#define HINDEX_H 1
+
+/* Hashed multimap.
+ *
+ * hindex is a hash table data structure that gracefully handles duplicates.
+ * With a high-quality hash function, insertion, deletion, and search are O(1)
+ * expected time, regardless of the number of duplicates for a given key. */
+
+#include <stdbool.h>
+#include <stdlib.h>
+#include "util.h"
+
+/* A hash index node, to embed inside the data structure being indexed.
+ *
+ * Nodes are linked together like this (the boxes are labeled with hash
+ * values):
+ *
+ * +--------+ d +--------+ d +--------+ d
+ * bucket---> | 6 |---->| 20 |---->| 15 |---->null
+ * +-|------+ +-|------+ +-|------+
+ * | ^ | | ^
+ * s| |d |s s| |d
+ * V | V V |
+ * +------|-+ null +------|-+
+ * | 6 | | 15 |
+ * +-|------+ +-|------+
+ * | ^ |
+ * s| |d s|
+ * V | V
+ * +------|-+ null
+ * | 6 |
+ * +-|------+
+ * |
+ * s|
+ * V
+ * null
+ *
+ * The basic usage is:
+ *
+ * - To visit the unique hash values in the hindex, follow the 'd'
+ * ("different") pointers starting from each bucket. The nodes visited
+ * this way are called "head" nodes, because they are at the head of the
+ * vertical chains.
+ *
+ * - To visit the nodes with hash value H, follow the 'd' pointers in the
+ * appropriate bucket until you find one with hash H, then follow the 's'
+ * ("same") pointers until you hit a null pointer. The non-head nodes
+ * visited this way are called "body" nodes.
+ *
+ * - The 'd' pointers in body nodes point back to the previous body node
+ * or, for the first body node, to the head node. (This makes it
+ * possible to remove a body node without traversing all the way downward
+ * from the head).
+ */
+struct hindex_node {
+ /* Hash value. */
+ size_t hash;
+
+ /* In a head node, the next head node (with a hash different from this
+ * node), or NULL if this is the last node in this bucket.
+ *
+ * In a body node, the previous head or body node (with the same hash as
+ * this node). Never null. */
+ struct hindex_node *d;
+
+ /* In a head or a body node, the next body node with the same hash as this
+ * node. NULL if this is the last node with this hash. */
+ struct hindex_node *s;
+};
+
+/* A hash index. */
+struct hindex {
+ struct hindex_node **buckets; /* Must point to 'one' iff 'mask' == 0. */
+ struct hindex_node *one;
+ size_t mask;
+ size_t n_unique; /* Number of unique hashes (the number of head nodes). */
+};
+
+/* Initializer for an empty hash index. */
+#define HINDEX_INITIALIZER(HINDEX) \
+ { (struct hindex_node **const) &(HINDEX)->one, NULL, 0, 0 }
+
+/* Initialization. */
+void hindex_init(struct hindex *);
+void hindex_destroy(struct hindex *);
+void hindex_clear(struct hindex *);
+void hindex_swap(struct hindex *a, struct hindex *b);
+void hindex_moved(struct hindex *hindex);
+static inline bool hindex_is_empty(const struct hindex *);
+
+/* Adjusting capacity. */
+void hindex_expand(struct hindex *);
+void hindex_shrink(struct hindex *);
+void hindex_reserve(struct hindex *, size_t capacity);
+
+/* Insertion and deletion. */
+void hindex_insert_fast(struct hindex *, struct hindex_node *, size_t hash);
+void hindex_insert(struct hindex *, struct hindex_node *, size_t hash);
+void hindex_remove(struct hindex *, struct hindex_node *);
+
+/* Search.
+ *
+ * HINDEX_FOR_EACH_WITH_HASH iterates NODE over all of the nodes in HINDEX that
+ * have hash value equal to HASH. MEMBER must be the name of the 'struct
+ * hindex_node' member within NODE.
+ *
+ * The loop should not change NODE to point to a different node or insert or
+ * delete nodes in HINDEX (unless it "break"s out of the loop to terminate
+ * iteration).
+ *
+ * Evaluates HASH only once.
+ */
+#define HINDEX_FOR_EACH_WITH_HASH(NODE, MEMBER, HASH, HINDEX) \
+ for (ASSIGN_CONTAINER(NODE, hindex_node_with_hash(HINDEX, HASH), MEMBER); \
+ &(NODE)->MEMBER != NULL; \
+ ASSIGN_CONTAINER(NODE, (NODE)->MEMBER.s, MEMBER))
+
+struct hindex_node *hindex_node_with_hash(const struct hindex *, size_t hash);
+
+/* Iteration. */
+
+/* Iterates through every node in HINDEX. */
+#define HINDEX_FOR_EACH(NODE, MEMBER, HINDEX) \
+ for (ASSIGN_CONTAINER(NODE, hindex_first(HINDEX), MEMBER); \
+ &(NODE)->MEMBER != NULL; \
+ ASSIGN_CONTAINER(NODE, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER))
+
+/* Safe when NODE may be freed (not needed when NODE may be removed from the
+ * hash index but its members remain accessible and intact). */
+#define HINDEX_FOR_EACH_SAFE(NODE, NEXT, MEMBER, HINDEX) \
+ for (ASSIGN_CONTAINER(NODE, hindex_first(HINDEX), MEMBER); \
+ (&(NODE)->MEMBER != NULL \
+ ? ASSIGN_CONTAINER(NEXT, hindex_next(HINDEX, &(NODE)->MEMBER), MEMBER) \
+ : 0); \
+ (NODE) = (NEXT))
+
+struct hindex_node *hindex_first(const struct hindex *);
+struct hindex_node *hindex_next(const struct hindex *,
+ const struct hindex_node *);
+
+/* Returns true if 'hindex' currently contains no nodes, false otherwise. */
+static inline bool
+hindex_is_empty(const struct hindex *hindex)
+{
+ return hindex->n_unique == 0;
+}
+
+#endif /* hindex.h */
diff --git a/tests/automake.mk b/tests/automake.mk
index 15df623..1af41cc 100644
--- a/tests/automake.mk
+++ b/tests/automake.mk
@@ -105,6 +105,7 @@ valgrind_wrappers = \
tests/valgrind/test-flows \
tests/valgrind/test-hash \
tests/valgrind/test-heap \
+ tests/valgrind/test-hindex \
tests/valgrind/test-hmap \
tests/valgrind/test-json \
tests/valgrind/test-jsonrpc \
@@ -203,6 +204,10 @@ noinst_PROGRAMS += tests/test-heap
tests_test_heap_SOURCES = tests/test-heap.c
tests_test_heap_LDADD = lib/libopenvswitch.a $(SSL_LIBS)
+noinst_PROGRAMS += tests/test-hindex
+tests_test_hindex_SOURCES = tests/test-hindex.c
+tests_test_hindex_LDADD = lib/libopenvswitch.a $(SSL_LIBS)
+
noinst_PROGRAMS += tests/test-hmap
tests_test_hmap_SOURCES = tests/test-hmap.c
tests_test_hmap_LDADD = lib/libopenvswitch.a $(SSL_LIBS)
diff --git a/tests/library.at b/tests/library.at
index 650fef3..532af3b 100644
--- a/tests/library.at
+++ b/tests/library.at
@@ -20,6 +20,11 @@ AT_CHECK([test-hmap], [0], [.........
])
AT_CLEANUP
+AT_SETUP([test hash index])
+AT_CHECK([test-hindex], [0], [..................
+])
+AT_CLEANUP
+
AT_SETUP([test linked lists])
AT_CHECK([test-list], [0], [..
])
diff --git a/tests/test-hindex.c b/tests/test-hindex.c
new file mode 100644
index 0000000..b5fe9f0
--- /dev/null
+++ b/tests/test-hindex.c
@@ -0,0 +1,319 @@
+/*
+ * Copyright (c) 2008, 2009, 2010, 2013 Nicira, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at:
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/* A non-exhaustive test for some of the functions and macros declared in
+ * hindex.h. */
+
+#include <config.h>
+#include "hindex.h"
+#include <string.h>
+#include "hash.h"
+#include "util.h"
+
+#undef NDEBUG
+#include <assert.h>
+
+/* Sample hindex element. */
+struct element {
+ int value;
+ struct hindex_node node;
+};
+
+typedef size_t hash_func(int value);
+
+static int
+compare_ints(const void *a_, const void *b_)
+{
+ const int *a = a_;
+ const int *b = b_;
+ return *a < *b ? -1 : *a > *b;
+}
+
+/* Verifies that 'hindex' contains exactly the 'n' values in 'values'. */
+static void
+check_hindex(struct hindex *hindex, const int values[], size_t n,
+ hash_func *hash)
+{
+ int *sort_values, *hindex_values;
+ struct element *e;
+ size_t i;
+
+ /* Check that all the values are there in iteration. */
+ sort_values = xmalloc(sizeof *sort_values * n);
+ hindex_values = xmalloc(sizeof *sort_values * n);
+
+ i = 0;
+ HINDEX_FOR_EACH (e, node, hindex) {
+ assert(i < n);
+ hindex_values[i++] = e->value;
+ }
+ assert(i == n);
+
+ memcpy(sort_values, values, sizeof *sort_values * n);
+ qsort(sort_values, n, sizeof *sort_values, compare_ints);
+ qsort(hindex_values, n, sizeof *hindex_values, compare_ints);
+
+ for (i = 0; i < n; i++) {
+ assert(sort_values[i] == hindex_values[i]);
+ }
+
+ free(hindex_values);
+ free(sort_values);
+
+ /* Check that all the values are there in lookup. */
+ for (i = 0; i < n; i++) {
+ size_t count = 0;
+
+ HINDEX_FOR_EACH_WITH_HASH (e, node, hash(values[i]), hindex) {
+ count += e->value == values[i];
+ }
+ assert(count == 1);
+ }
+
+ /* Check counters. */
+ assert(hindex_is_empty(hindex) == !n);
+ assert(hindex->n_unique <= n);
+}
+
+/* Puts the 'n' values in 'values' into 'elements', and then puts those
+ * elements into 'hindex'. */
+static void
+make_hindex(struct hindex *hindex, struct element elements[],
+ int values[], size_t n, hash_func *hash)
+{
+ size_t i;
+
+ hindex_init(hindex);
+ for (i = 0; i < n; i++) {
+ elements[i].value = i;
+ hindex_insert(hindex, &elements[i].node, hash(elements[i].value));
+ values[i] = i;
+ }
+}
+
+static void
+shuffle(int *p, size_t n)
+{
+ for (; n > 1; n--, p++) {
+ int *q = &p[rand() % n];
+ int tmp = *p;
+ *p = *q;
+ *q = tmp;
+ }
+}
+
+/* Prints the 'n' values in 'values', plus 'name' as a title. */
+static void OVS_UNUSED
+print_ints(const char *name, const int *values, size_t n)
+{
+ size_t i;
+
+ printf("%s:", name);
+ for (i = 0; i < n; i++) {
+ printf(" %d", values[i]);
+ }
+ printf("\n");
+}
+
+/* Prints the values in 'hindex', plus 'name' as a title. */
+static void OVS_UNUSED
+print_hindex(const char *name, struct hindex *hindex)
+{
+ struct element *e;
+
+ printf("%s:", name);
+ HINDEX_FOR_EACH (e, node, hindex) {
+ printf(" %d(%zu)", e->value, e->node.hash & hindex->mask);
+ }
+ printf("\n");
+}
+
+static size_t
+unique_hash(int value)
+{
+ return value;
+}
+
+static size_t
+good_hash(int value)
+{
+ return hash_int(value, 0x1234abcd);
+}
+
+static size_t
+constant_hash(int value OVS_UNUSED)
+{
+ return 123;
+}
+
+static size_t
+mod4_hash(int value)
+{
+ return value % 4;
+}
+
+static size_t
+mod3_hash(int value)
+{
+ return value % 3;
+}
+
+static size_t
+mod2_hash(int value)
+{
+ return value % 2;
+}
+
+/* Tests basic hindex insertion and deletion. */
+static void
+test_hindex_insert_delete(hash_func *hash)
+{
+ enum { N_ELEMS = 100 };
+
+ struct element elements[N_ELEMS];
+ int values[N_ELEMS];
+ struct hindex hindex;
+ size_t i;
+
+ hindex_init(&hindex);
+ for (i = 0; i < N_ELEMS; i++) {
+ elements[i].value = i;
+ hindex_insert(&hindex, &elements[i].node, hash(i));
+ values[i] = i;
+ check_hindex(&hindex, values, i + 1, hash);
+ }
+ shuffle(values, N_ELEMS);
+ for (i = 0; i < N_ELEMS; i++) {
+ hindex_remove(&hindex, &elements[values[i]].node);
+ check_hindex(&hindex, values + (i + 1), N_ELEMS - (i + 1), hash);
+ }
+ hindex_destroy(&hindex);
+}
+
+/* Tests basic hindex_reserve() and hindex_shrink(). */
+static void
+test_hindex_reserve_shrink(hash_func *hash)
+{
+ enum { N_ELEMS = 32 };
+
+ size_t i;
+
+ for (i = 0; i < N_ELEMS; i++) {
+ struct element elements[N_ELEMS];
+ int values[N_ELEMS];
+ struct hindex hindex;
+ size_t j;
+
+ hindex_init(&hindex);
+ hindex_reserve(&hindex, i);
+ for (j = 0; j < N_ELEMS; j++) {
+ elements[j].value = j;
+ hindex_insert(&hindex, &elements[j].node, hash(j));
+ values[j] = j;
+ check_hindex(&hindex, values, j + 1, hash);
+ }
+ shuffle(values, N_ELEMS);
+ for (j = 0; j < N_ELEMS; j++) {
+ hindex_remove(&hindex, &elements[values[j]].node);
+ hindex_shrink(&hindex);
+ check_hindex(&hindex, values + (j + 1), N_ELEMS - (j + 1), hash);
+ }
+ hindex_destroy(&hindex);
+ }
+}
+
+/* Tests that HINDEX_FOR_EACH_SAFE properly allows for deletion of the current
+ * element of a hindex. */
+static void
+test_hindex_for_each_safe(hash_func *hash)
+{
+ enum { MAX_ELEMS = 10 };
+ size_t n;
+ unsigned long int pattern;
+
+ for (n = 0; n <= MAX_ELEMS; n++) {
+ for (pattern = 0; pattern < 1ul << n; pattern++) {
+ struct element elements[MAX_ELEMS];
+ int values[MAX_ELEMS];
+ struct hindex hindex;
+ struct element *e, *next;
+ size_t n_remaining;
+ int i;
+
+ make_hindex(&hindex, elements, values, n, hash);
+
+ i = 0;
+ n_remaining = n;
+ HINDEX_FOR_EACH_SAFE (e, next, node, &hindex) {
+ assert(i < n);
+ if (pattern & (1ul << e->value)) {
+ size_t j;
+ hindex_remove(&hindex, &e->node);
+ for (j = 0; ; j++) {
+ assert(j < n_remaining);
+ if (values[j] == e->value) {
+ values[j] = values[--n_remaining];
+ break;
+ }
+ }
+ }
+ check_hindex(&hindex, values, n_remaining, hash);
+ i++;
+ }
+ assert(i == n);
+
+ for (i = 0; i < n; i++) {
+ if (pattern & (1ul << i)) {
+ n_remaining++;
+ }
+ }
+ assert(n == n_remaining);
+
+ hindex_destroy(&hindex);
+ }
+ }
+}
+
+static void
+run_test(void (*function)(hash_func *))
+{
+ hash_func *hash_funcs[] = {
+ unique_hash,
+ good_hash,
+ constant_hash,
+ mod4_hash,
+ mod3_hash,
+ mod2_hash,
+ };
+ size_t i;
+
+ for (i = 0; i < ARRAY_SIZE(hash_funcs); i++) {
+ function(hash_funcs[i]);
+ printf(".");
+ fflush(stdout);
+ }
+}
+
+int
+main(void)
+{
+ run_test(test_hindex_insert_delete);
+ run_test(test_hindex_for_each_safe);
+ run_test(test_hindex_reserve_shrink);
+ printf("\n");
+ return 0;
+}
+
--
1.7.2.5
More information about the dev
mailing list