From 95974447c9005f4ad6ef880b2331e7dca0e6f661 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Tue, 24 Jan 2012 15:07:41 -0800 Subject: [PATCH] heap: New library that implements a binary heap-based priority queue. Signed-off-by: Ben Pfaff --- 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 | 486 +++++++++++++++++++++++++++++++++++++++++++++ tests/testsuite.at | 3 +- 8 files changed, 891 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 4e2fcf3b..3531ba97 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 00000000..77b7955c --- /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 +#include "heap.h" +#include +#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 00000000..8cfcf70f --- /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 +#include +#include + +/* 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 affb2efe..76b6fed0 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 9ae4c5cd..8757466e 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 00000000..4e6e8ff1 --- /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 00000000..0541b8d8 --- /dev/null +++ b/tests/test-heap.c @@ -0,0 +1,486 @@ +/* + * 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 +#include "heap.h" +#include +#include +#include +#include "command-line.h" +#include "random.h" +#include "util.h" + +#undef NDEBUG +#include + +/* 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); +} + +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 d8af5924..7711ba30 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]) -- 2.30.2