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