tests/libpspp/ll-test.c

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