Added a dict parameter to data_in and dealt with the consequences.
[pspp-builds.git] / tests / libpspp / ll-test.c
1 /* PSPP - a program for statistical analysis.
2    Copyright (C) 2006 Free Software Foundation, Inc.
3
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.
8
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.
13
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/>. */
16
17 /* This is a test program for the ll_* 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 the ll_* routines.  "valgrind --leak-check=yes
21    --show-reachable=yes" should give a clean report.
22
23    This test program depends only on ll.c and the standard C
24    library.
25
26    See llx-test.c for a similar program for the llx_*
27    routines. */
28
29 #ifdef HAVE_CONFIG_H
30 #include <config.h>
31 #endif
32
33 #include <libpspp/ll.h>
34 #include <assert.h>
35 #include <stdio.h>
36 #include <stdlib.h>
37 #include <string.h>
38 \f
39 /* Support preliminaries. */
40 #if __GNUC__ >= 2 && !defined UNUSED
41 #define UNUSED __attribute__ ((unused))
42 #else
43 #define UNUSED
44 #endif
45
46 /* Currently running test. */
47 static const char *test_name;
48
49 /* Exit with a failure code.
50    (Place a breakpoint on this function while debugging.) */
51 static void
52 check_die (void)
53 {
54   exit (EXIT_FAILURE);
55 }
56
57 /* If OK is not true, prints a message about failure on the
58    current source file and the given LINE and terminates. */
59 static void
60 check_func (bool ok, int line)
61 {
62   if (!ok)
63     {
64       printf ("Check failed in %s test at %s, line %d\n",
65               test_name, __FILE__, line);
66       check_die ();
67     }
68 }
69
70 /* Verifies that EXPR evaluates to true.
71    If not, prints a message citing the calling line number and
72    terminates. */
73 #define check(EXPR) check_func ((EXPR), __LINE__)
74
75 /* Prints a message about memory exhaustion and exits with a
76    failure code. */
77 static void
78 xalloc_die (void)
79 {
80   printf ("virtual memory exhausted\n");
81   exit (EXIT_FAILURE);
82 }
83
84 /* Allocates and returns N bytes of memory. */
85 static void *
86 xmalloc (size_t n)
87 {
88   if (n != 0)
89     {
90       void *p = malloc (n);
91       if (p == NULL)
92         xalloc_die ();
93
94       return p;
95     }
96   else
97     return NULL;
98 }
99
100 /* Allocates and returns N * M bytes of memory. */
101 static void *
102 xnmalloc (size_t n, size_t m)
103 {
104   if ((size_t) -1 / m <= n)
105     xalloc_die ();
106   return xmalloc (n * m);
107 }
108 \f
109 /* List type and support routines. */
110
111 /* Test data element. */
112 struct element
113   {
114     struct ll ll;               /* Embedded list element. */
115     int x;                      /* Primary value. */
116     int y;                      /* Secondary value. */
117   };
118
119 static int aux_data;
120
121 /* Returns the `struct element' that LL is embedded within. */
122 static struct element *
123 ll_to_element (const struct ll *ll)
124 {
125   return ll_data (ll, struct element, ll);
126 }
127
128 /* Prints the elements in LIST. */
129 static void UNUSED
130 print_list (struct ll_list *list)
131 {
132   struct ll *x;
133
134   printf ("list:");
135   for (x = ll_head (list); x != ll_null (list); x = ll_next (x))
136     {
137       struct element *e = ll_to_element (x);
138       printf (" %d", e->x);
139     }
140   printf ("\n");
141 }
142
143 /* Prints the value returned by PREDICATE given auxiliary data
144    AUX for each element in LIST. */
145 static void UNUSED
146 print_pred (struct ll_list *list,
147             ll_predicate_func *predicate, void *aux UNUSED)
148 {
149   struct ll *x;
150
151   printf ("pred:");
152   for (x = ll_head (list); x != ll_null (list); x = ll_next (x))
153     printf (" %d", predicate (x, aux));
154   printf ("\n");
155 }
156
157 /* Prints the CNT numbers in VALUES. */
158 static void UNUSED
159 print_array (int values[], size_t cnt)
160 {
161   size_t i;
162
163   printf ("arry:");
164   for (i = 0; i < cnt; i++)
165     printf (" %d", values[i]);
166   printf ("\n");
167 }
168
169 /* Compares the `x' values in A and B and returns a strcmp-type
170    return value.  Verifies that AUX points to aux_data. */
171 static int
172 compare_elements (const struct ll *a_, const struct ll *b_, void *aux)
173 {
174   const struct element *a = ll_to_element (a_);
175   const struct element *b = ll_to_element (b_);
176
177   check (aux == &aux_data);
178   return a->x < b->x ? -1 : a->x > b->x;
179 }
180
181 /* Compares the `x' and `y' values in A and B and returns a
182    strcmp-type return value.  Verifies that AUX points to
183    aux_data. */
184 static int
185 compare_elements_x_y (const struct ll *a_, const struct ll *b_, void *aux)
186 {
187   const struct element *a = ll_to_element (a_);
188   const struct element *b = ll_to_element (b_);
189
190   check (aux == &aux_data);
191   if (a->x != b->x)
192     return a->x < b->x ? -1 : 1;
193   else if (a->y != b->y)
194     return a->y < b->y ? -1 : 1;
195   else
196     return 0;
197 }
198
199 /* Compares the `y' values in A and B and returns a strcmp-type
200    return value.  Verifies that AUX points to aux_data. */
201 static int
202 compare_elements_y (const struct ll *a_, const struct ll *b_, void *aux)
203 {
204   const struct element *a = ll_to_element (a_);
205   const struct element *b = ll_to_element (b_);
206
207   check (aux == &aux_data);
208   return a->y < b->y ? -1 : a->y > b->y;
209 }
210
211 /* Returns true if the bit in *PATTERN indicated by `x in
212    *ELEMENT is set, false otherwise. */
213 static bool
214 pattern_pred (const struct ll *element_, void *pattern_)
215 {
216   const struct element *element = ll_to_element (element_);
217   unsigned int *pattern = pattern_;
218
219   return (*pattern & (1u << element->x)) != 0;
220 }
221
222 /* Allocates N elements in *ELEMS.
223    Adds the elements to LIST, if it is nonnull.
224    Puts pointers to the elements' list elements in *ELEMP,
225    followed by a pointer to the list null element, if ELEMP is
226    nonnull.
227    Allocates space for N values in *VALUES, if VALUES is
228    nonnull. */
229 static void
230 allocate_elements (size_t n,
231                    struct ll_list *list,
232                    struct element ***elems,
233                    struct ll ***elemp,
234                    int **values)
235 {
236   size_t i;
237
238   if (list != NULL)
239     ll_init (list);
240
241   *elems = xnmalloc (n, sizeof **elems);
242   for (i = 0; i < n; i++)
243     {
244       (*elems)[i] = xmalloc (sizeof ***elems);
245       if (list != NULL)
246         ll_push_tail (list, &(*elems)[i]->ll);
247     }
248
249   if (elemp != NULL)
250     {
251       *elemp = xnmalloc (n + 1, sizeof *elemp);
252       for (i = 0; i < n; i++)
253         (*elemp)[i] = &(*elems)[i]->ll;
254       (*elemp)[n] = ll_null (list);
255     }
256
257   if (values != NULL)
258     *values = xnmalloc (n, sizeof *values);
259 }
260
261 /* Copies the CNT values of `x' from LIST into VALUES[]. */
262 static void
263 extract_values (struct ll_list *list, int values[], size_t cnt)
264 {
265   struct ll *x;
266
267   check (ll_count (list) == cnt);
268   for (x = ll_head (list); x != ll_null (list); x = ll_next (x))
269     {
270       struct element *e = ll_to_element (x);
271       *values++ = e->x;
272     }
273 }
274
275 /* As allocate_elements, but sets ascending values, starting
276    from 0, in `x' values in *ELEMS and in *VALUES (if
277    nonnull). */
278 static void
279 allocate_ascending (size_t n,
280                     struct ll_list *list,
281                     struct element ***elems,
282                     struct ll ***elemp,
283                     int **values)
284 {
285   size_t i;
286
287   allocate_elements (n, list, elems, elemp, values);
288
289   for (i = 0; i < n; i++)
290     (*elems)[i]->x = i;
291   if (values != NULL)
292     extract_values (list, *values, n);
293 }
294
295 /* As allocate_elements, but sets binary values extracted from
296    successive bits in PATTERN in `x' values in *ELEMS and in
297    *VALUES (if nonnull). */
298 static void
299 allocate_pattern (size_t n,
300                   int pattern,
301                   struct ll_list *list,
302                   struct element ***elems,
303                   struct ll ***elemp,
304                   int **values)
305 {
306   size_t i;
307
308   allocate_elements (n, list, elems, elemp, values);
309
310   for (i = 0; i < n; i++)
311     (*elems)[i]->x = (pattern & (1 << i)) != 0;
312   if (values != NULL)
313     extract_values (list, *values, n);
314 }
315
316 /* Randomly shuffles the CNT elements in ARRAY, each of which is
317    SIZE bytes in size. */
318 static void
319 random_shuffle (void *array_, size_t cnt, size_t size)
320 {
321   char *array = array_;
322   char *tmp = xmalloc (size);
323   size_t i;
324
325   for (i = 0; i < cnt; i++)
326     {
327       size_t j = rand () % (cnt - i) + i;
328       if (i != j)
329         {
330           memcpy (tmp, array + j * size, size);
331           memcpy (array + j * size, array + i * size, size);
332           memcpy (array + i * size, tmp, size);
333         }
334     }
335
336   free (tmp);
337 }
338
339 /* As allocate_ascending, but orders the values randomly. */
340 static void
341 allocate_random (size_t n,
342                  struct ll_list *list,
343                  struct element ***elems,
344                  struct ll ***elemp,
345                  int **values)
346 {
347   size_t i;
348
349   allocate_elements (n, list, elems, elemp, values);
350
351   for (i = 0; i < n; i++)
352     (*elems)[i]->x = i;
353   random_shuffle (*elems, n, sizeof **elems);
354   if (values != NULL)
355     extract_values (list, *values, n);
356 }
357
358 /* Frees the N elements of ELEMS, ELEMP, and VALUES. */
359 static void
360 free_elements (size_t n,
361                struct element **elems,
362                struct ll **elemp,
363                int *values)
364 {
365   size_t i;
366
367   for (i = 0; i < n; i++)
368     free (elems[i]);
369   free (elems);
370   free (elemp);
371   free (values);
372 }
373
374 /* Compares A and B and returns a strcmp-type return value. */
375 static int
376 compare_ints (const void *a_, const void *b_, void *aux UNUSED)
377 {
378   const int *a = a_;
379   const int *b = b_;
380
381   return *a < *b ? -1 : *a > *b;
382 }
383
384 /* Compares A and B and returns a strcmp-type return value. */
385 static int
386 compare_ints_noaux (const void *a_, const void *b_)
387 {
388   const int *a = a_;
389   const int *b = b_;
390
391   return *a < *b ? -1 : *a > *b;
392 }
393
394 /* Checks that LIST contains the CNT values in ELEMENTS. */
395 static void
396 check_list_contents (struct ll_list *list, int elements[], size_t cnt)
397 {
398   struct ll *ll;
399   size_t i;
400
401   check ((cnt == 0) == ll_is_empty (list));
402
403   /* Iterate in forward order. */
404   for (ll = ll_head (list), i = 0; i < cnt; ll = ll_next (ll), i++)
405     {
406       struct element *e = ll_to_element (ll);
407       check (elements[i] == e->x);
408       check (ll != ll_null (list));
409     }
410   check (ll == ll_null (list));
411
412   /* Iterate in reverse order. */
413   for (ll = ll_tail (list), i = 0; i < cnt; ll = ll_prev (ll), i++)
414     {
415       struct element *e = ll_to_element (ll);
416       check (elements[cnt - i - 1] == e->x);
417       check (ll != ll_null (list));
418     }
419   check (ll == ll_null (list));
420
421   check (ll_count (list) == cnt);
422 }
423
424 /* Lexicographically compares ARRAY1, which contains COUNT1
425    elements of SIZE bytes each, to ARRAY2, which contains COUNT2
426    elements of SIZE bytes, according to COMPARE.  Returns a
427    strcmp-type result.  AUX is passed to COMPARE as auxiliary
428    data. */
429 static int
430 lexicographical_compare_3way (const void *array1, size_t count1,
431                               const void *array2, size_t count2,
432                               size_t size,
433                               int (*compare) (const void *, const void *,
434                                               void *aux),
435                               void *aux)
436 {
437   const char *first1 = array1;
438   const char *first2 = array2;
439   size_t min_count = count1 < count2 ? count1 : count2;
440
441   while (min_count > 0)
442     {
443       int cmp = compare (first1, first2, aux);
444       if (cmp != 0)
445         return cmp;
446
447       first1 += size;
448       first2 += size;
449       min_count--;
450     }
451
452   return count1 < count2 ? -1 : count1 > count2;
453 }
454 \f
455 /* Tests. */
456
457 /* Tests list push and pop operations. */
458 static void
459 test_push_pop (void)
460 {
461   const int max_elems = 1024;
462
463   struct ll_list list;
464   struct element **elems;
465   int *values;
466
467   int i;
468
469   allocate_elements (max_elems, NULL, &elems, NULL, &values);
470
471   /* Push on tail. */
472   ll_init (&list);
473   check_list_contents (&list, NULL, 0);
474   for (i = 0; i < max_elems; i++)
475     {
476       values[i] = elems[i]->x = i;
477       ll_push_tail (&list, &elems[i]->ll);
478       check_list_contents (&list, values, i + 1);
479     }
480
481   /* Remove from tail. */
482   for (i = 0; i < max_elems; i++)
483     {
484       struct element *e = ll_to_element (ll_pop_tail (&list));
485       check (e->x == max_elems - i - 1);
486       check_list_contents (&list, values, max_elems - i - 1);
487     }
488
489   /* Push at start. */
490   check_list_contents (&list, NULL, 0);
491   for (i = 0; i < max_elems; i++)
492     {
493       values[max_elems - i - 1] = elems[i]->x = max_elems - i - 1;
494       ll_push_head (&list, &elems[i]->ll);
495       check_list_contents (&list, &values[max_elems - i - 1], i + 1);
496     }
497
498   /* Remove from start. */
499   for (i = 0; i < max_elems; i++)
500     {
501       struct element *e = ll_to_element (ll_pop_head (&list));
502       check (e->x == (int) i);
503       check_list_contents (&list, &values[i + 1], max_elems - i - 1);
504     }
505
506   free_elements (max_elems, elems, NULL, values);
507 }
508
509 /* Tests insertion and removal at arbitrary positions. */
510 static void
511 test_insert_remove (void)
512 {
513   const int max_elems = 16;
514   int cnt;
515
516   for (cnt = 0; cnt < max_elems; cnt++)
517     {
518       struct element **elems;
519       struct ll **elemp;
520       int *values = xnmalloc (cnt + 1, sizeof *values);
521
522       struct ll_list list;
523       struct element extra;
524       int pos;
525
526       allocate_ascending (cnt, &list, &elems, &elemp, NULL);
527       extra.x = -1;
528       for (pos = 0; pos <= cnt; pos++)
529         {
530           int i, j;
531
532           ll_insert (elemp[pos], &extra.ll);
533
534           j = 0;
535           for (i = 0; i < pos; i++)
536             values[j++] = i;
537           values[j++] = -1;
538           for (; i < cnt; i++)
539             values[j++] = i;
540           check_list_contents (&list, values, cnt + 1);
541
542           ll_remove (&extra.ll);
543         }
544       check_list_contents (&list, values, cnt);
545
546       free_elements (cnt, elems, elemp, values);
547     }
548 }
549
550 /* Tests swapping individual elements. */
551 static void
552 test_swap (void)
553 {
554   const int max_elems = 8;
555   int cnt;
556
557   for (cnt = 0; cnt <= max_elems; cnt++)
558     {
559       struct ll_list list;
560       struct element **elems;
561       int *values;
562
563       int i, j, k;
564
565       allocate_ascending (cnt, &list, &elems, NULL, &values);
566       check_list_contents (&list, values, cnt);
567
568       for (i = 0; i < cnt; i++)
569         for (j = 0; j < cnt; j++)
570           for (k = 0; k < 2; k++)
571             {
572               int t;
573
574               ll_swap (&elems[i]->ll, &elems[j]->ll);
575               t = values[i];
576               values[i] = values[j];
577               values[j] = t;
578               check_list_contents (&list, values, cnt);
579             }
580
581       free_elements (cnt, elems, NULL, values);
582     }
583 }
584
585 /* Tests swapping ranges of list elements. */
586 static void
587 test_swap_range (void)
588 {
589   const int max_elems = 8;
590   int cnt, a0, a1, b0, b1, r;
591
592   for (cnt = 0; cnt <= max_elems; cnt++)
593     for (a0 = 0; a0 <= cnt; a0++)
594       for (a1 = a0; a1 <= cnt; a1++)
595         for (b0 = a1; b0 <= cnt; b0++)
596           for (b1 = b0; b1 <= cnt; b1++)
597             for (r = 0; r < 2; r++)
598               {
599                 struct ll_list list;
600                 struct element **elems;
601                 struct ll **elemp;
602                 int *values;
603
604                 int i, j;
605
606                 allocate_ascending (cnt, &list, &elems, &elemp, &values);
607                 check_list_contents (&list, values, cnt);
608
609                 j = 0;
610                 for (i = 0; i < a0; i++)
611                   values[j++] = i;
612                 for (i = b0; i < b1; i++)
613                   values[j++] = i;
614                 for (i = a1; i < b0; i++)
615                   values[j++] = i;
616                 for (i = a0; i < a1; i++)
617                   values[j++] = i;
618                 for (i = b1; i < cnt; i++)
619                   values[j++] = i;
620                 check (j == cnt);
621
622                 if (r == 0)
623                   ll_swap_range (elemp[a0], elemp[a1], elemp[b0], elemp[b1]);
624                 else
625                   ll_swap_range (elemp[b0], elemp[b1], elemp[a0], elemp[a1]);
626                 check_list_contents (&list, values, cnt);
627
628                 free_elements (cnt, elems, elemp, values);
629               }
630 }
631
632 /* Tests removing ranges of list elements. */
633 static void
634 test_remove_range (void)
635 {
636   const int max_elems = 8;
637
638   int cnt, r0, r1;
639
640   for (cnt = 0; cnt <= max_elems; cnt++)
641     for (r0 = 0; r0 <= cnt; r0++)
642       for (r1 = r0; r1 <= cnt; r1++)
643         {
644           struct ll_list list;
645           struct element **elems;
646           struct ll **elemp;
647           int *values;
648
649           int i, j;
650
651           allocate_ascending (cnt, &list, &elems, &elemp, &values);
652           check_list_contents (&list, values, cnt);
653
654           j = 0;
655           for (i = 0; i < r0; i++)
656             values[j++] = i;
657           for (i = r1; i < cnt; i++)
658             values[j++] = i;
659
660           ll_remove_range (elemp[r0], elemp[r1]);
661           check_list_contents (&list, values, j);
662
663           free_elements (cnt, elems, elemp, values);
664         }
665 }
666
667 /* Tests ll_remove_equal. */
668 static void
669 test_remove_equal (void)
670 {
671   const int max_elems = 8;
672
673   int cnt, r0, r1, eq_pat;
674
675   for (cnt = 0; cnt <= max_elems; cnt++)
676     for (r0 = 0; r0 <= cnt; r0++)
677       for (r1 = r0; r1 <= cnt; r1++)
678         for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
679           {
680             struct ll_list list;
681             struct element **elems;
682             struct ll **elemp;
683             int *values;
684
685             struct element to_remove;
686             int remaining;
687             int i;
688
689             allocate_elements (cnt, &list, &elems, &elemp, &values);
690
691             remaining = 0;
692             for (i = 0; i < cnt; i++)
693               {
694                 int x = eq_pat & (1 << i) ? -1 : i;
695                 bool delete = x == -1 && r0 <= i && i < r1;
696                 elems[i]->x = x;
697                 if (!delete)
698                   values[remaining++] = x;
699               }
700
701             to_remove.x = -1;
702             check ((int) ll_remove_equal (elemp[r0], elemp[r1], &to_remove.ll,
703                                           compare_elements, &aux_data)
704                    == cnt - remaining);
705             check_list_contents (&list, values, remaining);
706
707             free_elements (cnt, elems, elemp, values);
708           }
709 }
710
711 /* Tests ll_remove_if. */
712 static void
713 test_remove_if (void)
714 {
715   const int max_elems = 8;
716
717   int cnt, r0, r1, pattern;
718
719   for (cnt = 0; cnt <= max_elems; cnt++)
720     for (r0 = 0; r0 <= cnt; r0++)
721       for (r1 = r0; r1 <= cnt; r1++)
722         for (pattern = 0; pattern <= 1 << cnt; pattern++)
723           {
724             struct ll_list list;
725             struct element **elems;
726             struct ll **elemp;
727             int *values;
728
729             int remaining;
730             int i;
731
732             allocate_elements (cnt, &list, &elems, &elemp, &values);
733
734             remaining = 0;
735             for (i = 0; i < cnt; i++)
736               {
737                 bool delete = (pattern & (1 << i)) && r0 <= i && i < r1;
738                 elems[i]->x = i;
739                 if (!delete)
740                   values[remaining++] = i;
741               }
742
743             check ((int) ll_remove_if (elemp[r0], elemp[r1],
744                                        pattern_pred, &pattern)
745                    == cnt - remaining);
746             check_list_contents (&list, values, remaining);
747
748             free_elements (cnt, elems, elemp, values);
749           }
750 }
751
752 /* Tests ll_moved. */
753 static void
754 test_moved (void)
755 {
756   const int max_elems = 8;
757
758   int cnt;
759
760   for (cnt = 0; cnt <= max_elems; cnt++)
761     {
762       struct ll_list list;
763       struct element **elems;
764       struct element **new_elems;
765       int *values;
766
767       int i;
768
769       allocate_ascending (cnt, &list, &elems, NULL, &values);
770       allocate_elements (cnt, NULL, &new_elems, NULL, NULL);
771       check_list_contents (&list, values, cnt);
772
773       for (i = 0; i < cnt; i++)
774         {
775           *new_elems[i] = *elems[i];
776           ll_moved (&new_elems[i]->ll);
777           check_list_contents (&list, values, cnt);
778         }
779
780       free_elements (cnt, elems, NULL, values);
781       free_elements (cnt, new_elems, NULL, NULL);
782     }
783 }
784
785 /* Tests, via HELPER, a function that looks at list elements
786    equal to some specified element. */
787 static void
788 test_examine_equal_range (void (*helper) (int r0, int r1, int eq_pat,
789                                           struct ll *to_find,
790                                           struct ll **elemp))
791 {
792   const int max_elems = 8;
793
794   int cnt, r0, r1, eq_pat;
795
796   for (cnt = 0; cnt <= max_elems; cnt++)
797     for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
798       {
799         struct ll_list list;
800         struct element **elems;
801         struct ll **elemp;
802         int *values;
803
804         struct element to_find;
805
806         int i;
807
808         allocate_ascending (cnt, &list, &elems, &elemp, &values);
809
810         for (i = 0; i < cnt; i++)
811           if (eq_pat & (1 << i))
812             values[i] = elems[i]->x = -1;
813
814         to_find.x = -1;
815         for (r0 = 0; r0 <= cnt; r0++)
816           for (r1 = r0; r1 <= cnt; r1++)
817             helper (r0, r1, eq_pat, &to_find.ll, elemp);
818
819         check_list_contents (&list, values, cnt);
820
821         free_elements (cnt, elems, elemp, values);
822       }
823 }
824
825 /* Tests, via HELPER, a function that looks at list elements for
826    which a given predicate returns true. */
827 static void
828 test_examine_if_range (void (*helper) (int r0, int r1, int eq_pat,
829                                        struct ll **elemp))
830 {
831   const int max_elems = 8;
832
833   int cnt, r0, r1, eq_pat;
834
835   for (cnt = 0; cnt <= max_elems; cnt++)
836     for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
837       {
838         struct ll_list list;
839         struct element **elems;
840         struct ll **elemp;
841         int *values;
842
843         allocate_ascending (cnt, &list, &elems, &elemp, &values);
844
845         for (r0 = 0; r0 <= cnt; r0++)
846           for (r1 = r0; r1 <= cnt; r1++)
847             helper (r0, r1, eq_pat, elemp);
848
849         check_list_contents (&list, values, cnt);
850
851         free_elements (cnt, elems, elemp, values);
852       }
853 }
854
855 /* Helper function for testing ll_find_equal. */
856 static void
857 test_find_equal_helper (int r0, int r1, int eq_pat,
858                         struct ll *to_find, struct ll **elemp)
859 {
860   struct ll *match;
861   int i;
862
863   match = ll_find_equal (elemp[r0], elemp[r1], to_find,
864                          compare_elements, &aux_data);
865   for (i = r0; i < r1; i++)
866     if (eq_pat & (1 << i))
867       break;
868
869   check (match == elemp[i]);
870 }
871
872 /* Tests ll_find_equal. */
873 static void
874 test_find_equal (void)
875 {
876   test_examine_equal_range (test_find_equal_helper);
877 }
878
879 /* Helper function for testing ll_find_if. */
880 static void
881 test_find_if_helper (int r0, int r1, int eq_pat, struct ll **elemp)
882 {
883   struct ll *match = ll_find_if (elemp[r0], elemp[r1],
884                                  pattern_pred, &eq_pat);
885   int i;
886
887   for (i = r0; i < r1; i++)
888     if (eq_pat & (1 << i))
889       break;
890
891   check (match == elemp[i]);
892 }
893
894 /* Tests ll_find_if. */
895 static void
896 test_find_if (void)
897 {
898   test_examine_if_range (test_find_if_helper);
899 }
900
901 /* Tests ll_find_adjacent_equal. */
902 static void
903 test_find_adjacent_equal (void)
904 {
905   const int max_elems = 8;
906
907   int cnt, eq_pat;
908
909   for (cnt = 0; cnt <= max_elems; cnt++)
910     for (eq_pat = 0; eq_pat <= 1 << cnt; eq_pat++)
911       {
912         struct ll_list list;
913         struct element **elems;
914         struct ll **elemp;
915         int *values;
916         int match;
917
918         int i;
919
920         allocate_ascending (cnt, &list, &elems, &elemp, &values);
921
922         match = -1;
923         for (i = 0; i < cnt - 1; i++)
924           {
925             elems[i]->y = i;
926             if (eq_pat & (1 << i))
927               {
928                 values[i] = elems[i]->x = match;
929                 values[i + 1] = elems[i + 1]->x = match;
930               }
931             else
932               match--;
933           }
934
935         for (i = 0; i <= cnt; i++)
936           {
937             struct ll *ll1 = ll_find_adjacent_equal (elemp[i], ll_null (&list),
938                                                      compare_elements,
939                                                      &aux_data);
940             struct ll *ll2;
941             int j;
942
943             ll2 = ll_null (&list);
944             for (j = i; j < cnt - 1; j++)
945               if (eq_pat & (1 << j))
946                 {
947                   ll2 = elemp[j];
948                   break;
949                 }
950             check (ll1 == ll2);
951           }
952         check_list_contents (&list, values, cnt);
953
954         free_elements (cnt, elems, elemp, values);
955       }
956 }
957
958 /* Helper function for testing ll_count_range. */
959 static void
960 test_count_range_helper (int r0, int r1, int eq_pat UNUSED, struct ll **elemp)
961 {
962   check ((int) ll_count_range (elemp[r0], elemp[r1]) == r1 - r0);
963 }
964
965 /* Tests ll_count_range. */
966 static void
967 test_count_range (void)
968 {
969   test_examine_if_range (test_count_range_helper);
970 }
971
972 /* Helper function for testing ll_count_equal. */
973 static void
974 test_count_equal_helper (int r0, int r1, int eq_pat,
975                          struct ll *to_find, struct ll **elemp)
976 {
977   int count1, count2;
978   int i;
979
980   count1 = ll_count_equal (elemp[r0], elemp[r1], to_find,
981                            compare_elements, &aux_data);
982   count2 = 0;
983   for (i = r0; i < r1; i++)
984     if (eq_pat & (1 << i))
985       count2++;
986
987   check (count1 == count2);
988 }
989
990 /* Tests ll_count_equal. */
991 static void
992 test_count_equal (void)
993 {
994   test_examine_equal_range (test_count_equal_helper);
995 }
996
997 /* Helper function for testing ll_count_if. */
998 static void
999 test_count_if_helper (int r0, int r1, int eq_pat, struct ll **elemp)
1000 {
1001   int count1;
1002   int count2;
1003   int i;
1004
1005   count1 = ll_count_if (elemp[r0], elemp[r1], pattern_pred, &eq_pat);
1006
1007   count2 = 0;
1008   for (i = r0; i < r1; i++)
1009     if (eq_pat & (1 << i))
1010       count2++;
1011
1012   check (count1 == count2);
1013 }
1014
1015 /* Tests ll_count_if. */
1016 static void
1017 test_count_if (void)
1018 {
1019   test_examine_if_range (test_count_if_helper);
1020 }
1021
1022 /* Returns N!. */
1023 static unsigned int
1024 factorial (unsigned int n)
1025 {
1026   unsigned int value = 1;
1027   while (n > 1)
1028     value *= n--;
1029   return value;
1030 }
1031
1032 /* Returns the number of permutations of the CNT values in
1033    VALUES.  If VALUES contains duplicates, they must be
1034    adjacent. */
1035 static unsigned int
1036 expected_perms (int *values, size_t cnt)
1037 {
1038   size_t i, j;
1039   unsigned int perm_cnt;
1040
1041   perm_cnt = factorial (cnt);
1042   for (i = 0; i < cnt; i = j)
1043     {
1044       for (j = i + 1; j < cnt; j++)
1045         if (values[i] != values[j])
1046           break;
1047       perm_cnt /= factorial (j - i);
1048     }
1049   return perm_cnt;
1050 }
1051
1052 /* Tests ll_min and ll_max. */
1053 static void
1054 test_min_max (void)
1055 {
1056   const int max_elems = 6;
1057   int cnt;
1058
1059   for (cnt = 0; cnt <= max_elems; cnt++)
1060     {
1061       struct ll_list list;
1062       struct element **elems;
1063       struct ll **elemp;
1064       int *values;
1065       int *new_values = xnmalloc (cnt, sizeof *values);
1066
1067       size_t perm_cnt;
1068
1069       allocate_ascending (cnt, &list, &elems, &elemp, &values);
1070
1071       perm_cnt = 1;
1072       while (ll_next_permutation (ll_head (&list), ll_null (&list),
1073                                   compare_elements, &aux_data))
1074         {
1075           int r0, r1;
1076           struct ll *x;
1077           int i;
1078
1079           for (i = 0, x = ll_head (&list); x != ll_null (&list);
1080                x = ll_next (x), i++)
1081             {
1082               struct element *e = ll_to_element (x);
1083               elemp[i] = x;
1084               new_values[i] = e->x;
1085             }
1086           for (r0 = 0; r0 <= cnt; r0++)
1087             for (r1 = r0; r1 <= cnt; r1++)
1088               {
1089                 struct ll *min = ll_min (elemp[r0], elemp[r1],
1090                                          compare_elements, &aux_data);
1091                 struct ll *max = ll_max (elemp[r0], elemp[r1],
1092                                          compare_elements, &aux_data);
1093                 if (r0 == r1)
1094                   {
1095                     check (min == elemp[r1]);
1096                     check (max == elemp[r1]);
1097                   }
1098                 else
1099                   {
1100                     int min_int, max_int;
1101                     int i;
1102
1103                     min_int = max_int = new_values[r0];
1104                     for (i = r0; i < r1; i++)
1105                       {
1106                         int value = new_values[i];
1107                         if (value < min_int)
1108                           min_int = value;
1109                         if (value > max_int)
1110                           max_int = value;
1111                       }
1112                     check (min != elemp[r1]
1113                            && ll_to_element (min)->x == min_int);
1114                     check (max != elemp[r1]
1115                            && ll_to_element (max)->x == max_int);
1116                   }
1117               }
1118           perm_cnt++;
1119         }
1120       check (perm_cnt == factorial (cnt));
1121       check_list_contents (&list, values, cnt);
1122
1123       free_elements (cnt, elems, elemp, values);
1124       free (new_values);
1125     }
1126 }
1127
1128 /* Tests ll_lexicographical_compare_3way. */
1129 static void
1130 test_lexicographical_compare_3way (void)
1131 {
1132   const int max_elems = 4;
1133
1134   int cnt_a, pat_a, cnt_b, pat_b;
1135
1136   for (cnt_a = 0; cnt_a <= max_elems; cnt_a++)
1137     for (pat_a = 0; pat_a <= 1 << cnt_a; pat_a++)
1138       for (cnt_b = 0; cnt_b <= max_elems; cnt_b++)
1139         for (pat_b = 0; pat_b <= 1 << cnt_b; pat_b++)
1140           {
1141             struct ll_list list_a, list_b;
1142             struct element **elems_a, **elems_b;
1143             struct ll **elemp_a, **elemp_b;
1144             int *values_a, *values_b;
1145
1146             int a0, a1, b0, b1;
1147
1148             allocate_pattern (cnt_a, pat_a,
1149                               &list_a, &elems_a, &elemp_a, &values_a);
1150             allocate_pattern (cnt_b, pat_b,
1151                               &list_b, &elems_b, &elemp_b, &values_b);
1152
1153             for (a0 = 0; a0 <= cnt_a; a0++)
1154               for (a1 = a0; a1 <= cnt_a; a1++)
1155                 for (b0 = 0; b0 <= cnt_b; b0++)
1156                   for (b1 = b0; b1 <= cnt_b; b1++)
1157                     {
1158                       int a_ordering = lexicographical_compare_3way (
1159                         values_a + a0, a1 - a0,
1160                         values_b + b0, b1 - b0,
1161                         sizeof *values_a,
1162                         compare_ints, NULL);
1163
1164                       int b_ordering = ll_lexicographical_compare_3way (
1165                         elemp_a[a0], elemp_a[a1],
1166                         elemp_b[b0], elemp_b[b1],
1167                         compare_elements, &aux_data);
1168
1169                       check (a_ordering == b_ordering);
1170                     }
1171
1172             free_elements (cnt_a, elems_a, elemp_a, values_a);
1173             free_elements (cnt_b, elems_b, elemp_b, values_b);
1174           }
1175 }
1176
1177 /* Appends the `x' value in element E to the array pointed to by
1178    NEXT_OUTPUT, and advances NEXT_OUTPUT to the next position. */
1179 static void
1180 apply_func (struct ll *e_, void *next_output_)
1181 {
1182   struct element *e = ll_to_element (e_);
1183   int **next_output = next_output_;
1184
1185   *(*next_output)++ = e->x;
1186 }
1187
1188 /* Tests ll_apply. */
1189 static void
1190 test_apply (void)
1191 {
1192   const int max_elems = 8;
1193
1194   int cnt, r0, r1;
1195
1196   for (cnt = 0; cnt <= max_elems; cnt++)
1197     for (r0 = 0; r0 <= cnt; r0++)
1198       for (r1 = r0; r1 <= cnt; r1++)
1199         {
1200           struct ll_list list;
1201           struct element **elems;
1202           struct ll **elemp;
1203           int *values;
1204
1205           int *output;
1206           int *next_output;
1207
1208           int i;
1209
1210           allocate_ascending (cnt, &list, &elems, &elemp, &values);
1211           check_list_contents (&list, values, cnt);
1212
1213           output = next_output = xnmalloc (cnt, sizeof *output);
1214           ll_apply (elemp[r0], elemp[r1], apply_func, &next_output);
1215           check_list_contents (&list, values, cnt);
1216
1217           check (r1 - r0 == next_output - output);
1218           for (i = 0; i < r1 - r0; i++)
1219             check (output[i] == r0 + i);
1220
1221           free_elements (cnt, elems, elemp, values);
1222           free (output);
1223         }
1224 }
1225
1226 /* Tests ll_reverse. */
1227 static void
1228 test_reverse (void)
1229 {
1230   const int max_elems = 8;
1231
1232   int cnt, r0, r1;
1233
1234   for (cnt = 0; cnt <= max_elems; cnt++)
1235     for (r0 = 0; r0 <= cnt; r0++)
1236       for (r1 = r0; r1 <= cnt; r1++)
1237         {
1238           struct ll_list list;
1239           struct element **elems;
1240           struct ll **elemp;
1241           int *values;
1242
1243           int i, j;
1244
1245           allocate_ascending (cnt, &list, &elems, &elemp, &values);
1246           check_list_contents (&list, values, cnt);
1247
1248           j = 0;
1249           for (i = 0; i < r0; i++)
1250             values[j++] = i;
1251           for (i = r1 - 1; i >= r0; i--)
1252             values[j++] = i;
1253           for (i = r1; i < cnt; i++)
1254             values[j++] = i;
1255
1256           ll_reverse (elemp[r0], elemp[r1]);
1257           check_list_contents (&list, values, cnt);
1258
1259           free_elements (cnt, elems, elemp, values);
1260         }
1261 }
1262
1263 /* Tests ll_next_permutation and ll_prev_permutation when the
1264    permuted values have no duplicates. */
1265 static void
1266 test_permutations_no_dups (void)
1267 {
1268   const int max_elems = 8;
1269   int cnt;
1270
1271   for (cnt = 0; cnt <= max_elems; cnt++)
1272     {
1273       struct ll_list list;
1274       struct element **elems;
1275       int *values;
1276       int *old_values = xnmalloc (cnt, sizeof *values);
1277       int *new_values = xnmalloc (cnt, sizeof *values);
1278
1279       size_t perm_cnt;
1280
1281       allocate_ascending (cnt, &list, &elems, NULL, &values);
1282
1283       perm_cnt = 1;
1284       extract_values (&list, old_values, cnt);
1285       while (ll_next_permutation (ll_head (&list), ll_null (&list),
1286                                   compare_elements, &aux_data))
1287         {
1288           extract_values (&list, new_values, cnt);
1289           check (lexicographical_compare_3way (new_values, cnt,
1290                                                old_values, cnt,
1291                                                sizeof *new_values,
1292                                                compare_ints, NULL) > 0);
1293           memcpy (old_values, new_values, (cnt) * sizeof *old_values);
1294           perm_cnt++;
1295         }
1296       check (perm_cnt == factorial (cnt));
1297       check_list_contents (&list, values, cnt);
1298
1299       perm_cnt = 1;
1300       ll_reverse (ll_head (&list), ll_null (&list));
1301       extract_values (&list, old_values, cnt);
1302       while (ll_prev_permutation (ll_head (&list), ll_null (&list),
1303                                   compare_elements, &aux_data))
1304         {
1305           extract_values (&list, new_values, cnt);
1306           check (lexicographical_compare_3way (new_values, cnt,
1307                                                old_values, cnt,
1308                                                sizeof *new_values,
1309                                                compare_ints, NULL) < 0);
1310           memcpy (old_values, new_values, (cnt) * sizeof *old_values);
1311           perm_cnt++;
1312         }
1313       check (perm_cnt == factorial (cnt));
1314       ll_reverse (ll_head (&list), ll_null (&list));
1315       check_list_contents (&list, values, cnt);
1316
1317       free_elements (cnt, elems, NULL, values);
1318       free (old_values);
1319       free (new_values);
1320     }
1321 }
1322
1323 /* Tests ll_next_permutation and ll_prev_permutation when the
1324    permuted values contain duplicates. */
1325 static void
1326 test_permutations_with_dups (void)
1327 {
1328   const int max_elems = 8;
1329   const int max_dup = 3;
1330   const int repetitions = 1024;
1331
1332   int cnt, repeat;
1333
1334   for (repeat = 0; repeat < repetitions; repeat++)
1335     for (cnt = 0; cnt < max_elems; cnt++)
1336       {
1337         struct ll_list list;
1338         struct element **elems;
1339         int *values;
1340         int *old_values = xnmalloc (max_elems, sizeof *values);
1341         int *new_values = xnmalloc (max_elems, sizeof *values);
1342
1343         unsigned int permutation_cnt;
1344         int left = cnt;
1345         int value = 0;
1346
1347         allocate_elements (cnt, &list, &elems, NULL, &values);
1348
1349         value = 0;
1350         while (left > 0)
1351           {
1352             int max = left < max_dup ? left : max_dup;
1353             int n = rand () % max + 1;
1354             while (n-- > 0)
1355               {
1356                 int idx = cnt - left--;
1357                 values[idx] = elems[idx]->x = value;
1358               }
1359             value++;
1360           }
1361
1362         permutation_cnt = 1;
1363         extract_values (&list, old_values, cnt);
1364         while (ll_next_permutation (ll_head (&list), ll_null (&list),
1365                                     compare_elements, &aux_data))
1366           {
1367             extract_values (&list, new_values, cnt);
1368             check (lexicographical_compare_3way (new_values, cnt,
1369                                                  old_values, cnt,
1370                                                  sizeof *new_values,
1371                                                  compare_ints, NULL) > 0);
1372             memcpy (old_values, new_values, cnt * sizeof *old_values);
1373             permutation_cnt++;
1374           }
1375         check (permutation_cnt == expected_perms (values, cnt));
1376         check_list_contents (&list, values, cnt);
1377
1378         permutation_cnt = 1;
1379         ll_reverse (ll_head (&list), ll_null (&list));
1380         extract_values (&list, old_values, cnt);
1381         while (ll_prev_permutation (ll_head (&list), ll_null (&list),
1382                                     compare_elements, &aux_data))
1383           {
1384             extract_values (&list, new_values, cnt);
1385             check (lexicographical_compare_3way (new_values, cnt,
1386                                                  old_values, cnt,
1387                                                  sizeof *new_values,
1388                                                  compare_ints, NULL) < 0);
1389             permutation_cnt++;
1390           }
1391         ll_reverse (ll_head (&list), ll_null (&list));
1392         check (permutation_cnt == expected_perms (values, cnt));
1393         check_list_contents (&list, values, cnt);
1394
1395         free_elements (cnt, elems, NULL, values);
1396         free (old_values);
1397         free (new_values);
1398       }
1399 }
1400
1401 /* Tests ll_merge when no equal values are to be merged. */
1402 static void
1403 test_merge_no_dups (void)
1404 {
1405   const int max_elems = 8;
1406   const int max_filler = 3;
1407
1408   int merge_cnt, pattern, pfx, gap, sfx, order;
1409
1410   for (merge_cnt = 0; merge_cnt < max_elems; merge_cnt++)
1411     for (pattern = 0; pattern <= (1 << merge_cnt); pattern++)
1412       for (pfx = 0; pfx < max_filler; pfx++)
1413         for (gap = 0; gap < max_filler; gap++)
1414           for (sfx = 0; sfx < max_filler; sfx++)
1415             for (order = 0; order < 2; order++)
1416               {
1417                 struct ll_list list;
1418                 struct element **elems;
1419                 struct ll **elemp;
1420                 int *values;
1421
1422                 int list_cnt = pfx + merge_cnt + gap + sfx;
1423                 int a0, a1, b0, b1;
1424                 int i, j;
1425
1426                 allocate_elements (list_cnt, &list,
1427                                    &elems, &elemp, &values);
1428
1429                 j = 0;
1430                 for (i = 0; i < pfx; i++)
1431                   elems[j++]->x = 100 + i;
1432                 a0 = j;
1433                 for (i = 0; i < merge_cnt; i++)
1434                   if (pattern & (1u << i))
1435                     elems[j++]->x = i;
1436                 a1 = j;
1437                 for (i = 0; i < gap; i++)
1438                   elems[j++]->x = 200 + i;
1439                 b0 = j;
1440                 for (i = 0; i < merge_cnt; i++)
1441                   if (!(pattern & (1u << i)))
1442                     elems[j++]->x = i;
1443                 b1 = j;
1444                 for (i = 0; i < sfx; i++)
1445                   elems[j++]->x = 300 + i;
1446                 check (list_cnt == j);
1447
1448                 j = 0;
1449                 for (i = 0; i < pfx; i++)
1450                   values[j++] = 100 + i;
1451                 if (order == 0)
1452                   for (i = 0; i < merge_cnt; i++)
1453                     values[j++] = i;
1454                 for (i = 0; i < gap; i++)
1455                   values[j++] = 200 + i;
1456                 if (order == 1)
1457                   for (i = 0; i < merge_cnt; i++)
1458                     values[j++] = i;
1459                 for (i = 0; i < sfx; i++)
1460                   values[j++] = 300 + i;
1461                 check (list_cnt == j);
1462
1463                 if (order == 0)
1464                   ll_merge (elemp[a0], elemp[a1], elemp[b0], elemp[b1],
1465                             compare_elements, &aux_data);
1466                 else
1467                   ll_merge (elemp[b0], elemp[b1], elemp[a0], elemp[a1],
1468                             compare_elements, &aux_data);
1469
1470                 check_list_contents (&list, values, list_cnt);
1471
1472                 free_elements (list_cnt, elems, elemp, values);
1473               }
1474 }
1475
1476 /* Tests ll_merge when equal values are to be merged. */
1477 static void
1478 test_merge_with_dups (void)
1479 {
1480   const int max_elems = 8;
1481
1482   int cnt, merge_pat, inc_pat, order;
1483
1484   for (cnt = 0; cnt <= max_elems; cnt++)
1485     for (merge_pat = 0; merge_pat <= (1 << cnt); merge_pat++)
1486       for (inc_pat = 0; inc_pat <= (1 << cnt); inc_pat++)
1487         for (order = 0; order < 2; order++)
1488           {
1489             struct ll_list list;
1490             struct element **elems;
1491             struct ll **elemp;
1492             int *values;
1493
1494             int mid;
1495             int i, j, k;
1496
1497             allocate_elements (cnt, &list, &elems, &elemp, &values);
1498
1499             j = 0;
1500             for (i = k = 0; i < cnt; i++)
1501               {
1502                 if (merge_pat & (1u << i))
1503                   elems[j++]->x = k;
1504                 if (inc_pat & (1u << i))
1505                   k++;
1506               }
1507             mid = j;
1508             for (i = k = 0; i < cnt; i++)
1509               {
1510                 if (!(merge_pat & (1u << i)))
1511                   elems[j++]->x = k;
1512                 if (inc_pat & (1u << i))
1513                   k++;
1514               }
1515             check (cnt == j);
1516
1517             if (order == 0)
1518               {
1519                 for (i = 0; i < cnt; i++)
1520                   elems[i]->y = i;
1521               }
1522             else
1523               {
1524                 for (i = 0; i < mid; i++)
1525                   elems[i]->y = 100 + i;
1526                 for (i = mid; i < cnt; i++)
1527                   elems[i]->y = i;
1528               }
1529
1530             j = 0;
1531             for (i = k = 0; i < cnt; i++)
1532               {
1533                 values[j++] = k;
1534                 if (inc_pat & (1u << i))
1535                   k++;
1536               }
1537             check (cnt == j);
1538
1539             if (order == 0)
1540               ll_merge (elemp[0], elemp[mid], elemp[mid], elemp[cnt],
1541                         compare_elements, &aux_data);
1542             else
1543               ll_merge (elemp[mid], elemp[cnt], elemp[0], elemp[mid],
1544                         compare_elements, &aux_data);
1545
1546             check_list_contents (&list, values, cnt);
1547             check (ll_is_sorted (ll_head (&list), ll_null (&list),
1548                                  compare_elements_x_y, &aux_data));
1549
1550             free_elements (cnt, elems, elemp, values);
1551           }
1552 }
1553
1554 /* Tests ll_sort on all permutations up to a maximum number of
1555    elements. */
1556 static void
1557 test_sort_exhaustive (void)
1558 {
1559   const int max_elems = 8;
1560   int cnt;
1561
1562   for (cnt = 0; cnt <= max_elems; cnt++)
1563     {
1564       struct ll_list list;
1565       struct element **elems;
1566       int *values;
1567
1568       struct element **perm_elems;
1569       int *perm_values;
1570
1571       size_t perm_cnt;
1572
1573       allocate_ascending (cnt, &list, &elems, NULL, &values);
1574       allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1575
1576       perm_cnt = 1;
1577       while (ll_next_permutation (ll_head (&list), ll_null (&list),
1578                                   compare_elements, &aux_data))
1579         {
1580           struct ll_list perm_list;
1581           int j;
1582
1583           extract_values (&list, perm_values, cnt);
1584           ll_init (&perm_list);
1585           for (j = 0; j < cnt; j++)
1586             {
1587               perm_elems[j]->x = perm_values[j];
1588               ll_push_tail (&perm_list, &perm_elems[j]->ll);
1589             }
1590           ll_sort (ll_head (&perm_list), ll_null (&perm_list),
1591                    compare_elements, &aux_data);
1592           check_list_contents (&perm_list, values, cnt);
1593           check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1594                                compare_elements, &aux_data));
1595           perm_cnt++;
1596         }
1597       check (perm_cnt == factorial (cnt));
1598
1599       free_elements (cnt, elems, NULL, values);
1600       free_elements (cnt, perm_elems, NULL, perm_values);
1601     }
1602 }
1603
1604 /* Tests that ll_sort is stable in the presence of equal
1605    values. */
1606 static void
1607 test_sort_stable (void)
1608 {
1609   const int max_elems = 6;
1610   int cnt, inc_pat;
1611
1612   for (cnt = 0; cnt <= max_elems; cnt++)
1613     for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1614       {
1615         struct ll_list list;
1616         struct element **elems;
1617         int *values;
1618
1619         struct element **perm_elems;
1620         int *perm_values;
1621
1622         size_t perm_cnt;
1623         int i, j;
1624
1625         allocate_elements (cnt, &list, &elems, NULL, &values);
1626         allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1627
1628         j = 0;
1629         for (i = 0; i < cnt; i++)
1630           {
1631             elems[i]->x = values[i] = j;
1632             if (inc_pat & (1 << i))
1633               j++;
1634             elems[i]->y = i;
1635           }
1636
1637         perm_cnt = 1;
1638         while (ll_next_permutation (ll_head (&list), ll_null (&list),
1639                                     compare_elements_y, &aux_data))
1640           {
1641             struct ll_list perm_list;
1642
1643             extract_values (&list, perm_values, cnt);
1644             ll_init (&perm_list);
1645             for (i = 0; i < cnt; i++)
1646               {
1647                 perm_elems[i]->x = perm_values[i];
1648                 perm_elems[i]->y = i;
1649                 ll_push_tail (&perm_list, &perm_elems[i]->ll);
1650               }
1651             ll_sort (ll_head (&perm_list), ll_null (&perm_list),
1652                      compare_elements, &aux_data);
1653             check_list_contents (&perm_list, values, cnt);
1654             check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1655                                  compare_elements_x_y, &aux_data));
1656             perm_cnt++;
1657           }
1658         check (perm_cnt == factorial (cnt));
1659
1660         free_elements (cnt, elems, NULL, values);
1661         free_elements (cnt, perm_elems, NULL, perm_values);
1662       }
1663 }
1664
1665 /* Tests that ll_sort does not disturb elements outside the
1666    range sorted. */
1667 static void
1668 test_sort_subset (void)
1669 {
1670   const int max_elems = 8;
1671
1672   int cnt, r0, r1, repeat;
1673
1674   for (cnt = 0; cnt <= max_elems; cnt++)
1675     for (repeat = 0; repeat < 100; repeat++)
1676       for (r0 = 0; r0 <= cnt; r0++)
1677         for (r1 = r0; r1 <= cnt; r1++)
1678           {
1679             struct ll_list list;
1680             struct element **elems;
1681             struct ll **elemp;
1682             int *values;
1683
1684             allocate_random (cnt, &list, &elems, &elemp, &values);
1685
1686             qsort (&values[r0], r1 - r0, sizeof *values, compare_ints_noaux);
1687             ll_sort (elemp[r0], elemp[r1], compare_elements, &aux_data);
1688             check_list_contents (&list, values, cnt);
1689
1690             free_elements (cnt, elems, elemp, values);
1691           }
1692 }
1693
1694 /* Tests that ll_sort works with large lists. */
1695 static void
1696 test_sort_big (void)
1697 {
1698   const int max_elems = 1024;
1699
1700   int cnt;
1701
1702   for (cnt = 0; cnt < max_elems; cnt++)
1703     {
1704       struct ll_list list;
1705       struct element **elems;
1706       int *values;
1707
1708       allocate_random (cnt, &list, &elems, NULL, &values);
1709
1710       qsort (values, cnt, sizeof *values, compare_ints_noaux);
1711       ll_sort (ll_head (&list), ll_null (&list), compare_elements, &aux_data);
1712       check_list_contents (&list, values, cnt);
1713
1714       free_elements (cnt, elems, NULL, values);
1715     }
1716 }
1717
1718 /* Tests ll_unique. */
1719 static void
1720 test_unique (void)
1721 {
1722   const int max_elems = 10;
1723
1724   int *ascending = xnmalloc (max_elems, sizeof *ascending);
1725
1726   int cnt, inc_pat, i, j, unique_values;
1727
1728   for (i = 0; i < max_elems; i++)
1729     ascending[i] = i;
1730
1731   for (cnt = 0; cnt < max_elems; cnt++)
1732     for (inc_pat = 0; inc_pat < (1 << cnt); inc_pat++)
1733       {
1734         struct ll_list list, dups;
1735         struct element **elems;
1736         int *values;
1737
1738         allocate_elements (cnt, &list, &elems, NULL, &values);
1739
1740         j = unique_values = 0;
1741         for (i = 0; i < cnt; i++)
1742           {
1743             unique_values = j + 1;
1744             elems[i]->x = values[i] = j;
1745             if (inc_pat & (1 << i))
1746               j++;
1747           }
1748         check_list_contents (&list, values, cnt);
1749
1750         ll_init (&dups);
1751         check (ll_unique (ll_head (&list), ll_null (&list), ll_null (&dups),
1752                           compare_elements, &aux_data)
1753                == (size_t) unique_values);
1754         check_list_contents (&list, ascending, unique_values);
1755
1756         ll_splice (ll_null (&list), ll_head (&dups), ll_null (&dups));
1757         ll_sort (ll_head (&list), ll_null (&list), compare_elements, &aux_data);
1758         check_list_contents (&list, values, cnt);
1759
1760         free_elements (cnt, elems, NULL, values);
1761       }
1762
1763   free (ascending);
1764 }
1765
1766 /* Tests ll_sort_unique. */
1767 static void
1768 test_sort_unique (void)
1769 {
1770   const int max_elems = 7;
1771   int cnt, inc_pat;
1772
1773   for (cnt = 0; cnt <= max_elems; cnt++)
1774     for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1775       {
1776         struct ll_list list;
1777         struct element **elems;
1778         int *values;
1779
1780         struct element **perm_elems;
1781         int *perm_values;
1782
1783         int unique_cnt;
1784         int *unique_values;
1785
1786         size_t perm_cnt;
1787         int i, j;
1788
1789         allocate_elements (cnt, &list, &elems, NULL, &values);
1790         allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1791
1792         j = unique_cnt = 0;
1793         for (i = 0; i < cnt; i++)
1794           {
1795             elems[i]->x = values[i] = j;
1796             unique_cnt = j + 1;
1797             if (inc_pat & (1 << i))
1798               j++;
1799           }
1800
1801         unique_values = xnmalloc (unique_cnt, sizeof *unique_values);
1802         for (i = 0; i < unique_cnt; i++)
1803           unique_values[i] = i;
1804
1805         perm_cnt = 1;
1806         while (ll_next_permutation (ll_head (&list), ll_null (&list),
1807                                     compare_elements, &aux_data))
1808           {
1809             struct ll_list perm_list;
1810
1811             extract_values (&list, perm_values, cnt);
1812             ll_init (&perm_list);
1813             for (i = 0; i < cnt; i++)
1814               {
1815                 perm_elems[i]->x = perm_values[i];
1816                 perm_elems[i]->y = i;
1817                 ll_push_tail (&perm_list, &perm_elems[i]->ll);
1818               }
1819             ll_sort_unique (ll_head (&perm_list), ll_null (&perm_list), NULL,
1820                             compare_elements, &aux_data);
1821             check_list_contents (&perm_list, unique_values, unique_cnt);
1822             check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1823                                  compare_elements_x_y, &aux_data));
1824             perm_cnt++;
1825           }
1826         check (perm_cnt == expected_perms (values, cnt));
1827
1828         free_elements (cnt, elems, NULL, values);
1829         free_elements (cnt, perm_elems, NULL, perm_values);
1830         free (unique_values);
1831       }
1832 }
1833
1834 /* Tests ll_insert_ordered. */
1835 static void
1836 test_insert_ordered (void)
1837 {
1838   const int max_elems = 6;
1839   int cnt, inc_pat;
1840
1841   for (cnt = 0; cnt <= max_elems; cnt++)
1842     for (inc_pat = 0; inc_pat <= 1 << cnt; inc_pat++)
1843       {
1844         struct ll_list list;
1845         struct element **elems;
1846         int *values;
1847
1848         struct element **perm_elems;
1849         int *perm_values;
1850
1851         size_t perm_cnt;
1852         int i, j;
1853
1854         allocate_elements (cnt, &list, &elems, NULL, &values);
1855         allocate_elements (cnt, NULL, &perm_elems, NULL, &perm_values);
1856
1857         j = 0;
1858         for (i = 0; i < cnt; i++)
1859           {
1860             elems[i]->x = values[i] = j;
1861             if (inc_pat & (1 << i))
1862               j++;
1863             elems[i]->y = i;
1864           }
1865
1866         perm_cnt = 1;
1867         while (ll_next_permutation (ll_head (&list), ll_null (&list),
1868                                     compare_elements_y, &aux_data))
1869           {
1870             struct ll_list perm_list;
1871
1872             extract_values (&list, perm_values, cnt);
1873             ll_init (&perm_list);
1874             for (i = 0; i < cnt; i++)
1875               {
1876                 perm_elems[i]->x = perm_values[i];
1877                 perm_elems[i]->y = i;
1878                 ll_insert_ordered (ll_head (&perm_list), ll_null (&perm_list),
1879                                    &perm_elems[i]->ll,
1880                                    compare_elements, &aux_data);
1881               }
1882             check (ll_is_sorted (ll_head (&perm_list), ll_null (&perm_list),
1883                                  compare_elements_x_y, &aux_data));
1884             perm_cnt++;
1885           }
1886         check (perm_cnt == factorial (cnt));
1887
1888         free_elements (cnt, elems, NULL, values);
1889         free_elements (cnt, perm_elems, NULL, perm_values);
1890       }
1891 }
1892
1893 /* Tests ll_partition. */
1894 static void
1895 test_partition (void)
1896 {
1897   const int max_elems = 10;
1898
1899   int cnt;
1900   unsigned int pbase;
1901   int r0, r1;
1902
1903   for (cnt = 0; cnt < max_elems; cnt++)
1904     for (r0 = 0; r0 <= cnt; r0++)
1905       for (r1 = r0; r1 <= cnt; r1++)
1906         for (pbase = 0; pbase <= (1u << (r1 - r0)); pbase++)
1907           {
1908             struct ll_list list;
1909             struct element **elems;
1910             struct ll **elemp;
1911             int *values;
1912
1913             unsigned int pattern = pbase << r0;
1914             int i, j;
1915             int first_false;
1916             struct ll *part_ll;
1917
1918             allocate_ascending (cnt, &list, &elems, &elemp, &values);
1919
1920             /* Check that ll_find_partition works okay in every
1921                case.  We use it after partitioning, too, but that
1922                only tests cases where it returns non-null. */
1923             for (i = r0; i < r1; i++)
1924               if (!(pattern & (1u << i)))
1925                 break;
1926             j = i;
1927             for (; i < r1; i++)
1928               if (pattern & (1u << i))
1929                 break;
1930             part_ll = ll_find_partition (elemp[r0], elemp[r1],
1931                                          pattern_pred,
1932                                          &pattern);
1933             if (i == r1)
1934               check (part_ll == elemp[j]);
1935             else
1936               check (part_ll == NULL);
1937
1938             /* Figure out expected results. */
1939             j = 0;
1940             first_false = -1;
1941             for (i = 0; i < r0; i++)
1942               values[j++] = i;
1943             for (i = r0; i < r1; i++)
1944               if (pattern & (1u << i))
1945                 values[j++] = i;
1946             for (i = r0; i < r1; i++)
1947               if (!(pattern & (1u << i)))
1948                 {
1949                   if (first_false == -1)
1950                     first_false = i;
1951                   values[j++] = i;
1952                 }
1953             if (first_false == -1)
1954               first_false = r1;
1955             for (i = r1; i < cnt; i++)
1956               values[j++] = i;
1957             check (j == cnt);
1958
1959             /* Partition and check for expected results. */
1960             check (ll_partition (elemp[r0], elemp[r1],
1961                                  pattern_pred, &pattern)
1962                    == elemp[first_false]);
1963             check (ll_find_partition (elemp[r0], elemp[r1],
1964                                       pattern_pred, &pattern)
1965                    == elemp[first_false]);
1966             check_list_contents (&list, values, cnt);
1967             check ((int) ll_count (&list) == cnt);
1968
1969             free_elements (cnt, elems, elemp, values);
1970           }
1971 }
1972 \f
1973 /* Main program. */
1974
1975 /* Runs TEST_FUNCTION and prints a message about NAME. */
1976 static void
1977 run_test (void (*test_function) (void), const char *name)
1978 {
1979   test_name = name;
1980   putchar ('.');
1981   fflush (stdout);
1982   test_function ();
1983 }
1984
1985 int
1986 main (void)
1987 {
1988   run_test (test_push_pop, "push/pop");
1989   run_test (test_insert_remove, "insert/remove");
1990   run_test (test_swap, "swap");
1991   run_test (test_swap_range, "swap_range");
1992   run_test (test_remove_range, "remove_range");
1993   run_test (test_remove_equal, "remove_equal");
1994   run_test (test_remove_if, "remove_if");
1995   run_test (test_moved, "moved");
1996   run_test (test_find_equal, "find_equal");
1997   run_test (test_find_if, "find_if");
1998   run_test (test_find_adjacent_equal, "find_adjacent_equal");
1999   run_test (test_count_range, "count_range");
2000   run_test (test_count_equal, "count_equal");
2001   run_test (test_count_if, "count_if");
2002   run_test (test_min_max, "min/max");
2003   run_test (test_lexicographical_compare_3way, "lexicographical_compare_3way");
2004   run_test (test_apply, "apply");
2005   run_test (test_reverse, "reverse");
2006   run_test (test_permutations_no_dups, "permutations (no dups)");
2007   run_test (test_permutations_with_dups, "permutations (with dups)");
2008   run_test (test_merge_no_dups, "merge (no dups)");
2009   run_test (test_merge_with_dups, "merge (with dups)");
2010   run_test (test_sort_exhaustive, "sort (exhaustive)");
2011   run_test (test_sort_stable, "sort (stability)");
2012   run_test (test_sort_subset, "sort (subset)");
2013   run_test (test_sort_big, "sort (big)");
2014   run_test (test_unique, "unique");
2015   run_test (test_sort_unique, "sort_unique");
2016   run_test (test_insert_ordered, "insert_ordered");
2017   run_test (test_partition, "partition");
2018   putchar ('\n');
2019
2020   return 0;
2021 }
2022
2023 /*
2024   Local Variables:
2025   compile-command: "gcc -Wall -Wstrict-prototypes -Wmissing-prototypes ll.c ll-test.c -o ll-test -g"
2026   End:
2027  */