1 /* PSPP - computes sample statistics.
2 Copyright (C) 2006 Free Software Foundation, Inc.
3 Written by Ben Pfaff <blp@gnu.org>.
5 This program is free software; you can redistribute it and/or
6 modify it under the terms of the GNU General Public License as
7 published by the Free Software Foundation; either version 2 of the
8 License, or (at your option) any later version.
10 This program is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 /* This is a test program for the ll_* routines defined in
21 ll.c. This test program aims to be as comprehensive as
22 possible. "gcov -b" should report 100% coverage of lines and
23 branches in the ll_* routines. "valgrind --leak-check=yes
24 --show-reachable=yes" should give a clean report.
26 This test program depends only on ll.c and the standard C
29 See llx-test.c for a similar program for the llx_*
32 #include <libpspp/ll.h>
38 /* Support preliminaries. */
39 #if __GNUC__ >= 2 && !defined UNUSED
40 #define UNUSED __attribute__ ((unused))
45 /* Exit with a failure code.
46 (Place a breakpoint on this function while debugging.) */
53 /* If OK is not true, prints a message about failure on the
54 current source file and the given LINE and terminates. */
56 check_func (bool ok, int line)
60 printf ("check failed at %s, line %d\n", __FILE__, line);
65 /* Verifies that EXPR evaluates to true.
66 If not, prints a message citing the calling line number and
68 #define check(EXPR) check_func ((EXPR), __LINE__)
70 /* Prints a message about memory exhaustion and exits with a
75 printf ("virtual memory exhausted\n");
79 /* Allocates and returns N bytes of memory. */
95 /* Allocates and returns N * M bytes of memory. */
97 xnmalloc (size_t n, size_t m)
99 if ((size_t) -1 / m <= n)
101 return xmalloc (n * m);
104 /* List type and support routines. */
106 /* Test data element. */
109 struct ll ll; /* Embedded list element. */
110 int x; /* Primary value. */
111 int y; /* Secondary value. */
116 /* Returns the `struct element' that LL is embedded within. */
117 static struct element *
118 ll_to_element (const struct ll *ll)
120 return ll_data (ll, struct element, ll);
123 /* Prints the elements in LIST. */
125 print_list (struct ll_list *list)
130 for (x = ll_head (list); x != ll_null (list); x = ll_next (x))
132 struct element *e = ll_to_element (x);
133 printf (" %d", e->x);
138 /* Prints the value returned by PREDICATE given auxiliary data
139 AUX for each element in LIST. */
141 print_pred (struct ll_list *list,
142 ll_predicate_func *predicate, void *aux UNUSED)
147 for (x = ll_head (list); x != ll_null (list); x = ll_next (x))
148 printf (" %d", predicate (x, aux));
152 /* Prints the CNT numbers in VALUES. */
154 print_array (int values[], size_t cnt)
159 for (i = 0; i < cnt; i++)
160 printf (" %d", values[i]);
164 /* Compares the `x' values in A and B and returns a strcmp-type
165 return value. Verifies that AUX points to aux_data. */
167 compare_elements (const struct ll *a_, const struct ll *b_, void *aux)
169 const struct element *a = ll_to_element (a_);
170 const struct element *b = ll_to_element (b_);
172 check (aux == &aux_data);
173 return a->x < b->x ? -1 : a->x > b->x;
176 /* Compares the `x' and `y' values in A and B and returns a
177 strcmp-type return value. Verifies that AUX points to
180 compare_elements_x_y (const struct ll *a_, const struct ll *b_, void *aux)
182 const struct element *a = ll_to_element (a_);
183 const struct element *b = ll_to_element (b_);
185 check (aux == &aux_data);
187 return a->x < b->x ? -1 : 1;
188 else if (a->y != b->y)
189 return a->y < b->y ? -1 : 1;
194 /* Compares the `y' values in A and B and returns a strcmp-type
195 return value. Verifies that AUX points to aux_data. */
197 compare_elements_y (const struct ll *a_, const struct ll *b_, void *aux)
199 const struct element *a = ll_to_element (a_);
200 const struct element *b = ll_to_element (b_);
202 check (aux == &aux_data);
203 return a->y < b->y ? -1 : a->y > b->y;
206 /* Returns true if the bit in *PATTERN indicated by `x in
207 *ELEMENT is set, false otherwise. */
209 pattern_pred (const struct ll *element_, void *pattern_)
211 const struct element *element = ll_to_element (element_);
212 unsigned *pattern = pattern_;
214 return (*pattern & (1u << element->x)) != 0;
217 /* Allocates N elements in *ELEMS.
218 Adds the elements to LIST, if it is nonnull.
219 Puts pointers to the elements' list elements in *ELEMP,
220 followed by a pointer to the list null element, if ELEMP is
222 Allocates space for N values in *VALUES, if VALUES is
225 allocate_elements (size_t n,
226 struct ll_list *list,
227 struct element ***elems,
236 *elems = xnmalloc (n, sizeof **elems);
237 for (i = 0; i < n; i++)
239 (*elems)[i] = xmalloc (sizeof ***elems);
241 ll_push_tail (list, &(*elems)[i]->ll);
246 *elemp = xnmalloc (n + 1, sizeof *elemp);
247 for (i = 0; i < n; i++)
248 (*elemp)[i] = &(*elems)[i]->ll;
249 (*elemp)[n] = ll_null (list);
253 *values = xnmalloc (n, sizeof *values);
256 /* Copies the CNT values of `x' from LIST into VALUES[]. */
258 extract_values (struct ll_list *list, int values[], size_t cnt)
262 check (ll_count (list) == cnt);
263 for (x = ll_head (list); x != ll_null (list); x = ll_next (x))
265 struct element *e = ll_to_element (x);
270 /* As allocate_elements, but sets ascending values, starting
271 from 0, in `x' values in *ELEMS and in *VALUES (if
274 allocate_ascending (size_t n,
275 struct ll_list *list,
276 struct element ***elems,
282 allocate_elements (n, list, elems, elemp, values);
284 for (i = 0; i < n; i++)
287 extract_values (list, *values, n);
290 /* As allocate_elements, but sets binary values extracted from
291 successive bits in PATTERN in `x' values in *ELEMS and in
292 *VALUES (if nonnull). */
294 allocate_pattern (size_t n,
296 struct ll_list *list,
297 struct element ***elems,
303 allocate_elements (n, list, elems, elemp, values);
305 for (i = 0; i < n; i++)
306 (*elems)[i]->x = (pattern & (1 << i)) != 0;
308 extract_values (list, *values, n);
311 /* Randomly shuffles the CNT elements in ARRAY, each of which is
312 SIZE bytes in size. */
314 random_shuffle (void *array_, size_t cnt, size_t size)
316 char *array = array_;
317 char *tmp = xmalloc (size);
320 for (i = 0; i < cnt; i++)
322 size_t j = rand () % (cnt - i) + i;
325 memcpy (tmp, array + j * size, size);
326 memcpy (array + j * size, array + i * size, size);
327 memcpy (array + i * size, tmp, size);
334 /* As allocate_ascending, but orders the values randomly. */
336 allocate_random (size_t n,
337 struct ll_list *list,
338 struct element ***elems,
344 allocate_elements (n, list, elems, elemp, values);
346 for (i = 0; i < n; i++)
348 random_shuffle (*elems, n, sizeof **elems);
350 extract_values (list, *values, n);
353 /* Frees the N elements of ELEMS, ELEMP, and VALUES. */
355 free_elements (size_t n,
356 struct element **elems,
362 for (i = 0; i < n; i++)
369 /* Compares A and B and returns a strcmp-type return value. */
371 compare_ints (const void *a_, const void *b_, void *aux UNUSED)
376 return *a < *b ? -1 : *a > *b;
379 /* Compares A and B and returns a strcmp-type return value. */
381 compare_ints_noaux (const void *a_, const void *b_)
386 return *a < *b ? -1 : *a > *b;
389 /* Checks that LIST contains the CNT values in ELEMENTS. */
391 check_list_contents (struct ll_list *list, int elements[], size_t cnt)
396 check ((cnt == 0) == ll_is_empty (list));
398 /* Iterate in forward order. */
399 for (ll = ll_head (list), i = 0; i < cnt; ll = ll_next (ll), i++)
401 struct element *e = ll_to_element (ll);
402 check (elements[i] == e->x);
403 check (ll != ll_null (list));
405 check (ll == ll_null (list));
407 /* Iterate in reverse order. */
408 for (ll = ll_tail (list), i = 0; i < cnt; ll = ll_prev (ll), i++)
410 struct element *e = ll_to_element (ll);
411 check (elements[cnt - i - 1] == e->x);
412 check (ll != ll_null (list));
414 check (ll == ll_null (list));
416 check (ll_count (list) == cnt);
419 /* Lexicographically compares ARRAY1, which contains COUNT1
420 elements of SIZE bytes each, to ARRAY2, which contains COUNT2
421 elements of SIZE bytes, according to COMPARE. Returns a
422 strcmp-type result. AUX is passed to COMPARE as auxiliary
425 lexicographical_compare_3way (const void *array1, size_t count1,
426 const void *array2, size_t count2,
428 int (*compare) (const void *, const void *,
432 const char *first1 = array1;
433 const char *first2 = array2;
434 size_t min_count = count1 < count2 ? count1 : count2;
436 while (min_count > 0)
438 int cmp = compare (first1, first2, aux);
447 return count1 < count2 ? -1 : count1 > count2;
452 /* Tests list push and pop operations. */
456 const int max_elems = 1024;
459 struct element **elems;
464 allocate_elements (max_elems, NULL, &elems, NULL, &values);
468 check_list_contents (&list, NULL, 0);
469 for (i = 0; i < max_elems; i++)
471 values[i] = elems[i]->x = i;
472 ll_push_tail (&list, &elems[i]->ll);
473 check_list_contents (&list, values, i + 1);
476 /* Remove from tail. */
477 for (i = 0; i < max_elems; i++)
479 struct element *e = ll_to_element (ll_pop_tail (&list));
480 check (e->x == max_elems - i - 1);
481 check_list_contents (&list, values, max_elems - i - 1);
485 check_list_contents (&list, NULL, 0);
486 for (i = 0; i < max_elems; i++)
488 values[max_elems - i - 1] = elems[i]->x = max_elems - i - 1;
489 ll_push_head (&list, &elems[i]->ll);
490 check_list_contents (&list, &values[max_elems - i - 1], i + 1);
493 /* Remove from start. */
494 for (i = 0; i < max_elems; i++)
496 struct element *e = ll_to_element (ll_pop_head (&list));
497 check (e->x == (int) i);
498 check_list_contents (&list, &values[i + 1], max_elems - i - 1);
501 free_elements (max_elems, elems, NULL, values);
504 /* Tests insertion and removal at arbitrary positions. */
506 test_insert_remove (void)
508 const int max_elems = 16;
511 for (cnt = 0; cnt < max_elems; cnt++)
513 struct element **elems;
515 int *values = xnmalloc (cnt + 1, sizeof *values);
518 struct element extra;
521 allocate_ascending (cnt, &list, &elems, &elemp, NULL);
523 for (pos = 0; pos <= cnt; pos++)
527 ll_insert (elemp[pos], &extra.ll);
530 for (i = 0; i < pos; i++)
535 check_list_contents (&list, values, cnt + 1);
537 ll_remove (&extra.ll);
539 check_list_contents (&list, values, cnt);
541 free_elements (cnt, elems, elemp, values);
545 /* Tests swapping individual elements. */
549 const int max_elems = 8;
552 for (cnt = 0; cnt <= max_elems; cnt++)
555 struct element **elems;
560 allocate_ascending (cnt, &list, &elems, NULL, &values);
561 check_list_contents (&list, values, cnt);
563 for (i = 0; i < cnt; i++)
564 for (j = 0; j < cnt; j++)
565 for (k = 0; k < 2; k++)
569 ll_swap (&elems[i]->ll, &elems[j]->ll);
571 values[i] = values[j];
573 check_list_contents (&list, values, cnt);
576 free_elements (cnt, elems, NULL, values);
580 /* Tests swapping ranges of list elements. */
582 test_swap_range (void)
584 const int max_elems = 8;
585 int cnt, a0, a1, b0, b1, r;
587 for (cnt = 0; cnt <= max_elems; cnt++)
588 for (a0 = 0; a0 <= cnt; a0++)
589 for (a1 = a0; a1 <= cnt; a1++)
590 for (b0 = a1; b0 <= cnt; b0++)
591 for (b1 = b0; b1 <= cnt; b1++)
592 for (r = 0; r < 2; r++)
595 struct element **elems;
601 allocate_ascending (cnt, &list, &elems, &elemp, &values);
602 check_list_contents (&list, values, cnt);
605 for (i = 0; i < a0; i++)
607 for (i = b0; i < b1; i++)
609 for (i = a1; i < b0; i++)
611 for (i = a0; i < a1; i++)
613 for (i = b1; i < cnt; i++)
618 ll_swap_range (elemp[a0], elemp[a1], elemp[b0], elemp[b1]);
620 ll_swap_range (elemp[b0], elemp[b1], elemp[a0], elemp[a1]);
621 check_list_contents (&list, values, cnt);
623 free_elements (cnt, elems, elemp, values);
627 /* Tests removing ranges of list elements. */
629 test_remove_range (void)
631 const int max_elems = 8;
635 for (cnt = 0; cnt <= max_elems; cnt++)
636 for (r0 = 0; r0 <= cnt; r0++)
637 for (r1 = r0; r1 <= cnt; r1++)
640 struct element **elems;
646 allocate_ascending (cnt, &list, &elems, &elemp, &values);
647 check_list_contents (&list, values, cnt);
650 for (i = 0; i < r0; i++)
652 for (i = r1; i < cnt; i++)
655 ll_remove_range (elemp[r0], elemp[r1]);
656 check_list_contents (&list, values, j);
658 free_elements (cnt, elems, elemp, values);
662 /* Tests ll_remove_equal. */
664 test_remove_equal (void)
666 const int max_elems = 8;
668 int cnt, r0, r1, eq_pat;
670 for (cnt = 0; cnt <= max_elems; cnt++)
671 for (r0 = 0; r0 <= cnt; r0++)
672 for (r1 = r0; r1 <= cnt; r1++)
673 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
676 struct element **elems;
680 struct element to_remove;
684 allocate_elements (cnt, &list, &elems, &elemp, &values);
687 for (i = 0; i < cnt; i++)
689 int x = eq_pat & (1 << i) ? -1 : i;
690 bool delete = x == -1 && r0 <= i && i < r1;
693 values[remaining++] = x;
697 check ((int) ll_remove_equal (elemp[r0], elemp[r1], &to_remove.ll,
698 compare_elements, &aux_data)
700 check_list_contents (&list, values, remaining);
702 free_elements (cnt, elems, elemp, values);
706 /* Tests ll_remove_if. */
708 test_remove_if (void)
710 const int max_elems = 8;
712 int cnt, r0, r1, pattern;
714 for (cnt = 0; cnt <= max_elems; cnt++)
715 for (r0 = 0; r0 <= cnt; r0++)
716 for (r1 = r0; r1 <= cnt; r1++)
717 for (pattern = 0; pattern <= 1 << cnt; pattern++)
720 struct element **elems;
727 allocate_elements (cnt, &list, &elems, &elemp, &values);
730 for (i = 0; i < cnt; i++)
732 bool delete = (pattern & (1 << i)) && r0 <= i && i < r1;
735 values[remaining++] = i;
738 check ((int) ll_remove_if (elemp[r0], elemp[r1],
739 pattern_pred, &pattern)
741 check_list_contents (&list, values, remaining);
743 free_elements (cnt, elems, elemp, values);
747 /* Tests ll_moved. */
751 const int max_elems = 8;
755 for (cnt = 0; cnt <= max_elems; cnt++)
758 struct element **elems;
759 struct element **new_elems;
764 allocate_ascending (cnt, &list, &elems, NULL, &values);
765 allocate_elements (cnt, NULL, &new_elems, NULL, NULL);
766 check_list_contents (&list, values, cnt);
768 for (i = 0; i < cnt; i++)
770 *new_elems[i] = *elems[i];
771 ll_moved (&new_elems[i]->ll);
772 check_list_contents (&list, values, cnt);
775 free_elements (cnt, elems, NULL, values);
776 free_elements (cnt, new_elems, NULL, NULL);
780 /* Tests, via HELPER, a function that looks at list elements
781 equal to some specified element. */
783 test_examine_equal_range (void (*helper) (int r0, int r1, int eq_pat,
787 const int max_elems = 8;
789 int cnt, r0, r1, eq_pat;
791 for (cnt = 0; cnt <= max_elems; cnt++)
792 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
795 struct element **elems;
799 struct element to_find;
803 allocate_ascending (cnt, &list, &elems, &elemp, &values);
805 for (i = 0; i < cnt; i++)
806 if (eq_pat & (1 << i))
807 values[i] = elems[i]->x = -1;
810 for (r0 = 0; r0 <= cnt; r0++)
811 for (r1 = r0; r1 <= cnt; r1++)
812 helper (r0, r1, eq_pat, &to_find.ll, elemp);
814 check_list_contents (&list, values, cnt);
816 free_elements (cnt, elems, elemp, values);
820 /* Tests, via HELPER, a function that looks at list elements for
821 which a given predicate returns true. */
823 test_examine_if_range (void (*helper) (int r0, int r1, int eq_pat,
826 const int max_elems = 8;
828 int cnt, r0, r1, eq_pat;
830 for (cnt = 0; cnt <= max_elems; cnt++)
831 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
834 struct element **elems;
838 allocate_ascending (cnt, &list, &elems, &elemp, &values);
840 for (r0 = 0; r0 <= cnt; r0++)
841 for (r1 = r0; r1 <= cnt; r1++)
842 helper (r0, r1, eq_pat, elemp);
844 check_list_contents (&list, values, cnt);
846 free_elements (cnt, elems, elemp, values);
850 /* Helper function for testing ll_find_equal. */
852 test_find_equal_helper (int r0, int r1, int eq_pat,
853 struct ll *to_find, struct ll **elemp)
858 match = ll_find_equal (elemp[r0], elemp[r1], to_find,
859 compare_elements, &aux_data);
860 for (i = r0; i < r1; i++)
861 if (eq_pat & (1 << i))
864 check (match == elemp[i]);
867 /* Tests ll_find_equal. */
869 test_find_equal (void)
871 test_examine_equal_range (test_find_equal_helper);
874 /* Helper function for testing ll_find_if. */
876 test_find_if_helper (int r0, int r1, int eq_pat, struct ll **elemp)
878 struct ll *match = ll_find_if (elemp[r0], elemp[r1],
879 pattern_pred, &eq_pat);
882 for (i = r0; i < r1; i++)
883 if (eq_pat & (1 << i))
886 check (match == elemp[i]);
889 /* Tests ll_find_if. */
893 test_examine_if_range (test_find_if_helper);
896 /* Tests ll_find_adjacent_equal. */
898 test_find_adjacent_equal (void)
900 const int max_elems = 8;
904 for (cnt = 0; cnt <= max_elems; cnt++)
905 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
908 struct element **elems;
915 allocate_ascending (cnt, &list, &elems, &elemp, &values);
918 for (i = 0; i < cnt - 1; i++)
921 if (eq_pat & (1 << i))
923 values[i] = elems[i]->x = match;
924 values[i + 1] = elems[i + 1]->x = match;
930 for (i = 0; i <= cnt; i++)
932 struct ll *ll1 = ll_find_adjacent_equal (elemp[i], ll_null (&list),
938 ll2 = ll_null (&list);
939 for (j = i; j < cnt - 1; j++)
940 if (eq_pat & (1 << j))
947 check_list_contents (&list, values, cnt);
949 free_elements (cnt, elems, elemp, values);
953 /* Helper function for testing ll_count_range. */
955 test_count_range_helper (int r0, int r1, int eq_pat UNUSED, struct ll **elemp)
957 check ((int) ll_count_range (elemp[r0], elemp[r1]) == r1 - r0);
960 /* Tests ll_count_range. */
962 test_count_range (void)
964 test_examine_if_range (test_count_range_helper);
967 /* Helper function for testing ll_count_equal. */
969 test_count_equal_helper (int r0, int r1, int eq_pat,
970 struct ll *to_find, struct ll **elemp)
975 count1 = ll_count_equal (elemp[r0], elemp[r1], to_find,
976 compare_elements, &aux_data);
978 for (i = r0; i < r1; i++)
979 if (eq_pat & (1 << i))
982 check (count1 == count2);
985 /* Tests ll_count_equal. */
987 test_count_equal (void)
989 test_examine_equal_range (test_count_equal_helper);
992 /* Helper function for testing ll_count_if. */
994 test_count_if_helper (int r0, int r1, int eq_pat, struct ll **elemp)
1000 count1 = ll_count_if (elemp[r0], elemp[r1], pattern_pred, &eq_pat);
1003 for (i = r0; i < r1; i++)
1004 if (eq_pat & (1 << i))
1007 check (count1 == count2);
1010 /* Tests ll_count_if. */
1012 test_count_if (void)
1014 test_examine_if_range (test_count_if_helper);
1019 factorial (unsigned n)
1027 /* Returns the number of permutations of the CNT values in
1028 VALUES. If VALUES contains duplicates, they must be
1031 expected_perms (int *values, size_t cnt)
1036 perm_cnt = factorial (cnt);
1037 for (i = 0; i < cnt; i = j)
1039 for (j = i + 1; j < cnt; j++)
1040 if (values[i] != values[j])
1042 perm_cnt /= factorial (j - i);
1047 /* Tests ll_min and ll_max. */
1051 const int max_elems = 6;
1054 for (cnt = 0; cnt <= max_elems; cnt++)
1056 struct ll_list list;
1057 struct element **elems;
1060 int *new_values = xnmalloc (cnt, sizeof *values);
1064 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1067 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1068 compare_elements, &aux_data))
1074 for (i = 0, x = ll_head (&list); x != ll_null (&list);
1075 x = ll_next (x), i++)
1077 struct element *e = ll_to_element (x);
1079 new_values[i] = e->x;
1081 for (r0 = 0; r0 <= cnt; r0++)
1082 for (r1 = r0; r1 <= cnt; r1++)
1084 struct ll *min = ll_min (elemp[r0], elemp[r1],
1085 compare_elements, &aux_data);
1086 struct ll *max = ll_max (elemp[r0], elemp[r1],
1087 compare_elements, &aux_data);
1090 check (min == elemp[r1]);
1091 check (max == elemp[r1]);
1095 int min_int, max_int;
1098 min_int = max_int = new_values[r0];
1099 for (i = r0; i < r1; i++)
1101 int value = new_values[i];
1102 if (value < min_int)
1104 if (value > max_int)
1107 check (min != elemp[r1]
1108 && ll_to_element (min)->x == min_int);
1109 check (max != elemp[r1]
1110 && ll_to_element (max)->x == max_int);
1115 check (perm_cnt == factorial (cnt));
1116 check_list_contents (&list, values, cnt);
1118 free_elements (cnt, elems, elemp, values);
1123 /* Tests ll_lexicographical_compare_3way. */
1125 test_lexicographical_compare_3way (void)
1127 const int max_elems = 4;
1129 int cnt_a, pat_a, cnt_b, pat_b;
1131 for (cnt_a = 0; cnt_a <= max_elems; cnt_a++)
1132 for (pat_a = 0; pat_a <= 1 << cnt_a; pat_a++)
1133 for (cnt_b = 0; cnt_b <= max_elems; cnt_b++)
1134 for (pat_b = 0; pat_b <= 1 << cnt_b; pat_b++)
1136 struct ll_list list_a, list_b;
1137 struct element **elems_a, **elems_b;
1138 struct ll **elemp_a, **elemp_b;
1139 int *values_a, *values_b;
1143 allocate_pattern (cnt_a, pat_a,
1144 &list_a, &elems_a, &elemp_a, &values_a);
1145 allocate_pattern (cnt_b, pat_b,
1146 &list_b, &elems_b, &elemp_b, &values_b);
1148 for (a0 = 0; a0 <= cnt_a; a0++)
1149 for (a1 = a0; a1 <= cnt_a; a1++)
1150 for (b0 = 0; b0 <= cnt_b; b0++)
1151 for (b1 = b0; b1 <= cnt_b; b1++)
1153 int a_ordering = lexicographical_compare_3way (
1154 values_a + a0, a1 - a0,
1155 values_b + b0, b1 - b0,
1157 compare_ints, NULL);
1159 int b_ordering = ll_lexicographical_compare_3way (
1160 elemp_a[a0], elemp_a[a1],
1161 elemp_b[b0], elemp_b[b1],
1162 compare_elements, &aux_data);
1164 check (a_ordering == b_ordering);
1167 free_elements (cnt_a, elems_a, elemp_a, values_a);
1168 free_elements (cnt_b, elems_b, elemp_b, values_b);
1172 /* Appends the `x' value in element E to the array pointed to by
1173 NEXT_OUTPUT, and advances NEXT_OUTPUT to the next position. */
1175 apply_func (struct ll *e_, void *next_output_)
1177 struct element *e = ll_to_element (e_);
1178 int **next_output = next_output_;
1180 *(*next_output)++ = e->x;
1183 /* Tests ll_apply. */
1187 const int max_elems = 8;
1191 for (cnt = 0; cnt <= max_elems; cnt++)
1192 for (r0 = 0; r0 <= cnt; r0++)
1193 for (r1 = r0; r1 <= cnt; r1++)
1195 struct ll_list list;
1196 struct element **elems;
1205 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1206 check_list_contents (&list, values, cnt);
1208 output = next_output = xnmalloc (cnt, sizeof *output);
1209 ll_apply (elemp[r0], elemp[r1], apply_func, &next_output);
1210 check_list_contents (&list, values, cnt);
1212 check (r1 - r0 == next_output - output);
1213 for (i = 0; i < r1 - r0; i++)
1214 check (output[i] == r0 + i);
1216 free_elements (cnt, elems, elemp, values);
1221 /* Tests ll_reverse. */
1225 const int max_elems = 8;
1229 for (cnt = 0; cnt <= max_elems; cnt++)
1230 for (r0 = 0; r0 <= cnt; r0++)
1231 for (r1 = r0; r1 <= cnt; r1++)
1233 struct ll_list list;
1234 struct element **elems;
1240 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1241 check_list_contents (&list, values, cnt);
1244 for (i = 0; i < r0; i++)
1246 for (i = r1 - 1; i >= r0; i--)
1248 for (i = r1; i < cnt; i++)
1251 ll_reverse (elemp[r0], elemp[r1]);
1252 check_list_contents (&list, values, cnt);
1254 free_elements (cnt, elems, elemp, values);
1258 /* Tests ll_next_permutation and ll_prev_permutation when the
1259 permuted values have no duplicates. */
1261 test_permutations_no_dups (void)
1263 const int max_elems = 8;
1266 for (cnt = 0; cnt <= max_elems; cnt++)
1268 struct ll_list list;
1269 struct element **elems;
1271 int *old_values = xnmalloc (cnt, sizeof *values);
1272 int *new_values = xnmalloc (cnt, sizeof *values);
1276 allocate_ascending (cnt, &list, &elems, NULL, &values);
1279 extract_values (&list, old_values, cnt);
1280 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1281 compare_elements, &aux_data))
1283 extract_values (&list, new_values, cnt);
1284 check (lexicographical_compare_3way (new_values, cnt,
1287 compare_ints, NULL) > 0);
1288 memcpy (old_values, new_values, (cnt) * sizeof *old_values);
1291 check (perm_cnt == factorial (cnt));
1292 check_list_contents (&list, values, cnt);
1295 ll_reverse (ll_head (&list), ll_null (&list));
1296 extract_values (&list, old_values, cnt);
1297 while (ll_prev_permutation (ll_head (&list), ll_null (&list),
1298 compare_elements, &aux_data))
1300 extract_values (&list, new_values, cnt);
1301 check (lexicographical_compare_3way (new_values, cnt,
1304 compare_ints, NULL) < 0);
1305 memcpy (old_values, new_values, (cnt) * sizeof *old_values);
1308 check (perm_cnt == factorial (cnt));
1309 ll_reverse (ll_head (&list), ll_null (&list));
1310 check_list_contents (&list, values, cnt);
1312 free_elements (cnt, elems, NULL, values);
1318 /* Tests ll_next_permutation and ll_prev_permutation when the
1319 permuted values contain duplicates. */
1321 test_permutations_with_dups (void)
1323 const int max_elems = 8;
1324 const int max_dup = 3;
1325 const int repetitions = 1024;
1329 for (repeat = 0; repeat < repetitions; repeat++)
1330 for (cnt = 0; cnt < max_elems; cnt++)
1332 struct ll_list list;
1333 struct element **elems;
1335 int *old_values = xnmalloc (max_elems, sizeof *values);
1336 int *new_values = xnmalloc (max_elems, sizeof *values);
1338 unsigned permutation_cnt;
1342 allocate_elements (cnt, &list, &elems, NULL, &values);
1347 int max = left < max_dup ? left : max_dup;
1348 int n = rand () % max + 1;
1351 int idx = cnt - left--;
1352 values[idx] = elems[idx]->x = value;
1357 permutation_cnt = 1;
1358 extract_values (&list, old_values, cnt);
1359 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1360 compare_elements, &aux_data))
1362 extract_values (&list, new_values, cnt);
1363 check (lexicographical_compare_3way (new_values, cnt,
1366 compare_ints, NULL) > 0);
1367 memcpy (old_values, new_values, cnt * sizeof *old_values);
1370 check (permutation_cnt == expected_perms (values, cnt));
1371 check_list_contents (&list, values, cnt);
1373 permutation_cnt = 1;
1374 ll_reverse (ll_head (&list), ll_null (&list));
1375 extract_values (&list, old_values, cnt);
1376 while (ll_prev_permutation (ll_head (&list), ll_null (&list),
1377 compare_elements, &aux_data))
1379 extract_values (&list, new_values, cnt);
1380 check (lexicographical_compare_3way (new_values, cnt,
1383 compare_ints, NULL) < 0);
1386 ll_reverse (ll_head (&list), ll_null (&list));
1387 check (permutation_cnt == expected_perms (values, cnt));
1388 check_list_contents (&list, values, cnt);
1390 free_elements (cnt, elems, NULL, values);
1396 /* Tests ll_merge when no equal values are to be merged. */
1398 test_merge_no_dups (void)
1400 const int max_elems = 8;
1401 const int max_filler = 3;
1403 int merge_cnt, pattern, pfx, gap, sfx, order;
1405 for (merge_cnt = 0; merge_cnt < max_elems; merge_cnt++)
1406 for (pattern = 0; pattern <= (1 << merge_cnt); pattern++)
1407 for (pfx = 0; pfx < max_filler; pfx++)
1408 for (gap = 0; gap < max_filler; gap++)
1409 for (sfx = 0; sfx < max_filler; sfx++)
1410 for (order = 0; order < 2; order++)
1412 struct ll_list list;
1413 struct element **elems;
1417 int list_cnt = pfx + merge_cnt + gap + sfx;
1421 allocate_elements (list_cnt, &list,
1422 &elems, &elemp, &values);
1425 for (i = 0; i < pfx; i++)
1426 elems[j++]->x = 100 + i;
1428 for (i = 0; i < merge_cnt; i++)
1429 if (pattern & (1u << i))
1432 for (i = 0; i < gap; i++)
1433 elems[j++]->x = 200 + i;
1435 for (i = 0; i < merge_cnt; i++)
1436 if (!(pattern & (1u << i)))
1439 for (i = 0; i < sfx; i++)
1440 elems[j++]->x = 300 + i;
1441 check (list_cnt == j);
1444 for (i = 0; i < pfx; i++)
1445 values[j++] = 100 + i;
1447 for (i = 0; i < merge_cnt; i++)
1449 for (i = 0; i < gap; i++)
1450 values[j++] = 200 + i;
1452 for (i = 0; i < merge_cnt; i++)
1454 for (i = 0; i < sfx; i++)
1455 values[j++] = 300 + i;
1456 check (list_cnt == j);
1459 ll_merge (elemp[a0], elemp[a1], elemp[b0], elemp[b1],
1460 compare_elements, &aux_data);
1462 ll_merge (elemp[b0], elemp[b1], elemp[a0], elemp[a1],
1463 compare_elements, &aux_data);
1465 check_list_contents (&list, values, list_cnt);
1467 free_elements (list_cnt, elems, elemp, values);
1471 /* Tests ll_merge when equal values are to be merged. */
1473 test_merge_with_dups (void)
1475 const int max_elems = 8;
1477 int cnt, merge_pat, inc_pat, order;
1479 for (cnt = 0; cnt <= max_elems; cnt++)
1480 for (merge_pat = 0; merge_pat <= (1 << cnt); merge_pat++)
1481 for (inc_pat = 0; inc_pat <= (1 << cnt); inc_pat++)
1482 for (order = 0; order < 2; order++)
1484 struct ll_list list;
1485 struct element **elems;
1492 allocate_elements (cnt, &list, &elems, &elemp, &values);
1495 for (i = k = 0; i < cnt; i++)
1497 if (merge_pat & (1u << i))
1499 if (inc_pat & (1u << i))
1503 for (i = k = 0; i < cnt; i++)
1505 if (!(merge_pat & (1u << i)))
1507 if (inc_pat & (1u << i))
1514 for (i = 0; i < cnt; i++)
1519 for (i = 0; i < mid; i++)
1520 elems[i]->y = 100 + i;
1521 for (i = mid; i < cnt; i++)
1526 for (i = k = 0; i < cnt; i++)
1529 if (inc_pat & (1u << i))
1535 ll_merge (elemp[0], elemp[mid], elemp[mid], elemp[cnt],
1536 compare_elements, &aux_data);
1538 ll_merge (elemp[mid], elemp[cnt], elemp[0], elemp[mid],
1539 compare_elements, &aux_data);
1541 check_list_contents (&list, values, cnt);
1542 check (ll_is_sorted (ll_head (&list), ll_null (&list),
1543 compare_elements_x_y, &aux_data));
1545 free_elements (cnt, elems, elemp, values);
1549 /* Tests ll_sort on all permutations up to a maximum number of
1552 test_sort_exhaustive (void)
1554 const int max_elems = 8;
1557 for (cnt = 0; cnt <= max_elems; cnt++)
1559 struct ll_list list;
1560 struct element **elems;
1563 struct element **perm_elems;
1568 allocate_ascending (cnt, &list, &elems, NULL, &values);
1569 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1572 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1573 compare_elements, &aux_data))
1575 struct ll_list perm_list;
1578 extract_values (&list, perm_values, cnt);
1579 ll_init (&perm_list);
1580 for (j = 0; j < cnt; j++)
1582 perm_elems[j]->x = perm_values[j];
1583 ll_push_tail (&perm_list, &perm_elems[j]->ll);
1585 ll_sort (ll_head (&perm_list), ll_null (&perm_list),
1586 compare_elements, &aux_data);
1587 check_list_contents (&perm_list, values, cnt);
1588 check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1589 compare_elements, &aux_data));
1592 check (perm_cnt == factorial (cnt));
1594 free_elements (cnt, elems, NULL, values);
1595 free_elements (cnt, perm_elems, NULL, perm_values);
1599 /* Tests that ll_sort is stable in the presence of equal
1602 test_sort_stable (void)
1604 const int max_elems = 6;
1607 for (cnt = 0; cnt <= max_elems; cnt++)
1608 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1610 struct ll_list list;
1611 struct element **elems;
1614 struct element **perm_elems;
1620 allocate_elements (cnt, &list, &elems, NULL, &values);
1621 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1624 for (i = 0; i < cnt; i++)
1626 elems[i]->x = values[i] = j;
1627 if (inc_pat & (1 << i))
1633 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1634 compare_elements_y, &aux_data))
1636 struct ll_list perm_list;
1638 extract_values (&list, perm_values, cnt);
1639 ll_init (&perm_list);
1640 for (i = 0; i < cnt; i++)
1642 perm_elems[i]->x = perm_values[i];
1643 perm_elems[i]->y = i;
1644 ll_push_tail (&perm_list, &perm_elems[i]->ll);
1646 ll_sort (ll_head (&perm_list), ll_null (&perm_list),
1647 compare_elements, &aux_data);
1648 check_list_contents (&perm_list, values, cnt);
1649 check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1650 compare_elements_x_y, &aux_data));
1653 check (perm_cnt == factorial (cnt));
1655 free_elements (cnt, elems, NULL, values);
1656 free_elements (cnt, perm_elems, NULL, perm_values);
1660 /* Tests that ll_sort does not disturb elements outside the
1663 test_sort_subset (void)
1665 const int max_elems = 8;
1667 int cnt, r0, r1, repeat;
1669 for (cnt = 0; cnt <= max_elems; cnt++)
1670 for (repeat = 0; repeat < 100; repeat++)
1671 for (r0 = 0; r0 <= cnt; r0++)
1672 for (r1 = r0; r1 <= cnt; r1++)
1674 struct ll_list list;
1675 struct element **elems;
1679 allocate_random (cnt, &list, &elems, &elemp, &values);
1681 qsort (&values[r0], r1 - r0, sizeof *values, compare_ints_noaux);
1682 ll_sort (elemp[r0], elemp[r1], compare_elements, &aux_data);
1683 check_list_contents (&list, values, cnt);
1685 free_elements (cnt, elems, elemp, values);
1689 /* Tests that ll_sort works with large lists. */
1691 test_sort_big (void)
1693 const int max_elems = 1024;
1697 for (cnt = 0; cnt < max_elems; cnt++)
1699 struct ll_list list;
1700 struct element **elems;
1703 allocate_random (cnt, &list, &elems, NULL, &values);
1705 qsort (values, cnt, sizeof *values, compare_ints_noaux);
1706 ll_sort (ll_head (&list), ll_null (&list), compare_elements, &aux_data);
1707 check_list_contents (&list, values, cnt);
1709 free_elements (cnt, elems, NULL, values);
1713 /* Tests ll_unique. */
1717 const int max_elems = 10;
1719 int *ascending = xnmalloc (max_elems, sizeof *ascending);
1721 int cnt, inc_pat, i, j, unique_values;
1723 for (i = 0; i < max_elems; i++)
1726 for (cnt = 0; cnt < max_elems; cnt++)
1727 for (inc_pat = 0; inc_pat < (1 << cnt); inc_pat++)
1729 struct ll_list list, dups;
1730 struct element **elems;
1733 allocate_elements (cnt, &list, &elems, NULL, &values);
1735 j = unique_values = 0;
1736 for (i = 0; i < cnt; i++)
1738 unique_values = j + 1;
1739 elems[i]->x = values[i] = j;
1740 if (inc_pat & (1 << i))
1743 check_list_contents (&list, values, cnt);
1746 check (ll_unique (ll_head (&list), ll_null (&list), ll_null (&dups),
1747 compare_elements, &aux_data)
1748 == (size_t) unique_values);
1749 check_list_contents (&list, ascending, unique_values);
1751 ll_splice (ll_null (&list), ll_head (&dups), ll_null (&dups));
1752 ll_sort (ll_head (&list), ll_null (&list), compare_elements, &aux_data);
1753 check_list_contents (&list, values, cnt);
1755 free_elements (cnt, elems, NULL, values);
1761 /* Tests ll_sort_unique. */
1763 test_sort_unique (void)
1765 const int max_elems = 7;
1768 for (cnt = 0; cnt <= max_elems; cnt++)
1769 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1771 struct ll_list list;
1772 struct element **elems;
1775 struct element **perm_elems;
1784 allocate_elements (cnt, &list, &elems, NULL, &values);
1785 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1788 for (i = 0; i < cnt; i++)
1790 elems[i]->x = values[i] = j;
1792 if (inc_pat & (1 << i))
1796 unique_values = xnmalloc (unique_cnt, sizeof *unique_values);
1797 for (i = 0; i < unique_cnt; i++)
1798 unique_values[i] = i;
1801 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1802 compare_elements, &aux_data))
1804 struct ll_list perm_list;
1806 extract_values (&list, perm_values, cnt);
1807 ll_init (&perm_list);
1808 for (i = 0; i < cnt; i++)
1810 perm_elems[i]->x = perm_values[i];
1811 perm_elems[i]->y = i;
1812 ll_push_tail (&perm_list, &perm_elems[i]->ll);
1814 ll_sort_unique (ll_head (&perm_list), ll_null (&perm_list), NULL,
1815 compare_elements, &aux_data);
1816 check_list_contents (&perm_list, unique_values, unique_cnt);
1817 check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1818 compare_elements_x_y, &aux_data));
1821 check (perm_cnt == expected_perms (values, cnt));
1823 free_elements (cnt, elems, NULL, values);
1824 free_elements (cnt, perm_elems, NULL, perm_values);
1825 free (unique_values);
1829 /* Tests ll_insert_ordered. */
1831 test_insert_ordered (void)
1833 const int max_elems = 6;
1836 for (cnt = 0; cnt <= max_elems; cnt++)
1837 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1839 struct ll_list list;
1840 struct element **elems;
1843 struct element **perm_elems;
1849 allocate_elements (cnt, &list, &elems, NULL, &values);
1850 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1853 for (i = 0; i < cnt; i++)
1855 elems[i]->x = values[i] = j;
1856 if (inc_pat & (1 << i))
1862 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1863 compare_elements_y, &aux_data))
1865 struct ll_list perm_list;
1867 extract_values (&list, perm_values, cnt);
1868 ll_init (&perm_list);
1869 for (i = 0; i < cnt; i++)
1871 perm_elems[i]->x = perm_values[i];
1872 perm_elems[i]->y = i;
1873 ll_insert_ordered (ll_head (&perm_list), ll_null (&perm_list),
1875 compare_elements, &aux_data);
1877 check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1878 compare_elements_x_y, &aux_data));
1881 check (perm_cnt == factorial (cnt));
1883 free_elements (cnt, elems, NULL, values);
1884 free_elements (cnt, perm_elems, NULL, perm_values);
1888 /* Tests ll_partition. */
1890 test_partition (void)
1892 const int max_elems = 10;
1898 for (cnt = 0; cnt < max_elems; cnt++)
1899 for (r0 = 0; r0 <= cnt; r0++)
1900 for (r1 = r0; r1 <= cnt; r1++)
1901 for (pbase = 0; pbase <= (1u << (r1 - r0)); pbase++)
1903 struct ll_list list;
1904 struct element **elems;
1908 unsigned pattern = pbase << r0;
1913 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1915 /* Check that ll_find_partition works okay in every
1916 case. We use it after partitioning, too, but that
1917 only tests cases where it returns non-null. */
1918 for (i = r0; i < r1; i++)
1919 if (!(pattern & (1u << i)))
1923 if (pattern & (1u << i))
1925 part_ll = ll_find_partition (elemp[r0], elemp[r1],
1929 check (part_ll == elemp[j]);
1931 check (part_ll == NULL);
1933 /* Figure out expected results. */
1936 for (i = 0; i < r0; i++)
1938 for (i = r0; i < r1; i++)
1939 if (pattern & (1u << i))
1941 for (i = r0; i < r1; i++)
1942 if (!(pattern & (1u << i)))
1944 if (first_false == -1)
1948 if (first_false == -1)
1950 for (i = r1; i < cnt; i++)
1954 /* Partition and check for expected results. */
1955 check (ll_partition (elemp[r0], elemp[r1],
1956 pattern_pred, &pattern)
1957 == elemp[first_false]);
1958 check (ll_find_partition (elemp[r0], elemp[r1],
1959 pattern_pred, &pattern)
1960 == elemp[first_false]);
1961 check_list_contents (&list, values, cnt);
1962 check ((int) ll_count (&list) == cnt);
1964 free_elements (cnt, elems, elemp, values);
1970 /* Runs TEST_FUNCTION and prints a message about NAME. */
1972 run_test (void (*test_function) (void), const char *name)
1974 printf ("Running %s test... ", name);
1983 run_test (test_push_pop, "push/pop");
1984 run_test (test_insert_remove, "insert/remove");
1985 run_test (test_swap, "swap");
1986 run_test (test_swap_range, "swap_range");
1987 run_test (test_remove_range, "remove_range");
1988 run_test (test_remove_equal, "remove_equal");
1989 run_test (test_remove_if, "remove_if");
1990 run_test (test_moved, "moved");
1991 run_test (test_find_equal, "find_equal");
1992 run_test (test_find_if, "find_if");
1993 run_test (test_find_adjacent_equal, "find_adjacent_equal");
1994 run_test (test_count_range, "count_range");
1995 run_test (test_count_equal, "count_equal");
1996 run_test (test_count_if, "count_if");
1997 run_test (test_min_max, "min/max");
1998 run_test (test_lexicographical_compare_3way, "lexicographical_compare_3way");
1999 run_test (test_apply, "apply");
2000 run_test (test_reverse, "reverse");
2001 run_test (test_permutations_no_dups, "permutations (no dups)");
2002 run_test (test_permutations_with_dups, "permutations (with dups)");
2003 run_test (test_merge_no_dups, "merge (no dups)");
2004 run_test (test_merge_with_dups, "merge (with dups)");
2005 run_test (test_sort_exhaustive, "sort (exhaustive)");
2006 run_test (test_sort_stable, "sort (stability)");
2007 run_test (test_sort_subset, "sort (subset)");
2008 run_test (test_sort_big, "sort (big)");
2009 run_test (test_unique, "unique");
2010 run_test (test_sort_unique, "sort_unique");
2011 run_test (test_insert_ordered, "insert_ordered");
2012 run_test (test_partition, "partition");
2019 compile-command: "gcc -Wall -Wstrict-prototypes -Wmissing-prototypes ll.c ll-test.c -o ll-test -g"