tests/libpspp/llx-test.c

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