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
6 * PROGRAMMER: Alex Ionescu (alex@relsoft.net)
9 /* INCLUDES *****************************************************************/
16 /* FUNCTIONS ***************************************************************/
23 RtlDelete(PRTL_SPLAY_LINKS Links
)
25 PRTL_SPLAY_LINKS N
, P
, C
, SP
;
28 /* Check if we have two children */
29 if ((RtlLeftChild(N
)) && (RtlRightChild(N
)))
31 /* Get the predecessor */
32 SP
= RtlSubtreePredecessor(N
);
34 /* Swap it with N, this will guarantee that N will have only a child */
35 //SwapSplayLinks(SP, N);
36 DPRINT1("UNIMPLEMENTED!\n");
39 /* Check if we have no children */
40 if (!(RtlLeftChild(N
)) && !(RtlRightChild(N
)))
42 /* If we are also the root, then the tree is gone */
48 /* Find out who is referencing us and delete the reference */
49 if (RtlIsLeftChild(N
))
51 /* N was a left child, so erase its parent's left child link */
52 RtlLeftChild(RtlParent(N
)) = NULL
;
56 /* N was a right child, so erase its parent's right child link */
57 RtlRightChild(RtlParent(N
)) = NULL
;
60 /* And finally splay the parent */
64 /* If we got here, we have a child (not two: we swapped above!) */
67 /* We have a left child, so get it */
72 /* We have a right child, get him instead */
76 /* Check if we are the root entry */
79 /* Our child is now root, return him */
84 /* Find out who is referencing us and link to our child instead */
85 if (RtlIsLeftChild(N
))
87 /* N was a left child, so set its parent's left child as our child */
88 RtlLeftChild(RtlParent(N
)) = C
;
92 /* N was a right child, so set its parent's right child as our child */
93 RtlRightChild(RtlParent(N
)) = C
;
96 /* Finally, inherit our parent and splay the parent */
97 C
->Parent
= N
->Parent
;
98 return RtlSplay(RtlParent(C
));
107 PRTL_SPLAY_LINKS Links
,
108 PRTL_SPLAY_LINKS
*Root
119 RtlRealPredecessor(PRTL_SPLAY_LINKS Links
)
121 PRTL_SPLAY_LINKS Child
;
123 /* Get the left child */
124 Child
= RtlLeftChild(Links
);
127 /* Get right-most child */
128 while (RtlRightChild(Child
)) Child
= RtlRightChild(Child
);
132 /* We don't have a left child, keep looping until we find our parent */
134 while (RtlIsLeftChild(Child
)) Child
= RtlParent(Child
);
136 /* The parent should be a right child, return the real predecessor */
137 if (RtlIsRightChild(Child
)) return RtlParent(Child
);
139 /* The parent isn't a right child, so no real precessor for us */
148 RtlRealSuccessor(PRTL_SPLAY_LINKS Links
)
150 PRTL_SPLAY_LINKS Child
;
152 /* Get the right child */
153 Child
= RtlRightChild(Links
);
156 /* Get left-most child */
157 while (RtlLeftChild(Child
)) Child
= RtlLeftChild(Child
);
161 /* We don't have a right child, keep looping until we find our parent */
163 while (RtlIsRightChild(Child
)) Child
= RtlParent(Child
);
165 /* The parent should be a left child, return the real successor */
166 if (RtlIsLeftChild(Child
)) return RtlParent(Child
);
168 /* The parent isn't a right child, so no real successor for us */
177 RtlSplay(PRTL_SPLAY_LINKS Links
)
180 * Implementation Notes (http://en.wikipedia.org/wiki/Splay_tree):
182 * To do a splay, we carry out a sequence of rotations,
183 * each of which moves the target node N closer to the root.
185 * Each particular step depends on only two factors:
186 * - Whether N is the left or right child of its parent node, P,
187 * - Whether P is the left or right child of its parent, G (for grandparent node).
189 * Thus, there are four cases:
190 * - Case 1: N is the left child of P and P is the left child of G.
191 * In this case we perform a double right rotation, so that
192 * P becomes N's right child, and G becomes P's right child.
194 * - Case 2: N is the right child of P and P is the right child of G.
195 * In this case we perform a double left rotation, so that
196 * P becomes N's left child, and G becomes P's left child.
198 * - Case 3: N is the left child of P and P is the right child of G.
199 * In this case we perform a rotation so that
200 * G becomes N's left child, and P becomes N's right child.
202 * - Case 4: N is the right child of P and P is the left child of G.
203 * In this case we perform a rotation so that
204 * P becomes N's left child, and G becomes N's right child.
206 * Finally, if N doesn't have a grandparent node, we simply perform a
207 * left or right rotation to move it to the root.
209 * By performing a splay on the node of interest after every operation,
210 * we keep recently accessed nodes near the root and keep the tree
211 * roughly balanced, so that we achieve the desired amortized time bounds.
213 PRTL_SPLAY_LINKS N
, P
, G
;
215 /* N is the item we'll be playing with */
218 /* Let the algorithm run until N becomes the root entry */
219 while (!RtlIsRoot(N
))
221 /* Now get the parent and grand-parent */
225 /* Case 1 & 3: N is left child of P */
226 if (RtlIsLeftChild(N
))
228 /* Case 1: P is the left child of G */
229 if (RtlIsLeftChild(P
))
232 * N's right-child becomes P's left child and
233 * P's right-child becomes G's left child.
235 RtlLeftChild(P
) = RtlRightChild(N
);
236 RtlLeftChild(G
) = RtlRightChild(P
);
239 * If they exist, update their parent pointers too,
240 * since they've changed trees.
242 if (RtlLeftChild(P
)) RtlParent(RtlLeftChild(P
)) = P
;
243 if (RtlLeftChild(G
)) RtlParent(RtlLeftChild(G
)) = G
;
246 * Now we'll shove N all the way to the top.
247 * Check if G is the root first.
251 /* G doesn't have a parent, so N will become the root! */
256 /* G has a parent, so inherit it since we take G's place */
257 RtlParent(N
) = RtlParent(G
);
260 * Now find out who was referencing G and have it reference
261 * N instead, since we're taking G's place.
263 if (RtlIsLeftChild(G
))
266 * G was a left child, so change its parent's left
267 * child link to point to N now.
269 RtlLeftChild(RtlParent(G
)) = N
;
274 * G was a right child, so change its parent's right
275 * child link to point to N now.
277 RtlRightChild(RtlParent(G
)) = N
;
281 /* Now N is on top, so P has become its child. */
282 RtlRightChild(N
) = P
;
285 /* N is on top, P is its child, so G is grandchild. */
286 RtlRightChild(P
) = G
;
289 /* Case 3: P is the right child of G */
290 else if (RtlIsRightChild(P
))
293 * N's left-child becomes G's right child and
294 * N's right-child becomes P's left child.
296 RtlRightChild(G
) = RtlLeftChild(N
);
297 RtlLeftChild(P
) = RtlRightChild(N
);
300 * If they exist, update their parent pointers too,
301 * since they've changed trees.
303 if (RtlRightChild(G
)) RtlParent(RtlRightChild(G
)) = G
;
304 if (RtlLeftChild(P
)) RtlParent(RtlLeftChild(P
)) = P
;
307 * Now we'll shove N all the way to the top.
308 * Check if G is the root first.
312 /* G doesn't have a parent, so N will become the root! */
317 /* G has a parent, so inherit it since we take G's place */
318 RtlParent(N
) = RtlParent(G
);
321 * Now find out who was referencing G and have it reference
322 * N instead, since we're taking G's place.
324 if (RtlIsLeftChild(G
))
327 * G was a left child, so change its parent's left
328 * child link to point to N now.
330 RtlLeftChild(RtlParent(G
)) = N
;
335 * G was a right child, so change its parent's right
336 * child link to point to N now.
338 RtlRightChild(RtlParent(G
)) = N
;
342 /* Now N is on top, so G has become its left child. */
346 /* N is on top, G is its left child, so P is right child. */
347 RtlRightChild(N
) = P
;
350 /* "Finally" case: N doesn't have a grandparent => P is root */
353 /* P's left-child becomes N's right child */
354 RtlLeftChild(P
) = RtlRightChild(N
);
356 /* If it exists, update its parent pointer too */
357 if (RtlLeftChild(P
)) RtlParent(RtlLeftChild(P
)) = P
;
359 /* Now make N the root, no need to worry about references */
362 /* And make P its right child */
367 /* Case 2 & 4: N is right child of P */
370 /* Case 2: P is the right child of G */
371 if (RtlIsRightChild(P
))
374 * P's left-child becomes G's right child and
375 * N's left-child becomes P's right child.
377 RtlRightChild(G
) = RtlLeftChild(P
);
378 RtlRightChild(P
) = RtlLeftChild(N
);
381 * If they exist, update their parent pointers too,
382 * since they've changed trees.
384 if (RtlRightChild(G
)) RtlParent(RtlRightChild(G
)) = G
;
385 if (RtlRightChild(P
)) RtlParent(RtlRightChild(P
)) = P
;
388 * Now we'll shove N all the way to the top.
389 * Check if G is the root first.
393 /* G doesn't have a parent, so N will become the root! */
398 /* G has a parent, so inherit it since we take G's place */
399 RtlParent(N
) = RtlParent(G
);
402 * Now find out who was referencing G and have it reference
403 * N instead, since we're taking G's place.
405 if (RtlIsLeftChild(G
))
408 * G was a left child, so change its parent's left
409 * child link to point to N now.
411 RtlLeftChild(RtlParent(G
)) = N
;
416 * G was a right child, so change its parent's right
417 * child link to point to N now.
419 RtlRightChild(RtlParent(G
)) = N
;
423 /* Now N is on top, so P has become its child. */
427 /* N is on top, P is its child, so G is grandchild. */
431 /* Case 4: P is the left child of G */
432 else if (RtlIsLeftChild(P
))
435 * N's left-child becomes G's right child and
436 * N's right-child becomes P's left child.
438 RtlRightChild(P
) = RtlLeftChild(N
);
439 RtlLeftChild(G
) = RtlRightChild(N
);
442 * If they exist, update their parent pointers too,
443 * since they've changed trees.
445 if (RtlRightChild(P
)) RtlParent(RtlRightChild(P
)) = P
;
446 if (RtlLeftChild(G
)) RtlParent(RtlLeftChild(G
)) = G
;
449 * Now we'll shove N all the way to the top.
450 * Check if G is the root first.
454 /* G doesn't have a parent, so N will become the root! */
459 /* G has a parent, so inherit it since we take G's place */
460 RtlParent(N
) = RtlParent(G
);
463 * Now find out who was referencing G and have it reference
464 * N instead, since we're taking G's place.
466 if (RtlIsLeftChild(G
))
469 * G was a left child, so change its parent's left
470 * child link to point to N now.
472 RtlLeftChild(RtlParent(G
)) = N
;
477 * G was a right child, so change its parent's right
478 * child link to point to N now.
480 RtlRightChild(RtlParent(G
)) = N
;
484 /* Now N is on top, so P has become its left child. */
488 /* N is on top, P is its left child, so G is right child. */
489 RtlRightChild(N
) = G
;
492 /* "Finally" case: N doesn't have a grandparent => P is root */
495 /* P's right-child becomes N's left child */
496 RtlRightChild(P
) = RtlLeftChild(N
);
498 /* If it exists, update its parent pointer too */
499 if (RtlRightChild(P
)) RtlParent(RtlRightChild(P
)) = P
;
501 /* Now make N the root, no need to worry about references */
504 /* And make P its left child */
511 /* Return the root entry */
520 RtlSubtreePredecessor(IN PRTL_SPLAY_LINKS Links
)
522 PRTL_SPLAY_LINKS Child
;
524 /* Get the left child */
525 Child
= RtlLeftChild(Links
);
526 if (!Child
) return NULL
;
528 /* Get right-most child */
529 while (RtlRightChild(Child
)) Child
= RtlRightChild(Child
);
540 RtlSubtreeSuccessor(IN PRTL_SPLAY_LINKS Links
)
542 PRTL_SPLAY_LINKS Child
;
544 /* Get the right child */
545 Child
= RtlRightChild(Links
);
546 if (!Child
) return NULL
;
548 /* Get left-most child */
549 while (RtlLeftChild(Child
)) Child
= RtlLeftChild(Child
);