pintos-os.org Git - pspp/blob - tests/libpspp/ll-test.c

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