ec3a11acd278a1d02202f1ab846cc10f36ce1b7a
[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 * @unimplemented
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 }
132 /* Case 3: P is the right child of G */
133 else if (RtlIsRightChild(P))
134 {
135
136 }
137 /* "Finally" case: N doesn't have a grandparent => P is root */
138 else
139 {
140
141 }
142 }
143 /* Case 2 & 4: N is right child of P */
144 else
145 {
146 /* Case 2: P is the left child of G */
147 if (RtlIsLeftChild(P))
148 {
149
150 }
151 /* Case 4: P is the right child of G */
152 else if (RtlIsRightChild(P))
153 {
154
155 }
156 /* "Finally" case: N doesn't have a grandparent => P is root */
157 else
158 {
159
160 }
161 }
162 }
163
164 /* Return the root entry */
165 return N;
166 }
167
168
169 /*
170 * @implemented
171 */
172 PRTL_SPLAY_LINKS NTAPI
173 RtlSubtreePredecessor (IN PRTL_SPLAY_LINKS Links)
174 {
175 PRTL_SPLAY_LINKS Child;
176
177 Child = Links->RightChild;
178 if (Child == NULL)
179 return NULL;
180
181 if (Child->LeftChild == NULL)
182 return Child;
183
184 /* Get left-most child */
185 while (Child->LeftChild != NULL)
186 Child = Child->LeftChild;
187
188 return Child;
189 }
190
191 /*
192 * @implemented
193 */
194 PRTL_SPLAY_LINKS NTAPI
195 RtlSubtreeSuccessor (IN PRTL_SPLAY_LINKS Links)
196 {
197 PRTL_SPLAY_LINKS Child;
198
199 Child = Links->LeftChild;
200 if (Child == NULL)
201 return NULL;
202
203 if (Child->RightChild == NULL)
204 return Child;
205
206 /* Get right-most child */
207 while (Child->RightChild != NULL)
208 Child = Child->RightChild;
209
210 return Child;
211 }
212
213 /* EOF */