From 756e3feab0a2dab6be0a96164079fce2a2d8f9b4 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Wed, 10 Jan 2007 14:50:16 +0000 Subject: [PATCH] Add heap data structure to src/libpspp, and a test to tests/libpspp. Thanks to John Darrington for review. --- src/libpspp/ChangeLog | 8 + src/libpspp/automake.mk | 2 + src/libpspp/heap.c | 283 ++++++++++++++++ src/libpspp/heap.h | 109 ++++++ tests/ChangeLog | 6 + tests/automake.mk | 19 +- tests/libpspp/heap-test.c | 675 ++++++++++++++++++++++++++++++++++++++ 7 files changed, 1099 insertions(+), 3 deletions(-) create mode 100644 src/libpspp/heap.c create mode 100644 src/libpspp/heap.h create mode 100644 tests/libpspp/heap-test.c diff --git a/src/libpspp/ChangeLog b/src/libpspp/ChangeLog index 3412d669..ecdad874 100644 --- a/src/libpspp/ChangeLog +++ b/src/libpspp/ChangeLog @@ -1,3 +1,11 @@ +Wed Jan 10 06:49:38 2007 Ben Pfaff + + * automake.mk: Add heap.c, heap.h to sources. + + * heap.c: New file. + + * heap.h: New file. + Sun Dec 10 13:54:03 2006 Ben Pfaff * str.c (ss_tokenize): Skip the first delimiter character diff --git a/src/libpspp/automake.mk b/src/libpspp/automake.mk index 512d59fa..942a72f3 100644 --- a/src/libpspp/automake.mk +++ b/src/libpspp/automake.mk @@ -23,6 +23,8 @@ src_libpspp_libpspp_a_SOURCES = \ src/libpspp/getl.c \ src/libpspp/hash.c \ src/libpspp/hash.h \ + src/libpspp/heap.c \ + src/libpspp/heap.h \ src/libpspp/i18n.c \ src/libpspp/i18n.h \ src/libpspp/integer-format.c \ diff --git a/src/libpspp/heap.c b/src/libpspp/heap.c new file mode 100644 index 00000000..d262d042 --- /dev/null +++ b/src/libpspp/heap.c @@ -0,0 +1,283 @@ +/* PSPP - computes sample statistics. + Copyright (C) 2007 Free Software Foundation, Inc. + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of the + License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + 02110-1301, USA. */ + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include +#include +#include + +#include "xalloc.h" + +/* A heap. */ +struct heap + { + /* Comparison function and auxiliary data. */ + heap_compare_func *compare; + const void *aux; + + /* Contents. */ + struct heap_node **nodes; /* Element 0 unused, 1...CNT are the heap. */ + size_t cnt; /* Number of elements in heap. */ + size_t cap; /* Max CNT without allocating more memory. */ + }; + +static inline void set_node (struct heap *, size_t idx, struct heap_node *); +static inline bool less (const struct heap *, size_t a, size_t b); +static bool UNUSED is_heap (const struct heap *); +static inline void propagate_down (struct heap *, size_t idx); +static inline bool propagate_up (struct heap *, size_t idx); + +/* Creates and return a new min-heap. COMPARE is used as + comparison function and passed AUX as auxiliary data. + + To obtain a max-heap, negate the return value of the + comparison function. */ +struct heap * +heap_create (heap_compare_func *compare, const void *aux) +{ + struct heap *h = xmalloc (sizeof *h); + h->compare = compare; + h->aux = aux; + h->nodes = NULL; + h->cap = 0; + h->cnt = 0; + return h; +} + +/* Destroys H (callback for pool). */ +static void +destroy_callback (void *h) +{ + heap_destroy (h); +} + +/* Creates and return a new min-heap and registers for its + destruction with POOL. COMPARE is used as comparison function + and passed AUX as auxiliary data. + + To obtain a max-heap, negate the return value of the + comparison function. */ +struct heap * +heap_create_pool (struct pool *pool, + heap_compare_func *compare, const void *aux) +{ + struct heap *h = heap_create (compare, aux); + pool_register (pool, destroy_callback, h); + return h; +} + +/* Destroys heap H. */ +void +heap_destroy (struct heap *h) +{ + if (h != NULL) + { + free (h->nodes); + free (h); + } +} + +/* Returns true if H is empty, false if it contains at least one + element. */ +bool +heap_is_empty (const struct heap *h) +{ + return h->cnt == 0; +} + +/* Returns the number of elements in H. */ +size_t +heap_count (const struct heap *h) +{ + return h->cnt; +} + +/* Heap nodes may be moved around in memory as necessary, e.g. as + the result of an realloc operation on a block that contains a + heap node. Once this is done, call this function passing the + NODE that was moved and its heap H before attempting any other + operation on H. */ +void +heap_moved (struct heap *h, struct heap_node *node) +{ + assert (node->idx <= h->cnt); + h->nodes[node->idx] = node; +} + +/* Returns the node with the minimum value in H, which must not + be empty. */ +struct heap_node * +heap_minimum (const struct heap *h) +{ + assert (!heap_is_empty (h)); + return h->nodes[1]; +} + +/* Inserts the given NODE into H. */ +void +heap_insert (struct heap *h, struct heap_node *node) +{ + if (h->cnt >= h->cap) + { + h->cap = 2 * (h->cap + 8); + h->nodes = xnrealloc (h->nodes, h->cap + 1, sizeof *h->nodes); + } + + h->cnt++; + set_node (h, h->cnt, node); + propagate_up (h, h->cnt); + + expensive_assert (is_heap (h)); +} + +/* Deletes the given NODE from H. */ +void +heap_delete (struct heap *h, struct heap_node *node) +{ + assert (node->idx <= h->cnt); + assert (h->nodes[node->idx] == node); + + if (node->idx < h->cnt) + { + set_node (h, node->idx, h->nodes[h->cnt--]); + heap_changed (h, h->nodes[node->idx]); + } + else + h->cnt--; +} + +/* After client code changes the value represented by a heap + node, it must use this function to update the heap structure. + It is also safe (but not useful) to call this function if + NODE's value has not changed. + + It is not safe to update more than one node's value in the + heap, then to call this function for each node. Instead, + update a single node's value, call this function, update + another node's value, and so on. Alternatively, remove all + the nodes from the heap, update their values, then re-insert + all of them. */ +void +heap_changed (struct heap *h, struct heap_node *node) +{ + assert (node->idx <= h->cnt); + assert (h->nodes[node->idx] == node); + + if (!propagate_up (h, node->idx)) + propagate_down (h, node->idx); + + expensive_assert (is_heap (h)); +} + +static inline size_t lesser_node (const struct heap *, size_t a, size_t b); +static inline void swap_nodes (struct heap *, size_t a, size_t b); + +/* Sets h->nodes[IDX] and updates NODE's 'idx' field + accordingly. */ +static void +set_node (struct heap *h, size_t idx, struct heap_node *node) +{ + h->nodes[idx] = node; + h->nodes[idx]->idx = idx; +} + +/* Moves the node with the given IDX down the heap as necessary + to restore the heap property. */ +static void +propagate_down (struct heap *h, size_t idx) +{ + for (;;) + { + size_t least; + least = lesser_node (h, idx, 2 * idx); + least = lesser_node (h, least, 2 * idx + 1); + if (least == idx) + break; + + swap_nodes (h, least, idx); + idx = least; + } +} + +/* Moves the node with the given IDX up the heap as necessary + to restore the heap property. Returns true if the node was + moved, false otherwise.*/ +static bool +propagate_up (struct heap *h, size_t idx) +{ + bool moved = false; + for (; idx > 1 && less (h, idx, idx / 2); idx /= 2) + { + swap_nodes (h, idx, idx / 2); + moved = true; + } + return moved; +} + +/* Returns true if, in H, the node with index A has value less + than the node with index B. */ +static bool +less (const struct heap *h, size_t a, size_t b) +{ + return h->compare (h->nodes[a], h->nodes[b], h->aux) < 0; +} + +/* Returns A or B according to which is the index of the node + with the lesser value. B is allowed to be out of the range of + valid node indexes, in which case A is returned. */ +static size_t +lesser_node (const struct heap *h, size_t a, size_t b) +{ + assert (a <= h->cnt); + return b > h->cnt || less (h, a, b) ? a : b; +} + +/* Swaps, in H, the nodes with indexes A and B. */ +static void +swap_nodes (struct heap *h, size_t a, size_t b) +{ + struct heap_node *t; + + assert (a <= h->cnt); + assert (b <= h->cnt); + + t = h->nodes[a]; + set_node (h, a, h->nodes[b]); + set_node (h, b, t); +} + +/* Returns true if H is a valid heap, + false otherwise. */ +static bool UNUSED +is_heap (const struct heap *h) +{ + size_t i; + + for (i = 2; i <= h->cnt; i++) + if (less (h, i, i / 2)) + return false; + + for (i = 1; i <= h->cnt; i++) + if (h->nodes[i]->idx != i) + return false; + + return true; +} diff --git a/src/libpspp/heap.h b/src/libpspp/heap.h new file mode 100644 index 00000000..70401c9c --- /dev/null +++ b/src/libpspp/heap.h @@ -0,0 +1,109 @@ +/* PSPP - computes sample statistics. + Copyright (C) 2007 Free Software Foundation, Inc. + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of the + License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + 02110-1301, USA. */ + +/* Embedded priority queue, implemented as a heap. + + Operations have the following cost, where N is the number of + nodes already in the heap: + + - Insert: O(lg N). + + - Find minimum: O(1). + + - Delete any node in the heap: O(lg N). + + - Change value of an node: O(lg N) in general; O(1) in + the typically common case where the node does not + change its position relative to other nodes. + + - Search for a node: O(N). (Not implemented; if you need + such a routine, use a different data structure or + maintain a separate index.) + + A heap data structure is structured as a packed array. If an + array is a natural data structure for your application, then + use the push_heap, pop_heap, make_heap, sort_heap, and is_heap + functions declared in libpspp/array.h. Otherwise, if your + data structure is more dynamic, this implementation may be + easier to use. + + An embedded heap is represented as `struct heap'. Each node + in the heap, presumably a structure type, must include a + `struct heap_node' member. + + Here's an example of a structure type that includes a `struct + heap_node': + + struct foo + { + struct heap_node node; // Heap node member. + int x; // Another member. + }; + + Here's an example of how to find the minimum value in such a + heap and delete it: + + struct heap *h = ...; + if (!heap_is_empty (h)) + { + struct foo *foo = heap_data (heap_minimum (h), struct foo, node); + printf ("Minimum is %d.\n", foo->x); + heap_delete (h, &foo->node); + } + else + printf ("Heap is empty.\n"); +*/ + +#ifndef LIBPSPP_HEAP_H +#define LIBPSPP_HEAP_H 1 + +#include +#include + +struct pool; + +/* Returns the data structure corresponding to the given heap + NODE, assuming that NODE is embedded as the given MEMBER name + in data type STRUCT. */ +#define heap_data(NODE, STRUCT, MEMBER) \ + ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER))) + +/* A node in a heap. Opaque. + One of these structures must be embedded in your heap node. */ +struct heap_node + { + size_t idx; + }; + +/* Returns negative if A < B, zero if A == B, positive if A > B. */ +typedef int heap_compare_func (const struct heap_node *a, + const struct heap_node *b, const void *aux); + +struct heap *heap_create (heap_compare_func *, const void *aux); +struct heap *heap_create_pool (struct pool *, + heap_compare_func *, const void *aux); +void heap_destroy (struct heap *); +bool heap_is_empty (const struct heap *); +size_t heap_count (const struct heap *); +void heap_moved (struct heap *, struct heap_node *); +struct heap_node *heap_minimum (const struct heap *); +void heap_insert (struct heap *, struct heap_node *); +void heap_delete (struct heap *, struct heap_node *); +void heap_changed (struct heap *, struct heap_node *); + +#endif /* libpspp/heap.h */ diff --git a/tests/ChangeLog b/tests/ChangeLog index 238e2c35..c6a34d63 100644 --- a/tests/ChangeLog +++ b/tests/ChangeLog @@ -1,3 +1,9 @@ +Wed Jan 10 06:50:01 2007 Ben Pfaff + + * automake.mk: Add tests/libpspp/heap-test. + + * test/libpspp/heap-test.c: New test. + Wed Dec 13 21:00:46 2006 Ben Pfaff * command/rank.sh (activity): Use DELETE VAR (which is new) diff --git a/tests/automake.mk b/tests/automake.mk index 72481b63..c682bbd2 100644 --- a/tests/automake.mk +++ b/tests/automake.mk @@ -131,10 +131,14 @@ TESTS = \ tests/expressions/variables.sh \ tests/expressions/vectors.sh \ tests/libpspp/ll-test \ - tests/libpspp/llx-test + tests/libpspp/llx-test \ + tests/libpspp/heap-test -check_PROGRAMS += tests/libpspp/ll-test tests/libpspp/llx-test \ - tests/formats/inexactify +check_PROGRAMS += \ + tests/libpspp/ll-test \ + tests/libpspp/llx-test \ + tests/formats/inexactify \ + tests/libpspp/heap-test tests_libpspp_ll_test_SOURCES = \ src/libpspp/ll.c \ @@ -148,6 +152,15 @@ tests_libpspp_llx_test_SOURCES = \ src/libpspp/llx.h \ tests/libpspp/llx-test.c +tests_libpspp_heap_test_SOURCES = \ + src/libpspp/heap.c \ + src/libpspp/heap.h \ + src/libpspp/pool.c \ + src/libpspp/pool.h \ + tests/libpspp/heap-test.c +tests_libpspp_heap_test_LDADD = gl/libgl.la +tests_libpspp_heap_test_CPPFLAGS = $(AM_CPPFLAGS) -DASSERT_LEVEL=10 + tests_formats_inexactify_SOURCES = tests/formats/inexactify.c EXTRA_DIST += $(TESTS) tests/weighting.data tests/data-list.data tests/list.data \ diff --git a/tests/libpspp/heap-test.c b/tests/libpspp/heap-test.c new file mode 100644 index 00000000..34ece38a --- /dev/null +++ b/tests/libpspp/heap-test.c @@ -0,0 +1,675 @@ +/* PSPP - computes sample statistics. + Copyright (C) 2007 Free Software Foundation, Inc. + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License as + published by the Free Software Foundation; either version 2 of the + License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA + 02110-1301, USA. */ + +/* This is a test program for the routines defined in heap.c. + This test program aims to be as comprehensive as possible. + With -DNDEBUG, "gcov -b" should report 100% coverage of lines + and branches in heap.c routines, except for the is_heap + function, which is not called at all with -DNDEBUG. (Without + -DNDEBUG, branches caused by failed assertions will also not + be taken.) "valgrind --leak-check=yes --show-reachable=yes" + should give a clean report, both with and without -DNDEBUG. */ + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include + +#include +#include +#include +#include +#include + +#include + +#include "xalloc.h" + +/* Currently running test. */ +static const char *test_name; + +/* Exit with a failure code. + (Place a breakpoint on this function while debugging.) */ +static void +check_die (void) +{ + exit (EXIT_FAILURE); +} + +/* If OK is not true, prints a message about failure on the + current source file and the given LINE and terminates. */ +static void +check_func (bool ok, int line) +{ + if (!ok) + { + printf ("Check failed in %s test at %s, line %d\n", + test_name, __FILE__, line); + check_die (); + } +} + +/* Verifies that EXPR evaluates to true. + If not, prints a message citing the calling line number and + terminates. */ +#define check(EXPR) check_func ((EXPR), __LINE__) + +/* Node type and support routines. */ + +/* Test data element. */ +struct element + { + struct heap_node node; /* Embedded heap element. */ + int x; /* Primary value. */ + }; + +int aux_data; + +/* Returns the `struct element' that NODE is embedded within. */ +static struct element * +heap_node_to_element (const struct heap_node *node) +{ + return heap_data (node, struct element, node); +} + +/* Compares the `x' values in A and B and returns a strcmp-type + return value. Verifies that AUX points to aux_data. */ +static int +compare_elements (const struct heap_node *a_, const struct heap_node *b_, + const void *aux) +{ + const struct element *a = heap_node_to_element (a_); + const struct element *b = heap_node_to_element (b_); + + check (aux == &aux_data); + return a->x < b->x ? -1 : a->x > b->x; +} + +/* Returns the smallest of the N integers in ARRAY. */ +static int +min_int (int *array, size_t n) +{ + int min; + size_t i; + + min = INT_MAX; + for (i = 0; i < n; i++) + if (array[i] < min) + min = array[i]; + return min; +} + +/* Swaps *A and *B. */ +static void +swap (int *a, int *b) +{ + int t = *a; + *a = *b; + *b = t; +} + +/* Reverses the order of the CNT integers starting at VALUES. */ +static void +reverse (int *values, size_t cnt) +{ + for (; cnt > 1; cnt -= 2, values++) + swap (values, &values[cnt - 1]); +} + +/* Arranges the CNT elements in VALUES into the lexicographically + next greater permutation. Returns true if successful. + If VALUES is already the lexicographically greatest + permutation of its elements (i.e. ordered from greatest to + smallest), arranges them into the lexicographically least + permutation (i.e. ordered from smallest to largest) and + returns false. */ +static bool +next_permutation (int *values, size_t cnt) +{ + if (cnt > 0) + { + size_t i = cnt - 1; + while (i != 0) + { + i--; + if (values[i] < values[i + 1]) + { + size_t j; + for (j = cnt - 1; values[i] >= values[j]; j--) + continue; + swap (values + i, values + j); + reverse (values + (i + 1), cnt - (i + 1)); + return true; + } + } + + reverse (values, cnt); + } + + return false; +} + +/* Returns N!. */ +static unsigned +factorial (unsigned n) +{ + unsigned value = 1; + while (n > 1) + value *= n--; + return value; +} + +/* Returns the number of permutations of the CNT values in + VALUES. If VALUES contains duplicates, they must be + adjacent. */ +static unsigned +expected_perms (int *values, size_t cnt) +{ + size_t i, j; + unsigned perm_cnt; + + perm_cnt = factorial (cnt); + for (i = 0; i < cnt; i = j) + { + for (j = i + 1; j < cnt; j++) + if (values[i] != values[j]) + break; + perm_cnt /= factorial (j - i); + } + return perm_cnt; +} + +/* Tests whether PARTS is a K-part integer composition of N. + Returns true if so, false otherwise. */ +static bool UNUSED +is_k_composition (int n, int k, const int parts[]) +{ + int sum; + int i; + + sum = 0; + for (i = 0; i < k; i++) + { + if (parts[i] < 1 || parts[i] > n) + return false; + sum += parts[i]; + } + return sum == n; +} + +/* Advances the K-part integer composition of N stored in PARTS + to the next lexicographically greater one. + Returns true if successful, false if the composition was + already the greatest K-part composition of N (in which case + PARTS is unaltered). */ +static bool +next_k_composition (int n UNUSED, int k, int parts[]) +{ + int x, i; + + assert (is_k_composition (n, k, parts)); + if (k == 1) + return false; + + for (i = k - 1; i > 0; i--) + if (parts[i] > 1) + break; + if (i == 0) + return false; + + x = parts[i] - 1; + parts[i] = 1; + parts[i - 1]++; + parts[k - 1] = x; + + assert (is_k_composition (n, k, parts)); + return true; +} + +/* Advances *K and PARTS to the next integer composition of N. + Compositions are ordered from shortest to longest and in + lexicographical order within a given length. + Before the first call, initialize *K to 0. + After each successful call, *K contains the length of the + current composition and the *K elements in PARTS contain its + parts. + Returns true if successful, false if the set of compositions + has been exhausted. */ +static bool +next_composition (int n, int *k, int parts[]) +{ + if (*k >= 1 && next_k_composition (n, *k, parts)) + return true; + else if (*k < n) + { + int i; + for (i = 0; i < *k; i++) + parts[i] = 1; + parts[i] = n - *k; + (*k)++; + return true; + } + else + return false; +} + +/* Inserts sequences without duplicates into a heap, and then + ensures that they appear as the minimum element in the correct + order as we delete them. Exhaustively tests every input + permutation up to 'max_elems' elements. */ +static void +test_insert_no_dups_delete_min (void) +{ + const int max_elems = 8; + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt++) + { + struct heap *h; + struct element *elements; + int *values; + unsigned int permutation_cnt; + int i; + + values = xnmalloc (cnt, sizeof *values); + elements = xnmalloc (cnt, sizeof *elements); + for (i = 0; i < cnt; i++) + values[i] = i; + + h = heap_create (compare_elements, &aux_data); + permutation_cnt = 0; + while (permutation_cnt == 0 || next_permutation (values, cnt)) + { + int i; + + for (i = 0; i < cnt; i++) + elements[i].x = values[i]; + + check (heap_is_empty (h)); + for (i = 0; i < cnt; i++) + { + heap_insert (h, &elements[i].node); + check (heap_node_to_element (heap_minimum (h))->x + == min_int (values, i + 1)); + check (heap_count (h) == i + 1); + } + + for (i = 0; i < cnt; i++) + { + check (heap_node_to_element (heap_minimum (h))->x == i); + heap_delete (h, heap_minimum (h)); + } + check (heap_is_empty (h)); + permutation_cnt++; + } + check (permutation_cnt == factorial (cnt)); + heap_destroy (h); + free (values); + free (elements); + } +} + +/* Inserts sequences with duplicates into a heap, and then + ensures that they appear as the minimum element in the correct + order as we delete them. Exhaustively tests every input + permutation up to 'max_elems' elements. + + See Usenet article <87mz4utika.fsf@blp.benpfaff.org> for + details of the algorithm used here. */ +static void +test_insert_with_dups_delete_min (void) +{ + const int max_elems = 7; + int cnt; + + for (cnt = 1; cnt <= max_elems; cnt++) + { + unsigned int composition_cnt; + int *dups; + int unique_cnt; + int *values; + int *sorted_values; + struct element *elements; + int n = 0; + + dups = xnmalloc (cnt, sizeof *dups); + values = xnmalloc (cnt, sizeof *values); + sorted_values = xnmalloc (cnt, sizeof *sorted_values); + elements = xnmalloc (cnt, sizeof *elements); + + unique_cnt = 0; + composition_cnt = 0; + while (next_composition (cnt, &unique_cnt, dups)) + { + struct heap *h; + int i, j, k; + unsigned int permutation_cnt; + + k = 0; + for (i = 0; i < unique_cnt; i++) + for (j = 0; j < dups[i]; j++) + { + values[k] = i; + sorted_values[k] = i; + k++; + } + check (k == cnt); + + h = heap_create (compare_elements, &aux_data); + permutation_cnt = 0; + while (permutation_cnt == 0 || next_permutation (values, cnt)) + { + int min = INT_MAX; + + for (i = 0; i < cnt; i++) + elements[i].x = values[i]; + n++; + + check (heap_is_empty (h)); + for (i = 0; i < cnt; i++) + { + heap_insert (h, &elements[i].node); + if (values[i] < min) + min = values[i]; + check (heap_node_to_element (heap_minimum (h))->x == min); + check (heap_count (h) == i + 1); + } + + for (i = 0; i < cnt; i++) + { + struct element *min = heap_node_to_element (heap_minimum (h)); + check (min->x == sorted_values[i]); + heap_delete (h, heap_minimum (h)); + } + check (heap_is_empty (h)); + permutation_cnt++; + } + check (permutation_cnt == expected_perms (values, cnt)); + heap_destroy (h); + + composition_cnt++; + } + check (composition_cnt == 1 << (cnt - 1)); + + free (dups); + free (values); + free (sorted_values); + free (elements); + } +} + +/* Inserts a sequence without duplicates into a heap, then + deletes them in a different order. */ +static void +test_insert_no_dups_delete_random (void) +{ + const int max_elems = 5; + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt++) + { + struct heap *h; + struct element *elements; + int *insert, *delete; + unsigned int insert_perm_cnt; + int i; + + insert = xnmalloc (cnt, sizeof *insert); + delete = xnmalloc (cnt, sizeof *delete); + elements = xnmalloc (cnt, sizeof *elements); + for (i = 0; i < cnt; i++) + { + insert[i] = i; + delete[i] = i; + elements[i].x = i; + } + + h = heap_create (compare_elements, &aux_data); + insert_perm_cnt = 0; + while (insert_perm_cnt == 0 || next_permutation (insert, cnt)) + { + unsigned int delete_perm_cnt = 0; + + while (delete_perm_cnt == 0 || next_permutation (delete, cnt)) + { + int min; + int i; + + check (heap_is_empty (h)); + min = INT_MAX; + for (i = 0; i < cnt; i++) + { + heap_insert (h, &elements[insert[i]].node); + if (insert[i] < min) + min = insert[i]; + check (heap_node_to_element (heap_minimum (h))->x == min); + check (heap_count (h) == i + 1); + } + + for (i = 0; i < cnt; i++) + { + int new_min = min_int (delete + i + 1, cnt - i - 1); + heap_delete (h, &elements[delete[i]].node); + check (heap_count (h) == cnt - i - 1); + if (!heap_is_empty (h)) + check (heap_node_to_element (heap_minimum (h))->x == new_min); + } + check (heap_is_empty (h)); + delete_perm_cnt++; + } + check (delete_perm_cnt == factorial (cnt)); + insert_perm_cnt++; + } + check (insert_perm_cnt == factorial (cnt)); + heap_destroy (h); + free (insert); + free (delete); + free (elements); + } +} + +/* Inserts a set of values into a heap, then changes them to a + different random set of values, then removes them in sorted + order. */ +static void +test_inc_dec (void) +{ + const int max_elems = 8; + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt++) + { + struct heap *h; + struct element *elements; + int *insert, *delete; + unsigned int insert_perm_cnt; + int i; + + insert = xnmalloc (cnt, sizeof *insert); + delete = xnmalloc (cnt, sizeof *delete); + elements = xnmalloc (cnt, sizeof *elements); + for (i = 0; i < cnt; i++) + insert[i] = i; + + h = heap_create (compare_elements, &aux_data); + insert_perm_cnt = 0; + while (insert_perm_cnt == 0 || next_permutation (insert, cnt)) + { + for (i = 0; i < cnt; i++) + elements[i].x = insert[i]; + + check (heap_is_empty (h)); + for (i = 0; i < cnt; i++) + { + int new_min = min_int (insert, i + 1); + heap_insert (h, &elements[i].node); + check (heap_node_to_element (heap_minimum (h))->x == new_min); + check (heap_count (h) == i + 1); + } + + for (i = 0; i < cnt; i++) + delete[i] = insert[i]; + for (i = 0; i < cnt; i++) + { + int old_value, old_min, new_min; + old_min = min_int (delete, cnt); + old_value = delete[i]; + elements[i].x = delete[i] = rand () % (cnt + 2) - 1; + new_min = min_int (delete, cnt); + heap_changed (h, &elements[i].node); + check (heap_node_to_element (heap_minimum (h))->x + == min_int (delete, cnt)); + } + + for (i = 0; i < cnt; i++) + { + int new_min = min_int (delete + i + 1, cnt - i - 1); + heap_delete (h, &elements[i].node); + check (heap_count (h) == cnt - i - 1); + if (!heap_is_empty (h)) + check (heap_node_to_element (heap_minimum (h))->x == new_min); + } + check (heap_is_empty (h)); + insert_perm_cnt++; + } + check (insert_perm_cnt == factorial (cnt)); + heap_destroy (h); + free (insert); + free (delete); + free (elements); + } +} + +/* Performs a random sequence of insertions and deletions in a + heap. */ +static void +test_random_insert_delete (void) +{ + const int max_elems = 64; + const int num_actions = 250000; + struct heap *h; + int *values; + struct element *elements; + int cnt; + int insert_chance; + int i; + + values = xnmalloc (max_elems, sizeof *values); + elements = xnmalloc (max_elems, sizeof *elements); + cnt = 0; + insert_chance = 5; + + h = heap_create (compare_elements, &aux_data); + for (i = 0; i < num_actions; i++) + { + enum { INSERT, DELETE } action; + + if (cnt == 0) + { + action = INSERT; + if (insert_chance < 9) + insert_chance++; + } + else if (cnt == max_elems) + { + action = DELETE; + if (insert_chance > 0) + insert_chance--; + } + else + action = rand () % 10 < insert_chance ? INSERT : DELETE; + + if (action == INSERT) + { + int new_value; + int old_min; + + new_value = rand () % max_elems; + values[cnt] = new_value; + elements[cnt].x = new_value; + + heap_insert (h, &elements[cnt].node); + + old_min = min_int (values, cnt); + + cnt++; + } + else if (action == DELETE) + { + int del_idx; + int del_value; + int old_min, new_min; + + old_min = min_int (values, cnt); + + del_idx = rand () % cnt; + del_value = values[del_idx]; + heap_delete (h, &elements[del_idx].node); + + cnt--; + if (del_idx != cnt) + { + values[del_idx] = values[cnt]; + elements[del_idx] = elements[cnt]; + heap_moved (h, &elements[del_idx].node); + } + + new_min = min_int (values, cnt); + } + else + abort (); + + check (heap_count (h) == cnt); + check (heap_is_empty (h) == (cnt == 0)); + if (cnt > 0) + check (heap_node_to_element (heap_minimum (h))->x + == min_int (values, cnt)); + } + heap_destroy (h); + free (elements); + free (values); +} + +/* Main program. */ + +/* Runs TEST_FUNCTION and prints a message about NAME. */ +static void +run_test (void (*test_function) (void), const char *name) +{ + test_name = name; + putchar ('.'); + fflush (stdout); + test_function (); +} + +int +main (void) +{ + run_test (test_insert_no_dups_delete_min, + "insert (no dups), delete minimum values"); + run_test (test_insert_with_dups_delete_min, + "insert with dups, delete minimum values"); + run_test (test_insert_no_dups_delete_random, + "insert (no dups), delete in random order"); + run_test (test_inc_dec, "increase and decrease values"); + run_test (test_random_insert_delete, "random insertions and deletions"); + putchar ('\n'); + + return 0; +} -- 2.30.2