pintos-os.org Git - pspp/blob - tests/libpspp/abt-test.c

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