tests/libpspp/llx-test.c

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