reactos/ntoskrnl/ex/btree.c

   1 /*
   2  *  ReactOS kernel
   3  *  Copyright (C) 1998-2002 ReactOS Team
   4  *
   5  *  This program is free software; you can redistribute it and/or modify
   6  *  it under the terms of the GNU General Public License as published by
   7  *  the Free Software Foundation; either version 2 of the License, or
   8  *  (at your option) any later version.
   9  *
  10  *  This program is distributed in the hope that it will be useful,
  11  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  *  GNU General Public License for more details.
  14  *
  15  *  You should have received a copy of the GNU General Public License
  16  *  along with this program; if not, write to the Free Software
  17  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  */
  19 /*
  20  * PROJECT:         ReactOS kernel
  21  * FILE:            btree.c
  22  * PURPOSE:         Binary tree support
  23  * PROGRAMMER:      Casper S. Hornstrup (chorns@users.sourceforge.net)
  24  * UPDATE HISTORY:
  25  *      15-03-2002  CSH  Created
  26  */
  27 #include <ddk/ntddk.h>
  28 #include <internal/ex.h>
  29
  30 #define NDEBUG
  31 #include <internal/debug.h>
  32
  33 /* DATA **********************************************************************/
  34
  35 typedef struct _BINARY_TREE_NODE
  36 {
  37   struct _BINARY_TREE_NODE  * Parent;
  38   struct _BINARY_TREE_NODE  * LeftChild;
  39   struct _BINARY_TREE_NODE  * RightChild;
  40   PVOID  Key;
  41   PVOID  Value;
  42 } BINARY_TREE_NODE, *PBINARY_TREE_NODE;
  43
  44 /* FUNCTIONS ****************************************************************/
  45
  46 #define ExpBinaryTreeRootNode(Tree)(((PBINARY_TREE) (Tree))->RootNode)
  47 #define ExpIsExternalBinaryTreeNode(Node)(((Node)->LeftChild == NULL) && ((Node)->RightChild == NULL))
  48 #define ExpIsInternalBinaryTreeNode(Node)(!ExpIsExternalBinaryTreeNode(Node))
  49 #define ExpBinaryTreeNodeKey(Node)((Node)->Key)
  50 #define ExpBinaryTreeNodeValue(Node)((Node)->Value)
  51 #define ExpBinaryTreeParentNode(Node)((Node)->Parent)
  52 #define ExpBinaryTreeLeftChildNode(Node)((Node)->LeftChild)
  53 #define ExpBinaryTreeRightChildNode(Node)((Node)->RightChild)
  54 #define ExpBinaryTreeNodeEqual(Equality)((Equality) == 0)
  55 #define ExpBinaryTreeNodeLess(Equality)((Equality) < 0)
  56 #define ExpBinaryTreeNodeMore(Equality)((Equality) > 0)
  57
  58
  59 /*
  60  * Allocate resources for a new node and initialize it.
  61  */
  62 inline PBINARY_TREE_NODE
  63 ExpCreateBinaryTreeNode(PBINARY_TREE Tree,
  64   PBINARY_TREE_NODE Parent,
  65   PVOID Value)
  66 {
  67   PBINARY_TREE_NODE Node;
  68
  69   Node = (PBINARY_TREE_NODE) ExAllocateFromPagedLookasideList(&Tree->LookasideList);
  70
  71   if (Node)
  72                 {
  73             ExpBinaryTreeParentNode(Node)     = Parent;
  74       ExpBinaryTreeLeftChildNode(Node)  = NULL;
  75       ExpBinaryTreeRightChildNode(Node) = NULL;
  76       ExpBinaryTreeNodeValue(Node)      = Value;
  77                 }
  78
  79   return Node;
  80 }
  81
  82
  83 /*
  84  * Release resources for the node.
  85  */
  86 inline VOID
  87 ExpDestroyBinaryTreeNode(PBINARY_TREE Tree,
  88   PBINARY_TREE_NODE  Node)
  89 {
  90   ExFreeToPagedLookasideList(&Tree->LookasideList, Node);
  91 }
  92
  93
  94 /*
  95  * Replaces a child node of a node with a new node.
  96  * The lock for the tree must be acquired when this routine is called.
  97  */
  98 inline VOID
  99 ExpBinaryTreeReplaceChildNode(PBINARY_TREE_NODE Child,
 100   PBINARY_TREE_NODE NewChild)
 101 {
 102   if (ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Child)) == Child)
 103     {
 104       ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Child)) = NewChild;
 105     }
 106         else
 107                 {
 108       ExpBinaryTreeRightChildNode(ExpBinaryTreeParentNode(Child)) = NewChild;
 109                 }
 110 }
 111
 112
 113 /*
 114  * Returns the sibling node of a node.
 115  * The lock for the tree must be acquired when this routine is called.
 116  */
 117 inline PBINARY_TREE_NODE
 118 ExpSiblingBinaryTreeNode(PBINARY_TREE Tree,
 119   PBINARY_TREE_NODE Node)
 120 {
 121   if (Node == ExpBinaryTreeRootNode(Tree))
 122                 {
 123       return NULL;
 124                 }
 125   else
 126     {
 127       if (ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Node)) == Node)
 128                     {
 129           return ExpBinaryTreeRightChildNode(ExpBinaryTreeParentNode(Node));
 130         }
 131                         else
 132                           {
 133                 return ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Node));
 134         }
 135                 }
 136 }
 137
 138
 139 /*
 140  * Expands an external node to an internal node.
 141  * The lock for the tree must be acquired when this routine is called.
 142  */
 143 VOID
 144 ExpExpandExternalBinaryTreeNode(PBINARY_TREE Tree,
 145   PBINARY_TREE_NODE Node)
 146 {
 147   ExpBinaryTreeLeftChildNode(Node) = ExpCreateBinaryTreeNode(Tree, Node, NULL);
 148
 149   if (!ExpBinaryTreeLeftChildNode(Node))
 150                 {
 151       /* FIXME: Throw exception */
 152       DbgPrint("ExpCreateBinaryTreeNode() failed\n");
 153                 }
 154
 155   ExpBinaryTreeRightChildNode(Node) = ExpCreateBinaryTreeNode(Tree, Node, NULL);
 156
 157   if (!ExpBinaryTreeRightChildNode(Node))
 158                 {
 159       ExpDestroyBinaryTreeNode(Tree, ExpBinaryTreeLeftChildNode(Node));
 160       /* FIXME: Throw exception */
 161       DbgPrint("ExpCreateBinaryTreeNode() failed\n");
 162                 }
 163 }
 164
 165
 166 /*
 167  * Searches a tree for a node with the specified key. If a node with the
 168  * specified key is not found, the external node where it should be is
 169  * returned.
 170  * The lock for the tree must be acquired when this routine is called.
 171  */
 172 inline PBINARY_TREE_NODE
 173 ExpSearchBinaryTree(PBINARY_TREE  Tree,
 174   PVOID  Key,
 175   PBINARY_TREE_NODE  Node)
 176 {
 177   LONG Equality;
 178
 179   /* FIXME: Possibly do this iteratively due to the small kernel-mode stack */
 180
 181   if (ExpIsExternalBinaryTreeNode(Node))
 182     {
 183       return Node;
 184     }
 185
 186   Equality = (*Tree->Compare)(Key, ExpBinaryTreeNodeKey(Node));
 187
 188   if (ExpBinaryTreeNodeEqual(Equality))
 189     {
 190       return Node;
 191     }
 192
 193   if (ExpBinaryTreeNodeLess(Equality))
 194     {
 195       return ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeLeftChildNode(Node));
 196     }
 197
 198 /*  if (ExpBinaryTreeNodeMore(Equality)) */
 199     {
 200       return ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeRightChildNode(Node));
 201     }
 202 }
 203
 204
 205 /*
 206  * Removes an external node and it's parent node from the tree.
 207  * The lock for the tree must be acquired when this routine is called.
 208  */
 209 VOID
 210 ExpRemoveAboveExternalBinaryTreeNode(PBINARY_TREE Tree,
 211   PBINARY_TREE_NODE Node)
 212 {
 213   assertmsg(ExpIsExternalBinaryTreeNode(Node), ("Node is not external"));
 214
 215   if (Node == ExpBinaryTreeRootNode(Tree))
 216                 {
 217       return;
 218                 }
 219   else
 220                 {
 221       PBINARY_TREE_NODE GrandParent;
 222             PBINARY_TREE_NODE NewChild;
 223
 224       GrandParent = ExpBinaryTreeParentNode(ExpBinaryTreeParentNode(Node));
 225             NewChild = ExpSiblingBinaryTreeNode(Tree, Node);
 226
 227       if (GrandParent != NULL)
 228         {
 229           ExpBinaryTreeReplaceChildNode(ExpBinaryTreeParentNode(Node), NewChild);
 230         }
 231
 232             ExpDestroyBinaryTreeNode(Tree, ExpBinaryTreeParentNode(Node));
 233             ExpDestroyBinaryTreeNode(Tree, Node);
 234                 }
 235 }
 236
 237
 238 /*
 239  * Release resources used by nodes of a binary (sub)tree.
 240  */
 241 VOID
 242 ExpDeleteBinaryTree(PBINARY_TREE Tree,
 243   PBINARY_TREE_NODE Node)
 244 {
 245   /* FIXME: Possibly do this iteratively due to the small kernel-mode stack */
 246
 247   if (ExpIsInternalBinaryTreeNode(Node))
 248     {
 249       ExpDeleteBinaryTree(Tree, ExpBinaryTreeLeftChildNode(Node));
 250       ExpDeleteBinaryTree(Tree, ExpBinaryTreeRightChildNode(Node));
 251     }
 252
 253   ExpDestroyBinaryTreeNode(Tree, Node);
 254 }
 255
 256
 257 /*
 258  * Default key compare function. Compares the integer values of the two keys.
 259  */
 260 LONG STDCALL
 261 ExpBinaryTreeDefaultCompare(PVOID  Key1,
 262   PVOID  Key2)
 263 {
 264   if (Key1 == Key2)
 265     return 0;
 266
 267   return (((LONG_PTR) Key1 < (LONG_PTR) Key2) ? -1 : 1);
 268 }
 269
 270
 271 /*
 272  * Initializes a binary tree.
 273  */
 274 BOOLEAN STDCALL
 275 ExInitializeBinaryTree(IN PBINARY_TREE  Tree,
 276   IN PKEY_COMPARATOR  Compare)
 277 {
 278   RtlZeroMemory(Tree, sizeof(BINARY_TREE));
 279
 280   Tree->Compare = (Compare == NULL)
 281     ? ExpBinaryTreeDefaultCompare : Compare;
 282
 283   ExInitializePagedLookasideList(
 284     &Tree->LookasideList,           /* Lookaside list */
 285     NULL,                           /* Allocate routine */
 286     NULL,                           /* Free routine */
 287     0,                              /* Flags */
 288     sizeof(BINARY_TREE_NODE),       /* Size of each entry */
 289     TAG('E','X','B','T'),           /* Tag */
 290     0);                             /* Depth */
 291
 292   ExInitializeFastMutex(&Tree->Lock);
 293
 294   ExpBinaryTreeRootNode(Tree) = ExpCreateBinaryTreeNode(Tree, NULL, NULL);
 295
 296   if (ExpBinaryTreeRootNode(Tree) == NULL)
 297                 {
 298       ExDeletePagedLookasideList(&Tree->LookasideList);
 299       return FALSE;
 300                 }
 301   else
 302                 {
 303       return TRUE;
 304                 }
 305 }
 306
 307
 308 /*
 309  * Release resources used by a binary tree.
 310  */
 311 VOID STDCALL
 312 ExDeleteBinaryTree(IN PBINARY_TREE  Tree)
 313 {
 314   /* Remove all nodes */
 315   ExpDeleteBinaryTree(Tree, ExpBinaryTreeRootNode(Tree));
 316
 317   ExDeletePagedLookasideList(&Tree->LookasideList);
 318 }
 319
 320
 321 /*
 322  * Insert a value in a binary tree.
 323  */
 324 VOID STDCALL
 325 ExInsertBinaryTree(IN PBINARY_TREE  Tree,
 326   IN PVOID  Key,
 327   IN PVOID  Value)
 328 {
 329   PBINARY_TREE_NODE Node;
 330
 331   /* FIXME: Use SEH for error reporting */
 332
 333   ExAcquireFastMutex(&Tree->Lock);
 334   Node = ExpBinaryTreeRootNode(Tree);
 335   do
 336     {
 337       Node = ExpSearchBinaryTree(Tree, Key, Node);
 338
 339                   if (ExpIsExternalBinaryTreeNode(Node))
 340                     {
 341           break;
 342                     }
 343                         else
 344                                 {
 345           Node = ExpBinaryTreeRightChildNode(Node);
 346                                 }
 347     } while (TRUE);
 348   ExpExpandExternalBinaryTreeNode(Tree, Node);
 349   ExpBinaryTreeNodeKey(Node)   = Key;
 350   ExpBinaryTreeNodeValue(Node) = Value;
 351   ExReleaseFastMutex(&Tree->Lock);
 352 }
 353
 354
 355 /*
 356  * Search for a value associated with a given key in a binary tree.
 357  */
 358 BOOLEAN STDCALL
 359 ExSearchBinaryTree(IN PBINARY_TREE  Tree,
 360   IN PVOID  Key,
 361   OUT PVOID  * Value)
 362 {
 363   PBINARY_TREE_NODE Node;
 364
 365   ExAcquireFastMutex(&Tree->Lock);
 366   Node = ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeRootNode(Tree));
 367
 368   if (ExpIsInternalBinaryTreeNode(Node))
 369     {
 370             *Value = ExpBinaryTreeNodeValue(Node);
 371       ExReleaseFastMutex(&Tree->Lock);
 372             return TRUE;
 373           }
 374         else
 375                 {
 376       ExReleaseFastMutex(&Tree->Lock);
 377       return FALSE;
 378                 }
 379 }
 380
 381
 382 /*
 383  * Remove a value associated with a given key from a binary tree.
 384  */
 385 BOOLEAN STDCALL
 386 ExRemoveBinaryTree(IN PBINARY_TREE  Tree,
 387   IN PVOID  Key,
 388   IN PVOID  * Value)
 389 {
 390   PBINARY_TREE_NODE Node;
 391
 392   ExAcquireFastMutex(&Tree->Lock);
 393   Node = ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeRootNode(Tree));
 394
 395   if (ExpIsExternalBinaryTreeNode(Node))
 396                 {
 397       ExReleaseFastMutex(&Tree->Lock);
 398       return FALSE;
 399                 }
 400         else
 401                 {
 402       *Value = ExpBinaryTreeNodeValue(Node);
 403                   if (ExpIsExternalBinaryTreeNode(ExpBinaryTreeLeftChildNode(Node)))
 404                                 {
 405           Node = ExpBinaryTreeLeftChildNode(Node);
 406                                 }
 407       else if (ExpIsExternalBinaryTreeNode(ExpBinaryTreeRightChildNode(Node)))
 408                                 {
 409           Node = ExpBinaryTreeRightChildNode(Node);
 410                                 }
 411       else
 412         {
 413           // Node has internal children
 414           PBINARY_TREE_NODE SwapNode;
 415
 416           SwapNode = Node;
 417           Node = ExpBinaryTreeRightChildNode(SwapNode);
 418           do
 419             {
 420               Node = ExpBinaryTreeLeftChildNode(Node);
 421             } while (ExpIsInternalBinaryTreeNode(Node));
 422         }
 423
 424       ExpRemoveAboveExternalBinaryTreeNode(Tree, Node);
 425       ExReleaseFastMutex(&Tree->Lock);
 426       return TRUE;
 427                 }
 428 }
 429
 430 /* EOF */