1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2006, 2010 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU 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, see <http://www.gnu.org/licenses/>. */
17 /* This is a test program for the llx_* routines defined in
18 ll.c. This test program aims to be as comprehensive as
19 possible. "gcov -b" should report 100% coverage of lines and
20 branches in llx.c and llx.h. "valgrind --leak-check=yes
21 --show-reachable=yes" should give a clean report.
23 This test program depends only on ll.c, llx.c, and the
26 See ll-test.c for a similar program for the ll_* routines. */
32 #include <libpspp/llx.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 /* Always returns a null pointer, failing allocation. */
110 null_allocate_node (void *aux UNUSED)
117 null_release_node (struct llx *llx UNUSED, void *aux UNUSED)
121 /* Memory manager that fails all allocations and does nothing on
123 static const struct llx_manager llx_null_mgr =
130 /* List type and support routines. */
132 /* Test data element. */
135 int x; /* Primary value. */
136 int y; /* Secondary value. */
141 /* Prints the elements in LIST. */
143 print_list (struct llx_list *list)
148 for (x = llx_head (list); x != llx_null (list); x = llx_next (x))
150 const struct element *e = llx_data (x);
151 printf (" %d", e->x);
156 /* Prints the value returned by PREDICATE given auxiliary data
157 AUX for each element in LIST. */
159 print_pred (struct llx_list *list,
160 llx_predicate_func *predicate, void *aux UNUSED)
165 for (x = llx_head (list); x != llx_null (list); x = llx_next (x))
166 printf (" %d", predicate (x, aux));
170 /* Prints the CNT numbers in VALUES. */
172 print_array (int values[], size_t cnt)
177 for (i = 0; i < cnt; i++)
178 printf (" %d", values[i]);
182 /* Compares the `x' values in A and B and returns a strcmp-type
183 return value. Verifies that AUX points to aux_data. */
185 compare_elements (const void *a_, const void *b_, void *aux)
187 const struct element *a = a_;
188 const struct element *b = b_;
190 check (aux == &aux_data);
191 return a->x < b->x ? -1 : a->x > b->x;
194 /* Compares the `x' and `y' values in A and B and returns a
195 strcmp-type return value. Verifies that AUX points to
198 compare_elements_x_y (const void *a_, const void *b_, void *aux)
200 const struct element *a = a_;
201 const struct element *b = b_;
203 check (aux == &aux_data);
205 return a->x < b->x ? -1 : 1;
206 else if (a->y != b->y)
207 return a->y < b->y ? -1 : 1;
212 /* Compares the `y' values in A and B and returns a strcmp-type
213 return value. Verifies that AUX points to aux_data. */
215 compare_elements_y (const void *a_, const void *b_, void *aux)
217 const struct element *a = a_;
218 const struct element *b = b_;
220 check (aux == &aux_data);
221 return a->y < b->y ? -1 : a->y > b->y;
224 /* Returns true if the bit in *PATTERN indicated by `x in
225 *ELEMENT is set, false otherwise. */
227 pattern_pred (const void *element_, void *pattern_)
229 const struct element *element = element_;
230 unsigned int *pattern = pattern_;
232 return (*pattern & (1u << element->x)) != 0;
235 /* Allocates N elements in *ELEMS.
236 Adds the elements to LIST, if it is nonnull.
237 Puts pointers to the elements' list elements in *ELEMP,
238 followed by a pointer to the list null element, if ELEMP is
240 Allocates space for N values in *VALUES, if VALUES is
243 allocate_elements (size_t n,
244 struct llx_list *list,
245 struct element ***elems,
254 *elems = xnmalloc (n, sizeof **elems);
257 *elemp = xnmalloc (n + 1, sizeof *elemp);
258 (*elemp)[n] = llx_null (list);
261 for (i = 0; i < n; i++)
263 (*elems)[i] = xmalloc (sizeof ***elems);
266 struct llx *llx = llx_push_tail (list, (*elems)[i], &llx_malloc_mgr);
273 *values = xnmalloc (n, sizeof *values);
276 /* Copies the CNT values of `x' from LIST into VALUES[]. */
278 extract_values (struct llx_list *list, int values[], size_t cnt)
282 check (llx_count (list) == cnt);
283 for (x = llx_head (list); x != llx_null (list); x = llx_next (x))
285 struct element *e = llx_data (x);
290 /* As allocate_elements, but sets ascending values, starting
291 from 0, in `x' values in *ELEMS and in *VALUES (if
294 allocate_ascending (size_t n,
295 struct llx_list *list,
296 struct element ***elems,
302 allocate_elements (n, list, elems, elemp, values);
304 for (i = 0; i < n; i++)
307 extract_values (list, *values, n);
310 /* As allocate_elements, but sets binary values extracted from
311 successive bits in PATTERN in `x' values in *ELEMS and in
312 *VALUES (if nonnull). */
314 allocate_pattern (size_t n,
316 struct llx_list *list,
317 struct element ***elems,
323 allocate_elements (n, list, elems, elemp, values);
325 for (i = 0; i < n; i++)
326 (*elems)[i]->x = (pattern & (1 << i)) != 0;
328 extract_values (list, *values, n);
331 /* Randomly shuffles the CNT elements in ARRAY, each of which is
332 SIZE bytes in size. */
334 random_shuffle (void *array_, size_t cnt, size_t size)
336 char *array = array_;
337 char *tmp = xmalloc (size);
340 for (i = 0; i < cnt; i++)
342 size_t j = rand () % (cnt - i) + i;
345 memcpy (tmp, array + j * size, size);
346 memcpy (array + j * size, array + i * size, size);
347 memcpy (array + i * size, tmp, size);
354 /* As allocate_ascending, but orders the values randomly. */
356 allocate_random (size_t n,
357 struct llx_list *list,
358 struct element ***elems,
364 allocate_elements (n, list, elems, elemp, values);
366 for (i = 0; i < n; i++)
368 random_shuffle (*elems, n, sizeof **elems);
370 extract_values (list, *values, n);
373 /* Frees LIST, the N elements of ELEMS, ELEMP, and VALUES. */
375 free_elements (size_t n,
376 struct llx_list *list,
377 struct element **elems,
384 llx_destroy (list, NULL, NULL, &llx_malloc_mgr);
385 for (i = 0; i < n; i++)
392 /* Compares A and B and returns a strcmp-type return value. */
394 compare_ints (const void *a_, const void *b_, void *aux UNUSED)
399 return *a < *b ? -1 : *a > *b;
402 /* Compares A and B and returns a strcmp-type return value. */
404 compare_ints_noaux (const void *a_, const void *b_)
409 return *a < *b ? -1 : *a > *b;
412 /* Checks that LIST contains the CNT values in ELEMENTS. */
414 check_list_contents (struct llx_list *list, int elements[], size_t cnt)
419 check ((cnt == 0) == llx_is_empty (list));
421 /* Iterate in forward order. */
422 for (llx = llx_head (list), i = 0; i < cnt; llx = llx_next (llx), i++)
424 struct element *e = llx_data (llx);
425 check (elements[i] == e->x);
426 check (llx != llx_null (list));
428 check (llx == llx_null (list));
430 /* Iterate in reverse order. */
431 for (llx = llx_tail (list), i = 0; i < cnt; llx = llx_prev (llx), i++)
433 struct element *e = llx_data (llx);
434 check (elements[cnt - i - 1] == e->x);
435 check (llx != llx_null (list));
437 check (llx == llx_null (list));
439 check (llx_count (list) == cnt);
442 /* Lexicographicallxy compares ARRAY1, which contains COUNT1
443 elements of SIZE bytes each, to ARRAY2, which contains COUNT2
444 elements of SIZE bytes, according to COMPARE. Returns a
445 strcmp-type result. AUX is passed to COMPARE as auxiliary
448 lexicographical_compare_3way (const void *array1, size_t count1,
449 const void *array2, size_t count2,
451 int (*compare) (const void *, const void *,
455 const char *first1 = array1;
456 const char *first2 = array2;
457 size_t min_count = count1 < count2 ? count1 : count2;
459 while (min_count > 0)
461 int cmp = compare (first1, first2, aux);
470 return count1 < count2 ? -1 : count1 > count2;
475 /* Tests list push and pop operations. */
479 const int max_elems = 1024;
481 struct llx_list list;
482 struct element **elems;
487 allocate_elements (max_elems, NULL, &elems, NULL, &values);
491 check_list_contents (&list, NULL, 0);
492 for (i = 0; i < max_elems; i++)
494 values[i] = elems[i]->x = i;
495 llx_push_tail (&list, elems[i], &llx_malloc_mgr);
496 check_list_contents (&list, values, i + 1);
499 /* Remove from tail. */
500 for (i = 0; i < max_elems; i++)
502 struct element *e = llx_pop_tail (&list, &llx_malloc_mgr);
503 check (e->x == max_elems - i - 1);
504 check_list_contents (&list, values, max_elems - i - 1);
508 check_list_contents (&list, NULL, 0);
509 for (i = 0; i < max_elems; i++)
511 values[max_elems - i - 1] = elems[i]->x = max_elems - i - 1;
512 llx_push_head (&list, elems[i], &llx_malloc_mgr);
513 check_list_contents (&list, &values[max_elems - i - 1], i + 1);
516 /* Remove from start. */
517 for (i = 0; i < max_elems; i++)
519 struct element *e = llx_pop_head (&list, &llx_malloc_mgr);
520 check (e->x == (int) i);
521 check_list_contents (&list, &values[i + 1], max_elems - i - 1);
524 free_elements (max_elems, &list, elems, NULL, values);
527 /* Tests insertion and removal at arbitrary positions. */
529 test_insert_remove (void)
531 const int max_elems = 16;
534 for (cnt = 0; cnt < max_elems; cnt++)
536 struct element **elems;
538 int *values = xnmalloc (cnt + 1, sizeof *values);
540 struct llx_list list;
541 struct element extra;
542 struct llx *extra_llx;
545 allocate_ascending (cnt, &list, &elems, &elemp, NULL);
547 for (pos = 0; pos <= cnt; pos++)
551 extra_llx = llx_insert (elemp[pos], &extra, &llx_malloc_mgr);
552 check (extra_llx != NULL);
555 for (i = 0; i < pos; i++)
560 check_list_contents (&list, values, cnt + 1);
562 llx_remove (extra_llx, &llx_malloc_mgr);
564 check_list_contents (&list, values, cnt);
566 free_elements (cnt, &list, elems, elemp, values);
570 /* Tests swapping individual elements. */
574 const int max_elems = 8;
577 for (cnt = 0; cnt <= max_elems; cnt++)
579 struct llx_list list;
580 struct element **elems;
586 allocate_ascending (cnt, &list, &elems, &elemp, &values);
587 check_list_contents (&list, values, cnt);
589 for (i = 0; i < cnt; i++)
590 for (j = 0; j < cnt; j++)
591 for (k = 0; k < 2; k++)
595 llx_swap (elemp[i], elemp[j]);
597 values[i] = values[j];
599 check_list_contents (&list, values, cnt);
602 free_elements (cnt, &list, elems, elemp, values);
606 /* Tests swapping ranges of list elements. */
608 test_swap_range (void)
610 const int max_elems = 8;
611 int cnt, a0, a1, b0, b1, r;
613 for (cnt = 0; cnt <= max_elems; cnt++)
614 for (a0 = 0; a0 <= cnt; a0++)
615 for (a1 = a0; a1 <= cnt; a1++)
616 for (b0 = a1; b0 <= cnt; b0++)
617 for (b1 = b0; b1 <= cnt; b1++)
618 for (r = 0; r < 2; r++)
620 struct llx_list list;
621 struct element **elems;
627 allocate_ascending (cnt, &list, &elems, &elemp, &values);
628 check_list_contents (&list, values, cnt);
631 for (i = 0; i < a0; i++)
633 for (i = b0; i < b1; i++)
635 for (i = a1; i < b0; i++)
637 for (i = a0; i < a1; i++)
639 for (i = b1; i < cnt; i++)
644 llx_swap_range (elemp[a0], elemp[a1], elemp[b0], elemp[b1]);
646 llx_swap_range (elemp[b0], elemp[b1], elemp[a0], elemp[a1]);
647 check_list_contents (&list, values, cnt);
649 free_elements (cnt, &list, elems, elemp, values);
653 /* Tests removing ranges of list elements. */
655 test_remove_range (void)
657 const int max_elems = 8;
661 for (cnt = 0; cnt <= max_elems; cnt++)
662 for (r0 = 0; r0 <= cnt; r0++)
663 for (r1 = r0; r1 <= cnt; r1++)
665 struct llx_list list;
666 struct element **elems;
672 allocate_ascending (cnt, &list, &elems, &elemp, &values);
673 check_list_contents (&list, values, cnt);
676 for (i = 0; i < r0; i++)
678 for (i = r1; i < cnt; i++)
681 llx_remove_range (elemp[r0], elemp[r1], &llx_malloc_mgr);
682 check_list_contents (&list, values, j);
684 free_elements (cnt, &list, elems, elemp, values);
688 /* Tests llx_remove_equal. */
690 test_remove_equal (void)
692 const int max_elems = 8;
694 int cnt, r0, r1, eq_pat;
696 for (cnt = 0; cnt <= max_elems; cnt++)
697 for (r0 = 0; r0 <= cnt; r0++)
698 for (r1 = r0; r1 <= cnt; r1++)
699 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
701 struct llx_list list;
702 struct element **elems;
706 struct element to_remove;
710 allocate_elements (cnt, &list, &elems, &elemp, &values);
713 for (i = 0; i < cnt; i++)
715 int x = eq_pat & (1 << i) ? -1 : i;
716 bool delete = x == -1 && r0 <= i && i < r1;
719 values[remaining++] = x;
723 check ((int) llx_remove_equal (elemp[r0], elemp[r1], &to_remove,
724 compare_elements, &aux_data,
727 check_list_contents (&list, values, remaining);
729 free_elements (cnt, &list, elems, elemp, values);
733 /* Tests llx_remove_if. */
735 test_remove_if (void)
737 const int max_elems = 8;
739 int cnt, r0, r1, pattern;
741 for (cnt = 0; cnt <= max_elems; cnt++)
742 for (r0 = 0; r0 <= cnt; r0++)
743 for (r1 = r0; r1 <= cnt; r1++)
744 for (pattern = 0; pattern <= 1 << cnt; pattern++)
746 struct llx_list list;
747 struct element **elems;
754 allocate_ascending (cnt, &list, &elems, &elemp, &values);
757 for (i = 0; i < cnt; i++)
759 bool delete = (pattern & (1 << i)) && r0 <= i && i < r1;
761 values[remaining++] = i;
764 check ((int) llx_remove_if (elemp[r0], elemp[r1],
765 pattern_pred, &pattern,
768 check_list_contents (&list, values, remaining);
770 free_elements (cnt, &list, elems, elemp, values);
774 /* Tests, via HELPER, a function that looks at list elements
775 equal to some specified element. */
777 test_examine_equal_range (void (*helper) (int r0, int r1, int eq_pat,
781 const int max_elems = 8;
783 int cnt, r0, r1, eq_pat;
785 for (cnt = 0; cnt <= max_elems; cnt++)
786 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
788 struct llx_list list;
789 struct element **elems;
793 struct element to_find;
797 allocate_ascending (cnt, &list, &elems, &elemp, &values);
799 for (i = 0; i < cnt; i++)
800 if (eq_pat & (1 << i))
801 values[i] = elems[i]->x = -1;
804 for (r0 = 0; r0 <= cnt; r0++)
805 for (r1 = r0; r1 <= cnt; r1++)
806 helper (r0, r1, eq_pat, &to_find, elemp);
808 check_list_contents (&list, values, cnt);
810 free_elements (cnt, &list, elems, elemp, values);
814 /* Tests, via HELPER, a function that looks at list elements for
815 which a given predicate returns true. */
817 test_examine_if_range (void (*helper) (int r0, int r1, int eq_pat,
820 const int max_elems = 8;
822 int cnt, r0, r1, eq_pat;
824 for (cnt = 0; cnt <= max_elems; cnt++)
825 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
827 struct llx_list list;
828 struct element **elems;
832 allocate_ascending (cnt, &list, &elems, &elemp, &values);
834 for (r0 = 0; r0 <= cnt; r0++)
835 for (r1 = r0; r1 <= cnt; r1++)
836 helper (r0, r1, eq_pat, elemp);
838 check_list_contents (&list, values, cnt);
840 free_elements (cnt, &list, elems, elemp, values);
844 /* Helper function for testing llx_find_equal. */
846 test_find_equal_helper (int r0, int r1, int eq_pat,
847 const void *to_find, struct llx **elemp)
852 match = llx_find_equal (elemp[r0], elemp[r1], to_find,
853 compare_elements, &aux_data);
854 for (i = r0; i < r1; i++)
855 if (eq_pat & (1 << i))
858 check (match == elemp[i]);
861 /* Tests llx_find_equal. */
863 test_find_equal (void)
865 test_examine_equal_range (test_find_equal_helper);
868 /* Tests llx_find(). */
872 const int max_elems = 8;
876 for (cnt = 0; cnt <= max_elems; cnt++)
878 struct llx_list list;
879 struct element **elems;
885 allocate_ascending (cnt, &list, &elems, &elemp, &values);
887 for (i = 0; i < cnt; i++)
888 check (llx_find (llx_head (&list), llx_null (&list), elems[i])
890 check (llx_find (llx_head (&list), llx_null (&list), NULL) == NULL);
892 free_elements (cnt, &list, elems, elemp, values);
896 /* Helper function for testing llx_find_if. */
898 test_find_if_helper (int r0, int r1, int eq_pat, struct llx **elemp)
900 struct llx *match = llx_find_if (elemp[r0], elemp[r1],
901 pattern_pred, &eq_pat);
904 for (i = r0; i < r1; i++)
905 if (eq_pat & (1 << i))
908 check (match == elemp[i]);
911 /* Tests llx_find_if. */
915 test_examine_if_range (test_find_if_helper);
918 /* Tests llx_find_adjacent_equal. */
920 test_find_adjacent_equal (void)
922 const int max_elems = 8;
926 for (cnt = 0; cnt <= max_elems; cnt++)
927 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
929 struct llx_list list;
930 struct element **elems;
937 allocate_ascending (cnt, &list, &elems, &elemp, &values);
940 for (i = 0; i < cnt - 1; i++)
943 if (eq_pat & (1 << i))
945 values[i] = elems[i]->x = match;
946 values[i + 1] = elems[i + 1]->x = match;
952 for (i = 0; i <= cnt; i++)
954 struct llx *llx1 = llx_find_adjacent_equal (elemp[i], llx_null (&list),
960 llx2 = llx_null (&list);
961 for (j = i; j < cnt - 1; j++)
962 if (eq_pat & (1 << j))
967 check (llx1 == llx2);
969 check_list_contents (&list, values, cnt);
971 free_elements (cnt, &list, elems, elemp, values);
975 /* Helper function for testing llx_count_range. */
977 test_count_range_helper (int r0, int r1, int eq_pat UNUSED, struct llx **elemp)
979 check ((int) llx_count_range (elemp[r0], elemp[r1]) == r1 - r0);
982 /* Tests llx_count_range. */
984 test_count_range (void)
986 test_examine_if_range (test_count_range_helper);
989 /* Helper function for testing llx_count_equal. */
991 test_count_equal_helper (int r0, int r1, int eq_pat,
992 const void *to_find, struct llx **elemp)
997 count1 = llx_count_equal (elemp[r0], elemp[r1], to_find,
998 compare_elements, &aux_data);
1000 for (i = r0; i < r1; i++)
1001 if (eq_pat & (1 << i))
1004 check (count1 == count2);
1007 /* Tests llx_count_equal. */
1009 test_count_equal (void)
1011 test_examine_equal_range (test_count_equal_helper);
1014 /* Helper function for testing llx_count_if. */
1016 test_count_if_helper (int r0, int r1, int eq_pat, struct llx **elemp)
1022 count1 = llx_count_if (elemp[r0], elemp[r1], pattern_pred, &eq_pat);
1025 for (i = r0; i < r1; i++)
1026 if (eq_pat & (1 << i))
1029 check (count1 == count2);
1032 /* Tests llx_count_if. */
1034 test_count_if (void)
1036 test_examine_if_range (test_count_if_helper);
1041 factorial (unsigned int n)
1043 unsigned int value = 1;
1049 /* Returns the number of permutations of the CNT values in
1050 VALUES. If VALUES contains duplicates, they must be
1053 expected_perms (int *values, size_t cnt)
1056 unsigned int perm_cnt;
1058 perm_cnt = factorial (cnt);
1059 for (i = 0; i < cnt; i = j)
1061 for (j = i + 1; j < cnt; j++)
1062 if (values[i] != values[j])
1064 perm_cnt /= factorial (j - i);
1069 /* Tests llx_min and llx_max. */
1073 const int max_elems = 6;
1076 for (cnt = 0; cnt <= max_elems; cnt++)
1078 struct llx_list list;
1079 struct element **elems;
1082 int *new_values = xnmalloc (cnt, sizeof *values);
1086 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1089 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1090 compare_elements, &aux_data))
1096 for (i = 0, x = llx_head (&list); x != llx_null (&list);
1097 x = llx_next (x), i++)
1099 struct element *e = llx_data (x);
1101 new_values[i] = e->x;
1103 for (r0 = 0; r0 <= cnt; r0++)
1104 for (r1 = r0; r1 <= cnt; r1++)
1106 struct llx *min = llx_min (elemp[r0], elemp[r1],
1107 compare_elements, &aux_data);
1108 struct llx *max = llx_max (elemp[r0], elemp[r1],
1109 compare_elements, &aux_data);
1112 check (min == elemp[r1]);
1113 check (max == elemp[r1]);
1117 struct element *min_elem = llx_data (min);
1118 struct element *max_elem = llx_data (max);
1119 int min_int, max_int;
1122 min_int = max_int = new_values[r0];
1123 for (i = r0; i < r1; i++)
1125 int value = new_values[i];
1126 if (value < min_int)
1128 if (value > max_int)
1131 check (min != elemp[r1] && min_elem->x == min_int);
1132 check (max != elemp[r1] && max_elem->x == max_int);
1137 check (perm_cnt == factorial (cnt));
1138 check_list_contents (&list, values, cnt);
1140 free_elements (cnt, &list, elems, elemp, values);
1145 /* Tests llx_lexicographical_compare_3way. */
1147 test_lexicographical_compare_3way (void)
1149 const int max_elems = 4;
1151 int cnt_a, pat_a, cnt_b, pat_b;
1153 for (cnt_a = 0; cnt_a <= max_elems; cnt_a++)
1154 for (pat_a = 0; pat_a <= 1 << cnt_a; pat_a++)
1155 for (cnt_b = 0; cnt_b <= max_elems; cnt_b++)
1156 for (pat_b = 0; pat_b <= 1 << cnt_b; pat_b++)
1158 struct llx_list list_a, list_b;
1159 struct element **elems_a, **elems_b;
1160 struct llx **elemp_a, **elemp_b;
1161 int *values_a, *values_b;
1165 allocate_pattern (cnt_a, pat_a,
1166 &list_a, &elems_a, &elemp_a, &values_a);
1167 allocate_pattern (cnt_b, pat_b,
1168 &list_b, &elems_b, &elemp_b, &values_b);
1170 for (a0 = 0; a0 <= cnt_a; a0++)
1171 for (a1 = a0; a1 <= cnt_a; a1++)
1172 for (b0 = 0; b0 <= cnt_b; b0++)
1173 for (b1 = b0; b1 <= cnt_b; b1++)
1175 int a_ordering = lexicographical_compare_3way (
1176 values_a + a0, a1 - a0,
1177 values_b + b0, b1 - b0,
1179 compare_ints, NULL);
1181 int b_ordering = llx_lexicographical_compare_3way (
1182 elemp_a[a0], elemp_a[a1],
1183 elemp_b[b0], elemp_b[b1],
1184 compare_elements, &aux_data);
1186 check (a_ordering == b_ordering);
1189 free_elements (cnt_a, &list_a, elems_a, elemp_a, values_a);
1190 free_elements (cnt_b, &list_b, elems_b, elemp_b, values_b);
1194 /* Appends the `x' value in element E to the array pointed to by
1195 NEXT_OUTPUT, and advances NEXT_OUTPUT to the next position. */
1197 apply_func (void *e_, void *next_output_)
1199 struct element *e = e_;
1200 int **next_output = next_output_;
1202 *(*next_output)++ = e->x;
1205 /* Tests llx_apply. */
1209 const int max_elems = 8;
1213 for (cnt = 0; cnt <= max_elems; cnt++)
1214 for (r0 = 0; r0 <= cnt; r0++)
1215 for (r1 = r0; r1 <= cnt; r1++)
1217 struct llx_list list;
1218 struct element **elems;
1226 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1227 check_list_contents (&list, values, cnt);
1229 output = next_output = xnmalloc (cnt, sizeof *output);
1230 llx_apply (elemp[r0], elemp[r1], apply_func, &next_output);
1231 check_list_contents (&list, values, cnt);
1232 llx_destroy (&list, NULL, NULL, &llx_malloc_mgr);
1234 check (r1 - r0 == next_output - output);
1235 for (j = 0; j < r1 - r0; j++)
1236 check (output[j] == r0 + j);
1238 free_elements (cnt, NULL, elems, elemp, values);
1243 /* Tests llx_destroy. */
1247 const int max_elems = 8;
1251 for (cnt = 0; cnt <= max_elems; cnt++)
1253 struct llx_list list;
1254 struct element **elems;
1262 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1263 check_list_contents (&list, values, cnt);
1265 output = next_output = xnmalloc (cnt, sizeof *output);
1266 llx_destroy (&list, apply_func, &next_output, &llx_malloc_mgr);
1268 check (cnt == next_output - output);
1269 for (j = 0; j < cnt; j++)
1270 check (output[j] == j);
1272 free_elements (cnt, NULL, elems, elemp, values);
1277 /* Tests llx_reverse. */
1281 const int max_elems = 8;
1285 for (cnt = 0; cnt <= max_elems; cnt++)
1286 for (r0 = 0; r0 <= cnt; r0++)
1287 for (r1 = r0; r1 <= cnt; r1++)
1289 struct llx_list list;
1290 struct element **elems;
1296 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1297 check_list_contents (&list, values, cnt);
1300 for (i = 0; i < r0; i++)
1302 for (i = r1 - 1; i >= r0; i--)
1304 for (i = r1; i < cnt; i++)
1307 llx_reverse (elemp[r0], elemp[r1]);
1308 check_list_contents (&list, values, cnt);
1310 free_elements (cnt, &list, elems, elemp, values);
1314 /* Tests llx_next_permutation and llx_prev_permutation when the
1315 permuted values have no duplicates. */
1317 test_permutations_no_dups (void)
1319 const int max_elems = 8;
1322 for (cnt = 0; cnt <= max_elems; cnt++)
1324 struct llx_list list;
1325 struct element **elems;
1327 int *old_values = xnmalloc (cnt, sizeof *values);
1328 int *new_values = xnmalloc (cnt, sizeof *values);
1332 allocate_ascending (cnt, &list, &elems, NULL, &values);
1335 extract_values (&list, old_values, cnt);
1336 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1337 compare_elements, &aux_data))
1339 extract_values (&list, new_values, cnt);
1340 check (lexicographical_compare_3way (new_values, cnt,
1343 compare_ints, NULL) > 0);
1344 memcpy (old_values, new_values, (cnt) * sizeof *old_values);
1347 check (perm_cnt == factorial (cnt));
1348 check_list_contents (&list, values, cnt);
1351 llx_reverse (llx_head (&list), llx_null (&list));
1352 extract_values (&list, old_values, cnt);
1353 while (llx_prev_permutation (llx_head (&list), llx_null (&list),
1354 compare_elements, &aux_data))
1356 extract_values (&list, new_values, cnt);
1357 check (lexicographical_compare_3way (new_values, cnt,
1360 compare_ints, NULL) < 0);
1361 memcpy (old_values, new_values, (cnt) * sizeof *old_values);
1364 check (perm_cnt == factorial (cnt));
1365 llx_reverse (llx_head (&list), llx_null (&list));
1366 check_list_contents (&list, values, cnt);
1368 free_elements (cnt, &list, elems, NULL, values);
1374 /* Tests llx_next_permutation and llx_prev_permutation when the
1375 permuted values contain duplicates. */
1377 test_permutations_with_dups (void)
1379 const int max_elems = 8;
1380 const int max_dup = 3;
1381 const int repetitions = 1024;
1385 for (repeat = 0; repeat < repetitions; repeat++)
1386 for (cnt = 0; cnt < max_elems; cnt++)
1388 struct llx_list list;
1389 struct element **elems;
1392 int *old_values = xnmalloc (max_elems, sizeof *values);
1393 int *new_values = xnmalloc (max_elems, sizeof *values);
1395 unsigned int permutation_cnt;
1399 allocate_elements (cnt, &list, &elems, &elemp, &values);
1404 int max = left < max_dup ? left : max_dup;
1405 int n = rand () % max + 1;
1408 int idx = cnt - left--;
1409 values[idx] = elems[idx]->x = value;
1414 permutation_cnt = 1;
1415 extract_values (&list, old_values, cnt);
1416 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1417 compare_elements, &aux_data))
1419 extract_values (&list, new_values, cnt);
1420 check (lexicographical_compare_3way (new_values, cnt,
1423 compare_ints, NULL) > 0);
1424 memcpy (old_values, new_values, cnt * sizeof *old_values);
1427 check (permutation_cnt == expected_perms (values, cnt));
1428 check_list_contents (&list, values, cnt);
1430 permutation_cnt = 1;
1431 llx_reverse (llx_head (&list), llx_null (&list));
1432 extract_values (&list, old_values, cnt);
1433 while (llx_prev_permutation (llx_head (&list), llx_null (&list),
1434 compare_elements, &aux_data))
1436 extract_values (&list, new_values, cnt);
1437 check (lexicographical_compare_3way (new_values, cnt,
1440 compare_ints, NULL) < 0);
1443 llx_reverse (llx_head (&list), llx_null (&list));
1444 check (permutation_cnt == expected_perms (values, cnt));
1445 check_list_contents (&list, values, cnt);
1447 free_elements (cnt, &list, elems, elemp, values);
1453 /* Tests llx_merge when no equal values are to be merged. */
1455 test_merge_no_dups (void)
1457 const int max_elems = 8;
1458 const int max_fillxer = 3;
1460 int merge_cnt, pattern, pfx, gap, sfx, order;
1462 for (merge_cnt = 0; merge_cnt < max_elems; merge_cnt++)
1463 for (pattern = 0; pattern <= (1 << merge_cnt); pattern++)
1464 for (pfx = 0; pfx < max_fillxer; pfx++)
1465 for (gap = 0; gap < max_fillxer; gap++)
1466 for (sfx = 0; sfx < max_fillxer; sfx++)
1467 for (order = 0; order < 2; order++)
1469 struct llx_list list;
1470 struct element **elems;
1474 int list_cnt = pfx + merge_cnt + gap + sfx;
1478 allocate_elements (list_cnt, &list,
1479 &elems, &elemp, &values);
1482 for (i = 0; i < pfx; i++)
1483 elems[j++]->x = 100 + i;
1485 for (i = 0; i < merge_cnt; i++)
1486 if (pattern & (1u << i))
1489 for (i = 0; i < gap; i++)
1490 elems[j++]->x = 200 + i;
1492 for (i = 0; i < merge_cnt; i++)
1493 if (!(pattern & (1u << i)))
1496 for (i = 0; i < sfx; i++)
1497 elems[j++]->x = 300 + i;
1498 check (list_cnt == j);
1501 for (i = 0; i < pfx; i++)
1502 values[j++] = 100 + i;
1504 for (i = 0; i < merge_cnt; i++)
1506 for (i = 0; i < gap; i++)
1507 values[j++] = 200 + i;
1509 for (i = 0; i < merge_cnt; i++)
1511 for (i = 0; i < sfx; i++)
1512 values[j++] = 300 + i;
1513 check (list_cnt == j);
1516 llx_merge (elemp[a0], elemp[a1], elemp[b0], elemp[b1],
1517 compare_elements, &aux_data);
1519 llx_merge (elemp[b0], elemp[b1], elemp[a0], elemp[a1],
1520 compare_elements, &aux_data);
1522 check_list_contents (&list, values, list_cnt);
1524 free_elements (list_cnt, &list, elems, elemp, values);
1528 /* Tests llx_merge when equal values are to be merged. */
1530 test_merge_with_dups (void)
1532 const int max_elems = 8;
1534 int cnt, merge_pat, inc_pat, order;
1536 for (cnt = 0; cnt <= max_elems; cnt++)
1537 for (merge_pat = 0; merge_pat <= (1 << cnt); merge_pat++)
1538 for (inc_pat = 0; inc_pat <= (1 << cnt); inc_pat++)
1539 for (order = 0; order < 2; order++)
1541 struct llx_list list;
1542 struct element **elems;
1549 allocate_elements (cnt, &list, &elems, &elemp, &values);
1552 for (i = k = 0; i < cnt; i++)
1554 if (merge_pat & (1u << i))
1556 if (inc_pat & (1u << i))
1560 for (i = k = 0; i < cnt; i++)
1562 if (!(merge_pat & (1u << i)))
1564 if (inc_pat & (1u << i))
1571 for (i = 0; i < cnt; i++)
1576 for (i = 0; i < mid; i++)
1577 elems[i]->y = 100 + i;
1578 for (i = mid; i < cnt; i++)
1583 for (i = k = 0; i < cnt; i++)
1586 if (inc_pat & (1u << i))
1592 llx_merge (elemp[0], elemp[mid], elemp[mid], elemp[cnt],
1593 compare_elements, &aux_data);
1595 llx_merge (elemp[mid], elemp[cnt], elemp[0], elemp[mid],
1596 compare_elements, &aux_data);
1598 check_list_contents (&list, values, cnt);
1599 check (llx_is_sorted (llx_head (&list), llx_null (&list),
1600 compare_elements_x_y, &aux_data));
1602 free_elements (cnt, &list, elems, elemp, values);
1606 /* Tests llx_sort on all permutations up to a maximum number of
1609 test_sort_exhaustive (void)
1611 const int max_elems = 8;
1614 for (cnt = 0; cnt <= max_elems; cnt++)
1616 struct llx_list list;
1617 struct element **elems;
1620 struct element **perm_elems;
1625 allocate_ascending (cnt, &list, &elems, NULL, &values);
1626 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1629 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1630 compare_elements, &aux_data))
1632 struct llx_list perm_list;
1635 extract_values (&list, perm_values, cnt);
1636 llx_init (&perm_list);
1637 for (j = 0; j < cnt; j++)
1639 perm_elems[j]->x = perm_values[j];
1640 llx_push_tail (&perm_list, perm_elems[j], &llx_malloc_mgr);
1642 llx_sort (llx_head (&perm_list), llx_null (&perm_list),
1643 compare_elements, &aux_data);
1644 check_list_contents (&perm_list, values, cnt);
1645 check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
1646 compare_elements, &aux_data));
1647 llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
1650 check (perm_cnt == factorial (cnt));
1652 free_elements (cnt, &list, elems, NULL, values);
1653 free_elements (cnt, NULL, perm_elems, NULL, perm_values);
1657 /* Tests that llx_sort is stable in the presence of equal
1660 test_sort_stable (void)
1662 const int max_elems = 6;
1665 for (cnt = 0; cnt <= max_elems; cnt++)
1666 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1668 struct llx_list list;
1669 struct element **elems;
1672 struct element **perm_elems;
1678 allocate_elements (cnt, &list, &elems, NULL, &values);
1679 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1682 for (i = 0; i < cnt; i++)
1684 elems[i]->x = values[i] = j;
1685 if (inc_pat & (1 << i))
1691 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1692 compare_elements_y, &aux_data))
1694 struct llx_list perm_list;
1696 extract_values (&list, perm_values, cnt);
1697 llx_init (&perm_list);
1698 for (i = 0; i < cnt; i++)
1700 perm_elems[i]->x = perm_values[i];
1701 perm_elems[i]->y = i;
1702 llx_push_tail (&perm_list, perm_elems[i], &llx_malloc_mgr);
1704 llx_sort (llx_head (&perm_list), llx_null (&perm_list),
1705 compare_elements, &aux_data);
1706 check_list_contents (&perm_list, values, cnt);
1707 check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
1708 compare_elements_x_y, &aux_data));
1709 llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
1712 check (perm_cnt == factorial (cnt));
1714 free_elements (cnt, &list, elems, NULL, values);
1715 free_elements (cnt, NULL, perm_elems, NULL, perm_values);
1719 /* Tests that llx_sort does not disturb elements outside the
1722 test_sort_subset (void)
1724 const int max_elems = 8;
1726 int cnt, r0, r1, repeat;
1728 for (cnt = 0; cnt <= max_elems; cnt++)
1729 for (repeat = 0; repeat < 100; repeat++)
1730 for (r0 = 0; r0 <= cnt; r0++)
1731 for (r1 = r0; r1 <= cnt; r1++)
1733 struct llx_list list;
1734 struct element **elems;
1738 allocate_random (cnt, &list, &elems, &elemp, &values);
1740 qsort (&values[r0], r1 - r0, sizeof *values, compare_ints_noaux);
1741 llx_sort (elemp[r0], elemp[r1], compare_elements, &aux_data);
1742 check_list_contents (&list, values, cnt);
1744 free_elements (cnt, &list, elems, elemp, values);
1748 /* Tests that llx_sort works with large lists. */
1750 test_sort_big (void)
1752 const int max_elems = 1024;
1756 for (cnt = 0; cnt < max_elems; cnt++)
1758 struct llx_list list;
1759 struct element **elems;
1762 allocate_random (cnt, &list, &elems, NULL, &values);
1764 qsort (values, cnt, sizeof *values, compare_ints_noaux);
1765 llx_sort (llx_head (&list), llx_null (&list), compare_elements, &aux_data);
1766 check_list_contents (&list, values, cnt);
1768 free_elements (cnt, &list, elems, NULL, values);
1772 /* Tests llx_unique. */
1776 const int max_elems = 10;
1778 int *ascending = xnmalloc (max_elems, sizeof *ascending);
1780 int cnt, inc_pat, i, j, unique_values;
1782 for (i = 0; i < max_elems; i++)
1785 for (cnt = 0; cnt < max_elems; cnt++)
1786 for (inc_pat = 0; inc_pat < (1 << cnt); inc_pat++)
1788 struct llx_list list, dups;
1789 struct element **elems;
1792 allocate_elements (cnt, &list, &elems, NULL, &values);
1794 j = unique_values = 0;
1795 for (i = 0; i < cnt; i++)
1797 unique_values = j + 1;
1798 elems[i]->x = values[i] = j;
1799 if (inc_pat & (1 << i))
1802 check_list_contents (&list, values, cnt);
1805 check (llx_unique (llx_head (&list), llx_null (&list),
1807 compare_elements, &aux_data,
1809 == (size_t) unique_values);
1810 check_list_contents (&list, ascending, unique_values);
1812 llx_splice (llx_null (&list), llx_head (&dups), llx_null (&dups));
1813 llx_sort (llx_head (&list), llx_null (&list), compare_elements, &aux_data);
1814 check_list_contents (&list, values, cnt);
1816 llx_destroy (&dups, NULL, NULL, &llx_malloc_mgr);
1817 free_elements (cnt, &list, elems, NULL, values);
1823 /* Tests llx_sort_unique. */
1825 test_sort_unique (void)
1827 const int max_elems = 7;
1830 for (cnt = 0; cnt <= max_elems; cnt++)
1831 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1833 struct llx_list list;
1834 struct element **elems;
1837 struct element **perm_elems;
1846 allocate_elements (cnt, &list, &elems, NULL, &values);
1847 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1850 for (i = 0; i < cnt; i++)
1852 elems[i]->x = values[i] = j;
1854 if (inc_pat & (1 << i))
1858 unique_values = xnmalloc (unique_cnt, sizeof *unique_values);
1859 for (i = 0; i < unique_cnt; i++)
1860 unique_values[i] = i;
1863 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1864 compare_elements, &aux_data))
1866 struct llx_list perm_list;
1868 extract_values (&list, perm_values, cnt);
1869 llx_init (&perm_list);
1870 for (i = 0; i < cnt; i++)
1872 perm_elems[i]->x = perm_values[i];
1873 perm_elems[i]->y = i;
1874 llx_push_tail (&perm_list, perm_elems[i], &llx_malloc_mgr);
1876 llx_sort_unique (llx_head (&perm_list), llx_null (&perm_list), NULL,
1877 compare_elements, &aux_data,
1879 check_list_contents (&perm_list, unique_values, unique_cnt);
1880 check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
1881 compare_elements_x_y, &aux_data));
1882 llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
1885 check (perm_cnt == expected_perms (values, cnt));
1887 free_elements (cnt, &list, elems, NULL, values);
1888 free_elements (cnt, NULL, perm_elems, NULL, perm_values);
1889 free (unique_values);
1893 /* Tests llx_insert_ordered. */
1895 test_insert_ordered (void)
1897 const int max_elems = 6;
1900 for (cnt = 0; cnt <= max_elems; cnt++)
1901 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1903 struct llx_list list;
1904 struct element **elems;
1907 struct element **perm_elems;
1913 allocate_elements (cnt, &list, &elems, NULL, &values);
1914 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1917 for (i = 0; i < cnt; i++)
1919 elems[i]->x = values[i] = j;
1920 if (inc_pat & (1 << i))
1926 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1927 compare_elements_y, &aux_data))
1929 struct llx_list perm_list;
1931 extract_values (&list, perm_values, cnt);
1932 llx_init (&perm_list);
1933 for (i = 0; i < cnt; i++)
1935 perm_elems[i]->x = perm_values[i];
1936 perm_elems[i]->y = i;
1937 llx_insert_ordered (llx_head (&perm_list),
1938 llx_null (&perm_list),
1940 compare_elements, &aux_data,
1943 check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
1944 compare_elements_x_y, &aux_data));
1945 llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
1948 check (perm_cnt == factorial (cnt));
1950 free_elements (cnt, &list, elems, NULL, values);
1951 free_elements (cnt, NULL, perm_elems, NULL, perm_values);
1955 /* Tests llx_partition. */
1957 test_partition (void)
1959 const int max_elems = 10;
1965 for (cnt = 0; cnt < max_elems; cnt++)
1966 for (r0 = 0; r0 <= cnt; r0++)
1967 for (r1 = r0; r1 <= cnt; r1++)
1968 for (pbase = 0; pbase <= (1u << (r1 - r0)); pbase++)
1970 struct llx_list list;
1971 struct element **elems;
1975 unsigned int pattern = pbase << r0;
1978 struct llx *part_llx;
1980 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1982 /* Check that llx_find_partition works okay in every
1983 case. We use it after partitioning, too, but that
1984 only tests cases where it returns non-null. */
1985 for (i = r0; i < r1; i++)
1986 if (!(pattern & (1u << i)))
1990 if (pattern & (1u << i))
1992 part_llx = llx_find_partition (elemp[r0], elemp[r1],
1996 check (part_llx == elemp[j]);
1998 check (part_llx == NULL);
2000 /* Figure out expected results. */
2003 for (i = 0; i < r0; i++)
2005 for (i = r0; i < r1; i++)
2006 if (pattern & (1u << i))
2008 for (i = r0; i < r1; i++)
2009 if (!(pattern & (1u << i)))
2011 if (first_false == -1)
2015 if (first_false == -1)
2017 for (i = r1; i < cnt; i++)
2021 /* Partition and check for expected results. */
2022 check (llx_partition (elemp[r0], elemp[r1],
2023 pattern_pred, &pattern)
2024 == elemp[first_false]);
2025 check (llx_find_partition (elemp[r0], elemp[r1],
2026 pattern_pred, &pattern)
2027 == elemp[first_false]);
2028 check_list_contents (&list, values, cnt);
2029 check ((int) llx_count (&list) == cnt);
2031 free_elements (cnt, &list, elems, elemp, values);
2035 /* Tests that allocation failure is gracefully handled. */
2037 test_allocation_failure (void)
2039 struct llx_list list;
2042 check (llx_push_head (&list, NULL, &llx_null_mgr) == NULL);
2043 check (llx_push_tail (&list, NULL, &llx_null_mgr) == NULL);
2044 check (llx_insert (llx_null (&list), NULL, &llx_null_mgr) == NULL);
2045 check_list_contents (&list, NULL, 0);
2050 /* Runs TEST_FUNCTION and prints a message about NAME. */
2052 run_test (void (*test_function) (void), const char *name)
2063 run_test (test_push_pop, "push/pop");
2064 run_test (test_insert_remove, "insert/remove");
2065 run_test (test_swap, "swap");
2066 run_test (test_swap_range, "swap_range");
2067 run_test (test_remove_range, "remove_range");
2068 run_test (test_remove_equal, "remove_equal");
2069 run_test (test_remove_if, "remove_if");
2070 run_test (test_find_equal, "find_equal");
2071 run_test (test_find, "find");
2072 run_test (test_find_if, "find_if");
2073 run_test (test_find_adjacent_equal, "find_adjacent_equal");
2074 run_test (test_count_range, "count_range");
2075 run_test (test_count_equal, "count_equal");
2076 run_test (test_count_if, "count_if");
2077 run_test (test_min_max, "min/max");
2078 run_test (test_lexicographical_compare_3way, "lexicographical_compare_3way");
2079 run_test (test_apply, "apply");
2080 run_test (test_destroy, "destroy");
2081 run_test (test_reverse, "reverse");
2082 run_test (test_permutations_no_dups, "permutations (no dups)");
2083 run_test (test_permutations_with_dups, "permutations (with dups)");
2084 run_test (test_merge_no_dups, "merge (no dups)");
2085 run_test (test_merge_with_dups, "merge (with dups)");
2086 run_test (test_sort_exhaustive, "sort (exhaustive)");
2087 run_test (test_sort_stable, "sort (stability)");
2088 run_test (test_sort_subset, "sort (subset)");
2089 run_test (test_sort_big, "sort (big)");
2090 run_test (test_unique, "unique");
2091 run_test (test_sort_unique, "sort_unique");
2092 run_test (test_insert_ordered, "insert_ordered");
2093 run_test (test_partition, "partition");
2094 run_test (test_allocation_failure, "allocation failure");
2102 compile-command: "gcc -Wall -Wstrict-prototypes -Wmissing-prototypes ll.c llx.c llx-test.c -o llx-test -g"