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 */

9 /* INCLUDES *****************************************************************/

11 #include <rtl.h>

13 #define NDEBUG

14 #include <debug.h>

16 /* FUNCTIONS ***************************************************************/

18 /*

19 * @unimplemented

20 */

21 PRTL_SPLAY_LINKS

22 NTAPI

24 PRTL_SPLAY_LINKS Links

25 )

26 {

27 UNIMPLEMENTED;

29 }

31 /*

32 * @unimplemented

33 */

34 VOID

35 NTAPI

37 PRTL_SPLAY_LINKS Links,

38 PRTL_SPLAY_LINKS *Root

39 )

40 {

41 UNIMPLEMENTED;

42 }

45 /*

46 * @unimplemented

47 */

48 PRTL_SPLAY_LINKS

49 NTAPI

51 PRTL_SPLAY_LINKS Links

52 )

53 {

54 UNIMPLEMENTED;

56 }

58 /*

59 * @unimplemented

60 */

61 PRTL_SPLAY_LINKS

62 NTAPI

64 PRTL_SPLAY_LINKS Links

65 )

66 {

67 UNIMPLEMENTED;

69 }

71 /*

72 * @implemented

73 */

74 PRTL_SPLAY_LINKS

75 NTAPI

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 */

114 /* N is the item we'll be playing with */

117 /* Let the algorithm run until N becomes the root entry */

119 {

120 /* Now get the parent and grand-parent */

124 /* Case 1 & 3: N is left child of P */

126 {

127 /* Case 1: P is the left child of G */

129 {

130 /*

131 * N's right-child becomes P's left child and

132 * P's right-child becomes G's left child.

133 */

137 /*

138 * If they exist, update their parent pointers too,

139 * since they've changed trees.

140 */

144 /*

145 * Now we'll shove N all the way to the top.

146 * Check if G is the root first.

147 */

149 {

150 /* G doesn't have a parent, so N will become the root! */

152 }

153 else

154 {

155 /* G has a parent, so inherit it since we take G's place */

158 /*

159 * Now find out who was referencing G and have it reference

160 * N instead, since we're taking G's place.

161 */

163 {

164 /*

165 * G was a left child, so change its parent's left

166 * child link to point to N now.

167 */

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 */

177 }

178 }

180 /* Now N is on top, so P has become its child. */

184 /* N is on top, P is its child, so G is grandchild. */

187 }

188 /* Case 3: P is the right child of G */

190 {

191 /*

192 * N's left-child becomes G's right child and

193 * N's right-child becomes P's left child.

194 */

198 /*

199 * If they exist, update their parent pointers too,

200 * since they've changed trees.

201 */

205 /*

206 * Now we'll shove N all the way to the top.

207 * Check if G is the root first.

208 */

210 {

211 /* G doesn't have a parent, so N will become the root! */

213 }

214 else

215 {

216 /* G has a parent, so inherit it since we take G's place */

219 /*

220 * Now find out who was referencing G and have it reference

221 * N instead, since we're taking G's place.

222 */

224 {

225 /*

226 * G was a left child, so change its parent's left

227 * child link to point to N now.

228 */

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 */

238 }

239 }

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. */

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 */

255 /* If it exists, update its parent pointer too */

258 /* Now make N the root, no need to worry about references */

261 /* And make P its right child */

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 */

271 {

272 /*

273 * P's left-child becomes G's right child and

274 * N's left-child becomes P's right child.

275 */

279 /*

280 * If they exist, update their parent pointers too,

281 * since they've changed trees.

282 */

286 /*

287 * Now we'll shove N all the way to the top.

288 * Check if G is the root first.

289 */

291 {

292 /* G doesn't have a parent, so N will become the root! */

294 }

295 else

296 {

297 /* G has a parent, so inherit it since we take G's place */

300 /*

301 * Now find out who was referencing G and have it reference

302 * N instead, since we're taking G's place.

303 */

305 {

306 /*

307 * G was a left child, so change its parent's left

308 * child link to point to N now.

309 */

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 */

319 }

320 }

322 /* Now N is on top, so P has become its child. */

326 /* N is on top, P is its child, so G is grandchild. */

329 }

330 /* Case 4: P is the left child of G */

332 {

333 /*

334 * N's left-child becomes G's right child and

335 * N's right-child becomes P's left child.

336 */

340 /*

341 * If they exist, update their parent pointers too,

342 * since they've changed trees.

343 */

347 /*

348 * Now we'll shove N all the way to the top.

349 * Check if G is the root first.

350 */

352 {

353 /* G doesn't have a parent, so N will become the root! */

355 }

356 else

357 {

358 /* G has a parent, so inherit it since we take G's place */

361 /*

362 * Now find out who was referencing G and have it reference

363 * N instead, since we're taking G's place.

364 */

366 {

367 /*

368 * G was a left child, so change its parent's left

369 * child link to point to N now.

370 */

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 */

380 }

381 }

383 /* Now N is on top, so P has become its left child. */

387 /* N is on top, P is its left child, so G is right child. */

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 */

397 /* If it exists, update its parent pointer too */

400 /* Now make N the root, no need to worry about references */

403 /* And make P its left child */

406 }

407 }

408 }

410 /* Return the root entry */

412 }

415 /*

416 * @implemented

417 */

418 PRTL_SPLAY_LINKS NTAPI

420 {

421 PRTL_SPLAY_LINKS Child;

430 /* Get left-most child */

435 }

437 /*

438 * @implemented

439 */

440 PRTL_SPLAY_LINKS NTAPI

442 {

443 PRTL_SPLAY_LINKS Child;

452 /* Get right-most child */

457 }

459 /* EOF */