tests/libpspp/ll-test.c

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