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_*
35 #include <libpspp/ll.h>
41 /* Support preliminaries. */
42 #if __GNUC__ >= 2 && !defined UNUSED
43 #define UNUSED __attribute__ ((unused))
48 /* Currently running test. */
49 static const char *test_name;
51 /* Exit with a failure code.
52 (Place a breakpoint on this function while debugging.) */
59 /* If OK is not true, prints a message about failure on the
60 current source file and the given LINE and terminates. */
62 check_func (bool ok, int line)
66 printf ("Check failed in %s test at %s, line %d\n",
67 test_name, __FILE__, line);
72 /* Verifies that EXPR evaluates to true.
73 If not, prints a message citing the calling line number and
75 #define check(EXPR) check_func ((EXPR), __LINE__)
77 /* Prints a message about memory exhaustion and exits with a
82 printf ("virtual memory exhausted\n");
86 /* Allocates and returns N bytes of memory. */
102 /* Allocates and returns N * M bytes of memory. */
104 xnmalloc (size_t n, size_t m)
106 if ((size_t) -1 / m <= n)
108 return xmalloc (n * m);
111 /* List type and support routines. */
113 /* Test data element. */
116 struct ll ll; /* Embedded list element. */
117 int x; /* Primary value. */
118 int y; /* Secondary value. */
123 /* Returns the `struct element' that LL is embedded within. */
124 static struct element *
125 ll_to_element (const struct ll *ll)
127 return ll_data (ll, struct element, ll);
130 /* Prints the elements in LIST. */
132 print_list (struct ll_list *list)
137 for (x = ll_head (list); x != ll_null (list); x = ll_next (x))
139 struct element *e = ll_to_element (x);
140 printf (" %d", e->x);
145 /* Prints the value returned by PREDICATE given auxiliary data
146 AUX for each element in LIST. */
148 print_pred (struct ll_list *list,
149 ll_predicate_func *predicate, void *aux UNUSED)
154 for (x = ll_head (list); x != ll_null (list); x = ll_next (x))
155 printf (" %d", predicate (x, aux));
159 /* Prints the CNT numbers in VALUES. */
161 print_array (int values[], size_t cnt)
166 for (i = 0; i < cnt; i++)
167 printf (" %d", values[i]);
171 /* Compares the `x' values in A and B and returns a strcmp-type
172 return value. Verifies that AUX points to aux_data. */
174 compare_elements (const struct ll *a_, const struct ll *b_, void *aux)
176 const struct element *a = ll_to_element (a_);
177 const struct element *b = ll_to_element (b_);
179 check (aux == &aux_data);
180 return a->x < b->x ? -1 : a->x > b->x;
183 /* Compares the `x' and `y' values in A and B and returns a
184 strcmp-type return value. Verifies that AUX points to
187 compare_elements_x_y (const struct ll *a_, const struct ll *b_, void *aux)
189 const struct element *a = ll_to_element (a_);
190 const struct element *b = ll_to_element (b_);
192 check (aux == &aux_data);
194 return a->x < b->x ? -1 : 1;
195 else if (a->y != b->y)
196 return a->y < b->y ? -1 : 1;
201 /* Compares the `y' values in A and B and returns a strcmp-type
202 return value. Verifies that AUX points to aux_data. */
204 compare_elements_y (const struct ll *a_, const struct ll *b_, void *aux)
206 const struct element *a = ll_to_element (a_);
207 const struct element *b = ll_to_element (b_);
209 check (aux == &aux_data);
210 return a->y < b->y ? -1 : a->y > b->y;
213 /* Returns true if the bit in *PATTERN indicated by `x in
214 *ELEMENT is set, false otherwise. */
216 pattern_pred (const struct ll *element_, void *pattern_)
218 const struct element *element = ll_to_element (element_);
219 unsigned int *pattern = pattern_;
221 return (*pattern & (1u << element->x)) != 0;
224 /* Allocates N elements in *ELEMS.
225 Adds the elements to LIST, if it is nonnull.
226 Puts pointers to the elements' list elements in *ELEMP,
227 followed by a pointer to the list null element, if ELEMP is
229 Allocates space for N values in *VALUES, if VALUES is
232 allocate_elements (size_t n,
233 struct ll_list *list,
234 struct element ***elems,
243 *elems = xnmalloc (n, sizeof **elems);
244 for (i = 0; i < n; i++)
246 (*elems)[i] = xmalloc (sizeof ***elems);
248 ll_push_tail (list, &(*elems)[i]->ll);
253 *elemp = xnmalloc (n + 1, sizeof *elemp);
254 for (i = 0; i < n; i++)
255 (*elemp)[i] = &(*elems)[i]->ll;
256 (*elemp)[n] = ll_null (list);
260 *values = xnmalloc (n, sizeof *values);
263 /* Copies the CNT values of `x' from LIST into VALUES[]. */
265 extract_values (struct ll_list *list, int values[], size_t cnt)
269 check (ll_count (list) == cnt);
270 for (x = ll_head (list); x != ll_null (list); x = ll_next (x))
272 struct element *e = ll_to_element (x);
277 /* As allocate_elements, but sets ascending values, starting
278 from 0, in `x' values in *ELEMS and in *VALUES (if
281 allocate_ascending (size_t n,
282 struct ll_list *list,
283 struct element ***elems,
289 allocate_elements (n, list, elems, elemp, values);
291 for (i = 0; i < n; i++)
294 extract_values (list, *values, n);
297 /* As allocate_elements, but sets binary values extracted from
298 successive bits in PATTERN in `x' values in *ELEMS and in
299 *VALUES (if nonnull). */
301 allocate_pattern (size_t n,
303 struct ll_list *list,
304 struct element ***elems,
310 allocate_elements (n, list, elems, elemp, values);
312 for (i = 0; i < n; i++)
313 (*elems)[i]->x = (pattern & (1 << i)) != 0;
315 extract_values (list, *values, n);
318 /* Randomly shuffles the CNT elements in ARRAY, each of which is
319 SIZE bytes in size. */
321 random_shuffle (void *array_, size_t cnt, size_t size)
323 char *array = array_;
324 char *tmp = xmalloc (size);
327 for (i = 0; i < cnt; i++)
329 size_t j = rand () % (cnt - i) + i;
332 memcpy (tmp, array + j * size, size);
333 memcpy (array + j * size, array + i * size, size);
334 memcpy (array + i * size, tmp, size);
341 /* As allocate_ascending, but orders the values randomly. */
343 allocate_random (size_t n,
344 struct ll_list *list,
345 struct element ***elems,
351 allocate_elements (n, list, elems, elemp, values);
353 for (i = 0; i < n; i++)
355 random_shuffle (*elems, n, sizeof **elems);
357 extract_values (list, *values, n);
360 /* Frees the N elements of ELEMS, ELEMP, and VALUES. */
362 free_elements (size_t n,
363 struct element **elems,
369 for (i = 0; i < n; i++)
376 /* Compares A and B and returns a strcmp-type return value. */
378 compare_ints (const void *a_, const void *b_, void *aux UNUSED)
383 return *a < *b ? -1 : *a > *b;
386 /* Compares A and B and returns a strcmp-type return value. */
388 compare_ints_noaux (const void *a_, const void *b_)
393 return *a < *b ? -1 : *a > *b;
396 /* Checks that LIST contains the CNT values in ELEMENTS. */
398 check_list_contents (struct ll_list *list, int elements[], size_t cnt)
403 check ((cnt == 0) == ll_is_empty (list));
405 /* Iterate in forward order. */
406 for (ll = ll_head (list), i = 0; i < cnt; ll = ll_next (ll), i++)
408 struct element *e = ll_to_element (ll);
409 check (elements[i] == e->x);
410 check (ll != ll_null (list));
412 check (ll == ll_null (list));
414 /* Iterate in reverse order. */
415 for (ll = ll_tail (list), i = 0; i < cnt; ll = ll_prev (ll), i++)
417 struct element *e = ll_to_element (ll);
418 check (elements[cnt - i - 1] == e->x);
419 check (ll != ll_null (list));
421 check (ll == ll_null (list));
423 check (ll_count (list) == cnt);
426 /* Lexicographically compares ARRAY1, which contains COUNT1
427 elements of SIZE bytes each, to ARRAY2, which contains COUNT2
428 elements of SIZE bytes, according to COMPARE. Returns a
429 strcmp-type result. AUX is passed to COMPARE as auxiliary
432 lexicographical_compare_3way (const void *array1, size_t count1,
433 const void *array2, size_t count2,
435 int (*compare) (const void *, const void *,
439 const char *first1 = array1;
440 const char *first2 = array2;
441 size_t min_count = count1 < count2 ? count1 : count2;
443 while (min_count > 0)
445 int cmp = compare (first1, first2, aux);
454 return count1 < count2 ? -1 : count1 > count2;
459 /* Tests list push and pop operations. */
463 const int max_elems = 1024;
466 struct element **elems;
471 allocate_elements (max_elems, NULL, &elems, NULL, &values);
475 check_list_contents (&list, NULL, 0);
476 for (i = 0; i < max_elems; i++)
478 values[i] = elems[i]->x = i;
479 ll_push_tail (&list, &elems[i]->ll);
480 check_list_contents (&list, values, i + 1);
483 /* Remove from tail. */
484 for (i = 0; i < max_elems; i++)
486 struct element *e = ll_to_element (ll_pop_tail (&list));
487 check (e->x == max_elems - i - 1);
488 check_list_contents (&list, values, max_elems - i - 1);
492 check_list_contents (&list, NULL, 0);
493 for (i = 0; i < max_elems; i++)
495 values[max_elems - i - 1] = elems[i]->x = max_elems - i - 1;
496 ll_push_head (&list, &elems[i]->ll);
497 check_list_contents (&list, &values[max_elems - i - 1], i + 1);
500 /* Remove from start. */
501 for (i = 0; i < max_elems; i++)
503 struct element *e = ll_to_element (ll_pop_head (&list));
504 check (e->x == (int) i);
505 check_list_contents (&list, &values[i + 1], max_elems - i - 1);
508 free_elements (max_elems, elems, NULL, values);
511 /* Tests insertion and removal at arbitrary positions. */
513 test_insert_remove (void)
515 const int max_elems = 16;
518 for (cnt = 0; cnt < max_elems; cnt++)
520 struct element **elems;
522 int *values = xnmalloc (cnt + 1, sizeof *values);
525 struct element extra;
528 allocate_ascending (cnt, &list, &elems, &elemp, NULL);
530 for (pos = 0; pos <= cnt; pos++)
534 ll_insert (elemp[pos], &extra.ll);
537 for (i = 0; i < pos; i++)
542 check_list_contents (&list, values, cnt + 1);
544 ll_remove (&extra.ll);
546 check_list_contents (&list, values, cnt);
548 free_elements (cnt, elems, elemp, values);
552 /* Tests swapping individual elements. */
556 const int max_elems = 8;
559 for (cnt = 0; cnt <= max_elems; cnt++)
562 struct element **elems;
567 allocate_ascending (cnt, &list, &elems, NULL, &values);
568 check_list_contents (&list, values, cnt);
570 for (i = 0; i < cnt; i++)
571 for (j = 0; j < cnt; j++)
572 for (k = 0; k < 2; k++)
576 ll_swap (&elems[i]->ll, &elems[j]->ll);
578 values[i] = values[j];
580 check_list_contents (&list, values, cnt);
583 free_elements (cnt, elems, NULL, values);
587 /* Tests swapping ranges of list elements. */
589 test_swap_range (void)
591 const int max_elems = 8;
592 int cnt, a0, a1, b0, b1, r;
594 for (cnt = 0; cnt <= max_elems; cnt++)
595 for (a0 = 0; a0 <= cnt; a0++)
596 for (a1 = a0; a1 <= cnt; a1++)
597 for (b0 = a1; b0 <= cnt; b0++)
598 for (b1 = b0; b1 <= cnt; b1++)
599 for (r = 0; r < 2; r++)
602 struct element **elems;
608 allocate_ascending (cnt, &list, &elems, &elemp, &values);
609 check_list_contents (&list, values, cnt);
612 for (i = 0; i < a0; i++)
614 for (i = b0; i < b1; i++)
616 for (i = a1; i < b0; i++)
618 for (i = a0; i < a1; i++)
620 for (i = b1; i < cnt; i++)
625 ll_swap_range (elemp[a0], elemp[a1], elemp[b0], elemp[b1]);
627 ll_swap_range (elemp[b0], elemp[b1], elemp[a0], elemp[a1]);
628 check_list_contents (&list, values, cnt);
630 free_elements (cnt, elems, elemp, values);
634 /* Tests removing ranges of list elements. */
636 test_remove_range (void)
638 const int max_elems = 8;
642 for (cnt = 0; cnt <= max_elems; cnt++)
643 for (r0 = 0; r0 <= cnt; r0++)
644 for (r1 = r0; r1 <= cnt; r1++)
647 struct element **elems;
653 allocate_ascending (cnt, &list, &elems, &elemp, &values);
654 check_list_contents (&list, values, cnt);
657 for (i = 0; i < r0; i++)
659 for (i = r1; i < cnt; i++)
662 ll_remove_range (elemp[r0], elemp[r1]);
663 check_list_contents (&list, values, j);
665 free_elements (cnt, elems, elemp, values);
669 /* Tests ll_remove_equal. */
671 test_remove_equal (void)
673 const int max_elems = 8;
675 int cnt, r0, r1, eq_pat;
677 for (cnt = 0; cnt <= max_elems; cnt++)
678 for (r0 = 0; r0 <= cnt; r0++)
679 for (r1 = r0; r1 <= cnt; r1++)
680 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
683 struct element **elems;
687 struct element to_remove;
691 allocate_elements (cnt, &list, &elems, &elemp, &values);
694 for (i = 0; i < cnt; i++)
696 int x = eq_pat & (1 << i) ? -1 : i;
697 bool delete = x == -1 && r0 <= i && i < r1;
700 values[remaining++] = x;
704 check ((int) ll_remove_equal (elemp[r0], elemp[r1], &to_remove.ll,
705 compare_elements, &aux_data)
707 check_list_contents (&list, values, remaining);
709 free_elements (cnt, elems, elemp, values);
713 /* Tests ll_remove_if. */
715 test_remove_if (void)
717 const int max_elems = 8;
719 int cnt, r0, r1, pattern;
721 for (cnt = 0; cnt <= max_elems; cnt++)
722 for (r0 = 0; r0 <= cnt; r0++)
723 for (r1 = r0; r1 <= cnt; r1++)
724 for (pattern = 0; pattern <= 1 << cnt; pattern++)
727 struct element **elems;
734 allocate_elements (cnt, &list, &elems, &elemp, &values);
737 for (i = 0; i < cnt; i++)
739 bool delete = (pattern & (1 << i)) && r0 <= i && i < r1;
742 values[remaining++] = i;
745 check ((int) ll_remove_if (elemp[r0], elemp[r1],
746 pattern_pred, &pattern)
748 check_list_contents (&list, values, remaining);
750 free_elements (cnt, elems, elemp, values);
754 /* Tests ll_moved. */
758 const int max_elems = 8;
762 for (cnt = 0; cnt <= max_elems; cnt++)
765 struct element **elems;
766 struct element **new_elems;
771 allocate_ascending (cnt, &list, &elems, NULL, &values);
772 allocate_elements (cnt, NULL, &new_elems, NULL, NULL);
773 check_list_contents (&list, values, cnt);
775 for (i = 0; i < cnt; i++)
777 *new_elems[i] = *elems[i];
778 ll_moved (&new_elems[i]->ll);
779 check_list_contents (&list, values, cnt);
782 free_elements (cnt, elems, NULL, values);
783 free_elements (cnt, new_elems, NULL, NULL);
787 /* Tests, via HELPER, a function that looks at list elements
788 equal to some specified element. */
790 test_examine_equal_range (void (*helper) (int r0, int r1, int eq_pat,
794 const int max_elems = 8;
796 int cnt, r0, r1, eq_pat;
798 for (cnt = 0; cnt <= max_elems; cnt++)
799 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
802 struct element **elems;
806 struct element to_find;
810 allocate_ascending (cnt, &list, &elems, &elemp, &values);
812 for (i = 0; i < cnt; i++)
813 if (eq_pat & (1 << i))
814 values[i] = elems[i]->x = -1;
817 for (r0 = 0; r0 <= cnt; r0++)
818 for (r1 = r0; r1 <= cnt; r1++)
819 helper (r0, r1, eq_pat, &to_find.ll, elemp);
821 check_list_contents (&list, values, cnt);
823 free_elements (cnt, elems, elemp, values);
827 /* Tests, via HELPER, a function that looks at list elements for
828 which a given predicate returns true. */
830 test_examine_if_range (void (*helper) (int r0, int r1, int eq_pat,
833 const int max_elems = 8;
835 int cnt, r0, r1, eq_pat;
837 for (cnt = 0; cnt <= max_elems; cnt++)
838 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
841 struct element **elems;
845 allocate_ascending (cnt, &list, &elems, &elemp, &values);
847 for (r0 = 0; r0 <= cnt; r0++)
848 for (r1 = r0; r1 <= cnt; r1++)
849 helper (r0, r1, eq_pat, elemp);
851 check_list_contents (&list, values, cnt);
853 free_elements (cnt, elems, elemp, values);
857 /* Helper function for testing ll_find_equal. */
859 test_find_equal_helper (int r0, int r1, int eq_pat,
860 struct ll *to_find, struct ll **elemp)
865 match = ll_find_equal (elemp[r0], elemp[r1], to_find,
866 compare_elements, &aux_data);
867 for (i = r0; i < r1; i++)
868 if (eq_pat & (1 << i))
871 check (match == elemp[i]);
874 /* Tests ll_find_equal. */
876 test_find_equal (void)
878 test_examine_equal_range (test_find_equal_helper);
881 /* Helper function for testing ll_find_if. */
883 test_find_if_helper (int r0, int r1, int eq_pat, struct ll **elemp)
885 struct ll *match = ll_find_if (elemp[r0], elemp[r1],
886 pattern_pred, &eq_pat);
889 for (i = r0; i < r1; i++)
890 if (eq_pat & (1 << i))
893 check (match == elemp[i]);
896 /* Tests ll_find_if. */
900 test_examine_if_range (test_find_if_helper);
903 /* Tests ll_find_adjacent_equal. */
905 test_find_adjacent_equal (void)
907 const int max_elems = 8;
911 for (cnt = 0; cnt <= max_elems; cnt++)
912 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
915 struct element **elems;
922 allocate_ascending (cnt, &list, &elems, &elemp, &values);
925 for (i = 0; i < cnt - 1; i++)
928 if (eq_pat & (1 << i))
930 values[i] = elems[i]->x = match;
931 values[i + 1] = elems[i + 1]->x = match;
937 for (i = 0; i <= cnt; i++)
939 struct ll *ll1 = ll_find_adjacent_equal (elemp[i], ll_null (&list),
945 ll2 = ll_null (&list);
946 for (j = i; j < cnt - 1; j++)
947 if (eq_pat & (1 << j))
954 check_list_contents (&list, values, cnt);
956 free_elements (cnt, elems, elemp, values);
960 /* Helper function for testing ll_count_range. */
962 test_count_range_helper (int r0, int r1, int eq_pat UNUSED, struct ll **elemp)
964 check ((int) ll_count_range (elemp[r0], elemp[r1]) == r1 - r0);
967 /* Tests ll_count_range. */
969 test_count_range (void)
971 test_examine_if_range (test_count_range_helper);
974 /* Helper function for testing ll_count_equal. */
976 test_count_equal_helper (int r0, int r1, int eq_pat,
977 struct ll *to_find, struct ll **elemp)
982 count1 = ll_count_equal (elemp[r0], elemp[r1], to_find,
983 compare_elements, &aux_data);
985 for (i = r0; i < r1; i++)
986 if (eq_pat & (1 << i))
989 check (count1 == count2);
992 /* Tests ll_count_equal. */
994 test_count_equal (void)
996 test_examine_equal_range (test_count_equal_helper);
999 /* Helper function for testing ll_count_if. */
1001 test_count_if_helper (int r0, int r1, int eq_pat, struct ll **elemp)
1007 count1 = ll_count_if (elemp[r0], elemp[r1], pattern_pred, &eq_pat);
1010 for (i = r0; i < r1; i++)
1011 if (eq_pat & (1 << i))
1014 check (count1 == count2);
1017 /* Tests ll_count_if. */
1019 test_count_if (void)
1021 test_examine_if_range (test_count_if_helper);
1026 factorial (unsigned int n)
1028 unsigned int value = 1;
1034 /* Returns the number of permutations of the CNT values in
1035 VALUES. If VALUES contains duplicates, they must be
1038 expected_perms (int *values, size_t cnt)
1041 unsigned int perm_cnt;
1043 perm_cnt = factorial (cnt);
1044 for (i = 0; i < cnt; i = j)
1046 for (j = i + 1; j < cnt; j++)
1047 if (values[i] != values[j])
1049 perm_cnt /= factorial (j - i);
1054 /* Tests ll_min and ll_max. */
1058 const int max_elems = 6;
1061 for (cnt = 0; cnt <= max_elems; cnt++)
1063 struct ll_list list;
1064 struct element **elems;
1067 int *new_values = xnmalloc (cnt, sizeof *values);
1071 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1074 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1075 compare_elements, &aux_data))
1081 for (i = 0, x = ll_head (&list); x != ll_null (&list);
1082 x = ll_next (x), i++)
1084 struct element *e = ll_to_element (x);
1086 new_values[i] = e->x;
1088 for (r0 = 0; r0 <= cnt; r0++)
1089 for (r1 = r0; r1 <= cnt; r1++)
1091 struct ll *min = ll_min (elemp[r0], elemp[r1],
1092 compare_elements, &aux_data);
1093 struct ll *max = ll_max (elemp[r0], elemp[r1],
1094 compare_elements, &aux_data);
1097 check (min == elemp[r1]);
1098 check (max == elemp[r1]);
1102 int min_int, max_int;
1105 min_int = max_int = new_values[r0];
1106 for (i = r0; i < r1; i++)
1108 int value = new_values[i];
1109 if (value < min_int)
1111 if (value > max_int)
1114 check (min != elemp[r1]
1115 && ll_to_element (min)->x == min_int);
1116 check (max != elemp[r1]
1117 && ll_to_element (max)->x == max_int);
1122 check (perm_cnt == factorial (cnt));
1123 check_list_contents (&list, values, cnt);
1125 free_elements (cnt, elems, elemp, values);
1130 /* Tests ll_lexicographical_compare_3way. */
1132 test_lexicographical_compare_3way (void)
1134 const int max_elems = 4;
1136 int cnt_a, pat_a, cnt_b, pat_b;
1138 for (cnt_a = 0; cnt_a <= max_elems; cnt_a++)
1139 for (pat_a = 0; pat_a <= 1 << cnt_a; pat_a++)
1140 for (cnt_b = 0; cnt_b <= max_elems; cnt_b++)
1141 for (pat_b = 0; pat_b <= 1 << cnt_b; pat_b++)
1143 struct ll_list list_a, list_b;
1144 struct element **elems_a, **elems_b;
1145 struct ll **elemp_a, **elemp_b;
1146 int *values_a, *values_b;
1150 allocate_pattern (cnt_a, pat_a,
1151 &list_a, &elems_a, &elemp_a, &values_a);
1152 allocate_pattern (cnt_b, pat_b,
1153 &list_b, &elems_b, &elemp_b, &values_b);
1155 for (a0 = 0; a0 <= cnt_a; a0++)
1156 for (a1 = a0; a1 <= cnt_a; a1++)
1157 for (b0 = 0; b0 <= cnt_b; b0++)
1158 for (b1 = b0; b1 <= cnt_b; b1++)
1160 int a_ordering = lexicographical_compare_3way (
1161 values_a + a0, a1 - a0,
1162 values_b + b0, b1 - b0,
1164 compare_ints, NULL);
1166 int b_ordering = ll_lexicographical_compare_3way (
1167 elemp_a[a0], elemp_a[a1],
1168 elemp_b[b0], elemp_b[b1],
1169 compare_elements, &aux_data);
1171 check (a_ordering == b_ordering);
1174 free_elements (cnt_a, elems_a, elemp_a, values_a);
1175 free_elements (cnt_b, elems_b, elemp_b, values_b);
1179 /* Appends the `x' value in element E to the array pointed to by
1180 NEXT_OUTPUT, and advances NEXT_OUTPUT to the next position. */
1182 apply_func (struct ll *e_, void *next_output_)
1184 struct element *e = ll_to_element (e_);
1185 int **next_output = next_output_;
1187 *(*next_output)++ = e->x;
1190 /* Tests ll_apply. */
1194 const int max_elems = 8;
1198 for (cnt = 0; cnt <= max_elems; cnt++)
1199 for (r0 = 0; r0 <= cnt; r0++)
1200 for (r1 = r0; r1 <= cnt; r1++)
1202 struct ll_list list;
1203 struct element **elems;
1212 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1213 check_list_contents (&list, values, cnt);
1215 output = next_output = xnmalloc (cnt, sizeof *output);
1216 ll_apply (elemp[r0], elemp[r1], apply_func, &next_output);
1217 check_list_contents (&list, values, cnt);
1219 check (r1 - r0 == next_output - output);
1220 for (i = 0; i < r1 - r0; i++)
1221 check (output[i] == r0 + i);
1223 free_elements (cnt, elems, elemp, values);
1228 /* Tests ll_reverse. */
1232 const int max_elems = 8;
1236 for (cnt = 0; cnt <= max_elems; cnt++)
1237 for (r0 = 0; r0 <= cnt; r0++)
1238 for (r1 = r0; r1 <= cnt; r1++)
1240 struct ll_list list;
1241 struct element **elems;
1247 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1248 check_list_contents (&list, values, cnt);
1251 for (i = 0; i < r0; i++)
1253 for (i = r1 - 1; i >= r0; i--)
1255 for (i = r1; i < cnt; i++)
1258 ll_reverse (elemp[r0], elemp[r1]);
1259 check_list_contents (&list, values, cnt);
1261 free_elements (cnt, elems, elemp, values);
1265 /* Tests ll_next_permutation and ll_prev_permutation when the
1266 permuted values have no duplicates. */
1268 test_permutations_no_dups (void)
1270 const int max_elems = 8;
1273 for (cnt = 0; cnt <= max_elems; cnt++)
1275 struct ll_list list;
1276 struct element **elems;
1278 int *old_values = xnmalloc (cnt, sizeof *values);
1279 int *new_values = xnmalloc (cnt, sizeof *values);
1283 allocate_ascending (cnt, &list, &elems, NULL, &values);
1286 extract_values (&list, old_values, cnt);
1287 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1288 compare_elements, &aux_data))
1290 extract_values (&list, new_values, cnt);
1291 check (lexicographical_compare_3way (new_values, cnt,
1294 compare_ints, NULL) > 0);
1295 memcpy (old_values, new_values, (cnt) * sizeof *old_values);
1298 check (perm_cnt == factorial (cnt));
1299 check_list_contents (&list, values, cnt);
1302 ll_reverse (ll_head (&list), ll_null (&list));
1303 extract_values (&list, old_values, cnt);
1304 while (ll_prev_permutation (ll_head (&list), ll_null (&list),
1305 compare_elements, &aux_data))
1307 extract_values (&list, new_values, cnt);
1308 check (lexicographical_compare_3way (new_values, cnt,
1311 compare_ints, NULL) < 0);
1312 memcpy (old_values, new_values, (cnt) * sizeof *old_values);
1315 check (perm_cnt == factorial (cnt));
1316 ll_reverse (ll_head (&list), ll_null (&list));
1317 check_list_contents (&list, values, cnt);
1319 free_elements (cnt, elems, NULL, values);
1325 /* Tests ll_next_permutation and ll_prev_permutation when the
1326 permuted values contain duplicates. */
1328 test_permutations_with_dups (void)
1330 const int max_elems = 8;
1331 const int max_dup = 3;
1332 const int repetitions = 1024;
1336 for (repeat = 0; repeat < repetitions; repeat++)
1337 for (cnt = 0; cnt < max_elems; cnt++)
1339 struct ll_list list;
1340 struct element **elems;
1342 int *old_values = xnmalloc (max_elems, sizeof *values);
1343 int *new_values = xnmalloc (max_elems, sizeof *values);
1345 unsigned int permutation_cnt;
1349 allocate_elements (cnt, &list, &elems, NULL, &values);
1354 int max = left < max_dup ? left : max_dup;
1355 int n = rand () % max + 1;
1358 int idx = cnt - left--;
1359 values[idx] = elems[idx]->x = value;
1364 permutation_cnt = 1;
1365 extract_values (&list, old_values, cnt);
1366 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1367 compare_elements, &aux_data))
1369 extract_values (&list, new_values, cnt);
1370 check (lexicographical_compare_3way (new_values, cnt,
1373 compare_ints, NULL) > 0);
1374 memcpy (old_values, new_values, cnt * sizeof *old_values);
1377 check (permutation_cnt == expected_perms (values, cnt));
1378 check_list_contents (&list, values, cnt);
1380 permutation_cnt = 1;
1381 ll_reverse (ll_head (&list), ll_null (&list));
1382 extract_values (&list, old_values, cnt);
1383 while (ll_prev_permutation (ll_head (&list), ll_null (&list),
1384 compare_elements, &aux_data))
1386 extract_values (&list, new_values, cnt);
1387 check (lexicographical_compare_3way (new_values, cnt,
1390 compare_ints, NULL) < 0);
1393 ll_reverse (ll_head (&list), ll_null (&list));
1394 check (permutation_cnt == expected_perms (values, cnt));
1395 check_list_contents (&list, values, cnt);
1397 free_elements (cnt, elems, NULL, values);
1403 /* Tests ll_merge when no equal values are to be merged. */
1405 test_merge_no_dups (void)
1407 const int max_elems = 8;
1408 const int max_filler = 3;
1410 int merge_cnt, pattern, pfx, gap, sfx, order;
1412 for (merge_cnt = 0; merge_cnt < max_elems; merge_cnt++)
1413 for (pattern = 0; pattern <= (1 << merge_cnt); pattern++)
1414 for (pfx = 0; pfx < max_filler; pfx++)
1415 for (gap = 0; gap < max_filler; gap++)
1416 for (sfx = 0; sfx < max_filler; sfx++)
1417 for (order = 0; order < 2; order++)
1419 struct ll_list list;
1420 struct element **elems;
1424 int list_cnt = pfx + merge_cnt + gap + sfx;
1428 allocate_elements (list_cnt, &list,
1429 &elems, &elemp, &values);
1432 for (i = 0; i < pfx; i++)
1433 elems[j++]->x = 100 + i;
1435 for (i = 0; i < merge_cnt; i++)
1436 if (pattern & (1u << i))
1439 for (i = 0; i < gap; i++)
1440 elems[j++]->x = 200 + i;
1442 for (i = 0; i < merge_cnt; i++)
1443 if (!(pattern & (1u << i)))
1446 for (i = 0; i < sfx; i++)
1447 elems[j++]->x = 300 + i;
1448 check (list_cnt == j);
1451 for (i = 0; i < pfx; i++)
1452 values[j++] = 100 + i;
1454 for (i = 0; i < merge_cnt; i++)
1456 for (i = 0; i < gap; i++)
1457 values[j++] = 200 + i;
1459 for (i = 0; i < merge_cnt; i++)
1461 for (i = 0; i < sfx; i++)
1462 values[j++] = 300 + i;
1463 check (list_cnt == j);
1466 ll_merge (elemp[a0], elemp[a1], elemp[b0], elemp[b1],
1467 compare_elements, &aux_data);
1469 ll_merge (elemp[b0], elemp[b1], elemp[a0], elemp[a1],
1470 compare_elements, &aux_data);
1472 check_list_contents (&list, values, list_cnt);
1474 free_elements (list_cnt, elems, elemp, values);
1478 /* Tests ll_merge when equal values are to be merged. */
1480 test_merge_with_dups (void)
1482 const int max_elems = 8;
1484 int cnt, merge_pat, inc_pat, order;
1486 for (cnt = 0; cnt <= max_elems; cnt++)
1487 for (merge_pat = 0; merge_pat <= (1 << cnt); merge_pat++)
1488 for (inc_pat = 0; inc_pat <= (1 << cnt); inc_pat++)
1489 for (order = 0; order < 2; order++)
1491 struct ll_list list;
1492 struct element **elems;
1499 allocate_elements (cnt, &list, &elems, &elemp, &values);
1502 for (i = k = 0; i < cnt; i++)
1504 if (merge_pat & (1u << i))
1506 if (inc_pat & (1u << i))
1510 for (i = k = 0; i < cnt; i++)
1512 if (!(merge_pat & (1u << i)))
1514 if (inc_pat & (1u << i))
1521 for (i = 0; i < cnt; i++)
1526 for (i = 0; i < mid; i++)
1527 elems[i]->y = 100 + i;
1528 for (i = mid; i < cnt; i++)
1533 for (i = k = 0; i < cnt; i++)
1536 if (inc_pat & (1u << i))
1542 ll_merge (elemp[0], elemp[mid], elemp[mid], elemp[cnt],
1543 compare_elements, &aux_data);
1545 ll_merge (elemp[mid], elemp[cnt], elemp[0], elemp[mid],
1546 compare_elements, &aux_data);
1548 check_list_contents (&list, values, cnt);
1549 check (ll_is_sorted (ll_head (&list), ll_null (&list),
1550 compare_elements_x_y, &aux_data));
1552 free_elements (cnt, elems, elemp, values);
1556 /* Tests ll_sort on all permutations up to a maximum number of
1559 test_sort_exhaustive (void)
1561 const int max_elems = 8;
1564 for (cnt = 0; cnt <= max_elems; cnt++)
1566 struct ll_list list;
1567 struct element **elems;
1570 struct element **perm_elems;
1575 allocate_ascending (cnt, &list, &elems, NULL, &values);
1576 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1579 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1580 compare_elements, &aux_data))
1582 struct ll_list perm_list;
1585 extract_values (&list, perm_values, cnt);
1586 ll_init (&perm_list);
1587 for (j = 0; j < cnt; j++)
1589 perm_elems[j]->x = perm_values[j];
1590 ll_push_tail (&perm_list, &perm_elems[j]->ll);
1592 ll_sort (ll_head (&perm_list), ll_null (&perm_list),
1593 compare_elements, &aux_data);
1594 check_list_contents (&perm_list, values, cnt);
1595 check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1596 compare_elements, &aux_data));
1599 check (perm_cnt == factorial (cnt));
1601 free_elements (cnt, elems, NULL, values);
1602 free_elements (cnt, perm_elems, NULL, perm_values);
1606 /* Tests that ll_sort is stable in the presence of equal
1609 test_sort_stable (void)
1611 const int max_elems = 6;
1614 for (cnt = 0; cnt <= max_elems; cnt++)
1615 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1617 struct ll_list list;
1618 struct element **elems;
1621 struct element **perm_elems;
1627 allocate_elements (cnt, &list, &elems, NULL, &values);
1628 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1631 for (i = 0; i < cnt; i++)
1633 elems[i]->x = values[i] = j;
1634 if (inc_pat & (1 << i))
1640 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1641 compare_elements_y, &aux_data))
1643 struct ll_list perm_list;
1645 extract_values (&list, perm_values, cnt);
1646 ll_init (&perm_list);
1647 for (i = 0; i < cnt; i++)
1649 perm_elems[i]->x = perm_values[i];
1650 perm_elems[i]->y = i;
1651 ll_push_tail (&perm_list, &perm_elems[i]->ll);
1653 ll_sort (ll_head (&perm_list), ll_null (&perm_list),
1654 compare_elements, &aux_data);
1655 check_list_contents (&perm_list, values, cnt);
1656 check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1657 compare_elements_x_y, &aux_data));
1660 check (perm_cnt == factorial (cnt));
1662 free_elements (cnt, elems, NULL, values);
1663 free_elements (cnt, perm_elems, NULL, perm_values);
1667 /* Tests that ll_sort does not disturb elements outside the
1670 test_sort_subset (void)
1672 const int max_elems = 8;
1674 int cnt, r0, r1, repeat;
1676 for (cnt = 0; cnt <= max_elems; cnt++)
1677 for (repeat = 0; repeat < 100; repeat++)
1678 for (r0 = 0; r0 <= cnt; r0++)
1679 for (r1 = r0; r1 <= cnt; r1++)
1681 struct ll_list list;
1682 struct element **elems;
1686 allocate_random (cnt, &list, &elems, &elemp, &values);
1688 qsort (&values[r0], r1 - r0, sizeof *values, compare_ints_noaux);
1689 ll_sort (elemp[r0], elemp[r1], compare_elements, &aux_data);
1690 check_list_contents (&list, values, cnt);
1692 free_elements (cnt, elems, elemp, values);
1696 /* Tests that ll_sort works with large lists. */
1698 test_sort_big (void)
1700 const int max_elems = 1024;
1704 for (cnt = 0; cnt < max_elems; cnt++)
1706 struct ll_list list;
1707 struct element **elems;
1710 allocate_random (cnt, &list, &elems, NULL, &values);
1712 qsort (values, cnt, sizeof *values, compare_ints_noaux);
1713 ll_sort (ll_head (&list), ll_null (&list), compare_elements, &aux_data);
1714 check_list_contents (&list, values, cnt);
1716 free_elements (cnt, elems, NULL, values);
1720 /* Tests ll_unique. */
1724 const int max_elems = 10;
1726 int *ascending = xnmalloc (max_elems, sizeof *ascending);
1728 int cnt, inc_pat, i, j, unique_values;
1730 for (i = 0; i < max_elems; i++)
1733 for (cnt = 0; cnt < max_elems; cnt++)
1734 for (inc_pat = 0; inc_pat < (1 << cnt); inc_pat++)
1736 struct ll_list list, dups;
1737 struct element **elems;
1740 allocate_elements (cnt, &list, &elems, NULL, &values);
1742 j = unique_values = 0;
1743 for (i = 0; i < cnt; i++)
1745 unique_values = j + 1;
1746 elems[i]->x = values[i] = j;
1747 if (inc_pat & (1 << i))
1750 check_list_contents (&list, values, cnt);
1753 check (ll_unique (ll_head (&list), ll_null (&list), ll_null (&dups),
1754 compare_elements, &aux_data)
1755 == (size_t) unique_values);
1756 check_list_contents (&list, ascending, unique_values);
1758 ll_splice (ll_null (&list), ll_head (&dups), ll_null (&dups));
1759 ll_sort (ll_head (&list), ll_null (&list), compare_elements, &aux_data);
1760 check_list_contents (&list, values, cnt);
1762 free_elements (cnt, elems, NULL, values);
1768 /* Tests ll_sort_unique. */
1770 test_sort_unique (void)
1772 const int max_elems = 7;
1775 for (cnt = 0; cnt <= max_elems; cnt++)
1776 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1778 struct ll_list list;
1779 struct element **elems;
1782 struct element **perm_elems;
1791 allocate_elements (cnt, &list, &elems, NULL, &values);
1792 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1795 for (i = 0; i < cnt; i++)
1797 elems[i]->x = values[i] = j;
1799 if (inc_pat & (1 << i))
1803 unique_values = xnmalloc (unique_cnt, sizeof *unique_values);
1804 for (i = 0; i < unique_cnt; i++)
1805 unique_values[i] = i;
1808 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1809 compare_elements, &aux_data))
1811 struct ll_list perm_list;
1813 extract_values (&list, perm_values, cnt);
1814 ll_init (&perm_list);
1815 for (i = 0; i < cnt; i++)
1817 perm_elems[i]->x = perm_values[i];
1818 perm_elems[i]->y = i;
1819 ll_push_tail (&perm_list, &perm_elems[i]->ll);
1821 ll_sort_unique (ll_head (&perm_list), ll_null (&perm_list), NULL,
1822 compare_elements, &aux_data);
1823 check_list_contents (&perm_list, unique_values, unique_cnt);
1824 check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1825 compare_elements_x_y, &aux_data));
1828 check (perm_cnt == expected_perms (values, cnt));
1830 free_elements (cnt, elems, NULL, values);
1831 free_elements (cnt, perm_elems, NULL, perm_values);
1832 free (unique_values);
1836 /* Tests ll_insert_ordered. */
1838 test_insert_ordered (void)
1840 const int max_elems = 6;
1843 for (cnt = 0; cnt <= max_elems; cnt++)
1844 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1846 struct ll_list list;
1847 struct element **elems;
1850 struct element **perm_elems;
1856 allocate_elements (cnt, &list, &elems, NULL, &values);
1857 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1860 for (i = 0; i < cnt; i++)
1862 elems[i]->x = values[i] = j;
1863 if (inc_pat & (1 << i))
1869 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1870 compare_elements_y, &aux_data))
1872 struct ll_list perm_list;
1874 extract_values (&list, perm_values, cnt);
1875 ll_init (&perm_list);
1876 for (i = 0; i < cnt; i++)
1878 perm_elems[i]->x = perm_values[i];
1879 perm_elems[i]->y = i;
1880 ll_insert_ordered (ll_head (&perm_list), ll_null (&perm_list),
1882 compare_elements, &aux_data);
1884 check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1885 compare_elements_x_y, &aux_data));
1888 check (perm_cnt == factorial (cnt));
1890 free_elements (cnt, elems, NULL, values);
1891 free_elements (cnt, perm_elems, NULL, perm_values);
1895 /* Tests ll_partition. */
1897 test_partition (void)
1899 const int max_elems = 10;
1905 for (cnt = 0; cnt < max_elems; cnt++)
1906 for (r0 = 0; r0 <= cnt; r0++)
1907 for (r1 = r0; r1 <= cnt; r1++)
1908 for (pbase = 0; pbase <= (1u << (r1 - r0)); pbase++)
1910 struct ll_list list;
1911 struct element **elems;
1915 unsigned int pattern = pbase << r0;
1920 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1922 /* Check that ll_find_partition works okay in every
1923 case. We use it after partitioning, too, but that
1924 only tests cases where it returns non-null. */
1925 for (i = r0; i < r1; i++)
1926 if (!(pattern & (1u << i)))
1930 if (pattern & (1u << i))
1932 part_ll = ll_find_partition (elemp[r0], elemp[r1],
1936 check (part_ll == elemp[j]);
1938 check (part_ll == NULL);
1940 /* Figure out expected results. */
1943 for (i = 0; i < r0; i++)
1945 for (i = r0; i < r1; i++)
1946 if (pattern & (1u << i))
1948 for (i = r0; i < r1; i++)
1949 if (!(pattern & (1u << i)))
1951 if (first_false == -1)
1955 if (first_false == -1)
1957 for (i = r1; i < cnt; i++)
1961 /* Partition and check for expected results. */
1962 check (ll_partition (elemp[r0], elemp[r1],
1963 pattern_pred, &pattern)
1964 == elemp[first_false]);
1965 check (ll_find_partition (elemp[r0], elemp[r1],
1966 pattern_pred, &pattern)
1967 == elemp[first_false]);
1968 check_list_contents (&list, values, cnt);
1969 check ((int) ll_count (&list) == cnt);
1971 free_elements (cnt, elems, elemp, values);
1977 /* Runs TEST_FUNCTION and prints a message about NAME. */
1979 run_test (void (*test_function) (void), const char *name)
1990 run_test (test_push_pop, "push/pop");
1991 run_test (test_insert_remove, "insert/remove");
1992 run_test (test_swap, "swap");
1993 run_test (test_swap_range, "swap_range");
1994 run_test (test_remove_range, "remove_range");
1995 run_test (test_remove_equal, "remove_equal");
1996 run_test (test_remove_if, "remove_if");
1997 run_test (test_moved, "moved");
1998 run_test (test_find_equal, "find_equal");
1999 run_test (test_find_if, "find_if");
2000 run_test (test_find_adjacent_equal, "find_adjacent_equal");
2001 run_test (test_count_range, "count_range");
2002 run_test (test_count_equal, "count_equal");
2003 run_test (test_count_if, "count_if");
2004 run_test (test_min_max, "min/max");
2005 run_test (test_lexicographical_compare_3way, "lexicographical_compare_3way");
2006 run_test (test_apply, "apply");
2007 run_test (test_reverse, "reverse");
2008 run_test (test_permutations_no_dups, "permutations (no dups)");
2009 run_test (test_permutations_with_dups, "permutations (with dups)");
2010 run_test (test_merge_no_dups, "merge (no dups)");
2011 run_test (test_merge_with_dups, "merge (with dups)");
2012 run_test (test_sort_exhaustive, "sort (exhaustive)");
2013 run_test (test_sort_stable, "sort (stability)");
2014 run_test (test_sort_subset, "sort (subset)");
2015 run_test (test_sort_big, "sort (big)");
2016 run_test (test_unique, "unique");
2017 run_test (test_sort_unique, "sort_unique");
2018 run_test (test_insert_ordered, "insert_ordered");
2019 run_test (test_partition, "partition");
2027 compile-command: "gcc -Wall -Wstrict-prototypes -Wmissing-prototypes ll.c ll-test.c -o ll-test -g"