home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 5 Edit / 05-Edit.zip / vile-src.zip / vile-8.1 / btree.c < prev    next >
C/C++ Source or Header  |  1998-04-28  |  20KB  |  913 lines
  1. /*
  2.  * $Id: btree.c,v 1.4 1998/04/28 10:15:52 tom Exp $
  3.  * Copyright 1997 by Thomas E. Dickey
  4.  *
  5.  * Maintains a balanced binary tree (aka AVL tree) of unspecified nodes.  The
  6.  * algorithm is taken from "The Art of Computer Programming -- Volume 3 --
  7.  * Sorting and Searching", by Donald Knuth.  Knuth presents the insertion and
  8.  * search algorithms in assembly language for MIX, and gives an overview of the
  9.  * deletion algorithm for the "interested reader".
  10.  */
  11.  
  12. #ifdef HAVE_CONFIG_H
  13. #include <config.h>
  14. #endif
  15.  
  16. #include <stdlib.h>
  17. #include <stdio.h>
  18. #include <string.h>
  19.  
  20. #if !defined(DEBUG_BTREE) && !defined(NDEBUG)
  21. #define NDEBUG
  22. #endif
  23.  
  24. #include <assert.h>
  25.  
  26. #include "btree.h"
  27.  
  28. #if defined(OPT_TRACE) || defined(DOALLOC)
  29. #include "trace.h"
  30. #endif
  31.  
  32. #ifdef USE_DBMALLOC
  33. #include <dbmalloc.h>
  34. #endif
  35.  
  36. #ifdef USE_DMALLOC
  37. #include <dmalloc.h>
  38. #endif
  39.  
  40. #define castalloc(cast,nbytes) (cast *)malloc(nbytes)
  41.  
  42.             /* definitions to make this simple, like Knuth */
  43. #define    LLINK(p)    BI_LEFT(p)
  44. #define    RLINK(p)    BI_RIGHT(p)
  45. #define    KEY(p)        BI_KEY(p)
  46. #define    B(p)        (p)->balance
  47.  
  48. #define COMPARE(a,b)    btree_strcmp(a,b)
  49.  
  50. #define    LINK(a,p)    (p)->links[(a)>0]
  51.  
  52. #ifdef DEBUG_BTREE
  53. # ifndef TRACE
  54. #  if DEBUG_BTREE > 0
  55. #   define TRACE(p)    printf p ; fflush(stdout) ;
  56. #  endif
  57. # endif
  58. #else
  59. # undef TRACE
  60. #endif
  61.  
  62. #if DEBUG_BTREE > 1
  63. #define TRACE_TREE(s,p)    TRACE((s)) btree_printf(p)
  64. #endif
  65.  
  66. #if DEBUG_BTREE > 2
  67. #define TRACE_SUBTREE(s,h,p)    TRACE(s); dump_nodes(h,p,0)
  68. #endif
  69.  
  70. #ifndef TRACE
  71. #define TRACE(p)    /*nothing*/
  72. #endif
  73.  
  74. #ifndef TRACE_TREE
  75. #define TRACE_TREE(s,p)    /*nothing*/
  76. #endif
  77.  
  78. #ifndef TRACE_SUBTREE
  79. #define TRACE_SUBTREE(s,h,p)    /*nothing*/
  80. #endif
  81.  
  82. #ifdef DEBUG_BTREE
  83. static int btree_verify(BI_TREE *funcs, BI_NODE *p);
  84. #endif
  85.  
  86. /*
  87.  * FIXME
  88.  */
  89. static int
  90. btree_strcmp(const char *a, const char *b)
  91. {
  92.     register int cmp = strcmp(a, b);
  93.     if (cmp < 0)
  94.         cmp = -1;
  95.     else if (cmp > 0)
  96.         cmp = 1;
  97.     return cmp;
  98. }
  99.  
  100. BI_DATA *
  101. btree_insert(BI_TREE *funcs, BI_DATA *data)
  102. {
  103.                 /* (A1:Initialize) */
  104. register
  105.     BI_NODE    *t = &(funcs->head),    /* 't' => to the father of 's'    */
  106.         *s = RLINK(t),        /* 's' => to rebalancing point    */
  107.         *p = RLINK(t),        /* 'p' => down the tree        */
  108.         *q,
  109.         *r;
  110. register
  111.     int    a;
  112.     BI_DATA    *value = 0;
  113.  
  114.     TRACE(("inserting '%s'\n", data->bi_key))
  115.     if (p == 0) {
  116.         RLINK(t) = p = (*funcs->allocat)(data);
  117.         funcs->depth += 1;
  118.         funcs->count += 1;
  119.         return &(p->value);
  120.     }
  121.                 /* (A2:Compare) */
  122.     while ((a = COMPARE(data->bi_key, KEY(p))) != 0) {
  123.                 /* (A3,A4: move left/right accordingly)    */
  124.         if ((q = LINK(a,p)) != 0) {
  125.             value = &(p->value);
  126.             if (B(q)) {
  127.                 t = p;
  128.                 s = q;
  129.             }
  130.             p = q;
  131.             /* ...continue comparing */
  132.         } else {
  133.             /* (A5:Insert) */
  134.             LINK(a,p) = q = (*funcs->allocat)(data);
  135.             funcs->count += 1;
  136.             value = &(q->value);
  137.  
  138.             /* (A6:Adjust balance factors) */
  139.             /*
  140.              * Now the balance factors on nodes between 's' and 'q'
  141.              * need to be changed from zero to +/- 1.
  142.              */
  143.             if (COMPARE(data->bi_key, KEY(s)) < 0)
  144.                 r = p = LLINK(s);
  145.             else
  146.                 r = p = RLINK(s);
  147.  
  148.             while (p != q) {
  149.                 if ((a = COMPARE(data->bi_key, KEY(p))) != 0) {
  150.                     B(p) = (a < 0) ? -1 : 1;
  151.                     p = LINK(a,p);
  152.                 }
  153.             }
  154.  
  155.                 /* (A7:Balancing act) */
  156.             a = (COMPARE(data->bi_key, KEY(s)) < 0) ? -1 : 1;
  157.  
  158.             if (B(s) == 0) {
  159.                 /* ...the tree has grown higher    */
  160.                 B(s) = a;
  161.                 funcs->depth += 1;
  162.             } else if (B(s) == -a) {
  163.                 /* ...the tree has gotten more balanced    */
  164.                 B(s) = 0;
  165.             } else /* (B(s) == a) */ {
  166.                 assert(B(s) == a);
  167.                 /* ...the tree has gotten out of balance */
  168.                 TRACE(("...must rebalance\n"))
  169.                 if (B(r) == a) {
  170.                     TRACE(("(A8:Single rotation)\n"))
  171.                     p          = r;
  172.                     LINK(a,s)  = LINK(-a,r);
  173.                     LINK(-a,r) = s;
  174.  
  175.                     B(s) = B(r) = 0;
  176.                 } else /* (B(r) == -a) */ {
  177.                     assert(B(r) == -a);
  178.                     TRACE(("(A9: Double rotation)\n"))
  179.                     p          = LINK(-a,r);
  180.                     LINK(-a,r) = LINK(a,p);
  181.                     LINK(a,p)  = r;
  182.                     LINK(a,s)  = LINK(-a,p);
  183.                     LINK(-a,p) = s;
  184.  
  185.                     TRACE(("r=%s\n", KEY(r)))
  186.                     TRACE(("s=%s\n", KEY(s)))
  187.                     TRACE(("B(%s) = %d vs a = %d\n",
  188.                         KEY(p), B(p), a))
  189.  
  190.                     if (B(p) == a)
  191.                         { B(s) = -a; B(r) = 0;    }
  192.                     else if (B(p) == 0)
  193.                         { B(s) =     B(r) = 0;  }
  194.                     else /* if (B(p) == -a) */
  195.                         { B(s) = 0;  B(r) = a;  }
  196.  
  197.                     B(p) = 0;
  198.                 }
  199.                 /* A10:Finishing touch */
  200.                 t->links[(s == RLINK(t))] = p;
  201.             }
  202.             break;
  203.         }
  204.     }
  205.     return (value);
  206. }
  207.  
  208. static BI_NODE *
  209. parent_of(BI_TREE *funcs, BI_NODE *s)
  210. {
  211.     BI_NODE    *r = &(funcs->head),
  212.         *p = RLINK(r);     /* 'p' => down the tree    */
  213.     int a;
  214.  
  215.     while ((a = COMPARE(KEY(s), KEY(p))) != 0) {
  216.         assert(LINK(a,p) != 0);
  217.         r = p;
  218.         p = LINK(a,p);
  219.     }
  220.     TRACE(("parent of '%s' is '%s'\n", KEY(s), KEY(r)))
  221.     return r;
  222. }
  223.  
  224. #define MAXSTK 20
  225. #define PUSH(A,P) { \
  226.     TRACE(("@%d:push #%d a=%2d, B=%2d, p='%s' -> '%s'\n", __LINE__, \
  227.         k, A, B(P), P?KEY(P):"", LINK(A,P)?KEY(LINK(A,P)):"")) \
  228.     stack[k].a = A;\
  229.     stack[k].p = P;\
  230.     k++; }
  231.  
  232. int
  233. btree_delete(BI_TREE *funcs, const char *data)
  234. {
  235.     struct {
  236.     BI_NODE    *p;
  237.     int    a;
  238.     } stack[MAXSTK];
  239.     int    k = 0;
  240.                 /* (A1:Initialize) */
  241. register
  242.     BI_NODE    *t = &(funcs->head),
  243.         *p = RLINK(t),
  244.         *q, *r, *s;
  245. register
  246.     int    a, b;
  247.     char    *value;
  248.  
  249.     if ((p = t) == 0
  250.      || (p = LINK(a=1,p)) == 0) {
  251.         return 0;
  252.     }
  253.                 /* (A2:Compare) */
  254.     while ((a = COMPARE(data, value = KEY(p))) != 0) {
  255.         if ((q = LINK(a,p)) == 0) {
  256.             value = 0;
  257.             break;
  258.         }
  259.                 /* (A3,A4: move left/right accordingly)    */
  260.         t = p;
  261.         p = LINK(a,p);
  262.         /* ...continue comparing */
  263.     }
  264.  
  265.     if (value != 0) {    /* we found the node to delete, in p */
  266.         TRACE(("deleting node '%s'\n", value))
  267.         q = p;
  268.         p = t;
  269.         a = (q == RLINK(p)) ? 1 : -1;
  270.  
  271.         TRACE(("@%d, p='%s'\n", __LINE__, p?KEY(p):""))
  272.         TRACE(("@%d, q='%s'\n", __LINE__, q?KEY(q):""))
  273.         TRACE(("@%d, a=%d\n",   __LINE__, a))
  274.  
  275.                 /* D1: Is RLINK null? */
  276.         if (RLINK(q) == 0) {
  277.             TRACE(("D1\n"))
  278.  
  279.             LINK(a,p) = LLINK(q);
  280.             s = p;
  281. #if LATER
  282.         } else if (LLINK(q) == 0) { /* D1.5 */
  283.             TRACE(("D1.5\n"))
  284.             LINK(a,p) = RLINK(q);
  285.             s = RLINK(q);
  286. #endif
  287.         } else {    /* D2: Find successor */
  288.             TRACE_SUBTREE("SUBTREE(p)-before\n", funcs, p);
  289.             r = RLINK(q);
  290.             if (LLINK(r) == 0) {
  291.                 TRACE(("D2, r='%s', q='%s'\n", KEY(r), KEY(q)))
  292.                 TRACE(("DIFF: %d\n", B(r) - B(q)))
  293.  
  294.                 LLINK(r) = LLINK(q);
  295.                 LINK(a,p) = r;
  296.                 s = r;
  297.                 TRACE(("(D2) replace balance %2d with %2d, a=%2d\n", B(s), B(q), a))
  298.                 B(s) = B(q);
  299.                 a = 1;    /* for RLINK(q) */
  300.  
  301.                 TRACE_SUBTREE("SUBTREE(p)-after\n", funcs, p);
  302.                 TRACE(("@%d, p='%s'\n", __LINE__, KEY(p)))
  303.                 TRACE(("@%d, r='%s'\n", __LINE__, KEY(r)))
  304.             } else { /* D3: Find null LLINK */
  305.                 TRACE(("D3: find null LLINK\n"))
  306.  
  307.                 TRACE(("@%d, r='%s'\n", __LINE__, r?KEY(r):""))
  308.                 s = r;
  309.                 do {
  310.                     r = s;
  311.                     s = LLINK(r);
  312.                 } while (LLINK(s) != 0);
  313.  
  314.                 LLINK(s) = LLINK(q);
  315.                 LLINK(r) = RLINK(s);
  316.                 RLINK(s) = RLINK(q);
  317.                 TRACE(("@%d, p='%s', a=%d\n", __LINE__, KEY(p), a))
  318.                 TRACE(("@%d, r='%s'\n", __LINE__, KEY(r)))
  319.                 TRACE(("@%d, s='%s'\n", __LINE__, KEY(s)))
  320.                 LINK(a,p) = s;
  321.                 TRACE(("(D3) replace balance %2d with %2d, a=%2d\n", B(s), B(q), a))
  322.                 B(s) = B(q);
  323.                 s = r;
  324.                 a = -1;    /* ...since we followed left */
  325.             }
  326.         }
  327.         b = a;
  328.                 /* D4: Free the node */
  329.         assert(q != 0);
  330.         (*funcs->dealloc)(q);
  331.         funcs->count -= 1;
  332.         TRACE_TREE("after delinking:",funcs);
  333.  
  334.                 /* Construct the auxiliary stack */
  335.         a = 1;
  336.         q = &(funcs->head);
  337.         if (s != 0
  338.          && s != q
  339.          && q != 0) {
  340.             TRACE(("Construct stack from '%s' down to '%s', final a=%d\n",
  341.                 q?KEY(q):"",
  342.                 s?KEY(s):"",
  343.                 b))
  344.             while (s != q) {
  345.                 PUSH(a,q);
  346.                 q = LINK(a,q);
  347.                 a = COMPARE(KEY(s), KEY(q));
  348.             }
  349.             PUSH(b,q);
  350.             TRACE(("...done building stack\n"))
  351.         }
  352.  
  353.                 /* Rebalance the tree */
  354.         for (;;) {
  355.             if (--k <= 0) {
  356.                 TRACE(("shorten the whole tree\n"))
  357.                 funcs->depth -= 1;
  358.                 break;
  359.             }
  360.             p = stack[k].p;
  361.             a = stack[k].a;
  362.             TRACE(("processing #%d '%s' B = %d, a = %d (%p)\n",
  363.                 k, KEY(p), B(p), a, LINK(a,p)))
  364.             if (B(p) == a) {
  365.                 TRACE(("Case (i)\n"))
  366.                 B(p) = 0;
  367.             } else if (B(p) == 0) {
  368.                 TRACE(("Case (ii)\n"))
  369.                 B(p) = -a;
  370.                 break;
  371.             } else {
  372.                 TRACE(("Case (iii): Rebalancing needed!\n"))
  373.  
  374.                 q = LINK(-a,p);
  375.                 assert(q != 0);
  376.                 assert(k >  0);
  377.                 assert(B(p) == -a);
  378.  
  379.                 t = stack[k-1].p;
  380.                 TRACE(("t:%s, balance:%d\n", KEY(t), B(t)))
  381.                 TRACE(("A:p:%s, balance:%d\n", KEY(p), B(p)))
  382.                 TRACE(("B:q:%s, balance:%d\n", KEY(q), B(q)))
  383.                 TRACE_TREE("before rebalancing:", funcs);
  384.  
  385.                 if (B(q) == -a) {
  386.                     TRACE(("CASE 1: single rotation\n"))
  387.  
  388.                     r          = q;
  389.  
  390.                     TRACE(("link LINK(-a,p) -> LINK( a,q) = '%s'\n", LINK(a,q)?KEY(LINK(a,q)):""))
  391.                     TRACE(("link LINK( a,q) -> p          = '%s'\n", p?KEY(p):""))
  392.  
  393.                     LINK(-a,p) = LINK(a,q);
  394.                     LINK(a,q)  = p;
  395.  
  396.                     B(p) = B(q) = 0;
  397.  
  398.                     t = parent_of(funcs, p);
  399.  
  400.                     TRACE(("Finish by linking '%s' to %sLINK(%s)\n",
  401.                         KEY(r),
  402.                         (p == RLINK(t))
  403.                             ? "R"
  404.                             : (p == LLINK(t))
  405.                                 ? "L" : "?",
  406.                         KEY(t)))
  407.  
  408.                     t->links[(p == RLINK(t))] = r;
  409.  
  410.                 } else if (B(q) == a) {
  411.                     TRACE(("CASE 2: double rotation\n"))
  412.  
  413.                     r          = LINK(a,q);
  414. #if DEBUG_BTREE > 1
  415.                     TRACE(("a = '%d'\n", a))
  416.                     TRACE(("p = '%s'\n", p?KEY(p):""))
  417.                     TRACE(("q = '%s'\n", q?KEY(q):""))
  418.                     TRACE(("r = '%s'\n", r?KEY(r):""))
  419.                     TRACE(("link LINK( a,q) -> LINK(-a,r) = '%s'\n", LINK(-a,r)?KEY(LINK(-a,r)):""))
  420.                     TRACE(("link LINK(-a,r) -> q          = '%s'\n", KEY(q)))
  421.                     TRACE(("link LINK(-a,p) -> LINK(a,r)  = '%s'\n", LINK(a,r)?KEY(LINK(a,r)):""))
  422.                     TRACE(("link LINK( a,r) -> p          = '%s'\n", KEY(p)))
  423. #endif
  424.                     LINK(a,q)  = LINK(-a,r);
  425.                     LINK(-a,r) = q;
  426.                     LINK(-a,p) = LINK(a,r);
  427.                     LINK(a,r)  = p;
  428.  
  429.                     TRACE(("compute balance for '%s', %d vs a=%d\n",
  430.                         KEY(r), B(r), a))
  431.  
  432.                     if (B(r) == -a)
  433.                         { B(p) = a;  B(q) = 0;    }
  434.                     else if (B(r) == 0)
  435.                         { B(p) =     B(q) = 0;  }
  436.                     else /* (B(r) == a) */
  437.                         { B(p) = 0;  B(q) = -a;  }
  438.  
  439.                     B(r) = 0;
  440.  
  441.                     a = stack[k-1].a;
  442.                     t = stack[k-1].p;
  443.  
  444.                     TRACE(("Finish by linking '%s' to %sLINK(%s)\n",
  445.                         KEY(r),
  446.                         (a>0) ? "R" : "L",
  447.                         KEY(t)))
  448.  
  449.                     LINK(a,t) = r;
  450.  
  451.                 } else {
  452.                     TRACE(("CASE 3: single rotation, end\n"))
  453.  
  454.                     r          = q;
  455.                     LINK(-a,p) = LINK(a,q);
  456.                     LINK(a,q)  = p;
  457.  
  458.                     B(q) = -B(p);
  459.  
  460.                     LINK(stack[k-1].a,stack[k-1].p) = q;
  461.                     break;
  462.                 }
  463.  
  464.                 TRACE_TREE("after rebalancing:", funcs);
  465.  
  466.             }
  467.         }
  468.     }
  469.     return (value != 0);
  470. }
  471.  
  472. BI_DATA *
  473. btree_search(BI_TREE *funcs, const char *data)
  474. {
  475.                 /* (A1:Initialize) */
  476. register
  477.     BI_NODE    *t = &(funcs->head),    /* 't' => to the father of 's'    */
  478.         *p = RLINK(t),        /* 'p' => down the tree        */
  479.         *q;
  480. register
  481.     int    a;
  482.  
  483.     if (p == 0) {
  484.         return 0;
  485.     }
  486.                 /* (A2:Compare) */
  487.     while ((a = COMPARE(data, KEY(p))) != 0) {
  488.                 /* (A3,A4: move left/right accordingly)    */
  489.         if ((q = LINK(a,p)) != 0) {
  490.             p = q;
  491.             /* ...continue comparing */
  492.         } else {
  493.             break;
  494.         }
  495.     }
  496.     return a ? 0 : &(p->value);
  497. }
  498.  
  499. /******************************************************************************/
  500.  
  501. #ifndef BTREE_VERIFY
  502. #define BTREE_VERIFY 1
  503. #endif
  504.  
  505. #ifndef BTREE_DRIVER
  506. #define BTREE_DRIVER 1
  507. #endif
  508.  
  509. #if DEBUG_BTREE >= BTREE_VERIFY
  510. static int
  511. btree_count(BI_NODE *p)
  512. {
  513.     int count = 0;
  514.     if (p != 0) {
  515.         count = 1;
  516.         count += btree_count(LLINK(p));
  517.         count += btree_count(RLINK(p));
  518.     }
  519.     return count;
  520. }
  521. #endif
  522.  
  523. #if DEBUG_BTREE >= BTREE_VERIFY
  524. static int
  525. btree_depth(BI_NODE *p)
  526. {
  527.     int depth = 0;
  528.     if (p != 0) {
  529.         int l, r;
  530.         assert(LLINK(p) != p);
  531.         assert(RLINK(p) != p);
  532.         l = btree_depth(LLINK(p));
  533.         r = btree_depth(RLINK(p));
  534.         depth = 1;
  535.         if (l > r)
  536.             depth += l;
  537.         else
  538.             depth += r;
  539.     }
  540.     return depth;
  541. }
  542. #endif
  543.  
  544. static void
  545. dump_nodes(BI_TREE *funcs, BI_NODE * p, int level)
  546. {
  547.     if (p) {
  548.         dump_nodes(funcs, LLINK(p),  level+1);
  549.         (*funcs->display)(p, level);
  550. #if DEBUG_BTREE > 0
  551.         if (LLINK(p) != 0
  552.          && COMPARE(KEY(LLINK(p)), KEY(p)) > 0)
  553.             TRACE((" OOPS:L"))
  554.         if (RLINK(p) != 0
  555.          && COMPARE(KEY(RLINK(p)), KEY(p)) < 0)
  556.             TRACE((" OOPS:R"))
  557.         TRACE((" %d", btree_depth(p)))
  558. #endif
  559. #if DEBUG_BTREE >= BTREE_DRIVER
  560.         printf("\n");
  561. #endif
  562.         dump_nodes(funcs, RLINK(p), level+1);
  563.     }
  564. }
  565.  
  566. /*
  567.  * Invoke display function for each node
  568.  */
  569. void
  570. btree_printf(BI_TREE * funcs)
  571. {
  572.     TRACE(("TREE, depth %d, count %d\n", funcs->depth, funcs->count))
  573.     dump_nodes(funcs, RLINK(&(funcs->head)), 0);
  574. }
  575.  
  576. /******************************************************************************/
  577.  
  578. /*
  579.  * Find the the matching entry given a name in the tree.  Match according to
  580.  * the 'mode' parameter:
  581.  *
  582.  *    If it's FALSE then only the first len characters must match and this
  583.  *    will return the parent of the subtree that contains these entries (so
  584.  *    that an inorder walk can find the other matches).
  585.  *
  586.  *    Use TRUE to force this to return the first of the ordered list of
  587.  *    partial matches; we need this behavior for interactive name completion.
  588.  */
  589. BI_NODE *
  590. btree_pmatch(BI_NODE *n, const int mode, const char *name)
  591. {
  592.     BI_NODE *m;
  593.     size_t len = strlen(name);
  594.  
  595.     while (n != 0) {
  596.         int cmp;
  597.  
  598.         cmp = strncmp(name, BI_KEY(n), len);
  599.  
  600.         if (cmp == 0) {
  601.             if (mode
  602.              && (m = btree_pmatch(BI_LEFT(n), mode, name)) != 0)
  603.                 n = m;
  604.             return n;
  605.         } else if (cmp < 0) {
  606.             n = BI_LEFT(n);
  607.         } else {
  608.             n = BI_RIGHT(n);
  609.         }
  610.     }
  611.     return 0;
  612. }
  613.  
  614. /*
  615.  * Find the size of the binary-subtree with the matching name.
  616.  */
  617. static int
  618. btree_pcount(BI_NODE *node, char *matchname, size_t len)
  619. {
  620.     int left = 0, right = 0, me = 0;
  621.  
  622.     if (BI_LEFT(node) != 0) {
  623.         left = btree_pcount(BI_LEFT(node), matchname, len);
  624.     }
  625.  
  626.     if ((len == 0)
  627.      || (strncmp(BI_KEY(node), matchname, len) == 0))
  628.         me = 1;
  629.  
  630.     if (BI_RIGHT(node) != 0) {
  631.         right = btree_pcount(BI_RIGHT(node), matchname, len);
  632.     }
  633.  
  634.     return me + left + right;
  635. }
  636.  
  637. static void
  638. build_parray(BI_NODE *head, char *matchname, size_t len, const char **nptr, int *i)
  639. {
  640.     if (BI_LEFT(head) != 0) {
  641.         build_parray(BI_LEFT(head), matchname, len, nptr, i);
  642.     }
  643.  
  644.     if ((len == 0)
  645.      || (strncmp(BI_KEY(head), matchname, len) == 0)) {
  646.         nptr[*i] = BI_KEY(head);
  647.         (*i)++;
  648.     }
  649.  
  650.     if (BI_RIGHT(head) != 0) {
  651.         build_parray(BI_RIGHT(head), matchname, len, nptr, i);
  652.     }
  653. }
  654.  
  655. /*
  656.  * Build an array of the keys that partially-match the given name to at least
  657.  * the given length 'len'.
  658.  */
  659. const char **
  660. btree_parray(BI_TREE *tree, char *name, unsigned len)
  661. {
  662.     BI_NODE *top;
  663.     const char **nptr = 0;
  664.     top = btree_pmatch(BI_RIGHT(&(tree->head)), 0, name);
  665.  
  666.     if (top != 0) {
  667.         int i = 0;
  668.         size_t cnt = btree_pcount(top, name, len);
  669.         nptr = castalloc(const char *, sizeof(const char *) * (cnt + 1));
  670.         if (nptr != 0) {
  671.             build_parray(top, name, len, nptr, &i);
  672.             nptr[i] = 0;
  673.         }
  674.     }
  675.     return nptr;
  676. }
  677.  
  678. int btree_freeup(BI_TREE *funcs)
  679. {
  680.     TRACE(("Deleting all nodes...\n"))
  681.     TRACE_TREE("INITIAL-", funcs);
  682.     while (RLINK(&(funcs->head))) {
  683.         TRACE(("Try to delete '%s'\n", KEY(RLINK(&(funcs->head)))))
  684.         if (!btree_delete(funcs, KEY(RLINK(&(funcs->head))))) {
  685.             TRACE(("Try-delete failed\n"))
  686.             return 0;
  687.         }
  688. #ifdef DEBUG_BTREE
  689.         TRACE_TREE("AFTER-DELETE, ", funcs);
  690.         if (!btree_verify(funcs, RLINK(&(funcs->head)))) {
  691.             TRACE(("Try-verify failed\n"))
  692.             return 0;
  693.         }
  694. #endif
  695.     }
  696.     return 1;
  697. }
  698.  
  699. /******************************************************************************/
  700.  
  701. #ifdef DEBUG_BTREE
  702.  
  703. static int
  704. btree_verify(BI_TREE *funcs, BI_NODE *p)
  705. {
  706. #if DEBUG_BTREE >= BTREE_VERIFY
  707.     int ok = 1;
  708.  
  709.     if (p != 0) {
  710.         int root = (p == &(funcs->head));
  711.         BI_NODE *l = root ? 0 : LLINK(p);
  712.         BI_NODE *r = RLINK(p);
  713.         int balance = 0;
  714.         int compare = 0;
  715.  
  716.         if (p == RLINK(&(funcs->head))) {
  717.             int count = btree_count(p);
  718.             if (count != funcs->count) {
  719.                 ok = 0;
  720.                 TRACE(("OOPS: Counted %d vs %d in header\n",
  721.                     count, funcs->count))
  722.             }
  723.         }
  724.         /* verify the balance factor */
  725.         if ((balance = btree_depth(r) - btree_depth(l)) != 0) {
  726.             if (balance > 0) {
  727.                 if (balance > 1) {
  728.                     ok = 0;
  729.                     TRACE(("OOPS: '%s' is unbalanced\n", KEY(p)))
  730.                 }
  731.                 balance = 1;
  732.             } else {
  733.                 if (balance < -1) {
  734.                     ok = 0;
  735.                     TRACE(("OOPS: '%s' is unbalanced\n", KEY(p)))
  736.                 }
  737.                 balance = -1;
  738.             }
  739.         }
  740.         if (B(p) != balance) {
  741.             ok = 0;
  742.             TRACE(("OOPS: Balance '%s' have %d vs %d\n",
  743.                 KEY(p), B(p), balance))
  744.         }
  745.  
  746.         /* verify that the nodes are in correct order */
  747.         compare = COMPARE(
  748.                 (l != 0) ? KEY(l) : "",
  749.                 (r != 0) ? KEY(r) : "\377");
  750.         if (compare >= 0) {
  751.             ok = 0;
  752.             TRACE(("OOPS: Compare %s, have %d vs -1\n",
  753.                 KEY(p), compare))
  754.         }
  755.  
  756.         /* recur as needed */
  757.         ok &= btree_verify(funcs, l);
  758.         ok &= btree_verify(funcs, r);
  759.     }
  760.     return ok;
  761. #else
  762.     return 1;
  763. #endif
  764. }
  765.  
  766. #if DEBUG_BTREE >= BTREE_DRIVER
  767.  
  768. /******************************************************************************/
  769. #undef typecalloc
  770. #define typecalloc(cast) (cast *)calloc(sizeof(cast),1)
  771.  
  772. static BI_NODE *
  773. new_node (BI_DATA * data)
  774. {
  775.     BI_NODE *result = typecalloc(BI_NODE);
  776.     result->value = *data;
  777.     result->value.bi_key = strdup(data->bi_key); /* DEBUG-only */
  778.     return result;
  779. }
  780.  
  781. static void
  782. old_node (BI_NODE *node)
  783. {
  784.     free(node);
  785. }
  786.  
  787. static void
  788. dpy_node (BI_NODE *a, int level)
  789. {
  790.     while (level-- > 0)
  791.         printf(". ");
  792.     printf("%s (%d)", KEY(a), B(a));
  793.     fflush(stdout);
  794. }
  795.  
  796. static    BI_TREE    text_tree = {
  797.     new_node,
  798.     old_node,
  799.     dpy_node
  800.     };
  801.  
  802. /******************************************************************************/
  803.  
  804. #define MAX_VEC 10000
  805.  
  806. int main(int argc, char *argv[])
  807. {
  808.     BI_DATA temp;
  809.     BI_NODE *top;
  810.     int n, m;
  811.     int done = 0;
  812.     char buffer[BUFSIZ];
  813.     int vector[MAX_VEC];
  814.     const char **list;
  815.  
  816.     memset(&temp, 0, sizeof(temp));
  817.     for (n = 1; n < argc; n++) {
  818.         temp.bi_key = argv[n];
  819.         btree_insert(&text_tree, &temp);
  820.     }
  821.  
  822.     btree_printf(&text_tree);
  823.     btree_verify(&text_tree, RLINK(&(text_tree.head)));
  824.  
  825.     while (!done && fgets(buffer, sizeof(buffer), stdin) != 0) {
  826.         char *t = buffer;
  827.         char *s = t + strlen(t);
  828.  
  829.         if (s != buffer && *--s == '\n')
  830.             *s = 0;
  831.  
  832.         switch (*t++) {
  833.         default:
  834.             printf("Commands are f(ind) i(nsert), d(elete), l(ist), p(rint), r(andom)\n");
  835.             break;
  836.         case 'f':
  837.             n = (btree_search(&text_tree, t) != 0);
  838.             printf("** found(%s) %d\n", t, n);
  839.             break;
  840.         case 'i':
  841.             temp.bi_key = t;
  842.             n = (btree_insert(&text_tree, &temp) != 0);
  843.             printf("** insert(%s) %d\n", t, n);
  844.             break;
  845.         case 'd':
  846.             n = btree_delete(&text_tree, t);
  847.             printf("** delete(%s) %d\n", t, n);
  848.             break;
  849.         case 'l':
  850.             if ((list = btree_parray(&text_tree, t, strlen(t))) != 0) {
  851.                 printf("** list(%s)\n", t);
  852.                 for (n = 0; list[n] != 0; n++)
  853.                     printf("[%d] '%s'\n", n, list[n]);
  854.                 free(list);
  855.             }
  856.             else
  857.                 printf("** list(%s) fail\n", t);
  858.             break;
  859.         case 'L':
  860.             if ((top = btree_pmatch(RLINK(&text_tree.head), 1, t)) != 0)
  861.                 printf("** List(%s) -> '%s'\n", t, KEY(top));
  862.             else
  863.                 printf("** List(%s) fail\n", t);
  864.             break;
  865.         case 'p':
  866.             btree_printf(&text_tree);
  867.             break;
  868.         case 'r':
  869.             for (n = 0; n < MAX_VEC; n++) {
  870.                 vector[n] = random();
  871.                 sprintf(buffer, "%d", vector[n]);
  872.                 temp.bi_key = buffer;
  873.                 (void) btree_insert(&text_tree, &temp);
  874.                 printf("** inserted(%s)\n", buffer);
  875.             }
  876.             for (m = 0; m < 2; m++)
  877.             for (n = 0; n < MAX_VEC; n++) {
  878.                 unsigned delete = random() & 1;
  879.                 char *name = delete ? "delete" : "insert";
  880.                 int ok;
  881.  
  882.                 sprintf(buffer, "%d", vector[n]);
  883.                 printf("** random %s (%s)\n", name, buffer);
  884.                 temp.bi_key = buffer;
  885.                 if (delete)
  886.                     ok = btree_delete(&text_tree, buffer);
  887.                 else
  888.                     ok = btree_insert(&text_tree, &temp) != 0;
  889.                 if (!btree_verify(&text_tree, RLINK(&(text_tree.head)))) {
  890.                     printf("OOPS: Random %s-verify '%s' failed\n", name, buffer);
  891.                     btree_printf(&text_tree);
  892.                     return (1);
  893.                 }
  894.                 printf("** result: %d\n", ok);
  895.             }
  896.             break;
  897.         case 'q':
  898.             done = 1;
  899.             break;
  900.         case '#':
  901.             break;
  902.         }
  903.         btree_verify(&text_tree, RLINK(&(text_tree.head)));
  904.     }
  905.     btree_freeup(&text_tree);
  906.  
  907.     printf("done!\n\n");
  908.     return 0;
  909. }
  910. #endif /* DEBUG_BTREE >= BTREE_DRIVER */
  911.  
  912. #endif /* DEBUG_BTREE */
  913.