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 {
 174   const char *p;
 175 #if USE_QPTRIE
 176   size_t n;
 177 #else
 178   unsigned short n;
 179 #endif
 180 } word;
 181
 182 struct node {
 183 #if USE_XYLA
 184   TREE_NODEPFX;
 185 #elif TREE == MLIB_SYM
 186   struct sym_base _s;
 187 # define WORDPTR(node) (SYM_NAME(node))
 188 # define WORDLEN(node) (SYM_LEN(node))
 189 #endif
 190 #if TREE == MLIB_SYM || (USE_QPTRIE && QPTRIE_ITER == QPITER_LIST)
 191   struct node *next;
 192 #endif
 193 #if TREE != MLIB_SYM
 194   struct word w;
 195 # define WORDPTR(node) ((node)->w.p)
 196 # define WORDLEN(node) ((node)->w.n)
 197 #endif
 198   struct node *down, *right, *up;
 199   short chlen;
 200 # define CHLEN(node) ((node)->chlen)
 201 };
 202
 203 #define WORDMAX 64
 204
 205 static void bail(const char *msg, ...)
 206 {
 207   va_list ap;
 208   long pos;
 209
 210   va_start(ap, msg); vfprintf(stderr, msg, ap); va_end(ap);
 211   pos = ftell(stdin);
 212   if (pos >= 0) fprintf(stderr, " (input pos = %ld)", pos);
 213   fputc('\n', stderr);
 214   exit(2);
 215 }
 216
 217 #if USE_XYLA || TREE == SGT_TREE234 || USE_LIBAVL
 218
 219 static int compare_words(const char *a, size_t alen,
 220                          const char *b, size_t blen)
 221 {
 222   int ord;
 223
 224   ord = memcmp(a, b, alen <= blen ? alen : blen);
 225   if (!ord) ord = alen < blen ? -1 : alen > blen ? +1 : 0;
 226   return (ord);
 227 }
 228
 229 #endif
 230
 231 #if USE_XYLA
 232
 233 union nodeu { struct node node; TREE_NODEUSFX; };
 234
 235 static int word_nav(struct xyla_bt_nodecls *cls,
 236                     const struct xyla_bt_node *nn, void *arg)
 237 {
 238   const struct word *k = arg;
 239   const struct node *node = (struct node *)nn;
 240
 241   return (compare_words(k->p, k->n, WORDPTR(node), WORDLEN(node)));
 242 }
 243
 244 #  define DECLS                                                         \
 245         struct xyla_bt_node *root = 0;                                  \
 246         union nodeu *nodeu;                                             \
 247         struct PATH path;                                               \
 248         struct ITER it
 249
 250 #  define INIT do ; while (0)
 251
 252 #  if TREE == XYLA_TREAP
 253 #    define EXTRA_NODE_SETUP do { node->trp.wt = rand(); } while (0)
 254 #  endif
 255 #  ifndef EXTRA_NODE_SETUP
 256 #    define EXTRA_NODE_SETUP do ; while (0)
 257 #  endif
 258 #  define INSERT do {                                                   \
 259         if (TREE_PROBE(0, &root, word_nav, &word, &path)) {             \
 260           fprintf(stderr, ";; duplicate `%s'\n", buf);                  \
 261           free(node); node = 0;                                         \
 262         } else {                                                        \
 263           EXTRA_NODE_SETUP;                                             \
 264           nodeu = (union nodeu *)node;                                  \
 265           TREE_INSERT(0, &path, &nodeu->T);                             \
 266         }                                                               \
 267    } while (0)
 268
 269 #  define ITERATE                                                       \
 270         for (TREE_INITITER(root, &it); node = TREE_NEXT(&it), node; )
 271
 272 #  if TREE == XYLA_SPLAY
 273 #    define FOCUS do { xyla_splay_splay(0, &path); } while (0)
 274 #  else
 275 #    define FOCUS do ; while (0)
 276 #  endif
 277
 278 #  define LOOKUP TREE_LOOKUP(0, &root, word_nav, &word)
 279
 280 #  define FREE do {                                                     \
 281         while (node = xyla_bt_severfirst(&root), node) free(node);      \
 282    } while (0)
 283
 284 #  ifndef WANT_CHECKS
 285 #    define CHECK do ; while (0)
 286 #  else
 287
 288 static const void *word_key(struct xyla_bt_nodecls *cls,
 289                             const struct xyla_bt_node *nn)
 290   { struct node *node = (struct node *)nn; return (&node->w); }
 291
 292 static void word_ident(struct xyla_bt_nodecls *cls,
 293                        const struct xyla_bt_node *nn, FILE *fp)
 294   { struct node *node = (struct node *)nn; fprintf(fp, "`%s'", node->w.p); }
 295
 296 static const struct xyla_bt_chkops word_ops = {
 297   { sizeof(word_ops), 0 },
 298   { word_nav, word_key },
 299   { xyla_bt_chkorder, sizeof(struct xyla_bt_ordinfo), word_ident }
 300 };
 301 struct xyla_bt_nodecls word_cls = { &word_ops.node };
 302
 303 #    define CHECK do {                                                  \
 304         if (TREE_CHECK(&word_cls, &root, stderr, 0 HARG(-1), 0))        \
 305           bail("check failed");                                         \
 306      } while (0)
 307 #  endif
 308
 309 #elif USE_QPTRIE
 310
 311 #  if QPTRIE_ITER == QPITER_FANF
 312 #    define my_Tnextl Tnextl
 313 #    define DECL_ITER                                                   \
 314         struct word cur;                                                \
 315         void *v
 316 #    define INSERT_LIST do ; while (0)
 317 #  elif QPTRIE_ITER == QPITER_MDW
 318 #    define DECL_ITER                                                   \
 319         struct word cur;                                                \
 320         void *v
 321 #    define INSERT_LIST do ; while (0)
 322
 323 #    if TREE == QPTRIE_QP
 324
 325 static bool my_Tnextl(Tbl *tbl, const char **k_inout, size_t *sz_inout,
 326                       void **val_out)
 327 {
 328   const char *k = *k_inout;
 329   size_t sz = *sz_inout;
 330   Trie *t, *resume;
 331   unsigned off, max;
 332   Tbitmap b;
 333
 334   if (!tbl)
 335     return (false);
 336   else {
 337     t = &tbl->root;
 338     if (k) {
 339       resume = 0;
 340       while (isbranch(t)) {
 341         __builtin_prefetch(t->branch.twigs);
 342         b = twigbit(t, k, sz);
 343         TWIGOFFMAX(off, max, t, b);
 344         if (!hastwig(t, b)) return (false);
 345         t = twig(t, off);
 346         if (off + 1 < max) resume = t + 1;
 347       }
 348       /* if (strcmp(k, t->leaf.key) != 0) return (false); */
 349       t = resume; if (!t) return (false);
 350     }
 351   }
 352   while (isbranch(t)) t = twig(t, 0);
 353   *k_inout = k = t->leaf.key; *sz_inout = strlen(k); *val_out = t->leaf.val;
 354   return (true);
 355 }
 356
 357 #    elif TREE == QPTRIE_FN
 358
 359 static bool my_Tnextl(Tbl *t, const char **k_inout, size_t *sz_inout,
 360                       void **val_out)
 361 {
 362   const char *k = *k_inout;
 363   size_t sz = *sz_inout;
 364   Trie *resume;
 365   unsigned off, max;
 366   Tbitmap b;
 367   Tindex i;
 368
 369   if (!t)
 370     return (false);
 371   else if (k) {
 372     resume = 0;
 373     while (isbranch(t)) {
 374       __builtin_prefetch(t->ptr);
 375       i = t->index; b = twigbit(i, k, sz);
 376       TWIGOFFMAX(off, max, i, b);
 377       if (!hastwig(i, b)) return (false);
 378       t = Tbranch_twigs(t) + off;
 379       if (off + 1 < max) resume = t + 1;
 380     }
 381     /* if (strcmp(k, Tleaf_key(t)) != 0) return (false); */
 382     t = resume; if (!t) return (false);
 383   }
 384   while (isbranch(t)) t = Tbranch_twigs(t);
 385   *k_inout = k = Tleaf_key(t); *sz_inout = strlen(k);
 386   *val_out = Tleaf_val(t);
 387   return (true);
 388 }
 389
 390 #    else
 391 #      error "no mdw `Tnextl' for this QP trie variant"
 392 #    endif
 393 #  elif QPTRIE_ITER == QPITER_LIST
 394 #    define DECL_ITER                                                   \
 395         struct node *all = 0, **all_tail = &all
 396 #    define INSERT_LIST do {                                            \
 397         node->next = 0; *all_tail = node; all_tail = &node->next;       \
 398      } while (0)
 399 #  endif
 400
 401 #  define DECLS                                                         \
 402         Tbl *tbl = 0;                                                   \
 403         DECL_ITER
 404
 405 #  define INIT do ; while (0)
 406
 407 #  define INSERT do {                                                   \
 408         tbl = Tsetl(tbl, node->w.p, node->w.n, node);                   \
 409         INSERT_LIST;                                                    \
 410    } while (0)
 411
 412 #  if QPTRIE_ITER == QPITER_LIST
 413 #    define ITERATE                                                     \
 414         for (next = all; node = next, node; next = next->next)
 415 #  else
 416 #    define ITERATE                                                     \
 417         for (cur.p = 0, cur.n = 0;                                      \
 418                my_Tnextl(tbl, &cur.p, &cur.n, &v) ? node = v, 1 : 0; )
 419 #endif
 420
 421 #  define FOCUS do ; while (0)
 422
 423 #  define GETPREFIX do {                                                \
 424         word.n = node->w.n - 1; assert(word.n < WORDMAX);               \
 425         memcpy(buf, node->w.p, word.n); buf[word.n] = 0;                \
 426    } while (0)
 427
 428 #  define LOOKUP Tgetl(tbl, buf, word.n)
 429
 430 #  if QPTRIE_ITER == QPITER_LIST
 431 #    define FREE do {                                                   \
 432         for (node = all; node; node = next) {                           \
 433           tbl = Tsetl(tbl, node->w.p, node->w.n, 0);                    \
 434           next = node->next; free(node);                                \
 435         }                                                               \
 436         assert(!tbl);                                                   \
 437      } while (0)
 438 #  else
 439 #    define FREE do {                                                   \
 440         while (tbl) {                                                   \
 441           cur.p = 0; cur.n = 0; my_Tnextl(tbl, &cur.p, &cur.n, &v);     \
 442           tbl = Tsetl(tbl, cur.p, cur.n, 0); free(v);                   \
 443         }                                                               \
 444      } while (0)
 445 #  endif
 446
 447 #  define CHECK do ; while (0)
 448
 449 #elif TREE == SGT_TREE234
 450
 451 static int node_cmp(void *a, void *b)
 452 {
 453   const struct node *na = a, *nb = b;
 454
 455   return (compare_words(WORDPTR(na), WORDLEN(na),
 456                         WORDPTR(nb), WORDLEN(nb)));
 457 }
 458
 459 static int word_cmp(void *k, void *n)
 460 {
 461   const struct word *word = k;
 462   const struct node *node = n;
 463
 464   return (compare_words(word->p, word->n, WORDPTR(node), WORDLEN(node)));
 465 }
 466
 467 #  define DECLS                                                         \
 468         tree234 *root;                                                  \
 469         int i
 470
 471 #  define INIT do { root = newtree234(node_cmp); } while (0)
 472
 473 #  define INSERT do {                                                   \
 474         if (add234(root, node) != node) {                               \
 475           fprintf(stderr, ";; duplicate `%s'\n", buf);                  \
 476           free(node); node = 0;                                         \
 477         }                                                               \
 478    } while (0)
 479
 480 #  define ITERATE for (i = 0; node = index234(root, i), node; i++)
 481
 482 #  define FOCUS do ; while (0)
 483
 484 #  define LOOKUP find234(root, &word, word_cmp)
 485
 486 #  define FREE do {                                                     \
 487         while (node = delpos234(root, 0), node) free(node);             \
 488         freetree234(root);                                              \
 489    } while (0)
 490
 491 #  define CHECK do ; while (0)
 492
 493 #elif USE_LIBAVL
 494
 495 static int node_cmp(const void *a, const void *b, void *arg)
 496 {
 497   const struct word *wa = a, *wb = b;
 498
 499   return (compare_words(wa->p, wa->n, wb->p, wb->n));
 500 }
 501
 502 static void free_node(void *n, void *arg) { free(n); }
 503
 504 #  define DECLS                                                         \
 505         struct TABLE *tab;                                              \
 506         struct TRAVERSER it;                                            \
 507         void **p
 508
 509 #  define INIT do {                                                     \
 510         tab = TREE_CREATE(node_cmp, 0, 0);                              \
 511         if (!tab) bail("out of memory");                                \
 512    } while (0)
 513
 514 #  define INSERT do {                                                   \
 515         p = TREE_PROBE(tab, node); if (!p) bail("out of memory");       \
 516         if (*p != node) {                                               \
 517           fprintf(stderr, ";; duplicate `%s'\n", buf);                  \
 518           free(node); node = 0;                                         \
 519         }                                                               \
 520    } while (0)
 521
 522 #  define ITERATE                                                       \
 523         for (TREE_T_INIT(&it, tab); node = TREE_T_NEXT(&it), node; )
 524
 525 #  define FOCUS do ; while (0)
 526
 527 #  define LOOKUP TREE_FIND(tab, &word)
 528
 529 #  define FREE do { TREE_DESTROY(tab, free_node); } while (0)
 530
 531 #  define CHECK do ; while (0)
 532
 533 #elif TREE == MLIB_SYM
 534
 535 #  define DECLS                                                         \
 536         sym_table tab;                                                  \
 537         struct node *all = 0, **all_tail = &all;                        \
 538         unsigned foundp
 539
 540 #  define INIT do {                                                     \
 541         unihash_setkey(&unihash_global, getpid());                      \
 542         sym_create(&tab);                                               \
 543    } while (0)
 544
 545 #  define PREPNODE do ; while (0)
 546
 547 #  define INSERT do {                                                   \
 548         node = sym_find(&tab, buf, word.n, sizeof(*node), &foundp);     \
 549         if (!foundp) {                                                  \
 550           node->next = 0; *all_tail = node; all_tail = &node->next;     \
 551         } else {                                                        \
 552           fprintf(stderr, ";; duplicate `%s'\n", buf);                  \
 553           free(node); node = 0;                                         \
 554         }                                                               \
 555    } while (0)
 556
 557 #  define ITERATE for (next = all; node = next, node; next = next->next)
 558
 559 #  define FOCUS do ; while (0)
 560
 561 #  define LOOKUP sym_find(&tab, word.p, word.n, 0, 0)
 562
 563 #  define FREE do { sym_destroy(&tab); } while (0)
 564
 565 #  define CHECK do ; while (0)
 566
 567 #endif
 568
 569 #ifndef PREPNODE
 570 #  define PREPNODE do {                                                 \
 571         node = malloc(sizeof(*node) + word.n + 1);                      \
 572           if (!node) bail("out of memory");                             \
 573         node->w.p = (char *)(node + 1);                                 \
 574         memcpy(node + 1, buf, word.n + 1); node->w.n = word.n;          \
 575    } while (0)
 576 #endif
 577
 578 #ifndef GETPREFIX
 579 #  define GETPREFIX do {                                                \
 580         word.p = WORDPTR(node); word.n = WORDLEN(node) - 1;             \
 581    } while (0)
 582
 583 #endif
 584
 585 static void print_chain(struct node *node)
 586 {
 587   if (!node->right) {
 588     fputs(WORDPTR(node), stdout);
 589     if (node->down) { putchar(' '); print_chain(node->down); }
 590   } else {
 591     fputs("{ ", stdout);
 592     for (;;) {
 593       fputs(WORDPTR(node), stdout);
 594       if (node->down) { putchar(' '); print_chain(node->down); }
 595       node = node->right; if (!node) break;
 596       fputs(" | ", stdout);
 597     }
 598     fputs(" }", stdout);
 599   }
 600 }
 601
 602 int main(void)
 603 {
 604   DECLS;
 605   struct node *node, *parent, *winners, **winners_tail, *next;
 606   struct word word;
 607   char buf[WORDMAX];
 608   int ch, max, nlen, plen;
 609
 610   INIT;
 611   word.p = buf;
 612   for (;;) {
 613     if (!fgets(buf, WORDMAX, stdin)) break;
 614     word.n = strlen(buf); assert(word.n);
 615     if (buf[word.n - 1] == '\n') buf[--word.n] = 0;
 616     else if (word.n == WORDMAX - 1) bail("word too long");
 617     else if (ch = getchar(), ch != EOF) bail("short read, found `%c'", ch);
 618
 619     PREPNODE; INSERT;
 620     if (node) { node->up = node->down = node->right = 0; CHLEN(node) = 1; }
 621   }
 622
 623   CHECK;
 624
 625   max = 0; winners_tail = &winners;
 626
 627   ITERATE {
 628     FOCUS;
 629     /* fprintf(stderr, ";; ponder `%.*s'\n", WORDLEN(node), WORDPTR(node)); */
 630     if (WORDLEN(node) <= 1)
 631       continue;
 632     else {
 633       GETPREFIX;
 634       /* fprintf(stderr, ";; search `%.*s'\n", word.n, word.p); */
 635       parent = LOOKUP; if (!parent) continue;
 636     }
 637     node->up = parent; nlen = CHLEN(node);
 638     for (;;) {
 639       if (!parent) {
 640         if (nlen >= max) {
 641           if (nlen > max)
 642             { max = nlen; *winners_tail = 0; winners_tail = &winners; }
 643           *winners_tail = node; winners_tail = &node->right;
 644         }
 645         break;
 646       }
 647       plen = CHLEN(parent); nlen++;
 648       if (plen > nlen)
 649         break;
 650       else if (plen == nlen) {
 651         node->right = parent->down; parent->down = node;
 652         break;
 653       } else {
 654         parent->down = node; node->right = 0;
 655         CHLEN(parent) = nlen;
 656         node = parent; parent = node->up;
 657       }
 658     }
 659   }
 660
 661   for (*winners_tail = 0, node = winners; node; node = next) {
 662     next = node->right; node->right = 0;
 663     print_chain(node); putchar('\n');
 664   }
 665   FREE;
 666   return (0);
 667 }