home *** CD-ROM | disk | FTP | other *** search
/ DP Tool Club 18 / CD_ASCQ_18_111294_W.iso / dos / prg / c / ms_sh23 / src / sh12.c < prev    next >
C/C++ Source or Header  |  1994-08-26  |  18KB  |  724 lines
  1. /*
  2.  * MS-DOS SHELL - TSEARCH functions
  3.  *
  4.  * MS-DOS SHELL - Copyright (c) 1990,4 Data Logic Limited
  5.  *
  6.  * This code is subject to the following copyright restrictions.  The
  7.  * code for the extended (non BASIC) tsearch.3 functions is based on code
  8.  * written by Peter Valkenburg & Michiel Huisjes.  The following copyright
  9.  * conditions apply:
  10.  *
  11.  * 1.  Redistribution and use in source and binary forms are permitted
  12.  *     provided that the above copyright notice is duplicated in the
  13.  *     source form and the copyright notice in file sh6.c is displayed
  14.  *     on entry to the program.
  15.  *
  16.  * 2.  The sources (or parts thereof) or objects generated from the sources
  17.  *     (or parts of sources) cannot be sold under any circumstances.
  18.  *
  19.  *    $Header: /usr/users/istewart/shell/sh2.3/Release/RCS/sh12.c,v 2.7 1994/08/25 20:49:11 istewart Exp $
  20.  *
  21.  *    $Log: sh12.c,v $
  22.  * Revision 2.7  1994/08/25  20:49:11  istewart
  23.  * MS Shell 2.3 Release
  24.  *
  25.  * Revision 2.6  1994/02/01  10:25:20  istewart
  26.  * Release 2.3 Beta 2, including first NT port
  27.  *
  28.  * Revision 2.5  1993/08/25  16:03:57  istewart
  29.  * Beta 225 - see Notes file
  30.  *
  31.  * Revision 2.4  1993/07/02  10:21:35  istewart
  32.  * 224 Beta fixes
  33.  *
  34.  * Revision 2.3  1993/06/02  09:52:35  istewart
  35.  * Beta 223 Updates - see Notes file
  36.  *
  37.  * Revision 2.2  1993/02/16  16:03:15  istewart
  38.  * Beta 2.22 Release
  39.  *
  40.  * Revision 2.1  1993/01/26  18:35:09  istewart
  41.  * Release 2.2 beta 0
  42.  *
  43.  * Revision 2.0  1992/07/10  10:52:48  istewart
  44.  * 211 Beta updates
  45.  *
  46.  *
  47.  * Start of original notes for the non-BASIC tsearch functions.
  48.  *
  49.  * "tsearch.c", Peter Valkenburg & Michiel Huisjes, november '89.
  50.  *
  51.  * Standard tsearch(3) compatible implementation of AVL height balanced trees.
  52.  * Performance is slightly better than SUN OS tsearch(3) for average case
  53.  * delete/add operations, but worst case behaviour (i.e. when ordinary trees
  54.  * get unbalanced) is much better.  Tsearch/tdelete/tfind run in O(2log(n)),
  55.  * twalk in O(n), where n is the size of binary tree.
  56.  *
  57.  * Entry points:
  58.  *
  59.  *    _ts_NODE_t *tsearch((void *)key, (_ts_NODE_t **)rootp, int (*compar)());
  60.  *    _ts_NODE_t *tdelete((void *)key, (_ts_NODE_t **)rootp, int (*compar)());
  61.  *    _ts_NODE_t *tfind((void *)key, (_ts_NODE_t **)rootp, int (*compar)());
  62.  *    void twalk((_ts_NODE_t *root), void (*action)());
  63.  *
  64.  * Here key is a pointer to any datum (to be) held in the tree rooted by *rootp
  65.  * or root.  Keys are compared by calling compar, which gets two key arguments
  66.  * and should return a value < 0, 0, or > 0, if the first parameter is to be
  67.  * considered less than , equal to, or greater than the second, respectively.
  68.  * Users can declare type (_ts_NODE_t *) as (char *) and (_ts_NODE_t **) as
  69.  * (char **).  The return values of tsearch/tdelete/tfind can be used as
  70.  * pointers to the key pointers of their _ts_NODE_t, by casting them to
  71.  * (char **).
  72.  *
  73.  * See manual page tsearch(3) for more extensive user documentation.
  74.  */
  75.  
  76. #include <sys/types.h>
  77. #include <sys/stat.h>
  78. #include <stdio.h>
  79. #include <string.h>
  80. #include <setjmp.h>
  81. #include <unistd.h>
  82. #include <limits.h>
  83. #include "sh.h"
  84.  
  85. /*
  86.  * Type for doubly linked AVL tree.
  87.  */
  88.  
  89. #ifndef BASIC
  90. typedef struct node_s {
  91.     void        *key;        /* ptr to datum            */
  92.     struct node_s    *parent;    /* ptr to parent ancestor    */
  93.     struct node_s    *sibls[2];    /* ptrs to L/R siblings        */
  94.     int            balance;    /* balance value (-1, 0 or +1)    */
  95. } _ts_NODE_t;
  96.  
  97. typedef int        _SibIndex_t;    /* type for indexing siblings    */
  98. #define    L        ((_SibIndex_t) 0)
  99. #define    R        ((_SibIndex_t) 1)
  100.  
  101. #define    LEFT        sibls[L]/* left sibling pointer _ts_NODE_t field */
  102. #define    RIGHT        sibls[R]/* right sibling pointer _ts_NODE_t field */
  103.  
  104. /*
  105.  * Direction gives direction in which child _ts_NODE_t c is under parent
  106.  * _ts_NODE_t p.
  107.  */
  108.  
  109. #define    direction(p, c)    ((_SibIndex_t) ((p)->RIGHT == (c)))
  110.  
  111. /*
  112.  * Cmp_dir gives direction corresponding with compare value v (R iff v > 0).
  113.  */
  114.  
  115. #define    cmp_dir(v)    ((_SibIndex_t) ((v) > 0))
  116.  
  117. /*
  118.  * Siblingp yields ptr to left (d == L) or right (d == R) child of _ts_NODE_t n.
  119.  */
  120.  
  121. #define    siblingp(n, d)    ((n)->sibls + (d))
  122.  
  123. /*
  124.  * Parentp yields ptr to parent's ptr to _ts_NODE_t n, or root ptr r if n is 0.
  125.  */
  126.  
  127. #define    parentp(r, n)    ((n)->parent == (_ts_NODE_t *)NULL ? (r) : \
  128.                  siblingp((n)->parent, direction((n)->parent, (n))))
  129.  
  130. /*
  131.  * Dir_bal yields balance value corresponding to _SibIndex_t d.
  132.  */
  133.  
  134. #define    dir_bal(d)    ((d) == L ? -1 : 1)
  135.  
  136. static _ts_NODE_t    *balance (_ts_NODE_t **, _ts_NODE_t *, int);
  137. static _ts_NODE_t    *single_rotation (_ts_NODE_t **, _ts_NODE_t *,
  138.                       _ts_NODE_t *, _SibIndex_t);
  139. static _ts_NODE_t    *double_rotation (_ts_NODE_t **, _ts_NODE_t *,
  140.                       _ts_NODE_t *, _SibIndex_t);
  141.  
  142. /*
  143.  * Tsearch adds node key to tree rooted by *rootp, using compar for
  144.  * comparing elements.  It returns the pointer to the _ts_NODE_t in which
  145.  * the (possibly already existing) key pointer resides.
  146.  */
  147.  
  148. void    *tsearch (key, root, compar)
  149. void    *key;
  150. void    **root;
  151. int    (*compar)(const void *, const void *);
  152. {
  153.     register _ts_NODE_t        *parent, *child;
  154.     _ts_NODE_t            *nnode;
  155.     register _SibIndex_t    d;
  156.     register int        cmp;
  157.     register _ts_NODE_t        **rootp = (_ts_NODE_t **)root;
  158.  
  159.     if (rootp == (_ts_NODE_t **)NULL)
  160.     return (_ts_NODE_t *)NULL;
  161.  
  162.     /* find place where key should go */
  163.  
  164.     parent = (_ts_NODE_t *)NULL;
  165.     child = *rootp;
  166.  
  167.     while (child != (_ts_NODE_t *)NULL)
  168.     {
  169.     if ((cmp = compar (key, child->key)) == 0)
  170.         return child;
  171.  
  172.     parent = child;
  173.     child = *siblingp (child, cmp_dir (cmp));
  174.     }
  175.  
  176.     /* create new node and set its parent's sibling pointer */
  177.  
  178.     nnode = (_ts_NODE_t *) GetAllocatedSpace (sizeof (_ts_NODE_t));
  179.  
  180.     if (nnode == (_ts_NODE_t *)NULL)
  181.     return (_ts_NODE_t *)NULL;
  182.  
  183.     SetMemoryAreaNumber ((void *) nnode, 0);
  184.     nnode->key = key;
  185.     nnode->balance = 0;
  186.     nnode->parent = parent;
  187.     nnode->LEFT = nnode->RIGHT = (_ts_NODE_t *)NULL;
  188.  
  189.     if (parent == (_ts_NODE_t *)NULL)
  190.     {
  191.     *rootp = nnode;
  192.     return nnode;            /* just created tree */
  193.     }
  194.  
  195.     *siblingp (parent, cmp_dir(cmp)) = nnode;
  196.     child = nnode;
  197.  
  198. /*
  199.  * Back up until tree is balanced.  This is achieved when either
  200.  * the tree is balanced by rotation or a node's balance becomes 0.
  201.  */
  202.  
  203.     do
  204.     {
  205.     d = direction (parent, child);
  206.  
  207.     if (parent->balance == dir_bal(d))
  208.     {
  209.         (void) balance (rootp, parent, d);
  210.         return nnode;
  211.     }
  212.  
  213.     else if ((parent->balance += dir_bal(d)) == 0)
  214.         return nnode;
  215.  
  216.     child = parent;
  217.     parent = parent->parent;
  218.  
  219.     } while (parent != (_ts_NODE_t *)NULL);
  220.  
  221.     return nnode;
  222. }
  223.  
  224. /*
  225.  * Tdelete removes key from the tree rooted by *rootp, using compar for
  226.  * comparing elements.  It returns the pointer to the _ts_NODE_t that was the
  227.  * parent of the _ts_NODE_t that contained the key pointer, 0 if it did not exist.
  228.  */
  229.  
  230. void    *tdelete (key, root, compar)
  231. void    *key;
  232. void     **root;
  233. int    (*compar)(const void *, const void *);
  234. {
  235.     register _ts_NODE_t        *parent, *child;
  236.     _ts_NODE_t            *dnode, *dparent;
  237.     register _SibIndex_t    d;
  238.     register int        cont_bal;
  239.     register int        cmp;
  240.     register _ts_NODE_t        **rootp = (_ts_NODE_t **)root;
  241.  
  242.     if (rootp == (_ts_NODE_t **)NULL)
  243.     return (void *)NULL;
  244.  
  245. /* find node to delete */
  246.  
  247.     child = *rootp;
  248.  
  249.     while (child != (_ts_NODE_t *)NULL)
  250.     {
  251.     if ((cmp = compar (key, child->key)) == 0)
  252.         break;
  253.  
  254.     child = *siblingp (child, cmp_dir (cmp));
  255.     }
  256.  
  257.     if (child == (_ts_NODE_t *)NULL)
  258.     return (void *)NULL;        /* key not in tree */
  259.  
  260. /* the node was found; get its successor (if any) to replace it */
  261.  
  262.     dnode = child;
  263.     dparent = dnode->parent;
  264.     child = child->RIGHT;
  265.  
  266.     if (child == (_ts_NODE_t *)NULL)        /* no successor for key */
  267.     {
  268.     if ((child = dnode->LEFT) != (_ts_NODE_t *)NULL)
  269.         child->parent = dparent;    /* set new parent */
  270.  
  271.     if (dparent == (_ts_NODE_t *)NULL)
  272.     {
  273.         ReleaseMemoryCell ((void *) dnode);
  274.         *rootp = child;
  275.         return (void *)NULL;    /* just deleted the root */
  276.     }
  277.  
  278.     d = direction (dparent, dnode);    /* for back up */
  279.     *siblingp(dparent, d) = child;    /* replace by left child */
  280.     ReleaseMemoryCell ((void *) dnode);
  281.     parent = dparent;
  282.     }
  283.  
  284.     else                /* key's successor exists */
  285.     {
  286.     while (child->LEFT != (_ts_NODE_t *)NULL)
  287.         child = child->LEFT;
  288.  
  289.     parent = child->parent;
  290.     d = direction(parent, child);        /* for back up */
  291.     *siblingp(parent, d) = child->RIGHT;
  292.  
  293.     if (child->RIGHT != (_ts_NODE_t *)NULL)
  294.         child->RIGHT->parent = parent;    /* set new parent */
  295.  
  296.     dnode->key = child->key;    /* successor replaces key */
  297.     ReleaseMemoryCell ((void *) child);
  298.     }
  299.  
  300. /*
  301.  * Back up until tree is balanced.  This is achieved when either the tree is
  302.  * balanced by rotation but not made shorter, or a node's balance was 0 before
  303.  * deletion.
  304.  */
  305.  
  306.     do
  307.     {
  308.     if (parent->balance == dir_bal(!d))
  309.     {
  310.         cont_bal = ((*siblingp(parent, !d))->balance != 0);
  311.         parent = balance(rootp, parent, !d);
  312.     }
  313.  
  314.     else
  315.     {
  316.         cont_bal = (parent->balance != 0);
  317.         parent->balance += dir_bal(!d);
  318.     }
  319.  
  320.     child = parent;
  321.  
  322.     if ((parent = parent->parent) == (_ts_NODE_t *)NULL)
  323.         return dparent;        /* we reached the root */
  324.  
  325.     d = direction(parent, child);
  326.  
  327.     } while (cont_bal);
  328.  
  329.     return dparent;
  330. }
  331.  
  332. /*
  333.  * Balance the subtree rooted at sb that has become to heavy on side d.
  334.  * Also adjusts sibling pointer of the parent of sb, or *rootp if sb is
  335.  * the top of the entire tree.
  336.  */
  337.  
  338. static _ts_NODE_t    *balance(rootp, sb, d)
  339. _ts_NODE_t        **rootp;
  340. _ts_NODE_t        *sb;
  341. _SibIndex_t        d;
  342. {
  343.     _ts_NODE_t    *sb_next = *siblingp (sb, d);
  344.  
  345.     if (sb_next->balance == -dir_bal(d))
  346.     return double_rotation (rootp, sb, sb_next, d);
  347.  
  348.     else
  349.     return single_rotation (rootp, sb, sb_next, d);
  350. }
  351.  
  352. /*
  353.  * Balance the subtree rooted at sb that has become to heavy on side d
  354.  * by single rotation of sb and sb_next.
  355.  * Also adjusts sibling pointer of the parent of sb, or *rootp if sb is
  356.  * the top of the entire tree.
  357.  *
  358.  *        sb        sb_next        Single rotation: Adding x or
  359.  *           /  \           /       \    deleting under 3 caused
  360.  *    sb_next       3          1        sb    rotation.  Same holds for mirror
  361.  *     /       \          |           /  \    image.  Single_rotation returns
  362.  *    1            2    ==>   x       2    3    top of new balanced tree.
  363.  *    |        |              |
  364.  *    x        y              y
  365.  */
  366.  
  367. static _ts_NODE_t    *single_rotation (rootp, sb, sb_next, d)
  368. _ts_NODE_t        **rootp;
  369. register _ts_NODE_t    *sb, *sb_next;
  370. register _SibIndex_t    d;
  371. {
  372.     *siblingp (sb, d)       = *siblingp(sb_next, !d);
  373.     *siblingp (sb_next, !d) = sb;
  374.     sb->balance             -= sb_next->balance;
  375.     sb_next->balance        = -sb->balance;
  376.     *parentp (rootp, sb)    = sb_next;
  377.     sb_next->parent         = sb->parent;
  378.     sb->parent              = sb_next;
  379.  
  380.     if (*siblingp (sb, d) != (_ts_NODE_t *)NULL)
  381.     (*siblingp (sb, d))->parent = sb;
  382.  
  383.     return sb_next;
  384. }
  385.  
  386. /*
  387.  * Balance the subtree rooted at sb that has become to heavy on side d
  388.  * by double rotation of sb and sb_next.
  389.  * Also adjusts sibling pointer of the parent of sb, or *rootp if sb is
  390.  * the top of the entire tree.
  391.  *
  392.  *        sb            sb_next2       Double rotation: Adding x or
  393.  *           /  \               /        \       x', or deleting under 4
  394.  *    sb_next    \        sb_next         sb    caused rotation. Same holds
  395.  *     /       \    \           /       \    /  \   for the mirror image.
  396.  *    1   sb_next2   4     ==>  1        2  3    4  Double_rotation returns top
  397.  *       /        \            |  |       of new balanced tree.
  398.  *      2          3            x  x'
  399.  *      |         |
  400.  *      x       x'
  401.  */
  402.  
  403. static _ts_NODE_t    *double_rotation (rootp, sb, sb_next, d)
  404. _ts_NODE_t        **rootp;
  405. register _ts_NODE_t    *sb, *sb_next;
  406. register _SibIndex_t    d;
  407. {
  408.     register _ts_NODE_t *sb_next2 = *siblingp(sb_next, !d);
  409.  
  410.     *siblingp (sb_next, !d)  = *siblingp (sb_next2, d);
  411.     *siblingp (sb, d)        = *siblingp (sb_next2, !d);
  412.     *siblingp (sb_next2, d)  = sb_next;
  413.     *siblingp (sb_next2, !d) = sb;
  414.  
  415.     if (sb_next2->balance == sb_next->balance)
  416.     sb_next->balance = -sb_next->balance;
  417.  
  418.     else
  419.     sb_next->balance = 0;
  420.  
  421.     if (sb_next2->balance == sb->balance)
  422.     sb->balance = -sb->balance;
  423.  
  424.     else
  425.     sb->balance = 0;
  426.  
  427.     sb_next2->balance    = 0;
  428.     *parentp (rootp, sb) = sb_next2;
  429.     sb_next2->parent     = sb->parent;
  430.     sb->parent           = sb_next->parent = sb_next2;
  431.  
  432.     if (*siblingp (sb_next, !d) != (_ts_NODE_t *)NULL)
  433.     (*siblingp (sb_next, !d))->parent = sb_next;
  434.  
  435.     if (*siblingp (sb, d) != (_ts_NODE_t *)NULL)
  436.     (*siblingp (sb, d))->parent = sb;
  437.  
  438.     return sb_next2;
  439. }
  440.  
  441. /*
  442.  * Tfind searches node key in the tree rooted by *rootp, using compar for
  443.  * comparing elements.  It returns the pointer to the _ts_NODE_t in which
  444.  * the key pointer resides, or 0 if key is not present.
  445.  */
  446.  
  447. void    *tfind(key, root, compar)
  448. void    *key;
  449. void    **root;
  450. int    (*compar)(const void *, const void *);
  451. {
  452.     register _ts_NODE_t    *node;
  453.     _ts_NODE_t        **rootp = (_ts_NODE_t **)root;
  454.     register int    cmp;
  455.  
  456.     if (rootp == (_ts_NODE_t **)NULL)
  457.     return (void *)NULL;
  458.  
  459.     node = *rootp;
  460.     while (node != (_ts_NODE_t *)NULL)
  461.     {
  462.     if ((cmp = compar (key, node->key)) == 0)
  463.         return node;
  464.  
  465.     node = *siblingp (node, cmp_dir (cmp));
  466.     }
  467.  
  468.     return (void *)NULL;
  469. }
  470.  
  471. /*
  472.  * Twalk walks the tree rooted by node, from top to bottom and left to right,
  473.  * calling action with the _ts_NODE_t pointer, visit order, and level in the tree
  474.  * (0 is root).  Leafs are visited only once and action is then called with
  475.  * `leaf' as the second parameter.  For nodes with children action is called
  476.  * three times with visit order parameter `preorder' before, `postorder' in
  477.  * between, and `endorder' after visiting the nodes children.
  478.  */
  479.  
  480. void        twalk (start, action)
  481. const void    *start;
  482. register void    (*action)(const void *, VISIT, int);
  483. {
  484.     register VISIT    visit;
  485.     register int    level;
  486.     register _ts_NODE_t    *node = (_ts_NODE_t *)start;
  487.  
  488.     if ((node == (_ts_NODE_t *)NULL) || (action == 0))
  489.     return;
  490.  
  491. /* run down tree from top to bottom, left to right */
  492.  
  493.     visit = preorder;
  494.     level = 0;
  495.  
  496.     while (node != (_ts_NODE_t *)NULL)
  497.     {
  498.     if ((visit == preorder) &&
  499.         (node->LEFT == (_ts_NODE_t *)NULL) &&
  500.         (node->RIGHT == (_ts_NODE_t *)NULL))
  501.         visit = leaf;        /* node turns out to be leaf */
  502.  
  503.     action (node, visit, level);
  504.  
  505.     switch (visit)
  506.     {
  507.         case preorder:            /* before visiting left child */
  508.         if (node->LEFT != (_ts_NODE_t *)NULL)
  509.         {
  510.             node = node->LEFT;
  511.             level++;
  512.         }
  513.  
  514.         else
  515.             visit = postorder;
  516.  
  517.         break;
  518.  
  519.         case postorder:        /* between visiting children */
  520.         if (node->RIGHT != (_ts_NODE_t *)NULL)
  521.         {
  522.             node = node->RIGHT;
  523.             visit = preorder;
  524.             level++;
  525.         }
  526.  
  527.         else
  528.             visit = endorder;
  529.  
  530.         break;
  531.  
  532.         case endorder:        /* after visiting children */
  533.         case leaf:            /* node has no children */
  534.         if (node->parent != (_ts_NODE_t *)NULL)
  535.         {
  536.             if (direction (node->parent, node) == L)
  537.             visit = postorder;
  538.  
  539.             else
  540.             visit = endorder;
  541.         }
  542.  
  543.         node = node->parent;
  544.         level--;
  545.  
  546.         break;
  547.     }
  548.     }
  549. }
  550. #else
  551.  
  552. /*
  553.  * Definition for t.... functions
  554.  */
  555.  
  556. typedef struct _t_node {
  557.     char        *key;
  558.     struct _t_node    *llink;
  559.     struct _t_node    *rlink;
  560. } _t_NODE;
  561.  
  562. static void        _twalk (_t_NODE *,
  563.                 void (*)(const void *, VISIT, int), int);
  564. /*
  565.  * Basic Tree Processing Functions
  566.  */
  567.  
  568. /*
  569.  * Delete node with key
  570.  */
  571.  
  572. void    *tdelete (key, rootcp, compar)
  573. void    *key;
  574. void    **rootcp;
  575. int    (*compar)(const void *, const void *);
  576. {
  577.     _t_NODE        *p;        /* Parent of node to be deleted */
  578.     register _t_NODE    *q;        /* Successor node        */
  579.     register _t_NODE    *r;        /* Right son node        */
  580.     int            ans;        /* Result of comparison        */
  581.     register _t_NODE    **rootp = (_t_NODE **)rootcp;
  582.  
  583.     if ((rootp == (_t_NODE **)NULL) || ((p = *rootp) == (_t_NODE *)NULL))
  584.     return (void *)NULL;
  585.  
  586.     while ((ans = (*compar)(key, (*rootp)->key)) != 0)
  587.     {
  588.     p = *rootp;
  589.     rootp = (ans < 0) ? &(*rootp)->llink : &(*rootp)->rlink;
  590.  
  591.     if (*rootp == (_t_NODE *)NULL)
  592.         return (void *)NULL;
  593.     }
  594.  
  595.     r = (*rootp)->rlink;
  596.  
  597.     if ((q = (*rootp)->llink) == (_t_NODE *)NULL)
  598.         q = r;
  599.  
  600.     else if (r != (_t_NODE *)NULL)
  601.     {
  602.     if (r->llink == (_t_NODE *)NULL)
  603.     {
  604.         r->llink = q;
  605.         q = r;
  606.     }
  607.  
  608.     else
  609.     {
  610.         for (q = r->llink; q->llink != (_t_NODE *)NULL; q = r->llink)
  611.         r = q;
  612.  
  613.         r->llink = q->rlink;
  614.         q->llink = (*rootp)->llink;
  615.         q->rlink = (*rootp)->rlink;
  616.     }
  617.     }
  618.  
  619.     ReleaseMemoryCell ((char *) *rootp);
  620.     *rootp = q;
  621.     return (void *)p;
  622. }
  623.  
  624. /*
  625.  * Find node with key
  626.  */
  627.  
  628. void    *tfind (key, rootcp, compar)
  629. void    *key;            /* Key to be located            */
  630. void    **rootcp;        /* Address of the root of the tree    */
  631. int    (*compar)(const void *, const void *);
  632. {
  633.     register _t_NODE    **rootp = (_t_NODE **)rootcp;
  634.  
  635.     if (rootp == (_t_NODE **)NULL)
  636.     return (void *)NULL;
  637.  
  638.     while (*rootp != (_t_NODE *)NULL)
  639.     {
  640.     int    r = (*compar)(key, (*rootp)->key);
  641.  
  642.     if (r == 0)
  643.         return (void *)*rootp;
  644.  
  645.     rootp = (r < 0) ? &(*rootp)->llink : &(*rootp)->rlink;
  646.     }
  647.  
  648.     return (void *)NULL;
  649. }
  650.  
  651. /*
  652.  * Search for a node with key key and add it if appropriate
  653.  */
  654.  
  655. void    *tsearch (key, rootcp, compar)
  656. void    *key;            /* Key to be located            */
  657. void    **rootcp;        /* Address of the root of the tree    */
  658. int    (*compar)(const void *, const void *);
  659. {
  660.     register _t_NODE    **rootp = (_t_NODE **)rootcp;
  661.     register _t_NODE    *q;    /* New node if key not found */
  662.  
  663.     if (rootp == (_t_NODE **)NULL)
  664.     return (void *)NULL;
  665.  
  666.     while (*rootp != (_t_NODE *)NULL)
  667.     {
  668.     int    r = (*compar)(key, (*rootp)->key);
  669.  
  670.     if (r == 0)
  671.         return (void *)*rootp;
  672.  
  673.     rootp = (r < 0) ? &(*rootp)->llink : &(*rootp)->rlink;
  674.     }
  675.  
  676.     q = (_t_NODE *) GetAllocatedSpace (sizeof (_t_NODE));
  677.  
  678.     if (q != (_t_NODE *)NULL)
  679.     {
  680.         SetMemoryAreaNumber ((void *)q, 0);
  681.     *rootp = q;
  682.     q->key = key;
  683.     q->llink = q->rlink = (_t_NODE *)NULL;
  684.     }
  685.  
  686.     return (void *)q;
  687. }
  688.  
  689.  
  690. /* Walk the nodes of a tree */
  691.  
  692. void        twalk (root, action)
  693. const void    *root;            /* Root of the tree to be walked */
  694. void        (*action)(const void *, VISIT, int);
  695. {
  696.     if ((root != (char *)NULL) && (action != NULL))
  697.     _twalk (root, action, 0);
  698. }
  699.  
  700. static void        _twalk (root, action, level)
  701. register _t_NODE    *root;
  702. register void        (*action)(const void *, VISIT, int);
  703. register int        level;
  704. {
  705.     if (root->llink == (_t_NODE *)NULL && root->rlink == NULL)
  706.     (*action)(root, leaf, level);
  707.  
  708.     else
  709.     {
  710.     (*action)(root, preorder, level);
  711.  
  712.     if (root->llink != (_t_NODE *)NULL)
  713.         _twalk (root->llink, action, level + 1);
  714.  
  715.     (*action)(root, postorder, level);
  716.  
  717.     if (root->rlink != (_t_NODE *)NULL)
  718.         _twalk (root->rlink, action, level + 1);
  719.  
  720.     (*action)(root, endorder, level);
  721.     }
  722. }
  723. #endif
  724.