tests/libpspp/abt-test.c

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 2007 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 abt_* routines defined in
  20    abt.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 abt_* routines.  "valgrind --leak-check=yes
  23    --show-reachable=yes" should give a clean report. */
  24
  25 #ifdef HAVE_CONFIG_H
  26 #include <config.h>
  27 #endif
  28
  29 #include <libpspp/abt.h>
  30
  31 #include <assert.h>
  32 #include <stdbool.h>
  33 #include <stddef.h>
  34 #include <stdio.h>
  35 #include <stdlib.h>
  36 #include <string.h>
  37
  38 #include <libpspp/compiler.h>
  39 \f
  40 /* Currently running test. */
  41 static const char *test_name;
  42
  43 /* Exit with a failure code.
  44    (Place a breakpoint on this function while debugging.) */
  45 static void
  46 check_die (void)
  47 {
  48   exit (EXIT_FAILURE);
  49 }
  50
  51 /* If OK is not true, prints a message about failure on the
  52    current source file and the given LINE and terminates. */
  53 static void
  54 check_func (bool ok, int line)
  55 {
  56   if (!ok)
  57     {
  58       printf ("Check failed in %s test at %s, line %d\n",
  59               test_name, __FILE__, line);
  60       check_die ();
  61     }
  62 }
  63
  64 /* Verifies that EXPR evaluates to true.
  65    If not, prints a message citing the calling line number and
  66    terminates. */
  67 #define check(EXPR) check_func ((EXPR), __LINE__)
  68
  69 /* Prints a message about memory exhaustion and exits with a
  70    failure code. */
  71 static void
  72 xalloc_die (void)
  73 {
  74   printf ("virtual memory exhausted\n");
  75   exit (EXIT_FAILURE);
  76 }
  77
  78 /* Allocates and returns N bytes of memory. */
  79 static void *
  80 xmalloc (size_t n)
  81 {
  82   if (n != 0)
  83     {
  84       void *p = malloc (n);
  85       if (p == NULL)
  86         xalloc_die ();
  87
  88       return p;
  89     }
  90   else
  91     return NULL;
  92 }
  93
  94 static void *
  95 xmemdup (const void *p, size_t n)
  96 {
  97   void *q = xmalloc (n);
  98   memcpy (q, p, n);
  99   return q;
 100 }
 101
 102 /* Allocates and returns N * M bytes of memory. */
 103 static void *
 104 xnmalloc (size_t n, size_t m)
 105 {
 106   if ((size_t) -1 / m <= n)
 107     xalloc_die ();
 108   return xmalloc (n * m);
 109 }
 110 \f
 111 /* Node type and support routines. */
 112
 113 /* Test data element. */
 114 struct element
 115   {
 116     struct abt_node node;       /* Embedded binary tree element. */
 117     int data;                   /* Primary value. */
 118     int count;                  /* Number of nodes in subtree,
 119                                    including this node. */
 120   };
 121
 122 static int aux_data;
 123
 124 /* Returns the `struct element' that NODE is embedded within. */
 125 static struct element *
 126 abt_node_to_element (const struct abt_node *node)
 127 {
 128   return abt_data (node, struct element, node);
 129 }
 130
 131 /* Compares the `x' values in A and B and returns a strcmp-type
 132    return value.  Verifies that AUX points to aux_data. */
 133 static int
 134 compare_elements (const struct abt_node *a_, const struct abt_node *b_,
 135                   const void *aux)
 136 {
 137   const struct element *a = abt_node_to_element (a_);
 138   const struct element *b = abt_node_to_element (b_);
 139
 140   check (aux == &aux_data);
 141   return a->data < b->data ? -1 : a->data > b->data;
 142 }
 143
 144 /* Recalculates the count for NODE's subtree by adding up the
 145    counts for its LEFT and RIGHT child subtrees. */
 146 static void
 147 reaugment_elements (struct abt_node *node_,
 148                     const struct abt_node *left,
 149                     const struct abt_node *right,
 150                     const void *aux)
 151 {
 152   struct element *node = abt_node_to_element (node_);
 153
 154   check (aux == &aux_data);
 155
 156   node->count = 1;
 157   if (left != NULL)
 158     node->count += abt_node_to_element (left)->count;
 159   if (right != NULL)
 160     node->count += abt_node_to_element (right)->count;
 161 }
 162
 163 /* Compares A and B and returns a strcmp-type return value. */
 164 static int
 165 compare_ints_noaux (const void *a_, const void *b_)
 166 {
 167   const int *a = a_;
 168   const int *b = b_;
 169
 170   return *a < *b ? -1 : *a > *b;
 171 }
 172
 173 /* Swaps *A and *B. */
 174 static void
 175 swap (int *a, int *b)
 176 {
 177   int t = *a;
 178   *a = *b;
 179   *b = t;
 180 }
 181
 182 /* Reverses the order of the CNT integers starting at VALUES. */
 183 static void
 184 reverse (int *values, size_t cnt)
 185 {
 186   size_t i = 0;
 187   size_t j = cnt;
 188
 189   while (j > i)
 190     swap (&values[i++], &values[--j]);
 191 }
 192
 193 /* Arranges the CNT elements in VALUES into the lexicographically
 194    next greater permutation.  Returns true if successful.
 195    If VALUES is already the lexicographically greatest
 196    permutation of its elements (i.e. ordered from greatest to
 197    smallest), arranges them into the lexicographically least
 198    permutation (i.e. ordered from smallest to largest) and
 199    returns false. */
 200 static bool
 201 next_permutation (int *values, size_t cnt)
 202 {
 203   if (cnt > 0)
 204     {
 205       size_t i = cnt - 1;
 206       while (i != 0)
 207         {
 208           i--;
 209           if (values[i] < values[i + 1])
 210             {
 211               size_t j;
 212               for (j = cnt - 1; values[i] >= values[j]; j--)
 213                 continue;
 214               swap (values + i, values + j);
 215               reverse (values + (i + 1), cnt - (i + 1));
 216               return true;
 217             }
 218         }
 219
 220       reverse (values, cnt);
 221     }
 222
 223   return false;
 224 }
 225
 226 /* Returns N!. */
 227 static unsigned int
 228 factorial (unsigned int n)
 229 {
 230   unsigned int value = 1;
 231   while (n > 1)
 232     value *= n--;
 233   return value;
 234 }
 235
 236 /* Randomly shuffles the CNT elements in ARRAY, each of which is
 237    SIZE bytes in size. */
 238 static void
 239 random_shuffle (void *array_, size_t cnt, size_t size)
 240 {
 241   char *array = array_;
 242   char *tmp = xmalloc (size);
 243   size_t i;
 244
 245   for (i = 0; i < cnt; i++)
 246     {
 247       size_t j = rand () % (cnt - i) + i;
 248       if (i != j)
 249         {
 250           memcpy (tmp, array + j * size, size);
 251           memcpy (array + j * size, array + i * size, size);
 252           memcpy (array + i * size, tmp, size);
 253         }
 254     }
 255
 256   free (tmp);
 257 }
 258
 259 /* Finds and returns the element in ABT that is in the given
 260    0-based POSITION in in-order. */
 261 static struct element *
 262 find_by_position (struct abt *abt, int position)
 263 {
 264   struct abt_node *p;
 265   for (p = abt->root; p != NULL; )
 266     {
 267       int p_pos = p->down[0] ? abt_node_to_element (p->down[0])->count : 0;
 268       if (position == p_pos)
 269         return abt_node_to_element (p);
 270       else if (position < p_pos)
 271         p = p->down[0];
 272       else
 273         {
 274           p = p->down[1];
 275           position -= p_pos + 1;
 276         }
 277     }
 278   return NULL;
 279 }
 280
 281 /* Checks that all the augmentations are correct in the subtree
 282    rooted at P.  Returns the number of nodes in the subtree. */
 283 static int
 284 check_augmentations (struct abt_node *p_)
 285 {
 286   if (p_ == NULL)
 287     return 0;
 288   else
 289     {
 290       struct element *p = abt_node_to_element (p_);
 291       int left_count = check_augmentations (p->node.down[0]);
 292       int right_count = check_augmentations (p->node.down[1]);
 293       int total = left_count + right_count + 1;
 294       check (p->count == total);
 295       return total;
 296     }
 297 }
 298
 299 /* Check that the levels are correct in the subtree rooted at P. */
 300 static void
 301 check_levels (struct abt_node *p)
 302 {
 303   if (p != NULL)
 304     {
 305       int i, j;
 306
 307       check_levels (p->down[0]);
 308       check_levels (p->down[1]);
 309
 310       check (p->level >= 1);
 311       if (p->level > 1)
 312         {
 313           struct abt_node *q = p->down[1];
 314           check (q != NULL);
 315           check (q->level == p->level || q->level == p->level - 1);
 316         }
 317
 318       for (i = 0; i < 2; i++)
 319         if (p->down[i] != NULL)
 320           for (j = 0; j < 2; j++)
 321             if (p->down[i]->down[j] != NULL)
 322               check (p->down[i]->down[j]->level < p->level);
 323     }
 324 }
 325
 326 /* Checks that ABT contains the CNT ints in DATA, that its
 327    structure is correct, and that certain operations on ABT
 328    produce the expected results. */
 329 static void
 330 check_abt (struct abt *abt, const int data[], size_t cnt)
 331 {
 332   struct element e;
 333   size_t i;
 334   int *order;
 335
 336   order = xmemdup (data, cnt * sizeof *data);
 337   qsort (order, cnt, sizeof *order, compare_ints_noaux);
 338
 339   for (i = 0; i < cnt; i++)
 340     {
 341       struct abt_node *p;
 342
 343       e.data = data[i];
 344       if (rand () % 2)
 345         p = abt_find (abt, &e.node);
 346       else
 347         p = abt_insert (abt, &e.node);
 348       check (p != NULL);
 349       check (p != &e.node);
 350       check (abt_node_to_element (p)->data == data[i]);
 351     }
 352
 353   e.data = -1;
 354   check (abt_find (abt, &e.node) == NULL);
 355
 356   check_levels (abt->root);
 357   check_augmentations (abt->root);
 358   for (i = 0; i < cnt; i++)
 359     check (find_by_position (abt, i)->data == order[i]);
 360
 361   if (cnt == 0)
 362     {
 363       check (abt_first (abt) == NULL);
 364       check (abt_last (abt) == NULL);
 365       check (abt_next (abt, NULL) == NULL);
 366       check (abt_prev (abt, NULL) == NULL);
 367     }
 368   else
 369     {
 370       struct abt_node *p;
 371
 372       for (p = abt_first (abt), i = 0; i < cnt; p = abt_next (abt, p), i++)
 373         check (abt_node_to_element (p)->data == order[i]);
 374       check (p == NULL);
 375
 376       for (p = abt_last (abt), i = 0; i < cnt; p = abt_prev (abt, p), i++)
 377         check (abt_node_to_element (p)->data == order[cnt - i - 1]);
 378       check (p == NULL);
 379     }
 380
 381   free (order);
 382 }
 383
 384 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
 385    ABT in the order specified by INSERTIONS, then deletes them in
 386    the order specified by DELETIONS, checking the ABT's contents
 387    for correctness after each operation. */
 388 static void
 389 test_insert_delete (const int insertions[],
 390                     const int deletions[],
 391                     size_t cnt)
 392 {
 393   struct element *elements;
 394   struct abt abt;
 395   size_t i;
 396
 397   elements = xnmalloc (cnt, sizeof *elements);
 398   for (i = 0; i < cnt; i++)
 399     elements[i].data = i;
 400
 401   abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
 402   check_abt (&abt, NULL, 0);
 403   for (i = 0; i < cnt; i++)
 404     {
 405       check (abt_insert (&abt, &elements[insertions[i]].node) == NULL);
 406       check_abt (&abt, insertions, i + 1);
 407     }
 408   for (i = 0; i < cnt; i++)
 409     {
 410       abt_delete (&abt, &elements[deletions[i]].node);
 411       check_abt (&abt, deletions + i + 1, cnt - i - 1);
 412     }
 413
 414   free (elements);
 415 }
 416 \f
 417 /* Inserts values into an ABT in each possible order, then
 418    removes them in each possible order, up to a specified maximum
 419    size. */
 420 static void
 421 test_insert_any_remove_any (void)
 422 {
 423   const int max_elems = 5;
 424   int cnt;
 425
 426   for (cnt = 0; cnt <= max_elems; cnt++)
 427     {
 428       int *insertions, *deletions;
 429       unsigned int ins_perm_cnt;
 430       int i;
 431
 432       insertions = xnmalloc (cnt, sizeof *insertions);
 433       deletions = xnmalloc (cnt, sizeof *deletions);
 434       for (i = 0; i < cnt; i++)
 435         insertions[i] = i;
 436
 437       for (ins_perm_cnt = 0;
 438            ins_perm_cnt == 0 || next_permutation (insertions, cnt);
 439            ins_perm_cnt++)
 440         {
 441           unsigned int del_perm_cnt;
 442           int i;
 443
 444           for (i = 0; i < cnt; i++)
 445             deletions[i] = i;
 446
 447           for (del_perm_cnt = 0;
 448                del_perm_cnt == 0 || next_permutation (deletions, cnt);
 449                del_perm_cnt++)
 450             test_insert_delete (insertions, deletions, cnt);
 451
 452           check (del_perm_cnt == factorial (cnt));
 453         }
 454       check (ins_perm_cnt == factorial (cnt));
 455
 456       free (insertions);
 457       free (deletions);
 458     }
 459 }
 460
 461 /* Inserts values into an ABT in each possible order, then
 462    removes them in the same order, up to a specified maximum
 463    size. */
 464 static void
 465 test_insert_any_remove_same (void)
 466 {
 467   const int max_elems = 7;
 468   int cnt;
 469
 470   for (cnt = 0; cnt <= max_elems; cnt++)
 471     {
 472       int *values;
 473       unsigned int permutation_cnt;
 474       int i;
 475
 476       values = xnmalloc (cnt, sizeof *values);
 477       for (i = 0; i < cnt; i++)
 478         values[i] = i;
 479
 480       for (permutation_cnt = 0;
 481            permutation_cnt == 0 || next_permutation (values, cnt);
 482            permutation_cnt++)
 483         test_insert_delete (values, values, cnt);
 484       check (permutation_cnt == factorial (cnt));
 485
 486       free (values);
 487     }
 488 }
 489
 490 /* Inserts values into an ABT in each possible order, then
 491    removes them in reverse order, up to a specified maximum
 492    size. */
 493 static void
 494 test_insert_any_remove_reverse (void)
 495 {
 496   const int max_elems = 7;
 497   int cnt;
 498
 499   for (cnt = 0; cnt <= max_elems; cnt++)
 500     {
 501       int *insertions, *deletions;
 502       unsigned int permutation_cnt;
 503       int i;
 504
 505       insertions = xnmalloc (cnt, sizeof *insertions);
 506       deletions = xnmalloc (cnt, sizeof *deletions);
 507       for (i = 0; i < cnt; i++)
 508         insertions[i] = i;
 509
 510       for (permutation_cnt = 0;
 511            permutation_cnt == 0 || next_permutation (insertions, cnt);
 512            permutation_cnt++)
 513         {
 514           memcpy (deletions, insertions, sizeof *insertions * cnt);
 515           reverse (deletions, cnt);
 516
 517           test_insert_delete (insertions, deletions, cnt);
 518         }
 519       check (permutation_cnt == factorial (cnt));
 520
 521       free (insertions);
 522       free (deletions);
 523     }
 524 }
 525
 526 /* Inserts and removes values in an ABT in random orders. */
 527 static void
 528 test_random_sequence (void)
 529 {
 530   const int max_elems = 128;
 531   const int max_trials = 8;
 532   int cnt;
 533
 534   for (cnt = 0; cnt <= max_elems; cnt += 2)
 535     {
 536       int *insertions, *deletions;
 537       int trial;
 538       int i;
 539
 540       insertions = xnmalloc (cnt, sizeof *insertions);
 541       deletions = xnmalloc (cnt, sizeof *deletions);
 542       for (i = 0; i < cnt; i++)
 543         insertions[i] = i;
 544       for (i = 0; i < cnt; i++)
 545         deletions[i] = i;
 546
 547       for (trial = 0; trial < max_trials; trial++)
 548         {
 549           random_shuffle (insertions, cnt, sizeof *insertions);
 550           random_shuffle (deletions, cnt, sizeof *deletions);
 551
 552           test_insert_delete (insertions, deletions, cnt);
 553         }
 554
 555       free (insertions);
 556       free (deletions);
 557     }
 558 }
 559
 560 /* Inserts elements into an ABT in ascending order. */
 561 static void
 562 test_insert_ordered (void)
 563 {
 564   const int max_elems = 1024;
 565   struct element *elements;
 566   int *values;
 567   struct abt abt;
 568   int i;
 569
 570   abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
 571   elements = xnmalloc (max_elems, sizeof *elements);
 572   values = xnmalloc (max_elems, sizeof *values);
 573   for (i = 0; i < max_elems; i++)
 574     {
 575       values[i] = elements[i].data = i;
 576       check (abt_insert (&abt, &elements[i].node) == NULL);
 577       check_abt (&abt, values, i + 1);
 578     }
 579   free (elements);
 580   free (values);
 581 }
 582
 583 /* Inserts elements into an ABT, then moves the nodes around in
 584    memory. */
 585 static void
 586 test_moved (void)
 587 {
 588   const int max_elems = 128;
 589   struct element *e[2];
 590   int cur;
 591   int *values;
 592   struct abt abt;
 593   int i, j;
 594
 595   abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
 596   e[0] = xnmalloc (max_elems, sizeof *e[0]);
 597   e[1] = xnmalloc (max_elems, sizeof *e[1]);
 598   values = xnmalloc (max_elems, sizeof *values);
 599   cur = 0;
 600   for (i = 0; i < max_elems; i++)
 601     {
 602       values[i] = e[cur][i].data = i;
 603       check (abt_insert (&abt, &e[cur][i].node) == NULL);
 604       check_abt (&abt, values, i + 1);
 605
 606       for (j = 0; j <= i; j++)
 607         {
 608           e[!cur][j] = e[cur][j];
 609           abt_moved (&abt, &e[!cur][j].node);
 610           check_abt (&abt, values, i + 1);
 611         }
 612       cur = !cur;
 613     }
 614   free (e[0]);
 615   free (e[1]);
 616   free (values);
 617 }
 618
 619 /* Inserts values into an ABT, then changes their values. */
 620 static void
 621 test_changed (void)
 622 {
 623   const int max_elems = 6;
 624   int cnt;
 625
 626   for (cnt = 0; cnt <= max_elems; cnt++)
 627     {
 628       int *values, *changed_values;
 629       struct element *elements;
 630       unsigned int permutation_cnt;
 631       int i;
 632
 633       values = xnmalloc (cnt, sizeof *values);
 634       changed_values = xnmalloc (cnt, sizeof *changed_values);
 635       elements = xnmalloc (cnt, sizeof *elements);
 636       for (i = 0; i < cnt; i++)
 637         values[i] = i;
 638
 639       for (permutation_cnt = 0;
 640            permutation_cnt == 0 || next_permutation (values, cnt);
 641            permutation_cnt++)
 642         {
 643           for (i = 0; i < cnt; i++)
 644             {
 645               int j, k;
 646               for (j = 0; j <= cnt; j++)
 647                 {
 648                   struct abt abt;
 649                   struct abt_node *changed_retval;
 650
 651                   abt_init (&abt, compare_elements, reaugment_elements,
 652                             &aux_data);
 653
 654                   /* Add to ABT in order. */
 655                   for (k = 0; k < cnt; k++)
 656                     {
 657                       int n = values[k];
 658                       elements[n].data = n;
 659                       check (abt_insert (&abt, &elements[n].node) == NULL);
 660                     }
 661                   check_abt (&abt, values, cnt);
 662
 663                   /* Change value i to j. */
 664                   elements[i].data = j;
 665                   for (k = 0; k < cnt; k++)
 666                     changed_values[k] = k;
 667                   changed_retval = abt_changed (&abt, &elements[i].node);
 668                   if (i != j && j < cnt)
 669                     {
 670                       /* Will cause duplicate. */
 671                       check (changed_retval == &elements[j].node);
 672                       changed_values[i] = changed_values[cnt - 1];
 673                       check_abt (&abt, changed_values, cnt - 1);
 674                     }
 675                   else
 676                     {
 677                       /* Succeeds. */
 678                       check (changed_retval == NULL);
 679                       changed_values[i] = j;
 680                       check_abt (&abt, changed_values, cnt);
 681                     }
 682                 }
 683             }
 684         }
 685       check (permutation_cnt == factorial (cnt));
 686
 687       free (values);
 688       free (changed_values);
 689       free (elements);
 690     }
 691 }
 692 \f
 693 /* Main program. */
 694
 695 /* Runs TEST_FUNCTION and prints a message about NAME. */
 696 static void
 697 run_test (void (*test_function) (void), const char *name)
 698 {
 699   test_name = name;
 700   putchar ('.');
 701   fflush (stdout);
 702   test_function ();
 703 }
 704
 705 int
 706 main (void)
 707 {
 708   run_test (test_insert_any_remove_any,
 709             "insert any order, delete any order");
 710   run_test (test_insert_any_remove_same,
 711             "insert any order, delete same order");
 712   run_test (test_insert_any_remove_reverse,
 713             "insert any order, delete reverse order");
 714   run_test (test_random_sequence,
 715             "insert and delete in random sequence");
 716   run_test (test_insert_ordered,
 717             "insert in ascending order");
 718   run_test (test_moved, "move elements around in memory");
 719   run_test (test_changed, "change key data in nodes");
 720   putchar ('\n');
 721
 722   return 0;
 723 }