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 * @unimplemented

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 {

253 }

254 }

255 /* Case 2 & 4: N is right child of P */

256 else

257 {

258 /* Case 2: P is the right child of G */

260 {

261 /*

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

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

264 */

268 /*

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

270 * since they've changed trees.

271 */

275 /*

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

277 * Check if G is the root first.

278 */

280 {

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

283 }

284 else

285 {

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

289 /*

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

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

292 */

294 {

295 /*

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

297 * child link to point to N now.

298 */

300 }

301 else

302 {

303 /*

304 * G was a right child, so change its parent's right

305 * child link to point to N now.

306 */

308 }

309 }

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

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

318 }

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

321 {

322 /*

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

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

325 */

329 /*

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

331 * since they've changed trees.

332 */

336 /*

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

338 * Check if G is the root first.

339 */

341 {

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

344 }

345 else

346 {

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

350 /*

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

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

353 */

355 {

356 /*

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

358 * child link to point to N now.

359 */

361 }

362 else

363 {

364 /*

365 * G was a right child, so change its parent's right

366 * child link to point to N now.

367 */

369 }

370 }

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

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

379 }

380 /* "Finally" case: N doesn't have a grandparent => P is root */

381 else

382 {

384 }

385 }

386 }

388 /* Return the root entry */

390 }

393 /*

394 * @implemented

395 */

396 PRTL_SPLAY_LINKS NTAPI

398 {

399 PRTL_SPLAY_LINKS Child;

408 /* Get left-most child */

413 }

415 /*

416 * @implemented

417 */

418 PRTL_SPLAY_LINKS NTAPI

420 {

421 PRTL_SPLAY_LINKS Child;

430 /* Get right-most child */

435 }

437 /* EOF */