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

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