Looks good, In heap_raw_insert() why not use x2nrealloc() instead of xrealloc()?
I didn't read the testing code closely, but I have two minor questions: 1) You've ifdef'd out some code. Any reason not to simply delete it? 2) You've implemented print_heap() without using it. I suppose that's for debugging purposes? Ethan On Fri, Jan 13, 2012 at 16:43, Ben Pfaff <b...@nicira.com> wrote: > Signed-off-by: Ben Pfaff <b...@nicira.com> > --- > lib/automake.mk | 4 +- > lib/heap.c | 216 ++++++++++++++++++++++ > lib/heap.h | 163 +++++++++++++++++ > tests/.gitignore | 1 + > tests/automake.mk | 7 + > tests/heap.at | 13 ++ > tests/test-heap.c | 504 > ++++++++++++++++++++++++++++++++++++++++++++++++++++ > tests/testsuite.at | 3 +- > 8 files changed, 909 insertions(+), 2 deletions(-) > create mode 100644 lib/heap.c > create mode 100644 lib/heap.h > create mode 100644 tests/heap.at > create mode 100644 tests/test-heap.c > > diff --git a/lib/automake.mk b/lib/automake.mk > index 4e2fcf3..3531ba9 100644 > --- a/lib/automake.mk > +++ b/lib/automake.mk > @@ -1,4 +1,4 @@ > -# Copyright (C) 2009, 2010, 2011 Nicira Networks, Inc. > +# Copyright (C) 2009, 2010, 2011, 2012 Nicira Networks, Inc. > # > # Copying and distribution of this file, with or without modification, > # are permitted in any medium without royalty provided the copyright > @@ -45,6 +45,8 @@ lib_libopenvswitch_a_SOURCES = \ > lib/dpif-provider.h \ > lib/dpif.c \ > lib/dpif.h \ > + lib/heap.c \ > + lib/heap.h \ > lib/dynamic-string.c \ > lib/dynamic-string.h \ > lib/entropy.c \ > diff --git a/lib/heap.c b/lib/heap.c > new file mode 100644 > index 0000000..77b7955 > --- /dev/null > +++ b/lib/heap.c > @@ -0,0 +1,216 @@ > +/* > + * Copyright (c) 2012 Nicira Networks. > + * > + * 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 "heap.h" > +#include <stdlib.h> > +#include "util.h" > + > +static void put_node(struct heap *, struct heap_node *, size_t i); > +static void swap_nodes(struct heap *, size_t i, size_t j); > +static bool float_up(struct heap *, size_t i); > +static void float_down(struct heap *, size_t i); > +static void float_up_or_down(struct heap *, size_t i); > + > +/* Initializes 'heap' as an empty heap. */ > +void > +heap_init(struct heap *heap) > +{ > + heap->array = NULL; > + heap->n = 0; > + heap->allocated = 0; > +} > + > +/* Frees memory owned internally by 'heap'. The caller is responsible for > + * freeing 'heap' itself, if necessary. */ > +void > +heap_destroy(struct heap *heap) > +{ > + if (heap) { > + free(heap->array); > + } > +} > + > +/* Removes all of the elements from 'heap', without freeing any allocated > + * memory. */ > +void > +heap_clear(struct heap *heap) > +{ > + heap->n = 0; > +} > + > +/* Exchanges the contents of 'a' and 'b'. */ > +void > +heap_swap(struct heap *a, struct heap *b) > +{ > + struct heap tmp = *a; > + *a = *b; > + *b = tmp; > +} > + > +/* Inserts 'node' into 'heap' with the specified 'priority'. > + * > + * This takes time O(lg n). */ > +void > +heap_insert(struct heap *heap, struct heap_node *node, uint32_t priority) > +{ > + heap_raw_insert(heap, node, priority); > + float_up(heap, node->idx); > +} > + > +/* Removes 'node' from 'heap'. > + * > + * This takes time O(lg n). */ > +void > +heap_remove(struct heap *heap, struct heap_node *node) > +{ > + size_t i = node->idx; > + > + heap_raw_remove(heap, node); > + if (i <= heap->n) { > + float_up_or_down(heap, i); > + } > +} > + > +/* Changes the priority of 'node' (which must be in 'heap') to 'priority'. > + * > + * This takes time O(lg n). */ > +void > +heap_change(struct heap *heap, struct heap_node *node, uint32_t priority) > +{ > + heap_raw_change(node, priority); > + float_up_or_down(heap, node->idx); > +} > + > +/* Inserts 'node' into 'heap' with the specified 'priority', without > + * maintaining the heap invariant. > + * > + * After this call, heap_max() will no longer necessarily return the maximum > + * value in the heap, and HEAP_FOR_EACH will no longer necessarily iterate in > + * heap level order, until the next call to heap_rebuild(heap). > + * > + * This takes time O(1). */ > +void > +heap_raw_insert(struct heap *heap, struct heap_node *node, uint32_t priority) > +{ > + if (heap->n >= heap->allocated) { > + heap->allocated = heap->n == 0 ? 1 : 2 * heap->n; > + heap->array = xrealloc(heap->array, > + (heap->allocated + 1) * sizeof *heap->array); > + } > + > + put_node(heap, node, ++heap->n); > + node->priority = priority; > +} > + > +/* Removes 'node' from 'heap', without maintaining the heap invariant. > + * > + * After this call, heap_max() will no longer necessarily return the maximum > + * value in the heap, and HEAP_FOR_EACH will no longer necessarily iterate in > + * heap level order, until the next call to heap_rebuild(heap). > + * > + * This takes time O(1). */ > +void > +heap_raw_remove(struct heap *heap, struct heap_node *node) > +{ > + size_t i = node->idx; > + if (i < heap->n) { > + put_node(heap, heap->array[heap->n], i); > + } > + heap->n--; > +} > + > +/* Rebuilds 'heap' to restore the heap invariant following a series of one or > + * more calls to heap_raw_*() functions. (Otherwise this function need not > be > + * called.) > + * > + * This takes time O(n) in the current size of the heap. */ > +void > +heap_rebuild(struct heap *heap) > +{ > + size_t i; > + > + for (i = heap->n / 2; i >= 1; i--) { > + float_down(heap, i); > + } > +} > + > +static void > +put_node(struct heap *heap, struct heap_node *node, size_t i) > +{ > + heap->array[i] = node; > + node->idx = i; > +} > + > +static void > +swap_nodes(struct heap *heap, size_t i, size_t j) > +{ > + struct heap_node *old_i = heap->array[i]; > + struct heap_node *old_j = heap->array[j]; > + > + put_node(heap, old_j, i); > + put_node(heap, old_i, j); > +} > + > +static bool > +float_up(struct heap *heap, size_t i) > +{ > + bool moved = false; > + size_t parent; > + > + for (; i > 1; i = parent) { > + parent = heap_parent__(i); > + if (heap->array[parent]->priority >= heap->array[i]->priority) { > + break; > + } > + swap_nodes(heap, parent, i); > + moved = true; > + } > + return moved; > +} > + > +static void > +float_down(struct heap *heap, size_t i) > +{ > + while (!heap_is_leaf__(heap, i)) { > + size_t left = heap_left__(i); > + size_t right = heap_right__(i); > + size_t max = i; > + > + if (heap->array[left]->priority > heap->array[max]->priority) { > + max = left; > + } > + if (right <= heap->n > + && heap->array[right]->priority > heap->array[max]->priority) { > + max = right; > + } > + if (max == i) { > + break; > + } > + > + swap_nodes(heap, max, i); > + i = max; > + } > +} > + > +static void > +float_up_or_down(struct heap *heap, size_t i) > +{ > + if (!float_up(heap, i)) { > + float_down(heap, i); > + } > +} > + > diff --git a/lib/heap.h b/lib/heap.h > new file mode 100644 > index 0000000..8cfcf70 > --- /dev/null > +++ b/lib/heap.h > @@ -0,0 +1,163 @@ > +/* > + * Copyright (c) 2012 Nicira Networks. > + * > + * 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 HEAP_H > +#define HEAP_H 1 > + > +#include <stdbool.h> > +#include <stddef.h> > +#include <stdint.h> > + > +/* A heap node, to be embedded inside the data structure in the heap. */ > +struct heap_node { > + size_t idx; > + uint32_t priority; > +}; > + > +/* A max-heap. */ > +struct heap { > + struct heap_node **array; /* Data in elements 1...n, element 0 unused. > */ > + size_t n; /* Number of nodes currently in the heap. */ > + size_t allocated; /* Max 'n' before 'array' must be enlarged. > */ > +}; > + > +/* Initialization. */ > +void heap_init(struct heap *); > +void heap_destroy(struct heap *); > +void heap_clear(struct heap *); > +void heap_swap(struct heap *a, struct heap *b); > +static inline size_t heap_count(const struct heap *); > +static inline bool heap_is_empty(const struct heap *); > + > +/* Insertion and deletion. */ > +void heap_insert(struct heap *, struct heap_node *, uint32_t priority); > +void heap_change(struct heap *, struct heap_node *, uint32_t priority); > +void heap_remove(struct heap *, struct heap_node *); > +static inline struct heap_node *heap_pop(struct heap *); > + > +/* Maximum. */ > +static inline struct heap_node *heap_max(const struct heap *); > + > +/* The "raw" functions below do not preserve the heap invariants. After you > + * call them, heap_max() will not necessarily return the right value until > you > + * subsequently call heap_rebuild(). */ > +void heap_raw_insert(struct heap *, struct heap_node *, uint32_t priority); > +static inline void heap_raw_change(struct heap_node *, uint32_t priority); > +void heap_raw_remove(struct heap *, struct heap_node *); > +void heap_rebuild(struct heap *); > + > +/* Iterates through each NODE in HEAP, where NODE->MEMBER must be a "struct > + * heap_node". Iterates in heap level order, which in particular means that > + * the first node visited is the maximum value in the heap. > + * > + * If a heap_raw_*() function has been called without a later call to > + * heap_rebuild(), then the first node visited may not be the maximum > + * element. */ > +#define HEAP_FOR_EACH(NODE, MEMBER, HEAP) \ > + for (((HEAP)->n > 0 \ > + ? ASSIGN_CONTAINER(NODE, (HEAP)->array[1], MEMBER) \ > + : ((NODE) = NULL, 1)); \ > + (NODE) != NULL; \ > + ((NODE)->MEMBER.idx < (HEAP)->n \ > + ? ASSIGN_CONTAINER(NODE, \ > + (HEAP)->array[(NODE)->MEMBER.idx + 1], \ > + MEMBER) \ > + : ((NODE) = NULL, 1))) > + > +/* Returns the index of the node that is the parent of the node with the > given > + * 'idx' within a heap. */ > +static inline size_t > +heap_parent__(size_t idx) > +{ > + return idx / 2; > +} > + > +/* Returns the index of the node that is the left child of the node with the > + * given 'idx' within a heap. */ > +static inline size_t > +heap_left__(size_t idx) > +{ > + return idx * 2; > +} > + > +/* Returns the index of the node that is the right child of the node with the > + * given 'idx' within a heap. */ > +static inline size_t > +heap_right__(size_t idx) > +{ > + return idx * 2 + 1; > +} > + > +/* Returns true if 'idx' is the index of a leaf node in 'heap', false > + * otherwise. */ > +static inline bool > +heap_is_leaf__(const struct heap *heap, size_t idx) > +{ > + return heap_left__(idx) > heap->n; > +} > + > +/* Returns the number of elements in 'heap'. */ > +static inline size_t > +heap_count(const struct heap *heap) > +{ > + return heap->n; > +} > + > +/* Returns true if 'heap' is empty, false if it contains at least one > + * element. */ > +static inline bool > +heap_is_empty(const struct heap *heap) > +{ > + return heap->n == 0; > +} > + > +/* Returns the largest element in 'heap'. > + * > + * The caller must ensure that 'heap' contains at least one element. > + * > + * The return value may be wrong (i.e. not the maximum element but some other > + * element) if a heap_raw_*() function has been called without a later call > to > + * heap_rebuild(). */ > +static inline struct heap_node * > +heap_max(const struct heap *heap) > +{ > + return heap->array[1]; > +} > + > +/* Removes an arbitrary node from 'heap', in O(1), maintaining the heap > + * invariant. Returns the node removed. > + * > + * The caller must ensure that 'heap' contains at least one element. */ > +static inline struct heap_node * > +heap_pop(struct heap *heap) > +{ > + return heap->array[heap->n--]; > +} > + > +/* Changes the priority of 'node' (which must be in 'heap') to 'priority'. > + * > + * After this call, heap_max() will no longer necessarily return the maximum > + * value in the heap, and HEAP_FOR_EACH will no longer necessarily iterate in > + * heap level order, until the next call to heap_rebuild(heap). > + * > + * This takes time O(1). */ > +static inline void > +heap_raw_change(struct heap_node *node, uint32_t priority) > +{ > + node->priority = priority; > +} > + > +#endif /* heap.h */ > diff --git a/tests/.gitignore b/tests/.gitignore > index affb2ef..76b6fed 100644 > --- a/tests/.gitignore > +++ b/tests/.gitignore > @@ -16,6 +16,7 @@ > /test-file_name > /test-flows > /test-hash > +/test-heap > /test-hmap > /test-json > /test-jsonrpc > diff --git a/tests/automake.mk b/tests/automake.mk > index 9ae4c5c..8757466 100644 > --- a/tests/automake.mk > +++ b/tests/automake.mk > @@ -8,6 +8,7 @@ TESTSUITE_AT = \ > tests/testsuite.at \ > tests/ovsdb-macros.at \ > tests/library.at \ > + tests/heap.at \ > tests/bundle.at \ > tests/classifier.at \ > tests/check-structs.at \ > @@ -82,6 +83,7 @@ lcov_wrappers = \ > tests/lcov/test-file_name \ > tests/lcov/test-flows \ > tests/lcov/test-hash \ > + tests/lcov/test-heap \ > tests/lcov/test-hmap \ > tests/lcov/test-json \ > tests/lcov/test-jsonrpc \ > @@ -138,6 +140,7 @@ valgrind_wrappers = \ > tests/valgrind/test-file_name \ > tests/valgrind/test-flows \ > tests/valgrind/test-hash \ > + tests/valgrind/test-heap \ > tests/valgrind/test-hmap \ > tests/valgrind/test-json \ > tests/valgrind/test-jsonrpc \ > @@ -225,6 +228,10 @@ noinst_PROGRAMS += tests/test-hash > tests_test_hash_SOURCES = tests/test-hash.c > tests_test_hash_LDADD = lib/libopenvswitch.a > > +noinst_PROGRAMS += tests/test-heap > +tests_test_heap_SOURCES = tests/test-heap.c > +tests_test_heap_LDADD = lib/libopenvswitch.a > + > noinst_PROGRAMS += tests/test-hmap > tests_test_hmap_SOURCES = tests/test-hmap.c > tests_test_hmap_LDADD = lib/libopenvswitch.a > diff --git a/tests/heap.at b/tests/heap.at > new file mode 100644 > index 0000000..4e6e8ff > --- /dev/null > +++ b/tests/heap.at > @@ -0,0 +1,13 @@ > +AT_BANNER([heap library]) > + > +m4_define([TEST_HEAP], > + [AT_SETUP([heap library -- m4_bpatsubst([$1], [-], [ ])]) > + AT_CHECK([test-heap $1]) > + AT_CLEANUP]) > + > +TEST_HEAP([insert-delete-same-order]) > +TEST_HEAP([insert-delete-reverse-order]) > +TEST_HEAP([insert-delete-every-order]) > +TEST_HEAP([insert-delete-same-order-with-dups]) > +TEST_HEAP([raw-insert]) > +TEST_HEAP([raw-delete]) > diff --git a/tests/test-heap.c b/tests/test-heap.c > new file mode 100644 > index 0000000..83580d3 > --- /dev/null > +++ b/tests/test-heap.c > @@ -0,0 +1,504 @@ > +/* > + * Copyright (c) 2012 Nicira Networks. > + * > + * 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 test for for functions and macros declared in heap.h. */ > + > +#include <config.h> > +#include "heap.h" > +#include <inttypes.h> > +#include <limits.h> > +#include <stdlib.h> > +#include "command-line.h" > +#include "random.h" > +#include "util.h" > + > +#undef NDEBUG > +#include <assert.h> > + > +/* Sample heap element. */ > +struct element { > + uint32_t full_pri; > + struct heap_node heap_node; > +}; > + > +static struct element * > +element_from_heap_node(const struct heap_node *node) > +{ > + return CONTAINER_OF(node, struct element, heap_node); > +} > + > +static int > +compare_uint32s(const void *a_, const void *b_) > +{ > + const uint32_t *a = a_; > + const uint32_t *b = b_; > + return *a < *b ? -1 : *a > *b; > +} > + > +/* Verifies that 'heap' is internally consistent and contains all 'n' of the > + * 'priorities'. */ > +static void > +check_heap(const struct heap *heap, const uint32_t priorities[], size_t n) > +{ > + uint32_t *priorities_copy; > + uint32_t *elements_copy; > + struct element *element; > + size_t i; > + > + assert(heap_count(heap) == n); > + assert(heap_is_empty(heap) == !n); > + if (n > 0) { > + assert(heap_max(heap) == heap->array[1]); > + } > + > + /* Check indexes. */ > + for (i = 1; i <= n; i++) { > + assert(heap->array[i]->idx == i); > + } > + > + /* Check that priority values are internally consistent. */ > + for (i = 1; i <= n; i++) { > + element = element_from_heap_node(heap->array[i]); > + assert(element->heap_node.priority == (element->full_pri >> 16)); > + } > + > + /* Check the heap property. */ > + for (i = 1; i <= n; i++) { > + size_t parent = heap_parent__(i); > + size_t left = heap_left__(i); > + size_t right = heap_right__(i); > + > + if (parent >= 1) { > + assert(heap->array[parent]->priority >= > heap->array[i]->priority); > + } > + if (left <= n) { > + assert(heap->array[left]->priority <= heap->array[i]->priority); > + } > + if (right <= n) { > + assert(heap->array[right]->priority <= heap->array[i]->priority); > + } > + } > + > + /* Check that HEAP_FOR_EACH iterates all the nodes in order. */ > + i = 0; > + HEAP_FOR_EACH (element, heap_node, heap) { > + assert(i < n); > + assert(&element->heap_node == heap->array[i + 1]); > + i++; > + } > + assert(i == n); > + > + priorities_copy = xmemdup(priorities, n * sizeof *priorities); > + elements_copy = xmalloc(n * sizeof *priorities); > + i = 0; > + HEAP_FOR_EACH (element, heap_node, heap) { > + elements_copy[i++] = element->heap_node.priority; > + } > + > + qsort(priorities_copy, n, sizeof *priorities_copy, compare_uint32s); > + qsort(elements_copy, n, sizeof *elements_copy, compare_uint32s); > + for (i = 0; i < n; i++) { > + assert((priorities_copy[i] >> 16) == elements_copy[i]); > + } > + > + free(priorities_copy); > + free(elements_copy); > +} > + > +#if 0 > +/* Puts the 'n' values in 'priorities' into 'elements', and then puts those > + * elements into 'heap'. */ > +static void > +make_heap(struct heap *heap, struct element elements[], > + uint32_t priorities[], size_t n) > +{ > + size_t i; > + > + heap_init(heap); > + for (i = 0; i < n; i++) { > + elements[i].priority_copy = i; > + heap_insert(heap, &elements[i].heap_node, priorities[i]); > + priorities[i] = i; > + } > +} > +#endif > + > +static void > +shuffle(uint32_t *p, size_t n) > +{ > + for (; n > 1; n--, p++) { > + uint32_t *q = &p[random_range(n)]; > + uint32_t tmp = *p; > + *p = *q; > + *q = tmp; > + } > +} > + > +/* Prints the values in 'heap', plus 'name' as a title. */ > +static void OVS_UNUSED > +print_heap(const char *name, struct heap *heap) > +{ > + struct element *e; > + > + printf("%s:", name); > + HEAP_FOR_EACH (e, heap_node, heap) { > + printf(" %"PRIu32":%"PRIu32, e->full_pri >> 16, e->full_pri & > 0xffff); > + } > + printf("\n"); > +} > + > +static int > +factorial(int n_items) > +{ > + int n, i; > + > + n = 1; > + for (i = 2; i <= n_items; i++) { > + n *= i; > + } > + return n; > +} > + > +static void > +swap(uint32_t *a, uint32_t *b) > +{ > + uint32_t tmp = *a; > + *a = *b; > + *b = tmp; > +} > + > +static void > +reverse(uint32_t *a, int n) > +{ > + int i; > + > + for (i = 0; i < n / 2; i++) { > + int j = n - (i + 1); > + swap(&a[i], &a[j]); > + } > +} > + > +static bool > +next_permutation(uint32_t *a, int n) > +{ > + int k; > + > + for (k = n - 2; k >= 0; k--) { > + if ((a[k] >> 16) < (a[k + 1] >> 16)) { > + int l; > + > + for (l = n - 1; ; l--) { > + if ((a[l] >> 16) > (a[k] >> 16)) { > + swap(&a[k], &a[l]); > + reverse(a + (k + 1), n - (k + 1)); > + return true; > + } > + } > + } > + } > + return false; > +} > + > +static void > +test_insert_delete__(struct element *elements, > + const uint32_t *insert, > + const uint32_t *delete, > + size_t n) > +{ > + struct heap heap; > + size_t i; > + > + heap_init(&heap); > + check_heap(&heap, NULL, 0); > + for (i = 0; i < n; i++) { > + uint32_t priority = insert[i]; > + > + elements[i].full_pri = priority; > + heap_insert(&heap, &elements[i].heap_node, priority >> 16); > + check_heap(&heap, insert, i + 1); > + } > + > + for (i = 0; i < n; i++) { > + struct element *element; > + > + HEAP_FOR_EACH (element, heap_node, &heap) { > + if (element->full_pri == delete[i]) { > + goto found; > + } > + } > + NOT_REACHED(); > + > + found: > + heap_remove(&heap, &element->heap_node); > + check_heap(&heap, delete + i + 1, n - (i + 1)); > + } > + heap_destroy(&heap); > +} > + > +static void > +test_insert_delete_raw__(struct element *elements, > + const uint32_t *insert, unsigned int insert_pattern, > + const uint32_t *delete, unsigned int delete_pattern, > + size_t n) > +{ > + struct heap heap; > + size_t i; > + > + heap_init(&heap); > + check_heap(&heap, NULL, 0); > + for (i = 0; i < n; i++) { > + uint32_t priority = insert[i]; > + > + elements[i].full_pri = priority; > + heap_raw_insert(&heap, &elements[i].heap_node, priority >> 16); > + if (insert_pattern & (1u << i)) { > + heap_rebuild(&heap); > + check_heap(&heap, insert, i + 1); > + } > + } > + > + for (i = 0; i < n; i++) { > + struct element *element; > + > + HEAP_FOR_EACH (element, heap_node, &heap) { > + if (element->full_pri == delete[i]) { > + goto found; > + } > + } > + NOT_REACHED(); > + > + found: > + heap_raw_remove(&heap, &element->heap_node); > + if (delete_pattern & (1u << i)) { > + heap_rebuild(&heap); > + check_heap(&heap, delete + i + 1, n - (i + 1)); > + } > + } > + heap_destroy(&heap); > +} > + > +static void > +test_heap_insert_delete_same_order(int argc OVS_UNUSED, > + char *argv[] OVS_UNUSED) > +{ > + enum { N_ELEMS = 7 }; > + > + uint32_t insert[N_ELEMS]; > + int n_permutations; > + size_t i; > + > + for (i = 0; i < N_ELEMS; i++) { > + insert[i] = i << 16; > + } > + > + n_permutations = 0; > + do { > + struct element elements[N_ELEMS]; > + > + n_permutations++; > + test_insert_delete__(elements, insert, insert, N_ELEMS); > + } while (next_permutation(insert, N_ELEMS)); > + assert(n_permutations == factorial(N_ELEMS)); > +} > + > +static void > +test_heap_insert_delete_reverse_order(int argc OVS_UNUSED, > + char *argv[] OVS_UNUSED) > +{ > + enum { N_ELEMS = 7 }; > + > + uint32_t insert[N_ELEMS]; > + int n_permutations; > + size_t i; > + > + for (i = 0; i < N_ELEMS; i++) { > + insert[i] = i << 16; > + } > + > + n_permutations = 0; > + do { > + struct element elements[N_ELEMS]; > + uint32_t delete[N_ELEMS]; > + > + n_permutations++; > + > + for (i = 0; i < N_ELEMS; i++) { > + delete[N_ELEMS - i - 1] = insert[i]; > + } > + > + test_insert_delete__(elements, insert, delete, N_ELEMS); > + } while (next_permutation(insert, N_ELEMS)); > + assert(n_permutations == factorial(N_ELEMS)); > +} > + > +static void > +test_heap_insert_delete_every_order(int argc OVS_UNUSED, > + char *argv[] OVS_UNUSED) > +{ > + enum { N_ELEMS = 5 }; > + > + uint32_t insert[N_ELEMS]; > + int outer_permutations; > + size_t i; > + > + for (i = 0; i < N_ELEMS; i++) { > + insert[i] = i << 16; > + } > + > + outer_permutations = 0; > + do { > + struct element elements[N_ELEMS]; > + uint32_t delete[N_ELEMS]; > + int inner_permutations; > + > + outer_permutations++; > + > + for (i = 0; i < N_ELEMS; i++) { > + delete[i] = i << 16; > + } > + > + inner_permutations = 0; > + do { > + inner_permutations++; > + test_insert_delete__(elements, insert, delete, N_ELEMS); > + } while (next_permutation(delete, N_ELEMS)); > + assert(inner_permutations == factorial(N_ELEMS)); > + } while (next_permutation(insert, N_ELEMS)); > + assert(outer_permutations == factorial(N_ELEMS)); > +} > + > +static void > +test_heap_insert_delete_same_order_with_dups(int argc OVS_UNUSED, > + char *argv[] OVS_UNUSED) > +{ > + enum { N_ELEMS = 7 }; > + > + unsigned int pattern; > + size_t i; > + > + for (pattern = 0; pattern < (1u << N_ELEMS); pattern += 2) { > + int n_permutations, expected_permutations; > + uint32_t insert[N_ELEMS]; > + int j; > + > + j = 0; > + for (i = 0; i < N_ELEMS; i++) { > + if (i && !(pattern & (1u << i))) { > + j++; > + } > + insert[i] = (j << 16) | i; > + } > + > + expected_permutations = factorial(N_ELEMS); > + for (i = 0; i < N_ELEMS; ) { > + j = i + 1; > + if (pattern & (1u << i)) { > + for (; j < N_ELEMS; j++) { > + if (!(pattern & (1u << j))) { > + break; > + } > + } > + expected_permutations /= factorial(j - i + 1); > + } > + i = j; > + } > + > + n_permutations = 0; > + do { > + struct element elements[N_ELEMS]; > + > + n_permutations++; > + test_insert_delete__(elements, insert, insert, N_ELEMS); > + } while (next_permutation(insert, N_ELEMS)); > + assert(n_permutations == expected_permutations); > + } > +} > + > +static void > +test_heap_raw_insert(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) > +{ > + enum { N_ELEMS = 7 }; > + > + uint32_t insert[N_ELEMS]; > + int n_permutations; > + size_t i; > + > + for (i = 0; i < N_ELEMS; i++) { > + insert[i] = i << 16; > + } > + > + n_permutations = 0; > + do { > + struct element elements[N_ELEMS]; > + > + n_permutations++; > + test_insert_delete_raw__(elements, > + insert, 1u << (N_ELEMS - 1), > + insert, UINT_MAX, > + N_ELEMS); > + } while (next_permutation(insert, N_ELEMS)); > + assert(n_permutations == factorial(N_ELEMS)); > +} > + > +static void > +test_heap_raw_delete(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) > +{ > + enum { N_ELEMS = 16 }; > + > + uint32_t insert[N_ELEMS]; > + uint32_t delete[N_ELEMS]; > + size_t i; > + > + for (i = 0; i < N_ELEMS; i++) { > + insert[i] = i << 16; > + delete[i] = i << 16; > + } > + > + for (i = 0; i < 1000; i++) { > + struct element elements[N_ELEMS]; > + > + shuffle(insert, N_ELEMS); > + shuffle(delete, N_ELEMS); > + > + test_insert_delete_raw__(elements, > + insert, 0, > + delete, > + (1u << (N_ELEMS - 1)) | (1u << (N_ELEMS / > 2)), > + N_ELEMS); > + } > +} > + > +static const struct command commands[] = { > + { "insert-delete-same-order", 0, 0, test_heap_insert_delete_same_order, > }, > + { "insert-delete-reverse-order", 0, 0, > + test_heap_insert_delete_reverse_order, }, > + { "insert-delete-every-order", 0, 0, > + test_heap_insert_delete_every_order, }, > + { "insert-delete-same-order-with-dups", 0, 0, > + test_heap_insert_delete_same_order_with_dups, }, > + { "raw-insert", 0, 0, test_heap_raw_insert, }, > + { "raw-delete", 0, 0, test_heap_raw_delete, }, > +}; > + > +int > +main(int argc, char *argv[]) > +{ > + set_program_name(argv[0]); > + > + run_command(argc - 1, argv + 1, commands); > + > + return 0; > +} > diff --git a/tests/testsuite.at b/tests/testsuite.at > index d8af592..7711ba3 100644 > --- a/tests/testsuite.at > +++ b/tests/testsuite.at > @@ -1,6 +1,6 @@ > AT_INIT > > -AT_COPYRIGHT([Copyright (c) 2009, 2010, 2011 Nicira Networks. > +AT_COPYRIGHT([Copyright (c) 2009, 2010, 2011, 2012 Nicira Networks. > > Licensed under the Apache License, Version 2.0 (the "License"); > you may not use this file except in compliance with the License. > @@ -40,6 +40,7 @@ m4_include([tests/ofproto-macros.at]) > > m4_include([tests/lacp.at]) > m4_include([tests/library.at]) > +m4_include([tests/heap.at]) > m4_include([tests/bundle.at]) > m4_include([tests/classifier.at]) > m4_include([tests/check-structs.at]) > -- > 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
