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 /* Currently running test. */
46 static const char *test_name;
48 /* Exit with a failure code.
49 (Place a breakpoint on this function while debugging.) */
56 /* If OK is not true, prints a message about failure on the
57 current source file and the given LINE and terminates. */
59 check_func (bool ok, int line)
63 printf ("Check failed in %s test at %s, line %d\n",
64 test_name, __FILE__, line);
69 /* Verifies that EXPR evaluates to true.
70 If not, prints a message citing the calling line number and
72 #define check(EXPR) check_func ((EXPR), __LINE__)
74 /* Prints a message about memory exhaustion and exits with a
79 printf ("virtual memory exhausted\n");
83 /* Allocates and returns N bytes of memory. */
99 /* Allocates and returns N * M bytes of memory. */
101 xnmalloc (size_t n, size_t m)
103 if ((size_t) -1 / m <= n)
105 return xmalloc (n * m);
108 /* List type and support routines. */
110 /* Test data element. */
113 struct ll ll; /* Embedded list element. */
114 int x; /* Primary value. */
115 int y; /* Secondary value. */
120 /* Returns the `struct element' that LL is embedded within. */
121 static struct element *
122 ll_to_element (const struct ll *ll)
124 return ll_data (ll, struct element, ll);
127 /* Prints the elements in LIST. */
129 print_list (struct ll_list *list)
134 for (x = ll_head (list); x != ll_null (list); x = ll_next (x))
136 struct element *e = ll_to_element (x);
137 printf (" %d", e->x);
142 /* Prints the value returned by PREDICATE given auxiliary data
143 AUX for each element in LIST. */
145 print_pred (struct ll_list *list,
146 ll_predicate_func *predicate, void *aux UNUSED)
151 for (x = ll_head (list); x != ll_null (list); x = ll_next (x))
152 printf (" %d", predicate (x, aux));
156 /* Prints the CNT numbers in VALUES. */
158 print_array (int values[], size_t cnt)
163 for (i = 0; i < cnt; i++)
164 printf (" %d", values[i]);
168 /* Compares the `x' values in A and B and returns a strcmp-type
169 return value. Verifies that AUX points to aux_data. */
171 compare_elements (const struct ll *a_, const struct ll *b_, void *aux)
173 const struct element *a = ll_to_element (a_);
174 const struct element *b = ll_to_element (b_);
176 check (aux == &aux_data);
177 return a->x < b->x ? -1 : a->x > b->x;
180 /* Compares the `x' and `y' values in A and B and returns a
181 strcmp-type return value. Verifies that AUX points to
184 compare_elements_x_y (const struct ll *a_, const struct ll *b_, void *aux)
186 const struct element *a = ll_to_element (a_);
187 const struct element *b = ll_to_element (b_);
189 check (aux == &aux_data);
191 return a->x < b->x ? -1 : 1;
192 else if (a->y != b->y)
193 return a->y < b->y ? -1 : 1;
198 /* Compares the `y' values in A and B and returns a strcmp-type
199 return value. Verifies that AUX points to aux_data. */
201 compare_elements_y (const struct ll *a_, const struct ll *b_, void *aux)
203 const struct element *a = ll_to_element (a_);
204 const struct element *b = ll_to_element (b_);
206 check (aux == &aux_data);
207 return a->y < b->y ? -1 : a->y > b->y;
210 /* Returns true if the bit in *PATTERN indicated by `x in
211 *ELEMENT is set, false otherwise. */
213 pattern_pred (const struct ll *element_, void *pattern_)
215 const struct element *element = ll_to_element (element_);
216 unsigned *pattern = pattern_;
218 return (*pattern & (1u << element->x)) != 0;
221 /* Allocates N elements in *ELEMS.
222 Adds the elements to LIST, if it is nonnull.
223 Puts pointers to the elements' list elements in *ELEMP,
224 followed by a pointer to the list null element, if ELEMP is
226 Allocates space for N values in *VALUES, if VALUES is
229 allocate_elements (size_t n,
230 struct ll_list *list,
231 struct element ***elems,
240 *elems = xnmalloc (n, sizeof **elems);
241 for (i = 0; i < n; i++)
243 (*elems)[i] = xmalloc (sizeof ***elems);
245 ll_push_tail (list, &(*elems)[i]->ll);
250 *elemp = xnmalloc (n + 1, sizeof *elemp);
251 for (i = 0; i < n; i++)
252 (*elemp)[i] = &(*elems)[i]->ll;
253 (*elemp)[n] = ll_null (list);
257 *values = xnmalloc (n, sizeof *values);
260 /* Copies the CNT values of `x' from LIST into VALUES[]. */
262 extract_values (struct ll_list *list, int values[], size_t cnt)
266 check (ll_count (list) == cnt);
267 for (x = ll_head (list); x != ll_null (list); x = ll_next (x))
269 struct element *e = ll_to_element (x);
274 /* As allocate_elements, but sets ascending values, starting
275 from 0, in `x' values in *ELEMS and in *VALUES (if
278 allocate_ascending (size_t n,
279 struct ll_list *list,
280 struct element ***elems,
286 allocate_elements (n, list, elems, elemp, values);
288 for (i = 0; i < n; i++)
291 extract_values (list, *values, n);
294 /* As allocate_elements, but sets binary values extracted from
295 successive bits in PATTERN in `x' values in *ELEMS and in
296 *VALUES (if nonnull). */
298 allocate_pattern (size_t n,
300 struct ll_list *list,
301 struct element ***elems,
307 allocate_elements (n, list, elems, elemp, values);
309 for (i = 0; i < n; i++)
310 (*elems)[i]->x = (pattern & (1 << i)) != 0;
312 extract_values (list, *values, n);
315 /* Randomly shuffles the CNT elements in ARRAY, each of which is
316 SIZE bytes in size. */
318 random_shuffle (void *array_, size_t cnt, size_t size)
320 char *array = array_;
321 char *tmp = xmalloc (size);
324 for (i = 0; i < cnt; i++)
326 size_t j = rand () % (cnt - i) + i;
329 memcpy (tmp, array + j * size, size);
330 memcpy (array + j * size, array + i * size, size);
331 memcpy (array + i * size, tmp, size);
338 /* As allocate_ascending, but orders the values randomly. */
340 allocate_random (size_t n,
341 struct ll_list *list,
342 struct element ***elems,
348 allocate_elements (n, list, elems, elemp, values);
350 for (i = 0; i < n; i++)
352 random_shuffle (*elems, n, sizeof **elems);
354 extract_values (list, *values, n);
357 /* Frees the N elements of ELEMS, ELEMP, and VALUES. */
359 free_elements (size_t n,
360 struct element **elems,
366 for (i = 0; i < n; i++)
373 /* Compares A and B and returns a strcmp-type return value. */
375 compare_ints (const void *a_, const void *b_, void *aux UNUSED)
380 return *a < *b ? -1 : *a > *b;
383 /* Compares A and B and returns a strcmp-type return value. */
385 compare_ints_noaux (const void *a_, const void *b_)
390 return *a < *b ? -1 : *a > *b;
393 /* Checks that LIST contains the CNT values in ELEMENTS. */
395 check_list_contents (struct ll_list *list, int elements[], size_t cnt)
400 check ((cnt == 0) == ll_is_empty (list));
402 /* Iterate in forward order. */
403 for (ll = ll_head (list), i = 0; i < cnt; ll = ll_next (ll), i++)
405 struct element *e = ll_to_element (ll);
406 check (elements[i] == e->x);
407 check (ll != ll_null (list));
409 check (ll == ll_null (list));
411 /* Iterate in reverse order. */
412 for (ll = ll_tail (list), i = 0; i < cnt; ll = ll_prev (ll), i++)
414 struct element *e = ll_to_element (ll);
415 check (elements[cnt - i - 1] == e->x);
416 check (ll != ll_null (list));
418 check (ll == ll_null (list));
420 check (ll_count (list) == cnt);
423 /* Lexicographically compares ARRAY1, which contains COUNT1
424 elements of SIZE bytes each, to ARRAY2, which contains COUNT2
425 elements of SIZE bytes, according to COMPARE. Returns a
426 strcmp-type result. AUX is passed to COMPARE as auxiliary
429 lexicographical_compare_3way (const void *array1, size_t count1,
430 const void *array2, size_t count2,
432 int (*compare) (const void *, const void *,
436 const char *first1 = array1;
437 const char *first2 = array2;
438 size_t min_count = count1 < count2 ? count1 : count2;
440 while (min_count > 0)
442 int cmp = compare (first1, first2, aux);
451 return count1 < count2 ? -1 : count1 > count2;
456 /* Tests list push and pop operations. */
460 const int max_elems = 1024;
463 struct element **elems;
468 allocate_elements (max_elems, NULL, &elems, NULL, &values);
472 check_list_contents (&list, NULL, 0);
473 for (i = 0; i < max_elems; i++)
475 values[i] = elems[i]->x = i;
476 ll_push_tail (&list, &elems[i]->ll);
477 check_list_contents (&list, values, i + 1);
480 /* Remove from tail. */
481 for (i = 0; i < max_elems; i++)
483 struct element *e = ll_to_element (ll_pop_tail (&list));
484 check (e->x == max_elems - i - 1);
485 check_list_contents (&list, values, max_elems - i - 1);
489 check_list_contents (&list, NULL, 0);
490 for (i = 0; i < max_elems; i++)
492 values[max_elems - i - 1] = elems[i]->x = max_elems - i - 1;
493 ll_push_head (&list, &elems[i]->ll);
494 check_list_contents (&list, &values[max_elems - i - 1], i + 1);
497 /* Remove from start. */
498 for (i = 0; i < max_elems; i++)
500 struct element *e = ll_to_element (ll_pop_head (&list));
501 check (e->x == (int) i);
502 check_list_contents (&list, &values[i + 1], max_elems - i - 1);
505 free_elements (max_elems, elems, NULL, values);
508 /* Tests insertion and removal at arbitrary positions. */
510 test_insert_remove (void)
512 const int max_elems = 16;
515 for (cnt = 0; cnt < max_elems; cnt++)
517 struct element **elems;
519 int *values = xnmalloc (cnt + 1, sizeof *values);
522 struct element extra;
525 allocate_ascending (cnt, &list, &elems, &elemp, NULL);
527 for (pos = 0; pos <= cnt; pos++)
531 ll_insert (elemp[pos], &extra.ll);
534 for (i = 0; i < pos; i++)
539 check_list_contents (&list, values, cnt + 1);
541 ll_remove (&extra.ll);
543 check_list_contents (&list, values, cnt);
545 free_elements (cnt, elems, elemp, values);
549 /* Tests swapping individual elements. */
553 const int max_elems = 8;
556 for (cnt = 0; cnt <= max_elems; cnt++)
559 struct element **elems;
564 allocate_ascending (cnt, &list, &elems, NULL, &values);
565 check_list_contents (&list, values, cnt);
567 for (i = 0; i < cnt; i++)
568 for (j = 0; j < cnt; j++)
569 for (k = 0; k < 2; k++)
573 ll_swap (&elems[i]->ll, &elems[j]->ll);
575 values[i] = values[j];
577 check_list_contents (&list, values, cnt);
580 free_elements (cnt, elems, NULL, values);
584 /* Tests swapping ranges of list elements. */
586 test_swap_range (void)
588 const int max_elems = 8;
589 int cnt, a0, a1, b0, b1, r;
591 for (cnt = 0; cnt <= max_elems; cnt++)
592 for (a0 = 0; a0 <= cnt; a0++)
593 for (a1 = a0; a1 <= cnt; a1++)
594 for (b0 = a1; b0 <= cnt; b0++)
595 for (b1 = b0; b1 <= cnt; b1++)
596 for (r = 0; r < 2; r++)
599 struct element **elems;
605 allocate_ascending (cnt, &list, &elems, &elemp, &values);
606 check_list_contents (&list, values, cnt);
609 for (i = 0; i < a0; i++)
611 for (i = b0; i < b1; i++)
613 for (i = a1; i < b0; i++)
615 for (i = a0; i < a1; i++)
617 for (i = b1; i < cnt; i++)
622 ll_swap_range (elemp[a0], elemp[a1], elemp[b0], elemp[b1]);
624 ll_swap_range (elemp[b0], elemp[b1], elemp[a0], elemp[a1]);
625 check_list_contents (&list, values, cnt);
627 free_elements (cnt, elems, elemp, values);
631 /* Tests removing ranges of list elements. */
633 test_remove_range (void)
635 const int max_elems = 8;
639 for (cnt = 0; cnt <= max_elems; cnt++)
640 for (r0 = 0; r0 <= cnt; r0++)
641 for (r1 = r0; r1 <= cnt; r1++)
644 struct element **elems;
650 allocate_ascending (cnt, &list, &elems, &elemp, &values);
651 check_list_contents (&list, values, cnt);
654 for (i = 0; i < r0; i++)
656 for (i = r1; i < cnt; i++)
659 ll_remove_range (elemp[r0], elemp[r1]);
660 check_list_contents (&list, values, j);
662 free_elements (cnt, elems, elemp, values);
666 /* Tests ll_remove_equal. */
668 test_remove_equal (void)
670 const int max_elems = 8;
672 int cnt, r0, r1, eq_pat;
674 for (cnt = 0; cnt <= max_elems; cnt++)
675 for (r0 = 0; r0 <= cnt; r0++)
676 for (r1 = r0; r1 <= cnt; r1++)
677 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
680 struct element **elems;
684 struct element to_remove;
688 allocate_elements (cnt, &list, &elems, &elemp, &values);
691 for (i = 0; i < cnt; i++)
693 int x = eq_pat & (1 << i) ? -1 : i;
694 bool delete = x == -1 && r0 <= i && i < r1;
697 values[remaining++] = x;
701 check ((int) ll_remove_equal (elemp[r0], elemp[r1], &to_remove.ll,
702 compare_elements, &aux_data)
704 check_list_contents (&list, values, remaining);
706 free_elements (cnt, elems, elemp, values);
710 /* Tests ll_remove_if. */
712 test_remove_if (void)
714 const int max_elems = 8;
716 int cnt, r0, r1, pattern;
718 for (cnt = 0; cnt <= max_elems; cnt++)
719 for (r0 = 0; r0 <= cnt; r0++)
720 for (r1 = r0; r1 <= cnt; r1++)
721 for (pattern = 0; pattern <= 1 << cnt; pattern++)
724 struct element **elems;
731 allocate_elements (cnt, &list, &elems, &elemp, &values);
734 for (i = 0; i < cnt; i++)
736 bool delete = (pattern & (1 << i)) && r0 <= i && i < r1;
739 values[remaining++] = i;
742 check ((int) ll_remove_if (elemp[r0], elemp[r1],
743 pattern_pred, &pattern)
745 check_list_contents (&list, values, remaining);
747 free_elements (cnt, elems, elemp, values);
751 /* Tests ll_moved. */
755 const int max_elems = 8;
759 for (cnt = 0; cnt <= max_elems; cnt++)
762 struct element **elems;
763 struct element **new_elems;
768 allocate_ascending (cnt, &list, &elems, NULL, &values);
769 allocate_elements (cnt, NULL, &new_elems, NULL, NULL);
770 check_list_contents (&list, values, cnt);
772 for (i = 0; i < cnt; i++)
774 *new_elems[i] = *elems[i];
775 ll_moved (&new_elems[i]->ll);
776 check_list_contents (&list, values, cnt);
779 free_elements (cnt, elems, NULL, values);
780 free_elements (cnt, new_elems, NULL, NULL);
784 /* Tests, via HELPER, a function that looks at list elements
785 equal to some specified element. */
787 test_examine_equal_range (void (*helper) (int r0, int r1, int eq_pat,
791 const int max_elems = 8;
793 int cnt, r0, r1, eq_pat;
795 for (cnt = 0; cnt <= max_elems; cnt++)
796 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
799 struct element **elems;
803 struct element to_find;
807 allocate_ascending (cnt, &list, &elems, &elemp, &values);
809 for (i = 0; i < cnt; i++)
810 if (eq_pat & (1 << i))
811 values[i] = elems[i]->x = -1;
814 for (r0 = 0; r0 <= cnt; r0++)
815 for (r1 = r0; r1 <= cnt; r1++)
816 helper (r0, r1, eq_pat, &to_find.ll, elemp);
818 check_list_contents (&list, values, cnt);
820 free_elements (cnt, elems, elemp, values);
824 /* Tests, via HELPER, a function that looks at list elements for
825 which a given predicate returns true. */
827 test_examine_if_range (void (*helper) (int r0, int r1, int eq_pat,
830 const int max_elems = 8;
832 int cnt, r0, r1, eq_pat;
834 for (cnt = 0; cnt <= max_elems; cnt++)
835 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
838 struct element **elems;
842 allocate_ascending (cnt, &list, &elems, &elemp, &values);
844 for (r0 = 0; r0 <= cnt; r0++)
845 for (r1 = r0; r1 <= cnt; r1++)
846 helper (r0, r1, eq_pat, elemp);
848 check_list_contents (&list, values, cnt);
850 free_elements (cnt, elems, elemp, values);
854 /* Helper function for testing ll_find_equal. */
856 test_find_equal_helper (int r0, int r1, int eq_pat,
857 struct ll *to_find, struct ll **elemp)
862 match = ll_find_equal (elemp[r0], elemp[r1], to_find,
863 compare_elements, &aux_data);
864 for (i = r0; i < r1; i++)
865 if (eq_pat & (1 << i))
868 check (match == elemp[i]);
871 /* Tests ll_find_equal. */
873 test_find_equal (void)
875 test_examine_equal_range (test_find_equal_helper);
878 /* Helper function for testing ll_find_if. */
880 test_find_if_helper (int r0, int r1, int eq_pat, struct ll **elemp)
882 struct ll *match = ll_find_if (elemp[r0], elemp[r1],
883 pattern_pred, &eq_pat);
886 for (i = r0; i < r1; i++)
887 if (eq_pat & (1 << i))
890 check (match == elemp[i]);
893 /* Tests ll_find_if. */
897 test_examine_if_range (test_find_if_helper);
900 /* Tests ll_find_adjacent_equal. */
902 test_find_adjacent_equal (void)
904 const int max_elems = 8;
908 for (cnt = 0; cnt <= max_elems; cnt++)
909 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
912 struct element **elems;
919 allocate_ascending (cnt, &list, &elems, &elemp, &values);
922 for (i = 0; i < cnt - 1; i++)
925 if (eq_pat & (1 << i))
927 values[i] = elems[i]->x = match;
928 values[i + 1] = elems[i + 1]->x = match;
934 for (i = 0; i <= cnt; i++)
936 struct ll *ll1 = ll_find_adjacent_equal (elemp[i], ll_null (&list),
942 ll2 = ll_null (&list);
943 for (j = i; j < cnt - 1; j++)
944 if (eq_pat & (1 << j))
951 check_list_contents (&list, values, cnt);
953 free_elements (cnt, elems, elemp, values);
957 /* Helper function for testing ll_count_range. */
959 test_count_range_helper (int r0, int r1, int eq_pat UNUSED, struct ll **elemp)
961 check ((int) ll_count_range (elemp[r0], elemp[r1]) == r1 - r0);
964 /* Tests ll_count_range. */
966 test_count_range (void)
968 test_examine_if_range (test_count_range_helper);
971 /* Helper function for testing ll_count_equal. */
973 test_count_equal_helper (int r0, int r1, int eq_pat,
974 struct ll *to_find, struct ll **elemp)
979 count1 = ll_count_equal (elemp[r0], elemp[r1], to_find,
980 compare_elements, &aux_data);
982 for (i = r0; i < r1; i++)
983 if (eq_pat & (1 << i))
986 check (count1 == count2);
989 /* Tests ll_count_equal. */
991 test_count_equal (void)
993 test_examine_equal_range (test_count_equal_helper);
996 /* Helper function for testing ll_count_if. */
998 test_count_if_helper (int r0, int r1, int eq_pat, struct ll **elemp)
1004 count1 = ll_count_if (elemp[r0], elemp[r1], pattern_pred, &eq_pat);
1007 for (i = r0; i < r1; i++)
1008 if (eq_pat & (1 << i))
1011 check (count1 == count2);
1014 /* Tests ll_count_if. */
1016 test_count_if (void)
1018 test_examine_if_range (test_count_if_helper);
1023 factorial (unsigned n)
1031 /* Returns the number of permutations of the CNT values in
1032 VALUES. If VALUES contains duplicates, they must be
1035 expected_perms (int *values, size_t cnt)
1040 perm_cnt = factorial (cnt);
1041 for (i = 0; i < cnt; i = j)
1043 for (j = i + 1; j < cnt; j++)
1044 if (values[i] != values[j])
1046 perm_cnt /= factorial (j - i);
1051 /* Tests ll_min and ll_max. */
1055 const int max_elems = 6;
1058 for (cnt = 0; cnt <= max_elems; cnt++)
1060 struct ll_list list;
1061 struct element **elems;
1064 int *new_values = xnmalloc (cnt, sizeof *values);
1068 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1071 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1072 compare_elements, &aux_data))
1078 for (i = 0, x = ll_head (&list); x != ll_null (&list);
1079 x = ll_next (x), i++)
1081 struct element *e = ll_to_element (x);
1083 new_values[i] = e->x;
1085 for (r0 = 0; r0 <= cnt; r0++)
1086 for (r1 = r0; r1 <= cnt; r1++)
1088 struct ll *min = ll_min (elemp[r0], elemp[r1],
1089 compare_elements, &aux_data);
1090 struct ll *max = ll_max (elemp[r0], elemp[r1],
1091 compare_elements, &aux_data);
1094 check (min == elemp[r1]);
1095 check (max == elemp[r1]);
1099 int min_int, max_int;
1102 min_int = max_int = new_values[r0];
1103 for (i = r0; i < r1; i++)
1105 int value = new_values[i];
1106 if (value < min_int)
1108 if (value > max_int)
1111 check (min != elemp[r1]
1112 && ll_to_element (min)->x == min_int);
1113 check (max != elemp[r1]
1114 && ll_to_element (max)->x == max_int);
1119 check (perm_cnt == factorial (cnt));
1120 check_list_contents (&list, values, cnt);
1122 free_elements (cnt, elems, elemp, values);
1127 /* Tests ll_lexicographical_compare_3way. */
1129 test_lexicographical_compare_3way (void)
1131 const int max_elems = 4;
1133 int cnt_a, pat_a, cnt_b, pat_b;
1135 for (cnt_a = 0; cnt_a <= max_elems; cnt_a++)
1136 for (pat_a = 0; pat_a <= 1 << cnt_a; pat_a++)
1137 for (cnt_b = 0; cnt_b <= max_elems; cnt_b++)
1138 for (pat_b = 0; pat_b <= 1 << cnt_b; pat_b++)
1140 struct ll_list list_a, list_b;
1141 struct element **elems_a, **elems_b;
1142 struct ll **elemp_a, **elemp_b;
1143 int *values_a, *values_b;
1147 allocate_pattern (cnt_a, pat_a,
1148 &list_a, &elems_a, &elemp_a, &values_a);
1149 allocate_pattern (cnt_b, pat_b,
1150 &list_b, &elems_b, &elemp_b, &values_b);
1152 for (a0 = 0; a0 <= cnt_a; a0++)
1153 for (a1 = a0; a1 <= cnt_a; a1++)
1154 for (b0 = 0; b0 <= cnt_b; b0++)
1155 for (b1 = b0; b1 <= cnt_b; b1++)
1157 int a_ordering = lexicographical_compare_3way (
1158 values_a + a0, a1 - a0,
1159 values_b + b0, b1 - b0,
1161 compare_ints, NULL);
1163 int b_ordering = ll_lexicographical_compare_3way (
1164 elemp_a[a0], elemp_a[a1],
1165 elemp_b[b0], elemp_b[b1],
1166 compare_elements, &aux_data);
1168 check (a_ordering == b_ordering);
1171 free_elements (cnt_a, elems_a, elemp_a, values_a);
1172 free_elements (cnt_b, elems_b, elemp_b, values_b);
1176 /* Appends the `x' value in element E to the array pointed to by
1177 NEXT_OUTPUT, and advances NEXT_OUTPUT to the next position. */
1179 apply_func (struct ll *e_, void *next_output_)
1181 struct element *e = ll_to_element (e_);
1182 int **next_output = next_output_;
1184 *(*next_output)++ = e->x;
1187 /* Tests ll_apply. */
1191 const int max_elems = 8;
1195 for (cnt = 0; cnt <= max_elems; cnt++)
1196 for (r0 = 0; r0 <= cnt; r0++)
1197 for (r1 = r0; r1 <= cnt; r1++)
1199 struct ll_list list;
1200 struct element **elems;
1209 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1210 check_list_contents (&list, values, cnt);
1212 output = next_output = xnmalloc (cnt, sizeof *output);
1213 ll_apply (elemp[r0], elemp[r1], apply_func, &next_output);
1214 check_list_contents (&list, values, cnt);
1216 check (r1 - r0 == next_output - output);
1217 for (i = 0; i < r1 - r0; i++)
1218 check (output[i] == r0 + i);
1220 free_elements (cnt, elems, elemp, values);
1225 /* Tests ll_reverse. */
1229 const int max_elems = 8;
1233 for (cnt = 0; cnt <= max_elems; cnt++)
1234 for (r0 = 0; r0 <= cnt; r0++)
1235 for (r1 = r0; r1 <= cnt; r1++)
1237 struct ll_list list;
1238 struct element **elems;
1244 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1245 check_list_contents (&list, values, cnt);
1248 for (i = 0; i < r0; i++)
1250 for (i = r1 - 1; i >= r0; i--)
1252 for (i = r1; i < cnt; i++)
1255 ll_reverse (elemp[r0], elemp[r1]);
1256 check_list_contents (&list, values, cnt);
1258 free_elements (cnt, elems, elemp, values);
1262 /* Tests ll_next_permutation and ll_prev_permutation when the
1263 permuted values have no duplicates. */
1265 test_permutations_no_dups (void)
1267 const int max_elems = 8;
1270 for (cnt = 0; cnt <= max_elems; cnt++)
1272 struct ll_list list;
1273 struct element **elems;
1275 int *old_values = xnmalloc (cnt, sizeof *values);
1276 int *new_values = xnmalloc (cnt, sizeof *values);
1280 allocate_ascending (cnt, &list, &elems, NULL, &values);
1283 extract_values (&list, old_values, cnt);
1284 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1285 compare_elements, &aux_data))
1287 extract_values (&list, new_values, cnt);
1288 check (lexicographical_compare_3way (new_values, cnt,
1291 compare_ints, NULL) > 0);
1292 memcpy (old_values, new_values, (cnt) * sizeof *old_values);
1295 check (perm_cnt == factorial (cnt));
1296 check_list_contents (&list, values, cnt);
1299 ll_reverse (ll_head (&list), ll_null (&list));
1300 extract_values (&list, old_values, cnt);
1301 while (ll_prev_permutation (ll_head (&list), ll_null (&list),
1302 compare_elements, &aux_data))
1304 extract_values (&list, new_values, cnt);
1305 check (lexicographical_compare_3way (new_values, cnt,
1308 compare_ints, NULL) < 0);
1309 memcpy (old_values, new_values, (cnt) * sizeof *old_values);
1312 check (perm_cnt == factorial (cnt));
1313 ll_reverse (ll_head (&list), ll_null (&list));
1314 check_list_contents (&list, values, cnt);
1316 free_elements (cnt, elems, NULL, values);
1322 /* Tests ll_next_permutation and ll_prev_permutation when the
1323 permuted values contain duplicates. */
1325 test_permutations_with_dups (void)
1327 const int max_elems = 8;
1328 const int max_dup = 3;
1329 const int repetitions = 1024;
1333 for (repeat = 0; repeat < repetitions; repeat++)
1334 for (cnt = 0; cnt < max_elems; cnt++)
1336 struct ll_list list;
1337 struct element **elems;
1339 int *old_values = xnmalloc (max_elems, sizeof *values);
1340 int *new_values = xnmalloc (max_elems, sizeof *values);
1342 unsigned permutation_cnt;
1346 allocate_elements (cnt, &list, &elems, NULL, &values);
1351 int max = left < max_dup ? left : max_dup;
1352 int n = rand () % max + 1;
1355 int idx = cnt - left--;
1356 values[idx] = elems[idx]->x = value;
1361 permutation_cnt = 1;
1362 extract_values (&list, old_values, cnt);
1363 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1364 compare_elements, &aux_data))
1366 extract_values (&list, new_values, cnt);
1367 check (lexicographical_compare_3way (new_values, cnt,
1370 compare_ints, NULL) > 0);
1371 memcpy (old_values, new_values, cnt * sizeof *old_values);
1374 check (permutation_cnt == expected_perms (values, cnt));
1375 check_list_contents (&list, values, cnt);
1377 permutation_cnt = 1;
1378 ll_reverse (ll_head (&list), ll_null (&list));
1379 extract_values (&list, old_values, cnt);
1380 while (ll_prev_permutation (ll_head (&list), ll_null (&list),
1381 compare_elements, &aux_data))
1383 extract_values (&list, new_values, cnt);
1384 check (lexicographical_compare_3way (new_values, cnt,
1387 compare_ints, NULL) < 0);
1390 ll_reverse (ll_head (&list), ll_null (&list));
1391 check (permutation_cnt == expected_perms (values, cnt));
1392 check_list_contents (&list, values, cnt);
1394 free_elements (cnt, elems, NULL, values);
1400 /* Tests ll_merge when no equal values are to be merged. */
1402 test_merge_no_dups (void)
1404 const int max_elems = 8;
1405 const int max_filler = 3;
1407 int merge_cnt, pattern, pfx, gap, sfx, order;
1409 for (merge_cnt = 0; merge_cnt < max_elems; merge_cnt++)
1410 for (pattern = 0; pattern <= (1 << merge_cnt); pattern++)
1411 for (pfx = 0; pfx < max_filler; pfx++)
1412 for (gap = 0; gap < max_filler; gap++)
1413 for (sfx = 0; sfx < max_filler; sfx++)
1414 for (order = 0; order < 2; order++)
1416 struct ll_list list;
1417 struct element **elems;
1421 int list_cnt = pfx + merge_cnt + gap + sfx;
1425 allocate_elements (list_cnt, &list,
1426 &elems, &elemp, &values);
1429 for (i = 0; i < pfx; i++)
1430 elems[j++]->x = 100 + i;
1432 for (i = 0; i < merge_cnt; i++)
1433 if (pattern & (1u << i))
1436 for (i = 0; i < gap; i++)
1437 elems[j++]->x = 200 + i;
1439 for (i = 0; i < merge_cnt; i++)
1440 if (!(pattern & (1u << i)))
1443 for (i = 0; i < sfx; i++)
1444 elems[j++]->x = 300 + i;
1445 check (list_cnt == j);
1448 for (i = 0; i < pfx; i++)
1449 values[j++] = 100 + i;
1451 for (i = 0; i < merge_cnt; i++)
1453 for (i = 0; i < gap; i++)
1454 values[j++] = 200 + i;
1456 for (i = 0; i < merge_cnt; i++)
1458 for (i = 0; i < sfx; i++)
1459 values[j++] = 300 + i;
1460 check (list_cnt == j);
1463 ll_merge (elemp[a0], elemp[a1], elemp[b0], elemp[b1],
1464 compare_elements, &aux_data);
1466 ll_merge (elemp[b0], elemp[b1], elemp[a0], elemp[a1],
1467 compare_elements, &aux_data);
1469 check_list_contents (&list, values, list_cnt);
1471 free_elements (list_cnt, elems, elemp, values);
1475 /* Tests ll_merge when equal values are to be merged. */
1477 test_merge_with_dups (void)
1479 const int max_elems = 8;
1481 int cnt, merge_pat, inc_pat, order;
1483 for (cnt = 0; cnt <= max_elems; cnt++)
1484 for (merge_pat = 0; merge_pat <= (1 << cnt); merge_pat++)
1485 for (inc_pat = 0; inc_pat <= (1 << cnt); inc_pat++)
1486 for (order = 0; order < 2; order++)
1488 struct ll_list list;
1489 struct element **elems;
1496 allocate_elements (cnt, &list, &elems, &elemp, &values);
1499 for (i = k = 0; i < cnt; i++)
1501 if (merge_pat & (1u << i))
1503 if (inc_pat & (1u << i))
1507 for (i = k = 0; i < cnt; i++)
1509 if (!(merge_pat & (1u << i)))
1511 if (inc_pat & (1u << i))
1518 for (i = 0; i < cnt; i++)
1523 for (i = 0; i < mid; i++)
1524 elems[i]->y = 100 + i;
1525 for (i = mid; i < cnt; i++)
1530 for (i = k = 0; i < cnt; i++)
1533 if (inc_pat & (1u << i))
1539 ll_merge (elemp[0], elemp[mid], elemp[mid], elemp[cnt],
1540 compare_elements, &aux_data);
1542 ll_merge (elemp[mid], elemp[cnt], elemp[0], elemp[mid],
1543 compare_elements, &aux_data);
1545 check_list_contents (&list, values, cnt);
1546 check (ll_is_sorted (ll_head (&list), ll_null (&list),
1547 compare_elements_x_y, &aux_data));
1549 free_elements (cnt, elems, elemp, values);
1553 /* Tests ll_sort on all permutations up to a maximum number of
1556 test_sort_exhaustive (void)
1558 const int max_elems = 8;
1561 for (cnt = 0; cnt <= max_elems; cnt++)
1563 struct ll_list list;
1564 struct element **elems;
1567 struct element **perm_elems;
1572 allocate_ascending (cnt, &list, &elems, NULL, &values);
1573 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1576 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1577 compare_elements, &aux_data))
1579 struct ll_list perm_list;
1582 extract_values (&list, perm_values, cnt);
1583 ll_init (&perm_list);
1584 for (j = 0; j < cnt; j++)
1586 perm_elems[j]->x = perm_values[j];
1587 ll_push_tail (&perm_list, &perm_elems[j]->ll);
1589 ll_sort (ll_head (&perm_list), ll_null (&perm_list),
1590 compare_elements, &aux_data);
1591 check_list_contents (&perm_list, values, cnt);
1592 check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1593 compare_elements, &aux_data));
1596 check (perm_cnt == factorial (cnt));
1598 free_elements (cnt, elems, NULL, values);
1599 free_elements (cnt, perm_elems, NULL, perm_values);
1603 /* Tests that ll_sort is stable in the presence of equal
1606 test_sort_stable (void)
1608 const int max_elems = 6;
1611 for (cnt = 0; cnt <= max_elems; cnt++)
1612 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1614 struct ll_list list;
1615 struct element **elems;
1618 struct element **perm_elems;
1624 allocate_elements (cnt, &list, &elems, NULL, &values);
1625 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1628 for (i = 0; i < cnt; i++)
1630 elems[i]->x = values[i] = j;
1631 if (inc_pat & (1 << i))
1637 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1638 compare_elements_y, &aux_data))
1640 struct ll_list perm_list;
1642 extract_values (&list, perm_values, cnt);
1643 ll_init (&perm_list);
1644 for (i = 0; i < cnt; i++)
1646 perm_elems[i]->x = perm_values[i];
1647 perm_elems[i]->y = i;
1648 ll_push_tail (&perm_list, &perm_elems[i]->ll);
1650 ll_sort (ll_head (&perm_list), ll_null (&perm_list),
1651 compare_elements, &aux_data);
1652 check_list_contents (&perm_list, values, cnt);
1653 check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1654 compare_elements_x_y, &aux_data));
1657 check (perm_cnt == factorial (cnt));
1659 free_elements (cnt, elems, NULL, values);
1660 free_elements (cnt, perm_elems, NULL, perm_values);
1664 /* Tests that ll_sort does not disturb elements outside the
1667 test_sort_subset (void)
1669 const int max_elems = 8;
1671 int cnt, r0, r1, repeat;
1673 for (cnt = 0; cnt <= max_elems; cnt++)
1674 for (repeat = 0; repeat < 100; repeat++)
1675 for (r0 = 0; r0 <= cnt; r0++)
1676 for (r1 = r0; r1 <= cnt; r1++)
1678 struct ll_list list;
1679 struct element **elems;
1683 allocate_random (cnt, &list, &elems, &elemp, &values);
1685 qsort (&values[r0], r1 - r0, sizeof *values, compare_ints_noaux);
1686 ll_sort (elemp[r0], elemp[r1], compare_elements, &aux_data);
1687 check_list_contents (&list, values, cnt);
1689 free_elements (cnt, elems, elemp, values);
1693 /* Tests that ll_sort works with large lists. */
1695 test_sort_big (void)
1697 const int max_elems = 1024;
1701 for (cnt = 0; cnt < max_elems; cnt++)
1703 struct ll_list list;
1704 struct element **elems;
1707 allocate_random (cnt, &list, &elems, NULL, &values);
1709 qsort (values, cnt, sizeof *values, compare_ints_noaux);
1710 ll_sort (ll_head (&list), ll_null (&list), compare_elements, &aux_data);
1711 check_list_contents (&list, values, cnt);
1713 free_elements (cnt, elems, NULL, values);
1717 /* Tests ll_unique. */
1721 const int max_elems = 10;
1723 int *ascending = xnmalloc (max_elems, sizeof *ascending);
1725 int cnt, inc_pat, i, j, unique_values;
1727 for (i = 0; i < max_elems; i++)
1730 for (cnt = 0; cnt < max_elems; cnt++)
1731 for (inc_pat = 0; inc_pat < (1 << cnt); inc_pat++)
1733 struct ll_list list, dups;
1734 struct element **elems;
1737 allocate_elements (cnt, &list, &elems, NULL, &values);
1739 j = unique_values = 0;
1740 for (i = 0; i < cnt; i++)
1742 unique_values = j + 1;
1743 elems[i]->x = values[i] = j;
1744 if (inc_pat & (1 << i))
1747 check_list_contents (&list, values, cnt);
1750 check (ll_unique (ll_head (&list), ll_null (&list), ll_null (&dups),
1751 compare_elements, &aux_data)
1752 == (size_t) unique_values);
1753 check_list_contents (&list, ascending, unique_values);
1755 ll_splice (ll_null (&list), ll_head (&dups), ll_null (&dups));
1756 ll_sort (ll_head (&list), ll_null (&list), compare_elements, &aux_data);
1757 check_list_contents (&list, values, cnt);
1759 free_elements (cnt, elems, NULL, values);
1765 /* Tests ll_sort_unique. */
1767 test_sort_unique (void)
1769 const int max_elems = 7;
1772 for (cnt = 0; cnt <= max_elems; cnt++)
1773 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1775 struct ll_list list;
1776 struct element **elems;
1779 struct element **perm_elems;
1788 allocate_elements (cnt, &list, &elems, NULL, &values);
1789 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1792 for (i = 0; i < cnt; i++)
1794 elems[i]->x = values[i] = j;
1796 if (inc_pat & (1 << i))
1800 unique_values = xnmalloc (unique_cnt, sizeof *unique_values);
1801 for (i = 0; i < unique_cnt; i++)
1802 unique_values[i] = i;
1805 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1806 compare_elements, &aux_data))
1808 struct ll_list perm_list;
1810 extract_values (&list, perm_values, cnt);
1811 ll_init (&perm_list);
1812 for (i = 0; i < cnt; i++)
1814 perm_elems[i]->x = perm_values[i];
1815 perm_elems[i]->y = i;
1816 ll_push_tail (&perm_list, &perm_elems[i]->ll);
1818 ll_sort_unique (ll_head (&perm_list), ll_null (&perm_list), NULL,
1819 compare_elements, &aux_data);
1820 check_list_contents (&perm_list, unique_values, unique_cnt);
1821 check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1822 compare_elements_x_y, &aux_data));
1825 check (perm_cnt == expected_perms (values, cnt));
1827 free_elements (cnt, elems, NULL, values);
1828 free_elements (cnt, perm_elems, NULL, perm_values);
1829 free (unique_values);
1833 /* Tests ll_insert_ordered. */
1835 test_insert_ordered (void)
1837 const int max_elems = 6;
1840 for (cnt = 0; cnt <= max_elems; cnt++)
1841 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1843 struct ll_list list;
1844 struct element **elems;
1847 struct element **perm_elems;
1853 allocate_elements (cnt, &list, &elems, NULL, &values);
1854 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1857 for (i = 0; i < cnt; i++)
1859 elems[i]->x = values[i] = j;
1860 if (inc_pat & (1 << i))
1866 while (ll_next_permutation (ll_head (&list), ll_null (&list),
1867 compare_elements_y, &aux_data))
1869 struct ll_list perm_list;
1871 extract_values (&list, perm_values, cnt);
1872 ll_init (&perm_list);
1873 for (i = 0; i < cnt; i++)
1875 perm_elems[i]->x = perm_values[i];
1876 perm_elems[i]->y = i;
1877 ll_insert_ordered (ll_head (&perm_list), ll_null (&perm_list),
1879 compare_elements, &aux_data);
1881 check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1882 compare_elements_x_y, &aux_data));
1885 check (perm_cnt == factorial (cnt));
1887 free_elements (cnt, elems, NULL, values);
1888 free_elements (cnt, perm_elems, NULL, perm_values);
1892 /* Tests ll_partition. */
1894 test_partition (void)
1896 const int max_elems = 10;
1902 for (cnt = 0; cnt < max_elems; cnt++)
1903 for (r0 = 0; r0 <= cnt; r0++)
1904 for (r1 = r0; r1 <= cnt; r1++)
1905 for (pbase = 0; pbase <= (1u << (r1 - r0)); pbase++)
1907 struct ll_list list;
1908 struct element **elems;
1912 unsigned pattern = pbase << r0;
1917 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1919 /* Check that ll_find_partition works okay in every
1920 case. We use it after partitioning, too, but that
1921 only tests cases where it returns non-null. */
1922 for (i = r0; i < r1; i++)
1923 if (!(pattern & (1u << i)))
1927 if (pattern & (1u << i))
1929 part_ll = ll_find_partition (elemp[r0], elemp[r1],
1933 check (part_ll == elemp[j]);
1935 check (part_ll == NULL);
1937 /* Figure out expected results. */
1940 for (i = 0; i < r0; i++)
1942 for (i = r0; i < r1; i++)
1943 if (pattern & (1u << i))
1945 for (i = r0; i < r1; i++)
1946 if (!(pattern & (1u << i)))
1948 if (first_false == -1)
1952 if (first_false == -1)
1954 for (i = r1; i < cnt; i++)
1958 /* Partition and check for expected results. */
1959 check (ll_partition (elemp[r0], elemp[r1],
1960 pattern_pred, &pattern)
1961 == elemp[first_false]);
1962 check (ll_find_partition (elemp[r0], elemp[r1],
1963 pattern_pred, &pattern)
1964 == elemp[first_false]);
1965 check_list_contents (&list, values, cnt);
1966 check ((int) ll_count (&list) == cnt);
1968 free_elements (cnt, elems, elemp, values);
1974 /* Runs TEST_FUNCTION and prints a message about NAME. */
1976 run_test (void (*test_function) (void), const char *name)
1987 run_test (test_push_pop, "push/pop");
1988 run_test (test_insert_remove, "insert/remove");
1989 run_test (test_swap, "swap");
1990 run_test (test_swap_range, "swap_range");
1991 run_test (test_remove_range, "remove_range");
1992 run_test (test_remove_equal, "remove_equal");
1993 run_test (test_remove_if, "remove_if");
1994 run_test (test_moved, "moved");
1995 run_test (test_find_equal, "find_equal");
1996 run_test (test_find_if, "find_if");
1997 run_test (test_find_adjacent_equal, "find_adjacent_equal");
1998 run_test (test_count_range, "count_range");
1999 run_test (test_count_equal, "count_equal");
2000 run_test (test_count_if, "count_if");
2001 run_test (test_min_max, "min/max");
2002 run_test (test_lexicographical_compare_3way, "lexicographical_compare_3way");
2003 run_test (test_apply, "apply");
2004 run_test (test_reverse, "reverse");
2005 run_test (test_permutations_no_dups, "permutations (no dups)");
2006 run_test (test_permutations_with_dups, "permutations (with dups)");
2007 run_test (test_merge_no_dups, "merge (no dups)");
2008 run_test (test_merge_with_dups, "merge (with dups)");
2009 run_test (test_sort_exhaustive, "sort (exhaustive)");
2010 run_test (test_sort_stable, "sort (stability)");
2011 run_test (test_sort_subset, "sort (subset)");
2012 run_test (test_sort_big, "sort (big)");
2013 run_test (test_unique, "unique");
2014 run_test (test_sort_unique, "sort_unique");
2015 run_test (test_insert_ordered, "insert_ordered");
2016 run_test (test_partition, "partition");
2024 compile-command: "gcc -Wall -Wstrict-prototypes -Wmissing-prototypes ll.c ll-test.c -o ll-test -g"