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 <stdbool.h>
  30 #include <stddef.h>
  31 #include <stdio.h>
  32 #include <stdlib.h>
  33 #include <string.h>
  34
  35 #include <libpspp/compiler.h>
  36 \f
  37 /* Exit with a failure code.
  38    (Place a breakpoint on this function while debugging.) */
  39 static void
  40 check_die (void)
  41 {
  42   exit (EXIT_FAILURE);
  43 }
  44
  45 /* If OK is not true, prints a message about failure on the
  46    current source file and the given LINE and terminates. */
  47 static void
  48 check_func (bool ok, int line)
  49 {
  50   if (!ok)
  51     {
  52       fprintf (stderr, "%s:%d: check failed\n", __FILE__, line);
  53       check_die ();
  54     }
  55 }
  56
  57 /* Verifies that EXPR evaluates to true.
  58    If not, prints a message citing the calling line number and
  59    terminates. */
  60 #define check(EXPR) check_func ((EXPR), __LINE__)
  61
  62 /* Prints a message about memory exhaustion and exits with a
  63    failure code. */
  64 static void
  65 xalloc_die (void)
  66 {
  67   printf ("virtual memory exhausted\n");
  68   exit (EXIT_FAILURE);
  69 }
  70
  71 /* Allocates and returns N bytes of memory. */
  72 static void *
  73 xmalloc (size_t n)
  74 {
  75   if (n != 0)
  76     {
  77       void *p = malloc (n);
  78       if (p == NULL)
  79         xalloc_die ();
  80
  81       return p;
  82     }
  83   else
  84     return NULL;
  85 }
  86
  87 static void *
  88 xmemdup (const void *p, size_t n)
  89 {
  90   void *q = xmalloc (n);
  91   memcpy (q, p, n);
  92   return q;
  93 }
  94
  95 /* Allocates and returns N * M bytes of memory. */
  96 static void *
  97 xnmalloc (size_t n, size_t m)
  98 {
  99   if ((size_t) -1 / m <= n)
 100     xalloc_die ();
 101   return xmalloc (n * m);
 102 }
 103 \f
 104 /* Node type and support routines. */
 105
 106 /* Test data element. */
 107 struct element
 108   {
 109     struct abt_node node;       /* Embedded binary tree element. */
 110     int data;                   /* Primary value. */
 111     int count;                  /* Number of nodes in subtree,
 112                                    including this node. */
 113   };
 114
 115 static int aux_data;
 116
 117 /* Returns the `struct element' that NODE is embedded within. */
 118 static struct element *
 119 abt_node_to_element (const struct abt_node *node)
 120 {
 121   return ABT_DATA (node, struct element, node);
 122 }
 123
 124 /* Compares the `x' values in A and B and returns a strcmp-type
 125    return value.  Verifies that AUX points to aux_data. */
 126 static int
 127 compare_elements (const struct abt_node *a_, const struct abt_node *b_,
 128                   const void *aux)
 129 {
 130   const struct element *a = abt_node_to_element (a_);
 131   const struct element *b = abt_node_to_element (b_);
 132
 133   check (aux == &aux_data);
 134   return a->data < b->data ? -1 : a->data > b->data;
 135 }
 136
 137 /* Recalculates the count for NODE's subtree by adding up the
 138    counts for its LEFT and RIGHT child subtrees. */
 139 static void
 140 reaugment_elements (struct abt_node *node_, const void *aux)
 141 {
 142   struct element *node = abt_node_to_element (node_);
 143
 144   check (aux == &aux_data);
 145
 146   node->count = 1;
 147   if (node->node.down[0] != NULL)
 148     node->count += abt_node_to_element (node->node.down[0])->count;
 149   if (node->node.down[1] != NULL)
 150     node->count += abt_node_to_element (node->node.down[1])->count;
 151 }
 152
 153 /* Compares A and B and returns a strcmp-type return value. */
 154 static int
 155 compare_ints_noaux (const void *a_, const void *b_)
 156 {
 157   const int *a = a_;
 158   const int *b = b_;
 159
 160   return *a < *b ? -1 : *a > *b;
 161 }
 162
 163 /* Swaps *A and *B. */
 164 static void
 165 swap (int *a, int *b)
 166 {
 167   int t = *a;
 168   *a = *b;
 169   *b = t;
 170 }
 171
 172 /* Reverses the order of the CNT integers starting at VALUES. */
 173 static void
 174 reverse (int *values, size_t cnt)
 175 {
 176   size_t i = 0;
 177   size_t j = cnt;
 178
 179   while (j > i)
 180     swap (&values[i++], &values[--j]);
 181 }
 182
 183 /* Arranges the CNT elements in VALUES into the lexicographically
 184    next greater permutation.  Returns true if successful.
 185    If VALUES is already the lexicographically greatest
 186    permutation of its elements (i.e. ordered from greatest to
 187    smallest), arranges them into the lexicographically least
 188    permutation (i.e. ordered from smallest to largest) and
 189    returns false. */
 190 static bool
 191 next_permutation (int *values, size_t cnt)
 192 {
 193   if (cnt > 0)
 194     {
 195       size_t i = cnt - 1;
 196       while (i != 0)
 197         {
 198           i--;
 199           if (values[i] < values[i + 1])
 200             {
 201               size_t j;
 202               for (j = cnt - 1; values[i] >= values[j]; j--)
 203                 continue;
 204               swap (values + i, values + j);
 205               reverse (values + (i + 1), cnt - (i + 1));
 206               return true;
 207             }
 208         }
 209
 210       reverse (values, cnt);
 211     }
 212
 213   return false;
 214 }
 215
 216 /* Returns N!. */
 217 static unsigned int
 218 factorial (unsigned int n)
 219 {
 220   unsigned int value = 1;
 221   while (n > 1)
 222     value *= n--;
 223   return value;
 224 }
 225
 226 /* Randomly shuffles the CNT elements in ARRAY, each of which is
 227    SIZE bytes in size. */
 228 static void
 229 random_shuffle (void *array_, size_t cnt, size_t size)
 230 {
 231   char *array = array_;
 232   char *tmp = xmalloc (size);
 233   size_t i;
 234
 235   for (i = 0; i < cnt; i++)
 236     {
 237       size_t j = rand () % (cnt - i) + i;
 238       if (i != j)
 239         {
 240           memcpy (tmp, array + j * size, size);
 241           memcpy (array + j * size, array + i * size, size);
 242           memcpy (array + i * size, tmp, size);
 243         }
 244     }
 245
 246   free (tmp);
 247 }
 248
 249 /* Finds and returns the element in ABT that is in the given
 250    0-based POSITION in in-order. */
 251 static struct element *
 252 find_by_position (struct abt *abt, int position)
 253 {
 254   struct abt_node *p;
 255   for (p = abt->root; p != NULL;)
 256     {
 257       int p_pos = p->down[0] ? abt_node_to_element (p->down[0])->count : 0;
 258       if (position == p_pos)
 259         return abt_node_to_element (p);
 260       else if (position < p_pos)
 261         p = p->down[0];
 262       else
 263         {
 264           p = p->down[1];
 265           position -= p_pos + 1;
 266         }
 267     }
 268   return NULL;
 269 }
 270
 271 /* Checks that all the augmentations are correct in the subtree
 272    rooted at P.  Returns the number of nodes in the subtree. */
 273 static int
 274 check_augmentations (struct abt_node *p_)
 275 {
 276   if (p_ == NULL)
 277     return 0;
 278   else
 279     {
 280       struct element *p = abt_node_to_element (p_);
 281       int left_count = check_augmentations (p->node.down[0]);
 282       int right_count = check_augmentations (p->node.down[1]);
 283       int total = left_count + right_count + 1;
 284       check (p->count == total);
 285       return total;
 286     }
 287 }
 288
 289 /* Check that the levels are correct in the subtree rooted at P. */
 290 static void
 291 check_levels (struct abt_node *p)
 292 {
 293   if (p != NULL)
 294     {
 295       int i, j;
 296
 297       check_levels (p->down[0]);
 298       check_levels (p->down[1]);
 299
 300       check (p->level >= 1);
 301       if (p->level > 1)
 302         {
 303           struct abt_node *q = p->down[1];
 304           check (q != NULL);
 305           check (q->level == p->level || q->level == p->level - 1);
 306         }
 307
 308       for (i = 0; i < 2; i++)
 309         if (p->down[i] != NULL)
 310           for (j = 0; j < 2; j++)
 311             if (p->down[i]->down[j] != NULL)
 312               check (p->down[i]->down[j]->level < p->level);
 313     }
 314 }
 315
 316 /* Checks that ABT contains the CNT ints in DATA, that its
 317    structure is correct, and that certain operations on ABT
 318    produce the expected results. */
 319 static void
 320 check_abt (struct abt *abt, const int data[], size_t cnt)
 321 {
 322   struct element e;
 323   size_t i;
 324   int *order;
 325
 326   order = xmemdup (data, cnt * sizeof *data);
 327   qsort (order, cnt, sizeof *order, compare_ints_noaux);
 328
 329   if (abt->compare != NULL)
 330     {
 331       for (i = 0; i < cnt; i++)
 332         {
 333           struct abt_node *p;
 334
 335           e.data = data[i];
 336           if (rand () % 2)
 337             p = abt_find (abt, &e.node);
 338           else
 339             p = abt_insert (abt, &e.node);
 340           check (p != NULL);
 341           check (p != &e.node);
 342           check (abt_node_to_element (p)->data == data[i]);
 343         }
 344
 345       e.data = -1;
 346       check (abt_find (abt, &e.node) == NULL);
 347     }
 348
 349   check_levels (abt->root);
 350   check_augmentations (abt->root);
 351   for (i = 0; i < cnt; i++)
 352     check (find_by_position (abt, i)->data == order[i]);
 353
 354   if (cnt == 0)
 355     {
 356       check (abt_first (abt) == NULL);
 357       check (abt_last (abt) == NULL);
 358       check (abt_next (abt, NULL) == NULL);
 359       check (abt_prev (abt, NULL) == NULL);
 360     }
 361   else
 362     {
 363       struct abt_node *p;
 364
 365       for (p = abt_first (abt), i = 0; i < cnt; p = abt_next (abt, p), i++)
 366         check (abt_node_to_element (p)->data == order[i]);
 367       check (p == NULL);
 368
 369       for (p = abt_last (abt), i = 0; i < cnt; p = abt_prev (abt, p), i++)
 370         check (abt_node_to_element (p)->data == order[cnt - i - 1]);
 371       check (p == NULL);
 372     }
 373   check (abt_is_empty (abt) == (cnt == 0));
 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 }