reactos/lib/rtl/austin/tree.c

   1 /*
   2  * Austin---Astonishing Universal Search Tree Interface Novelty
   3  * Copyright (C) 2000 Kaz Kylheku <kaz@ashi.footprints.net>
   4  *
   5  * Free Software License:
   6  *
   7  * All rights are reserved by the author, with the following exceptions:
   8  * Permission is granted to freely reproduce and distribute this software,
   9  * possibly in exchange for a fee, provided that this copyright notice appears
  10  * intact. Permission is also granted to adapt this software to produce
  11  * derivative works, as long as the modified versions carry this copyright
  12  * notice and additional notices stating that the work has been modified.
  13  * This source code may be translated into executable form and incorporated
  14  * into proprietary software; there is no requirement for such software to
  15  * contain a copyright notice related to this source.
  16  *
  17  * $Id: tree.c,v 1.8 1999/12/09 05:38:52 kaz Exp $
  18  * $Name: austin_0_2 $
  19  */
  20 /*
  21  * Modified for use in ReactOS by arty
  22  */
  23 #include "rtl.h"
  24 #include "udict.h"
  25 #include "tree.h"
  26 #include "macros.h"
  27
  28 void udict_tree_delete(udict_t *ud, udict_node_t *node, udict_node_t **pswap, udict_node_t **pchild)
  29 {
  30     udict_node_t *nil = tree_null_priv(ud), *child, *delparent = node->parent;
  31     udict_node_t *next = node, *nextparent;
  32
  33     if( tree_root_priv(ud) == node )
  34         delparent = &ud->BalancedRoot;
  35
  36     if (node->left != nil && node->right != nil) {
  37         next = udict_tree_next(ud, node);
  38         nextparent = next->parent;
  39
  40         if( tree_root_priv(ud) == next )
  41             nextparent = &ud->BalancedRoot;
  42
  43         assert (next != nil);
  44         assert (next->parent != nil);
  45         assert (next->left == nil);
  46
  47         /*
  48          * First, splice out the successor from the tree completely, by
  49          * moving up its right child into its place.
  50          */
  51
  52         child = next->right;
  53         child->parent = nextparent;
  54
  55         if (nextparent->left == next) {
  56             nextparent->left = child;
  57         } else {
  58             assert (nextparent->right == next);
  59             nextparent->right = child;
  60         }
  61
  62         /*
  63          * Now that the successor has been extricated from the tree, install it
  64          * in place of the node that we want deleted.
  65          */
  66
  67         next->parent = delparent;
  68         next->left = node->left;
  69         next->right = node->right;
  70         next->left->parent = next;
  71         next->right->parent = next;
  72
  73         if (delparent->left == node) {
  74             delparent->left = next;
  75         } else {
  76             assert (delparent->right == node);
  77             delparent->right = next;
  78         }
  79
  80     } else {
  81         assert (node != nil);
  82         assert (node->left == nil || node->right == nil);
  83
  84         child = (node->left != nil) ? node->left : node->right;
  85         child->parent = delparent = node->parent;
  86
  87         if (node == delparent->left) {
  88             delparent->left = child;
  89         } else {
  90             assert (node == delparent->right);
  91             delparent->right = child;
  92         }
  93     }
  94
  95     node->parent = nil;
  96     node->right = nil;
  97     node->left = nil;
  98
  99     ud->nodecount--;
 100
 101     *pswap = next;
 102     *pchild = child;
 103 }
 104
 105 udict_node_t *udict_tree_lookup(udict_t *ud, const void *_key)
 106 {
 107     udict_node_t *root = tree_root_priv(ud);
 108     udict_node_t *nil = tree_null_priv(ud);
 109     int result;
 110
 111     /* simple binary search adapted for trees that contain duplicate keys */
 112
 113     while (root != nil) {
 114         result = ud->compare(ud, (void *)_key, key(root));
 115         if (result < 0)
 116             root = root->left;
 117         else if (result > 0)
 118             root = root->right;
 119         else {
 120             return root;
 121         }
 122     }
 123
 124     return 0;
 125 }
 126
 127 udict_node_t *udict_tree_lower_bound(udict_t *ud, const void *_key)
 128 {
 129     udict_node_t *root = tree_root_priv(ud);
 130     udict_node_t *nil = tree_null_priv(ud);
 131     udict_node_t *tentative = 0;
 132
 133     while (root != nil) {
 134         int result = ud->compare(ud, (void *)_key, key(root));
 135
 136         if (result > 0) {
 137             root = root->right;
 138         } else if (result < 0) {
 139             tentative = root;
 140             root = root->left;
 141         } else {
 142             return root;
 143         }
 144     }
 145
 146     return tentative;
 147 }
 148
 149 udict_node_t *udict_tree_upper_bound(udict_t *ud, const void *_key)
 150 {
 151     udict_node_t *root = tree_root_priv(ud);
 152     udict_node_t *nil = tree_null_priv(ud);
 153     udict_node_t *tentative = 0;
 154
 155     while (root != nil) {
 156         int result = ud->compare(ud, (void *)_key, key(root));
 157
 158         if (result < 0) {
 159             root = root->left;
 160         } else if (result > 0) {
 161             tentative = root;
 162             root = root->right;
 163         } else {
 164             return root;
 165         }
 166     }
 167
 168     return tentative;
 169 }
 170
 171 udict_node_t *udict_tree_first(udict_t *ud)
 172 {
 173     udict_node_t *nil = tree_null_priv(ud), *root = tree_root_priv(ud), *left;
 174
 175     if (root != nil)
 176         while ((left = root->left) != nil)
 177             root = left;
 178
 179     return (root == nil) ? 0 : root;
 180 }
 181
 182 udict_node_t *udict_tree_last(udict_t *ud)
 183 {
 184     udict_node_t *nil = tree_null_priv(ud), *root = tree_root_priv(ud), *right;
 185
 186     if (root != nil)
 187         while ((right = root->right) != nil)
 188             root = right;
 189
 190     return (root == nil) ? 0 : root;
 191 }
 192
 193 udict_node_t *udict_tree_next(udict_t *ud, udict_node_t *curr)
 194 {
 195     udict_node_t *nil = tree_null_priv(ud), *parent, *left;
 196
 197     if (curr->right != nil) {
 198         curr = curr->right;
 199         while ((left = curr->left) != nil)
 200             curr = left;
 201         return curr;
 202     }
 203
 204     parent = curr->parent;
 205
 206     while (parent != nil && curr == parent->right) {
 207         curr = parent;
 208         parent = curr->parent;
 209     }
 210
 211     return (parent == nil) ? 0 : parent;
 212 }
 213
 214 udict_node_t *udict_tree_prev(udict_t *ud, udict_node_t *curr)
 215 {
 216     udict_node_t *nil = tree_null_priv(ud), *parent, *right;
 217
 218     if (curr->left != nil) {
 219         curr = curr->left;
 220         while ((right = curr->right) != nil)
 221             curr = right;
 222         return curr;
 223     }
 224
 225     parent = curr->parent;
 226
 227     while (parent != nil && curr == parent->left) {
 228         curr = parent;
 229         parent = curr->parent;
 230     }
 231
 232     return (parent == nil) ? 0 : parent;
 233 }
 234
 235 /*
 236  * Perform a ``left rotation'' adjustment on the tree.  The given parent node P
 237  * and its right child C are rearranged so that the P instead becomes the left
 238  * child of C.   The left subtree of C is inherited as the new right subtree
 239  * for P.  The ordering of the keys within the tree is thus preserved.
 240  */
 241
 242 void udict_tree_rotate_left(udict_node_t *child, udict_node_t *parent)
 243 {
 244     udict_node_t *leftgrandchild, *grandpa;
 245
 246     assert (parent->right == child);
 247
 248     child = parent->right;
 249     parent->right = leftgrandchild = child->left;
 250     leftgrandchild->parent = parent;
 251
 252     child->parent = grandpa = parent->parent;
 253
 254     if (parent == grandpa->left) {
 255         grandpa->left = child;
 256     } else {
 257         assert (parent == grandpa->right);
 258         grandpa->right = child;
 259     }
 260
 261     child->left = parent;
 262     parent->parent = child;
 263 }
 264
 265
 266 /*
 267  * This operation is the ``mirror'' image of rotate_left. It is
 268  * the same procedure, but with left and right interchanged.
 269  */
 270
 271 void udict_tree_rotate_right(udict_node_t *child, udict_node_t *parent)
 272 {
 273     udict_node_t *rightgrandchild, *grandpa;
 274
 275     assert (parent->left == child);
 276
 277     parent->left = rightgrandchild = child->right;
 278     rightgrandchild->parent = parent;
 279
 280     child->parent = grandpa = parent->parent;
 281
 282     if (parent == grandpa->right) {
 283         grandpa->right = child;
 284     } else {
 285         assert (parent == grandpa->left);
 286         grandpa->left = child;
 287     }
 288
 289     child->right = parent;
 290     parent->parent = child;
 291 }
 292