ntoskrnl/ex/stree.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:            stree.c
  22  * PURPOSE:         Splay tree support
  23  * PROGRAMMER:      Casper S. Hornstrup (chorns@users.sourceforge.net)
  24  * NOTES:           Based on a splay tree implementation by
  25  *                  Daniel Stenberg <Daniel.Stenberg@sth.frontec.se>
  26  *                  http://www.contactor.se/~dast/stuff/dsplay-1.2.tar.gz
  27  * UPDATE HISTORY:
  28  *      15-03-2002  CSH  Created
  29  */
  30 #include <ddk/ntddk.h>
  31 #include <internal/ex.h>
  32
  33 #define NDEBUG
  34 #include <internal/debug.h>
  35
  36 /* DATA **********************************************************************/
  37
  38 #define WEIGHT 1
  39 #undef UNIQUE_KEYS
  40
  41 typedef struct _SPLAY_TREE_NODE
  42 {
  43   /* Children on this branch that has smaller keys than this node */
  44   struct _SPLAY_TREE_NODE  * SmallerChild;
  45
  46   /* Children on this branch that has larger keys than this node */
  47   struct _SPLAY_TREE_NODE  * LargerChild;
  48
  49   /* Points to a node with identical key */
  50   struct _SPLAY_TREE_NODE  * Same;
  51
  52   /* Key of this node */
  53   PVOID  Key;
  54
  55   /* Value of this node */
  56   PVOID  Value;
  57
  58   /* The number of nodes rooted here */
  59   LONG  Weight;
  60 } SPLAY_TREE_NODE, *PSPLAY_TREE_NODE;
  61
  62 typedef struct _TRAVERSE_CONTEXT {
  63   PTRAVERSE_ROUTINE Routine;
  64   PVOID Context;
  65 } TRAVERSE_CONTEXT, *PTRAVERSE_CONTEXT;
  66
  67 #define SPLAY_INDEX 0
  68 #define SEARCH_INDEX 1
  69 #define INSERT_INDEX 2
  70 #define REMOVE_INDEX 3
  71
  72 typedef PSPLAY_TREE_NODE (*PSPLAY_TREE_SPLAY)(PSPLAY_TREE Tree,
  73   PVOID Key,
  74   PSPLAY_TREE_NODE Node);
  75
  76 typedef BOOLEAN (*PSPLAY_TREE_SEARCH)(PSPLAY_TREE Tree,
  77   PVOID Key,
  78   PSPLAY_TREE_NODE Node,
  79   PSPLAY_TREE_NODE * ReturnNode);
  80
  81 typedef PSPLAY_TREE_NODE (*PSPLAY_TREE_INSERT)(PSPLAY_TREE Tree,
  82   PVOID Key,
  83   PSPLAY_TREE_NODE Node,
  84   PSPLAY_TREE_NODE New);
  85
  86 typedef PSPLAY_TREE_NODE (*PSPLAY_TREE_REMOVE)(PSPLAY_TREE Tree,
  87   PVOID Key,
  88   PSPLAY_TREE_NODE Node,
  89   PSPLAY_TREE_NODE * RemovedNode);
  90
  91 /* FUNCTIONS ****************************************************************/
  92
  93 #define ExpSplayTreeRootNode(Tree)(((PSPLAY_TREE) (Tree))->RootNode)
  94 #define ExpSplayTreeNodeKey(Node)((Node)->Key)
  95 #define ExpSplayTreeNodeValue(Node)((Node)->Value)
  96 #define ExpSplayTreeSmallerChildNode(Node)((Node)->SmallerChild)
  97 #define ExpSplayTreeLargerChildNode(Node)((Node)->LargerChild)
  98 #define ExpSplayTreeNodeEqual(Equality)((Equality) == 0)
  99 #define ExpSplayTreeNodeLess(Equality)((Equality) < 0)
 100 #define ExpSplayTreeNodeMore(Equality)((Equality) > 0)
 101 #define ExpSplayTreeNodeSame(Node)((Node)->Same)
 102 #define ExpSplayTreeNodeWeight(Node)((Node)->Weight)
 103 #define ExpSplayTreeNodeGetWeight(Node)(((Node) == NULL) ? 0 : ((Node)->Weight))
 104 #define ExpSplayTreeNodeSetWeight(Node, _Weight)((Node)->Weight = (_Weight))
 105
 106 #define KEY_NOTUSED (PVOID)-1
 107
 108
 109 /*
 110  * Lock the splay tree
 111  */
 112 inline VOID
 113 ExpLockSplayTree(PSPLAY_TREE Tree,
 114   PKIRQL OldIrql)
 115 {
 116         if (Tree->UseNonPagedPool)
 117           {
 118       KeAcquireSpinLock(&Tree->Lock.NonPaged, OldIrql);
 119           }
 120         else
 121                 {
 122       ExAcquireFastMutex(&Tree->Lock.Paged);
 123                 }
 124 }
 125
 126
 127 /*
 128  * Unlock the splay tree
 129  */
 130 inline VOID
 131 ExpUnlockSplayTree(PSPLAY_TREE Tree,
 132   PKIRQL OldIrql)
 133 {
 134         if (Tree->UseNonPagedPool)
 135           {
 136       KeReleaseSpinLock(&Tree->Lock.NonPaged, *OldIrql);
 137           }
 138         else
 139                 {
 140       ExReleaseFastMutex(&Tree->Lock.Paged);
 141                 }
 142 }
 143
 144
 145 /*
 146  * Allocate resources for a new node and initialize it.
 147  */
 148 inline PSPLAY_TREE_NODE
 149 ExpCreateSplayTreeNode(PSPLAY_TREE Tree,
 150   PVOID Value)
 151 {
 152   PSPLAY_TREE_NODE Node;
 153
 154         if (Tree->UseNonPagedPool)
 155           {
 156       Node = (PSPLAY_TREE_NODE) ExAllocateFromNPagedLookasideList(&Tree->List.NonPaged);
 157           }
 158         else
 159                 {
 160       Node = (PSPLAY_TREE_NODE) ExAllocateFromPagedLookasideList(&Tree->List.Paged);
 161                 }
 162
 163   if (Node)
 164                 {
 165       ExpSplayTreeSmallerChildNode(Node) = NULL;
 166       ExpSplayTreeLargerChildNode(Node)  = NULL;
 167       ExpSplayTreeNodeValue(Node)        = Value;
 168                 }
 169
 170   return Node;
 171 }
 172
 173 /*
 174  * Release resources for the node.
 175  */
 176 inline VOID
 177 ExpDestroySplayTreeNode(PSPLAY_TREE Tree,
 178   PSPLAY_TREE_NODE Node)
 179 {
 180         if (Tree->UseNonPagedPool)
 181           {
 182       ExFreeToNPagedLookasideList(&Tree->List.NonPaged, Node);
 183           }
 184         else
 185                 {
 186       ExFreeToPagedLookasideList(&Tree->List.Paged, Node);
 187                 }
 188 }
 189
 190
 191 /*
 192  * Splay using the key 'Key' (which may or may not be in the tree). The starting
 193  * root is Node.
 194  * The lock for the tree must be acquired when this routine is called.
 195  * This routine does not maintain weight information.
 196  */
 197 PSPLAY_TREE_NODE
 198 ExpSplayTreeNoWeight(PSPLAY_TREE Tree,
 199   PVOID Key,
 200   PSPLAY_TREE_NODE Node)
 201 {
 202   PSPLAY_TREE_NODE l;
 203   PSPLAY_TREE_NODE r;
 204   PSPLAY_TREE_NODE y;
 205   LONG ChildEquality;
 206   SPLAY_TREE_NODE N;
 207   LONG Equality;
 208
 209   if (Node == NULL)
 210     return Node;
 211
 212   ExpSplayTreeSmallerChildNode(&N) = NULL;
 213   ExpSplayTreeLargerChildNode(&N)  = NULL;
 214   l = &N;
 215   r = &N;
 216
 217   for (;;)
 218     {
 219       Equality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node));
 220
 221       if (ExpSplayTreeNodeLess(Equality))
 222         {
 223           if (ExpSplayTreeSmallerChildNode(Node) == NULL)
 224                   break;
 225
 226           ChildEquality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(ExpSplayTreeSmallerChildNode(Node)));
 227           if (ExpSplayTreeNodeLess(ChildEquality))
 228             {
 229               y = ExpSplayTreeSmallerChildNode(Node);     /* Rotate smaller */
 230               ExpSplayTreeSmallerChildNode(Node) = ExpSplayTreeLargerChildNode(y);
 231               ExpSplayTreeLargerChildNode(y) = Node;
 232
 233                                 Node = y;
 234                                 if (ExpSplayTreeSmallerChildNode(Node) == NULL)
 235                                   break;
 236                         }
 237
 238                       ExpSplayTreeSmallerChildNode(r) = Node;           /* Link smaller */
 239                       r = Node;
 240                       Node = ExpSplayTreeSmallerChildNode(Node);
 241                     }
 242                   else if (ExpSplayTreeNodeMore(Equality))
 243                     {
 244                       if (ExpSplayTreeLargerChildNode(Node) == NULL)
 245                               break;
 246
 247                       ChildEquality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(ExpSplayTreeLargerChildNode(Node)));
 248                       if (ExpSplayTreeNodeMore(ChildEquality))
 249                         {
 250                                 y = ExpSplayTreeLargerChildNode(Node);        /* Rotate larger */
 251                                 ExpSplayTreeLargerChildNode(Node) = ExpSplayTreeSmallerChildNode(y);
 252                                 ExpSplayTreeSmallerChildNode(y) = Node;
 253
 254                                 Node = y;
 255                                 if (ExpSplayTreeLargerChildNode(Node) == NULL)
 256                                   break;
 257                         }
 258
 259                       ExpSplayTreeLargerChildNode(l) = Node;            /* Link larger */
 260                       l = Node;
 261                       Node = ExpSplayTreeLargerChildNode(Node);
 262                     }
 263                   else
 264                     {
 265                       break;
 266                     }
 267     }
 268
 269   ExpSplayTreeLargerChildNode(l)  = NULL;
 270   ExpSplayTreeSmallerChildNode(r) = NULL;
 271
 272   ExpSplayTreeLargerChildNode(l)     = ExpSplayTreeSmallerChildNode(Node);  /* Assemble */
 273   ExpSplayTreeSmallerChildNode(r)    = ExpSplayTreeLargerChildNode(Node);
 274   ExpSplayTreeSmallerChildNode(Node) = ExpSplayTreeLargerChildNode(&N);
 275   ExpSplayTreeLargerChildNode(Node)  = ExpSplayTreeSmallerChildNode(&N);
 276
 277   return Node;
 278 }
 279
 280
 281 /*
 282  * Splay using the key 'Key' (which may or may not be in the tree). The starting
 283  * root is Node.
 284  * The lock for the tree must be acquired when this routine is called.
 285  * This routine maintains weight information.
 286  */
 287 PSPLAY_TREE_NODE
 288 ExpSplayTreeWeight(PSPLAY_TREE Tree,
 289   PVOID Key,
 290   PSPLAY_TREE_NODE Node)
 291 {
 292   PSPLAY_TREE_NODE l;
 293   PSPLAY_TREE_NODE r;
 294   PSPLAY_TREE_NODE y;
 295   LONG ChildEquality;
 296   SPLAY_TREE_NODE N;
 297   LONG Equality;
 298 #ifdef WEIGHT
 299   LONG RootWeight;
 300   LONG Weight1;
 301   LONG Weight2;
 302 #endif
 303
 304   if (Node == NULL)
 305     return Node;
 306
 307   ExpSplayTreeSmallerChildNode(&N) = NULL;
 308   ExpSplayTreeLargerChildNode(&N)  = NULL;
 309   l = &N;
 310   r = &N;
 311
 312 #ifdef WEIGHT
 313   RootWeight = ExpSplayTreeNodeGetWeight(Node);
 314   Weight1 = 0;
 315   Weight2 = 0;
 316 #endif
 317
 318   for (;;)
 319     {
 320       Equality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node));
 321
 322       if (ExpSplayTreeNodeLess(Equality))
 323         {
 324           if (ExpSplayTreeSmallerChildNode(Node) == NULL)
 325                   break;
 326
 327           ChildEquality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(ExpSplayTreeSmallerChildNode(Node)));
 328           if (ExpSplayTreeNodeLess(ChildEquality))
 329             {
 330               y = ExpSplayTreeSmallerChildNode(Node);     /* Rotate smaller */
 331               ExpSplayTreeSmallerChildNode(Node) = ExpSplayTreeLargerChildNode(y);
 332               ExpSplayTreeLargerChildNode(y) = Node;
 333
 334 #ifdef WEIGHT
 335               ExpSplayTreeNodeSetWeight(Node, ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(Node))
 336                 + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(Node)) + 1);
 337 #endif
 338
 339                                 Node = y;
 340                                 if (ExpSplayTreeSmallerChildNode(Node) == NULL)
 341                                   break;
 342                         }
 343
 344                       ExpSplayTreeSmallerChildNode(r) = Node;           /* Link smaller */
 345                       r = Node;
 346                       Node = ExpSplayTreeSmallerChildNode(Node);
 347
 348 #ifdef WEIGHT
 349                       Weight2 += 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(r));
 350 #endif
 351                     }
 352                   else if (ExpSplayTreeNodeMore(Equality))
 353                     {
 354                       if (ExpSplayTreeLargerChildNode(Node) == NULL)
 355                               break;
 356
 357                       ChildEquality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(ExpSplayTreeLargerChildNode(Node)));
 358                       if (ExpSplayTreeNodeMore(ChildEquality))
 359                         {
 360                                 y = ExpSplayTreeLargerChildNode(Node);        /* Rotate larger */
 361                                 ExpSplayTreeLargerChildNode(Node) = ExpSplayTreeSmallerChildNode(y);
 362                                 ExpSplayTreeSmallerChildNode(y) = Node;
 363
 364 #ifdef WEIGHT
 365                                 ExpSplayTreeNodeSetWeight(Node, ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(Node))
 366                             + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(Node)) + 1);
 367 #endif
 368
 369                                 Node = y;
 370                                 if (ExpSplayTreeLargerChildNode(Node) == NULL)
 371                                   break;
 372                         }
 373
 374                       ExpSplayTreeLargerChildNode(l) = Node;            /* Link larger */
 375                       l = Node;
 376                       Node = ExpSplayTreeLargerChildNode(Node);
 377
 378 #ifdef WEIGHT
 379                       Weight1 += 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(l));
 380 #endif
 381
 382                     }
 383                   else
 384                     {
 385                       break;
 386                     }
 387     }
 388
 389 #ifdef WEIGHT
 390   Weight1 += ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(Node)); /* Now Weight1 and Weight2 are the weights of */
 391   Weight2 += ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(Node));  /* The 'smaller' and 'larger' trees we just built. */
 392   ExpSplayTreeNodeSetWeight(Node, Weight1 + Weight2 + 1);
 393 #endif
 394
 395   ExpSplayTreeLargerChildNode(l)  = NULL;
 396   ExpSplayTreeSmallerChildNode(r) = NULL;
 397
 398 #ifdef WEIGHT
 399   /* The following two loops correct the weight fields of the right path from
 400    * the left child of the root and the right path from the left child of the
 401    * root.
 402    */
 403   for (y = ExpSplayTreeLargerChildNode(&N); y != NULL; y = ExpSplayTreeLargerChildNode(y)) {
 404     ExpSplayTreeNodeSetWeight(y, Weight1);
 405     Weight1 -= 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(y));
 406   }
 407   for (y = ExpSplayTreeSmallerChildNode(&N); y != NULL; y = ExpSplayTreeSmallerChildNode(y)) {
 408     ExpSplayTreeNodeSetWeight(y, Weight2);
 409     Weight2 -= 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(y));
 410   }
 411 #endif
 412
 413   ExpSplayTreeLargerChildNode(l)     = ExpSplayTreeSmallerChildNode(Node);  /* Assemble */
 414   ExpSplayTreeSmallerChildNode(r)    = ExpSplayTreeLargerChildNode(Node);
 415   ExpSplayTreeSmallerChildNode(Node) = ExpSplayTreeLargerChildNode(&N);
 416   ExpSplayTreeLargerChildNode(Node)  = ExpSplayTreeSmallerChildNode(&N);
 417
 418   return Node;
 419 }
 420
 421
 422 inline PSPLAY_TREE_NODE
 423 ExpSplayTree(PSPLAY_TREE Tree,
 424   PVOID Key,
 425   PSPLAY_TREE_NODE Node)
 426 {
 427   return (*((PSPLAY_TREE_SPLAY)Tree->Reserved[SPLAY_INDEX]))(Tree, Key, Node);
 428 }
 429
 430
 431 /*
 432  * The lock for the tree must be acquired when this routine is called.
 433  * This routine does not maintain weight information.
 434  */
 435 BOOLEAN
 436 ExpSearchSplayTreeNoWeight(PSPLAY_TREE Tree,
 437   PVOID Key,
 438   PSPLAY_TREE_NODE Node,
 439   PSPLAY_TREE_NODE * ReturnNode)
 440 {
 441   LONG Equality;
 442
 443   if (Node == NULL)
 444     return FALSE;
 445
 446   Node = ExpSplayTree(Tree, Key, Node);
 447
 448   Equality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node));
 449   if (ExpSplayTreeNodeEqual(Equality))
 450     {
 451       /* Found the key */
 452
 453       *ReturnNode = Node;
 454                   return TRUE;
 455           }
 456         else
 457           {
 458             *ReturnNode = NULL;                 /* No match */
 459             return FALSE;                       /* It wasn't there */
 460           }
 461 }
 462
 463
 464 /*
 465  * The lock for the tree must be acquired when this routine is called.
 466  * This routine maintains weight information.
 467  */
 468 BOOLEAN
 469 ExpSearchSplayTreeWeight(PSPLAY_TREE Tree,
 470   PVOID Key,
 471   PSPLAY_TREE_NODE Node,
 472   PSPLAY_TREE_NODE * ReturnNode)
 473 {
 474   PSPLAY_TREE_NODE x = NULL;
 475   LONG Equality;
 476 #ifdef WEIGHT
 477   LONG tweight;
 478 #endif
 479
 480   if (Node == NULL)
 481     return FALSE;
 482
 483 #ifdef WEIGHT
 484   tweight = ExpSplayTreeNodeGetWeight(Node);
 485 #endif
 486
 487   Node = ExpSplayTree(Tree, Key, Node);
 488
 489   Equality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node));
 490   if (ExpSplayTreeNodeEqual(Equality))
 491     {
 492       /* Found the key */
 493
 494 #ifdef WEIGHT
 495                   if (x != NULL)
 496                     {
 497                       ExpSplayTreeNodeSetWeight(x, tweight - 1);
 498                     }
 499 #endif
 500
 501       *ReturnNode = Node;
 502                   return TRUE;
 503           }
 504         else
 505           {
 506             *ReturnNode = NULL;                 /* No match */
 507             return FALSE;                       /* It wasn't there */
 508           }
 509 }
 510
 511
 512 inline BOOLEAN
 513 ExpSearchSplayTree(PSPLAY_TREE Tree,
 514   PVOID Key,
 515   PSPLAY_TREE_NODE Node,
 516   PSPLAY_TREE_NODE * ReturnNode)
 517 {
 518   return (*((PSPLAY_TREE_SEARCH)Tree->Reserved[SEARCH_INDEX]))(Tree, Key, Node, ReturnNode);
 519 }
 520
 521
 522 /*
 523  * The lock for the tree must be acquired when this routine is called.
 524  * This routine does not maintain weight information.
 525  */
 526 PSPLAY_TREE_NODE
 527 ExpInsertSplayTreeNoWeight(PSPLAY_TREE Tree,
 528   PVOID Key,
 529   PSPLAY_TREE_NODE Node,
 530   PSPLAY_TREE_NODE New)
 531 {
 532   if (New == NULL)
 533     return Node;
 534
 535   if (Node != NULL)
 536     {
 537       LONG Equality;
 538
 539       Node = ExpSplayTree(Tree, Key, Node);
 540
 541       Equality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node));
 542       if (ExpSplayTreeNodeEqual(Equality))
 543         {
 544
 545 #ifdef UNIQUE_KEYS
 546
 547       /* This is how to prevent the same node key getting added twice */
 548       return NULL;
 549
 550 #else
 551
 552       /* It already exists one of this size */
 553
 554       ExpSplayTreeNodeSame(New) = Node;
 555       ExpSplayTreeNodeKey(New) = Key;
 556       ExpSplayTreeSmallerChildNode(New) = ExpSplayTreeSmallerChildNode(Node);
 557       ExpSplayTreeLargerChildNode(New) = ExpSplayTreeLargerChildNode(Node);
 558
 559       ExpSplayTreeSmallerChildNode(Node) = New;
 560       ExpSplayTreeNodeKey(Node) = KEY_NOTUSED;
 561
 562       /* New root node */
 563       return New;
 564
 565 #endif
 566
 567     }
 568   }
 569
 570   if (Node == NULL)
 571     {
 572       ExpSplayTreeSmallerChildNode(New) = NULL;
 573       ExpSplayTreeLargerChildNode(New)  = NULL;
 574     }
 575   else if (ExpSplayTreeNodeLess((*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node))))
 576     {
 577       ExpSplayTreeSmallerChildNode(New)  = ExpSplayTreeSmallerChildNode(Node);
 578       ExpSplayTreeLargerChildNode(New)   = Node;
 579       ExpSplayTreeSmallerChildNode(Node) = NULL;
 580     }
 581   else
 582     {
 583       ExpSplayTreeLargerChildNode(New)  = ExpSplayTreeLargerChildNode(Node);
 584       ExpSplayTreeSmallerChildNode(New) = Node;
 585       ExpSplayTreeLargerChildNode(Node) = NULL;
 586     }
 587
 588   ExpSplayTreeNodeKey(New) = Key;
 589
 590 #ifndef UNIQUE_KEYS
 591   /* No identical nodes (yet) */
 592   ExpSplayTreeNodeSame(New) = NULL;
 593 #endif
 594
 595   return New;
 596 }
 597
 598
 599 /*
 600  * The lock for the tree must be acquired when this routine is called.
 601  * This routine maintains weight information.
 602  */
 603 PSPLAY_TREE_NODE
 604 ExpInsertSplayTreeWeight(PSPLAY_TREE Tree,
 605   PVOID Key,
 606   PSPLAY_TREE_NODE Node,
 607   PSPLAY_TREE_NODE New)
 608 {
 609   if (New == NULL)
 610     return Node;
 611
 612   if (Node != NULL)
 613     {
 614       LONG Equality;
 615
 616       Node = ExpSplayTree(Tree, Key, Node);
 617
 618       Equality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node));
 619       if (ExpSplayTreeNodeEqual(Equality))
 620         {
 621
 622 #ifdef UNIQUE_KEYS
 623
 624       /* This is how to prevent the same node key getting added twice */
 625       return NULL;
 626
 627 #else
 628
 629       /* It already exists one of this size */
 630
 631       ExpSplayTreeNodeSame(New) = Node;
 632       ExpSplayTreeNodeKey(New) = Key;
 633       ExpSplayTreeSmallerChildNode(New) = ExpSplayTreeSmallerChildNode(Node);
 634       ExpSplayTreeLargerChildNode(New) = ExpSplayTreeLargerChildNode(Node);
 635
 636 #ifdef WEIGHT
 637       ExpSplayTreeNodeSetWeight(New, ExpSplayTreeNodeGetWeight(Node));
 638 #endif
 639
 640       ExpSplayTreeSmallerChildNode(Node) = New;
 641       ExpSplayTreeNodeKey(Node) = KEY_NOTUSED;
 642
 643       /* New root node */
 644       return New;
 645
 646 #endif
 647
 648     }
 649   }
 650
 651   if (Node == NULL)
 652     {
 653       ExpSplayTreeSmallerChildNode(New) = NULL;
 654       ExpSplayTreeLargerChildNode(New)  = NULL;
 655     }
 656   else if (ExpSplayTreeNodeLess((*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node))))
 657     {
 658       ExpSplayTreeSmallerChildNode(New)  = ExpSplayTreeSmallerChildNode(Node);
 659       ExpSplayTreeLargerChildNode(New)   = Node;
 660       ExpSplayTreeSmallerChildNode(Node) = NULL;
 661
 662 #ifdef WEIGHT
 663       ExpSplayTreeNodeSetWeight(Node, 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(Node)));
 664 #endif
 665
 666     }
 667   else
 668     {
 669       ExpSplayTreeLargerChildNode(New)  = ExpSplayTreeLargerChildNode(Node);
 670       ExpSplayTreeSmallerChildNode(New) = Node;
 671       ExpSplayTreeLargerChildNode(Node) = NULL;
 672
 673 #ifdef WEIGHT
 674       ExpSplayTreeNodeSetWeight(Node, 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(Node)));
 675 #endif
 676
 677     }
 678
 679   ExpSplayTreeNodeKey(New) = Key;
 680
 681 #ifdef WEIGHT
 682   ExpSplayTreeNodeSetWeight(New, 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(New))
 683     + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(New)));
 684 #endif
 685
 686 #ifndef UNIQUE_KEYS
 687   /* No identical nodes (yet) */
 688   ExpSplayTreeNodeSame(New) = NULL;
 689 #endif
 690
 691   return New;
 692 }
 693
 694
 695 inline PSPLAY_TREE_NODE
 696 ExpInsertSplayTree(PSPLAY_TREE Tree,
 697   PVOID Key,
 698   PSPLAY_TREE_NODE Node,
 699   PSPLAY_TREE_NODE New)
 700 {
 701   return (*((PSPLAY_TREE_INSERT)Tree->Reserved[INSERT_INDEX]))(Tree, Key, Node, New);
 702 }
 703
 704
 705 /*
 706  * Deletes the node with key 'Key' from the tree if it's there.
 707  * Return a pointer to the resulting tree.
 708  * The lock for the tree must be acquired when this routine is called.
 709  * This routine does not maintain weight information.
 710  */
 711 PSPLAY_TREE_NODE
 712 ExpRemoveSplayTreeNoWeight(PSPLAY_TREE Tree,
 713   PVOID Key,
 714   PSPLAY_TREE_NODE Node,
 715   PSPLAY_TREE_NODE * RemovedNode)
 716 {
 717   PSPLAY_TREE_NODE x;
 718   LONG Equality;
 719
 720   if (Node == NULL)
 721     return NULL;
 722
 723   Node = ExpSplayTree(Tree, Key, Node);
 724
 725   Equality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node));
 726   if (ExpSplayTreeNodeEqual(Equality))
 727     {
 728       /* Found the key */
 729
 730 #ifndef UNIQUE_KEYS
 731             /* FIRST! Check if there is a list with identical sizes */
 732       x = ExpSplayTreeNodeSame(Node);
 733             if (x)
 734               {
 735                 /* There is several, pick one from the list */
 736
 737                 /* 'x' is the new root node */
 738
 739                 ExpSplayTreeNodeKey(x)          = ExpSplayTreeNodeKey(Node);
 740                 ExpSplayTreeLargerChildNode(x)  = ExpSplayTreeLargerChildNode(Node);
 741                 ExpSplayTreeSmallerChildNode(x) = ExpSplayTreeSmallerChildNode(Node);
 742
 743           *RemovedNode = Node;
 744           return x;
 745         }
 746 #endif
 747
 748                   if (ExpSplayTreeSmallerChildNode(Node) == NULL)
 749                     {
 750                       x = ExpSplayTreeLargerChildNode(Node);
 751                     }
 752                   else
 753                     {
 754                       x = ExpSplayTree(Tree, Key, ExpSplayTreeSmallerChildNode(Node));
 755                       ExpSplayTreeLargerChildNode(x) = ExpSplayTreeLargerChildNode(Node);
 756                     }
 757                   *RemovedNode = Node;
 758
 759                   return x;
 760           }
 761         else
 762           {
 763             *RemovedNode = NULL;                /* No match */
 764             return Node;                        /* It wasn't there */
 765           }
 766 }
 767
 768
 769 /*
 770  * Deletes the node with key 'Key' from the tree if it's there.
 771  * Return a pointer to the resulting tree.
 772  * The lock for the tree must be acquired when this routine is called.
 773  * This routine maintains weight information.
 774  */
 775 PSPLAY_TREE_NODE
 776 ExpRemoveSplayTreeWeight(PSPLAY_TREE Tree,
 777   PVOID Key,
 778   PSPLAY_TREE_NODE Node,
 779   PSPLAY_TREE_NODE * RemovedNode)
 780 {
 781   PSPLAY_TREE_NODE x;
 782   LONG Equality;
 783
 784 #ifdef WEIGHT
 785   LONG tweight;
 786 #endif
 787
 788   if (Node == NULL)
 789     return NULL;
 790
 791 #ifdef WEIGHT
 792   tweight = ExpSplayTreeNodeGetWeight(Node);
 793 #endif
 794
 795   Node = ExpSplayTree(Tree, Key, Node);
 796
 797   Equality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node));
 798   if (ExpSplayTreeNodeEqual(Equality))
 799     {
 800       /* Found the key */
 801
 802 #ifndef UNIQUE_KEYS
 803             /* FIRST! Check if there is a list with identical sizes */
 804       x = ExpSplayTreeNodeSame(Node);
 805             if (x)
 806               {
 807                 /* There is several, pick one from the list */
 808
 809                 /* 'x' is the new root node */
 810
 811                 ExpSplayTreeNodeKey(x)          = ExpSplayTreeNodeKey(Node);
 812                 ExpSplayTreeLargerChildNode(x)  = ExpSplayTreeLargerChildNode(Node);
 813                 ExpSplayTreeSmallerChildNode(x) = ExpSplayTreeSmallerChildNode(Node);
 814
 815 #ifdef WEIGHT
 816           ExpSplayTreeNodeSetWeight(x, ExpSplayTreeNodeGetWeight(Node));
 817 #endif
 818
 819           *RemovedNode = Node;
 820           return x;
 821         }
 822 #endif
 823
 824                   if (ExpSplayTreeSmallerChildNode(Node) == NULL)
 825                     {
 826                       x = ExpSplayTreeLargerChildNode(Node);
 827                     }
 828                   else
 829                     {
 830                       x = ExpSplayTree(Tree, Key, ExpSplayTreeSmallerChildNode(Node));
 831                       ExpSplayTreeLargerChildNode(x) = ExpSplayTreeLargerChildNode(Node);
 832                     }
 833                   *RemovedNode = Node;
 834
 835 #ifdef WEIGHT
 836                   if (x != NULL)
 837                     {
 838                       ExpSplayTreeNodeSetWeight(x, tweight - 1);
 839                     }
 840 #endif
 841
 842                   return x;
 843           }
 844         else
 845           {
 846             *RemovedNode = NULL;                /* No match */
 847             return Node;                        /* It wasn't there */
 848           }
 849 }
 850
 851
 852 inline PSPLAY_TREE_NODE
 853 ExpRemoveSplayTree(PSPLAY_TREE Tree,
 854   PVOID Key,
 855   PSPLAY_TREE_NODE Node,
 856   PSPLAY_TREE_NODE * RemovedNode)
 857 {
 858   return (*((PSPLAY_TREE_REMOVE)Tree->Reserved[REMOVE_INDEX]))(Tree, Key, Node, RemovedNode);
 859 }
 860
 861
 862 /*
 863  * The lock for the tree must be acquired when this routine is called.
 864  */
 865 ULONG
 866 ExpPrintSplayTree(PSPLAY_TREE Tree,
 867   PSPLAY_TREE_NODE Node,
 868   ULONG Distance)
 869 {
 870   PSPLAY_TREE_NODE n;
 871   ULONG d = 0;
 872   ULONG i;
 873
 874   if (Node == NULL)
 875     return 0;
 876
 877   Distance += ExpPrintSplayTree(Tree, ExpSplayTreeLargerChildNode(Node), Distance + 1);
 878
 879   for (i = 0; i < Distance; i++)
 880     {
 881       DbgPrint("  ");
 882     }
 883
 884   if (Tree->Weighted)
 885     {
 886       DbgPrint("%d(%d)[%d]", ExpSplayTreeNodeKey(Node), ExpSplayTreeNodeGetWeight(Node), i);
 887     }
 888   else
 889    {
 890      DbgPrint("%d[%d]", ExpSplayTreeNodeKey(Node), i);
 891    }
 892
 893   for (n = ExpSplayTreeNodeSame(Node); n; n = ExpSplayTreeNodeSame(n))
 894     {
 895       d += i;
 896
 897       DbgPrint(" [+]");
 898     }
 899
 900   d += i;
 901
 902   d += ExpPrintSplayTree(Tree, ExpSplayTreeSmallerChildNode(Node), Distance + 1);
 903
 904   return d;
 905 }
 906
 907
 908 #define MAX_DIFF 4
 909
 910 #ifdef WEIGHT
 911
 912 /*
 913  * The lock for the tree must be acquired when this routine is called.
 914  * Returns the new root of the tree.
 915  * Use of this routine could improve performance, or it might not.
 916  * FIXME: Do some performance tests
 917  */
 918 PSPLAY_TREE_NODE
 919 ExpSplayTreeMaxTreeWeight(PSPLAY_TREE Tree,
 920   PSPLAY_TREE_NODE Node)
 921 {
 922   PSPLAY_TREE_NODE First = Node;
 923   LONG Diff;
 924
 925   do
 926     {
 927       Diff = ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(Node))
 928         - ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(Node));
 929
 930       if (Diff >= MAX_DIFF)
 931         {
 932           Node = ExpSplayTreeSmallerChildNode(Node);
 933         }
 934       else if (Diff <= -MAX_DIFF)
 935         {
 936           Node = ExpSplayTreeLargerChildNode(Node);
 937         }
 938       else
 939         break;
 940     } while (abs(Diff) >= MAX_DIFF);
 941
 942   if (Node != First)
 943     return ExpSplayTree(Tree, ExpSplayTreeNodeKey(Node), First);
 944   else
 945     return First;
 946 }
 947
 948 #endif
 949
 950
 951 /*
 952  * Traverse a splay tree using preorder traversal method.
 953  * Returns FALSE, if the traversal was terminated prematurely or
 954  * TRUE if the callback routine did not request that the traversal
 955  * be terminated prematurely.
 956  * The lock for the tree must be acquired when this routine is called.
 957  */
 958 BOOLEAN
 959 ExpTraverseSplayTreePreorder(PTRAVERSE_CONTEXT Context,
 960   PSPLAY_TREE_NODE Node)
 961 {
 962   PSPLAY_TREE_NODE n;
 963
 964   if (Node == NULL)
 965     return TRUE;
 966
 967   /* Call the traversal routine */
 968   if (!(*Context->Routine)(Context->Context,
 969     ExpSplayTreeNodeKey(Node),
 970     ExpSplayTreeNodeValue(Node)))
 971     {
 972       return FALSE;
 973     }
 974
 975         for (n = ExpSplayTreeNodeSame(Node); n; n = ExpSplayTreeNodeSame(n))
 976                 {
 977                   /* Call the traversal routine */
 978                   if (!(*Context->Routine)(Context->Context,
 979                     ExpSplayTreeNodeKey(n),
 980                     ExpSplayTreeNodeValue(n)))
 981                     {
 982                       return FALSE;
 983                     }
 984                 }
 985
 986   /* Traverse 'smaller' subtree */
 987   ExpTraverseSplayTreePreorder(Context, ExpSplayTreeSmallerChildNode(Node));
 988
 989   /* Traverse 'larger' subtree */
 990   ExpTraverseSplayTreePreorder(Context, ExpSplayTreeLargerChildNode(Node));
 991
 992   return TRUE;
 993 }
 994
 995
 996 /*
 997  * Traverse a splay tree using inorder traversal method.
 998  * Returns FALSE, if the traversal was terminated prematurely or
 999  * TRUE if the callback routine did not request that the traversal
1000  * be terminated prematurely.
1001  * The lock for the tree must be acquired when this routine is called.
1002  */
1003 BOOLEAN
1004 ExpTraverseSplayTreeInorder(PTRAVERSE_CONTEXT Context,
1005   PSPLAY_TREE_NODE Node)
1006 {
1007   PSPLAY_TREE_NODE n;
1008
1009   if (Node == NULL)
1010     return TRUE;
1011
1012   /* Traverse 'smaller' subtree */
1013   ExpTraverseSplayTreeInorder(Context, ExpSplayTreeSmallerChildNode(Node));
1014
1015   /* Call the traversal routine */
1016   if (!(*Context->Routine)(Context->Context,
1017     ExpSplayTreeNodeKey(Node),
1018     ExpSplayTreeNodeValue(Node)))
1019     {
1020       return FALSE;
1021     }
1022
1023         for (n = ExpSplayTreeNodeSame(Node); n; n = ExpSplayTreeNodeSame(n))
1024                 {
1025                   /* Call the traversal routine */
1026                   if (!(*Context->Routine)(Context->Context,
1027                     ExpSplayTreeNodeKey(n),
1028                     ExpSplayTreeNodeValue(n)))
1029                     {
1030                       return FALSE;
1031                     }
1032                 }
1033
1034   /* Traverse right subtree */
1035   ExpTraverseSplayTreeInorder(Context, ExpSplayTreeLargerChildNode(Node));
1036
1037   return TRUE;
1038 }
1039
1040
1041 /*
1042  * Traverse a splay tree using postorder traversal method.
1043  * Returns FALSE, if the traversal was terminated prematurely or
1044  * TRUE if the callback routine did not request that the traversal
1045  * be terminated prematurely.
1046  * The lock for the tree must be acquired when this routine is called.
1047  */
1048 BOOLEAN
1049 ExpTraverseSplayTreePostorder(PTRAVERSE_CONTEXT Context,
1050   PSPLAY_TREE_NODE Node)
1051 {
1052   PSPLAY_TREE_NODE n;
1053
1054   if (Node == NULL)
1055     return TRUE;
1056
1057   /* Traverse 'smaller' subtree */
1058   ExpTraverseSplayTreePostorder(Context, ExpSplayTreeSmallerChildNode(Node));
1059
1060   /* Traverse 'larger' subtree */
1061   ExpTraverseSplayTreePostorder(Context, ExpSplayTreeLargerChildNode(Node));
1062
1063   /* Call the traversal routine */
1064   if (!(*Context->Routine)(Context->Context,
1065     ExpSplayTreeNodeKey(Node),
1066     ExpSplayTreeNodeValue(Node)))
1067     {
1068       return FALSE;
1069     }
1070
1071         for (n = ExpSplayTreeNodeSame(Node); n; n = ExpSplayTreeNodeSame(n))
1072                 {
1073                   /* Call the traversal routine */
1074                   if (!(*Context->Routine)(Context->Context,
1075                     ExpSplayTreeNodeKey(n),
1076                     ExpSplayTreeNodeValue(n)))
1077                     {
1078                       return FALSE;
1079                     }
1080                 }
1081
1082   return TRUE;
1083 }
1084
1085
1086 /*
1087  * Default key compare function. Compares the integer values of the two keys.
1088  */
1089 LONG STDCALL
1090 ExpSplayTreeDefaultCompare(IN PVOID  Key1,
1091   IN PVOID  Key2)
1092 {
1093   if (Key1 == Key2)
1094     return 0;
1095
1096   return (((LONG_PTR) Key1 < (LONG_PTR) Key2) ? -1 : 1);
1097 }
1098
1099
1100 /*
1101  * Initializes a splay tree.
1102  */
1103 BOOLEAN STDCALL
1104 ExInitializeSplayTree(IN PSPLAY_TREE  Tree,
1105   IN PKEY_COMPARATOR  Compare,
1106   IN BOOLEAN  Weighted,
1107   IN BOOLEAN  UseNonPagedPool)
1108 {
1109   RtlZeroMemory(Tree, sizeof(SPLAY_TREE));
1110
1111   Tree->Compare = (Compare == NULL)
1112     ? ExpSplayTreeDefaultCompare : Compare;
1113
1114   Tree->Weighted = Weighted;
1115
1116   if (Weighted)
1117     {
1118       Tree->Reserved[SPLAY_INDEX]  = (PVOID) ExpSplayTreeWeight;
1119       Tree->Reserved[SEARCH_INDEX] = (PVOID) ExpSearchSplayTreeWeight;
1120       Tree->Reserved[INSERT_INDEX] = (PVOID) ExpInsertSplayTreeWeight;
1121       Tree->Reserved[REMOVE_INDEX] = (PVOID) ExpRemoveSplayTreeWeight;
1122     }
1123         else
1124                 {
1125       Tree->Reserved[SPLAY_INDEX]  = (PVOID) ExpSplayTreeNoWeight;
1126       Tree->Reserved[SEARCH_INDEX] = (PVOID) ExpSearchSplayTreeNoWeight;
1127       Tree->Reserved[INSERT_INDEX] = (PVOID) ExpInsertSplayTreeNoWeight;
1128       Tree->Reserved[REMOVE_INDEX] = (PVOID) ExpRemoveSplayTreeNoWeight;
1129                 }
1130
1131   Tree->UseNonPagedPool = UseNonPagedPool;
1132
1133   if (UseNonPagedPool)
1134     {
1135                   ExInitializeNPagedLookasideList(
1136                     &Tree->List.NonPaged,           /* Lookaside list */
1137                     NULL,                           /* Allocate routine */
1138                     NULL,                           /* Free routine */
1139                     0,                              /* Flags */
1140                     sizeof(SPLAY_TREE_NODE),        /* Size of each entry */
1141                     TAG('E','X','S','T'),           /* Tag */
1142                     0);                             /* Depth */
1143
1144       KeInitializeSpinLock(&Tree->Lock.NonPaged);
1145                 }
1146                 else
1147                 {
1148                   ExInitializePagedLookasideList(
1149                     &Tree->List.Paged,              /* Lookaside list */
1150                     NULL,                           /* Allocate routine */
1151                     NULL,                           /* Free routine */
1152                     0,                              /* Flags */
1153                     sizeof(SPLAY_TREE_NODE),       /* Size of each entry */
1154                     TAG('E','X','S','T'),           /* Tag */
1155                     0);                             /* Depth */
1156
1157       ExInitializeFastMutex(&Tree->Lock.Paged);
1158                 }
1159
1160   return TRUE;
1161 }
1162
1163
1164 /*
1165  * Release resources used by a splay tree.
1166  */
1167 VOID STDCALL
1168 ExDeleteSplayTree(IN PSPLAY_TREE  Tree)
1169 {
1170   PSPLAY_TREE_NODE RemovedNode;
1171   PSPLAY_TREE_NODE Node;
1172
1173   /* Remove all nodes */
1174   Node = ExpSplayTreeRootNode(Tree);
1175   while (Node != NULL)
1176     {
1177       Node = ExpRemoveSplayTree(Tree, Node->Key, Node, &RemovedNode);
1178
1179       if (RemovedNode != NULL)
1180                   {
1181           ExpDestroySplayTreeNode(Tree, RemovedNode);
1182         }
1183     }
1184
1185   if (Tree->UseNonPagedPool)
1186     {
1187       ExDeleteNPagedLookasideList(&Tree->List.NonPaged);
1188           }
1189         else
1190                 {
1191       ExDeletePagedLookasideList(&Tree->List.Paged);
1192                 }
1193 }
1194
1195
1196 /*
1197  * Insert a value in a splay tree.
1198  */
1199 VOID STDCALL
1200 ExInsertSplayTree(IN PSPLAY_TREE  Tree,
1201   IN PVOID  Key,
1202   IN PVOID  Value)
1203 {
1204   PSPLAY_TREE_NODE Node;
1205   PSPLAY_TREE_NODE NewNode;
1206   KIRQL OldIrql;
1207
1208   /* FIXME: Use SEH for error reporting */
1209
1210   NewNode = ExpCreateSplayTreeNode(Tree, Value);
1211
1212   ExpLockSplayTree(Tree, &OldIrql);
1213   Node = ExpInsertSplayTree(Tree, Key, ExpSplayTreeRootNode(Tree), NewNode);
1214   ExpSplayTreeRootNode(Tree) = Node;
1215   ExpUnlockSplayTree(Tree, &OldIrql);
1216 }
1217
1218
1219 /*
1220  * Search for a value associated with a given key in a splay tree.
1221  */
1222 BOOLEAN STDCALL
1223 ExSearchSplayTree(IN PSPLAY_TREE  Tree,
1224   IN PVOID  Key,
1225   OUT PVOID  * Value)
1226 {
1227   PSPLAY_TREE_NODE Node;
1228   BOOLEAN Status;
1229   KIRQL OldIrql;
1230
1231   ExpLockSplayTree(Tree, &OldIrql);
1232   Status = ExpSearchSplayTree(Tree, Key, ExpSplayTreeRootNode(Tree), &Node);
1233
1234   if (Status)
1235     {
1236       ExpSplayTreeRootNode(Tree) = Node;
1237       *Value = ExpSplayTreeNodeValue(Node);
1238       ExpUnlockSplayTree(Tree, &OldIrql);
1239                   return TRUE;
1240           }
1241         else
1242           {
1243       ExpUnlockSplayTree(Tree, &OldIrql);
1244             return FALSE;
1245           }
1246 }
1247
1248
1249 /*
1250  * Remove a value associated with a given key from a splay tree.
1251  */
1252 BOOLEAN STDCALL
1253 ExRemoveSplayTree(IN PSPLAY_TREE  Tree,
1254   IN PVOID  Key,
1255   IN PVOID  * Value)
1256 {
1257   PSPLAY_TREE_NODE RemovedNode;
1258   PSPLAY_TREE_NODE Node;
1259   KIRQL OldIrql;
1260
1261   ExpLockSplayTree(Tree, &OldIrql);
1262   Node = ExpRemoveSplayTree(Tree, Key, ExpSplayTreeRootNode(Tree), &RemovedNode);
1263   ExpSplayTreeRootNode(Tree) = Node;
1264   ExpUnlockSplayTree(Tree, &OldIrql);
1265
1266   if (RemovedNode != NULL)
1267                 {
1268       *Value = ExpSplayTreeNodeValue(RemovedNode);
1269       ExpDestroySplayTreeNode(Tree, RemovedNode);
1270       return TRUE;
1271                 }
1272         else
1273                 {
1274       return FALSE;
1275                 }
1276 }
1277
1278
1279 /*
1280  * Return the weight of the root node in the splay tree.
1281  * The returned value is the number of nodes in the tree.
1282  */
1283 BOOLEAN STDCALL
1284 ExWeightOfSplayTree(IN PSPLAY_TREE  Tree,
1285   OUT PULONG  Weight)
1286 {
1287   KIRQL OldIrql;
1288
1289   ExpLockSplayTree(Tree, &OldIrql);
1290
1291         if (!Tree->Weighted)
1292                 {
1293       ExpUnlockSplayTree(Tree, &OldIrql);
1294       return FALSE;
1295                 }
1296
1297   *Weight = ExpSplayTreeNodeWeight(ExpSplayTreeRootNode(Tree));
1298   ExpUnlockSplayTree(Tree, &OldIrql);
1299
1300   return TRUE;
1301 }
1302
1303
1304 /*
1305  * Traverse a splay tree using either preorder, inorder or postorder
1306  * traversal method.
1307  * Returns FALSE, if the traversal was terminated prematurely or
1308  * TRUE if the callback routine did not request that the traversal
1309  * be terminated prematurely.
1310  */
1311 BOOLEAN STDCALL
1312 ExTraverseSplayTree(IN PSPLAY_TREE  Tree,
1313   IN TRAVERSE_METHOD  Method,
1314   IN PTRAVERSE_ROUTINE  Routine,
1315   IN PVOID  Context)
1316 {
1317   TRAVERSE_CONTEXT tc;
1318   BOOLEAN Status;
1319   KIRQL OldIrql;
1320
1321   tc.Routine = Routine;
1322   tc.Context = Context;
1323
1324   ExpLockSplayTree(Tree, &OldIrql);
1325
1326   if (ExpSplayTreeRootNode(Tree) == NULL)
1327                 {
1328       ExpUnlockSplayTree(Tree, &OldIrql);
1329       return TRUE;
1330                 }
1331
1332   switch (Method)
1333     {
1334       case TraverseMethodPreorder:
1335         Status = ExpTraverseSplayTreePreorder(&tc, ExpSplayTreeRootNode(Tree));
1336         break;
1337
1338       case TraverseMethodInorder:
1339         Status = ExpTraverseSplayTreeInorder(&tc, ExpSplayTreeRootNode(Tree));
1340         break;
1341
1342       case TraverseMethodPostorder:
1343         Status = ExpTraverseSplayTreePostorder(&tc, ExpSplayTreeRootNode(Tree));
1344         break;
1345
1346       default:
1347         Status = FALSE;
1348         break;
1349     }
1350
1351   ExpUnlockSplayTree(Tree, &OldIrql);
1352
1353   return Status;
1354 }
1355
1356 /* EOF */