1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2006 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 /* Helper function for testing llx_find_if. */
870 test_find_if_helper (int r0, int r1, int eq_pat, struct llx **elemp)
872 struct llx *match = llx_find_if (elemp[r0], elemp[r1],
873 pattern_pred, &eq_pat);
876 for (i = r0; i < r1; i++)
877 if (eq_pat & (1 << i))
880 check (match == elemp[i]);
883 /* Tests llx_find_if. */
887 test_examine_if_range (test_find_if_helper);
890 /* Tests llx_find_adjacent_equal. */
892 test_find_adjacent_equal (void)
894 const int max_elems = 8;
898 for (cnt = 0; cnt <= max_elems; cnt++)
899 for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
901 struct llx_list list;
902 struct element **elems;
909 allocate_ascending (cnt, &list, &elems, &elemp, &values);
912 for (i = 0; i < cnt - 1; i++)
915 if (eq_pat & (1 << i))
917 values[i] = elems[i]->x = match;
918 values[i + 1] = elems[i + 1]->x = match;
924 for (i = 0; i <= cnt; i++)
926 struct llx *llx1 = llx_find_adjacent_equal (elemp[i], llx_null (&list),
932 llx2 = llx_null (&list);
933 for (j = i; j < cnt - 1; j++)
934 if (eq_pat & (1 << j))
939 check (llx1 == llx2);
941 check_list_contents (&list, values, cnt);
943 free_elements (cnt, &list, elems, elemp, values);
947 /* Helper function for testing llx_count_range. */
949 test_count_range_helper (int r0, int r1, int eq_pat UNUSED, struct llx **elemp)
951 check ((int) llx_count_range (elemp[r0], elemp[r1]) == r1 - r0);
954 /* Tests llx_count_range. */
956 test_count_range (void)
958 test_examine_if_range (test_count_range_helper);
961 /* Helper function for testing llx_count_equal. */
963 test_count_equal_helper (int r0, int r1, int eq_pat,
964 const void *to_find, struct llx **elemp)
969 count1 = llx_count_equal (elemp[r0], elemp[r1], to_find,
970 compare_elements, &aux_data);
972 for (i = r0; i < r1; i++)
973 if (eq_pat & (1 << i))
976 check (count1 == count2);
979 /* Tests llx_count_equal. */
981 test_count_equal (void)
983 test_examine_equal_range (test_count_equal_helper);
986 /* Helper function for testing llx_count_if. */
988 test_count_if_helper (int r0, int r1, int eq_pat, struct llx **elemp)
994 count1 = llx_count_if (elemp[r0], elemp[r1], pattern_pred, &eq_pat);
997 for (i = r0; i < r1; i++)
998 if (eq_pat & (1 << i))
1001 check (count1 == count2);
1004 /* Tests llx_count_if. */
1006 test_count_if (void)
1008 test_examine_if_range (test_count_if_helper);
1013 factorial (unsigned int n)
1015 unsigned int value = 1;
1021 /* Returns the number of permutations of the CNT values in
1022 VALUES. If VALUES contains duplicates, they must be
1025 expected_perms (int *values, size_t cnt)
1028 unsigned int perm_cnt;
1030 perm_cnt = factorial (cnt);
1031 for (i = 0; i < cnt; i = j)
1033 for (j = i + 1; j < cnt; j++)
1034 if (values[i] != values[j])
1036 perm_cnt /= factorial (j - i);
1041 /* Tests llx_min and llx_max. */
1045 const int max_elems = 6;
1048 for (cnt = 0; cnt <= max_elems; cnt++)
1050 struct llx_list list;
1051 struct element **elems;
1054 int *new_values = xnmalloc (cnt, sizeof *values);
1058 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1061 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1062 compare_elements, &aux_data))
1068 for (i = 0, x = llx_head (&list); x != llx_null (&list);
1069 x = llx_next (x), i++)
1071 struct element *e = llx_data (x);
1073 new_values[i] = e->x;
1075 for (r0 = 0; r0 <= cnt; r0++)
1076 for (r1 = r0; r1 <= cnt; r1++)
1078 struct llx *min = llx_min (elemp[r0], elemp[r1],
1079 compare_elements, &aux_data);
1080 struct llx *max = llx_max (elemp[r0], elemp[r1],
1081 compare_elements, &aux_data);
1084 check (min == elemp[r1]);
1085 check (max == elemp[r1]);
1089 struct element *min_elem = llx_data (min);
1090 struct element *max_elem = llx_data (max);
1091 int min_int, max_int;
1094 min_int = max_int = new_values[r0];
1095 for (i = r0; i < r1; i++)
1097 int value = new_values[i];
1098 if (value < min_int)
1100 if (value > max_int)
1103 check (min != elemp[r1] && min_elem->x == min_int);
1104 check (max != elemp[r1] && max_elem->x == max_int);
1109 check (perm_cnt == factorial (cnt));
1110 check_list_contents (&list, values, cnt);
1112 free_elements (cnt, &list, elems, elemp, values);
1117 /* Tests llx_lexicographical_compare_3way. */
1119 test_lexicographical_compare_3way (void)
1121 const int max_elems = 4;
1123 int cnt_a, pat_a, cnt_b, pat_b;
1125 for (cnt_a = 0; cnt_a <= max_elems; cnt_a++)
1126 for (pat_a = 0; pat_a <= 1 << cnt_a; pat_a++)
1127 for (cnt_b = 0; cnt_b <= max_elems; cnt_b++)
1128 for (pat_b = 0; pat_b <= 1 << cnt_b; pat_b++)
1130 struct llx_list list_a, list_b;
1131 struct element **elems_a, **elems_b;
1132 struct llx **elemp_a, **elemp_b;
1133 int *values_a, *values_b;
1137 allocate_pattern (cnt_a, pat_a,
1138 &list_a, &elems_a, &elemp_a, &values_a);
1139 allocate_pattern (cnt_b, pat_b,
1140 &list_b, &elems_b, &elemp_b, &values_b);
1142 for (a0 = 0; a0 <= cnt_a; a0++)
1143 for (a1 = a0; a1 <= cnt_a; a1++)
1144 for (b0 = 0; b0 <= cnt_b; b0++)
1145 for (b1 = b0; b1 <= cnt_b; b1++)
1147 int a_ordering = lexicographical_compare_3way (
1148 values_a + a0, a1 - a0,
1149 values_b + b0, b1 - b0,
1151 compare_ints, NULL);
1153 int b_ordering = llx_lexicographical_compare_3way (
1154 elemp_a[a0], elemp_a[a1],
1155 elemp_b[b0], elemp_b[b1],
1156 compare_elements, &aux_data);
1158 check (a_ordering == b_ordering);
1161 free_elements (cnt_a, &list_a, elems_a, elemp_a, values_a);
1162 free_elements (cnt_b, &list_b, elems_b, elemp_b, values_b);
1166 /* Appends the `x' value in element E to the array pointed to by
1167 NEXT_OUTPUT, and advances NEXT_OUTPUT to the next position. */
1169 apply_func (void *e_, void *next_output_)
1171 struct element *e = e_;
1172 int **next_output = next_output_;
1174 *(*next_output)++ = e->x;
1177 /* Tests llx_apply. */
1181 const int max_elems = 8;
1185 for (cnt = 0; cnt <= max_elems; cnt++)
1186 for (r0 = 0; r0 <= cnt; r0++)
1187 for (r1 = r0; r1 <= cnt; r1++)
1189 struct llx_list list;
1190 struct element **elems;
1198 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1199 check_list_contents (&list, values, cnt);
1201 output = next_output = xnmalloc (cnt, sizeof *output);
1202 llx_apply (elemp[r0], elemp[r1], apply_func, &next_output);
1203 check_list_contents (&list, values, cnt);
1204 llx_destroy (&list, NULL, NULL, &llx_malloc_mgr);
1206 check (r1 - r0 == next_output - output);
1207 for (j = 0; j < r1 - r0; j++)
1208 check (output[j] == r0 + j);
1210 free_elements (cnt, NULL, elems, elemp, values);
1215 /* Tests llx_destroy. */
1219 const int max_elems = 8;
1223 for (cnt = 0; cnt <= max_elems; cnt++)
1225 struct llx_list list;
1226 struct element **elems;
1234 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1235 check_list_contents (&list, values, cnt);
1237 output = next_output = xnmalloc (cnt, sizeof *output);
1238 llx_destroy (&list, apply_func, &next_output, &llx_malloc_mgr);
1240 check (cnt == next_output - output);
1241 for (j = 0; j < cnt; j++)
1242 check (output[j] == j);
1244 free_elements (cnt, NULL, elems, elemp, values);
1249 /* Tests llx_reverse. */
1253 const int max_elems = 8;
1257 for (cnt = 0; cnt <= max_elems; cnt++)
1258 for (r0 = 0; r0 <= cnt; r0++)
1259 for (r1 = r0; r1 <= cnt; r1++)
1261 struct llx_list list;
1262 struct element **elems;
1268 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1269 check_list_contents (&list, values, cnt);
1272 for (i = 0; i < r0; i++)
1274 for (i = r1 - 1; i >= r0; i--)
1276 for (i = r1; i < cnt; i++)
1279 llx_reverse (elemp[r0], elemp[r1]);
1280 check_list_contents (&list, values, cnt);
1282 free_elements (cnt, &list, elems, elemp, values);
1286 /* Tests llx_next_permutation and llx_prev_permutation when the
1287 permuted values have no duplicates. */
1289 test_permutations_no_dups (void)
1291 const int max_elems = 8;
1294 for (cnt = 0; cnt <= max_elems; cnt++)
1296 struct llx_list list;
1297 struct element **elems;
1299 int *old_values = xnmalloc (cnt, sizeof *values);
1300 int *new_values = xnmalloc (cnt, sizeof *values);
1304 allocate_ascending (cnt, &list, &elems, NULL, &values);
1307 extract_values (&list, old_values, cnt);
1308 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1309 compare_elements, &aux_data))
1311 extract_values (&list, new_values, cnt);
1312 check (lexicographical_compare_3way (new_values, cnt,
1315 compare_ints, NULL) > 0);
1316 memcpy (old_values, new_values, (cnt) * sizeof *old_values);
1319 check (perm_cnt == factorial (cnt));
1320 check_list_contents (&list, values, cnt);
1323 llx_reverse (llx_head (&list), llx_null (&list));
1324 extract_values (&list, old_values, cnt);
1325 while (llx_prev_permutation (llx_head (&list), llx_null (&list),
1326 compare_elements, &aux_data))
1328 extract_values (&list, new_values, cnt);
1329 check (lexicographical_compare_3way (new_values, cnt,
1332 compare_ints, NULL) < 0);
1333 memcpy (old_values, new_values, (cnt) * sizeof *old_values);
1336 check (perm_cnt == factorial (cnt));
1337 llx_reverse (llx_head (&list), llx_null (&list));
1338 check_list_contents (&list, values, cnt);
1340 free_elements (cnt, &list, elems, NULL, values);
1346 /* Tests llx_next_permutation and llx_prev_permutation when the
1347 permuted values contain duplicates. */
1349 test_permutations_with_dups (void)
1351 const int max_elems = 8;
1352 const int max_dup = 3;
1353 const int repetitions = 1024;
1357 for (repeat = 0; repeat < repetitions; repeat++)
1358 for (cnt = 0; cnt < max_elems; cnt++)
1360 struct llx_list list;
1361 struct element **elems;
1364 int *old_values = xnmalloc (max_elems, sizeof *values);
1365 int *new_values = xnmalloc (max_elems, sizeof *values);
1367 unsigned int permutation_cnt;
1371 allocate_elements (cnt, &list, &elems, &elemp, &values);
1376 int max = left < max_dup ? left : max_dup;
1377 int n = rand () % max + 1;
1380 int idx = cnt - left--;
1381 values[idx] = elems[idx]->x = value;
1386 permutation_cnt = 1;
1387 extract_values (&list, old_values, cnt);
1388 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1389 compare_elements, &aux_data))
1391 extract_values (&list, new_values, cnt);
1392 check (lexicographical_compare_3way (new_values, cnt,
1395 compare_ints, NULL) > 0);
1396 memcpy (old_values, new_values, cnt * sizeof *old_values);
1399 check (permutation_cnt == expected_perms (values, cnt));
1400 check_list_contents (&list, values, cnt);
1402 permutation_cnt = 1;
1403 llx_reverse (llx_head (&list), llx_null (&list));
1404 extract_values (&list, old_values, cnt);
1405 while (llx_prev_permutation (llx_head (&list), llx_null (&list),
1406 compare_elements, &aux_data))
1408 extract_values (&list, new_values, cnt);
1409 check (lexicographical_compare_3way (new_values, cnt,
1412 compare_ints, NULL) < 0);
1415 llx_reverse (llx_head (&list), llx_null (&list));
1416 check (permutation_cnt == expected_perms (values, cnt));
1417 check_list_contents (&list, values, cnt);
1419 free_elements (cnt, &list, elems, elemp, values);
1425 /* Tests llx_merge when no equal values are to be merged. */
1427 test_merge_no_dups (void)
1429 const int max_elems = 8;
1430 const int max_fillxer = 3;
1432 int merge_cnt, pattern, pfx, gap, sfx, order;
1434 for (merge_cnt = 0; merge_cnt < max_elems; merge_cnt++)
1435 for (pattern = 0; pattern <= (1 << merge_cnt); pattern++)
1436 for (pfx = 0; pfx < max_fillxer; pfx++)
1437 for (gap = 0; gap < max_fillxer; gap++)
1438 for (sfx = 0; sfx < max_fillxer; sfx++)
1439 for (order = 0; order < 2; order++)
1441 struct llx_list list;
1442 struct element **elems;
1446 int list_cnt = pfx + merge_cnt + gap + sfx;
1450 allocate_elements (list_cnt, &list,
1451 &elems, &elemp, &values);
1454 for (i = 0; i < pfx; i++)
1455 elems[j++]->x = 100 + i;
1457 for (i = 0; i < merge_cnt; i++)
1458 if (pattern & (1u << i))
1461 for (i = 0; i < gap; i++)
1462 elems[j++]->x = 200 + i;
1464 for (i = 0; i < merge_cnt; i++)
1465 if (!(pattern & (1u << i)))
1468 for (i = 0; i < sfx; i++)
1469 elems[j++]->x = 300 + i;
1470 check (list_cnt == j);
1473 for (i = 0; i < pfx; i++)
1474 values[j++] = 100 + i;
1476 for (i = 0; i < merge_cnt; i++)
1478 for (i = 0; i < gap; i++)
1479 values[j++] = 200 + i;
1481 for (i = 0; i < merge_cnt; i++)
1483 for (i = 0; i < sfx; i++)
1484 values[j++] = 300 + i;
1485 check (list_cnt == j);
1488 llx_merge (elemp[a0], elemp[a1], elemp[b0], elemp[b1],
1489 compare_elements, &aux_data);
1491 llx_merge (elemp[b0], elemp[b1], elemp[a0], elemp[a1],
1492 compare_elements, &aux_data);
1494 check_list_contents (&list, values, list_cnt);
1496 free_elements (list_cnt, &list, elems, elemp, values);
1500 /* Tests llx_merge when equal values are to be merged. */
1502 test_merge_with_dups (void)
1504 const int max_elems = 8;
1506 int cnt, merge_pat, inc_pat, order;
1508 for (cnt = 0; cnt <= max_elems; cnt++)
1509 for (merge_pat = 0; merge_pat <= (1 << cnt); merge_pat++)
1510 for (inc_pat = 0; inc_pat <= (1 << cnt); inc_pat++)
1511 for (order = 0; order < 2; order++)
1513 struct llx_list list;
1514 struct element **elems;
1521 allocate_elements (cnt, &list, &elems, &elemp, &values);
1524 for (i = k = 0; i < cnt; i++)
1526 if (merge_pat & (1u << i))
1528 if (inc_pat & (1u << i))
1532 for (i = k = 0; i < cnt; i++)
1534 if (!(merge_pat & (1u << i)))
1536 if (inc_pat & (1u << i))
1543 for (i = 0; i < cnt; i++)
1548 for (i = 0; i < mid; i++)
1549 elems[i]->y = 100 + i;
1550 for (i = mid; i < cnt; i++)
1555 for (i = k = 0; i < cnt; i++)
1558 if (inc_pat & (1u << i))
1564 llx_merge (elemp[0], elemp[mid], elemp[mid], elemp[cnt],
1565 compare_elements, &aux_data);
1567 llx_merge (elemp[mid], elemp[cnt], elemp[0], elemp[mid],
1568 compare_elements, &aux_data);
1570 check_list_contents (&list, values, cnt);
1571 check (llx_is_sorted (llx_head (&list), llx_null (&list),
1572 compare_elements_x_y, &aux_data));
1574 free_elements (cnt, &list, elems, elemp, values);
1578 /* Tests llx_sort on all permutations up to a maximum number of
1581 test_sort_exhaustive (void)
1583 const int max_elems = 8;
1586 for (cnt = 0; cnt <= max_elems; cnt++)
1588 struct llx_list list;
1589 struct element **elems;
1592 struct element **perm_elems;
1597 allocate_ascending (cnt, &list, &elems, NULL, &values);
1598 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1601 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1602 compare_elements, &aux_data))
1604 struct llx_list perm_list;
1607 extract_values (&list, perm_values, cnt);
1608 llx_init (&perm_list);
1609 for (j = 0; j < cnt; j++)
1611 perm_elems[j]->x = perm_values[j];
1612 llx_push_tail (&perm_list, perm_elems[j], &llx_malloc_mgr);
1614 llx_sort (llx_head (&perm_list), llx_null (&perm_list),
1615 compare_elements, &aux_data);
1616 check_list_contents (&perm_list, values, cnt);
1617 check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
1618 compare_elements, &aux_data));
1619 llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
1622 check (perm_cnt == factorial (cnt));
1624 free_elements (cnt, &list, elems, NULL, values);
1625 free_elements (cnt, NULL, perm_elems, NULL, perm_values);
1629 /* Tests that llx_sort is stable in the presence of equal
1632 test_sort_stable (void)
1634 const int max_elems = 6;
1637 for (cnt = 0; cnt <= max_elems; cnt++)
1638 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1640 struct llx_list list;
1641 struct element **elems;
1644 struct element **perm_elems;
1650 allocate_elements (cnt, &list, &elems, NULL, &values);
1651 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1654 for (i = 0; i < cnt; i++)
1656 elems[i]->x = values[i] = j;
1657 if (inc_pat & (1 << i))
1663 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1664 compare_elements_y, &aux_data))
1666 struct llx_list perm_list;
1668 extract_values (&list, perm_values, cnt);
1669 llx_init (&perm_list);
1670 for (i = 0; i < cnt; i++)
1672 perm_elems[i]->x = perm_values[i];
1673 perm_elems[i]->y = i;
1674 llx_push_tail (&perm_list, perm_elems[i], &llx_malloc_mgr);
1676 llx_sort (llx_head (&perm_list), llx_null (&perm_list),
1677 compare_elements, &aux_data);
1678 check_list_contents (&perm_list, values, cnt);
1679 check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
1680 compare_elements_x_y, &aux_data));
1681 llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
1684 check (perm_cnt == factorial (cnt));
1686 free_elements (cnt, &list, elems, NULL, values);
1687 free_elements (cnt, NULL, perm_elems, NULL, perm_values);
1691 /* Tests that llx_sort does not disturb elements outside the
1694 test_sort_subset (void)
1696 const int max_elems = 8;
1698 int cnt, r0, r1, repeat;
1700 for (cnt = 0; cnt <= max_elems; cnt++)
1701 for (repeat = 0; repeat < 100; repeat++)
1702 for (r0 = 0; r0 <= cnt; r0++)
1703 for (r1 = r0; r1 <= cnt; r1++)
1705 struct llx_list list;
1706 struct element **elems;
1710 allocate_random (cnt, &list, &elems, &elemp, &values);
1712 qsort (&values[r0], r1 - r0, sizeof *values, compare_ints_noaux);
1713 llx_sort (elemp[r0], elemp[r1], compare_elements, &aux_data);
1714 check_list_contents (&list, values, cnt);
1716 free_elements (cnt, &list, elems, elemp, values);
1720 /* Tests that llx_sort works with large lists. */
1722 test_sort_big (void)
1724 const int max_elems = 1024;
1728 for (cnt = 0; cnt < max_elems; cnt++)
1730 struct llx_list list;
1731 struct element **elems;
1734 allocate_random (cnt, &list, &elems, NULL, &values);
1736 qsort (values, cnt, sizeof *values, compare_ints_noaux);
1737 llx_sort (llx_head (&list), llx_null (&list), compare_elements, &aux_data);
1738 check_list_contents (&list, values, cnt);
1740 free_elements (cnt, &list, elems, NULL, values);
1744 /* Tests llx_unique. */
1748 const int max_elems = 10;
1750 int *ascending = xnmalloc (max_elems, sizeof *ascending);
1752 int cnt, inc_pat, i, j, unique_values;
1754 for (i = 0; i < max_elems; i++)
1757 for (cnt = 0; cnt < max_elems; cnt++)
1758 for (inc_pat = 0; inc_pat < (1 << cnt); inc_pat++)
1760 struct llx_list list, dups;
1761 struct element **elems;
1764 allocate_elements (cnt, &list, &elems, NULL, &values);
1766 j = unique_values = 0;
1767 for (i = 0; i < cnt; i++)
1769 unique_values = j + 1;
1770 elems[i]->x = values[i] = j;
1771 if (inc_pat & (1 << i))
1774 check_list_contents (&list, values, cnt);
1777 check (llx_unique (llx_head (&list), llx_null (&list),
1779 compare_elements, &aux_data,
1781 == (size_t) unique_values);
1782 check_list_contents (&list, ascending, unique_values);
1784 llx_splice (llx_null (&list), llx_head (&dups), llx_null (&dups));
1785 llx_sort (llx_head (&list), llx_null (&list), compare_elements, &aux_data);
1786 check_list_contents (&list, values, cnt);
1788 llx_destroy (&dups, NULL, NULL, &llx_malloc_mgr);
1789 free_elements (cnt, &list, elems, NULL, values);
1795 /* Tests llx_sort_unique. */
1797 test_sort_unique (void)
1799 const int max_elems = 7;
1802 for (cnt = 0; cnt <= max_elems; cnt++)
1803 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1805 struct llx_list list;
1806 struct element **elems;
1809 struct element **perm_elems;
1818 allocate_elements (cnt, &list, &elems, NULL, &values);
1819 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1822 for (i = 0; i < cnt; i++)
1824 elems[i]->x = values[i] = j;
1826 if (inc_pat & (1 << i))
1830 unique_values = xnmalloc (unique_cnt, sizeof *unique_values);
1831 for (i = 0; i < unique_cnt; i++)
1832 unique_values[i] = i;
1835 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1836 compare_elements, &aux_data))
1838 struct llx_list perm_list;
1840 extract_values (&list, perm_values, cnt);
1841 llx_init (&perm_list);
1842 for (i = 0; i < cnt; i++)
1844 perm_elems[i]->x = perm_values[i];
1845 perm_elems[i]->y = i;
1846 llx_push_tail (&perm_list, perm_elems[i], &llx_malloc_mgr);
1848 llx_sort_unique (llx_head (&perm_list), llx_null (&perm_list), NULL,
1849 compare_elements, &aux_data,
1851 check_list_contents (&perm_list, unique_values, unique_cnt);
1852 check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
1853 compare_elements_x_y, &aux_data));
1854 llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
1857 check (perm_cnt == expected_perms (values, cnt));
1859 free_elements (cnt, &list, elems, NULL, values);
1860 free_elements (cnt, NULL, perm_elems, NULL, perm_values);
1861 free (unique_values);
1865 /* Tests llx_insert_ordered. */
1867 test_insert_ordered (void)
1869 const int max_elems = 6;
1872 for (cnt = 0; cnt <= max_elems; cnt++)
1873 for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1875 struct llx_list list;
1876 struct element **elems;
1879 struct element **perm_elems;
1885 allocate_elements (cnt, &list, &elems, NULL, &values);
1886 allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1889 for (i = 0; i < cnt; i++)
1891 elems[i]->x = values[i] = j;
1892 if (inc_pat & (1 << i))
1898 while (llx_next_permutation (llx_head (&list), llx_null (&list),
1899 compare_elements_y, &aux_data))
1901 struct llx_list perm_list;
1903 extract_values (&list, perm_values, cnt);
1904 llx_init (&perm_list);
1905 for (i = 0; i < cnt; i++)
1907 perm_elems[i]->x = perm_values[i];
1908 perm_elems[i]->y = i;
1909 llx_insert_ordered (llx_head (&perm_list),
1910 llx_null (&perm_list),
1912 compare_elements, &aux_data,
1915 check (llx_is_sorted (llx_head (&perm_list), llx_null (&perm_list),
1916 compare_elements_x_y, &aux_data));
1917 llx_destroy (&perm_list, NULL, NULL, &llx_malloc_mgr);
1920 check (perm_cnt == factorial (cnt));
1922 free_elements (cnt, &list, elems, NULL, values);
1923 free_elements (cnt, NULL, perm_elems, NULL, perm_values);
1927 /* Tests llx_partition. */
1929 test_partition (void)
1931 const int max_elems = 10;
1937 for (cnt = 0; cnt < max_elems; cnt++)
1938 for (r0 = 0; r0 <= cnt; r0++)
1939 for (r1 = r0; r1 <= cnt; r1++)
1940 for (pbase = 0; pbase <= (1u << (r1 - r0)); pbase++)
1942 struct llx_list list;
1943 struct element **elems;
1947 unsigned int pattern = pbase << r0;
1950 struct llx *part_llx;
1952 allocate_ascending (cnt, &list, &elems, &elemp, &values);
1954 /* Check that llx_find_partition works okay in every
1955 case. We use it after partitioning, too, but that
1956 only tests cases where it returns non-null. */
1957 for (i = r0; i < r1; i++)
1958 if (!(pattern & (1u << i)))
1962 if (pattern & (1u << i))
1964 part_llx = llx_find_partition (elemp[r0], elemp[r1],
1968 check (part_llx == elemp[j]);
1970 check (part_llx == NULL);
1972 /* Figure out expected results. */
1975 for (i = 0; i < r0; i++)
1977 for (i = r0; i < r1; i++)
1978 if (pattern & (1u << i))
1980 for (i = r0; i < r1; i++)
1981 if (!(pattern & (1u << i)))
1983 if (first_false == -1)
1987 if (first_false == -1)
1989 for (i = r1; i < cnt; i++)
1993 /* Partition and check for expected results. */
1994 check (llx_partition (elemp[r0], elemp[r1],
1995 pattern_pred, &pattern)
1996 == elemp[first_false]);
1997 check (llx_find_partition (elemp[r0], elemp[r1],
1998 pattern_pred, &pattern)
1999 == elemp[first_false]);
2000 check_list_contents (&list, values, cnt);
2001 check ((int) llx_count (&list) == cnt);
2003 free_elements (cnt, &list, elems, elemp, values);
2007 /* Tests that allocation failure is gracefully handled. */
2009 test_allocation_failure (void)
2011 struct llx_list list;
2014 check (llx_push_head (&list, NULL, &llx_null_mgr) == NULL);
2015 check (llx_push_tail (&list, NULL, &llx_null_mgr) == NULL);
2016 check (llx_insert (llx_null (&list), NULL, &llx_null_mgr) == NULL);
2017 check_list_contents (&list, NULL, 0);
2022 /* Runs TEST_FUNCTION and prints a message about NAME. */
2024 run_test (void (*test_function) (void), const char *name)
2035 run_test (test_push_pop, "push/pop");
2036 run_test (test_insert_remove, "insert/remove");
2037 run_test (test_swap, "swap");
2038 run_test (test_swap_range, "swap_range");
2039 run_test (test_remove_range, "remove_range");
2040 run_test (test_remove_equal, "remove_equal");
2041 run_test (test_remove_if, "remove_if");
2042 run_test (test_find_equal, "find_equal");
2043 run_test (test_find_if, "find_if");
2044 run_test (test_find_adjacent_equal, "find_adjacent_equal");
2045 run_test (test_count_range, "count_range");
2046 run_test (test_count_equal, "count_equal");
2047 run_test (test_count_if, "count_if");
2048 run_test (test_min_max, "min/max");
2049 run_test (test_lexicographical_compare_3way, "lexicographical_compare_3way");
2050 run_test (test_apply, "apply");
2051 run_test (test_destroy, "destroy");
2052 run_test (test_reverse, "reverse");
2053 run_test (test_permutations_no_dups, "permutations (no dups)");
2054 run_test (test_permutations_with_dups, "permutations (with dups)");
2055 run_test (test_merge_no_dups, "merge (no dups)");
2056 run_test (test_merge_with_dups, "merge (with dups)");
2057 run_test (test_sort_exhaustive, "sort (exhaustive)");
2058 run_test (test_sort_stable, "sort (stability)");
2059 run_test (test_sort_subset, "sort (subset)");
2060 run_test (test_sort_big, "sort (big)");
2061 run_test (test_unique, "unique");
2062 run_test (test_sort_unique, "sort_unique");
2063 run_test (test_insert_ordered, "insert_ordered");
2064 run_test (test_partition, "partition");
2065 run_test (test_allocation_failure, "allocation failure");
2073 compile-command: "gcc -Wall -Wstrict-prototypes -Wmissing-prototypes ll.c llx.c llx-test.c -o llx-test -g"