- Finish implementing RtlSplayTree
[reactos.git] / reactos / lib / rtl / splaytree.c
1 /*
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:
7 */
8
9 /* INCLUDES *****************************************************************/
10
11 #include <rtl.h>
12
13 #define NDEBUG
14 #include <debug.h>
15
16 /* FUNCTIONS ***************************************************************/
17
18 /*
19 * @unimplemented
20 */
21 PRTL_SPLAY_LINKS
22 NTAPI
23 RtlDelete (
24 PRTL_SPLAY_LINKS Links
25 )
26 {
27 UNIMPLEMENTED;
28 return 0;
29 }
30
31 /*
32 * @unimplemented
33 */
34 VOID
35 NTAPI
36 RtlDeleteNoSplay (
37 PRTL_SPLAY_LINKS Links,
38 PRTL_SPLAY_LINKS *Root
39 )
40 {
41 UNIMPLEMENTED;
42 }
43
44
45 /*
46 * @unimplemented
47 */
48 PRTL_SPLAY_LINKS
49 NTAPI
50 RtlRealPredecessor (
51 PRTL_SPLAY_LINKS Links
52 )
53 {
54 UNIMPLEMENTED;
55 return 0;
56 }
57
58 /*
59 * @unimplemented
60 */
61 PRTL_SPLAY_LINKS
62 NTAPI
63 RtlRealSuccessor (
64 PRTL_SPLAY_LINKS Links
65 )
66 {
67 UNIMPLEMENTED;
68 return 0;
69 }
70
71 /*
72 * @implemented
73 */
74 PRTL_SPLAY_LINKS
75 NTAPI
76 RtlSplay(PRTL_SPLAY_LINKS Links)
77 {
78 /*
79 * Implementation Notes (http://en.wikipedia.org/wiki/Splay_tree):
80 *
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.
83 *
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).
87 *
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.
92 *
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.
96 *
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.
100 *
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.
104 *
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.
107 *
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.
111 */
112 PRTL_SPLAY_LINKS N, P, G;
113
114 /* N is the item we'll be playing with */
115 N = Links;
116
117 /* Let the algorithm run until N becomes the root entry */
118 while (!RtlIsRoot(N))
119 {
120 /* Now get the parent and grand-parent */
121 P = RtlParent(N);
122 G = RtlParent(P);
123
124 /* Case 1 & 3: N is left child of P */
125 if (RtlIsLeftChild(N))
126 {
127 /* Case 1: P is the left child of G */
128 if (RtlIsLeftChild(P))
129 {
130 /*
131 * N's right-child becomes P's left child and
132 * P's right-child becomes G's left child.
133 */
134 RtlLeftChild(P) = RtlRightChild(N);
135 RtlLeftChild(G) = RtlRightChild(P);
136
137 /*
138 * If they exist, update their parent pointers too,
139 * since they've changed trees.
140 */
141 if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P;
142 if (RtlLeftChild(G)) RtlParent(RtlLeftChild(G)) = G;
143
144 /*
145 * Now we'll shove N all the way to the top.
146 * Check if G is the root first.
147 */
148 if (RtlIsRoot(G))
149 {
150 /* G doesn't have a parent, so N will become the root! */
151 RtlParent(N) = N;
152 }
153 else
154 {
155 /* G has a parent, so inherit it since we take G's place */
156 RtlParent(N) = RtlParent(G);
157
158 /*
159 * Now find out who was referencing G and have it reference
160 * N instead, since we're taking G's place.
161 */
162 if (RtlIsLeftChild(G))
163 {
164 /*
165 * G was a left child, so change its parent's left
166 * child link to point to N now.
167 */
168 RtlLeftChild(RtlParent(G)) = N;
169 }
170 else
171 {
172 /*
173 * G was a right child, so change its parent's right
174 * child link to point to N now.
175 */
176 RtlLeftChild(RtlParent(G)) = N;
177 }
178 }
179
180 /* Now N is on top, so P has become its child. */
181 RtlRightChild(N) = P;
182 RtlParent(P) = N;
183
184 /* N is on top, P is its child, so G is grandchild. */
185 RtlRightChild(P) = G;
186 RtlParent(G) = P;
187 }
188 /* Case 3: P is the right child of G */
189 else if (RtlIsRightChild(P))
190 {
191 /*
192 * N's left-child becomes G's right child and
193 * N's right-child becomes P's left child.
194 */
195 RtlRightChild(G) = RtlLeftChild(N);
196 RtlLeftChild(P) = RtlRightChild(N);
197
198 /*
199 * If they exist, update their parent pointers too,
200 * since they've changed trees.
201 */
202 if (RtlRightChild(G)) RtlParent(RtlRightChild(G)) = G;
203 if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P;
204
205 /*
206 * Now we'll shove N all the way to the top.
207 * Check if G is the root first.
208 */
209 if (RtlIsRoot(G))
210 {
211 /* G doesn't have a parent, so N will become the root! */
212 RtlParent(N) = N;
213 }
214 else
215 {
216 /* G has a parent, so inherit it since we take G's place */
217 RtlParent(N) = RtlParent(G);
218
219 /*
220 * Now find out who was referencing G and have it reference
221 * N instead, since we're taking G's place.
222 */
223 if (RtlIsLeftChild(G))
224 {
225 /*
226 * G was a left child, so change its parent's left
227 * child link to point to N now.
228 */
229 RtlLeftChild(RtlParent(G)) = N;
230 }
231 else
232 {
233 /*
234 * G was a right child, so change its parent's right
235 * child link to point to N now.
236 */
237 RtlLeftChild(RtlParent(G)) = N;
238 }
239 }
240
241 /* Now N is on top, so G has become its left child. */
242 RtlLeftChild(N) = G;
243 RtlParent(G) = N;
244
245 /* N is on top, G is its left child, so P is right child. */
246 RtlRightChild(N) = P;
247 RtlParent(P) = N;
248 }
249 /* "Finally" case: N doesn't have a grandparent => P is root */
250 else
251 {
252 /* P's left-child becomes N's right child */
253 RtlLeftChild(P) = RtlRightChild(N);
254
255 /* If it exists, update its parent pointer too */
256 if (RtlLeftChild(P)) RtlParent(RtlLeftChild(P)) = P;
257
258 /* Now make N the root, no need to worry about references */
259 N->Parent = N;
260
261 /* And make P its right child */
262 N->RightChild = P;
263 P->Parent = N;
264 }
265 }
266 /* Case 2 & 4: N is right child of P */
267 else
268 {
269 /* Case 2: P is the right child of G */
270 if (RtlIsRightChild(P))
271 {
272 /*
273 * P's left-child becomes G's right child and
274 * N's left-child becomes P's right child.
275 */
276 RtlRightChild(G) = RtlLeftChild(P);
277 RtlRightChild(P) = RtlLeftChild(N);
278
279 /*
280 * If they exist, update their parent pointers too,
281 * since they've changed trees.
282 */
283 if (RtlRightChild(G)) RtlParent(RtlRightChild(G)) = G;
284 if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P;
285
286 /*
287 * Now we'll shove N all the way to the top.
288 * Check if G is the root first.
289 */
290 if (RtlIsRoot(G))
291 {
292 /* G doesn't have a parent, so N will become the root! */
293 RtlParent(N) = N;
294 }
295 else
296 {
297 /* G has a parent, so inherit it since we take G's place */
298 RtlParent(N) = RtlParent(G);
299
300 /*
301 * Now find out who was referencing G and have it reference
302 * N instead, since we're taking G's place.
303 */
304 if (RtlIsLeftChild(G))
305 {
306 /*
307 * G was a left child, so change its parent's left
308 * child link to point to N now.
309 */
310 RtlLeftChild(RtlParent(G)) = N;
311 }
312 else
313 {
314 /*
315 * G was a right child, so change its parent's right
316 * child link to point to N now.
317 */
318 RtlLeftChild(RtlParent(G)) = N;
319 }
320 }
321
322 /* Now N is on top, so P has become its child. */
323 RtlLeftChild(N) = P;
324 RtlParent(P) = N;
325
326 /* N is on top, P is its child, so G is grandchild. */
327 RtlLeftChild(P) = G;
328 RtlParent(G) = P;
329 }
330 /* Case 4: P is the left child of G */
331 else if (RtlIsLeftChild(P))
332 {
333 /*
334 * N's left-child becomes G's right child and
335 * N's right-child becomes P's left child.
336 */
337 RtlRightChild(P) = RtlLeftChild(N);
338 RtlLeftChild(G) = RtlRightChild(N);
339
340 /*
341 * If they exist, update their parent pointers too,
342 * since they've changed trees.
343 */
344 if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P;
345 if (RtlLeftChild(G)) RtlParent(RtlLeftChild(G)) = G;
346
347 /*
348 * Now we'll shove N all the way to the top.
349 * Check if G is the root first.
350 */
351 if (RtlIsRoot(G))
352 {
353 /* G doesn't have a parent, so N will become the root! */
354 RtlParent(N) = N;
355 }
356 else
357 {
358 /* G has a parent, so inherit it since we take G's place */
359 RtlParent(N) = RtlParent(G);
360
361 /*
362 * Now find out who was referencing G and have it reference
363 * N instead, since we're taking G's place.
364 */
365 if (RtlIsLeftChild(G))
366 {
367 /*
368 * G was a left child, so change its parent's left
369 * child link to point to N now.
370 */
371 RtlLeftChild(RtlParent(G)) = N;
372 }
373 else
374 {
375 /*
376 * G was a right child, so change its parent's right
377 * child link to point to N now.
378 */
379 RtlLeftChild(RtlParent(G)) = N;
380 }
381 }
382
383 /* Now N is on top, so P has become its left child. */
384 RtlLeftChild(N) = P;
385 RtlParent(G) = N;
386
387 /* N is on top, P is its left child, so G is right child. */
388 RtlRightChild(N) = G;
389 RtlParent(P) = N;
390 }
391 /* "Finally" case: N doesn't have a grandparent => P is root */
392 else
393 {
394 /* P's right-child becomes N's left child */
395 RtlRightChild(P) = RtlLeftChild(N);
396
397 /* If it exists, update its parent pointer too */
398 if (RtlRightChild(P)) RtlParent(RtlRightChild(P)) = P;
399
400 /* Now make N the root, no need to worry about references */
401 N->Parent = N;
402
403 /* And make P its left child */
404 N->LeftChild = P;
405 P->Parent = N;
406 }
407 }
408 }
409
410 /* Return the root entry */
411 return N;
412 }
413
414
415 /*
416 * @implemented
417 */
418 PRTL_SPLAY_LINKS NTAPI
419 RtlSubtreePredecessor (IN PRTL_SPLAY_LINKS Links)
420 {
421 PRTL_SPLAY_LINKS Child;
422
423 Child = Links->RightChild;
424 if (Child == NULL)
425 return NULL;
426
427 if (Child->LeftChild == NULL)
428 return Child;
429
430 /* Get left-most child */
431 while (Child->LeftChild != NULL)
432 Child = Child->LeftChild;
433
434 return Child;
435 }
436
437 /*
438 * @implemented
439 */
440 PRTL_SPLAY_LINKS NTAPI
441 RtlSubtreeSuccessor (IN PRTL_SPLAY_LINKS Links)
442 {
443 PRTL_SPLAY_LINKS Child;
444
445 Child = Links->LeftChild;
446 if (Child == NULL)
447 return NULL;
448
449 if (Child->RightChild == NULL)
450 return Child;
451
452 /* Get right-most child */
453 while (Child->RightChild != NULL)
454 Child = Child->RightChild;
455
456 return Child;
457 }
458
459 /* EOF */