tests/libpspp/llx-test.c

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