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 llx_* 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 llx.c and llx.h. "valgrind --leak-check=yes
23 --show-reachable=yes" should give a clean report.
25 This test program depends only on ll.c, llx.c, and the
28 See ll-test.c for a similar program for the ll_* routines. */
30 #include <libpspp/llx.h>
36 /* Support preliminaries. */
37 #if __GNUC__ >= 2 && !defined UNUSED
38 #define UNUSED __attribute__ ((unused))
43 /* Currently running test. */
44 static const char *test_name;
46 /* Exit with a failure code.
47 (Place a breakpoint on this function while debugging.) */
54 /* If OK is not true, prints a message about failure on the
55 current source file and the given LINE and terminates. */
57 check_func (bool ok, int line)
61 printf ("Check failed in %s test at %s, line %d\n",
62 test_name, __FILE__, line);
67 /* Verifies that EXPR evaluates to true.
68 If not, prints a message citing the calling line number and
70 #define check(EXPR) check_func ((EXPR), __LINE__)
72 /* Prints a message about memory exhaustion and exits with a
77 printf ("virtual memory exhausted\n");
81 /* Allocates and returns N bytes of memory. */
97 /* Allocates and returns N * M bytes of memory. */
99 xnmalloc (size_t n, size_t m)
101 if ((size_t) -1 / m <= n)
103 return xmalloc (n * m);
106 /* Always returns a null pointer, failing allocation. */
108 null_allocate_node (void *aux UNUSED)
115 null_release_node (struct llx *llx UNUSED, void *aux UNUSED)
119 /* Memory manager that fails all allocations and does nothing on
121 static const struct llx_manager llx_null_mgr =
128 /* List type and support routines. */
130 /* Test data element. */
133 int x; /* Primary value. */
134 int y; /* Secondary value. */
139 /* Prints the elements in LIST. */
141 print_list (struct llx_list *list)
146 for (x = llx_head (list); x != llx_null (list); x = llx_next (x))
148 const struct element *e = llx_data (x);
149 printf (" %d", e->x);
154 /* Prints the value returned by PREDICATE given auxiliary data
155 AUX for each element in LIST. */
157 print_pred (struct llx_list *list,
158 llx_predicate_func *predicate, void *aux UNUSED)
163 for (x = llx_head (list); x != llx_null (list); x = llx_next (x))
164 printf (" %d", predicate (x, aux));
168 /* Prints the CNT numbers in VALUES. */
170 print_array (int values[], size_t cnt)
175 for (i = 0; i < cnt; i++)
176 printf (" %d", values[i]);
180 /* Compares the `x' values in A and B and returns a strcmp-type
181 return value. Verifies that AUX points to aux_data. */
183 compare_elements (const void *a_, const void *b_, void *aux)
185 const struct element *a = a_;
186 const struct element *b = b_;
188 check (aux == &aux_data);
189 return a->x < b->x ? -1 : a->x > b->x;
192 /* Compares the `x' and `y' values in A and B and returns a
193 strcmp-type return value. Verifies that AUX points to
196 compare_elements_x_y (const void *a_, const void *b_, void *aux)
198 const struct element *a = a_;
199 const struct element *b = b_;
201 check (aux == &aux_data);
203 return a->x < b->x ? -1 : 1;
204 else if (a->y != b->y)
205 return a->y < b->y ? -1 : 1;
210 /* Compares the `y' values in A and B and returns a strcmp-type
211 return value. Verifies that AUX points to aux_data. */
213 compare_elements_y (const void *a_, const void *b_, void *aux)
215 const struct element *a = a_;
216 const struct element *b = b_;
218 check (aux == &aux_data);
219 return a->y < b->y ? -1 : a->y > b->y;
222 /* Returns true if the bit in *PATTERN indicated by `x in
223 *ELEMENT is set, false otherwise. */
225 pattern_pred (const void *element_, void *pattern_)
227 const struct element *element = element_;
228 unsigned *pattern = pattern_;
230 return (*pattern & (1u << element->x)) != 0;
233 /* Allocates N elements in *ELEMS.
234 Adds the elements to LIST, if it is nonnull.
235 Puts pointers to the elements' list elements in *ELEMP,
236 followed by a pointer to the list null element, if ELEMP is
238 Allocates space for N values in *VALUES, if VALUES is
241 allocate_elements (size_t n,
242 struct llx_list *list,
243 struct element ***elems,
252 *elems = xnmalloc (n, sizeof **elems);
255 *elemp = xnmalloc (n + 1, sizeof *elemp);
256 (*elemp)[n] = llx_null (list);
259 for (i = 0; i < n; i++)
261 (*elems)[i] = xmalloc (sizeof ***elems);
264 struct llx *llx = llx_push_tail (list, (*elems)[i], &llx_malloc_mgr);
271 *values = xnmalloc (n, sizeof *values);
274 /* Copies the CNT values of `x' from LIST into VALUES[]. */
276 extract_values (struct llx_list *list, int values[], size_t cnt)
280 check (llx_count (list) == cnt);
281 for (x = llx_head (list); x != llx_null (list); x = llx_next (x))
283 struct element *e = llx_data (x);
288 /* As allocate_elements, but sets ascending values, starting
289 from 0, in `x' values in *ELEMS and in *VALUES (if
292 allocate_ascending (size_t n,
293 struct llx_list *list,
294 struct element ***elems,
300 allocate_elements (n, list, elems, elemp, values);
302 for (i = 0; i < n; i++)
305 extract_values (list, *values, n);
308 /* As allocate_elements, but sets binary values extracted from
309 successive bits in PATTERN in `x' values in *ELEMS and in
310 *VALUES (if nonnull). */
312 allocate_pattern (size_t n,
314 struct llx_list *list,
315 struct element ***elems,
321 allocate_elements (n, list, elems, elemp, values);
323 for (i = 0; i < n; i++)
324 (*elems)[i]->x = (pattern & (1 << i)) != 0;
326 extract_values (list, *values, n);
329 /* Randomly shuffles the CNT elements in ARRAY, each of which is
330 SIZE bytes in size. */
332 random_shuffle (void *array_, size_t cnt, size_t size)
334 char *array = array_;
335 char *tmp = xmalloc (size);
338 for (i = 0; i < cnt; i++)
340 size_t j = rand () % (cnt - i) + i;
343 memcpy (tmp, array + j * size, size);
344 memcpy (array + j * size, array + i * size, size);
345 memcpy (array + i * size, tmp, size);
352 /* As allocate_ascending, but orders the values randomly. */
354 allocate_random (size_t n,
355 struct llx_list *list,
356 struct element ***elems,
362 allocate_elements (n, list, elems, elemp, values);
364 for (i = 0; i < n; i++)
366 random_shuffle (*elems, n, sizeof **elems);
368 extract_values (list, *values, n);
371 /* Frees LIST, the N elements of ELEMS, ELEMP, and VALUES. */
373 free_elements (size_t n,
374 struct llx_list *list,
375 struct element **elems,
382 llx_destroy (list, NULL, NULL, &llx_malloc_mgr);
383 for (i = 0; i < n; i++)
390 /* Compares A and B and returns a strcmp-type return value. */
392 compare_ints (const void *a_, const void *b_, void *aux UNUSED)
397 return *a < *b ? -1 : *a > *b;
400 /* Compares A and B and returns a strcmp-type return value. */
402 compare_ints_noaux (const void *a_, const void *b_)
407 return *a < *b ? -1 : *a > *b;
410 /* Checks that LIST contains the CNT values in ELEMENTS. */
412 check_list_contents (struct llx_list *list, int elements[], size_t cnt)
417 check ((cnt == 0) == llx_is_empty (list));
419 /* Iterate in forward order. */
420 for (llx = llx_head (list), i = 0; i < cnt; llx = llx_next (llx), i++)
422 struct element *e = llx_data (llx);
423 check (elements[i] == e->x);
424 check (llx != llx_null (list));
426 check (llx == llx_null (list));
428 /* Iterate in reverse order. */
429 for (llx = llx_tail (list), i = 0; i < cnt; llx = llx_prev (llx), i++)
431 struct element *e = llx_data (llx);
432 check (elements[cnt - i - 1] == e->x);
433 check (llx != llx_null (list));
435 check (llx == llx_null (list));
437 check (llx_count (list) == cnt);
440 /* Lexicographicallxy compares ARRAY1, which contains COUNT1
441 elements of SIZE bytes each, to ARRAY2, which contains COUNT2
442 elements of SIZE bytes, according to COMPARE. Returns a
443 strcmp-type result. AUX is passed to COMPARE as auxiliary
446 lexicographical_compare_3way (const void *array1, size_t count1,
447 const void *array2, size_t count2,
449 int (*compare) (const void *, const void *,
453 const char *first1 = array1;
454 const char *first2 = array2;
455 size_t min_count = count1 < count2 ? count1 : count2;
457 while (min_count > 0)
459 int cmp = compare (first1, first2, aux);
468 return count1 < count2 ? -1 : count1 > count2;
473 /* Tests list push and pop operations. */
477 const int max_elems = 1024;
479 struct llx_list list;
480 struct element **elems;
485 allocate_elements (max_elems, NULL, &elems, NULL, &values);
489 check_list_contents (&list, NULL, 0);
490 for (i = 0; i < max_elems; i++)
492 values[i] = elems[i]->x = i;
493 llx_push_tail (&list, elems[i], &llx_malloc_mgr);
494 check_list_contents (&list, values, i + 1);
497 /* Remove from tail. */
498 for (i = 0; i < max_elems; i++)
500 struct element *e = llx_pop_tail (&list, &llx_malloc_mgr);
501 check (e->x == max_elems - i - 1);
502 check_list_contents (&list, values, max_elems - i - 1);
506 check_list_contents (&list, NULL, 0);
507 for (i = 0; i < max_elems; i++)
509 values[max_elems - i - 1] = elems[i]->x = max_elems - i - 1;
510 llx_push_head (&list, elems[i], &llx_malloc_mgr);
511 check_list_contents (&list, &values[max_elems - i - 1], i + 1);
514 /* Remove from start. */
515 for (i = 0; i < max_elems; i++)
517 struct element *e = llx_pop_head (&list, &llx_malloc_mgr);
518 check (e->x == (int) i);
519 check_list_contents (&list, &values[i + 1], max_elems - i - 1);
522 free_elements (max_elems, &list, elems, NULL, values);
525 /* Tests insertion and removal at arbitrary positions. */
527 test_insert_remove (void)
529 const int max_elems = 16;
532 for (cnt = 0; cnt < max_elems; cnt++)
534 struct element **elems;
536 int *values = xnmalloc (cnt + 1, sizeof *values);
538 struct llx_list list;
539 struct element extra;
540 struct llx *extra_llx;
543 allocate_ascending (cnt, &list, &elems, &elemp, NULL);
545 for (pos = 0; pos <= cnt; pos++)
549 extra_llx = llx_insert (elemp[pos], &extra, &llx_malloc_mgr);
550 check (extra_llx != NULL);
553 for (i = 0; i < pos; i++)
558 check_list_contents (&list, values, cnt + 1);
560 llx_remove (extra_llx, &llx_malloc_mgr);
562 check_list_contents (&list, values, cnt);
564 free_elements (cnt, &list, elems, elemp, values);
568 /* Tests swapping individual elements. */
572 const int max_elems = 8;
575 for (cnt = 0; cnt <= max_elems; cnt++)
577 struct llx_list list;
578 struct element **elems;
584 allocate_ascending (cnt, &list, &elems, &elemp, &values);
585 check_list_contents (&list, values, cnt);
587 for (i = 0; i < cnt; i++)
588 for (j = 0; j < cnt; j++)
589 for (k = 0; k < 2; k++)
593 llx_swap (elemp[i], elemp[j]);
595 values[i] = values[j];
597 check_list_contents (&list, values, cnt);
600 free_elements (cnt, &list, elems, elemp, values);
604 /* Tests swapping ranges of list elements. */
606 test_swap_range (void)
608 const int max_elems = 8;
609 int cnt, a0, a1, b0, b1, r;
611 for (cnt = 0; cnt <= max_elems; cnt++)
612 for (a0 = 0; a0 <= cnt; a0++)
613 for (a1 = a0; a1 <= cnt; a1++)
614 for (b0 = a1; b0 <= cnt; b0++)
615 for (b1 = b0; b1 <= cnt; b1++)
616 for (r = 0; r < 2; r++)
618 struct llx_list list;
619 struct element **elems;
625 allocate_ascending (cnt, &list, &elems, &elemp, &values);
626 check_list_contents (&list, values, cnt);
629 for (i = 0; i < a0; i++)
631 for (i = b0; i < b1; i++)
633 for (i = a1; i < b0; i++)
635 for (i = a0; i < a1; i++)
637 for (i = b1; i < cnt; i++)
642 llx_swap_range (elemp[a0], elemp[a1], elemp[b0], elemp[b1]);
644 llx_swap_range (elemp[b0], elemp[b1], elemp[a0], elemp[a1]);
645 check_list_contents (&list, values, cnt);
647 free_elements (cnt, &list, elems, elemp, values);
651 /* Tests removing ranges of list elements. */
653 test_remove_range (void)
655 const int max_elems = 8;
659 for (cnt = 0; cnt <= max_elems; cnt++)
660 for (r0 = 0; r0 <= cnt; r0++)
661 for (r1 = r0; r1 <= cnt; r1++)
663 struct llx_list list;
664 struct element **elems;
670 allocate_ascending (cnt, &list, &elems, &elemp, &values);
671 check_list_contents (&list, values, cnt);
674 for (i = 0; i < r0; i++)
676 for (i = r1; i < cnt; i++)
679 llx_remove_range (elemp[r0], elemp[r1], &llx_malloc_mgr);
680 check_list_contents (&list, values, j);
682 free_elements (cnt, &list, elems, elemp, values);
686 /* Tests llx_remove_equal. */
688 test_remove_equal (void)
690 const int max_elems = 8;
692 int cnt, r0, r1, eq_pat;
694 for (cnt = 0; cnt <= max_elems; cnt++)
695 for (r0 = 0; r0 <= cnt; r0++)
696 for (r1 = r0; r1 <= cnt; r1++)
697 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
699 struct llx_list list;
700 struct element **elems;
704 struct element to_remove;
708 allocate_elements (cnt, &list, &elems, &elemp, &values);
711 for (i = 0; i < cnt; i++)
713 int x = eq_pat & (1 << i) ? -1 : i;
714 bool delete = x == -1 && r0 <= i && i < r1;
717 values[remaining++] = x;
721 check ((int) llx_remove_equal (elemp[r0], elemp[r1], &to_remove,
722 compare_elements, &aux_data,
725 check_list_contents (&list, values, remaining);
727 free_elements (cnt, &list, elems, elemp, values);
731 /* Tests llx_remove_if. */
733 test_remove_if (void)
735 const int max_elems = 8;
737 int cnt, r0, r1, pattern;
739 for (cnt = 0; cnt <= max_elems; cnt++)
740 for (r0 = 0; r0 <= cnt; r0++)
741 for (r1 = r0; r1 <= cnt; r1++)
742 for (pattern = 0; pattern <= 1 << cnt; pattern++)
744 struct llx_list list;
745 struct element **elems;
752 allocate_ascending (cnt, &list, &elems, &elemp, &values);
755 for (i = 0; i < cnt; i++)
757 bool delete = (pattern & (1 << i)) && r0 <= i && i < r1;
759 values[remaining++] = i;
762 check ((int) llx_remove_if (elemp[r0], elemp[r1],
763 pattern_pred, &pattern,
766 check_list_contents (&list, values, remaining);
768 free_elements (cnt, &list, elems, elemp, values);
772 /* Tests, via HELPER, a function that looks at list elements
773 equal to some specified element. */
775 test_examine_equal_range (void (*helper) (int r0, int r1, int eq_pat,
779 const int max_elems = 8;
781 int cnt, r0, r1, eq_pat;
783 for (cnt = 0; cnt <= max_elems; cnt++)
784 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
786 struct llx_list list;
787 struct element **elems;
791 struct element to_find;
795 allocate_ascending (cnt, &list, &elems, &elemp, &values);
797 for (i = 0; i < cnt; i++)
798 if (eq_pat & (1 << i))
799 values[i] = elems[i]->x = -1;
802 for (r0 = 0; r0 <= cnt; r0++)
803 for (r1 = r0; r1 <= cnt; r1++)
804 helper (r0, r1, eq_pat, &to_find, elemp);
806 check_list_contents (&list, values, cnt);
808 free_elements (cnt, &list, elems, elemp, values);
812 /* Tests, via HELPER, a function that looks at list elements for
813 which a given predicate returns true. */
815 test_examine_if_range (void (*helper) (int r0, int r1, int eq_pat,
818 const int max_elems = 8;
820 int cnt, r0, r1, eq_pat;
822 for (cnt = 0; cnt <= max_elems; cnt++)
823 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
825 struct llx_list list;
826 struct element **elems;
830 allocate_ascending (cnt, &list, &elems, &elemp, &values);
832 for (r0 = 0; r0 <= cnt; r0++)
833 for (r1 = r0; r1 <= cnt; r1++)
834 helper (r0, r1, eq_pat, elemp);
836 check_list_contents (&list, values, cnt);
838 free_elements (cnt, &list, elems, elemp, values);
842 /* Helper function for testing llx_find_equal. */
844 test_find_equal_helper (int r0, int r1, int eq_pat,
845 const void *to_find, struct llx **elemp)
850 match = llx_find_equal (elemp[r0], elemp[r1], to_find,
851 compare_elements, &aux_data);
852 for (i = r0; i < r1; i++)
853 if (eq_pat & (1 << i))
856 check (match == elemp[i]);
859 /* Tests llx_find_equal. */
861 test_find_equal (void)
863 test_examine_equal_range (test_find_equal_helper);
866 /* Helper function for testing llx_find_if. */
868 test_find_if_helper (int r0, int r1, int eq_pat, struct llx **elemp)
870 struct llx *match = llx_find_if (elemp[r0], elemp[r1],
871 pattern_pred, &eq_pat);
874 for (i = r0; i < r1; i++)
875 if (eq_pat & (1 << i))
878 check (match == elemp[i]);
881 /* Tests llx_find_if. */
885 test_examine_if_range (test_find_if_helper);
888 /* Tests llx_find_adjacent_equal. */
890 test_find_adjacent_equal (void)
892 const int max_elems = 8;
896 for (cnt = 0; cnt <= max_elems; cnt++)
897 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
899 struct llx_list list;
900 struct element **elems;
907 allocate_ascending (cnt, &list, &elems, &elemp, &values);
910 for (i = 0; i < cnt - 1; i++)
913 if (eq_pat & (1 << i))
915 values[i] = elems[i]->x = match;
916 values[i + 1] = elems[i + 1]->x = match;
922 for (i = 0; i <= cnt; i++)
924 struct llx *llx1 = llx_find_adjacent_equal (elemp[i], llx_null (&list),
930 llx2 = llx_null (&list);
931 for (j = i; j < cnt - 1; j++)
932 if (eq_pat & (1 << j))
937 check (llx1 == llx2);
939 check_list_contents (&list, values, cnt);
941 free_elements (cnt, &list, elems, elemp, values);
945 /* Helper function for testing llx_count_range. */
947 test_count_range_helper (int r0, int r1, int eq_pat UNUSED, struct llx **elemp)
949 check ((int) llx_count_range (elemp[r0], elemp[r1]) == r1 - r0);
952 /* Tests llx_count_range. */
954 test_count_range (void)
956 test_examine_if_range (test_count_range_helper);
959 /* Helper function for testing llx_count_equal. */
961 test_count_equal_helper (int r0, int r1, int eq_pat,
962 const void *to_find, struct llx **elemp)
967 count1 = llx_count_equal (elemp[r0], elemp[r1], to_find,
968 compare_elements, &aux_data);
970 for (i = r0; i < r1; i++)
971 if (eq_pat & (1 << i))
974 check (count1 == count2);
977 /* Tests llx_count_equal. */
979 test_count_equal (void)
981 test_examine_equal_range (test_count_equal_helper);
984 /* Helper function for testing llx_count_if. */
986 test_count_if_helper (int r0, int r1, int eq_pat, struct llx **elemp)
992 count1 = llx_count_if (elemp[r0], elemp[r1], pattern_pred, &eq_pat);
995 for (i = r0; i < r1; i++)
996 if (eq_pat & (1 << i))
999 check (count1 == count2);
1002 /* Tests llx_count_if. */
1004 test_count_if (void)
1006 test_examine_if_range (test_count_if_helper);
1011 factorial (unsigned n)
1019 /* Returns the number of permutations of the CNT values in
1020 VALUES. If VALUES contains duplicates, they must be
1023 expected_perms (int *values, size_t cnt)
1028 perm_cnt = factorial (cnt);
1029 for (i = 0; i < cnt; i = j)
1031 for (j = i + 1; j < cnt; j++)
1032 if (values[i] != values[j])
1034 perm_cnt /= factorial (j - i);
1039 /* Tests llx_min and llx_max. */
1043 const int max_elems = 6;
1046 for (cnt = 0; cnt <= max_elems; cnt++)
1048 struct llx_list list;
1049 struct element **elems;
1052 int *new_values = xnmalloc (cnt, sizeof *values);
1056 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1059 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1060 compare_elements, &aux_data))
1066 for (i = 0, x = llx_head (&list); x != llx_null (&list);
1067 x = llx_next (x), i++)
1069 struct element *e = llx_data (x);
1071 new_values[i] = e->x;
1073 for (r0 = 0; r0 <= cnt; r0++)
1074 for (r1 = r0; r1 <= cnt; r1++)
1076 struct llx *min = llx_min (elemp[r0], elemp[r1],
1077 compare_elements, &aux_data);
1078 struct llx *max = llx_max (elemp[r0], elemp[r1],
1079 compare_elements, &aux_data);
1082 check (min == elemp[r1]);
1083 check (max == elemp[r1]);
1087 struct element *min_elem = llx_data (min);
1088 struct element *max_elem = llx_data (max);
1089 int min_int, max_int;
1092 min_int = max_int = new_values[r0];
1093 for (i = r0; i < r1; i++)
1095 int value = new_values[i];
1096 if (value < min_int)
1098 if (value > max_int)
1101 check (min != elemp[r1] && min_elem->x == min_int);
1102 check (max != elemp[r1] && max_elem->x == max_int);
1107 check (perm_cnt == factorial (cnt));
1108 check_list_contents (&list, values, cnt);
1110 free_elements (cnt, &list, elems, elemp, values);
1115 /* Tests llx_lexicographical_compare_3way. */
1117 test_lexicographical_compare_3way (void)
1119 const int max_elems = 4;
1121 int cnt_a, pat_a, cnt_b, pat_b;
1123 for (cnt_a = 0; cnt_a <= max_elems; cnt_a++)
1124 for (pat_a = 0; pat_a <= 1 << cnt_a; pat_a++)
1125 for (cnt_b = 0; cnt_b <= max_elems; cnt_b++)
1126 for (pat_b = 0; pat_b <= 1 << cnt_b; pat_b++)
1128 struct llx_list list_a, list_b;
1129 struct element **elems_a, **elems_b;
1130 struct llx **elemp_a, **elemp_b;
1131 int *values_a, *values_b;
1135 allocate_pattern (cnt_a, pat_a,
1136 &list_a, &elems_a, &elemp_a, &values_a);
1137 allocate_pattern (cnt_b, pat_b,
1138 &list_b, &elems_b, &elemp_b, &values_b);
1140 for (a0 = 0; a0 <= cnt_a; a0++)
1141 for (a1 = a0; a1 <= cnt_a; a1++)
1142 for (b0 = 0; b0 <= cnt_b; b0++)
1143 for (b1 = b0; b1 <= cnt_b; b1++)
1145 int a_ordering = lexicographical_compare_3way (
1146 values_a + a0, a1 - a0,
1147 values_b + b0, b1 - b0,
1149 compare_ints, NULL);
1151 int b_ordering = llx_lexicographical_compare_3way (
1152 elemp_a[a0], elemp_a[a1],
1153 elemp_b[b0], elemp_b[b1],
1154 compare_elements, &aux_data);
1156 check (a_ordering == b_ordering);
1159 free_elements (cnt_a, &list_a, elems_a, elemp_a, values_a);
1160 free_elements (cnt_b, &list_b, elems_b, elemp_b, values_b);
1164 /* Appends the `x' value in element E to the array pointed to by
1165 NEXT_OUTPUT, and advances NEXT_OUTPUT to the next position. */
1167 apply_func (void *e_, void *next_output_)
1169 struct element *e = e_;
1170 int **next_output = next_output_;
1172 *(*next_output)++ = e->x;
1175 /* Tests llx_apply. */
1179 const int max_elems = 8;
1183 for (cnt = 0; cnt <= max_elems; cnt++)
1184 for (r0 = 0; r0 <= cnt; r0++)
1185 for (r1 = r0; r1 <= cnt; r1++)
1187 struct llx_list list;
1188 struct element **elems;
1196 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1197 check_list_contents (&list, values, cnt);
1199 output = next_output = xnmalloc (cnt, sizeof *output);
1200 llx_apply (elemp[r0], elemp[r1], apply_func, &next_output);
1201 check_list_contents (&list, values, cnt);
1202 llx_destroy (&list, NULL, NULL, &llx_malloc_mgr);
1204 check (r1 - r0 == next_output - output);
1205 for (j = 0; j < r1 - r0; j++)
1206 check (output[j] == r0 + j);
1208 free_elements (cnt, NULL, elems, elemp, values);
1213 /* Tests llx_destroy. */
1217 const int max_elems = 8;
1221 for (cnt = 0; cnt <= max_elems; cnt++)
1223 struct llx_list list;
1224 struct element **elems;
1232 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1233 check_list_contents (&list, values, cnt);
1235 output = next_output = xnmalloc (cnt, sizeof *output);
1236 llx_destroy (&list, apply_func, &next_output, &llx_malloc_mgr);
1238 check (cnt == next_output - output);
1239 for (j = 0; j < cnt; j++)
1240 check (output[j] == j);
1242 free_elements (cnt, NULL, elems, elemp, values);
1247 /* Tests llx_reverse. */
1251 const int max_elems = 8;
1255 for (cnt = 0; cnt <= max_elems; cnt++)
1256 for (r0 = 0; r0 <= cnt; r0++)
1257 for (r1 = r0; r1 <= cnt; r1++)
1259 struct llx_list list;
1260 struct element **elems;
1266 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1267 check_list_contents (&list, values, cnt);
1270 for (i = 0; i < r0; i++)
1272 for (i = r1 - 1; i >= r0; i--)
1274 for (i = r1; i < cnt; i++)
1277 llx_reverse (elemp[r0], elemp[r1]);
1278 check_list_contents (&list, values, cnt);
1280 free_elements (cnt, &list, elems, elemp, values);
1284 /* Tests llx_next_permutation and llx_prev_permutation when the
1285 permuted values have no duplicates. */
1287 test_permutations_no_dups (void)
1289 const int max_elems = 8;
1292 for (cnt = 0; cnt <= max_elems; cnt++)
1294 struct llx_list list;
1295 struct element **elems;
1297 int *old_values = xnmalloc (cnt, sizeof *values);
1298 int *new_values = xnmalloc (cnt, sizeof *values);
1302 allocate_ascending (cnt, &list, &elems, NULL, &values);
1305 extract_values (&list, old_values, cnt);
1306 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1307 compare_elements, &aux_data))
1309 extract_values (&list, new_values, cnt);
1310 check (lexicographical_compare_3way (new_values, cnt,
1313 compare_ints, NULL) > 0);
1314 memcpy (old_values, new_values, (cnt) * sizeof *old_values);
1317 check (perm_cnt == factorial (cnt));
1318 check_list_contents (&list, values, cnt);
1321 llx_reverse (llx_head (&list), llx_null (&list));
1322 extract_values (&list, old_values, cnt);
1323 while (llx_prev_permutation (llx_head (&list), llx_null (&list),
1324 compare_elements, &aux_data))
1326 extract_values (&list, new_values, cnt);
1327 check (lexicographical_compare_3way (new_values, cnt,
1330 compare_ints, NULL) < 0);
1331 memcpy (old_values, new_values, (cnt) * sizeof *old_values);
1334 check (perm_cnt == factorial (cnt));
1335 llx_reverse (llx_head (&list), llx_null (&list));
1336 check_list_contents (&list, values, cnt);
1338 free_elements (cnt, &list, elems, NULL, values);
1344 /* Tests llx_next_permutation and llx_prev_permutation when the
1345 permuted values contain duplicates. */
1347 test_permutations_with_dups (void)
1349 const int max_elems = 8;
1350 const int max_dup = 3;
1351 const int repetitions = 1024;
1355 for (repeat = 0; repeat < repetitions; repeat++)
1356 for (cnt = 0; cnt < max_elems; cnt++)
1358 struct llx_list list;
1359 struct element **elems;
1362 int *old_values = xnmalloc (max_elems, sizeof *values);
1363 int *new_values = xnmalloc (max_elems, sizeof *values);
1365 unsigned permutation_cnt;
1369 allocate_elements (cnt, &list, &elems, &elemp, &values);
1374 int max = left < max_dup ? left : max_dup;
1375 int n = rand () % max + 1;
1378 int idx = cnt - left--;
1379 values[idx] = elems[idx]->x = value;
1384 permutation_cnt = 1;
1385 extract_values (&list, old_values, cnt);
1386 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1387 compare_elements, &aux_data))
1389 extract_values (&list, new_values, cnt);
1390 check (lexicographical_compare_3way (new_values, cnt,
1393 compare_ints, NULL) > 0);
1394 memcpy (old_values, new_values, cnt * sizeof *old_values);
1397 check (permutation_cnt == expected_perms (values, cnt));
1398 check_list_contents (&list, values, cnt);
1400 permutation_cnt = 1;
1401 llx_reverse (llx_head (&list), llx_null (&list));
1402 extract_values (&list, old_values, cnt);
1403 while (llx_prev_permutation (llx_head (&list), llx_null (&list),
1404 compare_elements, &aux_data))
1406 extract_values (&list, new_values, cnt);
1407 check (lexicographical_compare_3way (new_values, cnt,
1410 compare_ints, NULL) < 0);
1413 llx_reverse (llx_head (&list), llx_null (&list));
1414 check (permutation_cnt == expected_perms (values, cnt));
1415 check_list_contents (&list, values, cnt);
1417 free_elements (cnt, &list, elems, elemp, values);
1423 /* Tests llx_merge when no equal values are to be merged. */
1425 test_merge_no_dups (void)
1427 const int max_elems = 8;
1428 const int max_fillxer = 3;
1430 int merge_cnt, pattern, pfx, gap, sfx, order;
1432 for (merge_cnt = 0; merge_cnt < max_elems; merge_cnt++)
1433 for (pattern = 0; pattern <= (1 << merge_cnt); pattern++)
1434 for (pfx = 0; pfx < max_fillxer; pfx++)
1435 for (gap = 0; gap < max_fillxer; gap++)
1436 for (sfx = 0; sfx < max_fillxer; sfx++)
1437 for (order = 0; order < 2; order++)
1439 struct llx_list list;
1440 struct element **elems;
1444 int list_cnt = pfx + merge_cnt + gap + sfx;
1448 allocate_elements (list_cnt, &list,
1449 &elems, &elemp, &values);
1452 for (i = 0; i < pfx; i++)
1453 elems[j++]->x = 100 + i;
1455 for (i = 0; i < merge_cnt; i++)
1456 if (pattern & (1u << i))
1459 for (i = 0; i < gap; i++)
1460 elems[j++]->x = 200 + i;
1462 for (i = 0; i < merge_cnt; i++)
1463 if (!(pattern & (1u << i)))
1466 for (i = 0; i < sfx; i++)
1467 elems[j++]->x = 300 + i;
1468 check (list_cnt == j);
1471 for (i = 0; i < pfx; i++)
1472 values[j++] = 100 + i;
1474 for (i = 0; i < merge_cnt; i++)
1476 for (i = 0; i < gap; i++)
1477 values[j++] = 200 + i;
1479 for (i = 0; i < merge_cnt; i++)
1481 for (i = 0; i < sfx; i++)
1482 values[j++] = 300 + i;
1483 check (list_cnt == j);
1486 llx_merge (elemp[a0], elemp[a1], elemp[b0], elemp[b1],
1487 compare_elements, &aux_data);
1489 llx_merge (elemp[b0], elemp[b1], elemp[a0], elemp[a1],
1490 compare_elements, &aux_data);
1492 check_list_contents (&list, values, list_cnt);
1494 free_elements (list_cnt, &list, elems, elemp, values);
1498 /* Tests llx_merge when equal values are to be merged. */
1500 test_merge_with_dups (void)
1502 const int max_elems = 8;
1504 int cnt, merge_pat, inc_pat, order;
1506 for (cnt = 0; cnt <= max_elems; cnt++)
1507 for (merge_pat = 0; merge_pat <= (1 << cnt); merge_pat++)
1508 for (inc_pat = 0; inc_pat <= (1 << cnt); inc_pat++)
1509 for (order = 0; order < 2; order++)
1511 struct llx_list list;
1512 struct element **elems;
1519 allocate_elements (cnt, &list, &elems, &elemp, &values);
1522 for (i = k = 0; i < cnt; i++)
1524 if (merge_pat & (1u << i))
1526 if (inc_pat & (1u << i))
1530 for (i = k = 0; i < cnt; i++)
1532 if (!(merge_pat & (1u << i)))
1534 if (inc_pat & (1u << i))
1541 for (i = 0; i < cnt; i++)
1546 for (i = 0; i < mid; i++)
1547 elems[i]->y = 100 + i;
1548 for (i = mid; i < cnt; i++)
1553 for (i = k = 0; i < cnt; i++)
1556 if (inc_pat & (1u << i))
1562 llx_merge (elemp[0], elemp[mid], elemp[mid], elemp[cnt],
1563 compare_elements, &aux_data);
1565 llx_merge (elemp[mid], elemp[cnt], elemp[0], elemp[mid],
1566 compare_elements, &aux_data);
1568 check_list_contents (&list, values, cnt);
1569 check (llx_is_sorted (llx_head (&list), llx_null (&list),
1570 compare_elements_x_y, &aux_data));
1572 free_elements (cnt, &list, elems, elemp, values);
1576 /* Tests llx_sort on all permutations up to a maximum number of
1579 test_sort_exhaustive (void)
1581 const int max_elems = 8;
1584 for (cnt = 0; cnt <= max_elems; cnt++)
1586 struct llx_list list;
1587 struct element **elems;
1590 struct element **perm_elems;
1595 allocate_ascending (cnt, &list, &elems, NULL, &values);
1596 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1599 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1600 compare_elements, &aux_data))
1602 struct llx_list perm_list;
1605 extract_values (&list, perm_values, cnt);
1606 llx_init (&perm_list);
1607 for (j = 0; j < cnt; j++)
1609 perm_elems[j]->x = perm_values[j];
1610 llx_push_tail (&perm_list, perm_elems[j], &llx_malloc_mgr);
1612 llx_sort (llx_head (&perm_list), llx_null (&perm_list),
1613 compare_elements, &aux_data);
1614 check_list_contents (&perm_list, values, cnt);
1615 check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
1616 compare_elements, &aux_data));
1617 llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
1620 check (perm_cnt == factorial (cnt));
1622 free_elements (cnt, &list, elems, NULL, values);
1623 free_elements (cnt, NULL, perm_elems, NULL, perm_values);
1627 /* Tests that llx_sort is stable in the presence of equal
1630 test_sort_stable (void)
1632 const int max_elems = 6;
1635 for (cnt = 0; cnt <= max_elems; cnt++)
1636 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1638 struct llx_list list;
1639 struct element **elems;
1642 struct element **perm_elems;
1648 allocate_elements (cnt, &list, &elems, NULL, &values);
1649 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1652 for (i = 0; i < cnt; i++)
1654 elems[i]->x = values[i] = j;
1655 if (inc_pat & (1 << i))
1661 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1662 compare_elements_y, &aux_data))
1664 struct llx_list perm_list;
1666 extract_values (&list, perm_values, cnt);
1667 llx_init (&perm_list);
1668 for (i = 0; i < cnt; i++)
1670 perm_elems[i]->x = perm_values[i];
1671 perm_elems[i]->y = i;
1672 llx_push_tail (&perm_list, perm_elems[i], &llx_malloc_mgr);
1674 llx_sort (llx_head (&perm_list), llx_null (&perm_list),
1675 compare_elements, &aux_data);
1676 check_list_contents (&perm_list, values, cnt);
1677 check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
1678 compare_elements_x_y, &aux_data));
1679 llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
1682 check (perm_cnt == factorial (cnt));
1684 free_elements (cnt, &list, elems, NULL, values);
1685 free_elements (cnt, NULL, perm_elems, NULL, perm_values);
1689 /* Tests that llx_sort does not disturb elements outside the
1692 test_sort_subset (void)
1694 const int max_elems = 8;
1696 int cnt, r0, r1, repeat;
1698 for (cnt = 0; cnt <= max_elems; cnt++)
1699 for (repeat = 0; repeat < 100; repeat++)
1700 for (r0 = 0; r0 <= cnt; r0++)
1701 for (r1 = r0; r1 <= cnt; r1++)
1703 struct llx_list list;
1704 struct element **elems;
1708 allocate_random (cnt, &list, &elems, &elemp, &values);
1710 qsort (&values[r0], r1 - r0, sizeof *values, compare_ints_noaux);
1711 llx_sort (elemp[r0], elemp[r1], compare_elements, &aux_data);
1712 check_list_contents (&list, values, cnt);
1714 free_elements (cnt, &list, elems, elemp, values);
1718 /* Tests that llx_sort works with large lists. */
1720 test_sort_big (void)
1722 const int max_elems = 1024;
1726 for (cnt = 0; cnt < max_elems; cnt++)
1728 struct llx_list list;
1729 struct element **elems;
1732 allocate_random (cnt, &list, &elems, NULL, &values);
1734 qsort (values, cnt, sizeof *values, compare_ints_noaux);
1735 llx_sort (llx_head (&list), llx_null (&list), compare_elements, &aux_data);
1736 check_list_contents (&list, values, cnt);
1738 free_elements (cnt, &list, elems, NULL, values);
1742 /* Tests llx_unique. */
1746 const int max_elems = 10;
1748 int *ascending = xnmalloc (max_elems, sizeof *ascending);
1750 int cnt, inc_pat, i, j, unique_values;
1752 for (i = 0; i < max_elems; i++)
1755 for (cnt = 0; cnt < max_elems; cnt++)
1756 for (inc_pat = 0; inc_pat < (1 << cnt); inc_pat++)
1758 struct llx_list list, dups;
1759 struct element **elems;
1762 allocate_elements (cnt, &list, &elems, NULL, &values);
1764 j = unique_values = 0;
1765 for (i = 0; i < cnt; i++)
1767 unique_values = j + 1;
1768 elems[i]->x = values[i] = j;
1769 if (inc_pat & (1 << i))
1772 check_list_contents (&list, values, cnt);
1775 check (llx_unique (llx_head (&list), llx_null (&list),
1777 compare_elements, &aux_data,
1779 == (size_t) unique_values);
1780 check_list_contents (&list, ascending, unique_values);
1782 llx_splice (llx_null (&list), llx_head (&dups), llx_null (&dups));
1783 llx_sort (llx_head (&list), llx_null (&list), compare_elements, &aux_data);
1784 check_list_contents (&list, values, cnt);
1786 llx_destroy (&dups, NULL, NULL, &llx_malloc_mgr);
1787 free_elements (cnt, &list, elems, NULL, values);
1793 /* Tests llx_sort_unique. */
1795 test_sort_unique (void)
1797 const int max_elems = 7;
1800 for (cnt = 0; cnt <= max_elems; cnt++)
1801 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1803 struct llx_list list;
1804 struct element **elems;
1807 struct element **perm_elems;
1816 allocate_elements (cnt, &list, &elems, NULL, &values);
1817 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1820 for (i = 0; i < cnt; i++)
1822 elems[i]->x = values[i] = j;
1824 if (inc_pat & (1 << i))
1828 unique_values = xnmalloc (unique_cnt, sizeof *unique_values);
1829 for (i = 0; i < unique_cnt; i++)
1830 unique_values[i] = i;
1833 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1834 compare_elements, &aux_data))
1836 struct llx_list perm_list;
1838 extract_values (&list, perm_values, cnt);
1839 llx_init (&perm_list);
1840 for (i = 0; i < cnt; i++)
1842 perm_elems[i]->x = perm_values[i];
1843 perm_elems[i]->y = i;
1844 llx_push_tail (&perm_list, perm_elems[i], &llx_malloc_mgr);
1846 llx_sort_unique (llx_head (&perm_list), llx_null (&perm_list), NULL,
1847 compare_elements, &aux_data,
1849 check_list_contents (&perm_list, unique_values, unique_cnt);
1850 check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
1851 compare_elements_x_y, &aux_data));
1852 llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
1855 check (perm_cnt == expected_perms (values, cnt));
1857 free_elements (cnt, &list, elems, NULL, values);
1858 free_elements (cnt, NULL, perm_elems, NULL, perm_values);
1859 free (unique_values);
1863 /* Tests llx_insert_ordered. */
1865 test_insert_ordered (void)
1867 const int max_elems = 6;
1870 for (cnt = 0; cnt <= max_elems; cnt++)
1871 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1873 struct llx_list list;
1874 struct element **elems;
1877 struct element **perm_elems;
1883 allocate_elements (cnt, &list, &elems, NULL, &values);
1884 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1887 for (i = 0; i < cnt; i++)
1889 elems[i]->x = values[i] = j;
1890 if (inc_pat & (1 << i))
1896 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1897 compare_elements_y, &aux_data))
1899 struct llx_list perm_list;
1901 extract_values (&list, perm_values, cnt);
1902 llx_init (&perm_list);
1903 for (i = 0; i < cnt; i++)
1905 perm_elems[i]->x = perm_values[i];
1906 perm_elems[i]->y = i;
1907 llx_insert_ordered (llx_head (&perm_list),
1908 llx_null (&perm_list),
1910 compare_elements, &aux_data,
1913 check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
1914 compare_elements_x_y, &aux_data));
1915 llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
1918 check (perm_cnt == factorial (cnt));
1920 free_elements (cnt, &list, elems, NULL, values);
1921 free_elements (cnt, NULL, perm_elems, NULL, perm_values);
1925 /* Tests llx_partition. */
1927 test_partition (void)
1929 const int max_elems = 10;
1935 for (cnt = 0; cnt < max_elems; cnt++)
1936 for (r0 = 0; r0 <= cnt; r0++)
1937 for (r1 = r0; r1 <= cnt; r1++)
1938 for (pbase = 0; pbase <= (1u << (r1 - r0)); pbase++)
1940 struct llx_list list;
1941 struct element **elems;
1945 unsigned pattern = pbase << r0;
1948 struct llx *part_llx;
1950 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1952 /* Check that llx_find_partition works okay in every
1953 case. We use it after partitioning, too, but that
1954 only tests cases where it returns non-null. */
1955 for (i = r0; i < r1; i++)
1956 if (!(pattern & (1u << i)))
1960 if (pattern & (1u << i))
1962 part_llx = llx_find_partition (elemp[r0], elemp[r1],
1966 check (part_llx == elemp[j]);
1968 check (part_llx == NULL);
1970 /* Figure out expected results. */
1973 for (i = 0; i < r0; i++)
1975 for (i = r0; i < r1; i++)
1976 if (pattern & (1u << i))
1978 for (i = r0; i < r1; i++)
1979 if (!(pattern & (1u << i)))
1981 if (first_false == -1)
1985 if (first_false == -1)
1987 for (i = r1; i < cnt; i++)
1991 /* Partition and check for expected results. */
1992 check (llx_partition (elemp[r0], elemp[r1],
1993 pattern_pred, &pattern)
1994 == elemp[first_false]);
1995 check (llx_find_partition (elemp[r0], elemp[r1],
1996 pattern_pred, &pattern)
1997 == elemp[first_false]);
1998 check_list_contents (&list, values, cnt);
1999 check ((int) llx_count (&list) == cnt);
2001 free_elements (cnt, &list, elems, elemp, values);
2005 /* Tests that allocation failure is gracefully handled. */
2007 test_allocation_failure (void)
2009 struct llx_list list;
2012 check (llx_push_head (&list, NULL, &llx_null_mgr) == NULL);
2013 check (llx_push_tail (&list, NULL, &llx_null_mgr) == NULL);
2014 check (llx_insert (llx_null (&list), NULL, &llx_null_mgr) == NULL);
2015 check_list_contents (&list, NULL, 0);
2020 /* Runs TEST_FUNCTION and prints a message about NAME. */
2022 run_test (void (*test_function) (void), const char *name)
2033 run_test (test_push_pop, "push/pop");
2034 run_test (test_insert_remove, "insert/remove");
2035 run_test (test_swap, "swap");
2036 run_test (test_swap_range, "swap_range");
2037 run_test (test_remove_range, "remove_range");
2038 run_test (test_remove_equal, "remove_equal");
2039 run_test (test_remove_if, "remove_if");
2040 run_test (test_find_equal, "find_equal");
2041 run_test (test_find_if, "find_if");
2042 run_test (test_find_adjacent_equal, "find_adjacent_equal");
2043 run_test (test_count_range, "count_range");
2044 run_test (test_count_equal, "count_equal");
2045 run_test (test_count_if, "count_if");
2046 run_test (test_min_max, "min/max");
2047 run_test (test_lexicographical_compare_3way, "lexicographical_compare_3way");
2048 run_test (test_apply, "apply");
2049 run_test (test_destroy, "destroy");
2050 run_test (test_reverse, "reverse");
2051 run_test (test_permutations_no_dups, "permutations (no dups)");
2052 run_test (test_permutations_with_dups, "permutations (with dups)");
2053 run_test (test_merge_no_dups, "merge (no dups)");
2054 run_test (test_merge_with_dups, "merge (with dups)");
2055 run_test (test_sort_exhaustive, "sort (exhaustive)");
2056 run_test (test_sort_stable, "sort (stability)");
2057 run_test (test_sort_subset, "sort (subset)");
2058 run_test (test_sort_big, "sort (big)");
2059 run_test (test_unique, "unique");
2060 run_test (test_sort_unique, "sort_unique");
2061 run_test (test_insert_ordered, "insert_ordered");
2062 run_test (test_partition, "partition");
2063 run_test (test_allocation_failure, "allocation failure");
2071 compile-command: "gcc -Wall -Wstrict-prototypes -Wmissing-prototypes ll.c llx.c llx-test.c -o llx-test -g"