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

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