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