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