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  * Lock the binary tree
  61  */
  62 inline VOID
  63 ExpLockBinaryTree(PBINARY_TREE Tree,
  64  PKIRQL OldIrql)
  65 {
  66         if (Tree->UseNonPagedPool)
  67           {
  68       KeAcquireSpinLock(&Tree->Lock.NonPaged, OldIrql);
  69           }
  70         else
  71                 {
  72       ExAcquireFastMutex(&Tree->Lock.Paged);
  73                 }
  74 }
  75
  76
  77 /*
  78  * Unlock the binary tree
  79  */
  80 inline VOID
  81 ExpUnlockBinaryTree(PBINARY_TREE Tree,
  82   PKIRQL OldIrql)
  83 {
  84         if (Tree->UseNonPagedPool)
  85           {
  86       KeReleaseSpinLock(&Tree->Lock.NonPaged, *OldIrql);
  87           }
  88         else
  89                 {
  90       ExReleaseFastMutex(&Tree->Lock.Paged);
  91                 }
  92 }
  93
  94
  95 /*
  96  * Allocate resources for a new node and initialize it.
  97  */
  98 inline PBINARY_TREE_NODE
  99 ExpCreateBinaryTreeNode(PBINARY_TREE Tree,
 100   PBINARY_TREE_NODE Parent,
 101   PVOID Value)
 102 {
 103   PBINARY_TREE_NODE Node;
 104
 105         if (Tree->UseNonPagedPool)
 106           {
 107       Node = (PBINARY_TREE_NODE) ExAllocateFromNPagedLookasideList(&Tree->List.NonPaged);
 108           }
 109         else
 110                 {
 111       Node = (PBINARY_TREE_NODE) ExAllocateFromPagedLookasideList(&Tree->List.Paged);
 112                 }
 113
 114   if (Node)
 115                 {
 116             ExpBinaryTreeParentNode(Node)     = Parent;
 117       ExpBinaryTreeLeftChildNode(Node)  = NULL;
 118       ExpBinaryTreeRightChildNode(Node) = NULL;
 119       ExpBinaryTreeNodeValue(Node)      = Value;
 120                 }
 121
 122   return Node;
 123 }
 124
 125
 126 /*
 127  * Release resources for the node.
 128  */
 129 inline VOID
 130 ExpDestroyBinaryTreeNode(PBINARY_TREE Tree,
 131   PBINARY_TREE_NODE  Node)
 132 {
 133         if (Tree->UseNonPagedPool)
 134           {
 135       ExFreeToNPagedLookasideList(&Tree->List.NonPaged, Node);
 136           }
 137         else
 138                 {
 139       ExFreeToPagedLookasideList(&Tree->List.Paged, Node);
 140                 }
 141 }
 142
 143
 144 /*
 145  * Replaces a child node of a node with a new node.
 146  * The lock for the tree must be acquired when this routine is called.
 147  */
 148 inline VOID
 149 ExpBinaryTreeReplaceChildNode(PBINARY_TREE_NODE Child,
 150   PBINARY_TREE_NODE NewChild)
 151 {
 152   if (ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Child)) == Child)
 153     {
 154       ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Child)) = NewChild;
 155     }
 156         else
 157                 {
 158       ExpBinaryTreeRightChildNode(ExpBinaryTreeParentNode(Child)) = NewChild;
 159                 }
 160 }
 161
 162
 163 /*
 164  * Returns the sibling node of a node.
 165  * The lock for the tree must be acquired when this routine is called.
 166  */
 167 inline PBINARY_TREE_NODE
 168 ExpSiblingBinaryTreeNode(PBINARY_TREE Tree,
 169   PBINARY_TREE_NODE Node)
 170 {
 171   if (Node == ExpBinaryTreeRootNode(Tree))
 172                 {
 173       return NULL;
 174                 }
 175   else
 176     {
 177       if (ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Node)) == Node)
 178                     {
 179           return ExpBinaryTreeRightChildNode(ExpBinaryTreeParentNode(Node));
 180         }
 181                         else
 182                           {
 183                 return ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Node));
 184         }
 185                 }
 186 }
 187
 188
 189 /*
 190  * Expands an external node to an internal node.
 191  * The lock for the tree must be acquired when this routine is called.
 192  */
 193 VOID
 194 ExpExpandExternalBinaryTreeNode(PBINARY_TREE Tree,
 195   PBINARY_TREE_NODE Node)
 196 {
 197   ExpBinaryTreeLeftChildNode(Node) = ExpCreateBinaryTreeNode(Tree, Node, NULL);
 198
 199   if (!ExpBinaryTreeLeftChildNode(Node))
 200                 {
 201       /* FIXME: Throw exception */
 202       DbgPrint("ExpCreateBinaryTreeNode() failed\n");
 203                 }
 204
 205   ExpBinaryTreeRightChildNode(Node) = ExpCreateBinaryTreeNode(Tree, Node, NULL);
 206
 207   if (!ExpBinaryTreeRightChildNode(Node))
 208                 {
 209       ExpDestroyBinaryTreeNode(Tree, ExpBinaryTreeLeftChildNode(Node));
 210       /* FIXME: Throw exception */
 211       DbgPrint("ExpCreateBinaryTreeNode() failed\n");
 212                 }
 213 }
 214
 215
 216 /*
 217  * Searches a tree for a node with the specified key. If a node with the
 218  * specified key is not found, the external node where it should be is
 219  * returned.
 220  * The lock for the tree must be acquired when this routine is called.
 221  */
 222 inline PBINARY_TREE_NODE
 223 ExpSearchBinaryTree(PBINARY_TREE  Tree,
 224   PVOID  Key,
 225   PBINARY_TREE_NODE  Node)
 226 {
 227   LONG Equality;
 228
 229   /* FIXME: Possibly do this iteratively due to the small kernel-mode stack */
 230
 231   if (ExpIsExternalBinaryTreeNode(Node))
 232     {
 233       return Node;
 234     }
 235
 236   Equality = (*Tree->Compare)(Key, ExpBinaryTreeNodeKey(Node));
 237
 238   if (ExpBinaryTreeNodeEqual(Equality))
 239     {
 240       return Node;
 241     }
 242
 243   if (ExpBinaryTreeNodeLess(Equality))
 244     {
 245       return ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeLeftChildNode(Node));
 246     }
 247
 248 /*  if (ExpBinaryTreeNodeMore(Equality)) */
 249     {
 250       return ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeRightChildNode(Node));
 251     }
 252 }
 253
 254
 255 /*
 256  * Removes an external node and it's parent node from the tree.
 257  * The lock for the tree must be acquired when this routine is called.
 258  */
 259 VOID
 260 ExpRemoveAboveExternalBinaryTreeNode(PBINARY_TREE Tree,
 261   PBINARY_TREE_NODE Node)
 262 {
 263   assertmsg(ExpIsExternalBinaryTreeNode(Node), ("Node is not external"));
 264
 265   if (Node == ExpBinaryTreeRootNode(Tree))
 266                 {
 267       return;
 268                 }
 269   else
 270                 {
 271       PBINARY_TREE_NODE GrandParent;
 272             PBINARY_TREE_NODE NewChild;
 273
 274       GrandParent = ExpBinaryTreeParentNode(ExpBinaryTreeParentNode(Node));
 275             NewChild = ExpSiblingBinaryTreeNode(Tree, Node);
 276
 277       if (GrandParent != NULL)
 278         {
 279           ExpBinaryTreeReplaceChildNode(ExpBinaryTreeParentNode(Node), NewChild);
 280         }
 281
 282             ExpDestroyBinaryTreeNode(Tree, ExpBinaryTreeParentNode(Node));
 283             ExpDestroyBinaryTreeNode(Tree, Node);
 284                 }
 285 }
 286
 287
 288 /*
 289  * Release resources used by nodes of a binary (sub)tree.
 290  */
 291 VOID
 292 ExpDeleteBinaryTree(PBINARY_TREE Tree,
 293   PBINARY_TREE_NODE Node)
 294 {
 295   /* FIXME: Possibly do this iteratively due to the small kernel-mode stack */
 296
 297   if (ExpIsInternalBinaryTreeNode(Node))
 298     {
 299       ExpDeleteBinaryTree(Tree, ExpBinaryTreeLeftChildNode(Node));
 300       ExpDeleteBinaryTree(Tree, ExpBinaryTreeRightChildNode(Node));
 301     }
 302
 303   ExpDestroyBinaryTreeNode(Tree, Node);
 304 }
 305
 306
 307 /*
 308  * Default key compare function. Compares the integer values of the two keys.
 309  */
 310 LONG STDCALL
 311 ExpBinaryTreeDefaultCompare(PVOID  Key1,
 312   PVOID  Key2)
 313 {
 314   if (Key1 == Key2)
 315     return 0;
 316
 317   return (((LONG_PTR) Key1 < (LONG_PTR) Key2) ? -1 : 1);
 318 }
 319
 320
 321 /*
 322  * Initializes a binary tree.
 323  */
 324 BOOLEAN STDCALL
 325 ExInitializeBinaryTree(IN PBINARY_TREE  Tree,
 326   IN PKEY_COMPARATOR  Compare,
 327   IN BOOLEAN  UseNonPagedPool)
 328 {
 329   RtlZeroMemory(Tree, sizeof(BINARY_TREE));
 330
 331   Tree->Compare = (Compare == NULL)
 332     ? ExpBinaryTreeDefaultCompare : Compare;
 333
 334   Tree->UseNonPagedPool = UseNonPagedPool;
 335
 336   if (UseNonPagedPool)
 337     {
 338                   ExInitializeNPagedLookasideList(
 339                     &Tree->List.NonPaged,           /* Lookaside list */
 340                     NULL,                           /* Allocate routine */
 341                     NULL,                           /* Free routine */
 342                     0,                              /* Flags */
 343                     sizeof(BINARY_TREE_NODE),       /* Size of each entry */
 344                     TAG('E','X','B','T'),           /* Tag */
 345                     0);                             /* Depth */
 346
 347       KeInitializeSpinLock(&Tree->Lock.NonPaged);
 348                 }
 349                 else
 350                 {
 351                   ExInitializePagedLookasideList(
 352                     &Tree->List.Paged,              /* Lookaside list */
 353                     NULL,                           /* Allocate routine */
 354                     NULL,                           /* Free routine */
 355                     0,                              /* Flags */
 356                     sizeof(BINARY_TREE_NODE),       /* Size of each entry */
 357                     TAG('E','X','B','T'),           /* Tag */
 358                     0);                             /* Depth */
 359
 360       ExInitializeFastMutex(&Tree->Lock.Paged);
 361                 }
 362
 363   ExpBinaryTreeRootNode(Tree) = ExpCreateBinaryTreeNode(Tree, NULL, NULL);
 364
 365   if (ExpBinaryTreeRootNode(Tree) == NULL)
 366                 {
 367                   if (UseNonPagedPool)
 368                     {
 369           ExDeleteNPagedLookasideList(&Tree->List.NonPaged);
 370                           }
 371                         else
 372                                 {
 373           ExDeletePagedLookasideList(&Tree->List.Paged);
 374                                 }
 375       return FALSE;
 376                 }
 377   else
 378                 {
 379       return TRUE;
 380                 }
 381 }
 382
 383
 384 /*
 385  * Release resources used by a binary tree.
 386  */
 387 VOID STDCALL
 388 ExDeleteBinaryTree(IN PBINARY_TREE  Tree)
 389 {
 390   /* Remove all nodes */
 391   ExpDeleteBinaryTree(Tree, ExpBinaryTreeRootNode(Tree));
 392
 393   if (Tree->UseNonPagedPool)
 394     {
 395       ExDeleteNPagedLookasideList(&Tree->List.NonPaged);
 396           }
 397         else
 398                 {
 399       ExDeletePagedLookasideList(&Tree->List.Paged);
 400                 }
 401 }
 402
 403
 404 /*
 405  * Insert a value in a binary tree.
 406  */
 407 VOID STDCALL
 408 ExInsertBinaryTree(IN PBINARY_TREE  Tree,
 409   IN PVOID  Key,
 410   IN PVOID  Value)
 411 {
 412   PBINARY_TREE_NODE Node;
 413   KIRQL OldIrql;
 414
 415   /* FIXME: Use SEH for error reporting */
 416
 417   ExpLockBinaryTree(Tree, &OldIrql);
 418   Node = ExpBinaryTreeRootNode(Tree);
 419   do
 420     {
 421       Node = ExpSearchBinaryTree(Tree, Key, Node);
 422
 423                   if (ExpIsExternalBinaryTreeNode(Node))
 424                     {
 425           break;
 426                     }
 427                         else
 428                                 {
 429           Node = ExpBinaryTreeRightChildNode(Node);
 430                                 }
 431     } while (TRUE);
 432   ExpExpandExternalBinaryTreeNode(Tree, Node);
 433   ExpBinaryTreeNodeKey(Node)   = Key;
 434   ExpBinaryTreeNodeValue(Node) = Value;
 435   ExpUnlockBinaryTree(Tree, &OldIrql);
 436 }
 437
 438
 439 /*
 440  * Search for a value associated with a given key in a binary tree.
 441  */
 442 BOOLEAN STDCALL
 443 ExSearchBinaryTree(IN PBINARY_TREE  Tree,
 444   IN PVOID  Key,
 445   OUT PVOID  * Value)
 446 {
 447   PBINARY_TREE_NODE Node;
 448   KIRQL OldIrql;
 449
 450   ExpLockBinaryTree(Tree, &OldIrql);
 451   Node = ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeRootNode(Tree));
 452
 453   if (ExpIsInternalBinaryTreeNode(Node))
 454     {
 455             *Value = ExpBinaryTreeNodeValue(Node);
 456       ExpUnlockBinaryTree(Tree, &OldIrql);
 457             return TRUE;
 458           }
 459         else
 460                 {
 461       ExpUnlockBinaryTree(Tree, &OldIrql);
 462       return FALSE;
 463                 }
 464 }
 465
 466
 467 /*
 468  * Remove a value associated with a given key from a binary tree.
 469  */
 470 BOOLEAN STDCALL
 471 ExRemoveBinaryTree(IN PBINARY_TREE  Tree,
 472   IN PVOID  Key,
 473   IN PVOID  * Value)
 474 {
 475   PBINARY_TREE_NODE Node;
 476   KIRQL OldIrql;
 477
 478   ExpLockBinaryTree(Tree, &OldIrql);
 479
 480   Node = ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeRootNode(Tree));
 481
 482   if (ExpIsExternalBinaryTreeNode(Node))
 483                 {
 484       ExpUnlockBinaryTree(Tree, &OldIrql);
 485       return FALSE;
 486                 }
 487         else
 488                 {
 489       *Value = ExpBinaryTreeNodeValue(Node);
 490                   if (ExpIsExternalBinaryTreeNode(ExpBinaryTreeLeftChildNode(Node)))
 491                                 {
 492           Node = ExpBinaryTreeLeftChildNode(Node);
 493                                 }
 494       else if (ExpIsExternalBinaryTreeNode(ExpBinaryTreeRightChildNode(Node)))
 495                                 {
 496           Node = ExpBinaryTreeRightChildNode(Node);
 497                                 }
 498       else
 499         {
 500           // Node has internal children
 501           PBINARY_TREE_NODE SwapNode;
 502
 503           SwapNode = Node;
 504           Node = ExpBinaryTreeRightChildNode(SwapNode);
 505           do
 506             {
 507               Node = ExpBinaryTreeLeftChildNode(Node);
 508             } while (ExpIsInternalBinaryTreeNode(Node));
 509         }
 510
 511       ExpRemoveAboveExternalBinaryTreeNode(Tree, Node);
 512       ExpUnlockBinaryTree(Tree, &OldIrql);
 513       return TRUE;
 514                 }
 515 }
 516
 517 /* EOF */