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