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