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
  28 #include <ntoskrnl.h>
  29 #define NDEBUG
  30 #include <internal/debug.h>
  31
  32 /* DATA **********************************************************************/
  33
  34 typedef struct _BINARY_TREE_NODE
  35 {
  36   struct _BINARY_TREE_NODE  * Parent;
  37   struct _BINARY_TREE_NODE  * LeftChild;
  38   struct _BINARY_TREE_NODE  * RightChild;
  39   PVOID  Key;
  40   PVOID  Value;
  41 } BINARY_TREE_NODE, *PBINARY_TREE_NODE;
  42
  43 typedef struct _TRAVERSE_CONTEXT {
  44   PTRAVERSE_ROUTINE Routine;
  45   PVOID Context;
  46 } TRAVERSE_CONTEXT, *PTRAVERSE_CONTEXT;
  47
  48 /* FUNCTIONS ****************************************************************/
  49
  50 #define ExpBinaryTreeRootNode(Tree)(((PBINARY_TREE) (Tree))->RootNode)
  51 #define ExpBinaryTreeIsExternalNode(Node)(((Node)->LeftChild == NULL) && ((Node)->RightChild == NULL))
  52 #define ExpBinaryTreeIsInternalNode(Node)(!ExpBinaryTreeIsExternalNode(Node))
  53 #define ExpBinaryTreeNodeKey(Node)((Node)->Key)
  54 #define ExpBinaryTreeNodeValue(Node)((Node)->Value)
  55 #define ExpBinaryTreeParentNode(Node)((Node)->Parent)
  56 #define ExpBinaryTreeLeftChildNode(Node)((Node)->LeftChild)
  57 #define ExpBinaryTreeRightChildNode(Node)((Node)->RightChild)
  58 #define ExpBinaryTreeNodeEqual(Equality)((Equality) == 0)
  59 #define ExpBinaryTreeNodeLess(Equality)((Equality) < 0)
  60 #define ExpBinaryTreeNodeMore(Equality)((Equality) > 0)
  61
  62
  63 /*
  64  * Lock the binary tree
  65  */
  66 inline VOID
  67 ExpLockBinaryTree(PBINARY_TREE Tree,
  68  PKIRQL OldIrql)
  69 {
  70         if (Tree->UseNonPagedPool)
  71           {
  72       KeAcquireSpinLock(&Tree->Lock.NonPaged, OldIrql);
  73           }
  74         else
  75                 {
  76       ExAcquireFastMutex(&Tree->Lock.Paged);
  77                 }
  78 }
  79
  80
  81 /*
  82  * Unlock the binary tree
  83  */
  84 inline VOID
  85 ExpUnlockBinaryTree(PBINARY_TREE Tree,
  86   PKIRQL OldIrql)
  87 {
  88         if (Tree->UseNonPagedPool)
  89           {
  90       KeReleaseSpinLock(&Tree->Lock.NonPaged, *OldIrql);
  91           }
  92         else
  93                 {
  94       ExReleaseFastMutex(&Tree->Lock.Paged);
  95                 }
  96 }
  97
  98
  99 /*
 100  * Allocate resources for a new node and initialize it.
 101  */
 102 inline PBINARY_TREE_NODE
 103 ExpCreateBinaryTreeNode(PBINARY_TREE Tree,
 104   PBINARY_TREE_NODE Parent,
 105   PVOID Value)
 106 {
 107   PBINARY_TREE_NODE Node;
 108
 109         if (Tree->UseNonPagedPool)
 110           {
 111       Node = (PBINARY_TREE_NODE) ExAllocateFromNPagedLookasideList(&Tree->List.NonPaged);
 112           }
 113         else
 114                 {
 115       Node = (PBINARY_TREE_NODE) ExAllocateFromPagedLookasideList(&Tree->List.Paged);
 116                 }
 117
 118   if (Node)
 119                 {
 120             ExpBinaryTreeParentNode(Node)     = Parent;
 121       ExpBinaryTreeLeftChildNode(Node)  = NULL;
 122       ExpBinaryTreeRightChildNode(Node) = NULL;
 123       ExpBinaryTreeNodeValue(Node)      = Value;
 124                 }
 125
 126   return Node;
 127 }
 128
 129
 130 /*
 131  * Release resources for the node.
 132  */
 133 inline VOID
 134 ExpDestroyBinaryTreeNode(PBINARY_TREE Tree,
 135   PBINARY_TREE_NODE  Node)
 136 {
 137         if (Tree->UseNonPagedPool)
 138           {
 139       ExFreeToNPagedLookasideList(&Tree->List.NonPaged, Node);
 140           }
 141         else
 142                 {
 143       ExFreeToPagedLookasideList(&Tree->List.Paged, Node);
 144                 }
 145 }
 146
 147
 148 /*
 149  * Replaces a child node of a node with a new node.
 150  * The lock for the tree must be acquired when this routine is called.
 151  */
 152 inline VOID
 153 ExpBinaryTreeReplaceChildNode(PBINARY_TREE_NODE Child,
 154   PBINARY_TREE_NODE NewChild)
 155 {
 156   if (ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Child)) == Child)
 157     {
 158       ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Child)) = NewChild;
 159     }
 160         else
 161                 {
 162       ExpBinaryTreeRightChildNode(ExpBinaryTreeParentNode(Child)) = NewChild;
 163                 }
 164 }
 165
 166
 167 /*
 168  * Returns the sibling node of a node.
 169  * The lock for the tree must be acquired when this routine is called.
 170  */
 171 inline PBINARY_TREE_NODE
 172 ExpSiblingBinaryTreeNode(PBINARY_TREE Tree,
 173   PBINARY_TREE_NODE Node)
 174 {
 175   if (Node == ExpBinaryTreeRootNode(Tree))
 176                 {
 177       return NULL;
 178                 }
 179   else
 180     {
 181       if (ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Node)) == Node)
 182                     {
 183           return ExpBinaryTreeRightChildNode(ExpBinaryTreeParentNode(Node));
 184         }
 185                         else
 186                           {
 187                 return ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Node));
 188         }
 189                 }
 190 }
 191
 192
 193 /*
 194  * Expands an external node to an internal node.
 195  * The lock for the tree must be acquired when this routine is called.
 196  */
 197 VOID
 198 ExpExpandExternalBinaryTreeNode(PBINARY_TREE Tree,
 199   PBINARY_TREE_NODE Node)
 200 {
 201   ExpBinaryTreeLeftChildNode(Node) = ExpCreateBinaryTreeNode(Tree, Node, NULL);
 202
 203   if (!ExpBinaryTreeLeftChildNode(Node))
 204                 {
 205       /* FIXME: Throw exception */
 206       DbgPrint("ExpCreateBinaryTreeNode() failed\n");
 207                 }
 208
 209   ExpBinaryTreeRightChildNode(Node) = ExpCreateBinaryTreeNode(Tree, Node, NULL);
 210
 211   if (!ExpBinaryTreeRightChildNode(Node))
 212                 {
 213       ExpDestroyBinaryTreeNode(Tree, ExpBinaryTreeLeftChildNode(Node));
 214       /* FIXME: Throw exception */
 215       DbgPrint("ExpCreateBinaryTreeNode() failed\n");
 216                 }
 217 }
 218
 219
 220 /*
 221  * Searches a tree for a node with the specified key. If a node with the
 222  * specified key is not found, the external node where it should be is
 223  * returned.
 224  * The lock for the tree must be acquired when this routine is called.
 225  */
 226 inline PBINARY_TREE_NODE
 227 ExpSearchBinaryTree(PBINARY_TREE  Tree,
 228   PVOID  Key,
 229   PBINARY_TREE_NODE  Node)
 230 {
 231   LONG Equality;
 232
 233   /* FIXME: Possibly do this iteratively due to the small kernel-mode stack */
 234
 235   if (ExpBinaryTreeIsExternalNode(Node))
 236     {
 237       return Node;
 238     }
 239
 240   Equality = (*Tree->Compare)(Key, ExpBinaryTreeNodeKey(Node));
 241
 242   if (ExpBinaryTreeNodeEqual(Equality))
 243     {
 244       return Node;
 245     }
 246
 247   if (ExpBinaryTreeNodeLess(Equality))
 248     {
 249       return ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeLeftChildNode(Node));
 250     }
 251
 252 /*  if (ExpBinaryTreeNodeMore(Equality)) */
 253     {
 254       return ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeRightChildNode(Node));
 255     }
 256 }
 257
 258
 259 /*
 260  * Removes an external node and it's parent node from the tree.
 261  * The lock for the tree must be acquired when this routine is called.
 262  */
 263 VOID
 264 ExpRemoveAboveExternalBinaryTreeNode(PBINARY_TREE Tree,
 265   PBINARY_TREE_NODE Node)
 266 {
 267   assertmsg(ExpBinaryTreeIsExternalNode(Node), ("Node is not external"));
 268
 269   if (Node == ExpBinaryTreeRootNode(Tree))
 270                 {
 271       return;
 272                 }
 273   else
 274                 {
 275       PBINARY_TREE_NODE GrandParent;
 276             PBINARY_TREE_NODE NewChild;
 277
 278       GrandParent = ExpBinaryTreeParentNode(ExpBinaryTreeParentNode(Node));
 279             NewChild = ExpSiblingBinaryTreeNode(Tree, Node);
 280
 281       if (GrandParent != NULL)
 282         {
 283           ExpBinaryTreeReplaceChildNode(ExpBinaryTreeParentNode(Node), NewChild);
 284         }
 285
 286             ExpDestroyBinaryTreeNode(Tree, ExpBinaryTreeParentNode(Node));
 287             ExpDestroyBinaryTreeNode(Tree, Node);
 288                 }
 289 }
 290
 291
 292 /*
 293  * Release resources used by nodes of a binary (sub)tree.
 294  */
 295 VOID
 296 ExpDeleteBinaryTree(PBINARY_TREE Tree,
 297   PBINARY_TREE_NODE Node)
 298 {
 299   /* FIXME: Possibly do this iteratively due to the small kernel-mode stack */
 300
 301   if (ExpBinaryTreeIsInternalNode(Node))
 302     {
 303       ExpDeleteBinaryTree(Tree, ExpBinaryTreeLeftChildNode(Node));
 304       ExpDeleteBinaryTree(Tree, ExpBinaryTreeRightChildNode(Node));
 305     }
 306
 307   ExpDestroyBinaryTreeNode(Tree, Node);
 308 }
 309
 310
 311 /*
 312  * Traverse a binary tree using preorder traversal method.
 313  * Returns FALSE, if the traversal was terminated prematurely or
 314  * TRUE if the callback routine did not request that the traversal
 315  * be terminated prematurely.
 316  * The lock for the tree must be acquired when this routine is called.
 317  */
 318 BOOLEAN
 319 ExpTraverseBinaryTreePreorder(PTRAVERSE_CONTEXT Context,
 320   PBINARY_TREE_NODE Node)
 321 {
 322   if (ExpBinaryTreeIsInternalNode(Node))
 323                 {
 324                   /* Call the traversal routine */
 325                   if (!(*Context->Routine)(Context->Context,
 326                     ExpBinaryTreeNodeKey(Node),
 327                     ExpBinaryTreeNodeValue(Node)))
 328                     {
 329                       return FALSE;
 330                     }
 331
 332       /* Traverse left subtree */
 333       ExpTraverseBinaryTreePreorder(Context, ExpBinaryTreeLeftChildNode(Node));
 334
 335       /* Traverse right subtree */
 336       ExpTraverseBinaryTreePreorder(Context, ExpBinaryTreeRightChildNode(Node));
 337                 }
 338
 339   return TRUE;
 340 }
 341
 342
 343 /*
 344  * Traverse a binary tree using inorder traversal method.
 345  * Returns FALSE, if the traversal was terminated prematurely or
 346  * TRUE if the callback routine did not request that the traversal
 347  * be terminated prematurely.
 348  * The lock for the tree must be acquired when this routine is called.
 349  */
 350 BOOLEAN
 351 ExpTraverseBinaryTreeInorder(PTRAVERSE_CONTEXT Context,
 352   PBINARY_TREE_NODE Node)
 353 {
 354   if (ExpBinaryTreeIsInternalNode(Node))
 355                 {
 356       /* Traverse left subtree */
 357       ExpTraverseBinaryTreeInorder(Context, ExpBinaryTreeLeftChildNode(Node));
 358
 359                   /* Call the traversal routine */
 360                   if (!(*Context->Routine)(Context->Context,
 361                     ExpBinaryTreeNodeKey(Node),
 362                     ExpBinaryTreeNodeValue(Node)))
 363                     {
 364                       return FALSE;
 365                     }
 366
 367       /* Traverse right subtree */
 368       ExpTraverseBinaryTreeInorder(Context, ExpBinaryTreeRightChildNode(Node));
 369                 }
 370
 371   return TRUE;
 372 }
 373
 374
 375 /*
 376  * Traverse a binary tree using postorder traversal method.
 377  * Returns FALSE, if the traversal was terminated prematurely or
 378  * TRUE if the callback routine did not request that the traversal
 379  * be terminated prematurely.
 380  * The lock for the tree must be acquired when this routine is called.
 381  */
 382 BOOLEAN
 383 ExpTraverseBinaryTreePostorder(PTRAVERSE_CONTEXT Context,
 384   PBINARY_TREE_NODE Node)
 385 {
 386   if (ExpBinaryTreeIsInternalNode(Node))
 387                 {
 388       /* Traverse left subtree */
 389       ExpTraverseBinaryTreePostorder(Context, ExpBinaryTreeLeftChildNode(Node));
 390
 391       /* Traverse right subtree */
 392       ExpTraverseBinaryTreePostorder(Context, ExpBinaryTreeRightChildNode(Node));
 393
 394                   /* Call the traversal routine */
 395                   return (*Context->Routine)(Context->Context,
 396                     ExpBinaryTreeNodeKey(Node),
 397                     ExpBinaryTreeNodeValue(Node));
 398                 }
 399
 400   return TRUE;
 401 }
 402
 403
 404 /*
 405  * Default key compare function. Compares the integer values of the two keys.
 406  */
 407 LONG STDCALL
 408 ExpBinaryTreeDefaultCompare(PVOID  Key1,
 409   PVOID  Key2)
 410 {
 411   if (Key1 == Key2)
 412     return 0;
 413
 414   return (((LONG_PTR) Key1 < (LONG_PTR) Key2) ? -1 : 1);
 415 }
 416
 417
 418 /*
 419  * Initializes a binary tree.
 420  */
 421 BOOLEAN STDCALL
 422 ExInitializeBinaryTree(IN PBINARY_TREE  Tree,
 423   IN PKEY_COMPARATOR  Compare,
 424   IN BOOLEAN  UseNonPagedPool)
 425 {
 426   RtlZeroMemory(Tree, sizeof(BINARY_TREE));
 427
 428   Tree->Compare = (Compare == NULL)
 429     ? ExpBinaryTreeDefaultCompare : Compare;
 430
 431   Tree->UseNonPagedPool = UseNonPagedPool;
 432
 433   if (UseNonPagedPool)
 434     {
 435                   ExInitializeNPagedLookasideList(
 436                     &Tree->List.NonPaged,           /* Lookaside list */
 437                     NULL,                           /* Allocate routine */
 438                     NULL,                           /* Free routine */
 439                     0,                              /* Flags */
 440                     sizeof(BINARY_TREE_NODE),       /* Size of each entry */
 441                     TAG('E','X','B','T'),           /* Tag */
 442                     0);                             /* Depth */
 443
 444       KeInitializeSpinLock(&Tree->Lock.NonPaged);
 445                 }
 446                 else
 447                 {
 448                   ExInitializePagedLookasideList(
 449                     &Tree->List.Paged,              /* Lookaside list */
 450                     NULL,                           /* Allocate routine */
 451                     NULL,                           /* Free routine */
 452                     0,                              /* Flags */
 453                     sizeof(BINARY_TREE_NODE),       /* Size of each entry */
 454                     TAG('E','X','B','T'),           /* Tag */
 455                     0);                             /* Depth */
 456
 457       ExInitializeFastMutex(&Tree->Lock.Paged);
 458                 }
 459
 460   ExpBinaryTreeRootNode(Tree) = ExpCreateBinaryTreeNode(Tree, NULL, NULL);
 461
 462   if (ExpBinaryTreeRootNode(Tree) == NULL)
 463                 {
 464                   if (UseNonPagedPool)
 465                     {
 466           ExDeleteNPagedLookasideList(&Tree->List.NonPaged);
 467                           }
 468                         else
 469                                 {
 470           ExDeletePagedLookasideList(&Tree->List.Paged);
 471                                 }
 472       return FALSE;
 473                 }
 474   else
 475                 {
 476       return TRUE;
 477                 }
 478 }
 479
 480
 481 /*
 482  * Release resources used by a binary tree.
 483  */
 484 VOID STDCALL
 485 ExDeleteBinaryTree(IN PBINARY_TREE  Tree)
 486 {
 487   /* Remove all nodes */
 488   ExpDeleteBinaryTree(Tree, ExpBinaryTreeRootNode(Tree));
 489
 490   if (Tree->UseNonPagedPool)
 491     {
 492       ExDeleteNPagedLookasideList(&Tree->List.NonPaged);
 493           }
 494         else
 495                 {
 496       ExDeletePagedLookasideList(&Tree->List.Paged);
 497                 }
 498 }
 499
 500
 501 /*
 502  * Insert a value in a binary tree.
 503  */
 504 VOID STDCALL
 505 ExInsertBinaryTree(IN PBINARY_TREE  Tree,
 506   IN PVOID  Key,
 507   IN PVOID  Value)
 508 {
 509   PBINARY_TREE_NODE Node;
 510   KIRQL OldIrql;
 511
 512   /* FIXME: Use SEH for error reporting */
 513
 514   ExpLockBinaryTree(Tree, &OldIrql);
 515   Node = ExpBinaryTreeRootNode(Tree);
 516   do
 517     {
 518       Node = ExpSearchBinaryTree(Tree, Key, Node);
 519
 520                   if (ExpBinaryTreeIsExternalNode(Node))
 521                     {
 522           break;
 523                     }
 524                         else
 525                                 {
 526           Node = ExpBinaryTreeRightChildNode(Node);
 527                                 }
 528     } while (TRUE);
 529   ExpExpandExternalBinaryTreeNode(Tree, Node);
 530   ExpBinaryTreeNodeKey(Node)   = Key;
 531   ExpBinaryTreeNodeValue(Node) = Value;
 532   ExpUnlockBinaryTree(Tree, &OldIrql);
 533 }
 534
 535
 536 /*
 537  * Search for a value associated with a given key in a binary tree.
 538  */
 539 BOOLEAN STDCALL
 540 ExSearchBinaryTree(IN PBINARY_TREE  Tree,
 541   IN PVOID  Key,
 542   OUT PVOID  * Value)
 543 {
 544   PBINARY_TREE_NODE Node;
 545   KIRQL OldIrql;
 546
 547   ExpLockBinaryTree(Tree, &OldIrql);
 548   Node = ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeRootNode(Tree));
 549
 550   if (ExpBinaryTreeIsInternalNode(Node))
 551     {
 552             *Value = ExpBinaryTreeNodeValue(Node);
 553       ExpUnlockBinaryTree(Tree, &OldIrql);
 554             return TRUE;
 555           }
 556         else
 557                 {
 558       ExpUnlockBinaryTree(Tree, &OldIrql);
 559       return FALSE;
 560                 }
 561 }
 562
 563
 564 /*
 565  * Remove a value associated with a given key from a binary tree.
 566  */
 567 BOOLEAN STDCALL
 568 ExRemoveBinaryTree(IN PBINARY_TREE  Tree,
 569   IN PVOID  Key,
 570   IN PVOID  * Value)
 571 {
 572   PBINARY_TREE_NODE Node;
 573   KIRQL OldIrql;
 574
 575   ExpLockBinaryTree(Tree, &OldIrql);
 576
 577   Node = ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeRootNode(Tree));
 578
 579   if (ExpBinaryTreeIsExternalNode(Node))
 580                 {
 581       ExpUnlockBinaryTree(Tree, &OldIrql);
 582       return FALSE;
 583                 }
 584         else
 585                 {
 586       *Value = ExpBinaryTreeNodeValue(Node);
 587                   if (ExpBinaryTreeIsExternalNode(ExpBinaryTreeLeftChildNode(Node)))
 588                                 {
 589           Node = ExpBinaryTreeLeftChildNode(Node);
 590                                 }
 591       else if (ExpBinaryTreeIsExternalNode(ExpBinaryTreeRightChildNode(Node)))
 592                                 {
 593           Node = ExpBinaryTreeRightChildNode(Node);
 594                                 }
 595       else
 596         {
 597           // Node has internal children
 598           PBINARY_TREE_NODE SwapNode;
 599
 600           SwapNode = Node;
 601           Node = ExpBinaryTreeRightChildNode(SwapNode);
 602           do
 603             {
 604               Node = ExpBinaryTreeLeftChildNode(Node);
 605             } while (ExpBinaryTreeIsInternalNode(Node));
 606         }
 607
 608       ExpRemoveAboveExternalBinaryTreeNode(Tree, Node);
 609       ExpUnlockBinaryTree(Tree, &OldIrql);
 610       return TRUE;
 611                 }
 612 }
 613
 614
 615 /*
 616  * Traverse a binary tree using either preorder, inorder or postorder
 617  * traversal method.
 618  * Returns FALSE, if the traversal was terminated prematurely or
 619  * TRUE if the callback routine did not request that the traversal
 620  * be terminated prematurely.
 621  */
 622 BOOLEAN STDCALL
 623 ExTraverseBinaryTree(IN PBINARY_TREE  Tree,
 624   IN TRAVERSE_METHOD  Method,
 625   IN PTRAVERSE_ROUTINE  Routine,
 626   IN PVOID  Context)
 627 {
 628   TRAVERSE_CONTEXT tc;
 629   BOOLEAN Status;
 630   KIRQL OldIrql;
 631
 632   tc.Routine = Routine;
 633   tc.Context = Context;
 634
 635   ExpLockBinaryTree(Tree, &OldIrql);
 636
 637   switch (Method)
 638     {
 639       case TraverseMethodPreorder:
 640         Status = ExpTraverseBinaryTreePreorder(&tc, ExpBinaryTreeRootNode(Tree));
 641         break;
 642
 643       case TraverseMethodInorder:
 644         Status = ExpTraverseBinaryTreeInorder(&tc, ExpBinaryTreeRootNode(Tree));
 645         break;
 646
 647       case TraverseMethodPostorder:
 648         Status = ExpTraverseBinaryTreePostorder(&tc, ExpBinaryTreeRootNode(Tree));
 649         break;
 650
 651       default:
 652         Status = FALSE;
 653         break;
 654     }
 655
 656   ExpUnlockBinaryTree(Tree, &OldIrql);
 657
 658   return Status;
 659 }
 660
 661 /* EOF */