tests/libpspp/abt-test.c

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