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