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