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  */