tests/libpspp/ll-test.c

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