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