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