[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Pspp-cvs] pspp src/libpspp/ChangeLog src/libpspp/automake...
|
From: |
Ben Pfaff |
|
Subject: |
[Pspp-cvs] pspp src/libpspp/ChangeLog src/libpspp/automake... |
|
Date: |
Wed, 10 Jan 2007 14:50:16 +0000 |
CVSROOT: /cvsroot/pspp
Module name: pspp
Changes by: Ben Pfaff <blp> 07/01/10 14:50:16
Modified files:
src/libpspp : ChangeLog automake.mk
tests : ChangeLog automake.mk
Added files:
src/libpspp : heap.c heap.h
tests/libpspp : heap-test.c
Log message:
Add heap data structure to src/libpspp, and a test to tests/libpspp.
Thanks to John Darrington for review.
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/ChangeLog?cvsroot=pspp&r1=1.46&r2=1.47
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/automake.mk?cvsroot=pspp&r1=1.18&r2=1.19
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/heap.c?cvsroot=pspp&rev=1.1
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/heap.h?cvsroot=pspp&rev=1.1
http://cvs.savannah.gnu.org/viewcvs/pspp/tests/ChangeLog?cvsroot=pspp&r1=1.75&r2=1.76
http://cvs.savannah.gnu.org/viewcvs/pspp/tests/automake.mk?cvsroot=pspp&r1=1.23&r2=1.24
http://cvs.savannah.gnu.org/viewcvs/pspp/tests/libpspp/heap-test.c?cvsroot=pspp&rev=1.1
Patches:
Index: src/libpspp/ChangeLog
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/ChangeLog,v
retrieving revision 1.46
retrieving revision 1.47
diff -u -b -r1.46 -r1.47
--- src/libpspp/ChangeLog 11 Dec 2006 15:39:23 -0000 1.46
+++ src/libpspp/ChangeLog 10 Jan 2007 14:50:16 -0000 1.47
@@ -1,3 +1,11 @@
+Wed Jan 10 06:49:38 2007 Ben Pfaff <address@hidden>
+
+ * 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 <address@hidden>
* str.c (ss_tokenize): Skip the first delimiter character
Index: src/libpspp/automake.mk
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/automake.mk,v
retrieving revision 1.18
retrieving revision 1.19
diff -u -b -r1.18 -r1.19
--- src/libpspp/automake.mk 24 Dec 2006 06:57:54 -0000 1.18
+++ src/libpspp/automake.mk 10 Jan 2007 14:50:16 -0000 1.19
@@ -23,6 +23,8 @@
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 \
Index: tests/ChangeLog
===================================================================
RCS file: /cvsroot/pspp/pspp/tests/ChangeLog,v
retrieving revision 1.75
retrieving revision 1.76
diff -u -b -r1.75 -r1.76
--- tests/ChangeLog 22 Dec 2006 04:38:23 -0000 1.75
+++ tests/ChangeLog 10 Jan 2007 14:50:16 -0000 1.76
@@ -1,3 +1,9 @@
+Wed Jan 10 06:50:01 2007 Ben Pfaff <address@hidden>
+
+ * automake.mk: Add tests/libpspp/heap-test.
+
+ * test/libpspp/heap-test.c: New test.
+
Wed Dec 13 21:00:46 2006 Ben Pfaff <address@hidden>
* command/rank.sh (activity): Use DELETE VAR (which is new)
Index: tests/automake.mk
===================================================================
RCS file: /cvsroot/pspp/pspp/tests/automake.mk,v
retrieving revision 1.23
retrieving revision 1.24
diff -u -b -r1.23 -r1.24
--- tests/automake.mk 22 Dec 2006 10:24:18 -0000 1.23
+++ tests/automake.mk 10 Jan 2007 14:50:16 -0000 1.24
@@ -131,10 +131,14 @@
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 @@
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 \
Index: src/libpspp/heap.c
===================================================================
RCS file: src/libpspp/heap.c
diff -N src/libpspp/heap.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ src/libpspp/heap.c 10 Jan 2007 14:50:16 -0000 1.1
@@ -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 <config.h>
+#endif
+
+#include <libpspp/heap.h>
+#include <libpspp/pool.h>
+#include <libpspp/assertion.h>
+
+#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;
+}
Index: src/libpspp/heap.h
===================================================================
RCS file: src/libpspp/heap.h
diff -N src/libpspp/heap.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ src/libpspp/heap.h 10 Jan 2007 14:50:16 -0000 1.1
@@ -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 <stdbool.h>
+#include <stddef.h>
+
+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 */
Index: tests/libpspp/heap-test.c
===================================================================
RCS file: tests/libpspp/heap-test.c
diff -N tests/libpspp/heap-test.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ tests/libpspp/heap-test.c 10 Jan 2007 14:50:16 -0000 1.1
@@ -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 <config.h>
+#endif
+
+#include <libpspp/heap.h>
+
+#include <assert.h>
+#include <limits.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <libpspp/compiler.h>
+
+#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 <address@hidden> 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;
+}
- [Pspp-cvs] pspp src/libpspp/ChangeLog src/libpspp/automake...,
Ben Pfaff <=