1 /* PSPP - computes sample statistics.
2 Copyright (C) 2006 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License as
6 published by the Free Software Foundation; either version 2 of the
7 License, or (at your option) any later version.
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 /* This is a test program for the ll_* routines defined in
20 ll.c. This test program aims to be as comprehensive as
21 possible. "gcov -b" should report 100% coverage of lines and
22 branches in the ll_* routines. "valgrind --leak-check=yes
23 --show-reachable=yes" should give a clean report.
25 This test program depends only on ll.c and the standard C
28 See llx-test.c for a similar program for the llx_*
31 #include <libpspp/ll.h>
37 /* Support preliminaries. */
38 #if __GNUC__ >= 2 && !defined UNUSED
39 #define UNUSED __attribute__ ((unused))
44 /* Currently running test. */
45 static const char *test_name;
47 /* Exit with a failure code.
48 (Place a breakpoint on this function while debugging.) */
55 /* If OK is not true, prints a message about failure on the
56 current source file and the given LINE and terminates. */
58 check_func (bool ok, int line)
62 printf ("Check failed in %s test at %s, line %d\n",
63 test_name, __FILE__, line);
68 /* Verifies that EXPR evaluates to true.
69 If not, prints a message citing the calling line number and
71 #define check(EXPR) check_func ((EXPR), __LINE__)
73 /* Prints a message about memory exhaustion and exits with a
78 printf ("virtual memory exhausted\n");
82 /* Allocates and returns N bytes of memory. */
98 /* Allocates and returns N * M bytes of memory. */
100 xnmalloc (size_t n, size_t m)
102 if ((size_t) -1 / m <= n)
104 return xmalloc (n * m);
107 /* List type and support routines. */
109 /* Test data element. */
112 struct ll ll; /* Embedded list element. */
113 int x; /* Primary value. */
114 int y; /* Secondary value. */
119 /* Returns the `struct element' that LL is embedded within. */
120 static struct element *
121 ll_to_element (const struct ll *ll)
123 return ll_data (ll, struct element, ll);
126 /* Prints the elements in LIST. */
128 print_list (struct ll_list *list)
133 for (x = ll_head (list); x != ll_null (list); x = ll_next (x))
135 struct element *e = ll_to_element (x);
136 printf (" %d", e->x);
141 /* Prints the value returned by PREDICATE given auxiliary data
142 AUX for each element in LIST. */
144 print_pred (struct ll_list *list,
145 ll_predicate_func *predicate, void *aux UNUSED)
150 for (x = ll_head (list); x != ll_null (list); x = ll_next (x))
151 printf (" %d", predicate (x, aux));
155 /* Prints the CNT numbers in VALUES. */
157 print_array (int values[], size_t cnt)
162 for (i = 0; i < cnt; i++)
163 printf (" %d", values[i]);
167 /* Compares the `x' values in A and B and returns a strcmp-type
168 return value. Verifies that AUX points to aux_data. */
170 compare_elements (const struct ll *a_, const struct ll *b_, void *aux)
172 const struct element *a = ll_to_element (a_);
173 const struct element *b = ll_to_element (b_);
175 check (aux == &aux_data);
176 return a->x < b->x ? -1 : a->x > b->x;
179 /* Compares the `x' and `y' values in A and B and returns a
180 strcmp-type return value. Verifies that AUX points to
183 compare_elements_x_y (const struct ll *a_, const struct ll *b_, void *aux)
185 const struct element *a = ll_to_element (a_);
186 const struct element *b = ll_to_element (b_);
188 check (aux == &aux_data);
190 return a->x < b->x ? -1 : 1;
191 else if (a->y != b->y)
192 return a->y < b->y ? -1 : 1;
197 /* Compares the `y' values in A and B and returns a strcmp-type
198 return value. Verifies that AUX points to aux_data. */
200 compare_elements_y (const struct ll *a_, const struct ll *b_, void *aux)
202 const struct element *a = ll_to_element (a_);
203 const struct element *b = ll_to_element (b_);
205 check (aux == &aux_data);
206 return a->y < b->y ? -1 : a->y > b->y;
209 /* Returns true if the bit in *PATTERN indicated by `x in
210 *ELEMENT is set, false otherwise. */
212 pattern_pred (const struct ll *element_, void *pattern_)
214 const struct element *element = ll_to_element (element_);
215 unsigned int *pattern = pattern_;
217 return (*pattern & (1u << element->x)) != 0;
220 /* Allocates N elements in *ELEMS.
221 Adds the elements to LIST, if it is nonnull.
222 Puts pointers to the elements' list elements in *ELEMP,
223 followed by a pointer to the list null element, if ELEMP is
225 Allocates space for N values in *VALUES, if VALUES is
228 allocate_elements (size_t n,
229 struct ll_list *list,
230 struct element ***elems,
239 *elems = xnmalloc (n, sizeof **elems);
240 for (i = 0; i < n; i++)
242 (*elems)[i] = xmalloc (sizeof ***elems);
244 ll_push_tail (list, &(*elems)[i]->ll);
249 *elemp = xnmalloc (n + 1, sizeof *elemp);
250 for (i = 0; i < n; i++)
251 (*elemp)[i] = &(*elems)[i]->ll;
252 (*elemp)[n] = ll_null (list);
256 *values = xnmalloc (n, sizeof *values);
259 /* Copies the CNT values of `x' from LIST into VALUES[]. */
261 extract_values (struct ll_list *list, int values[], size_t cnt)
265 check (ll_count (list) == cnt);
266 for (x = ll_head (list); x != ll_null (list); x = ll_next (x))
268 struct element *e = ll_to_element (x);
273 /* As allocate_elements, but sets ascending values, starting
274 from 0, in `x' values in *ELEMS and in *VALUES (if
277 allocate_ascending (size_t n,
278 struct ll_list *list,
279 struct element ***elems,
285 allocate_elements (n, list, elems, elemp, values);
287 for (i = 0; i < n; i++)
290 extract_values (list, *values, n);
293 /* As allocate_elements, but sets binary values extracted from
294 successive bits in PATTERN in `x' values in *ELEMS and in
295 *VALUES (if nonnull). */
297 allocate_pattern (size_t n,
299 struct ll_list *list,
300 struct element ***elems,
306 allocate_elements (n, list, elems, elemp, values);
308 for (i = 0; i < n; i++)
309 (*elems)[i]->x = (pattern & (1 << i)) != 0;
311 extract_values (list, *values, n);
314 /* Randomly shuffles the CNT elements in ARRAY, each of which is
315 SIZE bytes in size. */
317 random_shuffle (void *array_, size_t cnt, size_t size)
319 char *array = array_;
320 char *tmp = xmalloc (size);
323 for (i = 0; i < cnt; i++)
325 size_t j = rand () % (cnt - i) + i;
328 memcpy (tmp, array + j * size, size);
329 memcpy (array + j * size, array + i * size, size);
330 memcpy (array + i * size, tmp, size);
337 /* As allocate_ascending, but orders the values randomly. */
339 allocate_random (size_t n,
340 struct ll_list *list,
341 struct element ***elems,
347 allocate_elements (n, list, elems, elemp, values);
349 for (i = 0; i < n; i++)
351 random_shuffle (*elems, n, sizeof **elems);
353 extract_values (list, *values, n);
356 /* Frees the N elements of ELEMS, ELEMP, and VALUES. */
358 free_elements (size_t n,
359 struct element **elems,
365 for (i = 0; i < n; i++)
372 /* Compares A and B and returns a strcmp-type return value. */
374 compare_ints (const void *a_, const void *b_, void *aux UNUSED)
379 return *a < *b ? -1 : *a > *b;
382 /* Compares A and B and returns a strcmp-type return value. */
384 compare_ints_noaux (const void *a_, const void *b_)
389 return *a < *b ? -1 : *a > *b;
392 /* Checks that LIST contains the CNT values in ELEMENTS. */
394 check_list_contents (struct ll_list *list, int elements[], size_t cnt)
399 check ((cnt == 0) == ll_is_empty (list));
401 /* Iterate in forward order. */
402 for (ll = ll_head (list), i = 0; i < cnt; ll = ll_next (ll), i++)
404 struct element *e = ll_to_element (ll);
405 check (elements[i] == e->x);
406 check (ll != ll_null (list));
408 check (ll == ll_null (list));
410 /* Iterate in reverse order. */
411 for (ll = ll_tail (list), i = 0; i < cnt; ll = ll_prev (ll), i++)
413 struct element *e = ll_to_element (ll);
414 check (elements[cnt - i - 1] == e->x);
415 check (ll != ll_null (list));
417 check (ll == ll_null (list));
419 check (ll_count (list) == cnt);
422 /* Lexicographically compares ARRAY1, which contains COUNT1
423 elements of SIZE bytes each, to ARRAY2, which contains COUNT2
424 elements of SIZE bytes, according to COMPARE. Returns a
425 strcmp-type result. AUX is passed to COMPARE as auxiliary
428 lexicographical_compare_3way (const void *array1, size_t count1,
429 const void *array2, size_t count2,
431 int (*compare) (const void *, const void *,
435 const char *first1 = array1;
436 const char *first2 = array2;
437 size_t min_count = count1 < count2 ? count1 : count2;
439 while (min_count > 0)
441 int cmp = compare (first1, first2, aux);
450 return count1 < count2 ? -1 : count1 > count2;
455 /* Tests list push and pop operations. */
459 const int max_elems = 1024;
462 struct element **elems;
467 allocate_elements (max_elems, NULL, &elems, NULL, &values);
471 check_list_contents (&list, NULL, 0);
472 for (i = 0; i < max_elems; i++)
474 values[i] = elems[i]->x = i;
475 ll_push_tail (&list, &elems[i]->ll);
476 check_list_contents (&list, values, i + 1);
479 /* Remove from tail. */
480 for (i = 0; i < max_elems; i++)
482 struct element *e = ll_to_element (ll_pop_tail (&list));
483 check (e->x == max_elems - i - 1);
484 check_list_contents (&list, values, max_elems - i - 1);
488 check_list_contents (&list, NULL, 0);
489 for (i = 0; i < max_elems; i++)
491 values[max_elems - i - 1] = elems[i]->x = max_elems - i - 1;
492 ll_push_head (&list, &elems[i]->ll);
493 check_list_contents (&list, &values[max_elems - i - 1], i + 1);
496 /* Remove from start. */
497 for (i = 0; i < max_elems; i++)
499 struct element *e = ll_to_element (ll_pop_head (&list));
500 check (e->x == (int) i);
501 check_list_contents (&list, &values[i + 1], max_elems - i - 1);
504 free_elements (max_elems, elems, NULL, values);
507 /* Tests insertion and removal at arbitrary positions. */
509 test_insert_remove (void)
511 const int max_elems = 16;
514 for (cnt = 0; cnt < max_elems; cnt++)
516 struct element **elems;
518 int *values = xnmalloc (cnt + 1, sizeof *values);
521 struct element extra;
524 allocate_ascending (cnt, &list, &elems, &elemp, NULL);
526 for (pos = 0; pos <= cnt; pos++)
530 ll_insert (elemp[pos], &extra.ll);
533 for (i = 0; i < pos; i++)
538 check_list_contents (&list, values, cnt + 1);
540 ll_remove (&extra.ll);
542 check_list_contents (&list, values, cnt);
544 free_elements (cnt, elems, elemp, values);
548 /* Tests swapping individual elements. */
552 const int max_elems = 8;
555 for (cnt = 0; cnt <= max_elems; cnt++)
558 struct element **elems;
563 allocate_ascending (cnt, &list, &elems, NULL, &values);
564 check_list_contents (&list, values, cnt);
566 for (i = 0; i < cnt; i++)
567 for (j = 0; j < cnt; j++)
568 for (k = 0; k < 2; k++)
572 ll_swap (&elems[i]->ll, &elems[j]->ll);
574 values[i] = values[j];
576 check_list_contents (&list, values, cnt);
579 free_elements (cnt, elems, NULL, values);
583 /* Tests swapping ranges of list elements. */
585 test_swap_range (void)
587 const int max_elems = 8;
588 int cnt, a0, a1, b0, b1, r;
590 for (cnt = 0; cnt <= max_elems; cnt++)
591 for (a0 = 0; a0 <= cnt; a0++)
592 for (a1 = a0; a1 <= cnt; a1++)
593 for (b0 = a1; b0 <= cnt; b0++)
594 for (b1 = b0; b1 <= cnt; b1++)
595 for (r = 0; r < 2; r++)
598 struct element **elems;
604 allocate_ascending (cnt, &list, &elems, &elemp, &values);
605 check_list_contents (&list, values, cnt);
608 for (i = 0; i < a0; i++)
610 for (i = b0; i < b1; i++)
612 for (i = a1; i < b0; i++)
614 for (i = a0; i < a1; i++)
616 for (i = b1; i < cnt; i++)
621 ll_swap_range (elemp[a0], elemp[a1], elemp[b0], elemp[b1]);
623 ll_swap_range (elemp[b0], elemp[b1], elemp[a0], elemp[a1]);
624 check_list_contents (&list, values, cnt);
626 free_elements (cnt, elems, elemp, values);
630 /* Tests removing ranges of list elements. */
632 test_remove_range (void)
634 const int max_elems = 8;
638 for (cnt = 0; cnt <= max_elems; cnt++)
639 for (r0 = 0; r0 <= cnt; r0++)
640 for (r1 = r0; r1 <= cnt; r1++)
643 struct element **elems;
649 allocate_ascending (cnt, &list, &elems, &elemp, &values);
650 check_list_contents (&list, values, cnt);
653 for (i = 0; i < r0; i++)
655 for (i = r1; i < cnt; i++)
658 ll_remove_range (elemp[r0], elemp[r1]);
659 check_list_contents (&list, values, j);
661 free_elements (cnt, elems, elemp, values);
665 /* Tests ll_remove_equal. */
667 test_remove_equal (void)
669 const int max_elems = 8;
671 int cnt, r0, r1, eq_pat;
673 for (cnt = 0; cnt <= max_elems; cnt++)
674 for (r0 = 0; r0 <= cnt; r0++)
675 for (r1 = r0; r1 <= cnt; r1++)
676 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
679 struct element **elems;
683 struct element to_remove;
687 allocate_elements (cnt, &list, &elems, &elemp, &values);
690 for (i = 0; i < cnt; i++)
692 int x = eq_pat & (1 << i) ? -1 : i;
693 bool delete = x == -1 && r0 <= i && i < r1;
696 values[remaining++] = x;
700 check ((int) ll_remove_equal (elemp[r0], elemp[r1], &to_remove.ll,
701 compare_elements, &aux_data)
703 check_list_contents (&list, values, remaining);
705 free_elements (cnt, elems, elemp, values);
709 /* Tests ll_remove_if. */
711 test_remove_if (void)
713 const int max_elems = 8;
715 int cnt, r0, r1, pattern;
717 for (cnt = 0; cnt <= max_elems; cnt++)
718 for (r0 = 0; r0 <= cnt; r0++)
719 for (r1 = r0; r1 <= cnt; r1++)
720 for (pattern = 0; pattern <= 1 << cnt; pattern++)
723 struct element **elems;
730 allocate_elements (cnt, &list, &elems, &elemp, &values);
733 for (i = 0; i < cnt; i++)
735 bool delete = (pattern & (1 << i)) && r0 <= i && i < r1;
738 values[remaining++] = i;
741 check ((int) ll_remove_if (elemp[r0], elemp[r1],
742 pattern_pred, &pattern)
744 check_list_contents (&list, values, remaining);
746 free_elements (cnt, elems, elemp, values);
750 /* Tests ll_moved. */
754 const int max_elems = 8;
758 for (cnt = 0; cnt <= max_elems; cnt++)
761 struct element **elems;
762 struct element **new_elems;
767 allocate_ascending (cnt, &list, &elems, NULL, &values);
768 allocate_elements (cnt, NULL, &new_elems, NULL, NULL);
769 check_list_contents (&list, values, cnt);
771 for (i = 0; i < cnt; i++)
773 *new_elems[i] = *elems[i];
774 ll_moved (&new_elems[i]->ll);
775 check_list_contents (&list, values, cnt);
778 free_elements (cnt, elems, NULL, values);
779 free_elements (cnt, new_elems, NULL, NULL);
783 /* Tests, via HELPER, a function that looks at list elements
784 equal to some specified element. */
786 test_examine_equal_range (void (*helper) (int r0, int r1, int eq_pat,
790 const int max_elems = 8;
792 int cnt, r0, r1, eq_pat;
794 for (cnt = 0; cnt <= max_elems; cnt++)
795 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
798 struct element **elems;
802 struct element to_find;
806 allocate_ascending (cnt, &list, &elems, &elemp, &values);
808 for (i = 0; i < cnt; i++)
809 if (eq_pat & (1 << i))
810 values[i] = elems[i]->x = -1;
813 for (r0 = 0; r0 <= cnt; r0++)
814 for (r1 = r0; r1 <= cnt; r1++)
815 helper (r0, r1, eq_pat, &to_find.ll, elemp);
817 check_list_contents (&list, values, cnt);
819 free_elements (cnt, elems, elemp, values);
823 /* Tests, via HELPER, a function that looks at list elements for
824 which a given predicate returns true. */
826 test_examine_if_range (void (*helper) (int r0, int r1, int eq_pat,
829 const int max_elems = 8;
831 int cnt, r0, r1, eq_pat;
833 for (cnt = 0; cnt <= max_elems; cnt++)
834 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
837 struct element **elems;
841 allocate_ascending (cnt, &list, &elems, &elemp, &values);
843 for (r0 = 0; r0 <= cnt; r0++)
844 for (r1 = r0; r1 <= cnt; r1++)
845 helper (r0, r1, eq_pat, elemp);
847 check_list_contents (&list, values, cnt);
849 free_elements (cnt, elems, elemp, values);
853 /* Helper function for testing ll_find_equal. */
855 test_find_equal_helper (int r0, int r1, int eq_pat,
856 struct ll *to_find, struct ll **elemp)
861 match = ll_find_equal (elemp[r0], elemp[r1], to_find,
862 compare_elements, &aux_data);
863 for (i = r0; i < r1; i++)
864 if (eq_pat & (1 << i))
867 check (match == elemp[i]);
870 /* Tests ll_find_equal. */
872 test_find_equal (void)
874 test_examine_equal_range (test_find_equal_helper);
877 /* Helper function for testing ll_find_if. */
879 test_find_if_helper (int r0, int r1, int eq_pat, struct ll **elemp)
881 struct ll *match = ll_find_if (elemp[r0], elemp[r1],
882 pattern_pred, &eq_pat);
885 for (i = r0; i < r1; i++)
886 if (eq_pat & (1 << i))
889 check (match == elemp[i]);
892 /* Tests ll_find_if. */
896 test_examine_if_range (test_find_if_helper);
899 /* Tests ll_find_adjacent_equal. */
901 test_find_adjacent_equal (void)
903 const int max_elems = 8;
907 for (cnt = 0; cnt <= max_elems; cnt++)
908 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
911 struct element **elems;
918 allocate_ascending (cnt, &list, &elems, &elemp, &values);
921 for (i = 0; i < cnt - 1; i++)
924 if (eq_pat & (1 << i))
926 values[i] = elems[i]->x = match;
927 values[i + 1] = elems[i + 1]->x = match;
933 for (i = 0; i <= cnt; i++)
935 struct ll *ll1 = ll_find_adjacent_equal (elemp[i], ll_null (&list),
941 ll2 = ll_null (&list);
942 for (j = i; j < cnt - 1; j++)
943 if (eq_pat & (1 << j))
950 check_list_contents (&list, values, cnt);
952 free_elements (cnt, elems, elemp, values);
956 /* Helper function for testing ll_count_range. */
958 test_count_range_helper (int r0, int r1, int eq_pat UNUSED, struct ll **elemp)
960 check ((int) ll_count_range (elemp[r0], elemp[r1]) == r1 - r0);
963 /* Tests ll_count_range. */
965 test_count_range (void)
967 test_examine_if_range (test_count_range_helper);
970 /* Helper function for testing ll_count_equal. */
972 test_count_equal_helper (int r0, int r1, int eq_pat,
973 struct ll *to_find, struct ll **elemp)
978 count1 = ll_count_equal (elemp[r0], elemp[r1], to_find,
979 compare_elements, &aux_data);
981 for (i = r0; i < r1; i++)
982 if (eq_pat & (1 << i))
985 check (count1 == count2);
988 /* Tests ll_count_equal. */
990 test_count_equal (void)
992 test_examine_equal_range (test_count_equal_helper);
995 /* Helper function for testing ll_count_if. */
997 test_count_if_helper (int r0, int r1, int eq_pat, struct ll **elemp)
1003 count1 = ll_count_if (elemp[r0], elemp[r1], pattern_pred, &eq_pat);
1006 for (i = r0; i < r1; i++)
1007 if (eq_pat & (1 << i))
1010 check (count1 == count2);
1013 /* Tests ll_count_if. */
1015 test_count_if (void)
1017 test_examine_if_range (test_count_if_helper);
1022 factorial (unsigned int n)
1024 unsigned int value = 1;
1030 /* Returns the number of permutations of the CNT values in
1031 VALUES. If VALUES contains duplicates, they must be
1034 expected_perms (int *values, size_t cnt)
1037 unsigned int perm_cnt;
1039 perm_cnt = factorial (cnt);
1040 for (i = 0; i < cnt; i = j)
1042 for (j = i + 1; j < cnt; j++)
1043 if (values[i] != values[j])
1045 perm_cnt /= factorial (j - i);
1050 /* Tests ll_min and ll_max. */
1054 const int max_elems = 6;
1057 for (cnt = 0; cnt <= max_elems; cnt++)
1059 struct ll_list list;
1060 struct element **elems;
1063 int *new_values = xnmalloc (cnt, sizeof *values);
1067 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1070 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1071 compare_elements, &aux_data))
1077 for (i = 0, x = ll_head (&list); x != ll_null (&list);
1078 x = ll_next (x), i++)
1080 struct element *e = ll_to_element (x);
1082 new_values[i] = e->x;
1084 for (r0 = 0; r0 <= cnt; r0++)
1085 for (r1 = r0; r1 <= cnt; r1++)
1087 struct ll *min = ll_min (elemp[r0], elemp[r1],
1088 compare_elements, &aux_data);
1089 struct ll *max = ll_max (elemp[r0], elemp[r1],
1090 compare_elements, &aux_data);
1093 check (min == elemp[r1]);
1094 check (max == elemp[r1]);
1098 int min_int, max_int;
1101 min_int = max_int = new_values[r0];
1102 for (i = r0; i < r1; i++)
1104 int value = new_values[i];
1105 if (value < min_int)
1107 if (value > max_int)
1110 check (min != elemp[r1]
1111 && ll_to_element (min)->x == min_int);
1112 check (max != elemp[r1]
1113 && ll_to_element (max)->x == max_int);
1118 check (perm_cnt == factorial (cnt));
1119 check_list_contents (&list, values, cnt);
1121 free_elements (cnt, elems, elemp, values);
1126 /* Tests ll_lexicographical_compare_3way. */
1128 test_lexicographical_compare_3way (void)
1130 const int max_elems = 4;
1132 int cnt_a, pat_a, cnt_b, pat_b;
1134 for (cnt_a = 0; cnt_a <= max_elems; cnt_a++)
1135 for (pat_a = 0; pat_a <= 1 << cnt_a; pat_a++)
1136 for (cnt_b = 0; cnt_b <= max_elems; cnt_b++)
1137 for (pat_b = 0; pat_b <= 1 << cnt_b; pat_b++)
1139 struct ll_list list_a, list_b;
1140 struct element **elems_a, **elems_b;
1141 struct ll **elemp_a, **elemp_b;
1142 int *values_a, *values_b;
1146 allocate_pattern (cnt_a, pat_a,
1147 &list_a, &elems_a, &elemp_a, &values_a);
1148 allocate_pattern (cnt_b, pat_b,
1149 &list_b, &elems_b, &elemp_b, &values_b);
1151 for (a0 = 0; a0 <= cnt_a; a0++)
1152 for (a1 = a0; a1 <= cnt_a; a1++)
1153 for (b0 = 0; b0 <= cnt_b; b0++)
1154 for (b1 = b0; b1 <= cnt_b; b1++)
1156 int a_ordering = lexicographical_compare_3way (
1157 values_a + a0, a1 - a0,
1158 values_b + b0, b1 - b0,
1160 compare_ints, NULL);
1162 int b_ordering = ll_lexicographical_compare_3way (
1163 elemp_a[a0], elemp_a[a1],
1164 elemp_b[b0], elemp_b[b1],
1165 compare_elements, &aux_data);
1167 check (a_ordering == b_ordering);
1170 free_elements (cnt_a, elems_a, elemp_a, values_a);
1171 free_elements (cnt_b, elems_b, elemp_b, values_b);
1175 /* Appends the `x' value in element E to the array pointed to by
1176 NEXT_OUTPUT, and advances NEXT_OUTPUT to the next position. */
1178 apply_func (struct ll *e_, void *next_output_)
1180 struct element *e = ll_to_element (e_);
1181 int **next_output = next_output_;
1183 *(*next_output)++ = e->x;
1186 /* Tests ll_apply. */
1190 const int max_elems = 8;
1194 for (cnt = 0; cnt <= max_elems; cnt++)
1195 for (r0 = 0; r0 <= cnt; r0++)
1196 for (r1 = r0; r1 <= cnt; r1++)
1198 struct ll_list list;
1199 struct element **elems;
1208 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1209 check_list_contents (&list, values, cnt);
1211 output = next_output = xnmalloc (cnt, sizeof *output);
1212 ll_apply (elemp[r0], elemp[r1], apply_func, &next_output);
1213 check_list_contents (&list, values, cnt);
1215 check (r1 - r0 == next_output - output);
1216 for (i = 0; i < r1 - r0; i++)
1217 check (output[i] == r0 + i);
1219 free_elements (cnt, elems, elemp, values);
1224 /* Tests ll_reverse. */
1228 const int max_elems = 8;
1232 for (cnt = 0; cnt <= max_elems; cnt++)
1233 for (r0 = 0; r0 <= cnt; r0++)
1234 for (r1 = r0; r1 <= cnt; r1++)
1236 struct ll_list list;
1237 struct element **elems;
1243 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1244 check_list_contents (&list, values, cnt);
1247 for (i = 0; i < r0; i++)
1249 for (i = r1 - 1; i >= r0; i--)
1251 for (i = r1; i < cnt; i++)
1254 ll_reverse (elemp[r0], elemp[r1]);
1255 check_list_contents (&list, values, cnt);
1257 free_elements (cnt, elems, elemp, values);
1261 /* Tests ll_next_permutation and ll_prev_permutation when the
1262 permuted values have no duplicates. */
1264 test_permutations_no_dups (void)
1266 const int max_elems = 8;
1269 for (cnt = 0; cnt <= max_elems; cnt++)
1271 struct ll_list list;
1272 struct element **elems;
1274 int *old_values = xnmalloc (cnt, sizeof *values);
1275 int *new_values = xnmalloc (cnt, sizeof *values);
1279 allocate_ascending (cnt, &list, &elems, NULL, &values);
1282 extract_values (&list, old_values, cnt);
1283 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1284 compare_elements, &aux_data))
1286 extract_values (&list, new_values, cnt);
1287 check (lexicographical_compare_3way (new_values, cnt,
1290 compare_ints, NULL) > 0);
1291 memcpy (old_values, new_values, (cnt) * sizeof *old_values);
1294 check (perm_cnt == factorial (cnt));
1295 check_list_contents (&list, values, cnt);
1298 ll_reverse (ll_head (&list), ll_null (&list));
1299 extract_values (&list, old_values, cnt);
1300 while (ll_prev_permutation (ll_head (&list), ll_null (&list),
1301 compare_elements, &aux_data))
1303 extract_values (&list, new_values, cnt);
1304 check (lexicographical_compare_3way (new_values, cnt,
1307 compare_ints, NULL) < 0);
1308 memcpy (old_values, new_values, (cnt) * sizeof *old_values);
1311 check (perm_cnt == factorial (cnt));
1312 ll_reverse (ll_head (&list), ll_null (&list));
1313 check_list_contents (&list, values, cnt);
1315 free_elements (cnt, elems, NULL, values);
1321 /* Tests ll_next_permutation and ll_prev_permutation when the
1322 permuted values contain duplicates. */
1324 test_permutations_with_dups (void)
1326 const int max_elems = 8;
1327 const int max_dup = 3;
1328 const int repetitions = 1024;
1332 for (repeat = 0; repeat < repetitions; repeat++)
1333 for (cnt = 0; cnt < max_elems; cnt++)
1335 struct ll_list list;
1336 struct element **elems;
1338 int *old_values = xnmalloc (max_elems, sizeof *values);
1339 int *new_values = xnmalloc (max_elems, sizeof *values);
1341 unsigned int permutation_cnt;
1345 allocate_elements (cnt, &list, &elems, NULL, &values);
1350 int max = left < max_dup ? left : max_dup;
1351 int n = rand () % max + 1;
1354 int idx = cnt - left--;
1355 values[idx] = elems[idx]->x = value;
1360 permutation_cnt = 1;
1361 extract_values (&list, old_values, cnt);
1362 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1363 compare_elements, &aux_data))
1365 extract_values (&list, new_values, cnt);
1366 check (lexicographical_compare_3way (new_values, cnt,
1369 compare_ints, NULL) > 0);
1370 memcpy (old_values, new_values, cnt * sizeof *old_values);
1373 check (permutation_cnt == expected_perms (values, cnt));
1374 check_list_contents (&list, values, cnt);
1376 permutation_cnt = 1;
1377 ll_reverse (ll_head (&list), ll_null (&list));
1378 extract_values (&list, old_values, cnt);
1379 while (ll_prev_permutation (ll_head (&list), ll_null (&list),
1380 compare_elements, &aux_data))
1382 extract_values (&list, new_values, cnt);
1383 check (lexicographical_compare_3way (new_values, cnt,
1386 compare_ints, NULL) < 0);
1389 ll_reverse (ll_head (&list), ll_null (&list));
1390 check (permutation_cnt == expected_perms (values, cnt));
1391 check_list_contents (&list, values, cnt);
1393 free_elements (cnt, elems, NULL, values);
1399 /* Tests ll_merge when no equal values are to be merged. */
1401 test_merge_no_dups (void)
1403 const int max_elems = 8;
1404 const int max_filler = 3;
1406 int merge_cnt, pattern, pfx, gap, sfx, order;
1408 for (merge_cnt = 0; merge_cnt < max_elems; merge_cnt++)
1409 for (pattern = 0; pattern <= (1 << merge_cnt); pattern++)
1410 for (pfx = 0; pfx < max_filler; pfx++)
1411 for (gap = 0; gap < max_filler; gap++)
1412 for (sfx = 0; sfx < max_filler; sfx++)
1413 for (order = 0; order < 2; order++)
1415 struct ll_list list;
1416 struct element **elems;
1420 int list_cnt = pfx + merge_cnt + gap + sfx;
1424 allocate_elements (list_cnt, &list,
1425 &elems, &elemp, &values);
1428 for (i = 0; i < pfx; i++)
1429 elems[j++]->x = 100 + i;
1431 for (i = 0; i < merge_cnt; i++)
1432 if (pattern & (1u << i))
1435 for (i = 0; i < gap; i++)
1436 elems[j++]->x = 200 + i;
1438 for (i = 0; i < merge_cnt; i++)
1439 if (!(pattern & (1u << i)))
1442 for (i = 0; i < sfx; i++)
1443 elems[j++]->x = 300 + i;
1444 check (list_cnt == j);
1447 for (i = 0; i < pfx; i++)
1448 values[j++] = 100 + i;
1450 for (i = 0; i < merge_cnt; i++)
1452 for (i = 0; i < gap; i++)
1453 values[j++] = 200 + i;
1455 for (i = 0; i < merge_cnt; i++)
1457 for (i = 0; i < sfx; i++)
1458 values[j++] = 300 + i;
1459 check (list_cnt == j);
1462 ll_merge (elemp[a0], elemp[a1], elemp[b0], elemp[b1],
1463 compare_elements, &aux_data);
1465 ll_merge (elemp[b0], elemp[b1], elemp[a0], elemp[a1],
1466 compare_elements, &aux_data);
1468 check_list_contents (&list, values, list_cnt);
1470 free_elements (list_cnt, elems, elemp, values);
1474 /* Tests ll_merge when equal values are to be merged. */
1476 test_merge_with_dups (void)
1478 const int max_elems = 8;
1480 int cnt, merge_pat, inc_pat, order;
1482 for (cnt = 0; cnt <= max_elems; cnt++)
1483 for (merge_pat = 0; merge_pat <= (1 << cnt); merge_pat++)
1484 for (inc_pat = 0; inc_pat <= (1 << cnt); inc_pat++)
1485 for (order = 0; order < 2; order++)
1487 struct ll_list list;
1488 struct element **elems;
1495 allocate_elements (cnt, &list, &elems, &elemp, &values);
1498 for (i = k = 0; i < cnt; i++)
1500 if (merge_pat & (1u << i))
1502 if (inc_pat & (1u << i))
1506 for (i = k = 0; i < cnt; i++)
1508 if (!(merge_pat & (1u << i)))
1510 if (inc_pat & (1u << i))
1517 for (i = 0; i < cnt; i++)
1522 for (i = 0; i < mid; i++)
1523 elems[i]->y = 100 + i;
1524 for (i = mid; i < cnt; i++)
1529 for (i = k = 0; i < cnt; i++)
1532 if (inc_pat & (1u << i))
1538 ll_merge (elemp[0], elemp[mid], elemp[mid], elemp[cnt],
1539 compare_elements, &aux_data);
1541 ll_merge (elemp[mid], elemp[cnt], elemp[0], elemp[mid],
1542 compare_elements, &aux_data);
1544 check_list_contents (&list, values, cnt);
1545 check (ll_is_sorted (ll_head (&list), ll_null (&list),
1546 compare_elements_x_y, &aux_data));
1548 free_elements (cnt, elems, elemp, values);
1552 /* Tests ll_sort on all permutations up to a maximum number of
1555 test_sort_exhaustive (void)
1557 const int max_elems = 8;
1560 for (cnt = 0; cnt <= max_elems; cnt++)
1562 struct ll_list list;
1563 struct element **elems;
1566 struct element **perm_elems;
1571 allocate_ascending (cnt, &list, &elems, NULL, &values);
1572 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1575 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1576 compare_elements, &aux_data))
1578 struct ll_list perm_list;
1581 extract_values (&list, perm_values, cnt);
1582 ll_init (&perm_list);
1583 for (j = 0; j < cnt; j++)
1585 perm_elems[j]->x = perm_values[j];
1586 ll_push_tail (&perm_list, &perm_elems[j]->ll);
1588 ll_sort (ll_head (&perm_list), ll_null (&perm_list),
1589 compare_elements, &aux_data);
1590 check_list_contents (&perm_list, values, cnt);
1591 check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1592 compare_elements, &aux_data));
1595 check (perm_cnt == factorial (cnt));
1597 free_elements (cnt, elems, NULL, values);
1598 free_elements (cnt, perm_elems, NULL, perm_values);
1602 /* Tests that ll_sort is stable in the presence of equal
1605 test_sort_stable (void)
1607 const int max_elems = 6;
1610 for (cnt = 0; cnt <= max_elems; cnt++)
1611 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1613 struct ll_list list;
1614 struct element **elems;
1617 struct element **perm_elems;
1623 allocate_elements (cnt, &list, &elems, NULL, &values);
1624 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1627 for (i = 0; i < cnt; i++)
1629 elems[i]->x = values[i] = j;
1630 if (inc_pat & (1 << i))
1636 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1637 compare_elements_y, &aux_data))
1639 struct ll_list perm_list;
1641 extract_values (&list, perm_values, cnt);
1642 ll_init (&perm_list);
1643 for (i = 0; i < cnt; i++)
1645 perm_elems[i]->x = perm_values[i];
1646 perm_elems[i]->y = i;
1647 ll_push_tail (&perm_list, &perm_elems[i]->ll);
1649 ll_sort (ll_head (&perm_list), ll_null (&perm_list),
1650 compare_elements, &aux_data);
1651 check_list_contents (&perm_list, values, cnt);
1652 check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1653 compare_elements_x_y, &aux_data));
1656 check (perm_cnt == factorial (cnt));
1658 free_elements (cnt, elems, NULL, values);
1659 free_elements (cnt, perm_elems, NULL, perm_values);
1663 /* Tests that ll_sort does not disturb elements outside the
1666 test_sort_subset (void)
1668 const int max_elems = 8;
1670 int cnt, r0, r1, repeat;
1672 for (cnt = 0; cnt <= max_elems; cnt++)
1673 for (repeat = 0; repeat < 100; repeat++)
1674 for (r0 = 0; r0 <= cnt; r0++)
1675 for (r1 = r0; r1 <= cnt; r1++)
1677 struct ll_list list;
1678 struct element **elems;
1682 allocate_random (cnt, &list, &elems, &elemp, &values);
1684 qsort (&values[r0], r1 - r0, sizeof *values, compare_ints_noaux);
1685 ll_sort (elemp[r0], elemp[r1], compare_elements, &aux_data);
1686 check_list_contents (&list, values, cnt);
1688 free_elements (cnt, elems, elemp, values);
1692 /* Tests that ll_sort works with large lists. */
1694 test_sort_big (void)
1696 const int max_elems = 1024;
1700 for (cnt = 0; cnt < max_elems; cnt++)
1702 struct ll_list list;
1703 struct element **elems;
1706 allocate_random (cnt, &list, &elems, NULL, &values);
1708 qsort (values, cnt, sizeof *values, compare_ints_noaux);
1709 ll_sort (ll_head (&list), ll_null (&list), compare_elements, &aux_data);
1710 check_list_contents (&list, values, cnt);
1712 free_elements (cnt, elems, NULL, values);
1716 /* Tests ll_unique. */
1720 const int max_elems = 10;
1722 int *ascending = xnmalloc (max_elems, sizeof *ascending);
1724 int cnt, inc_pat, i, j, unique_values;
1726 for (i = 0; i < max_elems; i++)
1729 for (cnt = 0; cnt < max_elems; cnt++)
1730 for (inc_pat = 0; inc_pat < (1 << cnt); inc_pat++)
1732 struct ll_list list, dups;
1733 struct element **elems;
1736 allocate_elements (cnt, &list, &elems, NULL, &values);
1738 j = unique_values = 0;
1739 for (i = 0; i < cnt; i++)
1741 unique_values = j + 1;
1742 elems[i]->x = values[i] = j;
1743 if (inc_pat & (1 << i))
1746 check_list_contents (&list, values, cnt);
1749 check (ll_unique (ll_head (&list), ll_null (&list), ll_null (&dups),
1750 compare_elements, &aux_data)
1751 == (size_t) unique_values);
1752 check_list_contents (&list, ascending, unique_values);
1754 ll_splice (ll_null (&list), ll_head (&dups), ll_null (&dups));
1755 ll_sort (ll_head (&list), ll_null (&list), compare_elements, &aux_data);
1756 check_list_contents (&list, values, cnt);
1758 free_elements (cnt, elems, NULL, values);
1764 /* Tests ll_sort_unique. */
1766 test_sort_unique (void)
1768 const int max_elems = 7;
1771 for (cnt = 0; cnt <= max_elems; cnt++)
1772 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1774 struct ll_list list;
1775 struct element **elems;
1778 struct element **perm_elems;
1787 allocate_elements (cnt, &list, &elems, NULL, &values);
1788 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1791 for (i = 0; i < cnt; i++)
1793 elems[i]->x = values[i] = j;
1795 if (inc_pat & (1 << i))
1799 unique_values = xnmalloc (unique_cnt, sizeof *unique_values);
1800 for (i = 0; i < unique_cnt; i++)
1801 unique_values[i] = i;
1804 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1805 compare_elements, &aux_data))
1807 struct ll_list perm_list;
1809 extract_values (&list, perm_values, cnt);
1810 ll_init (&perm_list);
1811 for (i = 0; i < cnt; i++)
1813 perm_elems[i]->x = perm_values[i];
1814 perm_elems[i]->y = i;
1815 ll_push_tail (&perm_list, &perm_elems[i]->ll);
1817 ll_sort_unique (ll_head (&perm_list), ll_null (&perm_list), NULL,
1818 compare_elements, &aux_data);
1819 check_list_contents (&perm_list, unique_values, unique_cnt);
1820 check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1821 compare_elements_x_y, &aux_data));
1824 check (perm_cnt == expected_perms (values, cnt));
1826 free_elements (cnt, elems, NULL, values);
1827 free_elements (cnt, perm_elems, NULL, perm_values);
1828 free (unique_values);
1832 /* Tests ll_insert_ordered. */
1834 test_insert_ordered (void)
1836 const int max_elems = 6;
1839 for (cnt = 0; cnt <= max_elems; cnt++)
1840 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1842 struct ll_list list;
1843 struct element **elems;
1846 struct element **perm_elems;
1852 allocate_elements (cnt, &list, &elems, NULL, &values);
1853 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1856 for (i = 0; i < cnt; i++)
1858 elems[i]->x = values[i] = j;
1859 if (inc_pat & (1 << i))
1865 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1866 compare_elements_y, &aux_data))
1868 struct ll_list perm_list;
1870 extract_values (&list, perm_values, cnt);
1871 ll_init (&perm_list);
1872 for (i = 0; i < cnt; i++)
1874 perm_elems[i]->x = perm_values[i];
1875 perm_elems[i]->y = i;
1876 ll_insert_ordered (ll_head (&perm_list), ll_null (&perm_list),
1878 compare_elements, &aux_data);
1880 check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1881 compare_elements_x_y, &aux_data));
1884 check (perm_cnt == factorial (cnt));
1886 free_elements (cnt, elems, NULL, values);
1887 free_elements (cnt, perm_elems, NULL, perm_values);
1891 /* Tests ll_partition. */
1893 test_partition (void)
1895 const int max_elems = 10;
1901 for (cnt = 0; cnt < max_elems; cnt++)
1902 for (r0 = 0; r0 <= cnt; r0++)
1903 for (r1 = r0; r1 <= cnt; r1++)
1904 for (pbase = 0; pbase <= (1u << (r1 - r0)); pbase++)
1906 struct ll_list list;
1907 struct element **elems;
1911 unsigned int pattern = pbase << r0;
1916 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1918 /* Check that ll_find_partition works okay in every
1919 case. We use it after partitioning, too, but that
1920 only tests cases where it returns non-null. */
1921 for (i = r0; i < r1; i++)
1922 if (!(pattern & (1u << i)))
1926 if (pattern & (1u << i))
1928 part_ll = ll_find_partition (elemp[r0], elemp[r1],
1932 check (part_ll == elemp[j]);
1934 check (part_ll == NULL);
1936 /* Figure out expected results. */
1939 for (i = 0; i < r0; i++)
1941 for (i = r0; i < r1; i++)
1942 if (pattern & (1u << i))
1944 for (i = r0; i < r1; i++)
1945 if (!(pattern & (1u << i)))
1947 if (first_false == -1)
1951 if (first_false == -1)
1953 for (i = r1; i < cnt; i++)
1957 /* Partition and check for expected results. */
1958 check (ll_partition (elemp[r0], elemp[r1],
1959 pattern_pred, &pattern)
1960 == elemp[first_false]);
1961 check (ll_find_partition (elemp[r0], elemp[r1],
1962 pattern_pred, &pattern)
1963 == elemp[first_false]);
1964 check_list_contents (&list, values, cnt);
1965 check ((int) ll_count (&list) == cnt);
1967 free_elements (cnt, elems, elemp, values);
1973 /* Runs TEST_FUNCTION and prints a message about NAME. */
1975 run_test (void (*test_function) (void), const char *name)
1986 run_test (test_push_pop, "push/pop");
1987 run_test (test_insert_remove, "insert/remove");
1988 run_test (test_swap, "swap");
1989 run_test (test_swap_range, "swap_range");
1990 run_test (test_remove_range, "remove_range");
1991 run_test (test_remove_equal, "remove_equal");
1992 run_test (test_remove_if, "remove_if");
1993 run_test (test_moved, "moved");
1994 run_test (test_find_equal, "find_equal");
1995 run_test (test_find_if, "find_if");
1996 run_test (test_find_adjacent_equal, "find_adjacent_equal");
1997 run_test (test_count_range, "count_range");
1998 run_test (test_count_equal, "count_equal");
1999 run_test (test_count_if, "count_if");
2000 run_test (test_min_max, "min/max");
2001 run_test (test_lexicographical_compare_3way, "lexicographical_compare_3way");
2002 run_test (test_apply, "apply");
2003 run_test (test_reverse, "reverse");
2004 run_test (test_permutations_no_dups, "permutations (no dups)");
2005 run_test (test_permutations_with_dups, "permutations (with dups)");
2006 run_test (test_merge_no_dups, "merge (no dups)");
2007 run_test (test_merge_with_dups, "merge (with dups)");
2008 run_test (test_sort_exhaustive, "sort (exhaustive)");
2009 run_test (test_sort_stable, "sort (stability)");
2010 run_test (test_sort_subset, "sort (subset)");
2011 run_test (test_sort_big, "sort (big)");
2012 run_test (test_unique, "unique");
2013 run_test (test_sort_unique, "sort_unique");
2014 run_test (test_insert_ordered, "insert_ordered");
2015 run_test (test_partition, "partition");
2023 compile-command: "gcc -Wall -Wstrict-prototypes -Wmissing-prototypes ll.c ll-test.c -o ll-test -g"