heap: New library that implements a binary heap-based priority queue.

Signed-off-by: Ben Pfaff <blp@nicira.com>

5 files changed, 509 insertions, 1 deletions

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 <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);
+}
+
+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])