tests/libpspp/llx-test.c

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