3 * Copyright (C) 1998-2002 ReactOS Team
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.
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.
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.
20 * PROJECT: ReactOS kernel
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
28 * 15-03-2002 CSH Created
30 #include <ddk/ntddk.h>
31 #include <internal/ex.h>
34 #include <internal/debug.h>
36 /* DATA **********************************************************************/
41 typedef struct _SPLAY_TREE_NODE
43 /* Children on this branch has smaller keys than this node */
44 struct _SPLAY_TREE_NODE
* SmallerChild
;
46 /* Children on this branch has larger keys than this node */
47 struct _SPLAY_TREE_NODE
* LargerChild
;
49 /* Points to a node with identical key */
50 struct _SPLAY_TREE_NODE
* Same
;
52 /* Key of this node */
55 /* Value of this node */
58 /* The number of nodes rooted here */
60 } SPLAY_TREE_NODE
, *PSPLAY_TREE_NODE
;
63 #define SEARCH_INDEX 1
64 #define INSERT_INDEX 2
65 #define REMOVE_INDEX 3
67 typedef PSPLAY_TREE_NODE (*PSPLAY_TREE_SPLAY
)(PSPLAY_TREE Tree
,
69 PSPLAY_TREE_NODE Node
);
71 typedef BOOLEAN (*PSPLAY_TREE_SEARCH
)(PSPLAY_TREE Tree
,
73 PSPLAY_TREE_NODE Node
,
74 PSPLAY_TREE_NODE
* ReturnNode
);
76 typedef PSPLAY_TREE_NODE (*PSPLAY_TREE_INSERT
)(PSPLAY_TREE Tree
,
78 PSPLAY_TREE_NODE Node
,
79 PSPLAY_TREE_NODE New
);
81 typedef PSPLAY_TREE_NODE (*PSPLAY_TREE_REMOVE
)(PSPLAY_TREE Tree
,
83 PSPLAY_TREE_NODE Node
,
84 PSPLAY_TREE_NODE
* RemovedNode
);
86 /* FUNCTIONS ****************************************************************/
88 #define ExpSplayTreeRootNode(Tree)(((PSPLAY_TREE) (Tree))->RootNode)
89 #define ExpSplayTreeNodeKey(Node)((Node)->Key)
90 #define ExpSplayTreeNodeValue(Node)((Node)->Value)
91 #define ExpSplayTreeSmallerChildNode(Node)((Node)->SmallerChild)
92 #define ExpSplayTreeLargerChildNode(Node)((Node)->LargerChild)
93 #define ExpSplayTreeNodeEqual(Equality)((Equality) == 0)
94 #define ExpSplayTreeNodeLess(Equality)((Equality) < 0)
95 #define ExpSplayTreeNodeMore(Equality)((Equality) > 0)
96 #define ExpSplayTreeNodeSame(Node)((Node)->Same)
97 #define ExpSplayTreeNodeWeight(Node)((Node)->Weight)
98 #define ExpSplayTreeNodeGetWeight(Node)(((Node) == NULL) ? 0 : ((Node)->Weight))
99 #define ExpSplayTreeNodeSetWeight(Node, _Weight)((Node)->Weight = (_Weight))
101 #define KEY_NOTUSED (PVOID)-1
105 * Allocate resources for a new node and initialize it.
107 inline PSPLAY_TREE_NODE
108 ExpCreateSplayTreeNode(PSPLAY_TREE Tree
,
111 PSPLAY_TREE_NODE Node
;
113 Node
= (PSPLAY_TREE_NODE
) ExAllocateFromPagedLookasideList(&Tree
->LookasideList
);
117 ExpSplayTreeSmallerChildNode(Node
) = NULL
;
118 ExpSplayTreeLargerChildNode(Node
) = NULL
;
119 ExpSplayTreeNodeValue(Node
) = Value
;
126 * Release resources for the node.
129 ExpDestroySplayTreeNode(PSPLAY_TREE Tree
,
130 PSPLAY_TREE_NODE Node
)
132 ExFreeToPagedLookasideList(&Tree
->LookasideList
, Node
);
137 * Splay using the key 'Key' (which may or may not be in the tree). The starting
138 * root is Node. Weight fields are maintained.
139 * The lock for the tree must be acquired when this routine is called.
140 * This routine does not maintain weight information.
143 ExpSplayTreeNoWeight(PSPLAY_TREE Tree
,
145 PSPLAY_TREE_NODE Node
)
157 ExpSplayTreeSmallerChildNode(&N
) = NULL
;
158 ExpSplayTreeLargerChildNode(&N
) = NULL
;
164 Equality
= (*Tree
->Compare
)(Key
, ExpSplayTreeNodeKey(Node
));
166 if (ExpSplayTreeNodeLess(Equality
))
168 if (ExpSplayTreeSmallerChildNode(Node
) == NULL
)
171 ChildEquality
= (*Tree
->Compare
)(Key
, ExpSplayTreeNodeKey(ExpSplayTreeSmallerChildNode(Node
)));
172 if (ExpSplayTreeNodeLess(ChildEquality
))
174 y
= ExpSplayTreeSmallerChildNode(Node
); /* Rotate smaller */
175 ExpSplayTreeSmallerChildNode(Node
) = ExpSplayTreeLargerChildNode(y
);
176 ExpSplayTreeLargerChildNode(y
) = Node
;
179 if (ExpSplayTreeSmallerChildNode(Node
) == NULL
)
183 ExpSplayTreeSmallerChildNode(r
) = Node
; /* Link smaller */
185 Node
= ExpSplayTreeSmallerChildNode(Node
);
187 else if (ExpSplayTreeNodeMore(Equality
))
189 if (ExpSplayTreeLargerChildNode(Node
) == NULL
)
192 ChildEquality
= (*Tree
->Compare
)(Key
, ExpSplayTreeNodeKey(ExpSplayTreeLargerChildNode(Node
)));
193 if (ExpSplayTreeNodeMore(ChildEquality
))
195 y
= ExpSplayTreeLargerChildNode(Node
); /* Rotate larger */
196 ExpSplayTreeLargerChildNode(Node
) = ExpSplayTreeSmallerChildNode(y
);
197 ExpSplayTreeSmallerChildNode(y
) = Node
;
200 if (ExpSplayTreeLargerChildNode(Node
) == NULL
)
204 ExpSplayTreeLargerChildNode(l
) = Node
; /* Link larger */
206 Node
= ExpSplayTreeLargerChildNode(Node
);
214 ExpSplayTreeLargerChildNode(l
) = NULL
;
215 ExpSplayTreeSmallerChildNode(r
) = NULL
;
217 ExpSplayTreeLargerChildNode(l
) = ExpSplayTreeSmallerChildNode(Node
); /* Assemble */
218 ExpSplayTreeSmallerChildNode(r
) = ExpSplayTreeLargerChildNode(Node
);
219 ExpSplayTreeSmallerChildNode(Node
) = ExpSplayTreeLargerChildNode(&N
);
220 ExpSplayTreeLargerChildNode(Node
) = ExpSplayTreeSmallerChildNode(&N
);
227 * Splay using the key 'Key' (which may or may not be in the tree). The starting
228 * root is Node. Weight fields are maintained.
229 * The lock for the tree must be acquired when this routine is called.
230 * This routine maintains weight information.
233 ExpSplayTreeWeight(PSPLAY_TREE Tree
,
235 PSPLAY_TREE_NODE Node
)
252 ExpSplayTreeSmallerChildNode(&N
) = NULL
;
253 ExpSplayTreeLargerChildNode(&N
) = NULL
;
258 RootWeight
= ExpSplayTreeNodeGetWeight(Node
);
265 Equality
= (*Tree
->Compare
)(Key
, ExpSplayTreeNodeKey(Node
));
267 if (ExpSplayTreeNodeLess(Equality
))
269 if (ExpSplayTreeSmallerChildNode(Node
) == NULL
)
272 ChildEquality
= (*Tree
->Compare
)(Key
, ExpSplayTreeNodeKey(ExpSplayTreeSmallerChildNode(Node
)));
273 if (ExpSplayTreeNodeLess(ChildEquality
))
275 y
= ExpSplayTreeSmallerChildNode(Node
); /* Rotate smaller */
276 ExpSplayTreeSmallerChildNode(Node
) = ExpSplayTreeLargerChildNode(y
);
277 ExpSplayTreeLargerChildNode(y
) = Node
;
280 ExpSplayTreeNodeSetWeight(Node
, ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(Node
))
281 + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(Node
)) + 1);
285 if (ExpSplayTreeSmallerChildNode(Node
) == NULL
)
289 ExpSplayTreeSmallerChildNode(r
) = Node
; /* Link smaller */
291 Node
= ExpSplayTreeSmallerChildNode(Node
);
294 Weight2
+= 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(r
));
297 else if (ExpSplayTreeNodeMore(Equality
))
299 if (ExpSplayTreeLargerChildNode(Node
) == NULL
)
302 ChildEquality
= (*Tree
->Compare
)(Key
, ExpSplayTreeNodeKey(ExpSplayTreeLargerChildNode(Node
)));
303 if (ExpSplayTreeNodeMore(ChildEquality
))
305 y
= ExpSplayTreeLargerChildNode(Node
); /* Rotate larger */
306 ExpSplayTreeLargerChildNode(Node
) = ExpSplayTreeSmallerChildNode(y
);
307 ExpSplayTreeSmallerChildNode(y
) = Node
;
310 ExpSplayTreeNodeSetWeight(Node
, ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(Node
))
311 + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(Node
)) + 1);
315 if (ExpSplayTreeLargerChildNode(Node
) == NULL
)
319 ExpSplayTreeLargerChildNode(l
) = Node
; /* Link larger */
321 Node
= ExpSplayTreeLargerChildNode(Node
);
324 Weight1
+= 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(l
));
335 Weight1
+= ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(Node
)); /* Now Weight1 and Weight2 are the weights of */
336 Weight2
+= ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(Node
)); /* The 'smaller' and 'larger' trees we just built. */
337 ExpSplayTreeNodeSetWeight(Node
, Weight1
+ Weight2
+ 1);
340 ExpSplayTreeLargerChildNode(l
) = NULL
;
341 ExpSplayTreeSmallerChildNode(r
) = NULL
;
344 /* The following two loops correct the weight fields of the right path from
345 * the left child of the root and the right path from the left child of the
348 for (y
= ExpSplayTreeLargerChildNode(&N
); y
!= NULL
; y
= ExpSplayTreeLargerChildNode(y
)) {
349 ExpSplayTreeNodeSetWeight(y
, Weight1
);
350 Weight1
-= 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(y
));
352 for (y
= ExpSplayTreeSmallerChildNode(&N
); y
!= NULL
; y
= ExpSplayTreeSmallerChildNode(y
)) {
353 ExpSplayTreeNodeSetWeight(y
, Weight2
);
354 Weight2
-= 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(y
));
358 ExpSplayTreeLargerChildNode(l
) = ExpSplayTreeSmallerChildNode(Node
); /* Assemble */
359 ExpSplayTreeSmallerChildNode(r
) = ExpSplayTreeLargerChildNode(Node
);
360 ExpSplayTreeSmallerChildNode(Node
) = ExpSplayTreeLargerChildNode(&N
);
361 ExpSplayTreeLargerChildNode(Node
) = ExpSplayTreeSmallerChildNode(&N
);
367 inline PSPLAY_TREE_NODE
368 ExpSplayTree(PSPLAY_TREE Tree
,
370 PSPLAY_TREE_NODE Node
)
372 return (*((PSPLAY_TREE_SPLAY
)Tree
->Reserved
[SPLAY_INDEX
]))(Tree
, Key
, Node
);
377 * The lock for the tree must be acquired when this routine is called.
378 * This routine does not maintain weight information.
381 ExpSearchSplayTreeNoWeight(PSPLAY_TREE Tree
,
383 PSPLAY_TREE_NODE Node
,
384 PSPLAY_TREE_NODE
* ReturnNode
)
391 Node
= ExpSplayTree(Tree
, Key
, Node
);
393 Equality
= (*Tree
->Compare
)(Key
, ExpSplayTreeNodeKey(Node
));
394 if (ExpSplayTreeNodeEqual(Equality
))
403 *ReturnNode
= NULL
; /* No match */
404 return FALSE
; /* It wasn't there */
410 * The lock for the tree must be acquired when this routine is called.
411 * This routine maintains weight information.
414 ExpSearchSplayTreeWeight(PSPLAY_TREE Tree
,
416 PSPLAY_TREE_NODE Node
,
417 PSPLAY_TREE_NODE
* ReturnNode
)
429 tweight
= ExpSplayTreeNodeGetWeight(Node
);
432 Node
= ExpSplayTree(Tree
, Key
, Node
);
434 Equality
= (*Tree
->Compare
)(Key
, ExpSplayTreeNodeKey(Node
));
435 if (ExpSplayTreeNodeEqual(Equality
))
442 ExpSplayTreeNodeSetWeight(x
, tweight
- 1);
451 *ReturnNode
= NULL
; /* No match */
452 return FALSE
; /* It wasn't there */
458 ExpSearchSplayTree(PSPLAY_TREE Tree
,
460 PSPLAY_TREE_NODE Node
,
461 PSPLAY_TREE_NODE
* ReturnNode
)
463 return (*((PSPLAY_TREE_SEARCH
)Tree
->Reserved
[SEARCH_INDEX
]))(Tree
, Key
, Node
, ReturnNode
);
468 * The lock for the tree must be acquired when this routine is called.
469 * This routine does not maintain weight information.
472 ExpInsertSplayTreeNoWeight(PSPLAY_TREE Tree
,
474 PSPLAY_TREE_NODE Node
,
475 PSPLAY_TREE_NODE New
)
484 Node
= ExpSplayTree(Tree
, Key
, Node
);
486 Equality
= (*Tree
->Compare
)(Key
, ExpSplayTreeNodeKey(Node
));
487 if (ExpSplayTreeNodeEqual(Equality
))
492 /* This is how to prevent the same node key getting added twice */
497 /* It already exists one of this size */
499 ExpSplayTreeNodeSame(New
) = Node
;
500 ExpSplayTreeNodeKey(New
) = Key
;
501 ExpSplayTreeSmallerChildNode(New
) = ExpSplayTreeSmallerChildNode(Node
);
502 ExpSplayTreeLargerChildNode(New
) = ExpSplayTreeLargerChildNode(Node
);
504 ExpSplayTreeSmallerChildNode(Node
) = New
;
505 ExpSplayTreeNodeKey(Node
) = KEY_NOTUSED
;
517 ExpSplayTreeSmallerChildNode(New
) = NULL
;
518 ExpSplayTreeLargerChildNode(New
) = NULL
;
520 else if (ExpSplayTreeNodeLess((*Tree
->Compare
)(Key
, ExpSplayTreeNodeKey(Node
))))
522 ExpSplayTreeSmallerChildNode(New
) = ExpSplayTreeSmallerChildNode(Node
);
523 ExpSplayTreeLargerChildNode(New
) = Node
;
524 ExpSplayTreeSmallerChildNode(Node
) = NULL
;
528 ExpSplayTreeLargerChildNode(New
) = ExpSplayTreeLargerChildNode(Node
);
529 ExpSplayTreeSmallerChildNode(New
) = Node
;
530 ExpSplayTreeLargerChildNode(Node
) = NULL
;
533 ExpSplayTreeNodeKey(New
) = Key
;
536 /* No identical nodes (yet) */
537 ExpSplayTreeNodeSame(New
) = NULL
;
545 * The lock for the tree must be acquired when this routine is called.
546 * This routine maintains weight information.
549 ExpInsertSplayTreeWeight(PSPLAY_TREE Tree
,
551 PSPLAY_TREE_NODE Node
,
552 PSPLAY_TREE_NODE New
)
561 Node
= ExpSplayTree(Tree
, Key
, Node
);
563 Equality
= (*Tree
->Compare
)(Key
, ExpSplayTreeNodeKey(Node
));
564 if (ExpSplayTreeNodeEqual(Equality
))
569 /* This is how to prevent the same node key getting added twice */
574 /* It already exists one of this size */
576 ExpSplayTreeNodeSame(New
) = Node
;
577 ExpSplayTreeNodeKey(New
) = Key
;
578 ExpSplayTreeSmallerChildNode(New
) = ExpSplayTreeSmallerChildNode(Node
);
579 ExpSplayTreeLargerChildNode(New
) = ExpSplayTreeLargerChildNode(Node
);
582 ExpSplayTreeNodeSetWeight(New
, ExpSplayTreeNodeGetWeight(Node
));
585 ExpSplayTreeSmallerChildNode(Node
) = New
;
586 ExpSplayTreeNodeKey(Node
) = KEY_NOTUSED
;
598 ExpSplayTreeSmallerChildNode(New
) = NULL
;
599 ExpSplayTreeLargerChildNode(New
) = NULL
;
601 else if (ExpSplayTreeNodeLess((*Tree
->Compare
)(Key
, ExpSplayTreeNodeKey(Node
))))
603 ExpSplayTreeSmallerChildNode(New
) = ExpSplayTreeSmallerChildNode(Node
);
604 ExpSplayTreeLargerChildNode(New
) = Node
;
605 ExpSplayTreeSmallerChildNode(Node
) = NULL
;
608 ExpSplayTreeNodeSetWeight(Node
, 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(Node
)));
614 ExpSplayTreeLargerChildNode(New
) = ExpSplayTreeLargerChildNode(Node
);
615 ExpSplayTreeSmallerChildNode(New
) = Node
;
616 ExpSplayTreeLargerChildNode(Node
) = NULL
;
619 ExpSplayTreeNodeSetWeight(Node
, 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(Node
)));
624 ExpSplayTreeNodeKey(New
) = Key
;
627 ExpSplayTreeNodeSetWeight(New
, 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(New
))
628 + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(New
)));
632 /* No identical nodes (yet) */
633 ExpSplayTreeNodeSame(New
) = NULL
;
640 inline PSPLAY_TREE_NODE
641 ExpInsertSplayTree(PSPLAY_TREE Tree
,
643 PSPLAY_TREE_NODE Node
,
644 PSPLAY_TREE_NODE New
)
646 return (*((PSPLAY_TREE_INSERT
)Tree
->Reserved
[INSERT_INDEX
]))(Tree
, Key
, Node
, New
);
651 * Deletes the node with key 'Key' from the tree if it's there.
652 * Return a pointer to the resulting tree.
653 * The lock for the tree must be acquired when this routine is called.
654 * This routine does not maintain weight information.
657 ExpRemoveSplayTreeNoWeight(PSPLAY_TREE Tree
,
659 PSPLAY_TREE_NODE Node
,
660 PSPLAY_TREE_NODE
* RemovedNode
)
668 Node
= ExpSplayTree(Tree
, Key
, Node
);
670 Equality
= (*Tree
->Compare
)(Key
, ExpSplayTreeNodeKey(Node
));
671 if (ExpSplayTreeNodeEqual(Equality
))
676 /* FIRST! Check if there is a list with identical sizes */
677 x
= ExpSplayTreeNodeSame(Node
);
680 /* There is several, pick one from the list */
682 /* 'x' is the new root node */
684 ExpSplayTreeNodeKey(x
) = ExpSplayTreeNodeKey(Node
);
685 ExpSplayTreeLargerChildNode(x
) = ExpSplayTreeLargerChildNode(Node
);
686 ExpSplayTreeSmallerChildNode(x
) = ExpSplayTreeSmallerChildNode(Node
);
693 if (ExpSplayTreeSmallerChildNode(Node
) == NULL
)
695 x
= ExpSplayTreeLargerChildNode(Node
);
699 x
= ExpSplayTree(Tree
, Key
, ExpSplayTreeSmallerChildNode(Node
));
700 ExpSplayTreeLargerChildNode(x
) = ExpSplayTreeLargerChildNode(Node
);
708 *RemovedNode
= NULL
; /* No match */
709 return Node
; /* It wasn't there */
715 * Deletes the node with key 'Key' from the tree if it's there.
716 * Return a pointer to the resulting tree.
717 * The lock for the tree must be acquired when this routine is called.
718 * This routine maintains weight information.
721 ExpRemoveSplayTreeWeight(PSPLAY_TREE Tree
,
723 PSPLAY_TREE_NODE Node
,
724 PSPLAY_TREE_NODE
* RemovedNode
)
737 tweight
= ExpSplayTreeNodeGetWeight(Node
);
740 Node
= ExpSplayTree(Tree
, Key
, Node
);
742 Equality
= (*Tree
->Compare
)(Key
, ExpSplayTreeNodeKey(Node
));
743 if (ExpSplayTreeNodeEqual(Equality
))
748 /* FIRST! Check if there is a list with identical sizes */
749 x
= ExpSplayTreeNodeSame(Node
);
752 /* There is several, pick one from the list */
754 /* 'x' is the new root node */
756 ExpSplayTreeNodeKey(x
) = ExpSplayTreeNodeKey(Node
);
757 ExpSplayTreeLargerChildNode(x
) = ExpSplayTreeLargerChildNode(Node
);
758 ExpSplayTreeSmallerChildNode(x
) = ExpSplayTreeSmallerChildNode(Node
);
761 ExpSplayTreeNodeSetWeight(x
, ExpSplayTreeNodeGetWeight(Node
));
769 if (ExpSplayTreeSmallerChildNode(Node
) == NULL
)
771 x
= ExpSplayTreeLargerChildNode(Node
);
775 x
= ExpSplayTree(Tree
, Key
, ExpSplayTreeSmallerChildNode(Node
));
776 ExpSplayTreeLargerChildNode(x
) = ExpSplayTreeLargerChildNode(Node
);
783 ExpSplayTreeNodeSetWeight(x
, tweight
- 1);
791 *RemovedNode
= NULL
; /* No match */
792 return Node
; /* It wasn't there */
797 inline PSPLAY_TREE_NODE
798 ExpRemoveSplayTree(PSPLAY_TREE Tree
,
800 PSPLAY_TREE_NODE Node
,
801 PSPLAY_TREE_NODE
* RemovedNode
)
803 return (*((PSPLAY_TREE_REMOVE
)Tree
->Reserved
[REMOVE_INDEX
]))(Tree
, Key
, Node
, RemovedNode
);
808 * The lock for the tree must be acquired when this routine is called.
811 ExpPrintSplayTree(PSPLAY_TREE Tree
,
812 PSPLAY_TREE_NODE Node
,
822 Distance
+= ExpPrintSplayTree(Tree
, ExpSplayTreeLargerChildNode(Node
), Distance
+ 1);
824 for (i
= 0; i
< Distance
; i
++)
831 DbgPrint("%d(%d)[%d]", ExpSplayTreeNodeKey(Node
), ExpSplayTreeNodeGetWeight(Node
), i
);
835 DbgPrint("%d[%d]", ExpSplayTreeNodeKey(Node
), i
);
838 for (n
= ExpSplayTreeNodeSame(Node
); n
; n
= ExpSplayTreeNodeSame(n
))
847 d
+= ExpPrintSplayTree(Tree
, ExpSplayTreeSmallerChildNode(Node
), Distance
+ 1);
858 * The lock for the tree must be acquired when this routine is called.
859 * Returns the new root of the tree.
860 * Use of this routine could improve performance, or it might not.
861 * FIXME: Do some performance tests
864 ExpSplayTreeMaxTreeWeight(PSPLAY_TREE Tree
,
865 PSPLAY_TREE_NODE Node
)
867 PSPLAY_TREE_NODE First
= Node
;
872 Diff
= ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(Node
))
873 - ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(Node
));
875 if (Diff
>= MAX_DIFF
)
877 Node
= ExpSplayTreeSmallerChildNode(Node
);
879 else if (Diff
<= -MAX_DIFF
)
881 Node
= ExpSplayTreeLargerChildNode(Node
);
885 } while (abs(Diff
) >= MAX_DIFF
);
888 return ExpSplayTree(Tree
, ExpSplayTreeNodeKey(Node
), First
);
897 * Default key compare function. Compares the integer values of the two keys.
900 ExpSplayTreeDefaultCompare(IN PVOID Key1
,
906 return (((LONG_PTR
) Key1
< (LONG_PTR
) Key2
) ? -1 : 1);
911 * Initializes a splay tree.
914 ExInitializeSplayTree(IN PSPLAY_TREE Tree
,
915 IN PKEY_COMPARATOR Compare
,
918 RtlZeroMemory(Tree
, sizeof(SPLAY_TREE
));
920 Tree
->Compare
= (Compare
== NULL
)
921 ? ExpSplayTreeDefaultCompare
: Compare
;
923 Tree
->Weighted
= Weighted
;
927 Tree
->Reserved
[SPLAY_INDEX
] = (PVOID
) ExpSplayTreeWeight
;
928 Tree
->Reserved
[SEARCH_INDEX
] = (PVOID
) ExpSearchSplayTreeWeight
;
929 Tree
->Reserved
[INSERT_INDEX
] = (PVOID
) ExpInsertSplayTreeWeight
;
930 Tree
->Reserved
[REMOVE_INDEX
] = (PVOID
) ExpRemoveSplayTreeWeight
;
934 Tree
->Reserved
[SPLAY_INDEX
] = (PVOID
) ExpSplayTreeNoWeight
;
935 Tree
->Reserved
[SEARCH_INDEX
] = (PVOID
) ExpSearchSplayTreeNoWeight
;
936 Tree
->Reserved
[INSERT_INDEX
] = (PVOID
) ExpInsertSplayTreeNoWeight
;
937 Tree
->Reserved
[REMOVE_INDEX
] = (PVOID
) ExpRemoveSplayTreeNoWeight
;
940 ExInitializePagedLookasideList(
941 &Tree
->LookasideList
, /* Lookaside list */
942 NULL
, /* Allocate routine */
943 NULL
, /* Free routine */
945 sizeof(SPLAY_TREE_NODE
), /* Size of each entry */
946 TAG('E','X','S','T'), /* Tag */
949 ExInitializeFastMutex(&Tree
->Lock
);
956 * Release resources used by a splay tree.
959 ExDeleteSplayTree(IN PSPLAY_TREE Tree
)
961 PSPLAY_TREE_NODE RemovedNode
;
962 PSPLAY_TREE_NODE Node
;
964 /* Remove all nodes */
965 Node
= ExpSplayTreeRootNode(Tree
);
968 Node
= ExpRemoveSplayTree(Tree
, Node
->Key
, Node
, &RemovedNode
);
970 if (RemovedNode
!= NULL
)
972 ExpDestroySplayTreeNode(Tree
, RemovedNode
);
976 ExDeletePagedLookasideList(&Tree
->LookasideList
);
981 * Insert a value in a splay tree.
984 ExInsertSplayTree(IN PSPLAY_TREE Tree
,
988 PSPLAY_TREE_NODE Node
;
989 PSPLAY_TREE_NODE NewNode
;
991 /* FIXME: Use SEH for error reporting */
993 NewNode
= ExpCreateSplayTreeNode(Tree
, Value
);
995 ExAcquireFastMutex(&Tree
->Lock
);
996 Node
= ExpInsertSplayTree(Tree
, Key
, ExpSplayTreeRootNode(Tree
), NewNode
);
997 ExpSplayTreeRootNode(Tree
) = Node
;
998 ExReleaseFastMutex(&Tree
->Lock
);
1003 * Search for a value associated with a given key in a splay tree.
1006 ExSearchSplayTree(IN PSPLAY_TREE Tree
,
1010 PSPLAY_TREE_NODE Node
;
1013 ExAcquireFastMutex(&Tree
->Lock
);
1014 Status
= ExpSearchSplayTree(Tree
, Key
, ExpSplayTreeRootNode(Tree
), &Node
);
1018 ExpSplayTreeRootNode(Tree
) = Node
;
1019 *Value
= ExpSplayTreeNodeValue(Node
);
1020 ExReleaseFastMutex(&Tree
->Lock
);
1025 ExReleaseFastMutex(&Tree
->Lock
);
1032 * Remove a value associated with a given key from a splay tree.
1035 ExRemoveSplayTree(IN PSPLAY_TREE Tree
,
1039 PSPLAY_TREE_NODE RemovedNode
;
1040 PSPLAY_TREE_NODE Node
;
1042 ExAcquireFastMutex(&Tree
->Lock
);
1043 Node
= ExpRemoveSplayTree(Tree
, Key
, ExpSplayTreeRootNode(Tree
), &RemovedNode
);
1044 ExpSplayTreeRootNode(Tree
) = Node
;
1045 ExReleaseFastMutex(&Tree
->Lock
);
1047 if (RemovedNode
!= NULL
)
1049 *Value
= ExpSplayTreeNodeValue(RemovedNode
);
1050 ExpDestroySplayTreeNode(Tree
, RemovedNode
);
1061 * Return the weight of the root node in the splay tree.
1062 * The returned value is the number of nodes in the tree.
1065 ExWeightOfSplayTree(IN PSPLAY_TREE Tree
,
1068 ExAcquireFastMutex(&Tree
->Lock
);
1070 if (!Tree
->Weighted
)
1072 ExReleaseFastMutex(&Tree
->Lock
);
1076 *Weight
= ExpSplayTreeNodeWeight(ExpSplayTreeRootNode(Tree
));
1077 ExReleaseFastMutex(&Tree
->Lock
);