From db8c531ad19eff86adbc11e5435f07d5f780ab4a Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Sat, 1 Jul 2006 22:34:26 +0000 Subject: [PATCH] Add linked list library to PSPP. Reviewed by John Darrington, tested by Jason Stover. --- ChangeLog | 4 + Makefile.am | 1 + src/libpspp/ChangeLog | 12 + src/libpspp/automake.mk | 4 + src/libpspp/ll.c | 687 +++++++++++++ src/libpspp/ll.h | 457 +++++++++ src/libpspp/llx.c | 768 ++++++++++++++ src/libpspp/llx.h | 312 ++++++ tests/automake.mk | 18 +- tests/libpspp/ll-test.c | 2021 +++++++++++++++++++++++++++++++++++++ tests/libpspp/llx-test.c | 2069 ++++++++++++++++++++++++++++++++++++++ 11 files changed, 6352 insertions(+), 1 deletion(-) create mode 100644 src/libpspp/ll.c create mode 100644 src/libpspp/ll.h create mode 100644 src/libpspp/llx.c create mode 100644 src/libpspp/llx.h create mode 100644 tests/libpspp/ll-test.c create mode 100644 tests/libpspp/llx-test.c diff --git a/ChangeLog b/ChangeLog index 5e5f9897..1df380c8 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,7 @@ +Sat Jul 1 15:32:31 2006 Ben Pfaff + + * Makefile.am: Add noinst_PROGRAMS and define to empty. + Tue May 9 20:46:06 2006 Ben Pfaff * Smake: Add stdarg to GNULIB_MODULES. diff --git a/Makefile.am b/Makefile.am index 650446f7..1655d50a 100644 --- a/Makefile.am +++ b/Makefile.am @@ -39,6 +39,7 @@ MAINTAINERCLEANFILES = Makefile.in aclocal.m4 CLEANFILES = ACLOCAL_AMFLAGS = -I m4 -I gl/m4 noinst_LIBRARIES= +noinst_PROGRAMS= bin_PROGRAMS= include $(top_srcdir)/lib/automake.mk diff --git a/src/libpspp/ChangeLog b/src/libpspp/ChangeLog index 892dcd31..25d2de04 100644 --- a/src/libpspp/ChangeLog +++ b/src/libpspp/ChangeLog @@ -1,3 +1,15 @@ +Sat Jul 1 15:32:54 2006 Ben Pfaff + + * automake.mk: (src_libpspp_libpspp_a_SOURCES) Add new files. + + * ll.c: New file. + + * ll.h: New file. + + * llx.c: New file. + + * llx.h: New file. + Sun Jun 25 22:35:28 2006 Ben Pfaff Optimize rehashing: we know that none of the entries in the hash diff --git a/src/libpspp/automake.mk b/src/libpspp/automake.mk index b428672d..a8154966 100644 --- a/src/libpspp/automake.mk +++ b/src/libpspp/automake.mk @@ -18,6 +18,10 @@ src_libpspp_libpspp_a_SOURCES = \ src/libpspp/hash.h \ src/libpspp/i18n.c \ src/libpspp/i18n.h \ + src/libpspp/ll.c \ + src/libpspp/ll.h \ + src/libpspp/llx.c \ + src/libpspp/llx.h \ src/libpspp/magic.c \ src/libpspp/magic.h \ src/libpspp/misc.c \ diff --git a/src/libpspp/ll.c b/src/libpspp/ll.c new file mode 100644 index 00000000..9c322ada --- /dev/null +++ b/src/libpspp/ll.c @@ -0,0 +1,687 @@ +/* PSPP - computes sample statistics. + Copyright (C) 2006 Free Software Foundation, Inc. + Written by Ben Pfaff + + 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, circular doubly linked list. */ + +/* These library routines have no external dependencies other + than the standard C library. + + If you add routines in this file, please add a corresponding + test to ll-test.c. This test program should achieve 100% + coverage of lines and branches in this code, as reported by + "gcov -b". */ + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include +#include + +/* Returns the number of nodes in LIST (not counting the null + node). Executes in O(n) time in the length of the list. */ +size_t +ll_count (const struct ll_list *list) +{ + return ll_count_range (ll_head (list), ll_null (list)); +} + +/* Removes R0...R1 from their current list + and inserts them just before BEFORE. */ +void +ll_splice (struct ll *before, struct ll *r0, struct ll *r1) +{ + if (before != r0 && r0 != r1) + { + /* Change exclusive range to inclusive. */ + r1 = ll_prev (r1); + + /* Remove R0...R1 from its list. */ + r0->prev->next = r1->next; + r1->next->prev = r0->prev; + + /* Insert R0...R1 before BEFORE. */ + r0->prev = before->prev; + r1->next = before; + before->prev->next = r0; + before->prev = r1; + } +} + +/* Exchanges the positions of A and B, + which may be in the same list or different lists. */ +void +ll_swap (struct ll *a, struct ll *b) +{ + if (a != b) + { + if (ll_next (a) != b) + { + struct ll *a_next = ll_remove (a); + struct ll *b_next = ll_remove (b); + ll_insert (b_next, a); + ll_insert (a_next, b); + } + else + { + ll_remove (b); + ll_insert (a, b); + } + } +} + +/* Exchanges the positions of A0...A1 and B0...B1, + which may be in the same list or different lists but must not + overlap. */ +void +ll_swap_range (struct ll *a0, struct ll *a1, struct ll *b0, struct ll *b1) +{ + if (a0 == a1 || a1 == b0) + ll_splice (a0, b0, b1); + else if (b0 == b1 || b1 == a0) + ll_splice (b0, a0, a1); + else + { + struct ll *x0 = ll_prev (a0), *x1 = a1; + struct ll *y0 = ll_prev (b0), *y1 = b1; + a1 = ll_prev (a1); + b1 = ll_prev (b1); + x0->next = b0; + b0->prev = x0; + b1->next = x1; + x1->prev = b1; + y0->next = a0; + a0->prev = y0; + a1->next = y1; + y1->prev = a1; + } +} + +/* Removes from R0...R1 all the nodes that equal TARGET + according to COMPARE given auxiliary data AUX. + Returns the number of nodes removed. */ +size_t +ll_remove_equal (struct ll *r0, struct ll *r1, struct ll *target, + ll_compare_func *compare, void *aux) +{ + struct ll *x; + size_t count; + + count = 0; + for (x = r0; x != r1; ) + if (compare (x, target, aux) == 0) + { + x = ll_remove (x); + count++; + } + else + x = ll_next (x); + + return count; +} + +/* Removes from R0...R1 all the nodes for which PREDICATE returns + true given auxiliary data AUX. + Returns the number of nodes removed. */ +size_t +ll_remove_if (struct ll *r0, struct ll *r1, + ll_predicate_func *predicate, void *aux) +{ + struct ll *x; + size_t count; + + count = 0; + for (x = r0; x != r1; ) + if (predicate (x, aux)) + { + x = ll_remove (x); + count++; + } + else + x = ll_next (x); + + return count; +} + +/* Returns the first node in R0...R1 that equals TARGET + according to COMPARE given auxiliary data AUX. + Returns R1 if no node in R0...R1 equals TARGET. */ +struct ll * +ll_find_equal (const struct ll *r0, const struct ll *r1, + const struct ll *target, + ll_compare_func *compare, void *aux) +{ + const struct ll *x; + + for (x = r0; x != r1; x = ll_next (x)) + if (compare (x, target, aux) == 0) + break; + return (struct ll *) x; +} + +/* Returns the first node in R0...R1 for which PREDICATE returns + true given auxiliary data AUX. + Returns R1 if PREDICATE does not return true for any node in + R0...R1. */ +struct ll * +ll_find_if (const struct ll *r0, const struct ll *r1, + ll_predicate_func *predicate, void *aux) +{ + const struct ll *x; + + for (x = r0; x != r1; x = ll_next (x)) + if (predicate (x, aux)) + break; + return (struct ll *) x; +} + +/* Compares each pair of adjacent nodes in R0...R1 + using COMPARE with auxiliary data AUX + and returns the first node of the first pair that compares + equal. + Returns R1 if no pair compares equal. */ +struct ll * +ll_find_adjacent_equal (const struct ll *r0, const struct ll *r1, + ll_compare_func *compare, void *aux) +{ + if (r0 != r1) + { + const struct ll *x, *y; + + for (x = r0, y = ll_next (x); y != r1; x = y, y = ll_next (y)) + if (compare (x, y, aux) == 0) + return (struct ll *) x; + } + + return (struct ll *) r1; +} + +/* Returns the number of nodes in R0...R1. + Executes in O(n) time in the return value. */ +size_t +ll_count_range (const struct ll *r0, const struct ll *r1) +{ + const struct ll *x; + size_t count; + + count = 0; + for (x = r0; x != r1; x = ll_next (x)) + count++; + return count; +} + +/* Counts and returns the number of nodes in R0...R1 that equal + TARGET according to COMPARE given auxiliary data AUX. */ +size_t +ll_count_equal (const struct ll *r0, const struct ll *r1, + const struct ll *target, + ll_compare_func *compare, void *aux) +{ + const struct ll *x; + size_t count; + + count = 0; + for (x = r0; x != r1; x = ll_next (x)) + if (compare (x, target, aux) == 0) + count++; + return count; +} + +/* Counts and returns the number of nodes in R0...R1 for which + PREDICATE returns true given auxiliary data AUX. */ +size_t +ll_count_if (const struct ll *r0, const struct ll *r1, + ll_predicate_func *predicate, void *aux) +{ + const struct ll *x; + size_t count; + + count = 0; + for (x = r0; x != r1; x = ll_next (x)) + if (predicate (x, aux)) + count++; + return count; +} + +/* Returns the greatest node in R0...R1 according to COMPARE + given auxiliary data AUX. + Returns the first of multiple, equal maxima. */ +struct ll * +ll_max (const struct ll *r0, const struct ll *r1, + ll_compare_func *compare, void *aux) +{ + const struct ll *max = r0; + if (r0 != r1) + { + const struct ll *x; + + for (x = ll_next (r0); x != r1; x = ll_next (x)) + if (compare (x, max, aux) > 0) + max = x; + } + return (struct ll *) max; +} + +/* Returns the least node in R0...R1 according to COMPARE given + auxiliary data AUX. + Returns the first of multiple, equal minima. */ +struct ll * +ll_min (const struct ll *r0, const struct ll *r1, + ll_compare_func *compare, void *aux) +{ + const struct ll *min = r0; + if (r0 != r1) + { + const struct ll *x; + + for (x = ll_next (r0); x != r1; x = ll_next (x)) + if (compare (x, min, aux) < 0) + min = x; + } + return (struct ll *) min; +} + +/* Lexicographically compares A0...A1 to B0...B1. + Returns negative if A0...A1 < B0...B1, + zero if A0...A1 == B0...B1, and + positive if A0...A1 > B0...B1 + according to COMPARE given auxiliary data AUX. */ +int +ll_lexicographical_compare_3way (const struct ll *a0, const struct ll *a1, + const struct ll *b0, const struct ll *b1, + ll_compare_func *compare, void *aux) +{ + for (;;) + if (b0 == b1) + return a0 != a1; + else if (a0 == a1) + return -1; + else + { + int cmp = compare (a0, b0, aux); + if (cmp != 0) + return cmp; + + a0 = ll_next (a0); + b0 = ll_next (b0); + } +} + +/* Calls ACTION with auxiliary data AUX + for every node in R0...R1 in order. */ +void +ll_apply (struct ll *r0, struct ll *r1, ll_action_func *action, void *aux) +{ + struct ll *ll; + + for (ll = r0; ll != r1; ll = ll_next (ll)) + action (ll, aux); +} + +/* Reverses the order of nodes R0...R1. */ +void +ll_reverse (struct ll *r0, struct ll *r1) +{ + if (r0 != r1 && ll_next (r0) != r1) + { + struct ll *ll; + + for (ll = r0; ll != r1; ll = ll->prev) + { + struct ll *tmp = ll->next; + ll->next = ll->prev; + ll->prev = tmp; + } + r0->next->next = r1->prev; + r1->prev->prev = r0->next; + r0->next = r1; + r1->prev = r0; + } +} + +/* Arranges R0...R1 into the lexicographically next greater + permutation. Returns true if successful. + If R0...R1 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. + COMPARE with auxiliary data AUX is used to compare nodes. */ +bool +ll_next_permutation (struct ll *r0, struct ll *r1, + ll_compare_func *compare, void *aux) +{ + if (r0 != r1) + { + struct ll *i = ll_prev (r1); + while (i != r0) + { + i = ll_prev (i); + if (compare (i, ll_next (i), aux) < 0) + { + struct ll *j; + for (j = ll_prev (r1); compare (i, j, aux) >= 0; j = ll_prev (j)) + continue; + ll_swap (i, j); + ll_reverse (ll_next (j), r1); + return true; + } + } + + ll_reverse (r0, r1); + } + + return false; +} + +/* Arranges R0...R1 into the lexicographically next lesser + permutation. Returns true if successful. + If R0...R1 is already the lexicographically least + permutation of its elements (i.e. ordered from smallest to + greatest), arranges them into the lexicographically greatest + permutation (i.e. ordered from largest to smallest) and + returns false. + COMPARE with auxiliary data AUX is used to compare nodes. */ +bool +ll_prev_permutation (struct ll *r0, struct ll *r1, + ll_compare_func *compare, void *aux) +{ + if (r0 != r1) + { + struct ll *i = ll_prev (r1); + while (i != r0) + { + i = ll_prev (i); + if (compare (i, ll_next (i), aux) > 0) + { + struct ll *j; + for (j = ll_prev (r1); compare (i, j, aux) <= 0; j = ll_prev (j)) + continue; + ll_swap (i, j); + ll_reverse (ll_next (j), r1); + return true; + } + } + + ll_reverse (r0, r1); + } + + return false; +} + +/* Sorts R0...R1 into ascending order + according to COMPARE given auxiliary data AUX. + In use, keep in mind that R0 may move during the sort, so that + afterward R0...R1 may denote a different range. + (On the other hand, R1 is fixed in place.) + Runs in O(n lg n) time in the number of nodes in the range. */ +void +ll_sort (struct ll *r0, struct ll *r1, ll_compare_func *compare, void *aux) +{ + struct ll *pre_r0; + size_t output_run_cnt; + + if (r0 == r1 || ll_next (r0) == r1) + return; + + pre_r0 = ll_prev (r0); + do + { + struct ll *a0 = ll_next (pre_r0); + for (output_run_cnt = 1; ; output_run_cnt++) + { + struct ll *a1 = ll_find_run (a0, r1, compare, aux); + struct ll *a2 = ll_find_run (a1, r1, compare, aux); + if (a1 == a2) + break; + + a0 = ll_merge (a0, a1, a1, a2, compare, aux); + } + } + while (output_run_cnt > 1); +} + +/* Finds the extent of a run of nodes of increasing value + starting at R0 and extending no farther than R1. + Returns the first node in R0...R1 that is less than the + preceding node, or R1 if R0...R1 are arranged in nondecreasing + order. */ +struct ll * +ll_find_run (const struct ll *r0, const struct ll *r1, + ll_compare_func *compare, void *aux) +{ + if (r0 != r1) + { + do + { + r0 = ll_next (r0); + } + while (r0 != r1 && compare (ll_prev (r0), r0, aux) <= 0); + } + + return (struct ll *) r0; +} + +/* Merges B0...B1 into A0...A1 according to COMPARE given + auxiliary data AUX. + The ranges may be in the same list or different lists, but + must not overlap. + Returns the end of the merged range. + The merge is "stable" if A0...A1 is considered to precede + B0...B1, regardless of their actual ordering. + Runs in O(n) time in the total number of nodes in the ranges. */ +struct ll * +ll_merge (struct ll *a0, struct ll *a1, struct ll *b0, struct ll *b1, + ll_compare_func *compare, void *aux) +{ + if (a0 != a1 && b0 != b1) + { + a1 = ll_prev (a1); + b1 = ll_prev (b1); + for (;;) + if (compare (a0, b0, aux) <= 0) + { + if (a0 == a1) + { + ll_splice (ll_next (a0), b0, ll_next (b1)); + return ll_next (b1); + } + a0 = ll_next (a0); + } + else + { + if (b0 != b1) + { + struct ll *x = b0; + b0 = ll_remove (b0); + ll_insert (a0, x); + } + else + { + ll_splice (a0, b0, ll_next (b0)); + return ll_next (a1); + } + } + } + else + { + ll_splice (a0, b0, b1); + return b1; + } +} + +/* Returns true if R0...R1 is sorted in ascending order according + to COMPARE given auxiliary data AUX, false otherwise. */ +bool +ll_is_sorted (const struct ll *r0, const struct ll *r1, + ll_compare_func *compare, void *aux) +{ + return ll_find_run (r0, r1, compare, aux) == r1; +} + +/* Removes all but the first in each group of sequential + duplicates in R0...R1. Duplicates are determined using + COMPARE given auxiliary data AUX. Removed duplicates are + inserted before DUPS if it is nonnull; otherwise, their + identities are lost. + Only sequential duplicates are removed. ll_sort() may be used + to bring duplicates together, or ll_sort_unique() can do both + at once. */ +size_t +ll_unique (struct ll *r0, struct ll *r1, struct ll *dups, + ll_compare_func *compare, void *aux) +{ + size_t count = 0; + + if (r0 != r1) + { + struct ll *x = r0; + for (;;) + { + struct ll *y = ll_next (x); + if (y == r1) + { + count++; + break; + } + + if (compare (x, y, aux) == 0) + { + ll_remove (y); + if (dups != NULL) + ll_insert (dups, y); + } + else + { + x = y; + count++; + } + } + } + + return count; +} + +/* Sorts R0...R1 and removes duplicates. + Removed duplicates are inserted before DUPS if it is nonnull; + otherwise, their identities are lost. + Comparisons are made with COMPARE given auxiliary data AUX. + In use, keep in mind that R0 may move during the sort, so that + afterward R0...R1 may denote a different range. + (On the other hand, R1 is fixed in place.) + Runs in O(n lg n) time in the number of nodes in the range. */ +void +ll_sort_unique (struct ll *r0, struct ll *r1, struct ll *dups, + ll_compare_func *compare, void *aux) +{ + struct ll *pre_r0 = ll_prev (r0); + ll_sort (r0, r1, compare, aux); + ll_unique (ll_next (pre_r0), r1, dups, compare, aux); +} + +/* Inserts NEW_ELEM in the proper position in R0...R1, which must + be sorted according to COMPARE given auxiliary data AUX. + If NEW_ELEM is equal to one or more existing nodes in R0...R1, + then it is inserted after the existing nodes it equals. + Runs in O(n) time in the number of nodes in the range. */ +void +ll_insert_ordered (struct ll *r0, struct ll *r1, struct ll *new_elem, + ll_compare_func *compare, void *aux) +{ + struct ll *x; + + for (x = r0; x != r1; x = ll_next (x)) + if (compare (x, new_elem, aux) > 0) + break; + ll_insert (x, new_elem); +} + +/* Partitions R0...R1 into those nodes for which PREDICATE given + auxiliary data AUX returns true, followed by those for which + PREDICATE returns false. + Returns the first node in the "false" group, or R1 if + PREDICATE is true for every node in R0...R1. + The partition is "stable" in that the nodes in each group + retain their original relative order. + Runs in O(n) time in the number of nodes in the range. */ +struct ll * +ll_partition (struct ll *r0, struct ll *r1, + ll_predicate_func *predicate, void *aux) +{ + struct ll *t0, *t1; + + for (;;) + { + if (r0 == r1) + return r0; + else if (!predicate (r0, aux)) + break; + + r0 = ll_next (r0); + } + + for (t0 = r0;; t0 = t1) + { + do + { + t0 = ll_next (t0); + if (t0 == r1) + return r0; + } + while (!predicate (t0, aux)); + + t1 = t0; + do + { + t1 = ll_next (t1); + if (t1 == r1) + { + ll_splice (r0, t0, t1); + return r0; + } + } + while (predicate (t1, aux)); + + ll_splice (r0, t0, t1); + } +} + +/* Verifies that R0...R1 is parititioned into a sequence of nodes + for which PREDICATE given auxiliary data AUX returns true, + followed by those for which PREDICATE returns false. + Returns a null pointer if R0...R1 is not partitioned this way. + Otherwise, returns the first node in the "false" group, or R1 + if PREDICATE is true for every node in R0...R1. */ +struct ll * +ll_find_partition (const struct ll *r0, const struct ll *r1, + ll_predicate_func *predicate, void *aux) +{ + const struct ll *partition, *x; + + for (partition = r0; partition != r1; partition = ll_next (partition)) + if (!predicate (partition, aux)) + break; + + for (x = partition; x != r1; x = ll_next (x)) + if (predicate (x, aux)) + return NULL; + + return (struct ll *) partition; +} + diff --git a/src/libpspp/ll.h b/src/libpspp/ll.h new file mode 100644 index 00000000..4414e2e6 --- /dev/null +++ b/src/libpspp/ll.h @@ -0,0 +1,457 @@ +/* PSPP - computes sample statistics. + Copyright (C) 2006 Free Software Foundation, Inc. + Written by Ben Pfaff . + + 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. */ + +/* Circular doubly linked lists. + + This header (ll.h) supplies "embedded" circular doubly linked + lists. Its companion header (llx.h) supplies "external" + circular doubly linked lists. The two variants are described + briefly here. The embedded variant, for which this is the + header, is described in slightly more detail below. Each + function also has a detailed usage comment at its point of + definition. + + The "ll" embedded linked list implementation puts the linked + list node within the data structure that the list contains. + This makes allocation efficient, in space and time. It also + makes it easy to find the list node associated with a given + object. However, it's difficult to include a given object in + an arbitrary number of lists, or to include a single object in + a single list in multiple positions. + + The "llx" external linked list implementation allocates linked + list nodes separately from the objects in the list. Adding + and removing linked list nodes requires dynamic allocation, so + it is normally slower and takes more memory than the embedded + implementation. It also requires searching the list to find + the list node associated with a given object. However, it's + easy to include a given object in an arbitrary number of + lists, or to include a single object more than once within a + single list. It's also possible to create an external linked + list without adding a member to the data structure that the + list contains. */ + +#ifndef LL_H +#define LL_H + +#include +#include +#include + +/* Embedded, circular doubly linked list. + + Each list contains a single "null" element that separates the + head and the tail of the list. The null element is both + before the head and after the tail of the list. An empty list + contains just the null element. + + An embedded linked list is represented as `struct ll_list'. + Each node in the list, presumably a structure type, must + include a `struct ll' member. + + Many list functions take ranges of nodes as arguments. Ranges + are "half-open"; that is, R0...R1 includes R0 but not R1. A + range whose endpoints are the same (e.g. R0...R0) contains no + nodes at all. + + Here's an example of a structure type that includes a `struct + ll': + + struct ll_list list; + + struct foo + { + struct ll ll; // List member. + int x; // Another member. + }; + + Here's an example of iteration from head to tail: + + struct ll *ll; + for (ll = ll_head (&list); ll != ll_null (&list); ll = ll_next (ll)) + { + struct foo *foo = ll_data (ll, struct foo, ll); + ...do something with foo->x... + } + + Here's another way to do it: + + struct ll *ll = ll_null (&list); + while ((ll = ll_next (ll)) != ll_null (&list)) + { + struct foo *foo = ll_data (ll, struct foo, ll); + ...do something with foo->x... + } + + Here's a third way: + + struct foo *foo; + ll_for_each (foo, struct foo, ll, &list) + { + ...do something with foo->x... + } +*/ + +/* Returns the data structure corresponding to the given node LL, + assuming that LL is embedded as the given MEMBER name in data + type STRUCT. */ +#define ll_data(LL, STRUCT, MEMBER) \ + ((STRUCT *) ((char *) (LL) - offsetof (STRUCT, MEMBER))) + +/* Linked list node. */ +struct ll + { + struct ll *next; /* Next node. */ + struct ll *prev; /* Previous node. */ + }; + +/* Linked list. */ +struct ll_list + { + struct ll null; /* Null node. */ + }; + +/* Returns negative if A < B, zero if A == B, positive if A > B. */ +typedef int ll_compare_func (const struct ll *a, + const struct ll *b, void *aux); + +/* Returns true or false depending on properties of LL. */ +typedef bool ll_predicate_func (const struct ll *ll, void *aux); + +/* Takes some action on LL. */ +typedef void ll_action_func (struct ll *ll, void *aux); + +/* Suitable for use as the initializer for a `struct ll_list' + named LIST. Typical usage: + struct ll_list list = LL_INITIALIZER (list); + LL_INITIALIZER() is an alternative to ll_init(). */ +#define LL_INITIALIZER(LIST) { { &(LIST).null, &(LIST).null } } + +/* Basics. */ +static inline void ll_init (struct ll_list *); +static inline bool ll_is_empty (const struct ll_list *); +size_t ll_count (const struct ll_list *); + +/* Iteration. */ +static inline struct ll *ll_head (const struct ll_list *); +static inline struct ll *ll_tail (const struct ll_list *); +static inline struct ll *ll_null (const struct ll_list *); +static inline struct ll *ll_next (const struct ll *); +static inline struct ll *ll_prev (const struct ll *); + +/* Stack- and queue-like behavior. */ +static inline void ll_push_head (struct ll_list *, struct ll *); +static inline void ll_push_tail (struct ll_list *, struct ll *); +static inline struct ll *ll_pop_head (struct ll_list *); +static inline struct ll *ll_pop_tail (struct ll_list *); + +/* Insertion. */ +static inline void ll_insert (struct ll *before, struct ll *new); +void ll_splice (struct ll *before, struct ll *r0, struct ll *r1); +void ll_swap (struct ll *a, struct ll *b); +void ll_swap_range (struct ll *a0, struct ll *a1, + struct ll *b0, struct ll *b1); + +/* Removal. */ +static inline struct ll *ll_remove (struct ll *); +static inline void ll_remove_range (struct ll *r0, struct ll *r1); +size_t ll_remove_equal (struct ll *r0, struct ll *r1, struct ll *target, + ll_compare_func *, void *aux); +size_t ll_remove_if (struct ll *r0, struct ll *r1, + ll_predicate_func *, void *aux); +static inline void ll_moved (struct ll *); + +/* Non-mutating algorithms. */ +struct ll *ll_find_equal (const struct ll *r0, const struct ll *r1, + const struct ll *target, + ll_compare_func *, void *aux); +struct ll *ll_find_if (const struct ll *r0, const struct ll *r1, + ll_predicate_func *, void *aux); +struct ll *ll_find_adjacent_equal (const struct ll *r0, const struct ll *r1, + ll_compare_func *, void *aux); +size_t ll_count_range (const struct ll *r0, const struct ll *r1); +size_t ll_count_equal (const struct ll *r0, const struct ll *r1, + const struct ll *target, + ll_compare_func *, void *aux); +size_t ll_count_if (const struct ll *r0, const struct ll *r1, + ll_predicate_func *, void *aux); +struct ll *ll_max (const struct ll *r0, const struct ll *r1, + ll_compare_func *, void *aux); +struct ll *ll_min (const struct ll *r0, const struct ll *r1, + ll_compare_func *, void *aux); +int ll_lexicographical_compare_3way (const struct ll *a0, const struct ll *a1, + const struct ll *b0, const struct ll *b1, + ll_compare_func *, void *aux); + +/* Mutating algorithms. */ +void ll_apply (struct ll *r0, struct ll *r1, ll_action_func *, void *aux); +void ll_reverse (struct ll *r0, struct ll *r1); +bool ll_next_permutation (struct ll *r0, struct ll *r1, + ll_compare_func *, void *aux); +bool ll_prev_permutation (struct ll *r0, struct ll *r1, + ll_compare_func *, void *aux); + +/* Sorted list functions. */ +void ll_sort (struct ll *r0, struct ll *r1, ll_compare_func *, void *aux); +struct ll *ll_find_run (const struct ll *r0, const struct ll *r1, + ll_compare_func *, void *aux); +struct ll *ll_merge (struct ll *a0, struct ll *a1, + struct ll *b0, struct ll *b1, + ll_compare_func *, void *aux); +bool ll_is_sorted (const struct ll *r0, const struct ll *r1, + ll_compare_func *, void *aux); +size_t ll_unique (struct ll *r0, struct ll *r1, struct ll *dups, + ll_compare_func *, void *aux); +void ll_sort_unique (struct ll *r0, struct ll *r1, struct ll *dups, + ll_compare_func *, void *aux); +void ll_insert_ordered (struct ll *r0, struct ll *r1, struct ll *new_elem, + ll_compare_func *, void *aux); +struct ll *ll_partition (struct ll *r0, struct ll *r1, + ll_predicate_func *, void *aux); +struct ll *ll_find_partition (const struct ll *r0, const struct ll *r1, + ll_predicate_func *, void *aux); + +/* Iteration helper macros. */ + +/* Sets DATA to each object in LIST in turn, assuming that each + `struct ll' in LIST is embedded as the given MEMBER name in + data type STRUCT. + + Behavior is undefined if DATA is removed from the list between + loop iterations. */ +#define ll_for_each(DATA, STRUCT, MEMBER, LIST) \ + for (DATA = ll_head__ (STRUCT, MEMBER, LIST); \ + DATA != NULL; \ + DATA = ll_next__ (DATA, STRUCT, MEMBER, LIST)) + +/* Continues a iteration of LIST, starting from the object + currently in DATA and continuing forward through the remainder + of the list, assuming that each `struct ll' in LIST is + embedded as the given MEMBER name in data type STRUCT. + + Behavior is undefined if DATA is removed from the list between + loop iterations. */ +#define ll_for_each_continue(DATA, STRUCT, MEMBER, LIST) \ + for (; \ + DATA != NULL; \ + DATA = ll_next__ (DATA, STRUCT, MEMBER, LIST)) + +/* Sets DATA to each object in LIST in turn, assuming that each + `struct ll' in LIST is embedded as the given MEMBER name in + data type STRUCT. NEXT must be another variable of the same + type as DATA. + + Behavior is well-defined even if DATA is removed from the list + between iterations. */ +#define ll_for_each_safe(DATA, NEXT, STRUCT, MEMBER, LIST) \ + for (DATA = ll_head__ (STRUCT, MEMBER, LIST); \ + (DATA != NULL \ + ? (NEXT = ll_next__ (DATA, STRUCT, MEMBER, LIST), 1) \ + : 0); \ + DATA = NEXT) + +/* Continues a iteration of LIST, starting from the object + currently in DATA and continuing forward through the remainder + of the list, assuming that each `struct ll' in LIST is + embedded as the given MEMBER name in data type STRUCT. NEXT + must be another variable of the same type as DATA. + + Behavior is well-defined even if DATA is removed from the list + between iterations. */ +#define ll_for_each_safe_continue(DATA, NEXT, STRUCT, MEMBER, LIST) \ + for (; \ + (DATA != NULL \ + ? (NEXT = ll_next__ (DATA, STRUCT, MEMBER, LIST), 1) \ + : 0); \ + DATA = NEXT) + +/* Sets DATA to each object in LIST in turn, assuming that each + `struct ll' in LIST is embedded as the given MEMBER name in + data type STRUCT. + Each object is removed from LIST before its loop iteration. */ +#define ll_for_each_preremove(DATA, STRUCT, MEMBER, LIST) \ + while (!ll_is_empty (LIST) \ + ? (DATA = ll_data (ll_pop_head (LIST), STRUCT, MEMBER), 1) \ + : 0) + +/* Sets DATA to each object in LIST in turn, assuming that each + `struct ll' in LIST is embedded as the given MEMBER name in + data type STRUCT. + At the end of each loop iteration, DATA is removed from the + list. */ +#define ll_for_each_postremove(DATA, STRUCT, MEMBER, LIST) \ + for (; \ + (DATA = ll_head__ (STRUCT, MEMBER, LIST)) != NULL; \ + ll_remove (&DATA->MEMBER)) + +/* Macros for internal use only. */ +#define ll_data__(LL, STRUCT, MEMBER, LIST) \ + ((LL) != ll_null (LIST) ? ll_data (LL, STRUCT, MEMBER) : NULL) +#define ll_head__(STRUCT, MEMBER, LIST) \ + ll_data__ (ll_head (LIST), STRUCT, MEMBER, LIST) +#define ll_next__(DATA, STRUCT, MEMBER, LIST) \ + ll_data__ (ll_next (&DATA->MEMBER), STRUCT, MEMBER, LIST) +#define ll_remove__(DATA, STRUCT, MEMBER, LIST) \ + (ll_next (&DATA->MEMBER) == ll_null (LIST) \ + ? ll_remove (&DATA->MEMBER), NULL \ + : ll_data (ll_remove (&DATA->MEMBER), STRUCT, MEMBER)) + +/* Inline functions. */ + +/* Initializes LIST as an empty list. */ +static inline void +ll_init (struct ll_list *list) +{ + list->null.next = list->null.prev = &list->null; +} + +/* Returns true if LIST is empty (contains just the null node), + false if LIST is not empty (has at least one other node). + Executes in O(1) time. */ +static inline bool +ll_is_empty (const struct ll_list *list) +{ + return ll_head (list) == ll_null (list); +} + +/* Returns the first node in LIST, + or the null node if LIST is empty. */ +static inline struct ll * +ll_head (const struct ll_list *list) +{ + return ll_next (ll_null (list)); +} + +/* Returns the last node in LIST, + or the null node if LIST is empty. */ +static inline struct ll * +ll_tail (const struct ll_list *list) +{ + return ll_prev (ll_null (list)); +} + +/* Returns LIST's null node. */ +static inline struct ll * +ll_null (const struct ll_list *list) +{ + return (struct ll *) &list->null; +} + +/* Returns the node following LL in its list, + or the null node if LL is at the end of its list. + (In an empty list, the null node follows itself.) */ +static inline struct ll * +ll_next (const struct ll *ll) +{ + return ll->next; +} + +/* Returns the node preceding LL in its list, + or the null node if LL is the first node in its list. + (In an empty list, the null node precedes itself.) */ +static inline struct ll * +ll_prev (const struct ll *ll) +{ + return ll->prev; +} + +/* Inserts LL at the head of LIST. */ +static inline void +ll_push_head (struct ll_list *list, struct ll *ll) +{ + ll_insert (ll_head (list), ll); +} + +/* Inserts LL at the tail of LIST. */ +static inline void +ll_push_tail (struct ll_list *list, struct ll *ll) +{ + ll_insert (ll_null (list), ll); +} + +/* Removes and returns the first node in LIST, + which must not be empty. */ +static inline struct ll * +ll_pop_head (struct ll_list *list) +{ + struct ll *head; + assert (!ll_is_empty (list)); + head = ll_head (list); + ll_remove (head); + return head; +} + +/* Removes and returns the last node in LIST, + which must not be empty. */ +static inline struct ll * +ll_pop_tail (struct ll_list *list) +{ + struct ll *tail; + assert (!ll_is_empty (list)); + tail = ll_tail (list); + ll_remove (tail); + return tail; +} + +/* Inserts NEW_ELEM just before BEFORE. + (NEW_ELEM must not already be in a list.) */ +static inline void +ll_insert (struct ll *before, struct ll *new_elem) +{ + struct ll *before_prev = ll_prev (before); + new_elem->next = before; + new_elem->prev = before_prev; + before_prev->next = before->prev = new_elem; +} + +/* Removes LL from its list + and returns the node that formerly followed it. */ +static inline struct ll * +ll_remove (struct ll *ll) +{ + struct ll *next = ll_next (ll); + ll->prev->next = next; + ll->next->prev = ll->prev; + return next; +} + +/* Removes R0...R1 from their list. */ +static inline void +ll_remove_range (struct ll *r0, struct ll *r1) +{ + if (r0 != r1) + { + r1 = r1->prev; + r0->prev->next = r1->next; + r1->next->prev = r0->prev; + } +} + +/* Adjusts the nodes around LL to compensate for LL having + changed address, e.g. due to LL being inside a block of memory + that was realloc()'d. Equivalent to calling ll_remove() + before moving LL, then ll_insert() afterward, but more + efficient. */ +static inline void +ll_moved (struct ll *ll) +{ + ll->prev->next = ll->next->prev = ll; +} + +#endif /* ll.h */ diff --git a/src/libpspp/llx.c b/src/libpspp/llx.c new file mode 100644 index 00000000..2f970bf7 --- /dev/null +++ b/src/libpspp/llx.c @@ -0,0 +1,768 @@ +/* PSPP - computes sample statistics. + Copyright (C) 2006 Free Software Foundation, Inc. + Written by Ben Pfaff + + 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. */ + +/* External, circular doubly linked list. */ + +/* These library routines have no external dependencies, other + than ll.c and the standard C library. + + If you add routines in this file, please add a corresponding + test to llx-test.c. This test program should achieve 100% + coverage of lines and branches in this code, as reported by + "gcov -b". */ + +#ifdef HAVE_CONFIG_H +#include +#endif + +#include +#include +#include + +#if __GNUC__ >= 2 && !defined UNUSED +#define UNUSED __attribute__ ((unused)) +#else +#define UNUSED +#endif + +/* Destroys LIST and frees all of its nodes using MANAGER. + If DESTRUCTOR is non-null, each node in the list will be + passed to it in list order, with AUX as auxiliary data, before + that node is destroyed. */ +void +llx_destroy (struct llx_list *list, llx_action_func *destructor, void *aux, + const struct llx_manager *manager) +{ + struct llx *llx, *next; + + for (llx = llx_head (list); llx != llx_null (list); llx = next) + { + next = llx_next (llx); + if (destructor != NULL) + destructor (llx_data (llx), aux); + manager->release (llx, manager->aux); + } +} + +/* Returns the number of nodes in LIST (not counting the null + node). Executes in O(n) time in the length of the list. */ +size_t +llx_count (const struct llx_list *list) +{ + return llx_count_range (llx_head (list), llx_null (list)); +} + +/* Inserts DATA at the head of LIST. + Returns the new node (allocated with MANAGER), or a null + pointer if memory allocation failed. */ +struct llx * +llx_push_head (struct llx_list *list, void *data, + const struct llx_manager *manager) +{ + return llx_insert (llx_head (list), data, manager); +} + +/* Inserts DATA at the tail of LIST. + Returns the new node (allocated with MANAGER), or a null + pointer if memory allocation failed. */ +struct llx * +llx_push_tail (struct llx_list *list, void *data, + const struct llx_manager *manager) +{ + return llx_insert (llx_null (list), data, manager); +} + +/* Removes the first node in LIST, which must not be empty, + and returns the data that the node contained. + Frees the node removed with MANAGER. */ +void * +llx_pop_head (struct llx_list *list, const struct llx_manager *manager) +{ + struct llx *llx = llx_from_ll (ll_head (&list->ll_list)); + void *data = llx_data (llx); + llx_remove (llx, manager); + return data; +} + +/* Removes the last node in LIST, which must not be empty, + and returns the data that the node contained. + Frees the node removed with MANAGER. */ +void * +llx_pop_tail (struct llx_list *list, const struct llx_manager *manager) +{ + struct llx *llx = llx_from_ll (ll_tail (&list->ll_list)); + void *data = llx_data (llx); + llx_remove (llx, manager); + return data; +} + +/* Inserts DATA before BEFORE. + Returns the new node (allocated with MANAGER), or a null + pointer if memory allocation failed. */ +struct llx * +llx_insert (struct llx *before, void *data, const struct llx_manager *manager) +{ + struct llx *llx = manager->allocate (manager->aux); + if (llx != NULL) + { + llx->data = data; + ll_insert (&before->ll, &llx->ll); + } + return llx; +} + +/* Removes R0...R1 from their current list + and inserts them just before BEFORE. */ +void +llx_splice (struct llx *before, struct llx *r0, struct llx *r1) +{ + ll_splice (&before->ll, &r0->ll, &r1->ll); +} + +/* Exchanges the positions of A and B, + which may be in the same list or different lists. */ +void +llx_swap (struct llx *a, struct llx *b) +{ + ll_swap (&a->ll, &b->ll); +} + +/* Exchanges the positions of A0...A1 and B0...B1, + which may be in the same list or different lists but must not + overlap. */ +void +llx_swap_range (struct llx *a0, struct llx *a1, + struct llx *b0, struct llx *b1) +{ + ll_swap_range (&a0->ll, &a1->ll, &b0->ll, &b1->ll); +} + +/* Removes LLX from its list + and returns the node that formerly followed it. + Frees the node removed with MANAGER. */ +struct llx * +llx_remove (struct llx *llx, const struct llx_manager *manager) +{ + struct llx *next = llx_next (llx); + ll_remove (&llx->ll); + manager->release (llx, manager->aux); + return next; +} + +/* Removes R0...R1 from their list. + Frees the removed nodes with MANAGER. */ +void +llx_remove_range (struct llx *r0, struct llx *r1, + const struct llx_manager *manager) +{ + struct llx *llx; + + for (llx = r0; llx != r1; ) + llx = llx_remove (llx, manager); +} + +/* Removes from R0...R1 all the nodes that equal TARGET + according to COMPARE given auxiliary data AUX. + Frees the removed nodes with MANAGER. + Returns the number of nodes removed. */ +size_t +llx_remove_equal (struct llx *r0, struct llx *r1, const void *target, + llx_compare_func *compare, void *aux, + const struct llx_manager *manager) +{ + struct llx *x; + size_t count; + + count = 0; + for (x = r0; x != r1; ) + if (compare (llx_data (x), target, aux) == 0) + { + x = llx_remove (x, manager); + count++; + } + else + x = llx_next (x); + + return count; +} + +/* Removes from R0...R1 all the nodes for which PREDICATE returns + true given auxiliary data AUX. + Frees the removed nodes with MANAGER. + Returns the number of nodes removed. */ +size_t +llx_remove_if (struct llx *r0, struct llx *r1, + llx_predicate_func *predicate, void *aux, + const struct llx_manager *manager) +{ + struct llx *x; + size_t count; + + count = 0; + for (x = r0; x != r1; ) + if (predicate (llx_data (x), aux)) + { + x = llx_remove (x, manager); + count++; + } + else + x = llx_next (x); + + return count; +} + +/* Returns the first node in R0...R1 that equals TARGET + according to COMPARE given auxiliary data AUX. + Returns R1 if no node in R0...R1 equals TARGET. */ +struct llx * +llx_find_equal (const struct llx *r0, const struct llx *r1, + const void *target, + llx_compare_func *compare, void *aux) +{ + const struct llx *x; + + for (x = r0; x != r1; x = llx_next (x)) + if (compare (llx_data (x), target, aux) == 0) + break; + return (struct llx *) x; +} + +/* Returns the first node in R0...R1 for which PREDICATE returns + true given auxiliary data AUX. + Returns R1 if PREDICATE does not return true for any node in + R0...R1 . */ +struct llx * +llx_find_if (const struct llx *r0, const struct llx *r1, + llx_predicate_func *predicate, void *aux) +{ + const struct llx *x; + + for (x = r0; x != r1; x = llx_next (x)) + if (predicate (llx_data (x), aux)) + break; + return (struct llx *) x; +} + +/* Compares each pair of adjacent nodes in R0...R1 + using COMPARE with auxiliary data AUX + and returns the first node of the first pair that compares + equal. + Returns R1 if no pair compares equal. */ +struct llx * +llx_find_adjacent_equal (const struct llx *r0, const struct llx *r1, + llx_compare_func *compare, void *aux) +{ + if (r0 != r1) + { + const struct llx *x, *y; + + for (x = r0, y = llx_next (x); y != r1; x = y, y = llx_next (y)) + if (compare (llx_data (x), llx_data (y), aux) == 0) + return (struct llx *) x; + } + + return (struct llx *) r1; +} + +/* Returns the number of nodes in R0...R1. + Executes in O(n) time in the return value. */ +size_t +llx_count_range (const struct llx *r0, const struct llx *r1) +{ + return ll_count_range (&r0->ll, &r1->ll); +} + +/* Counts and returns the number of nodes in R0...R1 that equal + TARGET according to COMPARE given auxiliary data AUX. */ +size_t +llx_count_equal (const struct llx *r0, const struct llx *r1, + const void *target, + llx_compare_func *compare, void *aux) +{ + const struct llx *x; + size_t count; + + count = 0; + for (x = r0; x != r1; x = llx_next (x)) + if (compare (llx_data (x), target, aux) == 0) + count++; + return count; +} + +/* Counts and returns the number of nodes in R0...R1 for which + PREDICATE returns true given auxiliary data AUX. */ +size_t +llx_count_if (const struct llx *r0, const struct llx *r1, + llx_predicate_func *predicate, void *aux) +{ + const struct llx *x; + size_t count; + + count = 0; + for (x = r0; x != r1; x = llx_next (x)) + if (predicate (llx_data (x), aux)) + count++; + return count; +} + +/* Returns the greatest node in R0...R1 according to COMPARE + given auxiliary data AUX. + Returns the first of multiple, equal maxima. */ +struct llx * +llx_max (const struct llx *r0, const struct llx *r1, + llx_compare_func *compare, void *aux) +{ + const struct llx *max = r0; + if (r0 != r1) + { + struct llx *x; + + for (x = llx_next (r0); x != r1; x = llx_next (x)) + if (compare (llx_data (x), llx_data (max), aux) > 0) + max = x; + } + return (struct llx *) max; +} + +/* Returns the least node in R0...R1 according to COMPARE given + auxiliary data AUX. + Returns the first of multiple, equal minima. */ +struct llx * +llx_min (const struct llx *r0, const struct llx *r1, + llx_compare_func *compare, void *aux) +{ + const struct llx *min = r0; + if (r0 != r1) + { + struct llx *x; + + for (x = llx_next (r0); x != r1; x = llx_next (x)) + if (compare (llx_data (x), llx_data (min), aux) < 0) + min = x; + } + return (struct llx *) min; +} + +/* Lexicographically compares A0...A1 to B0...B1. + Returns negative if A0...A1 < B0...B1, + zero if A0...A1 == B0...B1, and + positive if A0...A1 > B0...B1 + according to COMPARE given auxiliary data AUX. */ +int +llx_lexicographical_compare_3way (const struct llx *a0, const struct llx *a1, + const struct llx *b0, const struct llx *b1, + llx_compare_func *compare, void *aux) +{ + for (;;) + if (b0 == b1) + return a0 != a1; + else if (a0 == a1) + return -1; + else + { + int cmp = compare (llx_data (a0), llx_data (b0), aux); + if (cmp != 0) + return cmp; + + a0 = llx_next (a0); + b0 = llx_next (b0); + } +} + +/* Calls ACTION with auxiliary data AUX + for every node in R0...R1 in order. */ +void +llx_apply (struct llx *r0, struct llx *r1, + llx_action_func *action, void *aux) +{ + struct llx *llx; + + for (llx = r0; llx != r1; llx = llx_next (llx)) + action (llx_data (llx), aux); +} + +/* Reverses the order of nodes R0...R1. */ +void +llx_reverse (struct llx *r0, struct llx *r1) +{ + ll_reverse (&r0->ll, &r1->ll); +} + +/* Arranges R0...R1 into the lexicographically next greater + permutation. Returns true if successful. + If R0...R1 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. + COMPARE with auxiliary data AUX is used to compare nodes. */ +bool +llx_next_permutation (struct llx *r0, struct llx *r1, + llx_compare_func *compare, void *aux) +{ + if (r0 != r1) + { + struct llx *i = llx_prev (r1); + while (i != r0) + { + i = llx_prev (i); + if (compare (llx_data (i), llx_data (llx_next (i)), aux) < 0) + { + struct llx *j; + for (j = llx_prev (r1); + compare (llx_data (i), llx_data (j), aux) >= 0; + j = llx_prev (j)) + continue; + llx_swap (i, j); + llx_reverse (llx_next (j), r1); + return true; + } + } + + llx_reverse (r0, r1); + } + + return false; +} + +/* Arranges R0...R1 into the lexicographically next lesser + permutation. Returns true if successful. + If R0...R1 is already the lexicographically least + permutation of its elements (i.e. ordered from smallest to + greatest), arranges them into the lexicographically greatest + permutation (i.e. ordered from largest to smallest) and + returns false. + COMPARE with auxiliary data AUX is used to compare nodes. */ +bool +llx_prev_permutation (struct llx *r0, struct llx *r1, + llx_compare_func *compare, void *aux) +{ + if (r0 != r1) + { + struct llx *i = llx_prev (r1); + while (i != r0) + { + i = llx_prev (i); + if (compare (llx_data (i), llx_data (llx_next (i)), aux) > 0) + { + struct llx *j; + for (j = llx_prev (r1); + compare (llx_data (i), llx_data (j), aux) <= 0; + j = llx_prev (j)) + continue; + llx_swap (i, j); + llx_reverse (llx_next (j), r1); + return true; + } + } + + llx_reverse (r0, r1); + } + + return false; +} + +/* Sorts R0...R1 into ascending order + according to COMPARE given auxiliary data AUX. + In use, keep in mind that R0 may move during the sort, so that + afterward R0...R1 may denote a different range. + (On the other hand, R1 is fixed in place.) + Runs in O(n lg n) time in the number of nodes in the range. */ +void +llx_sort (struct llx *r0, struct llx *r1, llx_compare_func *compare, void *aux) +{ + struct llx *pre_r0; + size_t output_run_cnt; + + if (r0 == r1 || llx_next (r0) == r1) + return; + + pre_r0 = llx_prev (r0); + do + { + struct llx *a0 = llx_next (pre_r0); + for (output_run_cnt = 1; ; output_run_cnt++) + { + struct llx *a1 = llx_find_run (a0, r1, compare, aux); + struct llx *a2 = llx_find_run (a1, r1, compare, aux); + if (a1 == a2) + break; + + a0 = llx_merge (a0, a1, a1, a2, compare, aux); + } + } + while (output_run_cnt > 1); +} + +/* Finds the extent of a run of nodes of increasing value + starting at R0 and extending no farther than R1. + Returns the first node in R0...R1 that is less than the + preceding node, or R1 if R0...R1 are arranged in nondecreasing + order. */ +struct llx * +llx_find_run (const struct llx *r0, const struct llx *r1, + llx_compare_func *compare, void *aux) +{ + if (r0 != r1) + { + do + { + r0 = llx_next (r0); + } + while (r0 != r1 && compare (llx_data (llx_prev (r0)), + llx_data (r0), aux) <= 0); + } + + return (struct llx *) r0; +} + +/* Merges B0...B1 into A0...A1 according to COMPARE given + auxiliary data AUX. + The ranges may be in the same list or different lists, but + must not overlap. + The merge is "stable" if A0...A1 is considered to precede + B0...B1, regardless of their actual ordering. + Runs in O(n) time in the total number of nodes in the ranges. */ +struct llx * +llx_merge (struct llx *a0, struct llx *a1, struct llx *b0, struct llx *b1, + llx_compare_func *compare, void *aux) +{ + if (a0 != a1 && b0 != b1) + { + a1 = llx_prev (a1); + b1 = llx_prev (b1); + for (;;) + if (compare (llx_data (a0), llx_data (b0), aux) <= 0) + { + if (a0 == a1) + { + llx_splice (llx_next (a0), b0, llx_next (b1)); + return llx_next (b1); + } + a0 = llx_next (a0); + } + else + { + if (b0 != b1) + { + struct llx *x = b0; + b0 = llx_next (b0); + llx_splice (a0, x, b0); + } + else + { + llx_splice (a0, b0, llx_next (b0)); + return llx_next (a1); + } + } + } + else + { + llx_splice (a0, b0, b1); + return b1; + } +} + +/* Returns true if R0...R1 is sorted in ascending order according + to COMPARE given auxiliary data AUX, + false otherwise. */ +bool +llx_is_sorted (const struct llx *r0, const struct llx *r1, + llx_compare_func *compare, void *aux) +{ + return llx_find_run (r0, r1, compare, aux) == r1; +} + +/* Removes all but the first in each group of sequential + duplicates in R0...R1. Duplicates are determined using + COMPARE given auxiliary data AUX. Removed duplicates are + inserted before DUPS if it is nonnull; otherwise, the removed + duplicates are freed with MANAGER. + Only sequential duplicates are removed. llx_sort() may be used + to bring duplicates together, or llx_sort_unique() can do both + at once. */ +size_t +llx_unique (struct llx *r0, struct llx *r1, struct llx *dups, + llx_compare_func *compare, void *aux, + const struct llx_manager *manager) +{ + size_t count = 0; + + if (r0 != r1) + { + struct llx *x = r0; + for (;;) + { + struct llx *y = llx_next (x); + if (y == r1) + { + count++; + break; + } + + if (compare (llx_data (x), llx_data (y), aux) == 0) + { + if (dups != NULL) + llx_splice (dups, y, llx_next (y)); + else + llx_remove (y, manager); + } + else + { + x = y; + count++; + } + } + } + + return count; +} + +/* Sorts R0...R1 and removes duplicates. + Removed duplicates are inserted before DUPS if it is nonnull; + otherwise, the removed duplicates are freed with MANAGER. + Comparisons are made with COMPARE given auxiliary data AUX. + In use, keep in mind that R0 may move during the sort, so that + afterward R0...R1 may denote a different range. + (On the other hand, R1 is fixed in place.) + Runs in O(n lg n) time in the number of nodes in the range. */ +void +llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups, + llx_compare_func *compare, void *aux, + const struct llx_manager *manager) +{ + struct llx *pre_r0 = llx_prev (r0); + llx_sort (r0, r1, compare, aux); + llx_unique (llx_next (pre_r0), r1, dups, compare, aux, manager); +} + +/* Inserts DATA in the proper position in R0...R1, which must + be sorted according to COMPARE given auxiliary data AUX. + If DATA is equal to one or more existing nodes in R0...R1, + then it is inserted after the existing nodes it equals. + Returns the new node (allocated with MANAGER), or a null + pointer if memory allocation failed. + Runs in O(n) time in the number of nodes in the range. */ +struct llx * +llx_insert_ordered (struct llx *r0, struct llx *r1, void *data, + llx_compare_func *compare, void *aux, + const struct llx_manager *manager) +{ + struct llx *x; + + for (x = r0; x != r1; x = llx_next (x)) + if (compare (llx_data (x), data, aux) > 0) + break; + return llx_insert (x, data, manager); +} + +/* Partitions R0...R1 into those nodes for which PREDICATE given + auxiliary data AUX returns true, followed by those for which + PREDICATE returns false. + Returns the first node in the "false" group, or R1 if + PREDICATE is true for every node in R0...R1. + The partition is "stable" in that the nodes in each group + retain their original relative order. + Runs in O(n) time in the number of nodes in the range. */ +struct llx * +llx_partition (struct llx *r0, struct llx *r1, + llx_predicate_func *predicate, void *aux) +{ + struct llx *t0, *t1; + + for (;;) + { + if (r0 == r1) + return r0; + else if (!predicate (llx_data (r0), aux)) + break; + + r0 = llx_next (r0); + } + + for (t0 = r0;; t0 = t1) + { + do + { + t0 = llx_next (t0); + if (t0 == r1) + return r0; + } + while (!predicate (llx_data (t0), aux)); + + t1 = t0; + do + { + t1 = llx_next (t1); + if (t1 == r1) + { + llx_splice (r0, t0, t1); + return r0; + } + } + while (predicate (llx_data (t1), aux)); + + llx_splice (r0, t0, t1); + } +} + +/* Verifies that R0...R1 is parititioned into a sequence of nodes + for which PREDICATE given auxiliary data AUX returns true, + followed by those for which PREDICATE returns false. + Returns a null pointer if R0...R1 is not partitioned this way. + Otherwise, returns the first node in the "false" group, or R1 + if PREDICATE is true for every node in R0...R1. */ +struct llx * +llx_find_partition (const struct llx *r0, const struct llx *r1, + llx_predicate_func *predicate, void *aux) +{ + const struct llx *partition, *x; + + for (partition = r0; partition != r1; partition = llx_next (partition)) + if (!predicate (llx_data (partition), aux)) + break; + + for (x = partition; x != r1; x = llx_next (x)) + if (predicate (llx_data (x), aux)) + return NULL; + + return (struct llx *) partition; +} + +/* Allocates and returns a node using malloc. */ +static struct llx * +malloc_allocate_node (void *aux UNUSED) +{ + return malloc (sizeof (struct llx)); +} + +/* Releases node LLX with free. */ +static void +malloc_release_node (struct llx *llx, void *aux UNUSED) +{ + free (llx); +} + +/* Manager that uses the standard malloc and free routines. */ +const struct llx_manager llx_malloc_mgr = + { + malloc_allocate_node, + malloc_release_node, + NULL, + }; diff --git a/src/libpspp/llx.h b/src/libpspp/llx.h new file mode 100644 index 00000000..7523636c --- /dev/null +++ b/src/libpspp/llx.h @@ -0,0 +1,312 @@ +/* PSPP - computes sample statistics. + Copyright (C) 2006 Free Software Foundation, Inc. + Written by Ben Pfaff . + + 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. */ + +/* Circular doubly linked lists. + + This header (llx.h) supplies "external" circular doubly linked + lists. Its companion header (ll.h) supplies "embedded" + circular doubly linked lists. The two variants are described + briefly here. The external variant, for which this is the + header, is described in slightly more detail below. Each + function also has a detailed usage comment at its point of + definition. + + The "ll" embedded linked list implementation puts the linked + list node within the data structure that the list contains. + This makes allocation efficient, in space and time. It also + makes it easy to find the list node associated with a given + object. However, it's difficult to include a given object in + an arbitrary number of lists, or to include a single object in + a single list in multiple positions. + + The "llx" external linked list implementation allocates linked + list nodes separately from the objects in the list. Adding + and removing linked list nodes requires dynamic allocation, so + it is normally slower and takes more memory than the embedded + implementation. It also requires searching the list to find + the list node associated with a given object. However, it's + easy to include a given object in an arbitrary number of + lists, or to include a single object more than once within a + single list. It's also possible to create an external linked + list without adding a member to the data structure that the + list contains. */ + +#ifndef LLX_H +#define LLX_H 1 + +#include +#include +#include + +/* External, circular doubly linked list. + + Each list contains a single "null" element that separates the + head and the tail of the list. The null element is both + before the head and after the tail of the list. An empty list + contains just the null element. + + An external linked list is represented as `struct llx_list'. + Each node in the list consists of a `struct llx' that contains + a `void *' pointer to the node's data. Use the llx_data() + function to extract the data pointer from a node. + + Many list functions take ranges of nodes as arguments. Ranges + are "half-open"; that is, R0...R1 includes R0 but not R1. A + range whose endpoints are the same (e.g. R0...R0) contains no + nodes at all. + + Consider the following declarations: + + struct llx_list list; + + struct foo + { + int x; // Data member. + }; + + Here's an example of iteration from head to tail: + + struct llx *llx; + for (llx = llx_head (&list); llx != llx_null (&list); + llx = llx_next (llx)) + { + struct foo *foo = llx_data (llx); + ...do something with foo->x... + } + + Here's another way to do it: + + struct llx *llx = llx_null (&list); + while ((llx = llx_next (llx)) != llx_null (&list)) + { + struct foo *foo = llx_data (llx); + ...do something with foo->x... + } +*/ + +/* External linked list node. */ +struct llx + { + struct ll ll; /* Node. */ + void *data; /* Member data. */ + }; + +/* Linked list. */ +struct llx_list + { + struct ll_list ll_list; /* The list. */ + }; + +/* Memory manager. */ +struct llx_manager + { + /* Allocates and returns memory for a new struct llx. + If space is unavailable, returns a null pointer. */ + struct llx *(*allocate) (void *aux); + + /* Releases a previously allocated struct llx. */ + void (*release) (struct llx *, void *aux); + + /* Auxiliary data passed to allocate and release + functions. */ + void *aux; + }; + +/* Manager that uses the standard malloc and free routines. */ +extern const struct llx_manager llx_malloc_mgr; + +/* Returns negative if A < B, zero if A == B, positive if A > B. */ +typedef int llx_compare_func (const void *a, const void *b, void *aux); + +/* Returns true or false depending on properties of DATA. */ +typedef bool llx_predicate_func (const void *data, void *aux); + +/* Takes some action on DATA. */ +typedef void llx_action_func (void *data, void *aux); + +/* Basics. */ +static inline void llx_init (struct llx_list *); +void llx_destroy (struct llx_list *, llx_action_func *destructor, void *aux, + const struct llx_manager *manager); +static inline bool llx_is_empty (const struct llx_list *); +size_t llx_count (const struct llx_list *); + +/* Iteration. */ +static inline struct llx *llx_head (const struct llx_list *); +static inline struct llx *llx_tail (const struct llx_list *); +static inline struct llx *llx_null (const struct llx_list *); +static inline struct llx *llx_next (const struct llx *); +static inline struct llx *llx_prev (const struct llx *); +static inline void *llx_data (const struct llx *); + +/* Stack- and queue-like behavior. */ +struct llx *llx_push_head (struct llx_list *, void *, + const struct llx_manager *); +struct llx *llx_push_tail (struct llx_list *, void *, + const struct llx_manager *); +void *llx_pop_head (struct llx_list *, const struct llx_manager *); +void *llx_pop_tail (struct llx_list *, const struct llx_manager *); + +/* Insertion. */ +struct llx *llx_insert (struct llx *before, void *, + const struct llx_manager *); +void llx_splice (struct llx *before, struct llx *r0, struct llx *r1); +void llx_swap (struct llx *a, struct llx *b); +void llx_swap_range (struct llx *a0, struct llx *a1, + struct llx *b0, struct llx *b1); + +/* Removal. */ +struct llx *llx_remove (struct llx *, const struct llx_manager *); +void llx_remove_range (struct llx *r0, struct llx *r1, + const struct llx_manager *); +size_t llx_remove_equal (struct llx *r0, struct llx *r1, const void *target, + llx_compare_func *, void *aux, + const struct llx_manager *); +size_t llx_remove_if (struct llx *r0, struct llx *r1, + llx_predicate_func *, void *aux, + const struct llx_manager *); + +/* Non-mutating algorithms. */ +struct llx *llx_find_equal (const struct llx *r0, const struct llx *r1, + const void *target, + llx_compare_func *, void *aux); +struct llx *llx_find_if (const struct llx *r0, const struct llx *r1, + llx_predicate_func *, void *aux); +struct llx *llx_find_adjacent_equal (const struct llx *r0, + const struct llx *r1, + llx_compare_func *, void *aux); +size_t llx_count_range (const struct llx *r0, const struct llx *r1); +size_t llx_count_equal (const struct llx *r0, const struct llx *r1, + const void *target, + llx_compare_func *, void *aux); +size_t llx_count_if (const struct llx *r0, const struct llx *r1, + llx_predicate_func *, void *aux); +struct llx *llx_max (const struct llx *r0, const struct llx *r1, + llx_compare_func *, void *aux); +struct llx *llx_min (const struct llx *r0, const struct llx *r1, + llx_compare_func *, void *aux); +int llx_lexicographical_compare_3way (const struct llx *a0, + const struct llx *a1, + const struct llx *b0, + const struct llx *b1, + llx_compare_func *, void *aux); + +/* Mutating algorithms. */ +void llx_apply (struct llx *r0, struct llx *r1, llx_action_func *, void *aux); +void llx_reverse (struct llx *r0, struct llx *r1); +bool llx_next_permutation (struct llx *r0, struct llx *r1, + llx_compare_func *, void *aux); +bool llx_prev_permutation (struct llx *r0, struct llx *r1, + llx_compare_func *, void *aux); + +/* Sorted list functions. */ +void llx_sort (struct llx *r0, struct llx *r1, llx_compare_func *, void *aux); +struct llx *llx_find_run (const struct llx *r0, const struct llx *r1, + llx_compare_func *, void *aux); +bool llx_is_sorted (const struct llx *r0, const struct llx *r1, + llx_compare_func *, void *aux); +struct llx *llx_merge (struct llx *a0, struct llx *a1, + struct llx *b0, struct llx *b1, + llx_compare_func *, void *aux); +size_t llx_unique (struct llx *r0, struct llx *r1, struct llx *dups, + llx_compare_func *, void *aux, + const struct llx_manager *); +void llx_sort_unique (struct llx *r0, struct llx *r1, struct llx *dups, + llx_compare_func *, void *aux, + const struct llx_manager *); +struct llx *llx_insert_ordered (struct llx *r0, struct llx *r1, void *data, + llx_compare_func *, void *aux, + const struct llx_manager *); +struct llx *llx_partition (struct llx *r0, struct llx *r1, + llx_predicate_func *, void *aux); +struct llx *llx_find_partition (const struct llx *r0, const struct llx *r1, + llx_predicate_func *, void *aux); + +/* Returns the llx within which LL is embedded. */ +static struct llx * +llx_from_ll (struct ll *ll) +{ + return ll_data (ll, struct llx, ll); +} + +/* Initializes LIST as an empty list. */ +static inline void +llx_init (struct llx_list *list) +{ + ll_init (&list->ll_list); +} + +/* Returns true if LIST is empty (contains just the null node), + false if LIST is not empty (has at least one other node). + Executes in O(1) time. */ +static inline bool +llx_is_empty (const struct llx_list *list) +{ + return ll_is_empty (&list->ll_list); +} + +/* Returns the first node in LIST, + or the null node if LIST is empty. */ +static inline struct llx * +llx_head (const struct llx_list *list) +{ + return llx_from_ll (ll_head (&list->ll_list)); +} + +/* Returns the last node in LIST, + or the null node if LIST is empty. */ +static inline struct llx * +llx_tail (const struct llx_list *list) +{ + return llx_from_ll (ll_tail (&list->ll_list)); +} + +/* Returns LIST's null node. */ +static inline struct llx * +llx_null (const struct llx_list *list) +{ + return llx_from_ll (ll_null (&list->ll_list)); +} + +/* Returns the node following LLX in its list, + or the null node if LLX is at the end of its list. + (In an empty list, the null node follows itself.) */ +static inline struct llx * +llx_next (const struct llx *llx) +{ + return llx_from_ll (ll_next (&llx->ll)); +} + +/* Returns the node preceding LLX in its list, + or the null node if LLX is the first node in its list. + (In an empty list, the null node precedes itself.) */ +static inline struct llx * +llx_prev (const struct llx *llx) +{ + return llx_from_ll (ll_prev (&llx->ll)); +} + +/* Returns the data in node LLX. */ +static inline void * +llx_data (const struct llx *llx) +{ + return llx->data; +} + +#endif /* llx.h */ diff --git a/tests/automake.mk b/tests/automake.mk index 03378596..7843b5eb 100644 --- a/tests/automake.mk +++ b/tests/automake.mk @@ -104,7 +104,23 @@ TESTS = \ tests/expressions/epoch.sh \ tests/expressions/randist.sh \ tests/expressions/variables.sh \ - tests/expressions/vectors.sh + tests/expressions/vectors.sh \ + tests/libpspp/ll-test \ + tests/libpspp/llx-test + +noinst_PROGRAMS += tests/libpspp/ll-test tests/libpspp/llx-test + +tests_libpspp_ll_test_SOURCES = \ + src/libpspp/ll.c \ + src/libpspp/ll.h \ + tests/libpspp/ll-test.c + +tests_libpspp_llx_test_SOURCES = \ + src/libpspp/ll.c \ + src/libpspp/ll.h \ + src/libpspp/llx.c \ + src/libpspp/llx.h \ + tests/libpspp/llx-test.c EXTRA_DIST += $(TESTS) tests/weighting.data tests/data-list.data tests/list.data \ tests/no_case_size.sav \ diff --git a/tests/libpspp/ll-test.c b/tests/libpspp/ll-test.c new file mode 100644 index 00000000..1ec96ed5 --- /dev/null +++ b/tests/libpspp/ll-test.c @@ -0,0 +1,2021 @@ +/* PSPP - computes sample statistics. + Copyright (C) 2006 Free Software Foundation, Inc. + Written by Ben Pfaff . + + 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 ll_* routines defined in + ll.c. This test program aims to be as comprehensive as + possible. "gcov -b" should report 100% coverage of lines and + branches in the ll_* routines. "valgrind --leak-check=yes + --show-reachable=yes" should give a clean report. + + This test program depends only on ll.c and the standard C + library. + + See llx-test.c for a similar program for the llx_* + routines. */ + +#include +#include +#include +#include +#include + +/* Support preliminaries. */ +#if __GNUC__ >= 2 && !defined UNUSED +#define UNUSED __attribute__ ((unused)) +#else +#define UNUSED +#endif + +/* 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 at %s, line %d\n", __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__) + +/* Prints a message about memory exhaustion and exits with a + failure code. */ +static void +xalloc_die (void) +{ + printf ("virtual memory exhausted\n"); + exit (EXIT_FAILURE); +} + +/* Allocates and returns N bytes of memory. */ +static void * +xmalloc (size_t n) +{ + if (n != 0) + { + void *p = malloc (n); + if (p == NULL) + xalloc_die (); + + return p; + } + else + return NULL; +} + +/* Allocates and returns N * M bytes of memory. */ +static void * +xnmalloc (size_t n, size_t m) +{ + if ((size_t) -1 / m <= n) + xalloc_die (); + return xmalloc (n * m); +} + +/* List type and support routines. */ + +/* Test data element. */ +struct element + { + struct ll ll; /* Embedded list element. */ + int x; /* Primary value. */ + int y; /* Secondary value. */ + }; + +int aux_data; + +/* Returns the `struct element' that LL is embedded within. */ +static struct element * +ll_to_element (const struct ll *ll) +{ + return ll_data (ll, struct element, ll); +} + +/* Prints the elements in LIST. */ +static void UNUSED +print_list (struct ll_list *list) +{ + struct ll *x; + + printf ("list:"); + for (x = ll_head (list); x != ll_null (list); x = ll_next (x)) + { + struct element *e = ll_to_element (x); + printf (" %d", e->x); + } + printf ("\n"); +} + +/* Prints the value returned by PREDICATE given auxiliary data + AUX for each element in LIST. */ +static void UNUSED +print_pred (struct ll_list *list, + ll_predicate_func *predicate, void *aux UNUSED) +{ + struct ll *x; + + printf ("pred:"); + for (x = ll_head (list); x != ll_null (list); x = ll_next (x)) + printf (" %d", predicate (x, aux)); + printf ("\n"); +} + +/* Prints the CNT numbers in VALUES. */ +static void UNUSED +print_array (int values[], size_t cnt) +{ + size_t i; + + printf ("arry:"); + for (i = 0; i < cnt; i++) + printf (" %d", values[i]); + printf ("\n"); +} + +/* 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 ll *a_, const struct ll *b_, void *aux) +{ + const struct element *a = ll_to_element (a_); + const struct element *b = ll_to_element (b_); + + check (aux == &aux_data); + return a->x < b->x ? -1 : a->x > b->x; +} + +/* Compares the `x' and `y' values in A and B and returns a + strcmp-type return value. Verifies that AUX points to + aux_data. */ +static int +compare_elements_x_y (const struct ll *a_, const struct ll *b_, void *aux) +{ + const struct element *a = ll_to_element (a_); + const struct element *b = ll_to_element (b_); + + check (aux == &aux_data); + if (a->x != b->x) + return a->x < b->x ? -1 : 1; + else if (a->y != b->y) + return a->y < b->y ? -1 : 1; + else + return 0; +} + +/* Compares the `y' values in A and B and returns a strcmp-type + return value. Verifies that AUX points to aux_data. */ +static int +compare_elements_y (const struct ll *a_, const struct ll *b_, void *aux) +{ + const struct element *a = ll_to_element (a_); + const struct element *b = ll_to_element (b_); + + check (aux == &aux_data); + return a->y < b->y ? -1 : a->y > b->y; +} + +/* Returns true if the bit in *PATTERN indicated by `x in + *ELEMENT is set, false otherwise. */ +static bool +pattern_pred (const struct ll *element_, void *pattern_) +{ + const struct element *element = ll_to_element (element_); + unsigned *pattern = pattern_; + + return (*pattern & (1u << element->x)) != 0; +} + +/* Allocates N elements in *ELEMS. + Adds the elements to LIST, if it is nonnull. + Puts pointers to the elements' list elements in *ELEMP, + followed by a pointer to the list null element, if ELEMP is + nonnull. + Allocates space for N values in *VALUES, if VALUES is + nonnull. */ +static void +allocate_elements (size_t n, + struct ll_list *list, + struct element ***elems, + struct ll ***elemp, + int **values) +{ + size_t i; + + if (list != NULL) + ll_init (list); + + *elems = xnmalloc (n, sizeof **elems); + for (i = 0; i < n; i++) + { + (*elems)[i] = xmalloc (sizeof ***elems); + if (list != NULL) + ll_push_tail (list, &(*elems)[i]->ll); + } + + if (elemp != NULL) + { + *elemp = xnmalloc (n + 1, sizeof *elemp); + for (i = 0; i < n; i++) + (*elemp)[i] = &(*elems)[i]->ll; + (*elemp)[n] = ll_null (list); + } + + if (values != NULL) + *values = xnmalloc (n, sizeof *values); +} + +/* Copies the CNT values of `x' from LIST into VALUES[]. */ +static void +extract_values (struct ll_list *list, int values[], size_t cnt) +{ + struct ll *x; + + check (ll_count (list) == cnt); + for (x = ll_head (list); x != ll_null (list); x = ll_next (x)) + { + struct element *e = ll_to_element (x); + *values++ = e->x; + } +} + +/* As allocate_elements, but sets ascending values, starting + from 0, in `x' values in *ELEMS and in *VALUES (if + nonnull). */ +static void +allocate_ascending (size_t n, + struct ll_list *list, + struct element ***elems, + struct ll ***elemp, + int **values) +{ + size_t i; + + allocate_elements (n, list, elems, elemp, values); + + for (i = 0; i < n; i++) + (*elems)[i]->x = i; + if (values != NULL) + extract_values (list, *values, n); +} + +/* As allocate_elements, but sets binary values extracted from + successive bits in PATTERN in `x' values in *ELEMS and in + *VALUES (if nonnull). */ +static void +allocate_pattern (size_t n, + int pattern, + struct ll_list *list, + struct element ***elems, + struct ll ***elemp, + int **values) +{ + size_t i; + + allocate_elements (n, list, elems, elemp, values); + + for (i = 0; i < n; i++) + (*elems)[i]->x = (pattern & (1 << i)) != 0; + if (values != NULL) + extract_values (list, *values, n); +} + +/* Randomly shuffles the CNT elements in ARRAY, each of which is + SIZE bytes in size. */ +static void +random_shuffle (void *array_, size_t cnt, size_t size) +{ + char *array = array_; + char *tmp = xmalloc (size); + size_t i; + + for (i = 0; i < cnt; i++) + { + size_t j = rand () % (cnt - i) + i; + if (i != j) + { + memcpy (tmp, array + j * size, size); + memcpy (array + j * size, array + i * size, size); + memcpy (array + i * size, tmp, size); + } + } + + free (tmp); +} + +/* As allocate_ascending, but orders the values randomly. */ +static void +allocate_random (size_t n, + struct ll_list *list, + struct element ***elems, + struct ll ***elemp, + int **values) +{ + size_t i; + + allocate_elements (n, list, elems, elemp, values); + + for (i = 0; i < n; i++) + (*elems)[i]->x = i; + random_shuffle (*elems, n, sizeof **elems); + if (values != NULL) + extract_values (list, *values, n); +} + +/* Frees the N elements of ELEMS, ELEMP, and VALUES. */ +static void +free_elements (size_t n, + struct element **elems, + struct ll **elemp, + int *values) +{ + size_t i; + + for (i = 0; i < n; i++) + free (elems[i]); + free (elems); + free (elemp); + free (values); +} + +/* Compares A and B and returns a strcmp-type return value. */ +static int +compare_ints (const void *a_, const void *b_, void *aux UNUSED) +{ + const int *a = a_; + const int *b = b_; + + return *a < *b ? -1 : *a > *b; +} + +/* Compares A and B and returns a strcmp-type return value. */ +static int +compare_ints_noaux (const void *a_, const void *b_) +{ + const int *a = a_; + const int *b = b_; + + return *a < *b ? -1 : *a > *b; +} + +/* Checks that LIST contains the CNT values in ELEMENTS. */ +static void +check_list_contents (struct ll_list *list, int elements[], size_t cnt) +{ + struct ll *ll; + size_t i; + + check ((cnt == 0) == ll_is_empty (list)); + + /* Iterate in forward order. */ + for (ll = ll_head (list), i = 0; i < cnt; ll = ll_next (ll), i++) + { + struct element *e = ll_to_element (ll); + check (elements[i] == e->x); + check (ll != ll_null (list)); + } + check (ll == ll_null (list)); + + /* Iterate in reverse order. */ + for (ll = ll_tail (list), i = 0; i < cnt; ll = ll_prev (ll), i++) + { + struct element *e = ll_to_element (ll); + check (elements[cnt - i - 1] == e->x); + check (ll != ll_null (list)); + } + check (ll == ll_null (list)); + + check (ll_count (list) == cnt); +} + +/* Lexicographically compares ARRAY1, which contains COUNT1 + elements of SIZE bytes each, to ARRAY2, which contains COUNT2 + elements of SIZE bytes, according to COMPARE. Returns a + strcmp-type result. AUX is passed to COMPARE as auxiliary + data. */ +static int +lexicographical_compare_3way (const void *array1, size_t count1, + const void *array2, size_t count2, + size_t size, + int (*compare) (const void *, const void *, + void *aux), + void *aux) +{ + const char *first1 = array1; + const char *first2 = array2; + size_t min_count = count1 < count2 ? count1 : count2; + + while (min_count > 0) + { + int cmp = compare (first1, first2, aux); + if (cmp != 0) + return cmp; + + first1 += size; + first2 += size; + min_count--; + } + + return count1 < count2 ? -1 : count1 > count2; +} + +/* Tests. */ + +/* Tests list push and pop operations. */ +static void +test_push_pop (void) +{ + const int max_elems = 1024; + + struct ll_list list; + struct element **elems; + int *values; + + int i; + + allocate_elements (max_elems, NULL, &elems, NULL, &values); + + /* Push on tail. */ + ll_init (&list); + check_list_contents (&list, NULL, 0); + for (i = 0; i < max_elems; i++) + { + values[i] = elems[i]->x = i; + ll_push_tail (&list, &elems[i]->ll); + check_list_contents (&list, values, i + 1); + } + + /* Remove from tail. */ + for (i = 0; i < max_elems; i++) + { + struct element *e = ll_to_element (ll_pop_tail (&list)); + check (e->x == max_elems - i - 1); + check_list_contents (&list, values, max_elems - i - 1); + } + + /* Push at start. */ + check_list_contents (&list, NULL, 0); + for (i = 0; i < max_elems; i++) + { + values[max_elems - i - 1] = elems[i]->x = max_elems - i - 1; + ll_push_head (&list, &elems[i]->ll); + check_list_contents (&list, &values[max_elems - i - 1], i + 1); + } + + /* Remove from start. */ + for (i = 0; i < max_elems; i++) + { + struct element *e = ll_to_element (ll_pop_head (&list)); + check (e->x == (int) i); + check_list_contents (&list, &values[i + 1], max_elems - i - 1); + } + + free_elements (max_elems, elems, NULL, values); +} + +/* Tests insertion and removal at arbitrary positions. */ +static void +test_insert_remove (void) +{ + const int max_elems = 16; + int cnt; + + for (cnt = 0; cnt < max_elems; cnt++) + { + struct element **elems; + struct ll **elemp; + int *values = xnmalloc (cnt + 1, sizeof *values); + + struct ll_list list; + struct element extra; + int pos; + + allocate_ascending (cnt, &list, &elems, &elemp, NULL); + extra.x = -1; + for (pos = 0; pos <= cnt; pos++) + { + int i, j; + + ll_insert (elemp[pos], &extra.ll); + + j = 0; + for (i = 0; i < pos; i++) + values[j++] = i; + values[j++] = -1; + for (; i < cnt; i++) + values[j++] = i; + check_list_contents (&list, values, cnt + 1); + + ll_remove (&extra.ll); + } + check_list_contents (&list, values, cnt); + + free_elements (cnt, elems, elemp, values); + } +} + +/* Tests swapping individual elements. */ +static void +test_swap (void) +{ + const int max_elems = 8; + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt++) + { + struct ll_list list; + struct element **elems; + int *values; + + int i, j, k; + + allocate_ascending (cnt, &list, &elems, NULL, &values); + check_list_contents (&list, values, cnt); + + for (i = 0; i < cnt; i++) + for (j = 0; j < cnt; j++) + for (k = 0; k < 2; k++) + { + int t; + + ll_swap (&elems[i]->ll, &elems[j]->ll); + t = values[i]; + values[i] = values[j]; + values[j] = t; + check_list_contents (&list, values, cnt); + } + + free_elements (cnt, elems, NULL, values); + } +} + +/* Tests swapping ranges of list elements. */ +static void +test_swap_range (void) +{ + const int max_elems = 8; + int cnt, a0, a1, b0, b1, r; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (a0 = 0; a0 <= cnt; a0++) + for (a1 = a0; a1 <= cnt; a1++) + for (b0 = a1; b0 <= cnt; b0++) + for (b1 = b0; b1 <= cnt; b1++) + for (r = 0; r < 2; r++) + { + struct ll_list list; + struct element **elems; + struct ll **elemp; + int *values; + + int i, j; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + check_list_contents (&list, values, cnt); + + j = 0; + for (i = 0; i < a0; i++) + values[j++] = i; + for (i = b0; i < b1; i++) + values[j++] = i; + for (i = a1; i < b0; i++) + values[j++] = i; + for (i = a0; i < a1; i++) + values[j++] = i; + for (i = b1; i < cnt; i++) + values[j++] = i; + check (j == cnt); + + if (r == 0) + ll_swap_range (elemp[a0], elemp[a1], elemp[b0], elemp[b1]); + else + ll_swap_range (elemp[b0], elemp[b1], elemp[a0], elemp[a1]); + check_list_contents (&list, values, cnt); + + free_elements (cnt, elems, elemp, values); + } +} + +/* Tests removing ranges of list elements. */ +static void +test_remove_range (void) +{ + const int max_elems = 8; + + int cnt, r0, r1; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + { + struct ll_list list; + struct element **elems; + struct ll **elemp; + int *values; + + int i, j; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + check_list_contents (&list, values, cnt); + + j = 0; + for (i = 0; i < r0; i++) + values[j++] = i; + for (i = r1; i < cnt; i++) + values[j++] = i; + + ll_remove_range (elemp[r0], elemp[r1]); + check_list_contents (&list, values, j); + + free_elements (cnt, elems, elemp, values); + } +} + +/* Tests ll_remove_equal. */ +static void +test_remove_equal (void) +{ + const int max_elems = 8; + + int cnt, r0, r1, eq_pat; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++) + { + struct ll_list list; + struct element **elems; + struct ll **elemp; + int *values; + + struct element to_remove; + int remaining; + int i; + + allocate_elements (cnt, &list, &elems, &elemp, &values); + + remaining = 0; + for (i = 0; i < cnt; i++) + { + int x = eq_pat & (1 << i) ? -1 : i; + bool delete = x == -1 && r0 <= i && i < r1; + elems[i]->x = x; + if (!delete) + values[remaining++] = x; + } + + to_remove.x = -1; + check ((int) ll_remove_equal (elemp[r0], elemp[r1], &to_remove.ll, + compare_elements, &aux_data) + == cnt - remaining); + check_list_contents (&list, values, remaining); + + free_elements (cnt, elems, elemp, values); + } +} + +/* Tests ll_remove_if. */ +static void +test_remove_if (void) +{ + const int max_elems = 8; + + int cnt, r0, r1, pattern; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + for (pattern = 0; pattern <= 1 << cnt; pattern++) + { + struct ll_list list; + struct element **elems; + struct ll **elemp; + int *values; + + int remaining; + int i; + + allocate_elements (cnt, &list, &elems, &elemp, &values); + + remaining = 0; + for (i = 0; i < cnt; i++) + { + bool delete = (pattern & (1 << i)) && r0 <= i && i < r1; + elems[i]->x = i; + if (!delete) + values[remaining++] = i; + } + + check ((int) ll_remove_if (elemp[r0], elemp[r1], + pattern_pred, &pattern) + == cnt - remaining); + check_list_contents (&list, values, remaining); + + free_elements (cnt, elems, elemp, values); + } +} + +/* Tests ll_moved. */ +static void +test_moved (void) +{ + const int max_elems = 8; + + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt++) + { + struct ll_list list; + struct element **elems; + struct element **new_elems; + int *values; + + int i; + + allocate_ascending (cnt, &list, &elems, NULL, &values); + allocate_elements (cnt, NULL, &new_elems, NULL, NULL); + check_list_contents (&list, values, cnt); + + for (i = 0; i < cnt; i++) + { + *new_elems[i] = *elems[i]; + ll_moved (&new_elems[i]->ll); + check_list_contents (&list, values, cnt); + } + + free_elements (cnt, elems, NULL, values); + free_elements (cnt, new_elems, NULL, NULL); + } +} + +/* Tests, via HELPER, a function that looks at list elements + equal to some specified element. */ +static void +test_examine_equal_range (void (*helper) (int r0, int r1, int eq_pat, + struct ll *to_find, + struct ll **elemp)) +{ + const int max_elems = 8; + + int cnt, r0, r1, eq_pat; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++) + { + struct ll_list list; + struct element **elems; + struct ll **elemp; + int *values; + + struct element to_find; + + int i; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + + for (i = 0; i < cnt; i++) + if (eq_pat & (1 << i)) + values[i] = elems[i]->x = -1; + + to_find.x = -1; + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + helper (r0, r1, eq_pat, &to_find.ll, elemp); + + check_list_contents (&list, values, cnt); + + free_elements (cnt, elems, elemp, values); + } +} + +/* Tests, via HELPER, a function that looks at list elements for + which a given predicate returns true. */ +static void +test_examine_if_range (void (*helper) (int r0, int r1, int eq_pat, + struct ll **elemp)) +{ + const int max_elems = 8; + + int cnt, r0, r1, eq_pat; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++) + { + struct ll_list list; + struct element **elems; + struct ll **elemp; + int *values; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + helper (r0, r1, eq_pat, elemp); + + check_list_contents (&list, values, cnt); + + free_elements (cnt, elems, elemp, values); + } +} + +/* Helper function for testing ll_find_equal. */ +static void +test_find_equal_helper (int r0, int r1, int eq_pat, + struct ll *to_find, struct ll **elemp) +{ + struct ll *match; + int i; + + match = ll_find_equal (elemp[r0], elemp[r1], to_find, + compare_elements, &aux_data); + for (i = r0; i < r1; i++) + if (eq_pat & (1 << i)) + break; + + check (match == elemp[i]); +} + +/* Tests ll_find_equal. */ +static void +test_find_equal (void) +{ + test_examine_equal_range (test_find_equal_helper); +} + +/* Helper function for testing ll_find_if. */ +static void +test_find_if_helper (int r0, int r1, int eq_pat, struct ll **elemp) +{ + struct ll *match = ll_find_if (elemp[r0], elemp[r1], + pattern_pred, &eq_pat); + int i; + + for (i = r0; i < r1; i++) + if (eq_pat & (1 << i)) + break; + + check (match == elemp[i]); +} + +/* Tests ll_find_if. */ +static void +test_find_if (void) +{ + test_examine_if_range (test_find_if_helper); +} + +/* Tests ll_find_adjacent_equal. */ +static void +test_find_adjacent_equal (void) +{ + const int max_elems = 8; + + int cnt, eq_pat; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++) + { + struct ll_list list; + struct element **elems; + struct ll **elemp; + int *values; + int match; + + int i; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + + match = -1; + for (i = 0; i < cnt - 1; i++) + { + elems[i]->y = i; + if (eq_pat & (1 << i)) + { + values[i] = elems[i]->x = match; + values[i + 1] = elems[i + 1]->x = match; + } + else + match--; + } + + for (i = 0; i <= cnt; i++) + { + struct ll *ll1 = ll_find_adjacent_equal (elemp[i], ll_null (&list), + compare_elements, + &aux_data); + struct ll *ll2; + int j; + + ll2 = ll_null (&list); + for (j = i; j < cnt - 1; j++) + if (eq_pat & (1 << j)) + { + ll2 = elemp[j]; + break; + } + check (ll1 == ll2); + } + check_list_contents (&list, values, cnt); + + free_elements (cnt, elems, elemp, values); + } +} + +/* Helper function for testing ll_count_range. */ +static void +test_count_range_helper (int r0, int r1, int eq_pat UNUSED, struct ll **elemp) +{ + check ((int) ll_count_range (elemp[r0], elemp[r1]) == r1 - r0); +} + +/* Tests ll_count_range. */ +static void +test_count_range (void) +{ + test_examine_if_range (test_count_range_helper); +} + +/* Helper function for testing ll_count_equal. */ +static void +test_count_equal_helper (int r0, int r1, int eq_pat, + struct ll *to_find, struct ll **elemp) +{ + int count1, count2; + int i; + + count1 = ll_count_equal (elemp[r0], elemp[r1], to_find, + compare_elements, &aux_data); + count2 = 0; + for (i = r0; i < r1; i++) + if (eq_pat & (1 << i)) + count2++; + + check (count1 == count2); +} + +/* Tests ll_count_equal. */ +static void +test_count_equal (void) +{ + test_examine_equal_range (test_count_equal_helper); +} + +/* Helper function for testing ll_count_if. */ +static void +test_count_if_helper (int r0, int r1, int eq_pat, struct ll **elemp) +{ + int count1; + int count2; + int i; + + count1 = ll_count_if (elemp[r0], elemp[r1], pattern_pred, &eq_pat); + + count2 = 0; + for (i = r0; i < r1; i++) + if (eq_pat & (1 << i)) + count2++; + + check (count1 == count2); +} + +/* Tests ll_count_if. */ +static void +test_count_if (void) +{ + test_examine_if_range (test_count_if_helper); +} + +/* 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 ll_min and ll_max. */ +static void +test_min_max (void) +{ + const int max_elems = 6; + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt++) + { + struct ll_list list; + struct element **elems; + struct ll **elemp; + int *values; + int *new_values = xnmalloc (cnt, sizeof *values); + + size_t perm_cnt; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + + perm_cnt = 1; + while (ll_next_permutation (ll_head (&list), ll_null (&list), + compare_elements, &aux_data)) + { + int r0, r1; + struct ll *x; + int i; + + for (i = 0, x = ll_head (&list); x != ll_null (&list); + x = ll_next (x), i++) + { + struct element *e = ll_to_element (x); + elemp[i] = x; + new_values[i] = e->x; + } + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + { + struct ll *min = ll_min (elemp[r0], elemp[r1], + compare_elements, &aux_data); + struct ll *max = ll_max (elemp[r0], elemp[r1], + compare_elements, &aux_data); + if (r0 == r1) + { + check (min == elemp[r1]); + check (max == elemp[r1]); + } + else + { + int min_int, max_int; + int i; + + min_int = max_int = new_values[r0]; + for (i = r0; i < r1; i++) + { + int value = new_values[i]; + if (value < min_int) + min_int = value; + if (value > max_int) + max_int = value; + } + check (min != elemp[r1] + && ll_to_element (min)->x == min_int); + check (max != elemp[r1] + && ll_to_element (max)->x == max_int); + } + } + perm_cnt++; + } + check (perm_cnt == factorial (cnt)); + check_list_contents (&list, values, cnt); + + free_elements (cnt, elems, elemp, values); + free (new_values); + } +} + +/* Tests ll_lexicographical_compare_3way. */ +static void +test_lexicographical_compare_3way (void) +{ + const int max_elems = 4; + + int cnt_a, pat_a, cnt_b, pat_b; + + for (cnt_a = 0; cnt_a <= max_elems; cnt_a++) + for (pat_a = 0; pat_a <= 1 << cnt_a; pat_a++) + for (cnt_b = 0; cnt_b <= max_elems; cnt_b++) + for (pat_b = 0; pat_b <= 1 << cnt_b; pat_b++) + { + struct ll_list list_a, list_b; + struct element **elems_a, **elems_b; + struct ll **elemp_a, **elemp_b; + int *values_a, *values_b; + + int a0, a1, b0, b1; + + allocate_pattern (cnt_a, pat_a, + &list_a, &elems_a, &elemp_a, &values_a); + allocate_pattern (cnt_b, pat_b, + &list_b, &elems_b, &elemp_b, &values_b); + + for (a0 = 0; a0 <= cnt_a; a0++) + for (a1 = a0; a1 <= cnt_a; a1++) + for (b0 = 0; b0 <= cnt_b; b0++) + for (b1 = b0; b1 <= cnt_b; b1++) + { + int a_ordering = lexicographical_compare_3way ( + values_a + a0, a1 - a0, + values_b + b0, b1 - b0, + sizeof *values_a, + compare_ints, NULL); + + int b_ordering = ll_lexicographical_compare_3way ( + elemp_a[a0], elemp_a[a1], + elemp_b[b0], elemp_b[b1], + compare_elements, &aux_data); + + check (a_ordering == b_ordering); + } + + free_elements (cnt_a, elems_a, elemp_a, values_a); + free_elements (cnt_b, elems_b, elemp_b, values_b); + } +} + +/* Appends the `x' value in element E to the array pointed to by + NEXT_OUTPUT, and advances NEXT_OUTPUT to the next position. */ +static void +apply_func (struct ll *e_, void *next_output_) +{ + struct element *e = ll_to_element (e_); + int **next_output = next_output_; + + *(*next_output)++ = e->x; +} + +/* Tests ll_apply. */ +static void +test_apply (void) +{ + const int max_elems = 8; + + int cnt, r0, r1; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + { + struct ll_list list; + struct element **elems; + struct ll **elemp; + int *values; + + int *output; + int *next_output; + + int i; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + check_list_contents (&list, values, cnt); + + output = next_output = xnmalloc (cnt, sizeof *output); + ll_apply (elemp[r0], elemp[r1], apply_func, &next_output); + check_list_contents (&list, values, cnt); + + check (r1 - r0 == next_output - output); + for (i = 0; i < r1 - r0; i++) + check (output[i] == r0 + i); + + free_elements (cnt, elems, elemp, values); + free (output); + } +} + +/* Tests ll_reverse. */ +static void +test_reverse (void) +{ + const int max_elems = 8; + + int cnt, r0, r1; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + { + struct ll_list list; + struct element **elems; + struct ll **elemp; + int *values; + + int i, j; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + check_list_contents (&list, values, cnt); + + j = 0; + for (i = 0; i < r0; i++) + values[j++] = i; + for (i = r1 - 1; i >= r0; i--) + values[j++] = i; + for (i = r1; i < cnt; i++) + values[j++] = i; + + ll_reverse (elemp[r0], elemp[r1]); + check_list_contents (&list, values, cnt); + + free_elements (cnt, elems, elemp, values); + } +} + +/* Tests ll_next_permutation and ll_prev_permutation when the + permuted values have no duplicates. */ +static void +test_permutations_no_dups (void) +{ + const int max_elems = 8; + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt++) + { + struct ll_list list; + struct element **elems; + int *values; + int *old_values = xnmalloc (cnt, sizeof *values); + int *new_values = xnmalloc (cnt, sizeof *values); + + size_t perm_cnt; + + allocate_ascending (cnt, &list, &elems, NULL, &values); + + perm_cnt = 1; + extract_values (&list, old_values, cnt); + while (ll_next_permutation (ll_head (&list), ll_null (&list), + compare_elements, &aux_data)) + { + extract_values (&list, new_values, cnt); + check (lexicographical_compare_3way (new_values, cnt, + old_values, cnt, + sizeof *new_values, + compare_ints, NULL) > 0); + memcpy (old_values, new_values, (cnt) * sizeof *old_values); + perm_cnt++; + } + check (perm_cnt == factorial (cnt)); + check_list_contents (&list, values, cnt); + + perm_cnt = 1; + ll_reverse (ll_head (&list), ll_null (&list)); + extract_values (&list, old_values, cnt); + while (ll_prev_permutation (ll_head (&list), ll_null (&list), + compare_elements, &aux_data)) + { + extract_values (&list, new_values, cnt); + check (lexicographical_compare_3way (new_values, cnt, + old_values, cnt, + sizeof *new_values, + compare_ints, NULL) < 0); + memcpy (old_values, new_values, (cnt) * sizeof *old_values); + perm_cnt++; + } + check (perm_cnt == factorial (cnt)); + ll_reverse (ll_head (&list), ll_null (&list)); + check_list_contents (&list, values, cnt); + + free_elements (cnt, elems, NULL, values); + free (old_values); + free (new_values); + } +} + +/* Tests ll_next_permutation and ll_prev_permutation when the + permuted values contain duplicates. */ +static void +test_permutations_with_dups (void) +{ + const int max_elems = 8; + const int max_dup = 3; + const int repetitions = 1024; + + int cnt, repeat; + + for (repeat = 0; repeat < repetitions; repeat++) + for (cnt = 0; cnt < max_elems; cnt++) + { + struct ll_list list; + struct element **elems; + int *values; + int *old_values = xnmalloc (max_elems, sizeof *values); + int *new_values = xnmalloc (max_elems, sizeof *values); + + unsigned permutation_cnt; + int left = cnt; + int value = 0; + + allocate_elements (cnt, &list, &elems, NULL, &values); + + value = 0; + while (left > 0) + { + int max = left < max_dup ? left : max_dup; + int n = rand () % max + 1; + while (n-- > 0) + { + int idx = cnt - left--; + values[idx] = elems[idx]->x = value; + } + value++; + } + + permutation_cnt = 1; + extract_values (&list, old_values, cnt); + while (ll_next_permutation (ll_head (&list), ll_null (&list), + compare_elements, &aux_data)) + { + extract_values (&list, new_values, cnt); + check (lexicographical_compare_3way (new_values, cnt, + old_values, cnt, + sizeof *new_values, + compare_ints, NULL) > 0); + memcpy (old_values, new_values, cnt * sizeof *old_values); + permutation_cnt++; + } + check (permutation_cnt == expected_perms (values, cnt)); + check_list_contents (&list, values, cnt); + + permutation_cnt = 1; + ll_reverse (ll_head (&list), ll_null (&list)); + extract_values (&list, old_values, cnt); + while (ll_prev_permutation (ll_head (&list), ll_null (&list), + compare_elements, &aux_data)) + { + extract_values (&list, new_values, cnt); + check (lexicographical_compare_3way (new_values, cnt, + old_values, cnt, + sizeof *new_values, + compare_ints, NULL) < 0); + permutation_cnt++; + } + ll_reverse (ll_head (&list), ll_null (&list)); + check (permutation_cnt == expected_perms (values, cnt)); + check_list_contents (&list, values, cnt); + + free_elements (cnt, elems, NULL, values); + free (old_values); + free (new_values); + } +} + +/* Tests ll_merge when no equal values are to be merged. */ +static void +test_merge_no_dups (void) +{ + const int max_elems = 8; + const int max_filler = 3; + + int merge_cnt, pattern, pfx, gap, sfx, order; + + for (merge_cnt = 0; merge_cnt < max_elems; merge_cnt++) + for (pattern = 0; pattern <= (1 << merge_cnt); pattern++) + for (pfx = 0; pfx < max_filler; pfx++) + for (gap = 0; gap < max_filler; gap++) + for (sfx = 0; sfx < max_filler; sfx++) + for (order = 0; order < 2; order++) + { + struct ll_list list; + struct element **elems; + struct ll **elemp; + int *values; + + int list_cnt = pfx + merge_cnt + gap + sfx; + int a0, a1, b0, b1; + int i, j; + + allocate_elements (list_cnt, &list, + &elems, &elemp, &values); + + j = 0; + for (i = 0; i < pfx; i++) + elems[j++]->x = 100 + i; + a0 = j; + for (i = 0; i < merge_cnt; i++) + if (pattern & (1u << i)) + elems[j++]->x = i; + a1 = j; + for (i = 0; i < gap; i++) + elems[j++]->x = 200 + i; + b0 = j; + for (i = 0; i < merge_cnt; i++) + if (!(pattern & (1u << i))) + elems[j++]->x = i; + b1 = j; + for (i = 0; i < sfx; i++) + elems[j++]->x = 300 + i; + check (list_cnt == j); + + j = 0; + for (i = 0; i < pfx; i++) + values[j++] = 100 + i; + if (order == 0) + for (i = 0; i < merge_cnt; i++) + values[j++] = i; + for (i = 0; i < gap; i++) + values[j++] = 200 + i; + if (order == 1) + for (i = 0; i < merge_cnt; i++) + values[j++] = i; + for (i = 0; i < sfx; i++) + values[j++] = 300 + i; + check (list_cnt == j); + + if (order == 0) + ll_merge (elemp[a0], elemp[a1], elemp[b0], elemp[b1], + compare_elements, &aux_data); + else + ll_merge (elemp[b0], elemp[b1], elemp[a0], elemp[a1], + compare_elements, &aux_data); + + check_list_contents (&list, values, list_cnt); + + free_elements (list_cnt, elems, elemp, values); + } +} + +/* Tests ll_merge when equal values are to be merged. */ +static void +test_merge_with_dups (void) +{ + const int max_elems = 8; + + int cnt, merge_pat, inc_pat, order; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (merge_pat = 0; merge_pat <= (1 << cnt); merge_pat++) + for (inc_pat = 0; inc_pat <= (1 << cnt); inc_pat++) + for (order = 0; order < 2; order++) + { + struct ll_list list; + struct element **elems; + struct ll **elemp; + int *values; + + int mid; + int i, j, k; + + allocate_elements (cnt, &list, &elems, &elemp, &values); + + j = 0; + for (i = k = 0; i < cnt; i++) + { + if (merge_pat & (1u << i)) + elems[j++]->x = k; + if (inc_pat & (1u << i)) + k++; + } + mid = j; + for (i = k = 0; i < cnt; i++) + { + if (!(merge_pat & (1u << i))) + elems[j++]->x = k; + if (inc_pat & (1u << i)) + k++; + } + check (cnt == j); + + if (order == 0) + { + for (i = 0; i < cnt; i++) + elems[i]->y = i; + } + else + { + for (i = 0; i < mid; i++) + elems[i]->y = 100 + i; + for (i = mid; i < cnt; i++) + elems[i]->y = i; + } + + j = 0; + for (i = k = 0; i < cnt; i++) + { + values[j++] = k; + if (inc_pat & (1u << i)) + k++; + } + check (cnt == j); + + if (order == 0) + ll_merge (elemp[0], elemp[mid], elemp[mid], elemp[cnt], + compare_elements, &aux_data); + else + ll_merge (elemp[mid], elemp[cnt], elemp[0], elemp[mid], + compare_elements, &aux_data); + + check_list_contents (&list, values, cnt); + check (ll_is_sorted (ll_head (&list), ll_null (&list), + compare_elements_x_y, &aux_data)); + + free_elements (cnt, elems, elemp, values); + } +} + +/* Tests ll_sort on all permutations up to a maximum number of + elements. */ +static void +test_sort_exhaustive (void) +{ + const int max_elems = 8; + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt++) + { + struct ll_list list; + struct element **elems; + int *values; + + struct element **perm_elems; + int *perm_values; + + size_t perm_cnt; + + allocate_ascending (cnt, &list, &elems, NULL, &values); + allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values); + + perm_cnt = 1; + while (ll_next_permutation (ll_head (&list), ll_null (&list), + compare_elements, &aux_data)) + { + struct ll_list perm_list; + int j; + + extract_values (&list, perm_values, cnt); + ll_init (&perm_list); + for (j = 0; j < cnt; j++) + { + perm_elems[j]->x = perm_values[j]; + ll_push_tail (&perm_list, &perm_elems[j]->ll); + } + ll_sort (ll_head (&perm_list), ll_null (&perm_list), + compare_elements, &aux_data); + check_list_contents (&perm_list, values, cnt); + check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list), + compare_elements, &aux_data)); + perm_cnt++; + } + check (perm_cnt == factorial (cnt)); + + free_elements (cnt, elems, NULL, values); + free_elements (cnt, perm_elems, NULL, perm_values); + } +} + +/* Tests that ll_sort is stable in the presence of equal + values. */ +static void +test_sort_stable (void) +{ + const int max_elems = 6; + int cnt, inc_pat; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++) + { + struct ll_list list; + struct element **elems; + int *values; + + struct element **perm_elems; + int *perm_values; + + size_t perm_cnt; + int i, j; + + allocate_elements (cnt, &list, &elems, NULL, &values); + allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values); + + j = 0; + for (i = 0; i < cnt; i++) + { + elems[i]->x = values[i] = j; + if (inc_pat & (1 << i)) + j++; + elems[i]->y = i; + } + + perm_cnt = 1; + while (ll_next_permutation (ll_head (&list), ll_null (&list), + compare_elements_y, &aux_data)) + { + struct ll_list perm_list; + + extract_values (&list, perm_values, cnt); + ll_init (&perm_list); + for (i = 0; i < cnt; i++) + { + perm_elems[i]->x = perm_values[i]; + perm_elems[i]->y = i; + ll_push_tail (&perm_list, &perm_elems[i]->ll); + } + ll_sort (ll_head (&perm_list), ll_null (&perm_list), + compare_elements, &aux_data); + check_list_contents (&perm_list, values, cnt); + check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list), + compare_elements_x_y, &aux_data)); + perm_cnt++; + } + check (perm_cnt == factorial (cnt)); + + free_elements (cnt, elems, NULL, values); + free_elements (cnt, perm_elems, NULL, perm_values); + } +} + +/* Tests that ll_sort does not disturb elements outside the + range sorted. */ +static void +test_sort_subset (void) +{ + const int max_elems = 8; + + int cnt, r0, r1, repeat; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (repeat = 0; repeat < 100; repeat++) + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + { + struct ll_list list; + struct element **elems; + struct ll **elemp; + int *values; + + allocate_random (cnt, &list, &elems, &elemp, &values); + + qsort (&values[r0], r1 - r0, sizeof *values, compare_ints_noaux); + ll_sort (elemp[r0], elemp[r1], compare_elements, &aux_data); + check_list_contents (&list, values, cnt); + + free_elements (cnt, elems, elemp, values); + } +} + +/* Tests that ll_sort works with large lists. */ +static void +test_sort_big (void) +{ + const int max_elems = 1024; + + int cnt; + + for (cnt = 0; cnt < max_elems; cnt++) + { + struct ll_list list; + struct element **elems; + int *values; + + allocate_random (cnt, &list, &elems, NULL, &values); + + qsort (values, cnt, sizeof *values, compare_ints_noaux); + ll_sort (ll_head (&list), ll_null (&list), compare_elements, &aux_data); + check_list_contents (&list, values, cnt); + + free_elements (cnt, elems, NULL, values); + } +} + +/* Tests ll_unique. */ +static void +test_unique (void) +{ + const int max_elems = 10; + + int *ascending = xnmalloc (max_elems, sizeof *ascending); + + int cnt, inc_pat, i, j, unique_values; + + for (i = 0; i < max_elems; i++) + ascending[i] = i; + + for (cnt = 0; cnt < max_elems; cnt++) + for (inc_pat = 0; inc_pat < (1 << cnt); inc_pat++) + { + struct ll_list list, dups; + struct element **elems; + int *values; + + allocate_elements (cnt, &list, &elems, NULL, &values); + + j = unique_values = 0; + for (i = 0; i < cnt; i++) + { + unique_values = j + 1; + elems[i]->x = values[i] = j; + if (inc_pat & (1 << i)) + j++; + } + check_list_contents (&list, values, cnt); + + ll_init (&dups); + check (ll_unique (ll_head (&list), ll_null (&list), ll_null (&dups), + compare_elements, &aux_data) + == (size_t) unique_values); + check_list_contents (&list, ascending, unique_values); + + ll_splice (ll_null (&list), ll_head (&dups), ll_null (&dups)); + ll_sort (ll_head (&list), ll_null (&list), compare_elements, &aux_data); + check_list_contents (&list, values, cnt); + + free_elements (cnt, elems, NULL, values); + } + + free (ascending); +} + +/* Tests ll_sort_unique. */ +static void +test_sort_unique (void) +{ + const int max_elems = 7; + int cnt, inc_pat; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++) + { + struct ll_list list; + struct element **elems; + int *values; + + struct element **perm_elems; + int *perm_values; + + int unique_cnt; + int *unique_values; + + size_t perm_cnt; + int i, j; + + allocate_elements (cnt, &list, &elems, NULL, &values); + allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values); + + j = unique_cnt = 0; + for (i = 0; i < cnt; i++) + { + elems[i]->x = values[i] = j; + unique_cnt = j + 1; + if (inc_pat & (1 << i)) + j++; + } + + unique_values = xnmalloc (unique_cnt, sizeof *unique_values); + for (i = 0; i < unique_cnt; i++) + unique_values[i] = i; + + perm_cnt = 1; + while (ll_next_permutation (ll_head (&list), ll_null (&list), + compare_elements, &aux_data)) + { + struct ll_list perm_list; + + extract_values (&list, perm_values, cnt); + ll_init (&perm_list); + for (i = 0; i < cnt; i++) + { + perm_elems[i]->x = perm_values[i]; + perm_elems[i]->y = i; + ll_push_tail (&perm_list, &perm_elems[i]->ll); + } + ll_sort_unique (ll_head (&perm_list), ll_null (&perm_list), NULL, + compare_elements, &aux_data); + check_list_contents (&perm_list, unique_values, unique_cnt); + check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list), + compare_elements_x_y, &aux_data)); + perm_cnt++; + } + check (perm_cnt == expected_perms (values, cnt)); + + free_elements (cnt, elems, NULL, values); + free_elements (cnt, perm_elems, NULL, perm_values); + free (unique_values); + } +} + +/* Tests ll_insert_ordered. */ +static void +test_insert_ordered (void) +{ + const int max_elems = 6; + int cnt, inc_pat; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++) + { + struct ll_list list; + struct element **elems; + int *values; + + struct element **perm_elems; + int *perm_values; + + size_t perm_cnt; + int i, j; + + allocate_elements (cnt, &list, &elems, NULL, &values); + allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values); + + j = 0; + for (i = 0; i < cnt; i++) + { + elems[i]->x = values[i] = j; + if (inc_pat & (1 << i)) + j++; + elems[i]->y = i; + } + + perm_cnt = 1; + while (ll_next_permutation (ll_head (&list), ll_null (&list), + compare_elements_y, &aux_data)) + { + struct ll_list perm_list; + + extract_values (&list, perm_values, cnt); + ll_init (&perm_list); + for (i = 0; i < cnt; i++) + { + perm_elems[i]->x = perm_values[i]; + perm_elems[i]->y = i; + ll_insert_ordered (ll_head (&perm_list), ll_null (&perm_list), + &perm_elems[i]->ll, + compare_elements, &aux_data); + } + check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list), + compare_elements_x_y, &aux_data)); + perm_cnt++; + } + check (perm_cnt == factorial (cnt)); + + free_elements (cnt, elems, NULL, values); + free_elements (cnt, perm_elems, NULL, perm_values); + } +} + +/* Tests ll_partition. */ +static void +test_partition (void) +{ + const int max_elems = 10; + + int cnt; + unsigned pbase; + int r0, r1; + + for (cnt = 0; cnt < max_elems; cnt++) + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + for (pbase = 0; pbase <= (1u << (r1 - r0)); pbase++) + { + struct ll_list list; + struct element **elems; + struct ll **elemp; + int *values; + + unsigned pattern = pbase << r0; + int i, j; + int first_false; + struct ll *part_ll; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + + /* Check that ll_find_partition works okay in every + case. We use it after partitioning, too, but that + only tests cases where it returns non-null. */ + for (i = r0; i < r1; i++) + if (!(pattern & (1u << i))) + break; + j = i; + for (; i < r1; i++) + if (pattern & (1u << i)) + break; + part_ll = ll_find_partition (elemp[r0], elemp[r1], + pattern_pred, + &pattern); + if (i == r1) + check (part_ll == elemp[j]); + else + check (part_ll == NULL); + + /* Figure out expected results. */ + j = 0; + first_false = -1; + for (i = 0; i < r0; i++) + values[j++] = i; + for (i = r0; i < r1; i++) + if (pattern & (1u << i)) + values[j++] = i; + for (i = r0; i < r1; i++) + if (!(pattern & (1u << i))) + { + if (first_false == -1) + first_false = i; + values[j++] = i; + } + if (first_false == -1) + first_false = r1; + for (i = r1; i < cnt; i++) + values[j++] = i; + check (j == cnt); + + /* Partition and check for expected results. */ + check (ll_partition (elemp[r0], elemp[r1], + pattern_pred, &pattern) + == elemp[first_false]); + check (ll_find_partition (elemp[r0], elemp[r1], + pattern_pred, &pattern) + == elemp[first_false]); + check_list_contents (&list, values, cnt); + check ((int) ll_count (&list) == cnt); + + free_elements (cnt, elems, elemp, values); + } +} + +/* Main program. */ + +/* Runs TEST_FUNCTION and prints a message about NAME. */ +static void +run_test (void (*test_function) (void), const char *name) +{ + printf ("Running %s test... ", name); + fflush (stdout); + test_function (); + printf ("done.\n"); +} + +int +main (void) +{ + run_test (test_push_pop, "push/pop"); + run_test (test_insert_remove, "insert/remove"); + run_test (test_swap, "swap"); + run_test (test_swap_range, "swap_range"); + run_test (test_remove_range, "remove_range"); + run_test (test_remove_equal, "remove_equal"); + run_test (test_remove_if, "remove_if"); + run_test (test_moved, "moved"); + run_test (test_find_equal, "find_equal"); + run_test (test_find_if, "find_if"); + run_test (test_find_adjacent_equal, "find_adjacent_equal"); + run_test (test_count_range, "count_range"); + run_test (test_count_equal, "count_equal"); + run_test (test_count_if, "count_if"); + run_test (test_min_max, "min/max"); + run_test (test_lexicographical_compare_3way, "lexicographical_compare_3way"); + run_test (test_apply, "apply"); + run_test (test_reverse, "reverse"); + run_test (test_permutations_no_dups, "permutations (no dups)"); + run_test (test_permutations_with_dups, "permutations (with dups)"); + run_test (test_merge_no_dups, "merge (no dups)"); + run_test (test_merge_with_dups, "merge (with dups)"); + run_test (test_sort_exhaustive, "sort (exhaustive)"); + run_test (test_sort_stable, "sort (stability)"); + run_test (test_sort_subset, "sort (subset)"); + run_test (test_sort_big, "sort (big)"); + run_test (test_unique, "unique"); + run_test (test_sort_unique, "sort_unique"); + run_test (test_insert_ordered, "insert_ordered"); + run_test (test_partition, "partition"); + + return 0; +} + +/* + Local Variables: + compile-command: "gcc -Wall -Wstrict-prototypes -Wmissing-prototypes ll.c ll-test.c -o ll-test -g" + End: + */ diff --git a/tests/libpspp/llx-test.c b/tests/libpspp/llx-test.c new file mode 100644 index 00000000..0de38b02 --- /dev/null +++ b/tests/libpspp/llx-test.c @@ -0,0 +1,2069 @@ +/* PSPP - computes sample statistics. + Copyright (C) 2006 Free Software Foundation, Inc. + Written by Ben Pfaff . + + 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 llx_* routines defined in + ll.c. This test program aims to be as comprehensive as + possible. "gcov -b" should report 100% coverage of lines and + branches in llx.c and llx.h. "valgrind --leak-check=yes + --show-reachable=yes" should give a clean report. + + This test program depends only on ll.c, llx.c, and the + standard C library. + + See ll-test.c for a similar program for the ll_* routines. */ + +#include +#include +#include +#include +#include + +/* Support preliminaries. */ +#if __GNUC__ >= 2 && !defined UNUSED +#define UNUSED __attribute__ ((unused)) +#else +#define UNUSED +#endif + +/* 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 at %s, line %d\n", __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__) + +/* Prints a message about memory exhaustion and exits with a + failure code. */ +static void +xalloc_die (void) +{ + printf ("virtual memory exhausted\n"); + exit (EXIT_FAILURE); +} + +/* Allocates and returns N bytes of memory. */ +static void * +xmalloc (size_t n) +{ + if (n != 0) + { + void *p = malloc (n); + if (p == NULL) + xalloc_die (); + + return p; + } + else + return NULL; +} + +/* Allocates and returns N * M bytes of memory. */ +static void * +xnmalloc (size_t n, size_t m) +{ + if ((size_t) -1 / m <= n) + xalloc_die (); + return xmalloc (n * m); +} + +/* Always returns a null pointer, failing allocation. */ +static struct llx * +null_allocate_node (void *aux UNUSED) +{ + return NULL; +} + +/* Does nothing. */ +static void +null_release_node (struct llx *llx UNUSED, void *aux UNUSED) +{ +} + +/* Memory manager that fails all allocations and does nothing on + free. */ +static const struct llx_manager llx_null_mgr = + { + null_allocate_node, + null_release_node, + NULL, + }; + +/* List type and support routines. */ + +/* Test data element. */ +struct element + { + int x; /* Primary value. */ + int y; /* Secondary value. */ + }; + +int aux_data; + +/* Prints the elements in LIST. */ +static void UNUSED +print_list (struct llx_list *list) +{ + struct llx *x; + + printf ("list:"); + for (x = llx_head (list); x != llx_null (list); x = llx_next (x)) + { + const struct element *e = llx_data (x); + printf (" %d", e->x); + } + printf ("\n"); +} + +/* Prints the value returned by PREDICATE given auxiliary data + AUX for each element in LIST. */ +static void UNUSED +print_pred (struct llx_list *list, + llx_predicate_func *predicate, void *aux UNUSED) +{ + struct llx *x; + + printf ("pred:"); + for (x = llx_head (list); x != llx_null (list); x = llx_next (x)) + printf (" %d", predicate (x, aux)); + printf ("\n"); +} + +/* Prints the CNT numbers in VALUES. */ +static void UNUSED +print_array (int values[], size_t cnt) +{ + size_t i; + + printf ("arry:"); + for (i = 0; i < cnt; i++) + printf (" %d", values[i]); + printf ("\n"); +} + +/* 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 void *a_, const void *b_, void *aux) +{ + const struct element *a = a_; + const struct element *b = b_; + + check (aux == &aux_data); + return a->x < b->x ? -1 : a->x > b->x; +} + +/* Compares the `x' and `y' values in A and B and returns a + strcmp-type return value. Verifies that AUX points to + aux_data. */ +static int +compare_elements_x_y (const void *a_, const void *b_, void *aux) +{ + const struct element *a = a_; + const struct element *b = b_; + + check (aux == &aux_data); + if (a->x != b->x) + return a->x < b->x ? -1 : 1; + else if (a->y != b->y) + return a->y < b->y ? -1 : 1; + else + return 0; +} + +/* Compares the `y' values in A and B and returns a strcmp-type + return value. Verifies that AUX points to aux_data. */ +static int +compare_elements_y (const void *a_, const void *b_, void *aux) +{ + const struct element *a = a_; + const struct element *b = b_; + + check (aux == &aux_data); + return a->y < b->y ? -1 : a->y > b->y; +} + +/* Returns true if the bit in *PATTERN indicated by `x in + *ELEMENT is set, false otherwise. */ +static bool +pattern_pred (const void *element_, void *pattern_) +{ + const struct element *element = element_; + unsigned *pattern = pattern_; + + return (*pattern & (1u << element->x)) != 0; +} + +/* Allocates N elements in *ELEMS. + Adds the elements to LIST, if it is nonnull. + Puts pointers to the elements' list elements in *ELEMP, + followed by a pointer to the list null element, if ELEMP is + nonnull. + Allocates space for N values in *VALUES, if VALUES is + nonnull. */ +static void +allocate_elements (size_t n, + struct llx_list *list, + struct element ***elems, + struct llx ***elemp, + int **values) +{ + size_t i; + + if (list != NULL) + llx_init (list); + + *elems = xnmalloc (n, sizeof **elems); + if (elemp != NULL) + { + *elemp = xnmalloc (n + 1, sizeof *elemp); + (*elemp)[n] = llx_null (list); + } + + for (i = 0; i < n; i++) + { + (*elems)[i] = xmalloc (sizeof ***elems); + if (list != NULL) + { + struct llx *llx = llx_push_tail (list, (*elems)[i], &llx_malloc_mgr); + if (elemp != NULL) + (*elemp)[i] = llx; + } + } + + if (values != NULL) + *values = xnmalloc (n, sizeof *values); +} + +/* Copies the CNT values of `x' from LIST into VALUES[]. */ +static void +extract_values (struct llx_list *list, int values[], size_t cnt) +{ + struct llx *x; + + check (llx_count (list) == cnt); + for (x = llx_head (list); x != llx_null (list); x = llx_next (x)) + { + struct element *e = llx_data (x); + *values++ = e->x; + } +} + +/* As allocate_elements, but sets ascending values, starting + from 0, in `x' values in *ELEMS and in *VALUES (if + nonnull). */ +static void +allocate_ascending (size_t n, + struct llx_list *list, + struct element ***elems, + struct llx ***elemp, + int **values) +{ + size_t i; + + allocate_elements (n, list, elems, elemp, values); + + for (i = 0; i < n; i++) + (*elems)[i]->x = i; + if (values != NULL) + extract_values (list, *values, n); +} + +/* As allocate_elements, but sets binary values extracted from + successive bits in PATTERN in `x' values in *ELEMS and in + *VALUES (if nonnull). */ +static void +allocate_pattern (size_t n, + int pattern, + struct llx_list *list, + struct element ***elems, + struct llx ***elemp, + int **values) +{ + size_t i; + + allocate_elements (n, list, elems, elemp, values); + + for (i = 0; i < n; i++) + (*elems)[i]->x = (pattern & (1 << i)) != 0; + if (values != NULL) + extract_values (list, *values, n); +} + +/* Randomly shuffles the CNT elements in ARRAY, each of which is + SIZE bytes in size. */ +static void +random_shuffle (void *array_, size_t cnt, size_t size) +{ + char *array = array_; + char *tmp = xmalloc (size); + size_t i; + + for (i = 0; i < cnt; i++) + { + size_t j = rand () % (cnt - i) + i; + if (i != j) + { + memcpy (tmp, array + j * size, size); + memcpy (array + j * size, array + i * size, size); + memcpy (array + i * size, tmp, size); + } + } + + free (tmp); +} + +/* As allocate_ascending, but orders the values randomly. */ +static void +allocate_random (size_t n, + struct llx_list *list, + struct element ***elems, + struct llx ***elemp, + int **values) +{ + size_t i; + + allocate_elements (n, list, elems, elemp, values); + + for (i = 0; i < n; i++) + (*elems)[i]->x = i; + random_shuffle (*elems, n, sizeof **elems); + if (values != NULL) + extract_values (list, *values, n); +} + +/* Frees LIST, the N elements of ELEMS, ELEMP, and VALUES. */ +static void +free_elements (size_t n, + struct llx_list *list, + struct element **elems, + struct llx **elemp, + int *values) +{ + size_t i; + + if (list != NULL) + llx_destroy (list, NULL, NULL, &llx_malloc_mgr); + for (i = 0; i < n; i++) + free (elems[i]); + free (elems); + free (elemp); + free (values); +} + +/* Compares A and B and returns a strcmp-type return value. */ +static int +compare_ints (const void *a_, const void *b_, void *aux UNUSED) +{ + const int *a = a_; + const int *b = b_; + + return *a < *b ? -1 : *a > *b; +} + +/* Compares A and B and returns a strcmp-type return value. */ +static int +compare_ints_noaux (const void *a_, const void *b_) +{ + const int *a = a_; + const int *b = b_; + + return *a < *b ? -1 : *a > *b; +} + +/* Checks that LIST contains the CNT values in ELEMENTS. */ +static void +check_list_contents (struct llx_list *list, int elements[], size_t cnt) +{ + struct llx *llx; + size_t i; + + check ((cnt == 0) == llx_is_empty (list)); + + /* Iterate in forward order. */ + for (llx = llx_head (list), i = 0; i < cnt; llx = llx_next (llx), i++) + { + struct element *e = llx_data (llx); + check (elements[i] == e->x); + check (llx != llx_null (list)); + } + check (llx == llx_null (list)); + + /* Iterate in reverse order. */ + for (llx = llx_tail (list), i = 0; i < cnt; llx = llx_prev (llx), i++) + { + struct element *e = llx_data (llx); + check (elements[cnt - i - 1] == e->x); + check (llx != llx_null (list)); + } + check (llx == llx_null (list)); + + check (llx_count (list) == cnt); +} + +/* Lexicographicallxy compares ARRAY1, which contains COUNT1 + elements of SIZE bytes each, to ARRAY2, which contains COUNT2 + elements of SIZE bytes, according to COMPARE. Returns a + strcmp-type result. AUX is passed to COMPARE as auxiliary + data. */ +static int +lexicographical_compare_3way (const void *array1, size_t count1, + const void *array2, size_t count2, + size_t size, + int (*compare) (const void *, const void *, + void *aux), + void *aux) +{ + const char *first1 = array1; + const char *first2 = array2; + size_t min_count = count1 < count2 ? count1 : count2; + + while (min_count > 0) + { + int cmp = compare (first1, first2, aux); + if (cmp != 0) + return cmp; + + first1 += size; + first2 += size; + min_count--; + } + + return count1 < count2 ? -1 : count1 > count2; +} + +/* Tests. */ + +/* Tests list push and pop operations. */ +static void +test_push_pop (void) +{ + const int max_elems = 1024; + + struct llx_list list; + struct element **elems; + int *values; + + int i; + + allocate_elements (max_elems, NULL, &elems, NULL, &values); + + /* Push on tail. */ + llx_init (&list); + check_list_contents (&list, NULL, 0); + for (i = 0; i < max_elems; i++) + { + values[i] = elems[i]->x = i; + llx_push_tail (&list, elems[i], &llx_malloc_mgr); + check_list_contents (&list, values, i + 1); + } + + /* Remove from tail. */ + for (i = 0; i < max_elems; i++) + { + struct element *e = llx_pop_tail (&list, &llx_malloc_mgr); + check (e->x == max_elems - i - 1); + check_list_contents (&list, values, max_elems - i - 1); + } + + /* Push at start. */ + check_list_contents (&list, NULL, 0); + for (i = 0; i < max_elems; i++) + { + values[max_elems - i - 1] = elems[i]->x = max_elems - i - 1; + llx_push_head (&list, elems[i], &llx_malloc_mgr); + check_list_contents (&list, &values[max_elems - i - 1], i + 1); + } + + /* Remove from start. */ + for (i = 0; i < max_elems; i++) + { + struct element *e = llx_pop_head (&list, &llx_malloc_mgr); + check (e->x == (int) i); + check_list_contents (&list, &values[i + 1], max_elems - i - 1); + } + + free_elements (max_elems, &list, elems, NULL, values); +} + +/* Tests insertion and removal at arbitrary positions. */ +static void +test_insert_remove (void) +{ + const int max_elems = 16; + int cnt; + + for (cnt = 0; cnt < max_elems; cnt++) + { + struct element **elems; + struct llx **elemp; + int *values = xnmalloc (cnt + 1, sizeof *values); + + struct llx_list list; + struct element extra; + struct llx *extra_llx; + int pos; + + allocate_ascending (cnt, &list, &elems, &elemp, NULL); + extra.x = -1; + for (pos = 0; pos <= cnt; pos++) + { + int i, j; + + extra_llx = llx_insert (elemp[pos], &extra, &llx_malloc_mgr); + check (extra_llx != NULL); + + j = 0; + for (i = 0; i < pos; i++) + values[j++] = i; + values[j++] = -1; + for (; i < cnt; i++) + values[j++] = i; + check_list_contents (&list, values, cnt + 1); + + llx_remove (extra_llx, &llx_malloc_mgr); + } + check_list_contents (&list, values, cnt); + + free_elements (cnt, &list, elems, elemp, values); + } +} + +/* Tests swapping individual elements. */ +static void +test_swap (void) +{ + const int max_elems = 8; + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + + int i, j, k; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + check_list_contents (&list, values, cnt); + + for (i = 0; i < cnt; i++) + for (j = 0; j < cnt; j++) + for (k = 0; k < 2; k++) + { + int t; + + llx_swap (elemp[i], elemp[j]); + t = values[i]; + values[i] = values[j]; + values[j] = t; + check_list_contents (&list, values, cnt); + } + + free_elements (cnt, &list, elems, elemp, values); + } +} + +/* Tests swapping ranges of list elements. */ +static void +test_swap_range (void) +{ + const int max_elems = 8; + int cnt, a0, a1, b0, b1, r; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (a0 = 0; a0 <= cnt; a0++) + for (a1 = a0; a1 <= cnt; a1++) + for (b0 = a1; b0 <= cnt; b0++) + for (b1 = b0; b1 <= cnt; b1++) + for (r = 0; r < 2; r++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + + int i, j; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + check_list_contents (&list, values, cnt); + + j = 0; + for (i = 0; i < a0; i++) + values[j++] = i; + for (i = b0; i < b1; i++) + values[j++] = i; + for (i = a1; i < b0; i++) + values[j++] = i; + for (i = a0; i < a1; i++) + values[j++] = i; + for (i = b1; i < cnt; i++) + values[j++] = i; + check (j == cnt); + + if (r == 0) + llx_swap_range (elemp[a0], elemp[a1], elemp[b0], elemp[b1]); + else + llx_swap_range (elemp[b0], elemp[b1], elemp[a0], elemp[a1]); + check_list_contents (&list, values, cnt); + + free_elements (cnt, &list, elems, elemp, values); + } +} + +/* Tests removing ranges of list elements. */ +static void +test_remove_range (void) +{ + const int max_elems = 8; + + int cnt, r0, r1; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + + int i, j; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + check_list_contents (&list, values, cnt); + + j = 0; + for (i = 0; i < r0; i++) + values[j++] = i; + for (i = r1; i < cnt; i++) + values[j++] = i; + + llx_remove_range (elemp[r0], elemp[r1], &llx_malloc_mgr); + check_list_contents (&list, values, j); + + free_elements (cnt, &list, elems, elemp, values); + } +} + +/* Tests llx_remove_equal. */ +static void +test_remove_equal (void) +{ + const int max_elems = 8; + + int cnt, r0, r1, eq_pat; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + + struct element to_remove; + int remaining; + int i; + + allocate_elements (cnt, &list, &elems, &elemp, &values); + + remaining = 0; + for (i = 0; i < cnt; i++) + { + int x = eq_pat & (1 << i) ? -1 : i; + bool delete = x == -1 && r0 <= i && i < r1; + elems[i]->x = x; + if (!delete) + values[remaining++] = x; + } + + to_remove.x = -1; + check ((int) llx_remove_equal (elemp[r0], elemp[r1], &to_remove, + compare_elements, &aux_data, + &llx_malloc_mgr) + == cnt - remaining); + check_list_contents (&list, values, remaining); + + free_elements (cnt, &list, elems, elemp, values); + } +} + +/* Tests llx_remove_if. */ +static void +test_remove_if (void) +{ + const int max_elems = 8; + + int cnt, r0, r1, pattern; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + for (pattern = 0; pattern <= 1 << cnt; pattern++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + + int remaining; + int i; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + + remaining = 0; + for (i = 0; i < cnt; i++) + { + bool delete = (pattern & (1 << i)) && r0 <= i && i < r1; + if (!delete) + values[remaining++] = i; + } + + check ((int) llx_remove_if (elemp[r0], elemp[r1], + pattern_pred, &pattern, + &llx_malloc_mgr) + == cnt - remaining); + check_list_contents (&list, values, remaining); + + free_elements (cnt, &list, elems, elemp, values); + } +} + +/* Tests, via HELPER, a function that looks at list elements + equal to some specified element. */ +static void +test_examine_equal_range (void (*helper) (int r0, int r1, int eq_pat, + const void *to_find, + struct llx **elemp)) +{ + const int max_elems = 8; + + int cnt, r0, r1, eq_pat; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + + struct element to_find; + + int i; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + + for (i = 0; i < cnt; i++) + if (eq_pat & (1 << i)) + values[i] = elems[i]->x = -1; + + to_find.x = -1; + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + helper (r0, r1, eq_pat, &to_find, elemp); + + check_list_contents (&list, values, cnt); + + free_elements (cnt, &list, elems, elemp, values); + } +} + +/* Tests, via HELPER, a function that looks at list elements for + which a given predicate returns true. */ +static void +test_examine_if_range (void (*helper) (int r0, int r1, int eq_pat, + struct llx **elemp)) +{ + const int max_elems = 8; + + int cnt, r0, r1, eq_pat; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + helper (r0, r1, eq_pat, elemp); + + check_list_contents (&list, values, cnt); + + free_elements (cnt, &list, elems, elemp, values); + } +} + +/* Helper function for testing llx_find_equal. */ +static void +test_find_equal_helper (int r0, int r1, int eq_pat, + const void *to_find, struct llx **elemp) +{ + struct llx *match; + int i; + + match = llx_find_equal (elemp[r0], elemp[r1], to_find, + compare_elements, &aux_data); + for (i = r0; i < r1; i++) + if (eq_pat & (1 << i)) + break; + + check (match == elemp[i]); +} + +/* Tests llx_find_equal. */ +static void +test_find_equal (void) +{ + test_examine_equal_range (test_find_equal_helper); +} + +/* Helper function for testing llx_find_if. */ +static void +test_find_if_helper (int r0, int r1, int eq_pat, struct llx **elemp) +{ + struct llx *match = llx_find_if (elemp[r0], elemp[r1], + pattern_pred, &eq_pat); + int i; + + for (i = r0; i < r1; i++) + if (eq_pat & (1 << i)) + break; + + check (match == elemp[i]); +} + +/* Tests llx_find_if. */ +static void +test_find_if (void) +{ + test_examine_if_range (test_find_if_helper); +} + +/* Tests llx_find_adjacent_equal. */ +static void +test_find_adjacent_equal (void) +{ + const int max_elems = 8; + + int cnt, eq_pat; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + int match; + + int i; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + + match = -1; + for (i = 0; i < cnt - 1; i++) + { + elems[i]->y = i; + if (eq_pat & (1 << i)) + { + values[i] = elems[i]->x = match; + values[i + 1] = elems[i + 1]->x = match; + } + else + match--; + } + + for (i = 0; i <= cnt; i++) + { + struct llx *llx1 = llx_find_adjacent_equal (elemp[i], llx_null (&list), + compare_elements, + &aux_data); + struct llx *llx2; + int j; + + llx2 = llx_null (&list); + for (j = i; j < cnt - 1; j++) + if (eq_pat & (1 << j)) + { + llx2 = elemp[j]; + break; + } + check (llx1 == llx2); + } + check_list_contents (&list, values, cnt); + + free_elements (cnt, &list, elems, elemp, values); + } +} + +/* Helper function for testing llx_count_range. */ +static void +test_count_range_helper (int r0, int r1, int eq_pat UNUSED, struct llx **elemp) +{ + check ((int) llx_count_range (elemp[r0], elemp[r1]) == r1 - r0); +} + +/* Tests llx_count_range. */ +static void +test_count_range (void) +{ + test_examine_if_range (test_count_range_helper); +} + +/* Helper function for testing llx_count_equal. */ +static void +test_count_equal_helper (int r0, int r1, int eq_pat, + const void *to_find, struct llx **elemp) +{ + int count1, count2; + int i; + + count1 = llx_count_equal (elemp[r0], elemp[r1], to_find, + compare_elements, &aux_data); + count2 = 0; + for (i = r0; i < r1; i++) + if (eq_pat & (1 << i)) + count2++; + + check (count1 == count2); +} + +/* Tests llx_count_equal. */ +static void +test_count_equal (void) +{ + test_examine_equal_range (test_count_equal_helper); +} + +/* Helper function for testing llx_count_if. */ +static void +test_count_if_helper (int r0, int r1, int eq_pat, struct llx **elemp) +{ + int count1; + int count2; + int i; + + count1 = llx_count_if (elemp[r0], elemp[r1], pattern_pred, &eq_pat); + + count2 = 0; + for (i = r0; i < r1; i++) + if (eq_pat & (1 << i)) + count2++; + + check (count1 == count2); +} + +/* Tests llx_count_if. */ +static void +test_count_if (void) +{ + test_examine_if_range (test_count_if_helper); +} + +/* 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 llx_min and llx_max. */ +static void +test_min_max (void) +{ + const int max_elems = 6; + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + int *new_values = xnmalloc (cnt, sizeof *values); + + size_t perm_cnt; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + + perm_cnt = 1; + while (llx_next_permutation (llx_head (&list), llx_null (&list), + compare_elements, &aux_data)) + { + int r0, r1; + struct llx *x; + int i; + + for (i = 0, x = llx_head (&list); x != llx_null (&list); + x = llx_next (x), i++) + { + struct element *e = llx_data (x); + elemp[i] = x; + new_values[i] = e->x; + } + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + { + struct llx *min = llx_min (elemp[r0], elemp[r1], + compare_elements, &aux_data); + struct llx *max = llx_max (elemp[r0], elemp[r1], + compare_elements, &aux_data); + if (r0 == r1) + { + check (min == elemp[r1]); + check (max == elemp[r1]); + } + else + { + struct element *min_elem = llx_data (min); + struct element *max_elem = llx_data (max); + int min_int, max_int; + int i; + + min_int = max_int = new_values[r0]; + for (i = r0; i < r1; i++) + { + int value = new_values[i]; + if (value < min_int) + min_int = value; + if (value > max_int) + max_int = value; + } + check (min != elemp[r1] && min_elem->x == min_int); + check (max != elemp[r1] && max_elem->x == max_int); + } + } + perm_cnt++; + } + check (perm_cnt == factorial (cnt)); + check_list_contents (&list, values, cnt); + + free_elements (cnt, &list, elems, elemp, values); + free (new_values); + } +} + +/* Tests llx_lexicographical_compare_3way. */ +static void +test_lexicographical_compare_3way (void) +{ + const int max_elems = 4; + + int cnt_a, pat_a, cnt_b, pat_b; + + for (cnt_a = 0; cnt_a <= max_elems; cnt_a++) + for (pat_a = 0; pat_a <= 1 << cnt_a; pat_a++) + for (cnt_b = 0; cnt_b <= max_elems; cnt_b++) + for (pat_b = 0; pat_b <= 1 << cnt_b; pat_b++) + { + struct llx_list list_a, list_b; + struct element **elems_a, **elems_b; + struct llx **elemp_a, **elemp_b; + int *values_a, *values_b; + + int a0, a1, b0, b1; + + allocate_pattern (cnt_a, pat_a, + &list_a, &elems_a, &elemp_a, &values_a); + allocate_pattern (cnt_b, pat_b, + &list_b, &elems_b, &elemp_b, &values_b); + + for (a0 = 0; a0 <= cnt_a; a0++) + for (a1 = a0; a1 <= cnt_a; a1++) + for (b0 = 0; b0 <= cnt_b; b0++) + for (b1 = b0; b1 <= cnt_b; b1++) + { + int a_ordering = lexicographical_compare_3way ( + values_a + a0, a1 - a0, + values_b + b0, b1 - b0, + sizeof *values_a, + compare_ints, NULL); + + int b_ordering = llx_lexicographical_compare_3way ( + elemp_a[a0], elemp_a[a1], + elemp_b[b0], elemp_b[b1], + compare_elements, &aux_data); + + check (a_ordering == b_ordering); + } + + free_elements (cnt_a, &list_a, elems_a, elemp_a, values_a); + free_elements (cnt_b, &list_b, elems_b, elemp_b, values_b); + } +} + +/* Appends the `x' value in element E to the array pointed to by + NEXT_OUTPUT, and advances NEXT_OUTPUT to the next position. */ +static void +apply_func (void *e_, void *next_output_) +{ + struct element *e = e_; + int **next_output = next_output_; + + *(*next_output)++ = e->x; +} + +/* Tests llx_apply. */ +static void +test_apply (void) +{ + const int max_elems = 8; + + int cnt, r0, r1; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + + int *output; + int *next_output; + int j; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + check_list_contents (&list, values, cnt); + + output = next_output = xnmalloc (cnt, sizeof *output); + llx_apply (elemp[r0], elemp[r1], apply_func, &next_output); + check_list_contents (&list, values, cnt); + llx_destroy (&list, NULL, NULL, &llx_malloc_mgr); + + check (r1 - r0 == next_output - output); + for (j = 0; j < r1 - r0; j++) + check (output[j] == r0 + j); + + free_elements (cnt, NULL, elems, elemp, values); + free (output); + } +} + +/* Tests llx_destroy. */ +static void +test_destroy (void) +{ + const int max_elems = 8; + + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + + int *output; + int *next_output; + int j; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + check_list_contents (&list, values, cnt); + + output = next_output = xnmalloc (cnt, sizeof *output); + llx_destroy (&list, apply_func, &next_output, &llx_malloc_mgr); + + check (cnt == next_output - output); + for (j = 0; j < cnt; j++) + check (output[j] == j); + + free_elements (cnt, NULL, elems, elemp, values); + free (output); + } +} + +/* Tests llx_reverse. */ +static void +test_reverse (void) +{ + const int max_elems = 8; + + int cnt, r0, r1; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + + int i, j; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + check_list_contents (&list, values, cnt); + + j = 0; + for (i = 0; i < r0; i++) + values[j++] = i; + for (i = r1 - 1; i >= r0; i--) + values[j++] = i; + for (i = r1; i < cnt; i++) + values[j++] = i; + + llx_reverse (elemp[r0], elemp[r1]); + check_list_contents (&list, values, cnt); + + free_elements (cnt, &list, elems, elemp, values); + } +} + +/* Tests llx_next_permutation and llx_prev_permutation when the + permuted values have no duplicates. */ +static void +test_permutations_no_dups (void) +{ + const int max_elems = 8; + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt++) + { + struct llx_list list; + struct element **elems; + int *values; + int *old_values = xnmalloc (cnt, sizeof *values); + int *new_values = xnmalloc (cnt, sizeof *values); + + size_t perm_cnt; + + allocate_ascending (cnt, &list, &elems, NULL, &values); + + perm_cnt = 1; + extract_values (&list, old_values, cnt); + while (llx_next_permutation (llx_head (&list), llx_null (&list), + compare_elements, &aux_data)) + { + extract_values (&list, new_values, cnt); + check (lexicographical_compare_3way (new_values, cnt, + old_values, cnt, + sizeof *new_values, + compare_ints, NULL) > 0); + memcpy (old_values, new_values, (cnt) * sizeof *old_values); + perm_cnt++; + } + check (perm_cnt == factorial (cnt)); + check_list_contents (&list, values, cnt); + + perm_cnt = 1; + llx_reverse (llx_head (&list), llx_null (&list)); + extract_values (&list, old_values, cnt); + while (llx_prev_permutation (llx_head (&list), llx_null (&list), + compare_elements, &aux_data)) + { + extract_values (&list, new_values, cnt); + check (lexicographical_compare_3way (new_values, cnt, + old_values, cnt, + sizeof *new_values, + compare_ints, NULL) < 0); + memcpy (old_values, new_values, (cnt) * sizeof *old_values); + perm_cnt++; + } + check (perm_cnt == factorial (cnt)); + llx_reverse (llx_head (&list), llx_null (&list)); + check_list_contents (&list, values, cnt); + + free_elements (cnt, &list, elems, NULL, values); + free (old_values); + free (new_values); + } +} + +/* Tests llx_next_permutation and llx_prev_permutation when the + permuted values contain duplicates. */ +static void +test_permutations_with_dups (void) +{ + const int max_elems = 8; + const int max_dup = 3; + const int repetitions = 1024; + + int cnt, repeat; + + for (repeat = 0; repeat < repetitions; repeat++) + for (cnt = 0; cnt < max_elems; cnt++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + int *old_values = xnmalloc (max_elems, sizeof *values); + int *new_values = xnmalloc (max_elems, sizeof *values); + + unsigned permutation_cnt; + int left = cnt; + int value = 0; + + allocate_elements (cnt, &list, &elems, &elemp, &values); + + value = 0; + while (left > 0) + { + int max = left < max_dup ? left : max_dup; + int n = rand () % max + 1; + while (n-- > 0) + { + int idx = cnt - left--; + values[idx] = elems[idx]->x = value; + } + value++; + } + + permutation_cnt = 1; + extract_values (&list, old_values, cnt); + while (llx_next_permutation (llx_head (&list), llx_null (&list), + compare_elements, &aux_data)) + { + extract_values (&list, new_values, cnt); + check (lexicographical_compare_3way (new_values, cnt, + old_values, cnt, + sizeof *new_values, + compare_ints, NULL) > 0); + memcpy (old_values, new_values, cnt * sizeof *old_values); + permutation_cnt++; + } + check (permutation_cnt == expected_perms (values, cnt)); + check_list_contents (&list, values, cnt); + + permutation_cnt = 1; + llx_reverse (llx_head (&list), llx_null (&list)); + extract_values (&list, old_values, cnt); + while (llx_prev_permutation (llx_head (&list), llx_null (&list), + compare_elements, &aux_data)) + { + extract_values (&list, new_values, cnt); + check (lexicographical_compare_3way (new_values, cnt, + old_values, cnt, + sizeof *new_values, + compare_ints, NULL) < 0); + permutation_cnt++; + } + llx_reverse (llx_head (&list), llx_null (&list)); + check (permutation_cnt == expected_perms (values, cnt)); + check_list_contents (&list, values, cnt); + + free_elements (cnt, &list, elems, elemp, values); + free (old_values); + free (new_values); + } +} + +/* Tests llx_merge when no equal values are to be merged. */ +static void +test_merge_no_dups (void) +{ + const int max_elems = 8; + const int max_fillxer = 3; + + int merge_cnt, pattern, pfx, gap, sfx, order; + + for (merge_cnt = 0; merge_cnt < max_elems; merge_cnt++) + for (pattern = 0; pattern <= (1 << merge_cnt); pattern++) + for (pfx = 0; pfx < max_fillxer; pfx++) + for (gap = 0; gap < max_fillxer; gap++) + for (sfx = 0; sfx < max_fillxer; sfx++) + for (order = 0; order < 2; order++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + + int list_cnt = pfx + merge_cnt + gap + sfx; + int a0, a1, b0, b1; + int i, j; + + allocate_elements (list_cnt, &list, + &elems, &elemp, &values); + + j = 0; + for (i = 0; i < pfx; i++) + elems[j++]->x = 100 + i; + a0 = j; + for (i = 0; i < merge_cnt; i++) + if (pattern & (1u << i)) + elems[j++]->x = i; + a1 = j; + for (i = 0; i < gap; i++) + elems[j++]->x = 200 + i; + b0 = j; + for (i = 0; i < merge_cnt; i++) + if (!(pattern & (1u << i))) + elems[j++]->x = i; + b1 = j; + for (i = 0; i < sfx; i++) + elems[j++]->x = 300 + i; + check (list_cnt == j); + + j = 0; + for (i = 0; i < pfx; i++) + values[j++] = 100 + i; + if (order == 0) + for (i = 0; i < merge_cnt; i++) + values[j++] = i; + for (i = 0; i < gap; i++) + values[j++] = 200 + i; + if (order == 1) + for (i = 0; i < merge_cnt; i++) + values[j++] = i; + for (i = 0; i < sfx; i++) + values[j++] = 300 + i; + check (list_cnt == j); + + if (order == 0) + llx_merge (elemp[a0], elemp[a1], elemp[b0], elemp[b1], + compare_elements, &aux_data); + else + llx_merge (elemp[b0], elemp[b1], elemp[a0], elemp[a1], + compare_elements, &aux_data); + + check_list_contents (&list, values, list_cnt); + + free_elements (list_cnt, &list, elems, elemp, values); + } +} + +/* Tests llx_merge when equal values are to be merged. */ +static void +test_merge_with_dups (void) +{ + const int max_elems = 8; + + int cnt, merge_pat, inc_pat, order; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (merge_pat = 0; merge_pat <= (1 << cnt); merge_pat++) + for (inc_pat = 0; inc_pat <= (1 << cnt); inc_pat++) + for (order = 0; order < 2; order++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + + int mid; + int i, j, k; + + allocate_elements (cnt, &list, &elems, &elemp, &values); + + j = 0; + for (i = k = 0; i < cnt; i++) + { + if (merge_pat & (1u << i)) + elems[j++]->x = k; + if (inc_pat & (1u << i)) + k++; + } + mid = j; + for (i = k = 0; i < cnt; i++) + { + if (!(merge_pat & (1u << i))) + elems[j++]->x = k; + if (inc_pat & (1u << i)) + k++; + } + check (cnt == j); + + if (order == 0) + { + for (i = 0; i < cnt; i++) + elems[i]->y = i; + } + else + { + for (i = 0; i < mid; i++) + elems[i]->y = 100 + i; + for (i = mid; i < cnt; i++) + elems[i]->y = i; + } + + j = 0; + for (i = k = 0; i < cnt; i++) + { + values[j++] = k; + if (inc_pat & (1u << i)) + k++; + } + check (cnt == j); + + if (order == 0) + llx_merge (elemp[0], elemp[mid], elemp[mid], elemp[cnt], + compare_elements, &aux_data); + else + llx_merge (elemp[mid], elemp[cnt], elemp[0], elemp[mid], + compare_elements, &aux_data); + + check_list_contents (&list, values, cnt); + check (llx_is_sorted (llx_head (&list), llx_null (&list), + compare_elements_x_y, &aux_data)); + + free_elements (cnt, &list, elems, elemp, values); + } +} + +/* Tests llx_sort on all permutations up to a maximum number of + elements. */ +static void +test_sort_exhaustive (void) +{ + const int max_elems = 8; + int cnt; + + for (cnt = 0; cnt <= max_elems; cnt++) + { + struct llx_list list; + struct element **elems; + int *values; + + struct element **perm_elems; + int *perm_values; + + size_t perm_cnt; + + allocate_ascending (cnt, &list, &elems, NULL, &values); + allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values); + + perm_cnt = 1; + while (llx_next_permutation (llx_head (&list), llx_null (&list), + compare_elements, &aux_data)) + { + struct llx_list perm_list; + int j; + + extract_values (&list, perm_values, cnt); + llx_init (&perm_list); + for (j = 0; j < cnt; j++) + { + perm_elems[j]->x = perm_values[j]; + llx_push_tail (&perm_list, perm_elems[j], &llx_malloc_mgr); + } + llx_sort (llx_head (&perm_list), llx_null (&perm_list), + compare_elements, &aux_data); + check_list_contents (&perm_list, values, cnt); + check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list), + compare_elements, &aux_data)); + llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr); + perm_cnt++; + } + check (perm_cnt == factorial (cnt)); + + free_elements (cnt, &list, elems, NULL, values); + free_elements (cnt, NULL, perm_elems, NULL, perm_values); + } +} + +/* Tests that llx_sort is stable in the presence of equal + values. */ +static void +test_sort_stable (void) +{ + const int max_elems = 6; + int cnt, inc_pat; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++) + { + struct llx_list list; + struct element **elems; + int *values; + + struct element **perm_elems; + int *perm_values; + + size_t perm_cnt; + int i, j; + + allocate_elements (cnt, &list, &elems, NULL, &values); + allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values); + + j = 0; + for (i = 0; i < cnt; i++) + { + elems[i]->x = values[i] = j; + if (inc_pat & (1 << i)) + j++; + elems[i]->y = i; + } + + perm_cnt = 1; + while (llx_next_permutation (llx_head (&list), llx_null (&list), + compare_elements_y, &aux_data)) + { + struct llx_list perm_list; + + extract_values (&list, perm_values, cnt); + llx_init (&perm_list); + for (i = 0; i < cnt; i++) + { + perm_elems[i]->x = perm_values[i]; + perm_elems[i]->y = i; + llx_push_tail (&perm_list, perm_elems[i], &llx_malloc_mgr); + } + llx_sort (llx_head (&perm_list), llx_null (&perm_list), + compare_elements, &aux_data); + check_list_contents (&perm_list, values, cnt); + check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list), + compare_elements_x_y, &aux_data)); + llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr); + perm_cnt++; + } + check (perm_cnt == factorial (cnt)); + + free_elements (cnt, &list, elems, NULL, values); + free_elements (cnt, NULL, perm_elems, NULL, perm_values); + } +} + +/* Tests that llx_sort does not disturb elements outside the + range sorted. */ +static void +test_sort_subset (void) +{ + const int max_elems = 8; + + int cnt, r0, r1, repeat; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (repeat = 0; repeat < 100; repeat++) + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + + allocate_random (cnt, &list, &elems, &elemp, &values); + + qsort (&values[r0], r1 - r0, sizeof *values, compare_ints_noaux); + llx_sort (elemp[r0], elemp[r1], compare_elements, &aux_data); + check_list_contents (&list, values, cnt); + + free_elements (cnt, &list, elems, elemp, values); + } +} + +/* Tests that llx_sort works with large lists. */ +static void +test_sort_big (void) +{ + const int max_elems = 1024; + + int cnt; + + for (cnt = 0; cnt < max_elems; cnt++) + { + struct llx_list list; + struct element **elems; + int *values; + + allocate_random (cnt, &list, &elems, NULL, &values); + + qsort (values, cnt, sizeof *values, compare_ints_noaux); + llx_sort (llx_head (&list), llx_null (&list), compare_elements, &aux_data); + check_list_contents (&list, values, cnt); + + free_elements (cnt, &list, elems, NULL, values); + } +} + +/* Tests llx_unique. */ +static void +test_unique (void) +{ + const int max_elems = 10; + + int *ascending = xnmalloc (max_elems, sizeof *ascending); + + int cnt, inc_pat, i, j, unique_values; + + for (i = 0; i < max_elems; i++) + ascending[i] = i; + + for (cnt = 0; cnt < max_elems; cnt++) + for (inc_pat = 0; inc_pat < (1 << cnt); inc_pat++) + { + struct llx_list list, dups; + struct element **elems; + int *values; + + allocate_elements (cnt, &list, &elems, NULL, &values); + + j = unique_values = 0; + for (i = 0; i < cnt; i++) + { + unique_values = j + 1; + elems[i]->x = values[i] = j; + if (inc_pat & (1 << i)) + j++; + } + check_list_contents (&list, values, cnt); + + llx_init (&dups); + check (llx_unique (llx_head (&list), llx_null (&list), + llx_null (&dups), + compare_elements, &aux_data, + &llx_malloc_mgr) + == (size_t) unique_values); + check_list_contents (&list, ascending, unique_values); + + llx_splice (llx_null (&list), llx_head (&dups), llx_null (&dups)); + llx_sort (llx_head (&list), llx_null (&list), compare_elements, &aux_data); + check_list_contents (&list, values, cnt); + + llx_destroy (&dups, NULL, NULL, &llx_malloc_mgr); + free_elements (cnt, &list, elems, NULL, values); + } + + free (ascending); +} + +/* Tests llx_sort_unique. */ +static void +test_sort_unique (void) +{ + const int max_elems = 7; + int cnt, inc_pat; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++) + { + struct llx_list list; + struct element **elems; + int *values; + + struct element **perm_elems; + int *perm_values; + + int unique_cnt; + int *unique_values; + + size_t perm_cnt; + int i, j; + + allocate_elements (cnt, &list, &elems, NULL, &values); + allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values); + + j = unique_cnt = 0; + for (i = 0; i < cnt; i++) + { + elems[i]->x = values[i] = j; + unique_cnt = j + 1; + if (inc_pat & (1 << i)) + j++; + } + + unique_values = xnmalloc (unique_cnt, sizeof *unique_values); + for (i = 0; i < unique_cnt; i++) + unique_values[i] = i; + + perm_cnt = 1; + while (llx_next_permutation (llx_head (&list), llx_null (&list), + compare_elements, &aux_data)) + { + struct llx_list perm_list; + + extract_values (&list, perm_values, cnt); + llx_init (&perm_list); + for (i = 0; i < cnt; i++) + { + perm_elems[i]->x = perm_values[i]; + perm_elems[i]->y = i; + llx_push_tail (&perm_list, perm_elems[i], &llx_malloc_mgr); + } + llx_sort_unique (llx_head (&perm_list), llx_null (&perm_list), NULL, + compare_elements, &aux_data, + &llx_malloc_mgr); + check_list_contents (&perm_list, unique_values, unique_cnt); + check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list), + compare_elements_x_y, &aux_data)); + llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr); + perm_cnt++; + } + check (perm_cnt == expected_perms (values, cnt)); + + free_elements (cnt, &list, elems, NULL, values); + free_elements (cnt, NULL, perm_elems, NULL, perm_values); + free (unique_values); + } +} + +/* Tests llx_insert_ordered. */ +static void +test_insert_ordered (void) +{ + const int max_elems = 6; + int cnt, inc_pat; + + for (cnt = 0; cnt <= max_elems; cnt++) + for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++) + { + struct llx_list list; + struct element **elems; + int *values; + + struct element **perm_elems; + int *perm_values; + + size_t perm_cnt; + int i, j; + + allocate_elements (cnt, &list, &elems, NULL, &values); + allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values); + + j = 0; + for (i = 0; i < cnt; i++) + { + elems[i]->x = values[i] = j; + if (inc_pat & (1 << i)) + j++; + elems[i]->y = i; + } + + perm_cnt = 1; + while (llx_next_permutation (llx_head (&list), llx_null (&list), + compare_elements_y, &aux_data)) + { + struct llx_list perm_list; + + extract_values (&list, perm_values, cnt); + llx_init (&perm_list); + for (i = 0; i < cnt; i++) + { + perm_elems[i]->x = perm_values[i]; + perm_elems[i]->y = i; + llx_insert_ordered (llx_head (&perm_list), + llx_null (&perm_list), + perm_elems[i], + compare_elements, &aux_data, + &llx_malloc_mgr); + } + check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list), + compare_elements_x_y, &aux_data)); + llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr); + perm_cnt++; + } + check (perm_cnt == factorial (cnt)); + + free_elements (cnt, &list, elems, NULL, values); + free_elements (cnt, NULL, perm_elems, NULL, perm_values); + } +} + +/* Tests llx_partition. */ +static void +test_partition (void) +{ + const int max_elems = 10; + + int cnt; + unsigned pbase; + int r0, r1; + + for (cnt = 0; cnt < max_elems; cnt++) + for (r0 = 0; r0 <= cnt; r0++) + for (r1 = r0; r1 <= cnt; r1++) + for (pbase = 0; pbase <= (1u << (r1 - r0)); pbase++) + { + struct llx_list list; + struct element **elems; + struct llx **elemp; + int *values; + + unsigned pattern = pbase << r0; + int i, j; + int first_false; + struct llx *part_llx; + + allocate_ascending (cnt, &list, &elems, &elemp, &values); + + /* Check that llx_find_partition works okay in every + case. We use it after partitioning, too, but that + only tests cases where it returns non-null. */ + for (i = r0; i < r1; i++) + if (!(pattern & (1u << i))) + break; + j = i; + for (; i < r1; i++) + if (pattern & (1u << i)) + break; + part_llx = llx_find_partition (elemp[r0], elemp[r1], + pattern_pred, + &pattern); + if (i == r1) + check (part_llx == elemp[j]); + else + check (part_llx == NULL); + + /* Figure out expected results. */ + j = 0; + first_false = -1; + for (i = 0; i < r0; i++) + values[j++] = i; + for (i = r0; i < r1; i++) + if (pattern & (1u << i)) + values[j++] = i; + for (i = r0; i < r1; i++) + if (!(pattern & (1u << i))) + { + if (first_false == -1) + first_false = i; + values[j++] = i; + } + if (first_false == -1) + first_false = r1; + for (i = r1; i < cnt; i++) + values[j++] = i; + check (j == cnt); + + /* Partition and check for expected results. */ + check (llx_partition (elemp[r0], elemp[r1], + pattern_pred, &pattern) + == elemp[first_false]); + check (llx_find_partition (elemp[r0], elemp[r1], + pattern_pred, &pattern) + == elemp[first_false]); + check_list_contents (&list, values, cnt); + check ((int) llx_count (&list) == cnt); + + free_elements (cnt, &list, elems, elemp, values); + } +} + +/* Tests that allocation failure is gracefully handled. */ +static void +test_allocation_failure (void) +{ + struct llx_list list; + + llx_init (&list); + check (llx_push_head (&list, NULL, &llx_null_mgr) == NULL); + check (llx_push_tail (&list, NULL, &llx_null_mgr) == NULL); + check (llx_insert (llx_null (&list), NULL, &llx_null_mgr) == NULL); + check_list_contents (&list, NULL, 0); +} + +/* Main program. */ + +/* Runs TEST_FUNCTION and prints a message about NAME. */ +static void +run_test (void (*test_function) (void), const char *name) +{ + printf ("Running %s test... ", name); + fflush (stdout); + test_function (); + printf ("done.\n"); +} + +int +main (void) +{ + run_test (test_push_pop, "push/pop"); + run_test (test_insert_remove, "insert/remove"); + run_test (test_swap, "swap"); + run_test (test_swap_range, "swap_range"); + run_test (test_remove_range, "remove_range"); + run_test (test_remove_equal, "remove_equal"); + run_test (test_remove_if, "remove_if"); + run_test (test_find_equal, "find_equal"); + run_test (test_find_if, "find_if"); + run_test (test_find_adjacent_equal, "find_adjacent_equal"); + run_test (test_count_range, "count_range"); + run_test (test_count_equal, "count_equal"); + run_test (test_count_if, "count_if"); + run_test (test_min_max, "min/max"); + run_test (test_lexicographical_compare_3way, "lexicographical_compare_3way"); + run_test (test_apply, "apply"); + run_test (test_destroy, "destroy"); + run_test (test_reverse, "reverse"); + run_test (test_permutations_no_dups, "permutations (no dups)"); + run_test (test_permutations_with_dups, "permutations (with dups)"); + run_test (test_merge_no_dups, "merge (no dups)"); + run_test (test_merge_with_dups, "merge (with dups)"); + run_test (test_sort_exhaustive, "sort (exhaustive)"); + run_test (test_sort_stable, "sort (stability)"); + run_test (test_sort_subset, "sort (subset)"); + run_test (test_sort_big, "sort (big)"); + run_test (test_unique, "unique"); + run_test (test_sort_unique, "sort_unique"); + run_test (test_insert_ordered, "insert_ordered"); + run_test (test_partition, "partition"); + run_test (test_allocation_failure, "allocation failure"); + + return 0; +} + +/* + Local Variables: + compile-command: "gcc -Wall -Wstrict-prototypes -Wmissing-prototypes ll.c llx.c llx-test.c -o llx-test -g" + End: + */ -- 2.30.2