Ignore:
Timestamp:
Jun 28, 2001, 7:13:56 PM (24 years ago)
Author:
umoeller
Message:

Many misc updates.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/helpers/tree.c

    r56 r83  
    44 *      contains helper functions for maintaining 'Red-Black' balanced
    55 *      binary trees.
    6  *      See explanations below.
    7  *
    8  *      This file is all new with V0.9.5 (2000-09-29) [umoeller].
    96 *
    107 *      Usage: All C programs; not OS/2-specific.
    … …  
    1310 *      --  tree*    tree helper functions
    1411 *
    15  *      This has been taken from the Standard Function Library (SFL)
    16  *      by iMatix Corporation and changed to user the "id" member for
    17  *      tree sorting/comparison. This implementation is released
    18  *      under the GPL.
    19  *
    2012 *      <B>Introduction</B>
    2113 *
    22  *      Binary trees are different from linked lists in that items
    23  *      are not simply linked sequentially, but instead put into
    24  *      a tree-like structure.
    25  *
    26  *      While lists have "next" and "previous" pointers, trees have
    27  *      "left" and "right" pointers which keep the tree sorted at
    28  *      all times.
    29  *
    30  *      Per definition, in our trees, if you follow the "left" pointer,
    31  *      you will reach an item which is "greater than" the current node.
    32  *      Reversely, following the "right" pointer will lead you to a
    33  *      node which is "less than" the current node.
    34  *
    35  *      What is considered "less" or "greater" is determined by a
    36  *      comparison callback to be supplied by the caller.
    37  *
    38  *      For this, the functions here use the TREE structure. You can
    39  *      easily see that this has the "left" and "right" members,
    40  *      which make up the tree.
    41  *
    42  *      In addition, each tree has a "tree root" item, from which all
    43  *      other tree nodes can be reached by following the "left" and
    44  *      "right" pointers.
    45  *
    46  *      The implementation here has the following characteristics:
    47  *
    48  *      -- We have "binary" trees. That is, there are only "left" and
    49  *         "right" pointers.
    50  *
    51  *      -- The tree is always "balanced". The tree gets completely
    52  *         reordered when items are added/removed to ensure that
    53  *         all paths through the tree are approximately the same
    54  *         length. This avoids the "worst case" scenario that some
    55  *         paths grow terribly long while others remain short, which
    56  *         can make searching very inefficient.
    57  *
    58  *      -- The tree nodes are marked as either "red" or "black", which
    59  *         is an algorithm to allow the implementation of 2-3-4 trees
    60  *         using a binary tree only. I don't fully understand how this
    61  *         works, but essentially, "red" nodes represent a 3 or 4 node,
    62  *         while "black" nodes are plain binary nodes.
    63  *
    64  *      As much as I understand about all this, red-black balanced
    65  *      binary trees are the most efficient tree algorithm known to
    66  *      mankind. As long as you are sure that trees are more efficient
    67  *      in your situation than a linked list in the first place (see
    68  *      below for comparisons), use the functions in here.
    69  *
    70  *      <B>Using binary trees</B>
    71  *
    72  *      You can use any structure as elements in a tree, provided
    73  *      that the first member in the structure is a TREE structure
    74  *      (i.e. it has the left, right, parent, id, and colour members).
    75  *      The tree functions don't care what follows, since they do
    76  *      not manage any memory themselves.
    77  *
    78  *      So the implementation here is slightly different from the
    79  *      linked lists in linklist.c, because the LISTNODE structs
    80  *      only have pointers to the data. By contrast, the TREE structs
    81  *      are expected to contain the data themselves. See treeInsertID()
    82  *      for a sample.
    83  *
    84  *      Initialize the root of the tree with treeInit(). Then
    85  *      add nodes to the tree with treeInsertID() and remove nodes
    86  *      with treeDelete().
    87  *
    88  *      You can test whether a tree is empty by comparing its
    89  *      root with TREE_NULL.
    90  *
    91  *      Most functions in here come in two flavors.
    92  *
    93  *      -- You can provide a comparison function and use the "Node"
    94  *         flavors of these functions. This is useful, for example,
    95  *         if you are storing strings. You can then write a short
    96  *         comparison function which does a strcmp() on the data
    97  *         of tree nodes.
    98  *
    99  *         The order of nodes in the tree is determined by calling a
    100  *         node comparison function provided by the caller
    101  *         (which you must write). This must be declared as:
    102  *
    103  +              int TREEENTRY fnMyCompareNodes(TREE *t1, TREE *t2);
    104  *
    105  *         It obviously receives two TREE pointers, which it must
    106  *         compare and return:
    107  *
    108  +               0: tree1 == tree2
    109  +              -1: tree1 < tree2
    110  +              +1: tree1 > tree2
    111  *
    112  *      -- The "ID" functions (e.g. treeInsertID) do not require
    113  *         a comparison function, but will use the "id" member of
    114  *         the TREE structure instead. If this flavor is used, an
    115  *         internal comparison function is used for comparing the
    116  *         "id" fields, which are assumed to be plain ULONGs.
     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.
    11736 *
    11837 *      <B>Trees vs. linked lists</B>
    11938 *
    12039 *      Compared to linked lists (as implemented by linklist.c),
    121  *      trees allow for much faster searching.
     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.
    12262 *
    12363 *      Assuming a linked list contains N items, then searching a
    … …  
    13171 *      average.
    13272 *
    133  *      Example: You need to build a list of files, and you
    134  *      will search the list frequently according to the file
    135  *      handles. This would make the handle an ideal "id" field.
    136  *
    13773 *      Differences compared to linklist.c:
     74 *
     75 *      -- A tree is always sorted.
    13876 *
    13977 *      -- Trees are considerably slower when inserting and removing
    … …  
    14280 *         nodes because the tree is always sorted.
    14381 *
    144  *      -- If you are not using the "ID" flavors, you must supply a
    145  *         comparison function to allow the tree functions to sort the tree.
    146  *
    14782 *      -- As opposed to a LISTNODE, the TREE structure (which
    14883 *         represents a tree node) does not contain a data pointer,
    14984 *         as said above. The caller must do all memory management.
    15085 *
     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 reordered.
     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 *         The color of each node is instrumental in determining the
     123 *         balance of the tree. During insert and delete operations,
     124 *         nodes may be rotated to maintain tree balance.
     125 *
     126 *         I don't fully understand why this works, but if you really
     127 *         care, this is explained at
     128 *         "http://www.eli.sdsu.edu/courses/fall96/cs660/notes/redBlack/redBlack.html".
     129 *
     130 *      In other words, as opposed to regular binary trees, RB trees
     131 *      are not _fully_ balanced, but they are _mostly_ balanced. With
     132 *      respect to efficiency, RB trees are thus a good compromise:
     133 *
     134 *      -- Completely unbalanced trees are efficient when inserting,
     135 *         but can have a terrible worst case when searching.
     136 *
     137 *      -- RB trees are still acceptably efficient when inserting
     138 *         and quite efficient when searching.
     139 *         A RB tree with n internal nodes has a height of at most
     140 *         2lg(n+1). Both average and worst-case search time is O(lg n).
     141 *
     142 *      -- Fully balanced binary trees are inefficient when inserting
     143 *         but most efficient when searching.
     144 *
     145 *      So as long as you are sure that trees are more efficient
     146 *      in your situation than a linked list in the first place, use
     147 *      these RB trees instead of linked lists.
     148 *
     149 *      <B>Using binary trees</B>
     150 *
     151 *      You can use any structure as elements in a tree, provided
     152 *      that the first member in the structure is a TREE structure
     153 *      (i.e. it has the left, right, parent, and color members).
     154 *      Each TREE node has a ulKey field which is used for
     155 *      comparing tree nodes and thus determines the location of
     156 *      the node in the tree.
     157 *
     158 *      The tree functions don't care what follows in each TREE
     159 *      node since they do not manage any memory themselves.
     160 *      So the implementation here is slightly different from the
     161 *      linked lists in linklist.c, because the LISTNODE structs
     162 *      only have pointers to the data. By contrast, the TREE structs
     163 *      are expected to contain the data themselves.
     164 *
     165 *      Initialize the root of the tree with treeInit(). Then
     166 *      add nodes to the tree with treeInsert() and remove nodes
     167 *      with treeDelete(). See below for a sample.
     168 *
     169 *      You can test whether a tree is empty by comparing its
     170 *      root with LEAF.
     171 *
     172 *      For most tree* functions, you must specify a comparison
     173 *      function which will always receive two "key" parameters
     174 *      to compare. This must be declared as
     175 +
     176 +          int TREEENTRY fnCompare(ULONG ul1, ULONG ul2);
     177 *
     178 *      This will receive two TREE.ulKey members (whose meaning
     179 *      is defined by your implementation) and must return
     180 *
     181 *      -- something < 0: ul1 < ul2
     182 *      -- 0: ul1 == ul2
     183 *      -- something > 1: ul1 > ul2
     184 *
     185 *      <B>Example</B>
     186 *
     187 *      A good example where trees are efficient would be the
     188 *      case where you have "keyword=value" string pairs and
     189 *      you frequently need to search for "keyword" to find
     190 *      a "value". So "keyword" would be an ideal candidate for
     191 *      the TREE.key field.
     192 *
     193 *      You'd then define your own tree nodes like this:
     194 *
     195 +          typedef struct _MYTREENODE
     196 +          {
     197 +              TREE        Tree;       // regular tree node, which has
     198 +                                      // the ULONG "key" field; we'd
     199 +                                      // use this as a const char*
     200 +                                      // pointer to the keyword string
     201 +              // here come the additional fields
     202 +              // (whatever you need for your data)
     203 +              const char  *pcszValue;
     204 +
     205 +          } MYTREENODE, *PMYTREENODE;
     206 *
     207 *      Initialize the tree root:
     208 *
     209 +          TREE *root;
     210 +          treeInit(&root);
     211 *
     212 *      To add a new "keyword=value" pair, do this:
     213 *
     214 +          PMYTREENODE AddNode(TREE **root,
     215 +                              const char *pcszKeyword,
     216 +                              const char *pcszValue)
     217 +          {
     218 +              PMYTREENODE p = (PMYTREENODE)malloc(sizeof(MYTREENODE));
     219 +              p.Tree.ulKey = (ULONG)pcszKeyword;
     220 +              p.pcszValue = pcszValue;
     221 +              treeInsert(root,                // tree's root
     222 +                         p,                   // new tree node
     223 +                         fnCompare);          // comparison func
     224 +              return (p);
     225 +          }
     226 *
     227 *      Your comparison func receives two ulKey values to compare,
     228 *      which in this case would be the typecast string pointers:
     229 *
     230 +          int TREEENTRY fnCompare(ULONG ul1, ULONG ul2)
     231 +          {
     232 +              return (strcmp((const char*)ul1,
     233 +                             (const char*)ul2));
     234 +          }
     235 *
     236 *      You can then use treeFind to very quickly find a node
     237 *      with a specified ulKey member.
     238 *
     239 *      This file was new with V0.9.5 (2000-09-29) [umoeller].
     240 *      With V0.9.13, all the code has been replaced with the public
     241 *      domain code found at http://epaperpress.com/sortsearch/index.html
     242 *      ("A compact guide to searching and sorting") by Thomas Niemann.
     243 *      The old implementation from the Standard Function Library (SFL)
     244 *      turned out to be buggy for large trees (more than 100 nodes).
     245 *
    151246 *@@added V0.9.5 (2000-09-29) [umoeller]
    152247 *@@header "helpers\tree.h"
    … …  
    154249
    155250/*
    156  *      Written:    97/11/18  Jonathan Schultz <jonathan@imatix.com>
    157  *      Revised:    98/12/08  Jonathan Schultz <jonathan@imatix.com>
    158  *
    159  *      Copyright (C) 1991-99 iMatix Corporation.
    160  *      Copyright (C) 2000 Ulrich M”ller.
     251 *      Original coding by Thomas Niemann, placed in the public domain
     252 *      (see http://epaperpress.com/sortsearch/index.html).
     253 *
     254 *      This implementation Copyright (C) 2001 Ulrich M”ller.
    161255 *      This file is part of the "XWorkplace helpers" source package.
    162256 *      This is free software; you can redistribute it and/or modify
    … …  
    178272#include "helpers\tree.h"
    179273
    180 //  Constants
    181 TREE    TREE_EMPTY = {TREE_NULL, TREE_NULL, NULL, BLACK};
    182 
    183 //  Internal function prototypes
    184 static void insert_fixup(TREE **root, TREE *tree);
    185 static void rotate_left(TREE **root, TREE *tree);
    186 static void rotate_right(TREE **root, TREE *tree);
    187 static void delete_fixup(TREE **root, TREE *tree);
     274#define LEAF &sentinel           // all leafs are sentinels
     275static TREE sentinel = { LEAF, LEAF, 0, BLACK};
     276
     277/*
     278A binary search tree is a red-black tree if:
     279
     2801. Every node is either red or black.
     2812. Every leaf (nil) is black.
     2823. If a node is red, then both its children are black.
     2834. Every simple path from a node to a descendant leaf contains the same
     284   number of black nodes.
     285*/
    188286
    189287/*
    190288 *@@ treeInit:
    191  *      initializes an empty tree. The data on the
    192  *      tree will be invalid, and no memory will be
    193  *      freed.
    194  *
    195  *      Usage:
    196  +          TREE *TreeRoot;
    197  +          treeInit(&TreeRoot);
     289 *      initializes the root of a tree.
     290 *
    198291 */
    199292
    200293void treeInit(TREE **root)
    201294{
    202     *root = TREE_NULL;
    203 }
    204 
    205 /*
    206  * fnCompareIDs:
    207  *
    208  *added V0.9.9 (2001-02-06) [umoeller]
    209  */
    210 
    211 int TREEENTRY fnCompareIDs(unsigned long id1, unsigned long id2)
    212 {
    213     if (id1 < id2)
     295    *root = LEAF;
     296}
     297
     298/*
     299 *@@ treeCompareKeys:
     300 *      standard comparison func if the TREE.ulKey
     301 *      field really is a ULONG.
     302 */
     303
     304int TREEENTRY treeCompareKeys(unsigned long  ul1, unsigned long ul2)
     305{
     306    if (ul1 < ul2)
    214307        return -1;
    215     if (id1 > id2)
     308    if (ul1 > ul2)
    216309        return +1;
    217310    return (0);
    … …  
    219312
    220313/*
    221  *@@ treeInsertID:
    222  *      inserts a node into an existing tree.
    223  *
    224  *      Note: A tree node MUST contain a TREE structure
    225  *      at the beginning for the tree functions to work.
    226  *      So to create a tree node with usable data, do this:
    227  *
    228  +          typedef _MYTREENODE
    229  +          {
    230  +              // TREE must be at beginning
    231  +              TREE        Tree;
    232  +              // now use whatever you want
    233  +              CHAR        szMyExtraData[100];
    234  +          } MYTREENODE, *PMYTREENODE;
    235  *
    236  *      When calling the tree functions, manually cast your
    237  *      MYTREENODE pointers to (TREE*).
    238  *
    239  *      This function initialises the node pointers and colour
    240  *      in the TREE structure to correct values, so the caller
    241  *      does not have to worry about those.
    242  *
    243  *      However you must initialize the TREE.id member correctly
    244  *      so that your comparison function can compare on that
    245  *      to find the correct place in the tree to insert the node.
    246  *
    247  *      Usage:
    248  +          TREE *TreeRoot;
    249  +          treeInit(&TreeRoot);
    250  +
    251  +          PMYTREENODE pTreeItem = malloc(sizeof(MYTREENODE));
    252  +          pTreeItem->Tree.id = 1;
    253  +
    254  +          treeInsertID(&TreeRoot,
    255  +                       (TREE*)pTreeItem,
    256  +                       FALSE);
    257  *
    258  *      Returns:
    259  *
    260  *      -- TREE_OK: OK, item inserted.
    261  *
    262  *      -- TREE_DUPLICATE: if (fAllowDuplicates == FALSE), this is
    263  *          returned if a tree item with the specified ID already
    264  *          exists.
    265  *
    266  *@@changed V0.9.9 (2001-02-06) [umoeller]: removed comparison func
    267  */
    268 
    269 int treeInsertID(TREE **root,             // in: root of tree
    270                  TREE *tree,              // in: new tree node
    271                  BOOL fAllowDuplicates)   // in: whether duplicates with the same ID are allowed
     314 *@@ rotateLeft:
     315 *      private function during rebalancing.
     316 */
     317
     318static void rotateLeft(TREE **root,
     319                       TREE *x)
     320{
     321   /**************************
     322    *  rotate node x to left *
     323    **************************/
     324
     325    TREE *y = x->right;
     326
     327    // establish x->right link
     328    x->right = y->left;
     329    if (y->left != LEAF)
     330        y->left->parent = x;
     331
     332    // establish y->parent link
     333    if (y != LEAF)
     334        y->parent = x->parent;
     335    if (x->parent)
     336    {
     337        if (x == x->parent->left)
     338            x->parent->left = y;
     339        else
     340            x->parent->right = y;
     341    }
     342    else
     343        *root = y;
     344
     345    // link x and y
     346    y->left = x;
     347    if (x != LEAF)
     348        x->parent = y;
     349}
     350
     351/*
     352 *@@ rotateRight:
     353 *      private function during rebalancing.
     354 */
     355
     356static void rotateRight(TREE **root,
     357                        TREE *x)
     358{
     359
     360   /****************************
     361    *  rotate node x to right  *
     362    ****************************/
     363
     364    TREE *y = x->left;
     365
     366    // establish x->left link
     367    x->left = y->right;
     368    if (y->right != LEAF)
     369        y->right->parent = x;
     370
     371    // establish y->parent link
     372    if (y != LEAF)
     373        y->parent = x->parent;
     374    if (x->parent)
     375    {
     376        if (x == x->parent->right)
     377            x->parent->right = y;
     378        else
     379            x->parent->left = y;
     380    }
     381    else
     382        *root = y;
     383
     384    // link x and y
     385    y->right = x;
     386    if (x != LEAF)
     387        x->parent = y;
     388}
     389
     390/*
     391 *@@ insertFixup:
     392 *      private function during rebalancing.
     393 */
     394
     395static void insertFixup(TREE **root,
     396                        TREE *x)
     397{
     398   /*************************************
     399    *  maintain Red-Black tree balance  *
     400    *  after inserting node x           *
     401    *************************************/
     402
     403    // check Red-Black properties
     404    while (    x != *root
     405            && x->parent->color == RED
     406          )
     407    {
     408        // we have a violation
     409        if (x->parent == x->parent->parent->left)
     410        {
     411            TREE *y = x->parent->parent->right;
     412            if (y->color == RED)
     413            {
     414                // uncle is RED
     415                x->parent->color = BLACK;
     416                y->color = BLACK;
     417                x->parent->parent->color = RED;
     418                x = x->parent->parent;
     419            }
     420            else
     421            {
     422                // uncle is BLACK
     423                if (x == x->parent->right)
     424                {
     425                    // make x a left child
     426                    x = x->parent;
     427                    rotateLeft(root,
     428                               x);
     429                }
     430
     431                // recolor and rotate
     432                x->parent->color = BLACK;
     433                x->parent->parent->color = RED;
     434                rotateRight(root,
     435                            x->parent->parent);
     436            }
     437        }
     438        else
     439        {
     440            // mirror image of above code
     441            TREE *y = x->parent->parent->left;
     442            if (y->color == RED)
     443            {
     444                // uncle is RED
     445                x->parent->color = BLACK;
     446                y->color = BLACK;
     447                x->parent->parent->color = RED;
     448                x = x->parent->parent;
     449            }
     450            else
     451            {
     452                // uncle is BLACK
     453                if (x == x->parent->left)
     454                {
     455                    x = x->parent;
     456                    rotateRight(root,
     457                                x);
     458                }
     459                x->parent->color = BLACK;
     460                x->parent->parent->color = RED;
     461                rotateLeft(root,
     462                           x->parent->parent);
     463            }
     464        }
     465    }
     466    (*root)->color = BLACK;
     467}
     468
     469/*
     470 *@@ treeInsert:
     471 *      inserts a new tree node into the specified
     472 *      tree, using the specified comparison function
     473 *      for sorting.
     474 *
     475 *      "x" specifies the new tree node which must
     476 *      have been allocated by the caller. x->ulKey
     477 *      must already contain the node's key (data).
     478 *      This function will then set the parent,
     479 *      left, right, and color members.
     480 *
     481 *      Returns 0 if no error. Might return
     482 *      STATUS_DUPLICATE_KEY if a node with the
     483 *      same ulKey already exists.
     484 */
     485
     486int treeInsert(TREE **root,                     // in: root of the tree
     487               TREE *x,                         // in: new node to insert
     488               FNTREE_COMPARE *pfnCompare)      // in: comparison func
    272489{
    273490    TREE    *current,
    274491            *parent;
    275     int     last_comp = 0;
    276 
    277     // find where node belongs
     492
     493    unsigned long key = x->ulKey;
     494
     495    // find future parent
    278496    current = *root;
    279     parent  = NULL;
    280     while (current != TREE_NULL)
    281     {
    282         parent  = current;
    283         last_comp = fnCompareIDs(tree->id, current->id);
    284         switch (last_comp)
    285         {
    286             case -1: current = current->left;  break;
    287             case  1: current = current->right; break;
    288             default:
    289                 if (fAllowDuplicates)
    290                     current = current->left;
    291                 else
    292                     return TREE_DUPLICATE;
    293         }
     497    parent = 0;
     498
     499    while (current != LEAF)
     500    {
     501        int iResult;
     502        if (0 == (iResult = pfnCompare(key, current->ulKey))) // if (compEQ(key, current->key))
     503            return STATUS_DUPLICATE_KEY;
     504        parent = current;
     505        current = (iResult < 0)    // compLT(key, current->key)
     506                    ? current->left
     507                    : current->right;
    294508    }
    295509
    296510    // set up new node
    297     ((TREE*)tree)->parent = parent;
    298     ((TREE*)tree)->left   = TREE_NULL;
    299     ((TREE*)tree)->right  = TREE_NULL;
    300     ((TREE*)tree)->colour = RED;
     511    /* if ((x = malloc (sizeof(*x))) == 0)
     512        return STATUS_MEM_EXHAUSTED; */
     513    x->parent = parent;
     514    x->left = LEAF;
     515    x->right = LEAF;
     516    x->color = RED;
     517    // x->key = key;
     518    // x->rec = *rec;
    301519
    302520    // insert node in tree
    303521    if (parent)
    304         switch (last_comp)
    305         {
    306             case  1: parent->right = tree;  break;
    307             default: parent->left  = tree;
    308         }
     522    {
     523        if (pfnCompare(key, parent->ulKey) < 0) // (compLT(key, parent->key))
     524            parent->left = x;
     525        else
     526            parent->right = x;
     527    }
    309528    else
    310         *root = tree;
    311 
    312     insert_fixup(root, tree);
    313     return(TREE_OK);
    314 }
    315 
    316 /*
    317  *@@ treeInsertNode:
    318  *      similar to treeInsertID, but this uses
    319  *      a comparision function which compares
    320  *      nodes.
    321  */
    322 
    323 int treeInsertNode(TREE **root,             // in: root of tree
    324                    TREE *tree,              // in: new tree node
    325                    FNTREE_COMPARE_NODES *comp,  // in: comparison function
    326                    BOOL fAllowDuplicates)   // in: whether duplicates with the same ID are allowed
    327 {
    328     TREE
    329        *current,
    330        *parent;
    331     int
    332         last_comp = 0;
    333 
    334     // find where node belongs
    335     current = *root;
    336     parent  = NULL;
    337     while (current != TREE_NULL)
    338     {
    339         parent  = current;
    340         last_comp = comp(tree, current);
    341         switch (last_comp)
    342         {
    343             case -1: current = current->left;  break;
    344             case  1: current = current->right; break;
    345             default: if (fAllowDuplicates)
    346                          current = current->left;
    347                      else
    348                          return TREE_DUPLICATE;
    349 
    350         }
    351     }
    352 
    353     // set up new node
    354     ((TREE*)tree)->parent = parent;
    355     ((TREE*)tree)->left   = TREE_NULL;
    356     ((TREE*)tree)->right  = TREE_NULL;
    357     ((TREE*)tree)->colour = RED;
    358 
    359     // insert node in tree
    360     if (parent)
    361         switch (last_comp)
    362         {
    363             case  1: parent->right = tree;  break;
    364             default: parent->left  = tree;
    365         }
     529        *root = x;
     530
     531    insertFixup(root,
     532                x);
     533    // lastFind = NULL;
     534
     535    return STATUS_OK;
     536}
     537
     538/*
     539 *@@ deleteFixup:
     540 *
     541 */
     542
     543static void deleteFixup(TREE **root,
     544                        TREE *tree)
     545{
     546    TREE    *s;
     547
     548    while (    tree != *root
     549            && tree->color == BLACK
     550          )
     551    {
     552        if (tree == tree->parent->left)
     553        {
     554            s = tree->parent->right;
     555            if (s->color == RED)
     556            {
     557                s->color = BLACK;
     558                tree->parent->color = RED;
     559                rotateLeft(root, tree->parent);
     560                s = tree->parent->right;
     561            }
     562            if (    (s->left->color == BLACK)
     563                 && (s->right->color == BLACK)
     564               )
     565            {
     566                s->color = RED;
     567                tree = tree->parent;
     568            }
     569            else
     570            {
     571                if (s->right->color == BLACK)
     572                {
     573                    s->left->color = BLACK;
     574                    s->color = RED;
     575                    rotateRight(root, s);
     576                    s = tree->parent->right;
     577                }
     578                s->color = tree->parent->color;
     579                tree->parent->color = BLACK;
     580                s->right->color = BLACK;
     581                rotateLeft(root, tree->parent);
     582                tree = *root;
     583            }
     584        }
     585        else
     586        {
     587            s = tree->parent->left;
     588            if (s->color == RED)
     589            {
     590                s->color = BLACK;
     591                tree->parent->color = RED;
     592                rotateRight(root, tree->parent);
     593                s = tree->parent->left;
     594            }
     595            if (    (s->right->color == BLACK)
     596                 && (s->left->color == BLACK)
     597               )
     598            {
     599                s->color = RED;
     600                tree = tree->parent;
     601            }
     602            else
     603            {
     604                if (s->left->color == BLACK)
     605                {
     606                    s->right->color = BLACK;
     607                    s->color = RED;
     608                    rotateLeft(root, s);
     609                    s = tree->parent->left;
     610                }
     611                s->color = tree->parent->color;
     612                tree->parent->color = BLACK;
     613                s->left->color = BLACK;
     614                rotateRight (root, tree->parent);
     615                tree = *root;
     616            }
     617        }
     618    }
     619    tree->color = BLACK;
     620
     621   /*************************************
     622    *  maintain Red-Black tree balance  *
     623    *  after deleting node x            *
     624    *************************************/
     625
     626    /* while (    x != *root
     627            && x->color == BLACK
     628          )
     629    {
     630        if (x == x->parent->left)
     631        {
     632            TREE *w = x->parent->right;
     633            if (w->color == RED)
     634            {
     635                w->color = BLACK;
     636                x->parent->color = RED;
     637                rotateLeft(root,
     638                           x->parent);
     639                w = x->parent->right;
     640            }
     641            if (    w->left->color == BLACK
     642                 && w->right->color == BLACK
     643               )
     644            {
     645                w->color = RED;
     646                x = x->parent;
     647            }
     648            else
     649            {
     650                if (w->right->color == BLACK)
     651                {
     652                    w->left->color = BLACK;
     653                    w->color = RED;
     654                    rotateRight(root,
     655                                w);
     656                    w = x->parent->right;
     657                }
     658                w->color = x->parent->color;
     659                x->parent->color = BLACK;
     660                w->right->color = BLACK;
     661                rotateLeft(root,
     662                           x->parent);
     663                x = *root;
     664            }
     665        }
     666        else
     667        {
     668            TREE *w = x->parent->left;
     669            if (w->color == RED)
     670            {
     671                w->color = BLACK;
     672                x->parent->color = RED;
     673                rotateRight(root,
     674                            x->parent);
     675                w = x->parent->left;
     676            }
     677            if (    w->right->color == BLACK
     678                 && w->left->color == BLACK
     679               )
     680            {
     681                w->color = RED;
     682                x = x->parent;
     683            }
     684            else
     685            {
     686                if (w->left->color == BLACK)
     687                {
     688                    w->right->color = BLACK;
     689                    w->color = RED;
     690                    rotateLeft(root,
     691                               w);
     692                    w = x->parent->left;
     693                }
     694                w->color = x->parent->color;
     695                x->parent->color = BLACK;
     696                w->left->color = BLACK;
     697                rotateRight(root,
     698                            x->parent);
     699                x = *root;
     700            }
     701        }
     702    }
     703    x->color = BLACK; */
     704}
     705
     706/*
     707 *@@ treeDelete:
     708 *      removes the specified node from the tree.
     709 *      Does not free() the node though.
     710 *
     711 *      Returns 0 if the node was deleted or
     712 *      STATUS_INVALID_NODE if not.
     713 */
     714
     715int treeDelete(TREE **root,         // in: root of the tree
     716               TREE *tree)          // in: tree node to delete
     717{
     718    TREE        *y,
     719                *d;
     720    nodeColor   color;
     721
     722    if (    (!tree)
     723         || (tree == LEAF)
     724       )
     725        return STATUS_INVALID_NODE;
     726
     727    if (    (tree->left  == LEAF)
     728         || (tree->right == LEAF)
     729       )
     730        // d has a TREE_NULL node as a child
     731        d = tree;
    366732    else
    367         *root = tree;
    368 
    369     insert_fixup(root, tree);
    370     return(TREE_OK);
    371 }
    372 
    373 /*
    374  * insert_fixup:
    375  *      maintains the Red-Black tree balance after a node has been inserted.
    376  *
    377  *      Private function.
    378  */
    379 
    380 static void insert_fixup(TREE **root,
    381                          TREE *tree)
    382 {
    383     TREE *uncle;
    384 
    385     // check red-black properties
    386     while ((tree != *root)
    387        &&  (tree->parent->colour == RED))
    388     {
    389         // we have a violation
    390         if (tree->parent == tree->parent->parent->left)
    391         {
    392             uncle = tree->parent->parent->right;
    393             if (uncle->colour == RED)
    394             {
    395                 // uncle is RED
    396                 tree ->parent->colour = BLACK;
    397                 uncle->colour = BLACK;
    398                 tree ->parent->parent->colour = RED;
    399 
    400                 tree = tree->parent->parent;
    401             }
     733    {
     734        // find tree successor with a TREE_NULL node as a child
     735        d = tree->right;
     736        while (d->left != LEAF)
     737            d = d->left;
     738    }
     739
     740    // y is d's only child, if there is one, else TREE_NULL
     741    if (d->left != LEAF)
     742        y = d->left;
     743    else
     744        y = d->right;
     745
     746    // remove d from the parent chain
     747    if (y != LEAF)
     748        y->parent = d->parent;
     749    if (d->parent)
     750    {
     751        if (d == d->parent->left)
     752            d->parent->left  = y;
     753        else
     754            d->parent->right = y;
     755    }
     756    else
     757        *root = y;
     758
     759    color = d->color;
     760
     761    if (d != tree)
     762    {
     763        // move the data from d to tree; we do this by
     764        // linking d into the structure in the place of tree
     765        d->left   = tree->left;
     766        d->right  = tree->right;
     767        d->parent = tree->parent;
     768        d->color  = tree->color;
     769
     770        if (d->parent)
     771        {
     772            if (tree == d->parent->left)
     773                d->parent->left  = d;
    402774            else
    403             {
    404                 // uncle is BLACK
    405                 if (tree == tree->parent->right)
    406                 {
    407                     // make tree a left child
    408                     tree = tree->parent;
    409                     rotate_left (root, tree);
    410                 }
    411 
    412                 // recolor and rotate
    413                 tree->parent->colour = BLACK;
    414                 tree->parent->parent->colour = RED;
    415                 rotate_right (root, tree->parent->parent);
    416             }
     775                d->parent->right = d;
    417776        }
    418777        else
    419         {
    420             // mirror image of above code
    421             uncle = tree->parent->parent->left;
    422             if (uncle->colour == RED)
    423             {
    424                 // uncle is RED
    425                 tree ->parent->colour = BLACK;
    426                 uncle->colour = BLACK;
    427                 tree ->parent->parent->colour = RED;
    428 
    429                 tree = tree->parent->parent;
    430             }
     778            *root = d;
     779
     780        if (d->left != LEAF)
     781            d->left->parent = d;
     782
     783        if (d->right != LEAF)
     784            d->right->parent = d;
     785    }
     786
     787    if (    (y != LEAF)
     788         && (color == BLACK)
     789       )
     790        deleteFixup(root,
     791                    y);
     792
     793    return (STATUS_OK);
     794
     795    /* TREE    *x,
     796            *y; */
     797            // *z;
     798
     799   /*****************************
     800    *  delete node z from tree  *
     801    *****************************/
     802
     803    // find node in tree
     804    /* if (lastFind && compEQ(lastFind->key, key))
     805        // if we just found node, use pointer
     806        z = lastFind;
     807    else {
     808        z = *root;
     809        while(z != LEAF)
     810        {
     811            int iResult = pfnCompare(key, z->key);
     812            if (iResult == 0)
     813            // if(compEQ(key, z->key))
     814                break;
    431815            else
    432             {
    433                 // uncle is BLACK
    434                 if (tree == tree->parent->left)
    435                 {
    436                     tree = tree->parent;
    437                     rotate_right (root, tree);
    438                 }
    439                 tree->parent->colour = BLACK;
    440                 tree->parent->parent->colour = RED;
    441                 rotate_left (root, tree->parent->parent);
    442             }
    443         }
    444     }
    445     (*root)->colour = BLACK;
    446 }
    447 
    448 /*
    449  * rotate_left:
    450  *      rotates tree to left.
    451  *
    452  *      Private function.
    453  */
    454 
    455 static void rotate_left(TREE **root,
    456                         TREE *tree)
    457 {
    458     TREE *other = tree->right;
    459 
    460     // establish tree->right link
    461     tree->right = other->left;
    462     if (other->left != TREE_NULL)
    463         other->left->parent = tree;
    464 
    465     // establish other->parent link
    466     if (other != TREE_NULL)
    467         other->parent = tree->parent;
    468 
    469     if (tree->parent)
    470     {
    471         if (tree == tree->parent->left)
    472             tree->parent->left  = other;
     816                z = (iResult < 0) // compLT(key, z->key)
     817                    ? z->left
     818                    : z->right;
     819        }
     820        if (z == LEAF)
     821            return STATUS_KEY_NOT_FOUND;
     822    }
     823
     824    if (    z->left == LEAF
     825         || z->right == LEAF
     826       )
     827    {
     828        // y has a LEAF node as a child
     829        y = z;
     830    }
     831    else
     832    {
     833        // find tree successor with a LEAF node as a child
     834        y = z->right;
     835        while (y->left != LEAF)
     836            y = y->left;
     837    }
     838
     839    // x is y's only child
     840    if (y->left != LEAF)
     841        x = y->left;
     842    else
     843        x = y->right;
     844
     845    // remove y from the parent chain
     846    x->parent = y->parent;
     847    if (y->parent)
     848        if (y == y->parent->left)
     849            y->parent->left = x;
    473850        else
    474             tree->parent->right = other;
    475     }
     851            y->parent->right = x;
    476852    else
    477         *root = other;
    478 
    479     // link tree and other
    480     other->left = tree;
    481     if (tree != TREE_NULL)
    482         tree->parent = other;
    483 }
    484 
    485 /*
    486  * rotate_right:
    487  *      rotates tree to right.
    488  *
    489  *      Private function.
    490  */
    491 
    492 static void rotate_right(TREE **root,
    493                          TREE *tree)
    494 {
    495     TREE *other;
    496 
    497     other = tree->left;
    498 
    499     // establish tree->left link
    500     tree->left = other->right;
    501     if (other->right != TREE_NULL)
    502         other->right->parent = tree;
    503 
    504     // establish other->parent link
    505     if (other != TREE_NULL)
    506         other->parent = tree->parent;
    507 
    508     if (tree->parent)
    509     {
    510         if (tree == tree->parent->right)
    511             tree->parent->right = other;
     853        *root = x;
     854
     855    // y is about to be deleted...
     856
     857    if (y != z)
     858    {
     859        // now, the original code simply copied the data
     860        // from y to z... we can't safely do that since
     861        // we don't know about the real data in the
     862        // caller's TREE structure
     863        z->ulKey = y->ulKey;
     864        // z->rec = y->rec;         // hope this works...
     865                                    // the original implementation used rec
     866                                    // for the node's data
     867
     868        if (cbStruct > sizeof(TREE))
     869        {
     870            memcpy(((char*)&z) + sizeof(TREE),
     871                   ((char*)&y) + sizeof(TREE),
     872                   cbStruct - sizeof(TREE));
     873        }
     874    }
     875
     876    if (y->color == BLACK)
     877        deleteFixup(root,
     878                    x);
     879
     880    // free(y);
     881    // lastFind = NULL;
     882
     883    return STATUS_OK; */
     884}
     885
     886/*
     887 *@@ treeFind:
     888 *      finds the tree node with the specified key.
     889 */
     890
     891TREE* treeFind(TREE *root,                    // in: root of the tree
     892               unsigned long key,             // in: key to find
     893               FNTREE_COMPARE *pfnCompare)    // in: comparison func
     894{
     895   /*******************************
     896    *  find node containing data  *
     897    *******************************/
     898
     899    TREE *current = root;
     900    while (current != LEAF)
     901    {
     902        int iResult;
     903        if (0 == (iResult = pfnCompare(key, current->ulKey)))
     904            return (current);
    512905        else
    513             tree->parent->left  = other;
    514     }
    515     else
    516         *root = other;
    517 
    518     // link tree and other
    519     other->right = tree;
    520     if (tree != TREE_NULL)
    521         tree->parent = other;
    522 }
    523 
    524 /*
    525  *@@ treeDelete:
    526  *      deletes a node from a tree. Does not deallocate any memory.
    527  *
    528  *      Returns:
    529  *
    530  *      -- TREE_OK: node deleted.
    531  *      -- TREE_INVALID_NODE: tree node not found.
    532  */
    533 
    534 int treeDelete(TREE **root,     // in: root of tree
    535                TREE *tree)      // in: tree node to delete
    536 {
    537     int irc = TREE_OK;
    538 
    539     TREE
    540        *youngest, *descendent;
    541     TREE_COLOUR
    542         colour;
    543 
    544     if (    (!tree)
    545          || (tree == TREE_NULL)
    546        )
    547         return TREE_INVALID_NODE;
    548 
    549     if (    (((TREE*)tree)->left  == TREE_NULL)
    550          || (((TREE*)tree)->right == TREE_NULL)
    551        )
    552         // descendent has a TREE_NULL node as a child
    553         descendent = tree;
    554     else
    555   {
    556         // find tree successor with a TREE_NULL node as a child
    557         descendent = ((TREE*)tree)->right;
    558         while (descendent->left != TREE_NULL)
    559             descendent = descendent->left;
    560   }
    561 
    562     // youngest is descendent's only child, if there is one, else TREE_NULL
    563     if (descendent->left != TREE_NULL)
    564         youngest = descendent->left;
    565     else
    566         youngest = descendent->right;
    567 
    568     // remove descendent from the parent chain
    569     if (youngest != TREE_NULL)
    570         youngest->parent = descendent->parent;
    571     if (descendent->parent)
    572     {
    573         if (descendent == descendent->parent->left)
    574             descendent->parent->left  = youngest;
    575         else
    576             descendent->parent->right = youngest;
    577     }
    578     else
    579         *root = youngest;
    580 
    581     colour = descendent->colour;
    582 
    583     if (descendent != (TREE *) tree)
    584     {
    585         // Conceptually what we are doing here is moving the data from
    586         // descendent to tree.  In fact we do this by linking descendent
    587         // into the structure in the place of tree.
    588         descendent->left   = ((TREE*)tree)->left;
    589         descendent->right  = ((TREE*)tree)->right;
    590         descendent->parent = ((TREE*)tree)->parent;
    591         descendent->colour = ((TREE*)tree)->colour;
    592 
    593         if (descendent->parent)
    594         {
    595             if (tree == descendent->parent->left)
    596                 descendent->parent->left  = descendent;
    597             else
    598                 descendent->parent->right = descendent;
    599         }
    600         else
    601             *root = descendent;
    602 
    603         if (descendent->left != TREE_NULL)
    604             descendent->left->parent = descendent;
    605 
    606         if (descendent->right != TREE_NULL)
    607             descendent->right->parent = descendent;
    608     }
    609 
    610     if (    (youngest != TREE_NULL)
    611         &&  (colour   == BLACK))
    612         delete_fixup (root, youngest);
    613 
    614     return (irc);
    615 }
    616 
    617 /*
    618  *@@ delete_fixup:
    619  *      maintains Red-Black tree balance after deleting a node.
    620  *
    621  *      Private function.
    622  */
    623 
    624 static void delete_fixup(TREE **root,
    625                          TREE *tree)
    626 {
    627     TREE
    628        *sibling;
    629 
    630     while (tree != *root && tree->colour == BLACK)
    631     {
    632         if (tree == tree->parent->left)
    633         {
    634             sibling = tree->parent->right;
    635             if (sibling->colour == RED)
    636             {
    637                 sibling->colour = BLACK;
    638                 tree->parent->colour = RED;
    639                 rotate_left (root, tree->parent);
    640                 sibling = tree->parent->right;
    641             }
    642             if ((sibling->left->colour == BLACK)
    643             &&  (sibling->right->colour == BLACK))
    644             {
    645                 sibling->colour = RED;
    646                 tree = tree->parent;
    647             }
    648             else
    649             {
    650                 if (sibling->right->colour == BLACK)
    651                 {
    652                     sibling->left->colour = BLACK;
    653                     sibling->colour = RED;
    654                     rotate_right (root, sibling);
    655                     sibling = tree->parent->right;
    656                 }
    657                 sibling->colour = tree->parent->colour;
    658                 tree->parent->colour = BLACK;
    659                 sibling->right->colour = BLACK;
    660                 rotate_left (root, tree->parent);
    661                 tree = *root;
    662             }
    663         }
    664         else
    665         {
    666             sibling = tree->parent->left;
    667             if (sibling->colour == RED)
    668             {
    669                 sibling->colour = BLACK;
    670                 tree->parent->colour = RED;
    671                 rotate_right (root, tree->parent);
    672                 sibling = tree->parent->left;
    673             }
    674             if ((sibling->right->colour == BLACK)
    675             &&  (sibling->left->colour == BLACK))
    676             {
    677                 sibling->colour = RED;
    678                 tree = tree->parent;
    679             }
    680             else
    681             {
    682                 if (sibling->left->colour == BLACK)
    683                 {
    684                     sibling->right->colour = BLACK;
    685                     sibling->colour = RED;
    686                     rotate_left (root, sibling);
    687                     sibling = tree->parent->left;
    688                 }
    689                 sibling->colour = tree->parent->colour;
    690                 tree->parent->colour = BLACK;
    691                 sibling->left->colour = BLACK;
    692                 rotate_right (root, tree->parent);
    693                 tree = *root;
    694             }
    695         }
    696     }
    697     tree->colour = BLACK;
    698 }
    699 
    700 /*
    701  *@@ treeFindEQID:
    702  *      finds a node with ID exactly matching that provided.
    703  *      Returns NULL if not found.
    704  */
    705 
    706 void* treeFindEQID(TREE **root,
    707                    unsigned long id)
    708 {
    709     TREE    *current = *root,
    710             *found = NULL;
    711 
    712     while (current != TREE_NULL)
    713         switch (fnCompareIDs(current->id, id))
    714         {
    715             case -1: current = current->right; break;
    716             case  1: current = current->left;  break;
    717             default: found = current;           //  In case of duplicates,
    718                      current = current->left;  //  get the first one.
    719         }
    720 
    721     return found;
    722 }
    723 
    724 /*
    725  *@@ treeFindGEID:
    726  *      finds a node with ID greater than or equal to provided.
    727  *      To find a tree node, your comparison function must
    728  *      compare the tree node IDs.
    729  */
    730 
    731 void* treeFindGEID(TREE **root,
    732                    unsigned long idFind)
    733 {
    734     TREE    *current = *root,
    735             *found;
    736 
    737     found = NULL;
    738     while (current != TREE_NULL)
    739         switch (fnCompareIDs(current->id, idFind))
    740         {
    741             case -1: current = current->right; break;
    742             default: found = current;
    743                      current = current->left;
    744         }
    745 
    746     return found;
    747 }
    748 
    749 /*
    750  *@@ treeFindEQNode:
    751  *      finds a node with ID exactly matching that provided.
    752  *      To find a tree node, your comparison function must
    753  *      compare the tree nodes.
    754  */
    755 
    756 void* treeFindEQNode(TREE **root,
    757                      TREE *nodeFind,
    758                      FNTREE_COMPARE_NODES *comp)
    759 {
    760     TREE    *current = *root,
    761             *found;
    762 
    763     found = NULL;
    764     while (current != TREE_NULL)
    765         switch (comp(current, nodeFind))
    766         {
    767             case -1: current = current->right; break;
    768             case  1: current = current->left;  break;
    769             default: found = current;           //  In case of duplicates,
    770                      current = current->left;  //  get the first one.
    771         }
    772 
    773     return found;
    774 }
    775 
    776 /*
    777  *@@ treeFindGENode:
    778  *      finds a node with ID greater than or equal to provided.
    779  *      To find a tree node, your comparison function must
    780  *      compare the tree nodes.
    781  */
    782 
    783 void* treeFindGENode(TREE **root,
    784                      TREE *nodeFind,
    785                      FNTREE_COMPARE_NODES *comp)
    786 {
    787     TREE    *current = *root,
    788             *found;
    789 
    790     found = NULL;
    791     while (current != TREE_NULL)
    792         switch (comp(current, nodeFind))
    793         {
    794             case -1: current = current->right; break;
    795             default: found = current;
    796                      current = current->left;
    797         }
    798 
    799     return found;
    800 }
    801 
    802 /*
    803  *@@ treeFindLTNode:
    804  *      finds a node with Node less than provided.
    805  *      To find a tree node, your comparison function must
    806  *      compare the tree nodes.
    807  */
    808 
    809 void* treeFindLTNode(TREE **root,
    810                      TREE *nodeFind,
    811                      FNTREE_COMPARE_NODES *comp)
    812 {
    813     TREE    *current = *root,
    814             *found;
    815 
    816     found = NULL;
    817     while (current != TREE_NULL)
    818         switch (comp(current, nodeFind))
    819         {
    820             case -1: found = current;
    821                      current = current->right; break;
    822             default: current = current->left;
    823         }
    824 
    825     return found;
    826 }
    827 
    828 /*
    829  *@@ treeFindLENode:
    830  *      finds a node with Node less than or equal to provided.
    831  *      To find a tree node, your comparison function must
    832  *      compare the tree nodes.
    833  */
    834 
    835 void* treeFindLENode(TREE **root,
    836                      TREE *nodeFind,
    837                      FNTREE_COMPARE_NODES *comp)
    838 {
    839     TREE    *current = *root,
    840             *found;
    841 
    842     found = NULL;
    843     while (current != TREE_NULL)
    844         switch (comp(current, nodeFind))
    845         {
    846             case 1 : current = current->left;  break;
    847             default: found = current;
    848                      current = current->right;
    849         }
    850 
    851     return found;
    852 }
    853 
    854 /*
    855  *@@ treeFindGTNode:
    856  *      finds a node with Node greater than provided.
    857  *      To find a tree node, your comparison function must
    858  *      compare the tree nodes.
    859  */
    860 
    861 void* treeFindGTNode(TREE **root,
    862                      TREE *nodeFind,
    863                      FNTREE_COMPARE_NODES *comp)
    864 {
    865     TREE    *current = *root,
    866             *found;
    867 
    868     found = NULL;
    869     while (current != TREE_NULL)
    870         switch (comp(current, nodeFind))
    871         {
    872             case 1 : found = current;
    873                      current = current->left; break;
    874             default: current = current->right;
    875         }
    876 
    877     return found;
    878 }
    879 
    880 /*
    881  *@@ treeFindEQID:
    882  *      finds a node with data exactly matching that provided.
    883  *      To find a tree node, your comparison function must
    884  *      compare a tree member with external data.
    885  *
    886  *      This is useful for finding a tree item from a string ID.
    887  *
    888  *      Make sure to use treeInsertNode and compare according
    889  *      to a string member, and then write a second compare
    890  *      function for this function which compares the string
    891  *      member to an external string.
    892  */
    893 
    894 void* treeFindEQData(TREE **root,
    895                      void *pData,
    896                      FNTREE_COMPARE_DATA *comp)
    897 {
    898     TREE    *current = *root,
    899             *found = NULL;
    900 
    901     while (current != TREE_NULL)
    902         switch (comp(current, pData))
    903         {
    904             case -1: current = current->right; break;
    905             case  1: current = current->left;  break;
    906             default: found = current;           //  In case of duplicates,
    907                      current = current->left;  //  get the first one.
    908         }
    909 
    910     return found;
    911 }
    912 
    913 /*
    914  *@@ treeTraverse:
    915  *      traverses the specified tree, calling a processing function
    916  *      for each tree node.
    917  *
    918  *      The processing function ("process") must be declared as
    919  *      follows:
    920  *
    921  +          void fnProcess(TREE *t,         // current tree node
    922  +                         void *pUser);    // user data
    923  *
    924  *      and will receive the "pUser" parameter, which you can use
    925  *      as a data pointer to some structure for whatever you like.
    926  *
    927  *      WARNING: This function recurses and can use up a lot of
    928  *      stack. For very deep trees, traverse the tree using
    929  *      treeFirst and treeNext instead. See treeNext for a sample.
    930  *
    931  *      "method" specifies in which order the nodes are traversed.
    932  *      This can be:
    933  *
    934  *      -- 1: current node first, then left node, then right node.
    935  *      -- 2: left node first, then right node, then current node.
    936  *      -- 0 or other: left node first, then current node, then right node.
    937  *           This is the sorted order.
    938  */
    939 
    940 void treeTraverse(TREE *tree,               // in: root of tree
    941                   TREE_PROCESS *process,    // in: callback for each node
    942                   void *pUser,              // in: user param for callback
    943                   int method)               // in: traversal mode
    944 {
    945     if (    (!tree)
    946          || (tree == TREE_NULL))
    947         return;
    948 
    949     if (method == 1)
    950     {
    951         process(tree, pUser);
    952         treeTraverse (((TREE*)tree)->left,  process, pUser, method);
    953         treeTraverse (((TREE*)tree)->right, process, pUser, method);
    954     }
    955     else if (method == 2)
    956     {
    957         treeTraverse (((TREE*)tree)->left,  process, pUser, method);
    958         treeTraverse (((TREE*)tree)->right, process, pUser, method);
    959         process(tree, pUser);
    960     }
    961     else
    962     {
    963         treeTraverse (((TREE*)tree)->left,  process, pUser, method);
    964         process(tree, pUser);
    965         treeTraverse (((TREE*)tree)->right, process, pUser, method);
    966     }
     906        {
     907            current = (iResult < 0) // compLT (key, current->key)
     908                ? current->left
     909                : current->right;
     910        }
     911    }
     912
     913    return 0;
    967914}
    968915
    … …  
    974921 */
    975922
    976 void* treeFirst(TREE *tree)
    977 {
    978     TREE
    979        *current;
    980 
    981     if (    (!tree)
    982          || (tree == TREE_NULL)
     923TREE* treeFirst(TREE *r)
     924{
     925    TREE    *p;
     926
     927    if (    (!r)
     928         || (r == LEAF)
    983929       )
    984930        return NULL;
    985931
    986     current = tree;
    987     while (current->left != TREE_NULL)
    988         current = current->left;
    989 
    990     return current;
     932    p = r;
     933    while (p->left != LEAF)
     934        p = p->left;
     935
     936    return p;
    991937}
    992938
    … …  
    996942 */
    997943
    998 void* treeLast(TREE *tree)
    999 {
    1000     TREE
    1001        *current;
    1002 
    1003     if (    (!tree)
    1004          || (tree == TREE_NULL))
     944TREE* treeLast(TREE *r)
     945{
     946    TREE    *p;
     947
     948    if (    (!r)
     949         || (r == LEAF))
    1005950        return NULL;
    1006951
    1007     current = tree;
    1008     while (current->right != TREE_NULL)
    1009         current = current->right;
    1010 
    1011     return current;
     952    p = r;
     953    while (p->right != LEAF)
     954        p = p->right;
     955
     956    return p;
    1012957}
    1013958
    … …  
    1016961 *      finds and returns the next node in a tree.
    1017962 *
    1018  *      Example for traversing a whole tree if you don't
    1019  *      want to use treeTraverse:
     963 *      Example for traversing a whole tree:
    1020964 *
    1021965 +          TREE    *TreeRoot;
    … …  
    1031975 */
    1032976
    1033 void* treeNext(TREE *tree)
    1034 {
    1035     TREE
    1036        *current,
    1037        *child;
    1038 
    1039     if (    (!tree)
    1040          || (tree == TREE_NULL)
     977TREE* treeNext(TREE *r)
     978{
     979    TREE    *p,
     980            *child;
     981
     982    if (    (!r)
     983         || (r == LEAF)
    1041984       )
    1042985        return NULL;
    1043986
    1044     current = tree;
    1045     if (current->right != TREE_NULL)
    1046         return treeFirst (current->right);
     987    p = r;
     988    if (p->right != LEAF)
     989        return treeFirst (p->right);
    1047990    else
    1048991    {
    1049         current = tree;
    1050         child   = TREE_NULL;
    1051         while (    (current->parent)
    1052                 && (current->right == child)
     992        p = r;
     993        child   = LEAF;
     994        while (    (p->parent)
     995                && (p->right == child)
    1053996              )
    1054997        {
    1055             child = current;
    1056             current = current->parent;
    1057         }
    1058         if (current->right != child)
    1059             return current;
     998            child = p;
     999            p = p->parent;
     1000        }
     1001        if (p->right != child)
     1002            return p;
    10601003        else
    10611004            return NULL;
    … …  
    10681011 */
    10691012
    1070 void* treePrev(TREE *tree)
    1071 {
    1072     TREE
    1073        *current,
    1074        *child;
    1075 
    1076     if (    (!tree)
    1077          || (tree == TREE_NULL))
     1013TREE* treePrev(TREE *r)
     1014{
     1015    TREE    *p,
     1016            *child;
     1017
     1018    if (    (!r)
     1019         || (r == LEAF))
    10781020        return NULL;
    10791021
    1080     current = tree;
    1081     if (current->left != TREE_NULL)
    1082         return treeLast (current->left);
     1022    p = r;
     1023    if (p->left != LEAF)
     1024        return treeLast (p->left);
    10831025    else
    10841026    {
    1085         current = tree;
    1086         child   = TREE_NULL;
    1087         while ((current->parent)
    1088            &&  (current->left == child))
    1089         {
    1090             child = current;
    1091             current = current->parent;
    1092         }
    1093         if (current->left != child)
    1094             return current;
     1027        p = r;
     1028        child   = LEAF;
     1029        while ((p->parent)
     1030           &&  (p->left == child))
     1031        {
     1032            child = p;
     1033            p = p->parent;
     1034        }
     1035        if (p->left != child)
     1036            return p;
    10951037        else
    10961038            return NULL;
    … …  
    11251067 +          // add stuff to the tree
    11261068 +          TREE    *pNewNode = malloc(...);
    1127  +          treeInsertID(&G_TreeRoot, pNewNode, FALSE)
     1069 +          treeInsert(&G_TreeRoot, pNewNode, fnCompare)
    11281070 +
    11291071 +          // now delete all nodes
    … …  
    11861128}
    11871129
    1188 
     1130/* void main(int argc, char **argv) {
     1131    int maxnum, ct;
     1132    recType rec;
     1133    keyType key;
     1134    statusEnum status;
     1135
     1136    maxnum = atoi(argv[1]);
     1137
     1138    printf("maxnum = %d\n", maxnum);
     1139    for (ct = maxnum; ct; ct--) {
     1140        key = rand() % 9 + 1;
     1141        if ((status = find(key, &rec)) == STATUS_OK) {
     1142            status = delete(key);
     1143            if (status) printf("fail: status = %d\n", status);
     1144        } else {
     1145            status = insert(key, &rec);
     1146            if (status) printf("fail: status = %d\n", status);
     1147        }
     1148    }
     1149} */
Note: See TracChangeset for help on using the changeset viewer.