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
 375   free (order);
 376 }
 377
 378 /* Ways that nodes can be inserted. */
 379 enum insertion_method
 380   {
 381     INSERT,             /* With abt_insert. */
 382     INSERT_AFTER,       /* With abt_insert_after. */
 383     INSERT_BEFORE       /* With abt_insert_before. */
 384   };
 385
 386 /* Inserts INSERT into ABT with the given METHOD. */
 387 static void
 388 insert_node (struct abt *abt, struct element *insert,
 389              enum insertion_method method)
 390 {
 391   if (method == INSERT)
 392     check (abt_insert (abt, &insert->node) == NULL);
 393   else
 394     {
 395       struct abt_node *p = abt->root;
 396       int dir = 0;
 397       if (p != NULL)
 398         for (;;)
 399           {
 400             dir = insert->data > abt_node_to_element (p)->data;
 401             if (p->down[dir] == NULL)
 402               break;
 403             p = p->down[dir];
 404           }
 405       if (method == INSERT_AFTER)
 406         {
 407           if (p != NULL && (dir != 1 || p->down[1] != NULL))
 408             p = abt_prev (abt, p);
 409           abt_insert_after (abt, p, &insert->node);
 410         }
 411       else
 412         {
 413           if (p != NULL && (dir != 0 || p->down[0] != NULL))
 414             p = abt_next (abt, p);
 415           abt_insert_before (abt, p, &insert->node);
 416         }
 417     }
 418 }
 419
 420
 421 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
 422    ABT in the order specified by INSERTIONS using the given
 423    METHOD, then deletes them in the order specified by DELETIONS,
 424    checking the ABT's contents for correctness after each
 425    operation. */
 426 static void
 427 do_test_insert_delete (enum insertion_method method,
 428                        const int insertions[],
 429                        const int deletions[],
 430                        size_t cnt)
 431 {
 432   struct element *elements;
 433   struct abt abt;
 434   size_t i;
 435
 436   elements = xnmalloc (cnt, sizeof *elements);
 437   for (i = 0; i < cnt; i++)
 438     elements[i].data = i;
 439
 440   abt_init (&abt, method == INSERT ? compare_elements : NULL,
 441             reaugment_elements, &aux_data);
 442   check_abt (&abt, NULL, 0);
 443   for (i = 0; i < cnt; i++)
 444     {
 445       insert_node (&abt, &elements[insertions[i]], method);
 446       check_abt (&abt, insertions, i + 1);
 447     }
 448   for (i = 0; i < cnt; i++)
 449     {
 450       abt_delete (&abt, &elements[deletions[i]].node);
 451       check_abt (&abt, deletions + i + 1, cnt - i - 1);
 452     }
 453
 454   free (elements);
 455 }
 456
 457 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
 458    ABT in the order specified by INSERTIONS, then deletes them in
 459    the order specified by DELETIONS, checking the ABT's contents
 460    for correctness after each operation. */
 461 static void
 462 test_insert_delete (const int insertions[],
 463                     const int deletions[],
 464                     size_t cnt)
 465 {
 466   do_test_insert_delete (INSERT, insertions, deletions, cnt);
 467   do_test_insert_delete (INSERT_AFTER, insertions, deletions, cnt);
 468   do_test_insert_delete (INSERT_BEFORE, insertions, deletions, cnt);
 469 }
 470 \f
 471 /* Inserts values into an ABT in each possible order, then
 472    removes them in each possible order, up to a specified maximum
 473    size. */
 474 static void
 475 test_insert_any_remove_any (void)
 476 {
 477   const int max_elems = 5;
 478   int cnt;
 479
 480   for (cnt = 0; cnt <= max_elems; cnt++)
 481     {
 482       int *insertions, *deletions;
 483       unsigned int ins_perm_cnt;
 484       int i;
 485
 486       insertions = xnmalloc (cnt, sizeof *insertions);
 487       deletions = xnmalloc (cnt, sizeof *deletions);
 488       for (i = 0; i < cnt; i++)
 489         insertions[i] = i;
 490
 491       for (ins_perm_cnt = 0;
 492            ins_perm_cnt == 0 || next_permutation (insertions, cnt);
 493            ins_perm_cnt++)
 494         {
 495           unsigned int del_perm_cnt;
 496           int i;
 497
 498           for (i = 0; i < cnt; i++)
 499             deletions[i] = i;
 500
 501           for (del_perm_cnt = 0;
 502                del_perm_cnt == 0 || next_permutation (deletions, cnt);
 503                del_perm_cnt++)
 504             test_insert_delete (insertions, deletions, cnt);
 505
 506           check (del_perm_cnt == factorial (cnt));
 507         }
 508       check (ins_perm_cnt == factorial (cnt));
 509
 510       free (insertions);
 511       free (deletions);
 512     }
 513 }
 514
 515 /* Inserts values into an ABT in each possible order, then
 516    removes them in the same order, up to a specified maximum
 517    size. */
 518 static void
 519 test_insert_any_remove_same (void)
 520 {
 521   const int max_elems = 7;
 522   int cnt;
 523
 524   for (cnt = 0; cnt <= max_elems; cnt++)
 525     {
 526       int *values;
 527       unsigned int permutation_cnt;
 528       int i;
 529
 530       values = xnmalloc (cnt, sizeof *values);
 531       for (i = 0; i < cnt; i++)
 532         values[i] = i;
 533
 534       for (permutation_cnt = 0;
 535            permutation_cnt == 0 || next_permutation (values, cnt);
 536            permutation_cnt++)
 537         test_insert_delete (values, values, cnt);
 538       check (permutation_cnt == factorial (cnt));
 539
 540       free (values);
 541     }
 542 }
 543
 544 /* Inserts values into an ABT in each possible order, then
 545    removes them in reverse order, up to a specified maximum
 546    size. */
 547 static void
 548 test_insert_any_remove_reverse (void)
 549 {
 550   const int max_elems = 7;
 551   int cnt;
 552
 553   for (cnt = 0; cnt <= max_elems; cnt++)
 554     {
 555       int *insertions, *deletions;
 556       unsigned int permutation_cnt;
 557       int i;
 558
 559       insertions = xnmalloc (cnt, sizeof *insertions);
 560       deletions = xnmalloc (cnt, sizeof *deletions);
 561       for (i = 0; i < cnt; i++)
 562         insertions[i] = i;
 563
 564       for (permutation_cnt = 0;
 565            permutation_cnt == 0 || next_permutation (insertions, cnt);
 566            permutation_cnt++)
 567         {
 568           memcpy (deletions, insertions, sizeof *insertions * cnt);
 569           reverse (deletions, cnt);
 570
 571           test_insert_delete (insertions, deletions, cnt);
 572         }
 573       check (permutation_cnt == factorial (cnt));
 574
 575       free (insertions);
 576       free (deletions);
 577     }
 578 }
 579
 580 /* Inserts and removes values in an ABT in random orders. */
 581 static void
 582 test_random_sequence (void)
 583 {
 584   const int max_elems = 128;
 585   const int max_trials = 8;
 586   int cnt;
 587
 588   for (cnt = 0; cnt <= max_elems; cnt += 2)
 589     {
 590       int *insertions, *deletions;
 591       int trial;
 592       int i;
 593
 594       insertions = xnmalloc (cnt, sizeof *insertions);
 595       deletions = xnmalloc (cnt, sizeof *deletions);
 596       for (i = 0; i < cnt; i++)
 597         insertions[i] = i;
 598       for (i = 0; i < cnt; i++)
 599         deletions[i] = i;
 600
 601       for (trial = 0; trial < max_trials; trial++)
 602         {
 603           random_shuffle (insertions, cnt, sizeof *insertions);
 604           random_shuffle (deletions, cnt, sizeof *deletions);
 605
 606           test_insert_delete (insertions, deletions, cnt);
 607         }
 608
 609       free (insertions);
 610       free (deletions);
 611     }
 612 }
 613
 614 /* Inserts elements into an ABT in ascending order. */
 615 static void
 616 test_insert_ordered (void)
 617 {
 618   const int max_elems = 1024;
 619   struct element *elements;
 620   int *values;
 621   struct abt abt;
 622   int i;
 623
 624   abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
 625   elements = xnmalloc (max_elems, sizeof *elements);
 626   values = xnmalloc (max_elems, sizeof *values);
 627   for (i = 0; i < max_elems; i++)
 628     {
 629       values[i] = elements[i].data = i;
 630       check (abt_insert (&abt, &elements[i].node) == NULL);
 631       check_abt (&abt, values, i + 1);
 632     }
 633   free (elements);
 634   free (values);
 635 }
 636
 637 /* Inserts elements into an ABT, then moves the nodes around in
 638    memory. */
 639 static void
 640 test_moved (void)
 641 {
 642   const int max_elems = 128;
 643   struct element *e[2];
 644   int cur;
 645   int *values;
 646   struct abt abt;
 647   int i, j;
 648
 649   abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
 650   e[0] = xnmalloc (max_elems, sizeof *e[0]);
 651   e[1] = xnmalloc (max_elems, sizeof *e[1]);
 652   values = xnmalloc (max_elems, sizeof *values);
 653   cur = 0;
 654   for (i = 0; i < max_elems; i++)
 655     {
 656       values[i] = e[cur][i].data = i;
 657       check (abt_insert (&abt, &e[cur][i].node) == NULL);
 658       check_abt (&abt, values, i + 1);
 659
 660       for (j = 0; j <= i; j++)
 661         {
 662           e[!cur][j] = e[cur][j];
 663           abt_moved (&abt, &e[!cur][j].node);
 664           check_abt (&abt, values, i + 1);
 665         }
 666       cur = !cur;
 667     }
 668   free (e[0]);
 669   free (e[1]);
 670   free (values);
 671 }
 672
 673 /* Inserts values into an ABT, then changes their values. */
 674 static void
 675 test_changed (void)
 676 {
 677   const int max_elems = 6;
 678   int cnt;
 679
 680   for (cnt = 0; cnt <= max_elems; cnt++)
 681     {
 682       int *values, *changed_values;
 683       struct element *elements;
 684       unsigned int permutation_cnt;
 685       int i;
 686
 687       values = xnmalloc (cnt, sizeof *values);
 688       changed_values = xnmalloc (cnt, sizeof *changed_values);
 689       elements = xnmalloc (cnt, sizeof *elements);
 690       for (i = 0; i < cnt; i++)
 691         values[i] = i;
 692
 693       for (permutation_cnt = 0;
 694            permutation_cnt == 0 || next_permutation (values, cnt);
 695            permutation_cnt++)
 696         {
 697           for (i = 0; i < cnt; i++)
 698             {
 699               int j, k;
 700               for (j = 0; j <= cnt; j++)
 701                 {
 702                   struct abt abt;
 703                   struct abt_node *changed_retval;
 704
 705                   abt_init (&abt, compare_elements, reaugment_elements,
 706                             &aux_data);
 707
 708                   /* Add to ABT in order. */
 709                   for (k = 0; k < cnt; k++)
 710                     {
 711                       int n = values[k];
 712                       elements[n].data = n;
 713                       check (abt_insert (&abt, &elements[n].node) == NULL);
 714                     }
 715                   check_abt (&abt, values, cnt);
 716
 717                   /* Change value i to j. */
 718                   elements[i].data = j;
 719                   for (k = 0; k < cnt; k++)
 720                     changed_values[k] = k;
 721                   changed_retval = abt_changed (&abt, &elements[i].node);
 722                   if (i != j && j < cnt)
 723                     {
 724                       /* Will cause duplicate. */
 725                       check (changed_retval == &elements[j].node);
 726                       changed_values[i] = changed_values[cnt - 1];
 727                       check_abt (&abt, changed_values, cnt - 1);
 728                     }
 729                   else
 730                     {
 731                       /* Succeeds. */
 732                       check (changed_retval == NULL);
 733                       changed_values[i] = j;
 734                       check_abt (&abt, changed_values, cnt);
 735                     }
 736                 }
 737             }
 738         }
 739       check (permutation_cnt == factorial (cnt));
 740
 741       free (values);
 742       free (changed_values);
 743       free (elements);
 744     }
 745 }
 746 \f
 747 /* Main program. */
 748
 749 struct test
 750   {
 751     const char *name;
 752     const char *description;
 753     void (*function) (void);
 754   };
 755
 756 static const struct test tests[] =
 757   {
 758     {
 759       "insert-any-remove-any",
 760       "insert any order, delete any order",
 761       test_insert_any_remove_any
 762     },
 763     {
 764       "insert-any-remove-same",
 765       "insert any order, delete same order",
 766       test_insert_any_remove_same
 767     },
 768     {
 769       "insert-any-remove-reverse",
 770       "insert any order, delete reverse order",
 771       test_insert_any_remove_reverse
 772     },
 773     {
 774       "random-sequence",
 775       "insert and delete in random sequence",
 776       test_random_sequence
 777     },
 778     {
 779       "insert-ordered",
 780       "insert in ascending order",
 781       test_insert_ordered
 782     },
 783     {
 784       "moved",
 785       "move elements around in memory",
 786       test_moved
 787     },
 788     {
 789       "changed",
 790       "change key data in nodes",
 791       test_changed
 792     }
 793   };
 794
 795 enum { N_TESTS = sizeof tests / sizeof *tests };
 796
 797 int
 798 main (int argc, char *argv[])
 799 {
 800   int i;
 801
 802   if (argc != 2)
 803     {
 804       fprintf (stderr, "exactly one argument required; use --help for help\n");
 805       return EXIT_FAILURE;
 806     }
 807   else if (!strcmp (argv[1], "--help"))
 808     {
 809       printf ("%s: test augmented binary tree\n"
 810               "usage: %s TEST-NAME\n"
 811               "where TEST-NAME is one of the following:\n",
 812               argv[0], argv[0]);
 813       for (i = 0; i < N_TESTS; i++)
 814         printf ("  %s\n    %s\n", tests[i].name, tests[i].description);
 815       return 0;
 816     }
 817   else
 818     {
 819       for (i = 0; i < N_TESTS; i++)
 820         if (!strcmp (argv[1], tests[i].name))
 821           {
 822             tests[i].function ();
 823             return 0;
 824           }
 825
 826       fprintf (stderr, "unknown test %s; use --help for help\n", argv[1]);
 827       return EXIT_FAILURE;
 828     }
 829 }