home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / xwphescr.zip / XWPH0208.ZIP / src / helpers / tree.c < prev    next >
Text File  |  2002-08-08  |  29KB  |  1,024 lines
  1.  
  2. /*
  3.  *@@sourcefile tree.c:
  4.  *      contains helper functions for maintaining 'Red-Black' balanced
  5.  *      binary trees.
  6.  *
  7.  *      Usage: All C programs; not OS/2-specific.
  8.  *
  9.  *      Function prefixes (new with V0.81):
  10.  *      --  tree*    tree helper functions
  11.  *
  12.  *      <B>Introduction</B>
  13.  *
  14.  *      While linked lists have "next" and "previous" pointers (which
  15.  *      makes them one-dimensional), trees have a two-dimensional layout:
  16.  *      each tree node has one "parent" and two "children" which are
  17.  *      called "left" and "right". The "left" pointer will always lead
  18.  *      to a tree node that is "less than" its parent node, while the
  19.  *      "right" pointer will lead to a node that is "greater than"
  20.  *      its parent. What is considered "less" or "greater" for sorting
  21.  *      is determined by a comparison callback to be supplied by the
  22.  *      tree functions' caller. The "leafs" of the tree will have
  23.  *      null left and right pointers.
  24.  *
  25.  *      For this, the functions here use the TREE structure. The most
  26.  *      important member here is the "ulKey" field which is used for
  27.  *      sorting (passed to the compare callbacks). Since the tree
  28.  *      functions do no memory allocation, the caller can easily
  29.  *      use an extended TREE structure with additional fields as
  30.  *      long as the first member is the TREE structure. See below.
  31.  *
  32.  *      Each tree must have a "root" item, from which all other tree
  33.  *      nodes can eventually be reached by following the "left" and
  34.  *      "right" pointers. The root node is the only node whose
  35.  *      parent is null.
  36.  *
  37.  *      <B>Trees vs. linked lists</B>
  38.  *
  39.  *      Compared to linked lists (as implemented by linklist.c),
  40.  *      trees allow for much faster searching, since they are
  41.  *      always sorted.
  42.  *
  43.  *      Take an array of numbers, and assume you'd need to find
  44.  *      the array node with the specified number.
  45.  *
  46.  *      With a (sorted) linked list, this would look like:
  47.  *
  48.  +          4  -->  7  -->  16  -->  20  -->  37  -->  38  -->  43
  49.  *
  50.  *      Searching for "43" would need 6 iterations.
  51.  *
  52.  *      With a binary tree, this would instead look like:
  53.  *
  54.  +                       20
  55.  +                     /    \
  56.  +                    7      38
  57.  +                   / \    /  \
  58.  +                  4  16  37   43
  59.  +                 / \ / \ / \ / \
  60.  *
  61.  *      Searching for "43" would need 2 iterations only.
  62.  *
  63.  *      Assuming a linked list contains N items, then searching a
  64.  *      linked list for an item will take an average of N/2 comparisons
  65.  *      and even N comparisons if the item cannot be found (unless
  66.  *      you keep the list sorted, but linklist.c doesn't do this).
  67.  *
  68.  *      According to "Algorithms in C", a search in a balanced
  69.  *      "red-black" binary tree takes about lg N comparisons on
  70.  *      average, and insertions take less than one rotation on
  71.  *      average.
  72.  *
  73.  *      Differences compared to linklist.c:
  74.  *
  75.  *      -- A tree is always sorted.
  76.  *
  77.  *      -- Trees are considerably slower when inserting and removing
  78.  *         nodes because the tree has to be rebalanced every time
  79.  *         a node changes. By contrast, trees are much faster finding
  80.  *         nodes because the tree is always sorted.
  81.  *
  82.  *      -- As opposed to a LISTNODE, the TREE structure (which
  83.  *         represents a tree node) does not contain a data pointer,
  84.  *         as said above. The caller must do all memory management.
  85.  *
  86.  *      <B>Background</B>
  87.  *
  88.  *      Now, a "red-black balanced binary tree" means the following:
  89.  *
  90.  *      -- We have "binary" trees. That is, there are only "left" and
  91.  *         "right" pointers. (Other algorithms allow tree nodes to
  92.  *         have more than two children, but binary trees are usually
  93.  *         more efficient.)
  94.  *
  95.  *      -- The tree is always "balanced". The tree gets reordered
  96.  *         when items are added/removed to ensure that all paths
  97.  *         through the tree are approximately the same length.
  98.  *         This avoids the "worst case" scenario that some paths
  99.  *         grow terribly long while others remain short ("degenerated"
  100.  *         trees), which can make searching very inefficient:
  101.  *
  102.  +                  4
  103.  +                 / \
  104.  +                    7
  105.  +                   / \
  106.  +                      16
  107.  +                     / \
  108.  +                        20
  109.  +                       / \
  110.  +                          37
  111.  +                         / \
  112.  +                            43
  113.  +                           /  \
  114.  *
  115.  *      -- Fully balanced trees can be quite expensive because on
  116.  *         every insertion or deletion, the tree nodes must be rotated.
  117.  *         By contrast, "Red-black" binary balanced trees contain
  118.  *         an additional bit in each node which marks the node as
  119.  *         either red or black. This bit is used only for efficient
  120.  *         rebalancing when inserting or deleting nodes.
  121.  *
  122.  *         I don't fully understand why this works, but if you really
  123.  *         care, this is explained at
  124.  *         "http://www.eli.sdsu.edu/courses/fall96/cs660/notes/redBlack/redBlack.html".
  125.  *
  126.  *      In other words, as opposed to regular binary trees, RB trees
  127.  *      are not _fully_ balanced, but they are _mostly_ balanced. With
  128.  *      respect to efficiency, RB trees are thus a good compromise:
  129.  *
  130.  *      -- Completely unbalanced trees are efficient when inserting,
  131.  *         but can have a terrible worst case when searching.
  132.  *
  133.  *      -- RB trees are still acceptably efficient when inserting
  134.  *         and quite efficient when searching.
  135.  *         A RB tree with n internal nodes has a height of at most
  136.  *         2lg(n+1). Both average and worst-case search time is O(lg n).
  137.  *
  138.  *      -- Fully balanced binary trees are inefficient when inserting
  139.  *         but most efficient when searching.
  140.  *
  141.  *      So as long as you are sure that trees are more efficient
  142.  *      in your situation than a linked list in the first place, use
  143.  *      these RB trees instead of linked lists.
  144.  *
  145.  *      <B>Using binary trees</B>
  146.  *
  147.  *      You can use any structure as elements in a tree, provided
  148.  *      that the first member in the structure is a TREE structure
  149.  *      (i.e. it has the left, right, parent, and color members).
  150.  *      Each TREE node has a ulKey field which is used for
  151.  *      comparing tree nodes and thus determines the location of
  152.  *      the node in the tree.
  153.  *
  154.  *      The tree functions don't care what follows in each TREE
  155.  *      node since they do not manage any memory themselves.
  156.  *      So the implementation here is slightly different from the
  157.  *      linked lists in linklist.c, because the LISTNODE structs
  158.  *      only have pointers to the data. By contrast, the TREE structs
  159.  *      are expected to contain the data themselves.
  160.  *
  161.  *      Initialize the root of the tree with treeInit(). Then
  162.  *      add nodes to the tree with treeInsert() and remove nodes
  163.  *      with treeDelete(). See below for a sample.
  164.  *
  165.  *      You can test whether a tree is empty by comparing its
  166.  *      root with LEAF.
  167.  *
  168.  *      For most tree* functions, you must specify a comparison
  169.  *      function which will always receive two "key" parameters
  170.  *      to compare. This must be declared as
  171.  +
  172.  +          int TREEENTRY fnCompare(ULONG ul1, ULONG ul2);
  173.  *
  174.  *      This will receive two TREE.ulKey members (whose meaning
  175.  *      is defined by your implementation) and must return
  176.  *
  177.  *      -- something < 0: ul1 < ul2
  178.  *      -- 0: ul1 == ul2
  179.  *      -- something > 1: ul1 > ul2
  180.  *
  181.  *      <B>Example</B>
  182.  *
  183.  *      A good example where trees are efficient would be the
  184.  *      case where you have "keyword=value" string pairs and
  185.  *      you frequently need to search for "keyword" to find
  186.  *      a "value". So "keyword" would be an ideal candidate for
  187.  *      the TREE.key field.
  188.  *
  189.  *      You'd then define your own tree nodes like this:
  190.  *
  191.  +          typedef struct _MYTREENODE
  192.  +          {
  193.  +              TREE        Tree;       // regular tree node, which has
  194.  +                                      // the ULONG "key" field; we'd
  195.  +                                      // use this as a const char*
  196.  +                                      // pointer to the keyword string
  197.  +              // here come the additional fields
  198.  +              // (whatever you need for your data)
  199.  +              const char  *pcszValue;
  200.  +
  201.  +          } MYTREENODE, *PMYTREENODE;
  202.  *
  203.  *      Initialize the tree root:
  204.  *
  205.  +          TREE *root;
  206.  +          treeInit(&root);
  207.  *
  208.  *      To add a new "keyword=value" pair, do this:
  209.  *
  210.  +          PMYTREENODE AddNode(TREE **root,
  211.  +                              const char *pcszKeyword,
  212.  +                              const char *pcszValue)
  213.  +          {
  214.  +              PMYTREENODE p = (PMYTREENODE)malloc(sizeof(MYTREENODE));
  215.  +              p.Tree.ulKey = (ULONG)pcszKeyword;
  216.  +              p.pcszValue = pcszValue;
  217.  +              treeInsert(root,                // tree's root
  218.  +                         p,                   // new tree node
  219.  +                         fnCompare);          // comparison func
  220.  +              return (p);
  221.  +          }
  222.  *
  223.  *      Your comparison func receives two ulKey values to compare,
  224.  *      which in this case would be the typecast string pointers:
  225.  *
  226.  +          int TREEENTRY fnCompare(ULONG ul1, ULONG ul2)
  227.  +          {
  228.  +              return (strcmp((const char*)ul1,
  229.  +                             (const char*)ul2));
  230.  +          }
  231.  *
  232.  *      You can then use treeFind to very quickly find a node
  233.  *      with a specified ulKey member.
  234.  *
  235.  *      This file was new with V0.9.5 (2000-09-29) [umoeller].
  236.  *      With V0.9.13, all the code has been replaced with the public
  237.  *      domain code found at http://epaperpress.com/sortsearch/index.html
  238.  *      ("A compact guide to searching and sorting") by Thomas Niemann.
  239.  *      The old implementation from the Standard Function Library (SFL)
  240.  *      turned out to be buggy for large trees (more than 100 nodes).
  241.  *
  242.  *@@added V0.9.5 (2000-09-29) [umoeller]
  243.  *@@header "helpers\tree.h"
  244.  */
  245.  
  246. /*
  247.  *      Original coding by Thomas Niemann, placed in the public domain
  248.  *      (see http://epaperpress.com/sortsearch/index.html).
  249.  *
  250.  *      This implementation Copyright (C) 2001 Ulrich Möller.
  251.  *      This file is part of the "XWorkplace helpers" source package.
  252.  *      This is free software; you can redistribute it and/or modify
  253.  *      it under the terms of the GNU General Public License as published
  254.  *      by the Free Software Foundation, in version 2 as it comes in the
  255.  *      "COPYING" file of the XWorkplace main distribution.
  256.  *      This program is distributed in the hope that it will be useful,
  257.  *      but WITHOUT ANY WARRANTY; without even the implied warranty of
  258.  *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  259.  *      GNU General Public License for more details.
  260.  */
  261.  
  262. /*
  263.  *@@category: Helpers\C helpers\Red-black balanced binary trees
  264.  *      See tree.c.
  265.  */
  266.  
  267. #include "setup.h"
  268. #include "helpers\tree.h"
  269.  
  270. #define LEAF &sentinel           // all leafs are sentinels
  271. static TREE sentinel = { LEAF, LEAF, 0, BLACK};
  272.  
  273. /*
  274. A binary search tree is a red-black tree if:
  275.  
  276. 1. Every node is either red or black.
  277. 2. Every leaf (nil) is black.
  278. 3. If a node is red, then both its children are black.
  279. 4. Every simple path from a node to a descendant leaf contains the same
  280.    number of black nodes.
  281. */
  282.  
  283. /*
  284.  *@@ treeInit:
  285.  *      initializes the root of a tree.
  286.  *
  287.  *      If (plCount != NULL), *plCount is set to null also.
  288.  *      This same plCount pointer can then be passed to
  289.  *      treeInsert and treeDelete also to automatically
  290.  *      maintain a tree item count.
  291.  *
  292.  *@@changed V0.9.16 (2001-10-19) [umoeller]: added plCount
  293.  */
  294.  
  295. void treeInit(TREE **root,
  296.               PLONG plCount)            // out: tree item count, set to 0 (ptr can be NULL)
  297. {
  298.     *root = LEAF;
  299.  
  300.     if (plCount)
  301.         *plCount = 0;       // V0.9.16 (2001-10-19) [umoeller]
  302. }
  303.  
  304. /*
  305.  *@@ treeCompareKeys:
  306.  *      standard comparison func if the TREE.ulKey
  307.  *      field really is a ULONG.
  308.  */
  309.  
  310. int TREEENTRY treeCompareKeys(unsigned long  ul1, unsigned long ul2)
  311. {
  312.     if (ul1 < ul2)
  313.         return -1;
  314.  
  315.     if (ul1 > ul2)
  316.         return +1;
  317.  
  318.     return 0;
  319. }
  320.  
  321. /*
  322.  *@@ treeCompareStrings:
  323.  *      standard comparison func if the TREE.ulKey
  324.  *      field really is a string pointer (PCSZ).
  325.  *
  326.  *      This runs strcmp internally, but can handle
  327.  *      NULL pointers without crashing.
  328.  *
  329.  *@@added V0.9.16 (2001-09-29) [umoeller]
  330.  */
  331.  
  332. int TREEENTRY treeCompareStrings(unsigned long  ul1, unsigned long ul2)
  333. {
  334.     #define p1 (const char*)(ul1)
  335.     #define p2 (const char*)(ul2)
  336.  
  337.     if (p1 && p2)
  338.     {
  339.         int i = strcmp(p1, p2);
  340.         if (i < 0)
  341.             return -1;
  342.         if (i > 0)
  343.             return +1;
  344.     }
  345.     else if (p1)
  346.         // but p2 is NULL: p1 greater than p2 then
  347.         return +1;
  348.     else if (p2)
  349.         // but p1 is NULL: p1 less than p2 then
  350.         return -1;
  351.  
  352.     // return 0 if strcmp returned 0 above or both strings are NULL
  353.     return 0;
  354. }
  355.  
  356. /*
  357.  *@@ rotateLeft:
  358.  *      private function during rebalancing.
  359.  */
  360.  
  361. static void rotateLeft(TREE **root,
  362.                        TREE *x)
  363. {
  364.     // rotate node x to left
  365.  
  366.     TREE *y = x->right;
  367.  
  368.     // establish x->right link
  369.     x->right = y->left;
  370.     if (y->left != LEAF)
  371.         y->left->parent = x;
  372.  
  373.     // establish y->parent link
  374.     if (y != LEAF)
  375.         y->parent = x->parent;
  376.  
  377.     if (x->parent)
  378.     {
  379.         if (x == x->parent->left)
  380.             x->parent->left = y;
  381.         else
  382.             x->parent->right = y;
  383.     }
  384.     else
  385.         *root = y;
  386.  
  387.     // link x and y
  388.     y->left = x;
  389.     if (x != LEAF)
  390.         x->parent = y;
  391. }
  392.  
  393. /*
  394.  *@@ rotateRight:
  395.  *      private function during rebalancing.
  396.  */
  397.  
  398. static void rotateRight(TREE **root,
  399.                         TREE *x)
  400. {
  401.     // rotate node x to right
  402.  
  403.     TREE *y = x->left;
  404.  
  405.     // establish x->left link
  406.     x->left = y->right;
  407.     if (y->right != LEAF)
  408.         y->right->parent = x;
  409.  
  410.     // establish y->parent link
  411.     if (y != LEAF)
  412.         y->parent = x->parent;
  413.  
  414.     if (x->parent)
  415.     {
  416.         if (x == x->parent->right)
  417.             x->parent->right = y;
  418.         else
  419.             x->parent->left = y;
  420.     }
  421.     else
  422.         *root = y;
  423.  
  424.     // link x and y
  425.     y->right = x;
  426.     if (x != LEAF)
  427.         x->parent = y;
  428. }
  429.  
  430. /*
  431.  *@@ insertFixup:
  432.  *      private function during rebalancing.
  433.  */
  434.  
  435. static void insertFixup(TREE **root,
  436.                         TREE *x)
  437. {
  438.     // check Red-Black properties
  439.     while (    x != *root
  440.             && x->parent->color == RED
  441.           )
  442.     {
  443.         // we have a violation
  444.         if (x->parent == x->parent->parent->left)
  445.         {
  446.             TREE *y = x->parent->parent->right;
  447.             if (y->color == RED)
  448.             {
  449.                 // uncle is RED
  450.                 x->parent->color = BLACK;
  451.                 y->color = BLACK;
  452.                 x->parent->parent->color = RED;
  453.                 x = x->parent->parent;
  454.             }
  455.             else
  456.             {
  457.                 // uncle is BLACK
  458.                 if (x == x->parent->right)
  459.                 {
  460.                     // make x a left child
  461.                     x = x->parent;
  462.                     rotateLeft(root,
  463.                                x);
  464.                 }
  465.  
  466.                 // recolor and rotate
  467.                 x->parent->color = BLACK;
  468.                 x->parent->parent->color = RED;
  469.                 rotateRight(root,
  470.                             x->parent->parent);
  471.             }
  472.         }
  473.         else
  474.         {
  475.             // mirror image of above code
  476.             TREE *y = x->parent->parent->left;
  477.             if (y->color == RED)
  478.             {
  479.                 // uncle is RED
  480.                 x->parent->color = BLACK;
  481.                 y->color = BLACK;
  482.                 x->parent->parent->color = RED;
  483.                 x = x->parent->parent;
  484.             }
  485.             else
  486.             {
  487.                 // uncle is BLACK
  488.                 if (x == x->parent->left)
  489.                 {
  490.                     x = x->parent;
  491.                     rotateRight(root,
  492.                                 x);
  493.                 }
  494.                 x->parent->color = BLACK;
  495.                 x->parent->parent->color = RED;
  496.                 rotateLeft(root,
  497.                            x->parent->parent);
  498.             }
  499.         }
  500.     }
  501.  
  502.     (*root)->color = BLACK;
  503. }
  504.  
  505. /*
  506.  *@@ treeInsert:
  507.  *      inserts a new tree node into the specified
  508.  *      tree, using the specified comparison function
  509.  *      for sorting.
  510.  *
  511.  *      "x" specifies the new tree node which must
  512.  *      have been allocated by the caller. x->ulKey
  513.  *      must already contain the node's key (data)
  514.  *      which the sort function can understand.
  515.  *
  516.  *      This function will then set the parent,
  517.  *      left, right, and color members. In addition,
  518.  *      if (plCount != NULL), *plCount is raised by
  519.  *      one.
  520.  *
  521.  *      Returns 0 if no error. Might return
  522.  *      STATUS_DUPLICATE_KEY if a node with the
  523.  *      same ulKey already exists.
  524.  *
  525.  *@@changed V0.9.16 (2001-10-19) [umoeller]: added plCount
  526.  */
  527.  
  528. int treeInsert(TREE **root,                     // in: root of the tree
  529.                PLONG plCount,                   // in/out: item count (ptr can be NULL)
  530.                TREE *x,                         // in: new node to insert
  531.                FNTREE_COMPARE *pfnCompare)      // in: comparison func
  532. {
  533.     TREE    *current,
  534.             *parent;
  535.  
  536.     unsigned long key = x->ulKey;
  537.  
  538.     // find future parent
  539.     current = *root;
  540.     parent = 0;
  541.  
  542.     while (current != LEAF)
  543.     {
  544.         int iResult;
  545.         if (!(iResult = pfnCompare(key, current->ulKey)))
  546.             return STATUS_DUPLICATE_KEY;
  547.  
  548.         parent = current;
  549.         current = (iResult < 0)
  550.                     ? current->left
  551.                     : current->right;
  552.     }
  553.  
  554.     // set up new node
  555.     x->parent = parent;
  556.     x->left = LEAF;
  557.     x->right = LEAF;
  558.     x->color = RED;
  559.  
  560.     // insert node in tree
  561.     if (parent)
  562.     {
  563.         if (pfnCompare(key, parent->ulKey) < 0) // (compLT(key, parent->key))
  564.             parent->left = x;
  565.         else
  566.             parent->right = x;
  567.     }
  568.     else
  569.         *root = x;
  570.  
  571.     insertFixup(root,
  572.                 x);
  573.  
  574.     if (plCount)
  575.         (*plCount)++;       // V0.9.16 (2001-10-19) [umoeller]
  576.  
  577.     return STATUS_OK;
  578. }
  579.  
  580. /*
  581.  *@@ deleteFixup:
  582.  *
  583.  */
  584.  
  585. static void deleteFixup(TREE **root,
  586.                         TREE *tree)
  587. {
  588.     TREE    *s;
  589.  
  590.     while (    tree != *root
  591.             && tree->color == BLACK
  592.           )
  593.     {
  594.         if (tree == tree->parent->left)
  595.         {
  596.             s = tree->parent->right;
  597.             if (s->color == RED)
  598.             {
  599.                 s->color = BLACK;
  600.                 tree->parent->color = RED;
  601.                 rotateLeft(root, tree->parent);
  602.                 s = tree->parent->right;
  603.             }
  604.             if (    (s->left->color == BLACK)
  605.                  && (s->right->color == BLACK)
  606.                )
  607.             {
  608.                 s->color = RED;
  609.                 tree = tree->parent;
  610.             }
  611.             else
  612.             {
  613.                 if (s->right->color == BLACK)
  614.                 {
  615.                     s->left->color = BLACK;
  616.                     s->color = RED;
  617.                     rotateRight(root, s);
  618.                     s = tree->parent->right;
  619.                 }
  620.                 s->color = tree->parent->color;
  621.                 tree->parent->color = BLACK;
  622.                 s->right->color = BLACK;
  623.                 rotateLeft(root, tree->parent);
  624.                 tree = *root;
  625.             }
  626.         }
  627.         else
  628.         {
  629.             s = tree->parent->left;
  630.             if (s->color == RED)
  631.             {
  632.                 s->color = BLACK;
  633.                 tree->parent->color = RED;
  634.                 rotateRight(root, tree->parent);
  635.                 s = tree->parent->left;
  636.             }
  637.             if (    (s->right->color == BLACK)
  638.                  && (s->left->color == BLACK)
  639.                )
  640.             {
  641.                 s->color = RED;
  642.                 tree = tree->parent;
  643.             }
  644.             else
  645.             {
  646.                 if (s->left->color == BLACK)
  647.                 {
  648.                     s->right->color = BLACK;
  649.                     s->color = RED;
  650.                     rotateLeft(root, s);
  651.                     s = tree->parent->left;
  652.                 }
  653.                 s->color = tree->parent->color;
  654.                 tree->parent->color = BLACK;
  655.                 s->left->color = BLACK;
  656.                 rotateRight (root, tree->parent);
  657.                 tree = *root;
  658.             }
  659.         }
  660.     }
  661.  
  662.     tree->color = BLACK;
  663. }
  664.  
  665. /*
  666.  *@@ treeDelete:
  667.  *      removes the specified node from the tree.
  668.  *      Does not free() the node though.
  669.  *
  670.  *      In addition, if (plCount != NULL), *plCount is
  671.  *      decremented.
  672.  *
  673.  *      Returns 0 if the node was deleted or
  674.  *      STATUS_INVALID_NODE if not.
  675.  *
  676.  *@@changed V0.9.16 (2001-10-19) [umoeller]: added plCount
  677.  */
  678.  
  679. int treeDelete(TREE **root,         // in: root of the tree
  680.                PLONG plCount,       // in/out: item count (ptr can be NULL)
  681.                TREE *tree)          // in: tree node to delete
  682. {
  683.     TREE        *y,
  684.                 *d;
  685.     nodeColor   color;
  686.  
  687.     if (    (!tree)
  688.          || (tree == LEAF)
  689.        )
  690.         return STATUS_INVALID_NODE;
  691.  
  692.     if (    (tree->left  == LEAF)
  693.          || (tree->right == LEAF)
  694.        )
  695.         // d has a TREE_NULL node as a child
  696.         d = tree;
  697.     else
  698.     {
  699.         // find tree successor with a TREE_NULL node as a child
  700.         d = tree->right;
  701.         while (d->left != LEAF)
  702.             d = d->left;
  703.     }
  704.  
  705.     // y is d's only child, if there is one, else TREE_NULL
  706.     if (d->left != LEAF)
  707.         y = d->left;
  708.     else
  709.         y = d->right;
  710.  
  711.     // remove d from the parent chain
  712.     if (y != LEAF)
  713.         y->parent = d->parent;
  714.  
  715.     if (d->parent)
  716.     {
  717.         if (d == d->parent->left)
  718.             d->parent->left  = y;
  719.         else
  720.             d->parent->right = y;
  721.     }
  722.     else
  723.         *root = y;
  724.  
  725.     color = d->color;
  726.  
  727.     if (d != tree)
  728.     {
  729.         // move the data from d to tree; we do this by
  730.         // linking d into the structure in the place of tree
  731.         d->left   = tree->left;
  732.         d->right  = tree->right;
  733.         d->parent = tree->parent;
  734.         d->color  = tree->color;
  735.  
  736.         if (d->parent)
  737.         {
  738.             if (tree == d->parent->left)
  739.                 d->parent->left  = d;
  740.             else
  741.                 d->parent->right = d;
  742.         }
  743.         else
  744.             *root = d;
  745.  
  746.         if (d->left != LEAF)
  747.             d->left->parent = d;
  748.  
  749.         if (d->right != LEAF)
  750.             d->right->parent = d;
  751.     }
  752.  
  753.     if (    (y != LEAF)
  754.          && (color == BLACK)
  755.        )
  756.         deleteFixup(root,
  757.                     y);
  758.  
  759.     if (plCount)
  760.         (*plCount)--;       // V0.9.16 (2001-10-19) [umoeller]
  761.  
  762.     return (STATUS_OK);
  763. }
  764.  
  765. /*
  766.  *@@ treeFind:
  767.  *      finds the tree node with the specified key.
  768.  *      Returns NULL if none exists.
  769.  */
  770.  
  771. TREE* treeFind(TREE *root,                    // in: root of the tree
  772.                unsigned long key,             // in: key to find
  773.                FNTREE_COMPARE *pfnCompare)    // in: comparison func
  774. {
  775.     TREE *current = root;
  776.     while (current != LEAF)
  777.     {
  778.         int iResult;
  779.         if (!(iResult = pfnCompare(key, current->ulKey)))
  780.             return current;
  781.  
  782.         current = (iResult < 0)
  783.             ? current->left
  784.             : current->right;
  785.     }
  786.  
  787.     return 0;
  788. }
  789.  
  790. /*
  791.  *@@ treeFirst:
  792.  *      finds and returns the first node in a (sub-)tree.
  793.  *
  794.  *      See treeNext for a sample usage for traversing a tree.
  795.  */
  796.  
  797. TREE* treeFirst(TREE *r)
  798. {
  799.     TREE    *p;
  800.  
  801.     if (    (!r)
  802.          || (r == LEAF)
  803.        )
  804.         return NULL;
  805.  
  806.     p = r;
  807.     while (p->left != LEAF)
  808.         p = p->left;
  809.  
  810.     return p;
  811. }
  812.  
  813. /*
  814.  *@@ treeLast:
  815.  *      finds and returns the last node in a (sub-)tree.
  816.  */
  817.  
  818. TREE* treeLast(TREE *r)
  819. {
  820.     TREE    *p;
  821.  
  822.     if (    (!r)
  823.          || (r == LEAF))
  824.         return NULL;
  825.  
  826.     p = r;
  827.     while (p->right != LEAF)
  828.         p = p->right;
  829.  
  830.     return p;
  831. }
  832.  
  833. /*
  834.  *@@ treeNext:
  835.  *      finds and returns the next node in a tree.
  836.  *
  837.  *      Example for traversing a whole tree:
  838.  *
  839.  +          TREE    *TreeRoot;
  840.  +          ...
  841.  +          TREE* pNode = treeFirst(TreeRoot);
  842.  +          while (pNode)
  843.  +          {
  844.  +              ...
  845.  +              pNode = treeNext(pNode);
  846.  +          }
  847.  *
  848.  *      This runs through the tree items in sorted order.
  849.  */
  850.  
  851. TREE* treeNext(TREE *r)
  852. {
  853.     TREE    *p,
  854.             *child;
  855.  
  856.     if (    (!r)
  857.          || (r == LEAF)
  858.        )
  859.         return NULL;
  860.  
  861.     p = r;
  862.     if (p->right != LEAF)
  863.         return treeFirst(p->right);
  864.  
  865.     p = r;
  866.     child   = LEAF;
  867.     while (    (p->parent)
  868.             && (p->right == child)
  869.           )
  870.     {
  871.         child = p;
  872.         p = p->parent;
  873.     }
  874.  
  875.     if (p->right != child)
  876.         return p;
  877.  
  878.     return NULL;
  879. }
  880.  
  881. /*
  882.  *@@ treePrev:
  883.  *      finds and returns the previous node in a tree.
  884.  */
  885.  
  886. TREE* treePrev(TREE *r)
  887. {
  888.     TREE    *p,
  889.             *child;
  890.  
  891.     if (    (!r)
  892.          || (r == LEAF)
  893.        )
  894.         return NULL;
  895.  
  896.     p = r;
  897.     if (p->left != LEAF)
  898.         return treeLast (p->left);
  899.  
  900.     p = r;
  901.     child   = LEAF;
  902.     while (    (p->parent)
  903.             && (p->left == child)
  904.           )
  905.     {
  906.         child = p;
  907.         p = p->parent;
  908.     }
  909.  
  910.     if (p->left != child)
  911.         return p;
  912.  
  913.     return NULL;
  914. }
  915.  
  916. /*
  917.  *@@ treeBuildArray:
  918.  *      builds an array of TREE* pointers containing
  919.  *      all tree items in sorted order.
  920.  *
  921.  *      This returns a TREE** pointer to the array.
  922.  *      Each item in the array is a TREE* pointer to
  923.  *      the respective tree item.
  924.  *
  925.  *      The array has been allocated using malloc()
  926.  *      and must be free()'d by the caller.
  927.  *
  928.  *      NOTE: This will only work if you maintain a
  929.  *      tree node count yourself, which you must pass
  930.  *      in *pulCount on input.
  931.  *
  932.  *      This is most useful if you want to delete an
  933.  *      entire tree without having to traverse it
  934.  *      and rebalance the tree on every delete.
  935.  *
  936.  *      Example usage for deletion:
  937.  *
  938.  +          TREE    *G_TreeRoot;
  939.  +          treeInit(&G_TreeRoot);
  940.  +
  941.  +          // add stuff to the tree
  942.  +          TREE    *pNewNode = malloc(...);
  943.  +          treeInsert(&G_TreeRoot, pNewNode, fnCompare)
  944.  +
  945.  +          // now delete all nodes
  946.  +          ULONG   cItems = ... // insert item count here
  947.  +          TREE**  papNodes = treeBuildArray(G_TreeRoot,
  948.  +                                            &cItems);
  949.  +          if (papNodes)
  950.  +          {
  951.  +              ULONG ul;
  952.  +              for (ul = 0; ul < cItems; ul++)
  953.  +              {
  954.  +                  TREE *pNodeThis = papNodes[ul];
  955.  +                  free(pNodeThis);
  956.  +              }
  957.  +
  958.  +              free(papNodes);
  959.  +          }
  960.  +
  961.  *
  962.  *@@added V0.9.9 (2001-04-05) [umoeller]
  963.  */
  964.  
  965. TREE** treeBuildArray(TREE* pRoot,
  966.                       PLONG plCount)  // in: item count, out: array item count
  967. {
  968.     TREE            **papNodes = NULL,
  969.                     **papThis = NULL;
  970.     long            cb = (sizeof(TREE*) * (*plCount)),
  971.                     cNodes = 0;
  972.  
  973.     if (cb)
  974.     {
  975.         papNodes = (TREE**)malloc(cb);
  976.         papThis = papNodes;
  977.  
  978.         if (papNodes)
  979.         {
  980.             TREE    *pNode = (TREE*)treeFirst(pRoot);
  981.  
  982.             memset(papNodes, 0, cb);
  983.  
  984.             // copy nodes to array
  985.             while (    pNode
  986.                     && cNodes < (*plCount)     // just to make sure
  987.                   )
  988.             {
  989.                 *papThis = pNode;
  990.                 cNodes++;
  991.                 papThis++;
  992.  
  993.                 pNode = (TREE*)treeNext(pNode);
  994.             }
  995.  
  996.             // output count
  997.             *plCount = cNodes;
  998.         }
  999.     }
  1000.  
  1001.     return (papNodes);
  1002. }
  1003.  
  1004. /* void main(int argc, char **argv) {
  1005.     int maxnum, ct;
  1006.     recType rec;
  1007.     keyType key;
  1008.     statusEnum status;
  1009.  
  1010.     maxnum = atoi(argv[1]);
  1011.  
  1012.     printf("maxnum = %d\n", maxnum);
  1013.     for (ct = maxnum; ct; ct--) {
  1014.         key = rand() % 9 + 1;
  1015.         if ((status = find(key, &rec)) == STATUS_OK) {
  1016.             status = delete(key);
  1017.             if (status) printf("fail: status = %d\n", status);
  1018.         } else {
  1019.             status = insert(key, &rec);
  1020.             if (status) printf("fail: status = %d\n", status);
  1021.         }
  1022.     }
  1023. } */
  1024.