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