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