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