tests/libpspp/ll-test.c

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