All looks good and tests pass. However, I'd probably add a comment on the hindex.mask (in hindex.h) stating that it has a number of lowest order bits set, others cleared. After realizing that reading the code became a bit easier..
I also changed the cookie indexing to use this and it also passes all tests and seems to work as expected in my performance tests. Jarno On Jun 17, 2013, at 23:57 , ext Ben Pfaff wrote: > Signed-off-by: Ben Pfaff <b...@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 > > _______________________________________________ > dev mailing list > dev@openvswitch.org > http://openvswitch.org/mailman/listinfo/dev _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev
