ReactOS  0.4.14-dev-1256-g2125fec
splaytree.c
Go to the documentation of this file.
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: Alex Ionescu (alex@relsoft.net)
7  */
8 
9 /* INCLUDES *****************************************************************/
10 
11 #include <rtl.h>
12 
13 #define NDEBUG
14 #include <debug.h>
15 
16 //#define VERIFY_SWAP_SPLAY_LINKS
17 
18 /* FUNCTIONS ***************************************************************/
19 
20 static
21 VOID
23 {
24  if (RtlLeftChild(Links))
25  {
26  RtlInsertAsLeftChild(Links, RtlLeftChild(Links));
27  }
28 
29  if (RtlRightChild(Links))
30  {
31  RtlInsertAsRightChild(Links, RtlRightChild(Links));
32  }
33 
34  if (!Root)
35  {
36  if (LeftChild)
37  {
38  RtlInsertAsLeftChild(RtlParent(Links), Links);
39  }
40  else
41  {
42  RtlInsertAsRightChild(RtlParent(Links), Links);
43  }
44  }
45 }
46 
47 /*
48 
49 Given the tree:
50  D
51  B F
52 A C E G
53 
54 Swap(Q,S):
55 
56 Q S Q.P Q.L Q.R S.P S.L S.R
57 A C S.P S.L S.R Q.P Q.L Q.R
58 B A S S.L S.R Q.P Q Q.R
59 B C S S.L S.R Q.P Q.L Q
60 D A S.P S.L S.R S Q.L Q.R
61 D B S S.L S.R S Q Q.R
62 D F S S.L S.R S Q.L Q
63 
64 When Q is the immediate parent of S,
65  Set Q's parent to S, and the proper child ptr of S to Q
66 When Q is the root,
67  Set S's parent to S
68 
69 */
70 
71 static
72 VOID
74  PRTL_SPLAY_LINKS LinkB)
75 {
76  if (RtlParent(LinkA) == LinkB || RtlIsRoot(LinkB))
77  {
78  PRTL_SPLAY_LINKS Tmp = LinkA;
79  LinkA = LinkB;
80  LinkB = Tmp;
81  }
82 
83  {
84  RTL_SPLAY_LINKS Ta = *LinkA, Tb = *LinkB;
85  BOOLEAN RootA = RtlIsRoot(LinkA),
86  LeftA = RtlIsLeftChild(LinkA),
87  LeftB = RtlIsLeftChild(LinkB);
88 
89  *LinkB = Ta; *LinkA = Tb;
90 
91  // A was parent of B is a special case: A->Parent is now B
92  if (RtlParent(&Tb) == LinkA)
93  {
94  if (!RootA)
95  {
96  if (LeftA)
97  {
98  RtlInsertAsLeftChild(RtlParent(&Ta), LinkB);
99  }
100  else
101  {
102  RtlInsertAsRightChild(RtlParent(&Ta), LinkB);
103  }
104  }
105 
106  if (LeftB)
107  {
108  RtlInsertAsLeftChild(LinkB, LinkA);
109  }
110  else
111  {
112  RtlInsertAsRightChild(LinkB, LinkA);
113  }
114  }
115 
116  FixupChildLinks(LinkA, FALSE, LeftB);
117  FixupChildLinks(LinkB, RootA, LeftA);
118 
119  // A was root is a special case: B->Parent is now B
120  if (RootA)
121  RtlParent(LinkB) = LinkB;
122 
123 #ifdef VERIFY_SWAP_SPLAY_LINKS
124  // Verify the distinct cases of node swap
125  if (RootA)
126  {
127  if (RtlParent(&Tb) == LinkA)
128  {
129  // LinkA = D, LinkB = B
130  // D B S S.L S.R S Q Q.R
131  ASSERT(RtlParent(LinkA) == LinkB);
132  ASSERT(RtlLeftChild(LinkA) == RtlLeftChild(&Tb));
133  ASSERT(RtlRightChild(LinkA) == RtlRightChild(&Tb));
134  ASSERT(RtlParent(LinkB) == LinkB);
135  ASSERT(RtlLeftChild(LinkB) == (LeftB ? LinkA : RtlLeftChild(&Ta)));
136  ASSERT(RtlRightChild(LinkB) == (LeftB ? RtlRightChild(&Ta) : LinkA));
137  }
138  else
139  {
140  // LinkA = D, LinkB = A
141  // D A S.P S.L S.R S Q.L Q.R
142  ASSERT(RtlParent(LinkA) == RtlParent(&Tb));
143  ASSERT(RtlLeftChild(LinkA) == RtlLeftChild(&Tb));
144  ASSERT(RtlRightChild(LinkA) == RtlRightChild(&Tb));
145  ASSERT(RtlParent(LinkB) == LinkB);
146  ASSERT(RtlLeftChild(LinkB) == RtlLeftChild(&Ta));
147  ASSERT(RtlRightChild(LinkB) == RtlRightChild(&Ta));
148  }
149  }
150  else
151  {
152  if (RtlParent(&Tb) == LinkA)
153  {
154  // LinkA = B, LinkB = A
155  // B A S S.L S.R Q.P Q Q.R
156  ASSERT(RtlParent(LinkA) == LinkB);
157  ASSERT(RtlLeftChild(LinkA) == RtlLeftChild(&Tb));
158  ASSERT(RtlRightChild(LinkA) == RtlRightChild(&Tb));
159  ASSERT(RtlParent(LinkB) == RtlParent(&Ta));
160  ASSERT(RtlLeftChild(LinkB) == (LeftB ? LinkA : RtlLeftChild(&Ta)));
161  ASSERT(RtlRightChild(LinkB) == (LeftB ? RtlRightChild(&Ta) : LinkA));
162  }
163  else
164  {
165  // LinkA = A, LinkB = C
166  // A C S.P S.L S.R Q.P Q.L Q.R
167  ASSERT(!memcmp(LinkA, &Tb, sizeof(Tb)));
168  ASSERT(!memcmp(LinkB, &Ta, sizeof(Ta)));
169  }
170  }
171 #endif
172  }
173 }
174 
175 /*
176  * @implemented
177  */
179 NTAPI
181 {
182  PRTL_SPLAY_LINKS N, P, C, SP;
183  N = Links;
184 
185  /* Check if we have two children */
186  if (RtlLeftChild(N) && RtlRightChild(N))
187  {
188  /* Get the predecessor */
189  SP = RtlSubtreePredecessor(N);
190 
191  /* Swap it with N, this will guarantee that N will only have a child */
192  SwapSplayLinks(SP, N);
193  }
194 
195  /* Check if we have no children */
196  if (!RtlLeftChild(N) && !RtlRightChild(N))
197  {
198  /* If we are also the root, then the tree is gone */
199  if (RtlIsRoot(N)) return NULL;
200 
201  /* Get our parent */
202  P = RtlParent(N);
203 
204  /* Find out who is referencing us and delete the reference */
205  if (RtlIsLeftChild(N))
206  {
207  /* N was a left child, so erase its parent's left child link */
208  RtlLeftChild(P) = NULL;
209  }
210  else
211  {
212  /* N was a right child, so erase its parent's right child link */
213  RtlRightChild(P) = NULL;
214  }
215 
216  /* And finally splay the parent */
217  return RtlSplay(P);
218  }
219 
220  /* If we got here, we have a child (not two: we swapped above!) */
221  if (RtlLeftChild(N))
222  {
223  /* We have a left child, so get it */
224  C = RtlLeftChild(N);
225  }
226  else
227  {
228  /* We have a right child, get it instead */
229  C = RtlRightChild(N);
230  }
231 
232  /* Check if we are the root entry */
233  if (RtlIsRoot(N))
234  {
235  /* Our child is now root, return it */
236  RtlParent(C) = C;
237  return C;
238  }
239 
240  /* Get our parent */
241  P = RtlParent(N);
242 
243  /* Find out who is referencing us and link to our child instead */
244  if (RtlIsLeftChild(N))
245  {
246  /* N was a left child, so set its parent's left child as our child */
247  RtlLeftChild(P) = C;
248  }
249  else
250  {
251  /* N was a right child, so set its parent's right child as our child */
252  RtlRightChild(P) = C;
253  }
254 
255  /* Finally, inherit our parent and splay the parent */
256  RtlParent(C) = P;
257  return RtlSplay(P);
258 }
259 
260 /*
261  * @implemented
262  */
263 VOID
264 NTAPI
267 {
268  PRTL_SPLAY_LINKS N, P, C, SP;
269  N = Links;
270 
271  /* Check if we have two children */
272  if (RtlLeftChild(N) && RtlRightChild(N))
273  {
274  /* Get the predecessor */
275  SP = RtlSubtreePredecessor(N);
276 
277  /* If we are the root, the new root will be our predecessor after swapping */
278  if (RtlIsRoot(N)) *Root = SP;
279 
280  /* Swap the predecessor with N, this will guarantee that N will only have a child */
281  SwapSplayLinks(SP, N);
282  }
283 
284  /* Check if we have no children */
285  if (!RtlLeftChild(N) && !RtlRightChild(N))
286  {
287  /* If we are also the root, then the tree is gone */
288  if (RtlIsRoot(N))
289  {
290  *Root = NULL;
291  return;
292  }
293 
294  /* Get our parent */
295  P = RtlParent(N);
296 
297  /* Find out who is referencing us and delete the reference */
298  if (RtlIsLeftChild(N))
299  {
300  /* N was a left child, so erase its parent's left child link */
301  RtlLeftChild(P) = NULL;
302  }
303  else
304  {
305  /* N was a right child, so erase its parent's right child link */
306  RtlRightChild(P) = NULL;
307  }
308 
309  /* We are done */
310  return;
311  }
312 
313  /* If we got here, we have a child (not two: we swapped above!) */
314  if (RtlLeftChild(N))
315  {
316  /* We have a left child, so get it */
317  C = RtlLeftChild(N);
318  }
319  else
320  {
321  /* We have a right child, get it instead */
322  C = RtlRightChild(N);
323  }
324 
325  /* Check if we are the root entry */
326  if (RtlIsRoot(N))
327  {
328  /* Our child is now root, return it */
329  RtlParent(C) = C;
330  *Root = C;
331  return;
332  }
333 
334  /* Get our parent */
335  P = RtlParent(N);
336 
337  /* Find out who is referencing us and link to our child instead */
338  if (RtlIsLeftChild(N))
339  {
340  /* N was a left child, so set its parent's left child as our child */
341  RtlLeftChild(P) = C;
342  }
343  else
344  {
345  /* N was a right child, so set its parent's right child as our child */
346  RtlRightChild(P) = C;
347  }
348 
349  /* Finally, inherit our parent and we are done */
350  RtlParent(C) = P;
351  return;
352 }
353 
354 /*
355  * @implemented
356  */
358 NTAPI
360 {
362 
363  /* Get the left child */
364  Child = RtlLeftChild(Links);
365  if (Child)
366  {
367  /* Get right-most child */
369  return Child;
370  }
371 
372  /* We don't have a left child, keep looping until we find our parent */
373  Child = Links;
375 
376  /* The parent should be a right child, return the real predecessor */
377  if (RtlIsRightChild(Child)) return RtlParent(Child);
378 
379  /* The parent isn't a right child, so no real precessor for us */
380  return NULL;
381 }
382 
383 /*
384  * @implemented
385  */
387 NTAPI
389 {
391 
392  /* Get the right child */
393  Child = RtlRightChild(Links);
394  if (Child)
395  {
396  /* Get left-most child */
398  return Child;
399  }
400 
401  /* We don't have a right child, keep looping until we find our parent */
402  Child = Links;
404 
405  /* The parent should be a left child, return the real successor */
406  if (RtlIsLeftChild(Child)) return RtlParent(Child);
407 
408  /* The parent isn't a right child, so no real successor for us */
409  return NULL;
410 }
411 
412 /*
413  * @implemented
414  */
416 NTAPI
418 {
419  /*
420  * Implementation Notes (http://en.wikipedia.org/wiki/Splay_tree):
421  *
422  * To do a splay, we carry out a sequence of rotations,
423  * each of which moves the target node N closer to the root.
424  *
425  * Each particular step depends on only two factors:
426  * - Whether N is the left or right child of its parent node, P,
427  * - Whether P is the left or right child of its parent, G (for grandparent node).
428  *
429  * Thus, there are four cases:
430  * - Case 1: N is the left child of P and P is the left child of G.
431  * In this case we perform a double right rotation, so that
432  * P becomes N's right child, and G becomes P's right child.
433  *
434  * - Case 2: N is the right child of P and P is the right child of G.
435  * In this case we perform a double left rotation, so that
436  * P becomes N's left child, and G becomes P's left child.
437  *
438  * - Case 3: N is the left child of P and P is the right child of G.
439  * In this case we perform a rotation so that
440  * G becomes N's left child, and P becomes N's right child.
441  *
442  * - Case 4: N is the right child of P and P is the left child of G.
443  * In this case we perform a rotation so that
444  * P becomes N's left child, and G becomes N's right child.
445  *
446  * Finally, if N doesn't have a grandparent node, we simply perform a
447  * left or right rotation to move it to the root.
448  *
449  * By performing a splay on the node of interest after every operation,
450  * we keep recently accessed nodes near the root and keep the tree
451  * roughly balanced, so that we achieve the desired amortized time bounds.
452  */
453  PRTL_SPLAY_LINKS N, P, G;
454 
455  /* N is the item we'll be playing with */
456  N = Links;
457 
458  /* Let the algorithm run until N becomes the root entry */
459  while (!RtlIsRoot(N))
460  {
461  /* Now get the parent and grand-parent */
462  P = RtlParent(N);
463  G = RtlParent(P);
464 
465  /* Case 1 & 3: N is left child of P */
466  if (RtlIsLeftChild(N))
467  {
468  /* Case 1: P is the left child of G */
469  if (RtlIsLeftChild(P))
470  {
471  /*
472  * N's right-child becomes P's left child and
473  * P's right-child becomes G's left child.
474  */
477 
478  /*
479  * If they exist, update their parent pointers too,
480  * since they've changed trees.
481  */
484 
485  /*
486  * Now we'll shove N all the way to the top.
487  * Check if G is the root first.
488  */
489  if (RtlIsRoot(G))
490  {
491  /* G doesn't have a parent, so N will become the root! */
492  RtlParent(N) = N;
493  }
494  else
495  {
496  /* G has a parent, so inherit it since we take G's place */
497  RtlParent(N) = RtlParent(G);
498 
499  /*
500  * Now find out who was referencing G and have it reference
501  * N instead, since we're taking G's place.
502  */
503  if (RtlIsLeftChild(G))
504  {
505  /*
506  * G was a left child, so change its parent's left
507  * child link to point to N now.
508  */
509  RtlLeftChild(RtlParent(G)) = N;
510  }
511  else
512  {
513  /*
514  * G was a right child, so change its parent's right
515  * child link to point to N now.
516  */
517  RtlRightChild(RtlParent(G)) = N;
518  }
519  }
520 
521  /* Now N is on top, so P has become its child. */
522  RtlRightChild(N) = P;
523  RtlParent(P) = N;
524 
525  /* N is on top, P is its child, so G is grandchild. */
526  RtlRightChild(P) = G;
527  RtlParent(G) = P;
528  }
529  /* Case 3: P is the right child of G */
530  else if (RtlIsRightChild(P))
531  {
532  /*
533  * N's left-child becomes G's right child and
534  * N's right-child becomes P's left child.
535  */
538 
539  /*
540  * If they exist, update their parent pointers too,
541  * since they've changed trees.
542  */
545 
546  /*
547  * Now we'll shove N all the way to the top.
548  * Check if G is the root first.
549  */
550  if (RtlIsRoot(G))
551  {
552  /* G doesn't have a parent, so N will become the root! */
553  RtlParent(N) = N;
554  }
555  else
556  {
557  /* G has a parent, so inherit it since we take G's place */
558  RtlParent(N) = RtlParent(G);
559 
560  /*
561  * Now find out who was referencing G and have it reference
562  * N instead, since we're taking G's place.
563  */
564  if (RtlIsLeftChild(G))
565  {
566  /*
567  * G was a left child, so change its parent's left
568  * child link to point to N now.
569  */
570  RtlLeftChild(RtlParent(G)) = N;
571  }
572  else
573  {
574  /*
575  * G was a right child, so change its parent's right
576  * child link to point to N now.
577  */
578  RtlRightChild(RtlParent(G)) = N;
579  }
580  }
581 
582  /* Now N is on top, so G has become its left child. */
583  RtlLeftChild(N) = G;
584  RtlParent(G) = N;
585 
586  /* N is on top, G is its left child, so P is right child. */
587  RtlRightChild(N) = P;
588  RtlParent(P) = N;
589  }
590  /* "Finally" case: N doesn't have a grandparent => P is root */
591  else
592  {
593  /* P's left-child becomes N's right child */
595 
596  /* If it exists, update its parent pointer too */
598 
599  /* Now make N the root, no need to worry about references */
600  N->Parent = N;
601 
602  /* And make P its right child */
603  N->RightChild = P;
604  P->Parent = N;
605  }
606  }
607  /* Case 2 & 4: N is right child of P */
608  else
609  {
610  /* Case 2: P is the right child of G */
611  if (RtlIsRightChild(P))
612  {
613  /*
614  * P's left-child becomes G's right child and
615  * N's left-child becomes P's right child.
616  */
619 
620  /*
621  * If they exist, update their parent pointers too,
622  * since they've changed trees.
623  */
626 
627  /*
628  * Now we'll shove N all the way to the top.
629  * Check if G is the root first.
630  */
631  if (RtlIsRoot(G))
632  {
633  /* G doesn't have a parent, so N will become the root! */
634  RtlParent(N) = N;
635  }
636  else
637  {
638  /* G has a parent, so inherit it since we take G's place */
639  RtlParent(N) = RtlParent(G);
640 
641  /*
642  * Now find out who was referencing G and have it reference
643  * N instead, since we're taking G's place.
644  */
645  if (RtlIsLeftChild(G))
646  {
647  /*
648  * G was a left child, so change its parent's left
649  * child link to point to N now.
650  */
651  RtlLeftChild(RtlParent(G)) = N;
652  }
653  else
654  {
655  /*
656  * G was a right child, so change its parent's right
657  * child link to point to N now.
658  */
659  RtlRightChild(RtlParent(G)) = N;
660  }
661  }
662 
663  /* Now N is on top, so P has become its child. */
664  RtlLeftChild(N) = P;
665  RtlParent(P) = N;
666 
667  /* N is on top, P is its child, so G is grandchild. */
668  RtlLeftChild(P) = G;
669  RtlParent(G) = P;
670  }
671  /* Case 4: P is the left child of G */
672  else if (RtlIsLeftChild(P))
673  {
674  /*
675  * N's left-child becomes G's right child and
676  * N's right-child becomes P's left child.
677  */
680 
681  /*
682  * If they exist, update their parent pointers too,
683  * since they've changed trees.
684  */
687 
688  /*
689  * Now we'll shove N all the way to the top.
690  * Check if G is the root first.
691  */
692  if (RtlIsRoot(G))
693  {
694  /* G doesn't have a parent, so N will become the root! */
695  RtlParent(N) = N;
696  }
697  else
698  {
699  /* G has a parent, so inherit it since we take G's place */
700  RtlParent(N) = RtlParent(G);
701 
702  /*
703  * Now find out who was referencing G and have it reference
704  * N instead, since we're taking G's place.
705  */
706  if (RtlIsLeftChild(G))
707  {
708  /*
709  * G was a left child, so change its parent's left
710  * child link to point to N now.
711  */
712  RtlLeftChild(RtlParent(G)) = N;
713  }
714  else
715  {
716  /*
717  * G was a right child, so change its parent's right
718  * child link to point to N now.
719  */
720  RtlRightChild(RtlParent(G)) = N;
721  }
722  }
723 
724  /* Now N is on top, so P has become its left child. */
725  RtlLeftChild(N) = P;
726  RtlParent(G) = N;
727 
728  /* N is on top, P is its left child, so G is right child. */
729  RtlRightChild(N) = G;
730  RtlParent(P) = N;
731  }
732  /* "Finally" case: N doesn't have a grandparent => P is root */
733  else
734  {
735  /* P's right-child becomes N's left child */
737 
738  /* If it exists, update its parent pointer too */
740 
741  /* Now make N the root, no need to worry about references */
742  N->Parent = N;
743 
744  /* And make P its left child */
745  N->LeftChild = P;
746  P->Parent = N;
747  }
748  }
749  }
750 
751  /* Return the root entry */
752  ASSERT(RtlIsRoot(N));
753  return N;
754 }
755 
756 /*
757  * @implemented
758  */
760 NTAPI
762 {
764 
765  /* Get the left child */
766  Child = RtlLeftChild(Links);
767  if (!Child) return NULL;
768 
769  /* Get right-most child */
771 
772  /* Return it */
773  return Child;
774 }
775 
776 /*
777  * @implemented
778  */
780 NTAPI
782 {
784 
785  /* Get the right child */
786  Child = RtlRightChild(Links);
787  if (!Child) return NULL;
788 
789  /* Get left-most child */
791 
792  /* Return it */
793  return Child;
794 }
795 
796 /* EOF */
static VOID SwapSplayLinks(PRTL_SPLAY_LINKS LinkA, PRTL_SPLAY_LINKS LinkB)
Definition: splaytree.c:73
PRTL_SPLAY_LINKS NTAPI RtlRealSuccessor(PRTL_SPLAY_LINKS Links)
Definition: splaytree.c:388
#define IN
Definition: typedefs.h:39
PRTL_SPLAY_LINKS NTAPI RtlSubtreePredecessor(IN PRTL_SPLAY_LINKS Links)
Definition: splaytree.c:761
int memcmp(void *Buffer1, void *Buffer2, ACPI_SIZE Count)
Definition: utclib.c:112
static VOID FixupChildLinks(PRTL_SPLAY_LINKS Links, BOOLEAN Root, BOOLEAN LeftChild)
Definition: splaytree.c:22
#define RtlInsertAsRightChild(ParentLinks, ChildLinks)
#define RtlInsertAsLeftChild(ParentLinks, ChildLinks)
PRTL_SPLAY_LINKS NTAPI RtlSubtreeSuccessor(IN PRTL_SPLAY_LINKS Links)
Definition: splaytree.c:781
NTSTATUS(* NTAPI)(IN PFILE_FULL_EA_INFORMATION EaBuffer, IN ULONG EaLength, OUT PULONG ErrorOffset)
Definition: IoEaTest.cpp:117
#define RtlIsLeftChild(Links)
#define RtlIsRoot(Links)
unsigned char BOOLEAN
smooth NULL
Definition: ftsmooth.c:416
root entry for file system trees
Definition: entries.h:148
#define RtlParent(Links)
#define RtlLeftChild(Links)
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
PRTL_SPLAY_LINKS NTAPI RtlDelete(PRTL_SPLAY_LINKS Links)
Definition: splaytree.c:180
#define RtlIsRightChild(Links)
#define P(row, col)
#define G(x, y, z)
Definition: md5.c:52
Definition: ttei6.cpp:27
static PTUNNEL Tb
Definition: FsRtlTunnel.c:26
#define C(c)
Definition: builtin.c:4556
ACPI_PHYSICAL_ADDRESS ACPI_SIZE BOOLEAN Warn BOOLEAN Physical UINT32 ACPI_TABLE_HEADER *OutTableHeader ACPI_TABLE_HEADER **OutTable ACPI_HANDLE UINT32 ACPI_WALK_CALLBACK ACPI_WALK_CALLBACK void void **ReturnValue UINT32 ACPI_BUFFER *RetPathPtr ACPI_OBJECT_HANDLER void *Data ACPI_OBJECT_HANDLER void **Data ACPI_STRING ACPI_OBJECT_LIST ACPI_BUFFER *ReturnObjectBuffer ACPI_DEVICE_INFO **ReturnBuffer ACPI_HANDLE ACPI_HANDLE Child
Definition: acpixf.h:728
#define RtlRightChild(Links)
PRTL_SPLAY_LINKS NTAPI RtlRealPredecessor(PRTL_SPLAY_LINKS Links)
Definition: splaytree.c:359
PRTL_SPLAY_LINKS NTAPI RtlSplay(PRTL_SPLAY_LINKS Links)
Definition: splaytree.c:417
VOID NTAPI RtlDeleteNoSplay(PRTL_SPLAY_LINKS Links, PRTL_SPLAY_LINKS *Root)
Definition: splaytree.c:265