chiark - git - mdw - wordchain/blob - chain.c

   1 #include <assert.h>
   2 #include <stdarg.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6
   7 #define XYLA_AVL 1
   8 #define XYLA_RB 2
   9 #define XYLA_SPLAY 3
  10 #define XYLA_TREAP 4
  11 #define QPTRIE_QP 5
  12 #define QPTRIE_FN 6
  13 #define SGT_TREE234 7
  14 #define LIBAVL_AVL 8
  15 #define LIBAVL_BST 9
  16 #define LIBAVL_RB 10
  17 #define LIBAVL_PAVL 11
  18 #define LIBAVL_PBST 12
  19 #define LIBAVL_PRB 13
  20 #define LIBAVL_RTAVL 14
  21 #define LIBAVL_RTBST 15
  22 #define LIBAVL_RTRB 16
  23 #define LIBAVL_TAVL 17
  24 #define LIBAVL_TBST 18
  25 #define LIBAVL_TRB 19
  26 #define MLIB_SYM 20
  27
  28 #define QPITER_FANF 1
  29 #define QPITER_MDW 2
  30 #define QPITER_LIST 3
  31
  32 #if !TREE
  33 #  error "`TREE' not defined or bungled constant setting"
  34 #elif TREE == XYLA_AVL
  35 #  include "avl.h"
  36 #  define USE_XYLA 1
  37 #  define WANT_HEIGHT 1
  38 #  define TREE__NAME(name) XYLA_AVL_##name
  39 #  define tree__name(name) xyla_avl_##name
  40 #  define T avl
  41 #elif TREE == XYLA_RB
  42 #  include "rb.h"
  43 #  define USE_XYLA 1
  44 #  define WANT_HEIGHT 1
  45 #  define TREE__NAME(name) XYLA_RB_##name
  46 #  define tree__name(name) xyla_rb_##name
  47 #  define T rb
  48 #elif TREE == XYLA_SPLAY
  49 #  include "splay.h"
  50 #  define USE_XYLA 1
  51 #  undef WANT_HEIGHT
  52 #  define TREE__NAME(name) XYLA_SPLAY_##name
  53 #  define tree__name(name) xyla_splay_##name
  54 #  define T spl
  55 #elif TREE == XYLA_TREAP
  56 #  include "treap.h"
  57 #  define USE_XYLA 1
  58 #  undef WANT_HEIGHT
  59 #  define TREE__NAME(name) XYLA_TREAP_##name
  60 #  define tree__name(name) xyla_treap_##name
  61 #  define T trp
  62 #elif TREE == QPTRIE_QP
  63 #  include <stdbool.h>
  64 #  include <stdint.h>
  65 #  include "Tbl.h"
  66 #  include "qp.h"
  67 #  define USE_QPTRIE 1
  68 #elif TREE == QPTRIE_FN
  69 #  include <stdbool.h>
  70 #  include <stdint.h>
  71 #  include "Tbl.h"
  72 #  include "fn.h"
  73 #  define USE_QPTRIE 1
  74 #elif TREE == SGT_TREE234
  75 #  include "tree234.h"
  76 #elif TREE == LIBAVL_AVL
  77 #  include "avl.h"
  78 #  define USE_LIBAVL 1
  79 #  define tree__name(name) avl_##name
  80 #elif TREE == LIBAVL_BST
  81 #  include "bst.h"
  82 #  define USE_LIBAVL 1
  83 #  define tree__name(name) bst_##name
  84 #elif TREE == LIBAVL_RB
  85 #  include "rb.h"
  86 #  define USE_LIBAVL 1
  87 #  define tree__name(name) rb_##name
  88 #elif TREE == LIBAVL_PAVL
  89 #  include "pavl.h"
  90 #  define USE_LIBAVL 1
  91 #  define tree__name(name) pavl_##name
  92 #elif TREE == LIBAVL_PBST
  93 #  include "pbst.h"
  94 #  define USE_LIBAVL 1
  95 #  define tree__name(name) pbst_##name
  96 #elif TREE == LIBAVL_PRB
  97 #  include "prb.h"
  98 #  define USE_LIBAVL 1
  99 #  define tree__name(name) prb_##name
 100 #elif TREE == LIBAVL_RTAVL
 101 #  include "rtavl.h"
 102 #  define USE_LIBAVL 1
 103 #  define tree__name(name) rtavl_##name
 104 #elif TREE == LIBAVL_RTBST
 105 #  include "rtbst.h"
 106 #  define USE_LIBAVL 1
 107 #  define tree__name(name) rtbst_##name
 108 #elif TREE == LIBAVL_RTRB
 109 #  include "rtrb.h"
 110 #  define USE_LIBAVL 1
 111 #  define tree__name(name) rtrb_##name
 112 #elif TREE == LIBAVL_TAVL
 113 #  include "tavl.h"
 114 #  define USE_LIBAVL 1
 115 #  define tree__name(name) tavl_##name
 116 #elif TREE == LIBAVL_BST
 117 #  include "tbst.h"
 118 #  define USE_LIBAVL 1
 119 #  define tree__name(name) tbst_##name
 120 #elif TREE == LIBAVL_TRB
 121 #  include "trb.h"
 122 #  define USE_LIBAVL 1
 123 #  define tree__name(name) trb_##name
 124 #elif TREE == MLIB_SYM
 125 #  include <unistd.h>
 126 #  include <mLib/sym.h>
 127 #  include <mLib/unihash.h>
 128 #else
 129 #  error "unknown `TREE' value"
 130 #endif
 131
 132 #if USE_XYLA
 133 #  define NODE tree__name(node)
 134 #  define PATH tree__name(path)
 135 #  define ITER tree__name(iter)
 136 #  define TREE_NODEPFX TREE__NAME(NODEPFX)
 137 #  define TREE_NODEUSFX TREE__NAME(NODEUSFX)
 138 #  define TREE_CHECK tree__name(check)
 139 #  define TREE_LOOKUP tree__name(lookup)
 140 #  define TREE_PROBE tree__name(probe)
 141 #  define TREE_INITITER tree__name(inititer)
 142 #  define TREE_NEXT tree__name(next)
 143 #  define TREE_INSERT tree__name(insert)
 144 #  if WANT_HEIGHT
 145 #    define H(x) x
 146 #    define HARG(x) , x
 147 #  else
 148 #    define H(x)
 149 #    define HARG(x)
 150 #  endif
 151 #elif USE_LIBAVL
 152 #  define TABLE tree__name(table)
 153 #  define TRAVERSER tree__name(traverser)
 154 #  define TREE_CREATE tree__name(create)
 155 #  define TREE_DESTROY tree__name(destroy)
 156 #  define TREE_PROBE tree__name(probe)
 157 #  define TREE_FIND tree__name(find)
 158 #  define TREE_T_INIT tree__name(t_init)
 159 #  define TREE_T_NEXT tree__name(t_next)
 160 #endif
 161
 162 #if USE_QPTRIE
 163 #  if !QPTRIE_ITER
 164 #    error "`QPTRIE_ITER' not defined or bungled constant setting"
 165 #  elif QPTRIE_ITER == QPITER_FANF
 166 #  elif QPTRIE_ITER == QPITER_MDW
 167 #  elif QPTRIE_ITER == QPITER_LIST
 168 #  else
 169 #    error "unknown `QPTRIE_ITER' value"
 170 #  endif
 171 #endif
 172
 173 struct word { const char *p; size_t n; } word;
 174
 175 struct node {
 176 #if USE_XYLA
 177   TREE_NODEPFX;
 178 #elif TREE == MLIB_SYM
 179   struct sym_base _s;
 180 #endif
 181 #if TREE == MLIB_SYM || (USE_QPTRIE && QPTRIE_ITER == QPITER_LIST)
 182   struct node *next;
 183 #endif
 184 #if TREE != MLIB_SYM
 185   struct word w;
 186 #endif
 187   struct node *down, *right, *up;
 188   int len;
 189 };
 190
 191 #define WORDMAX 64
 192
 193 static void bail(const char *msg, ...)
 194 {
 195   va_list ap;
 196   long pos;
 197
 198   va_start(ap, msg); vfprintf(stderr, msg, ap); va_end(ap);
 199   pos = ftell(stdin);
 200   if (pos >= 0) fprintf(stderr, " (input pos = %ld)", pos);
 201   fputc('\n', stderr);
 202   exit(2);
 203 }
 204
 205 #if USE_XYLA || TREE == SGT_TREE234 || USE_LIBAVL
 206
 207 static int compare_words(const struct word *a, const struct word *b)
 208 {
 209   size_t alen = a->n, blen = b->n;
 210   int ord;
 211
 212   ord = memcmp(a->p, b->p, alen <= blen ? alen : blen);
 213   if (!ord) ord = alen < blen ? -1 : alen > blen ? +1 : 0;
 214   return (ord);
 215 }
 216
 217 #endif
 218
 219 #if USE_XYLA
 220
 221 union nodeu { struct node node; TREE_NODEUSFX; };
 222
 223 static int word_nav(struct xyla_bt_nodecls *cls,
 224                     const struct xyla_bt_node *nn, void *arg)
 225 {
 226   const struct word *k = arg;
 227   const struct node *node = (struct node *)nn;
 228
 229   return (compare_words(k, &node->w));
 230 }
 231
 232 #  define DECLS                                                         \
 233         struct xyla_bt_node *root = 0;                                  \
 234         union nodeu *nodeu;                                             \
 235         struct PATH path;                                               \
 236         struct ITER it
 237
 238 #  define INIT do ; while (0)
 239
 240 #  if TREE == XYLA_TREAP
 241 #    define EXTRA_NODE_SETUP do { node->trp.wt = rand(); } while (0)
 242 #  endif
 243 #  ifndef EXTRA_NODE_SETUP
 244 #    define EXTRA_NODE_SETUP do ; while (0)
 245 #  endif
 246 #  define INSERT do {                                                   \
 247         if (TREE_PROBE(0, &root, word_nav, &word, &path)) {             \
 248           fprintf(stderr, ";; duplicate `%s'\n", buf);                  \
 249           free(node); node = 0;                                         \
 250         } else {                                                        \
 251           EXTRA_NODE_SETUP;                                             \
 252           nodeu = (union nodeu *)node;                                  \
 253           TREE_INSERT(0, &path, &nodeu->T);                             \
 254         }                                                               \
 255    } while (0)
 256
 257 #  define ITERATE                                                       \
 258         for (TREE_INITITER(root, &it); node = TREE_NEXT(&it), node; )
 259
 260 #  if TREE == XYLA_SPLAY
 261 #    define FOCUS do { xyla_splay_splay(0, &path); } while (0)
 262 #  else
 263 #    define FOCUS do ; while (0)
 264 #  endif
 265
 266 #  define LOOKUP TREE_LOOKUP(0, &root, word_nav, &word)
 267
 268 #  define FREE do {                                                     \
 269         while (node = xyla_bt_severfirst(&root), node) free(node);      \
 270    } while (0)
 271
 272 #  ifndef WANT_CHECKS
 273 #    define CHECK do ; while (0)
 274 #  else
 275
 276 static const void *word_key(struct xyla_bt_nodecls *cls,
 277                             const struct xyla_bt_node *nn)
 278   { struct node *node = (struct node *)nn; return (&node->w); }
 279
 280 static void word_ident(struct xyla_bt_nodecls *cls,
 281                        const struct xyla_bt_node *nn, FILE *fp)
 282   { struct node *node = (struct node *)nn; fprintf(fp, "`%s'", node->w.p); }
 283
 284 static const struct xyla_bt_chkops word_ops = {
 285   { sizeof(word_ops), 0 },
 286   { word_nav, word_key },
 287   { xyla_bt_chkorder, sizeof(struct xyla_bt_ordinfo), word_ident }
 288 };
 289 struct xyla_bt_nodecls word_cls = { &word_ops.node };
 290
 291 #    define CHECK do {                                                  \
 292         if (TREE_CHECK(&word_cls, &root, stderr, 0 HARG(-1), 0))        \
 293           bail("check failed");                                         \
 294      } while (0)
 295 #  endif
 296
 297 #elif USE_QPTRIE
 298
 299 #  if QPTRIE_ITER == QPITER_FANF
 300 #    define my_Tnextl Tnextl
 301 #    define DECL_ITER                                                   \
 302         struct word cur;                                                \
 303         void *v
 304 #    define INSERT_LIST do ; while (0)
 305 #  elif QPTRIE_ITER == QPITER_MDW
 306 #    define DECL_ITER                                                   \
 307         struct word cur;                                                \
 308         void *v
 309 #    define INSERT_LIST do ; while (0)
 310
 311 #    if TREE == QPTRIE_QP
 312
 313 static bool my_Tnextl(Tbl *tbl, const char **k_inout, size_t *sz_inout,
 314                       void **val_out)
 315 {
 316   const char *k = *k_inout;
 317   size_t sz = *sz_inout;
 318   Trie *t, *resume;
 319   unsigned off, max;
 320   Tbitmap b;
 321
 322   if (!tbl)
 323     return (false);
 324   else {
 325     t = &tbl->root;
 326     if (k) {
 327       resume = 0;
 328       while (isbranch(t)) {
 329         __builtin_prefetch(t->branch.twigs);
 330         b = twigbit(t, k, sz);
 331         TWIGOFFMAX(off, max, t, b);
 332         if (!hastwig(t, b)) return (false);
 333         t = twig(t, off);
 334         if (off + 1 < max) resume = t + 1;
 335       }
 336       /* if (strcmp(k, t->leaf.key) != 0) return (false); */
 337       t = resume; if (!t) return (false);
 338     }
 339   }
 340   while (isbranch(t)) t = twig(t, 0);
 341   *k_inout = k = t->leaf.key; *sz_inout = strlen(k); *val_out = t->leaf.val;
 342   return (true);
 343 }
 344
 345 #    elif TREE == QPTRIE_FN
 346
 347 static bool my_Tnextl(Tbl *t, const char **k_inout, size_t *sz_inout,
 348                       void **val_out)
 349 {
 350   const char *k = *k_inout;
 351   size_t sz = *sz_inout;
 352   Trie *resume;
 353   unsigned off, max;
 354   Tbitmap b;
 355   Tindex i;
 356
 357   if (!t)
 358     return (false);
 359   else if (k) {
 360     resume = 0;
 361     while (isbranch(t)) {
 362       __builtin_prefetch(t->ptr);
 363       i = t->index; b = twigbit(i, k, sz);
 364       TWIGOFFMAX(off, max, i, b);
 365       if (!hastwig(i, b)) return (false);
 366       t = Tbranch_twigs(t) + off;
 367       if (off + 1 < max) resume = t + 1;
 368     }
 369     /* if (strcmp(k, Tleaf_key(t)) != 0) return (false); */
 370     t = resume; if (!t) return (false);
 371   }
 372   while (isbranch(t)) t = Tbranch_twigs(t);
 373   *k_inout = k = Tleaf_key(t); *sz_inout = strlen(k);
 374   *val_out = Tleaf_val(t);
 375   return (true);
 376 }
 377
 378 #    else
 379 #      error "no mdw `Tnextl' for this QP trie variant"
 380 #    endif
 381 #  elif QPTRIE_ITER == QPITER_LIST
 382 #    define DECL_ITER                                                   \
 383         struct node *all = 0, **all_tail = &all
 384 #    define INSERT_LIST do {                                            \
 385         node->next = 0; *all_tail = node; all_tail = &node->next;       \
 386      } while (0)
 387 #  endif
 388
 389 #  define DECLS                                                         \
 390         Tbl *tbl = 0;                                                   \
 391         DECL_ITER
 392
 393 #  define INIT do ; while (0)
 394
 395 #  define INSERT do {                                                   \
 396         tbl = Tsetl(tbl, node->w.p, node->w.n, node);                   \
 397         INSERT_LIST;                                                    \
 398    } while (0)
 399
 400 #  if QPTRIE_ITER == QPITER_LIST
 401 #    define ITERATE                                                     \
 402         for (next = all; node = next, node; next = next->next)
 403 #  else
 404 #    define ITERATE                                                     \
 405         for (cur.p = 0, cur.n = 0;                                      \
 406                my_Tnextl(tbl, &cur.p, &cur.n, &v) ? node = v, 1 : 0; )
 407 #endif
 408
 409 #  define FOCUS do ; while (0)
 410
 411 #  define GETPREFIX do {                                                \
 412         word.n = node->w.n - 1; assert(word.n < WORDMAX);               \
 413         memcpy(buf, node->w.p, word.n); buf[word.n] = 0;                \
 414    } while (0)
 415
 416 #  define LOOKUP Tgetl(tbl, buf, word.n)
 417
 418 #  if QPTRIE_ITER == QPITER_LIST
 419 #    define FREE do {                                                   \
 420         for (node = all; node; node = next) {                           \
 421           tbl = Tsetl(tbl, node->w.p, node->w.n, 0);                    \
 422           next = node->next; free(node);                                \
 423         }                                                               \
 424         assert(!tbl);                                                   \
 425      } while (0)
 426 #  else
 427 #    define FREE do {                                                   \
 428         while (tbl) {                                                   \
 429           cur.p = 0; cur.n = 0; my_Tnextl(tbl, &cur.p, &cur.n, &v);     \
 430           tbl = Tsetl(tbl, cur.p, cur.n, 0); free(v);                   \
 431         }                                                               \
 432      } while (0)
 433 #  endif
 434
 435 #  define CHECK do ; while (0)
 436
 437 #elif TREE == SGT_TREE234
 438
 439 static int node_cmp(void *a, void *b)
 440   { const struct word *wa = a, *wb = b; return (compare_words(wa, wb)); }
 441
 442 #  define DECLS                                                         \
 443         tree234 *root;                                                  \
 444         int i
 445
 446 #  define INIT do { root = newtree234(node_cmp); } while (0)
 447
 448 #  define INSERT do {                                                   \
 449         if (add234(root, node) != node) {                               \
 450           fprintf(stderr, ";; duplicate `%s'\n", buf);                  \
 451           free(node); node = 0;                                         \
 452         }                                                               \
 453    } while (0)
 454
 455 #  define ITERATE for (i = 0; node = index234(root, i), node; i++)
 456
 457 #  define FOCUS do ; while (0)
 458
 459 #  define LOOKUP find234(root, &word, 0)
 460
 461 #  define FREE do {                                                     \
 462         while (node = delpos234(root, 0), node) free(node);             \
 463         freetree234(root);                                              \
 464    } while (0)
 465
 466 #  define CHECK do ; while (0)
 467
 468 #elif USE_LIBAVL
 469
 470 static int node_cmp(const void *a, const void *b, void *arg)
 471   { const struct word *wa = a, *wb = b; return (compare_words(wa, wb)); }
 472
 473 static void free_node(void *n, void *arg) { free(n); }
 474
 475 #  define DECLS                                                         \
 476         struct TABLE *tab;                                              \
 477         struct TRAVERSER it;                                            \
 478         void **p
 479
 480 #  define INIT do {                                                     \
 481         tab = TREE_CREATE(node_cmp, 0, 0);                              \
 482         if (!tab) bail("out of memory");                                \
 483    } while (0)
 484
 485 #  define INSERT do {                                                   \
 486         p = TREE_PROBE(tab, node); if (!p) bail("out of memory");       \
 487         if (*p != node) {                                               \
 488           fprintf(stderr, ";; duplicate `%s'\n", buf);                  \
 489           free(node); node = 0;                                         \
 490         }                                                               \
 491    } while (0)
 492
 493 #  define ITERATE                                                       \
 494         for (TREE_T_INIT(&it, tab); node = TREE_T_NEXT(&it), node; )
 495
 496 #  define FOCUS do ; while (0)
 497
 498 #  define LOOKUP TREE_FIND(tab, &word)
 499
 500 #  define FREE do { TREE_DESTROY(tab, free_node); } while (0)
 501
 502 #  define CHECK do ; while (0)
 503
 504 #elif TREE == MLIB_SYM
 505
 506 #  define DECLS                                                         \
 507         sym_table tab;                                                  \
 508         struct node *all = 0, **all_tail = &all;                        \
 509         unsigned foundp
 510
 511 #  define INIT do {                                                     \
 512         unihash_setkey(&unihash_global, getpid());                      \
 513         sym_create(&tab);                                               \
 514    } while (0)
 515
 516 #  define PREPNODE do ; while (0)
 517
 518 #  define INSERT do {                                                   \
 519         node = sym_find(&tab, buf, word.n, sizeof(*node), &foundp);     \
 520         if (!foundp) {                                                  \
 521           node->next = 0; *all_tail = node; all_tail = &node->next;     \
 522         } else {                                                        \
 523           fprintf(stderr, ";; duplicate `%s'\n", buf);                  \
 524           free(node); node = 0;                                         \
 525         }                                                               \
 526    } while (0)
 527
 528 #  define ITERATE for (next = all; node = next, node; next = next->next)
 529
 530 #  define FOCUS do ; while (0)
 531
 532 #  define WORDPTR(node) (SYM_NAME(node))
 533 #  define WORDLEN(node) (SYM_LEN(node))
 534
 535 #  define LOOKUP sym_find(&tab, word.p, word.n, 0, 0)
 536
 537 #  define FREE do { sym_destroy(&tab); } while (0)
 538
 539 #  define CHECK do ; while (0)
 540
 541 #endif
 542
 543 #ifndef PREPNODE
 544 #  define PREPNODE do {                                                 \
 545         node = malloc(sizeof(*node) + word.n + 1);                      \
 546           if (!node) bail("out of memory");                             \
 547         node->w.p = (char *)(node + 1);                                 \
 548         memcpy(node + 1, buf, word.n + 1); node->w.n = word.n;          \
 549    } while (0)
 550 #endif
 551
 552 #ifndef WORDPTR
 553 #  define WORDPTR(node) ((node)->w.p)
 554 #endif
 555
 556 #ifndef WORDLEN
 557 #  define WORDLEN(node) ((node)->w.n)
 558 #endif
 559
 560 #ifndef GETPREFIX
 561 #  define GETPREFIX do {                                                \
 562         word.p = WORDPTR(node); word.n = WORDLEN(node) - 1;             \
 563    } while (0)
 564
 565 #endif
 566
 567 static void print_chain(struct node *node)
 568 {
 569   if (!node->right) {
 570     fputs(WORDPTR(node), stdout);
 571     if (node->down) { putchar(' '); print_chain(node->down); }
 572   } else {
 573     fputs("{ ", stdout);
 574     for (;;) {
 575       fputs(WORDPTR(node), stdout);
 576       if (node->down) { putchar(' '); print_chain(node->down); }
 577       node = node->right; if (!node) break;
 578       fputs(" | ", stdout);
 579     }
 580     fputs(" }", stdout);
 581   }
 582 }
 583
 584 int main(void)
 585 {
 586   DECLS;
 587   struct node *node, *parent, *winners, **winners_tail, *next;
 588   struct word word;
 589   char buf[WORDMAX];
 590   int ch, max, nlen, plen;
 591
 592   INIT;
 593   word.p = buf;
 594   for (;;) {
 595     if (!fgets(buf, WORDMAX, stdin)) break;
 596     word.n = strlen(buf); assert(word.n);
 597     if (buf[word.n - 1] == '\n') buf[--word.n] = 0;
 598     else if (word.n == WORDMAX - 1) bail("word too long");
 599     else if (ch = getchar(), ch != EOF) bail("short read, found `%c'", ch);
 600
 601     PREPNODE; INSERT;
 602     if (node) { node->up = node->down = node->right = 0; node->len = 1; }
 603   }
 604
 605   CHECK;
 606
 607   max = 0; winners_tail = &winners;
 608
 609   ITERATE {
 610     FOCUS;
 611     /* fprintf(stderr, ";; ponder `%.*s'\n", WORDLEN(node), WORDPTR(node)); */
 612     if (WORDLEN(node) <= 1)
 613       continue;
 614     else {
 615       GETPREFIX;
 616       /* fprintf(stderr, ";; search `%.*s'\n", word.n, word.p); */
 617       parent = LOOKUP; if (!parent) continue;
 618     }
 619     node->up = parent; nlen = node->len;
 620     for (;;) {
 621       if (!parent) {
 622         if (nlen >= max) {
 623           if (nlen > max)
 624             { max = nlen; *winners_tail = 0; winners_tail = &winners; }
 625           *winners_tail = node; winners_tail = &node->right;
 626         }
 627         break;
 628       }
 629       plen = parent->len; nlen++;
 630       if (plen > nlen)
 631         break;
 632       else if (plen == nlen) {
 633         node->right = parent->down; parent->down = node;
 634         break;
 635       } else {
 636         parent->down = node; node->right = 0;
 637         parent->len = nlen;
 638         node = parent; parent = node->up;
 639       }
 640     }
 641   }
 642
 643   for (*winners_tail = 0, node = winners; node; node = next) {
 644     next = node->right; node->right = 0;
 645     print_chain(node); putchar('\n');
 646   }
 647   FREE;
 648   return (0);
 649 }