2 * COPYRIGHT: See COPYING in the top level directory
3 * PROJECT: ReactOS system libraries
4 * PURPOSE: Splay-Tree implementation
5 * FILE: lib/rtl/splaytree.c
9 /* INCLUDES *****************************************************************/
16 /* FUNCTIONS ***************************************************************/
24 PRTL_SPLAY_LINKS Links
37 PRTL_SPLAY_LINKS Links
,
38 PRTL_SPLAY_LINKS
*Root
51 PRTL_SPLAY_LINKS Links
64 PRTL_SPLAY_LINKS Links
76 RtlSplay(PRTL_SPLAY_LINKS Links
)
79 * Implementation Notes (http://en.wikipedia.org/wiki/Splay_tree):
81 * To do a splay, we carry out a sequence of rotations,
82 * each of which moves the target node N closer to the root.
84 * Each particular step depends on only two factors:
85 * - Whether N is the left or right child of its parent node, P,
86 * - Whether P is the left or right child of its parent, G (for grandparent node).
88 * Thus, there are four cases:
89 * - Case 1: N is the left child of P and P is the left child of G.
90 * In this case we perform a double right rotation, so that
91 * P becomes N's right child, and G becomes P's right child.
93 * - Case 2: N is the right child of P and P is the right child of G.
94 * In this case we perform a double left rotation, so that
95 * P becomes N's left child, and G becomes P's left child.
97 * - Case 3: N is the left child of P and P is the right child of G.
98 * In this case we perform a rotation so that
99 * G becomes N's left child, and P becomes N's right child.
101 * - Case 4: N is the right child of P and P is the left child of G.
102 * In this case we perform a rotation so that
103 * P becomes N's left child, and G becomes N's right child.
105 * Finally, if N doesn't have a grandparent node, we simply perform a
106 * left or right rotation to move it to the root.
108 * By performing a splay on the node of interest after every operation,
109 * we keep recently accessed nodes near the root and keep the tree
110 * roughly balanced, so that we achieve the desired amortized time bounds.
112 PRTL_SPLAY_LINKS N
, P
, G
;
114 /* N is the item we'll be playing with */
117 /* Let the algorithm run until N becomes the root entry */
118 while (!RtlIsRoot(N
))
120 /* Now get the parent and grand-parent */
124 /* Case 1 & 3: N is left child of P */
125 if (RtlIsLeftChild(N
))
127 /* Case 1: P is the left child of G */
128 if (RtlIsLeftChild(P
))
131 * N's right-child becomes P's left child and
132 * P's right-child becomes G's left child.
134 RtlLeftChild(P
) = RtlRightChild(N
);
135 RtlLeftChild(G
) = RtlRightChild(P
);
138 * If they exist, update their parent pointers too,
139 * since they've changed trees.
141 if (RtlLeftChild(P
)) RtlParent(RtlLeftChild(P
)) = P
;
142 if (RtlLeftChild(G
)) RtlParent(RtlLeftChild(G
)) = G
;
145 * Now we'll shove N all the way to the top.
146 * Check if G is the root first.
150 /* G doesn't have a parent, so N will become the root! */
155 /* G has a parent, so inherit it since we take G's place */
156 RtlParent(N
) = RtlParent(G
);
159 * Now find out who was referencing G and have it reference
160 * N instead, since we're taking G's place.
162 if (RtlIsLeftChild(G
))
165 * G was a left child, so change its parent's left
166 * child link to point to N now.
168 RtlLeftChild(RtlParent(G
)) = N
;
173 * G was a right child, so change its parent's right
174 * child link to point to N now.
176 RtlLeftChild(RtlParent(G
)) = N
;
180 /* Now N is on top, so P has become its child. */
181 RtlRightChild(N
) = P
;
184 /* N is on top, P is its child, so G is grandchild. */
185 RtlRightChild(P
) = G
;
188 /* Case 3: P is the right child of G */
189 else if (RtlIsRightChild(P
))
192 * N's left-child becomes G's right child and
193 * N's right-child becomes P's left child.
195 RtlRightChild(G
) = RtlLeftChild(N
);
196 RtlLeftChild(P
) = RtlRightChild(N
);
199 * If they exist, update their parent pointers too,
200 * since they've changed trees.
202 if (RtlRightChild(G
)) RtlParent(RtlRightChild(G
)) = G
;
203 if (RtlLeftChild(P
)) RtlParent(RtlLeftChild(P
)) = P
;
206 * Now we'll shove N all the way to the top.
207 * Check if G is the root first.
211 /* G doesn't have a parent, so N will become the root! */
216 /* G has a parent, so inherit it since we take G's place */
217 RtlParent(N
) = RtlParent(G
);
220 * Now find out who was referencing G and have it reference
221 * N instead, since we're taking G's place.
223 if (RtlIsLeftChild(G
))
226 * G was a left child, so change its parent's left
227 * child link to point to N now.
229 RtlLeftChild(RtlParent(G
)) = N
;
234 * G was a right child, so change its parent's right
235 * child link to point to N now.
237 RtlLeftChild(RtlParent(G
)) = N
;
241 /* Now N is on top, so G has become its left child. */
245 /* N is on top, G is its left child, so P is right child. */
246 RtlRightChild(N
) = P
;
249 /* "Finally" case: N doesn't have a grandparent => P is root */
255 /* Case 2 & 4: N is right child of P */
258 /* Case 2: P is the left child of G */
259 if (RtlIsLeftChild(P
))
263 /* Case 4: P is the right child of G */
264 else if (RtlIsRightChild(P
))
268 /* "Finally" case: N doesn't have a grandparent => P is root */
276 /* Return the root entry */
284 PRTL_SPLAY_LINKS NTAPI
285 RtlSubtreePredecessor (IN PRTL_SPLAY_LINKS Links
)
287 PRTL_SPLAY_LINKS Child
;
289 Child
= Links
->RightChild
;
293 if (Child
->LeftChild
== NULL
)
296 /* Get left-most child */
297 while (Child
->LeftChild
!= NULL
)
298 Child
= Child
->LeftChild
;
306 PRTL_SPLAY_LINKS NTAPI
307 RtlSubtreeSuccessor (IN PRTL_SPLAY_LINKS Links
)
309 PRTL_SPLAY_LINKS Child
;
311 Child
= Links
->LeftChild
;
315 if (Child
->RightChild
== NULL
)
318 /* Get right-most child */
319 while (Child
->RightChild
!= NULL
)
320 Child
= Child
->RightChild
;