ReactOS  0.4.14-dev-1233-gf5658fd
avlsupp.c
Go to the documentation of this file.
1 /*
2  * PROJECT: ReactOS Runtime Library
3  * LICENSE: BSD - See COPYING.ARM in the top level directory
4  * FILE: lib/rtl/avlsupp.c
5  * PURPOSE: AVL Tree Internal Support Routines/Main Algorithms
6  * PROGRAMMERS: ReactOS Portable Systems Group
7  */
8 
9 /* INCLUDES ******************************************************************/
10 
11 /* Internal header for table entries */
12 typedef struct _TABLE_ENTRY_HEADER
13 {
17 
19 {
25 
27 
28 /* FUNCTIONS ******************************************************************/
29 
33  IN PVOID Buffer,
34  OUT PRTL_BALANCED_LINKS *NodeOrParent)
35 {
36  PRTL_BALANCED_LINKS CurrentNode, ChildNode;
38 
39  /* Quick check to see if the table is empty */
40  if (!Table->NumberGenericTableElements) return TableEmptyTree;
41 
42  /* Set the current node */
43  CurrentNode = RtlRightChildAvl(&Table->BalancedRoot);
44 
45  /* Start compare loop */
46  while (TRUE)
47  {
48  /* Compare which side is greater */
50  Buffer,
51  &((PTABLE_ENTRY_HEADER)CurrentNode)->
52  UserData);
53  if (Result == GenericLessThan)
54  {
55  /* We're less, check if this is the left child */
56  ChildNode = RtlLeftChildAvl(CurrentNode);
57  if (ChildNode)
58  {
59  /* Continue searching from this node */
60  CurrentNode = ChildNode;
61  }
62  else
63  {
64  /* Otherwise, the element isn't in this tree */
65  *NodeOrParent = CurrentNode;
66  return TableInsertAsLeft;
67  }
68  }
69  else if (Result == GenericGreaterThan)
70  {
71  /* We're more, check if this is the right child */
72  ChildNode = RtlRightChildAvl(CurrentNode);
73  if (ChildNode)
74  {
75  /* Continue searching from this node */
76  CurrentNode = ChildNode;
77  }
78  else
79  {
80  /* Otherwise, the element isn't in this tree */
81  *NodeOrParent = CurrentNode;
82  return TableInsertAsRight;
83  }
84  }
85  else
86  {
87  /* We should've found the node */
89 
90  /* Return node found */
91  *NodeOrParent = CurrentNode;
92  return TableFoundNode;
93  }
94  }
95 }
96 
98 VOID
100 {
101  PRTL_BALANCED_LINKS ParentNode, SuperParentNode;
102  PRTL_BALANCED_LINKS *SwapNode1, *SwapNode2;
103 
104  /* Grab parents up to 2 levels high */
105  ParentNode = RtlParentAvl(Node);
106  SuperParentNode = RtlParentAvl(ParentNode);
107 
108  /* Pick which nodes will be rotated */
109  SwapNode1 = RtlIsLeftChildAvl(Node) ? &ParentNode->LeftChild : &ParentNode->RightChild;
110  SwapNode2 = RtlIsLeftChildAvl(Node) ? &Node->RightChild : &Node->LeftChild;
111 
112  /* Do the rotate, and update the parent and super-parent as needed */
113  *SwapNode1 = *SwapNode2;
114  if (*SwapNode1) RtlSetParent(*SwapNode1, ParentNode);
115  *SwapNode2 = ParentNode;
116  RtlSetParent(ParentNode, Node);
117 
118  /* Now update the super-parent child link, and make it parent of the node*/
119  SwapNode1 = (RtlLeftChildAvl(SuperParentNode) == ParentNode) ?
120  &SuperParentNode->LeftChild: &SuperParentNode->RightChild;
121  *SwapNode1 = Node;
122  RtlSetParent(Node, SuperParentNode);
123 }
124 
126 BOOLEAN
128 {
129  PRTL_BALANCED_LINKS ChildNode, SubChildNode;
130  CHAR Balance;
132 
133  /* Get the balance, and figure out which child node to go down on */
135  ChildNode = (Balance == RtlRightHeavyAvlTree) ?
137 
138  /* The child and node have the same balance, promote the child upwards */
139  if (RtlBalance(ChildNode) == Balance)
140  {
141  /* This performs the rotation described in Knuth A8-A10 for Case 1 */
142  RtlpPromoteAvlTreeNode(ChildNode);
143 
144  /* The nodes are now balanced */
145  RtlSetBalance(ChildNode, RtlBalancedAvlTree);
147  return FALSE;
148  }
149 
150  /* The child has the opposite balance, a double promotion of the child's child must happen */
151  if (RtlBalance(ChildNode) == -Balance)
152  {
153  /* Pick which sub-child to use based on the balance */
154  SubChildNode = (Balance == RtlRightHeavyAvlTree) ?
155  RtlLeftChildAvl(ChildNode) : RtlRightChildAvl(ChildNode);
156 
157  /* Do the double-rotation described in Knuth A8-A10 for Case 2 */
158  RtlpPromoteAvlTreeNode(SubChildNode);
159  RtlpPromoteAvlTreeNode(SubChildNode);
160 
161  /* Was the sub-child sharing the same balance as the node? */
162  if (RtlBalance(SubChildNode) == Balance)
163  {
164  /* Then the subchild is now balanced, and the node's weight is inversed */
165  RtlSetBalance(ChildNode, RtlBalancedAvlTree);
167  }
168  else if (RtlBalance(SubChildNode) == -Balance)
169  {
170  /*
171  * In this case, the sub-child weight was the inverse of the node, so
172  * the child now shares the node's balance original weight, while the
173  * node becomes balanced.
174  */
175  RtlSetBalance(ChildNode, Balance);
177  }
178  else
179  {
180  /*
181  * Otherwise, the sub-child was unbalanced, so both the child and node
182  * now become balanced.
183  */
184  RtlSetBalance(ChildNode, RtlBalancedAvlTree);
186  }
187 
188  /* In all cases, the sub-child is now balanced */
189  RtlSetBalance(SubChildNode, RtlBalancedAvlTree);
190  return FALSE;
191  }
192 
193  /*
194  * The case that remains is that the child was already balanced, so this is
195  * This is the rotation required for Case 3 in Knuth A8-A10
196  */
197  RtlpPromoteAvlTreeNode(ChildNode);
198 
199  /* Now the child has the opposite weight of the node */
200  RtlSetBalance(ChildNode, -Balance);
201 
202  /* This only happens on deletion, so we return TRUE to terminate the delete */
203  return TRUE;
204 }
205 
207 VOID
209  IN PRTL_BALANCED_LINKS NewNode,
210  IN OUT PVOID NodeOrParent,
211  IN OUT TABLE_SEARCH_RESULT SearchResult)
212 {
213  CHAR Balance;
214 
215  /* Initialize the new inserted element */
216  MI_ASSERT(SearchResult != TableFoundNode);
217  NewNode->LeftChild = NewNode->RightChild = NULL;
219 
220  /* Increase element count */
221  Table->NumberGenericTableElements++;
222 
223  /* Check where we should insert the entry */
224  if (SearchResult == TableEmptyTree)
225  {
226  /* This is the new root node */
227  RtlInsertAsRightChildAvl(&Table->BalancedRoot, NewNode);
228 
229  /* On AVL trees, we also update the depth */
230  ASSERT(Table->DepthOfTree == 0);
231  Table->DepthOfTree = 1;
232  return;
233  }
234  else if (SearchResult == TableInsertAsLeft)
235  {
236  /* Insert it left */
237  RtlInsertAsLeftChildAvl(NodeOrParent, NewNode);
238  }
239  else
240  {
241  /* Right node */
242  RtlInsertAsRightChildAvl(NodeOrParent, NewNode);
243  }
244 
245  /* Little cheat to save on loop processing, taken from Timo */
246  RtlSetBalance(&Table->BalancedRoot, RtlLeftHeavyAvlTree);
247 
248  /*
249  * This implements A6-A7 from Knuth based on http://coding.derkeiler.com
250  * /pdf/Archive/C_CPP/comp.lang.c/2004-01/1812.pdf, however the algorithm
251  * is slightly modified to follow the tree based on the Parent Node such
252  * as the Windows algorithm does it, instead of following the nodes down.
253  */
254  while (TRUE)
255  {
256  /* Calculate which side to balance on */
258 
259  /* Check if the parent node was balanced */
260  if (RtlBalance(NodeOrParent) == RtlBalancedAvlTree)
261  {
262  /* It's not balanced anymore (heavy on one side) */
263  RtlSetBalance(NodeOrParent, Balance);
264 
265  /* Move up */
266  NewNode = NodeOrParent;
267  NodeOrParent = RtlParentAvl(NodeOrParent);
268  }
269  else if (RtlBalance(NodeOrParent) != Balance)
270  {
271  /* The parent's balance is opposite, so the tree is balanced now */
272  RtlSetBalance(NodeOrParent, RtlBalancedAvlTree);
273 
274  /* Check if this is the root (the cheat applied earlier gets us here) */
275  if (RtlBalance(&Table->BalancedRoot) == RtlBalancedAvlTree)
276  {
277  /* The depth has thus increased */
278  Table->DepthOfTree++;
279  }
280 
281  /* We reached the root or a balanced node, so we're done */
282  break;
283  }
284  else
285  {
286  /* The tree is now unbalanced, so AVL rebalancing must happen */
287  RtlpRebalanceAvlTreeNode(NodeOrParent);
288  break;
289  }
290  }
291 }
292 
294 VOID
297 {
298  PRTL_BALANCED_LINKS DeleteNode = NULL, ParentNode;
299  PRTL_BALANCED_LINKS *Node1, *Node2;
300  CHAR Balance;
301 
302  /* Take one of the children if possible */
304 
305  /* Otherwise, check if one side is longer */
307  {
308  /* Pick the successor which will be the longest side in this case */
311  }
312  else if (!DeleteNode)
313  {
314  /* Pick the predecessor which will be the longest side in this case */
317  }
318 
319  /* Get the parent node */
320  ParentNode = RtlParentAvl(DeleteNode);
321  DPRINT("Parent: %p\n", ParentNode);
322 
323  /* Pick which now to use based on whether or not we have a left child */
324  Node1 = RtlLeftChildAvl(DeleteNode) ? &DeleteNode->LeftChild : &DeleteNode->RightChild;
325  DPRINT("Node 1: %p %p\n", Node1, *Node1);
326 
327  /* Pick which node to swap based on if we're already a left child or not */
328  Node2 = RtlIsLeftChildAvl(DeleteNode) ? &ParentNode->LeftChild : &ParentNode->RightChild;
329  DPRINT("Node 2: %p %p\n", Node2, *Node2);
330 
331  /* Pick the correct balance depending on which side will get heavier */
333  DPRINT("Balance: %lx\n", Balance);
334 
335  /* Swap the children nodes, making one side heavier */
336  *Node2 = *Node1;
337 
338  /* If the node has a child now, update its parent */
339  if (*Node1) RtlSetParent(*Node1, ParentNode);
340 
341  /* Assume balanced root for loop optimization */
342  RtlSetBalance(&Table->BalancedRoot, RtlBalancedAvlTree);
343 
344  /* Loop up the tree by parents */
345  while (TRUE)
346  {
347  /* Check if the tree's balance increased */
348  if (RtlBalance(ParentNode) == Balance)
349  {
350  /* Now the tree is balanced */
351  RtlSetBalance(ParentNode, RtlBalancedAvlTree);
352  }
353  else if (RtlBalance(ParentNode) == RtlBalancedAvlTree)
354  {
355  /* The tree has now become less balanced, since it was balanced */
356  RtlSetBalance(ParentNode, -Balance);
357 
358  /* Deal with the loop optimization to detect loss of a tree level */
359  if (RtlBalance(&Table->BalancedRoot) != RtlBalancedAvlTree) Table->DepthOfTree--;
360  break;
361  }
362  else
363  {
364  /* The tree has become unbalanced, so a rebalance is needed */
365  if (RtlpRebalanceAvlTreeNode(ParentNode)) break;
366 
367  /* Get the new parent after the balance */
368  ParentNode = RtlParentAvl(ParentNode);
369  }
370 
371  /* Choose which balance factor to use based on which side we're on */
372  Balance = RtlIsRightChild(ParentNode) ?
374 
375  /* Iterate up the tree */
376  ParentNode = RtlParentAvl(ParentNode);
377  }
378 
379  /* Check if this isn't the node we ended up deleting directly */
380  if (Node == DeleteNode) return;
381 
382  /* Copy the deleted node itself */
384 
385  /* Pick the right node to unlink */
386  Node1 = RtlIsLeftChildAvl(Node) ?
387  &(RtlParentAvl(DeleteNode))->LeftChild : &(RtlParentAvl(DeleteNode))->RightChild;
388  *Node1 = DeleteNode;
389 
390  /* Reparent as appropriate */
393 }
394 
395 /* EOF */
FORCEINLINE VOID RtlpDeleteAvlTreeNode(IN PRTL_AVL_TABLE Table, IN PRTL_BALANCED_LINKS Node)
Definition: avlsupp.c:295
#define IN
Definition: typedefs.h:39
FORCEINLINE BOOLEAN RtlpRebalanceAvlTreeNode(IN PRTL_BALANCED_LINKS Node)
Definition: avlsupp.c:127
ASMGENDATA Table[]
Definition: genincdata.c:61
#define TRUE
Definition: types.h:120
static const UCHAR Balance[]
Definition: usbehci.c:97
FORCEINLINE CHAR RtlBalance(IN PRTL_BALANCED_LINKS Node)
Definition: rtlavl.h:65
char CHAR
Definition: xmlstorage.h:175
enum _TABLE_SEARCH_RESULT TABLE_SEARCH_RESULT
LONGLONG UserData
Definition: avlsupp.c:15
#define RtlRightChildAvl
Definition: miavl.h:45
FORCEINLINE VOID RtlpInsertAvlTreeNode(IN PRTL_AVL_TABLE Table, IN PRTL_BALANCED_LINKS NewNode, IN OUT PVOID NodeOrParent, IN OUT TABLE_SEARCH_RESULT SearchResult)
Definition: avlsupp.c:208
FORCEINLINE VOID RtlSetBalance(IN PRTL_BALANCED_LINKS Node, IN CHAR Balance)
Definition: rtlavl.h:57
C_ASSERT(RtlBalancedAvlTree==0)
union node Node
Definition: types.h:1255
unsigned char BOOLEAN
smooth NULL
Definition: ftsmooth.c:416
#define FORCEINLINE
Definition: ntbasedef.h:221
_At_(*)(_In_ PWSK_CLIENT Client, _In_opt_ PUNICODE_STRING NodeName, _In_opt_ PUNICODE_STRING ServiceName, _In_opt_ ULONG NameSpace, _In_opt_ GUID *Provider, _In_opt_ PADDRINFOEXW Hints, _Outptr_ PADDRINFOEXW *Result, _In_opt_ PEPROCESS OwningProcess, _In_opt_ PETHREAD OwningThread, _Inout_ PIRP Irp Result)(Mem)) NTSTATUS(WSKAPI *PFN_WSK_GET_ADDRESS_INFO
Definition: wsk.h:426
void DPRINT(...)
Definition: polytest.cpp:61
Definition: bufpool.h:45
BOOL DeleteNode(HWND hwndTV, HTREEITEM hItem)
Definition: treeview.c:102
int64_t LONGLONG
Definition: typedefs.h:67
RTL_BALANCED_LINKS BalancedLinks
Definition: avlsupp.c:14
FORCEINLINE VOID RtlpPromoteAvlTreeNode(IN PRTL_BALANCED_LINKS Node)
Definition: avlsupp.c:99
Definition: avlsupp.c:12
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
struct _TABLE_ENTRY_HEADER * PTABLE_ENTRY_HEADER
FORCEINLINE VOID RtlSetParent(IN PRTL_BALANCED_LINKS Node, IN PRTL_BALANCED_LINKS Parent)
Definition: rtlavl.h:49
#define RtlIsRightChild(Links)
#define RtlIsLeftChildAvl
Definition: miavl.h:47
FORCEINLINE TABLE_SEARCH_RESULT RtlpFindAvlTableNodeOrParent(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, OUT PRTL_BALANCED_LINKS *NodeOrParent)
Definition: avlsupp.c:32
#define RtlLeftChildAvl
Definition: miavl.h:46
#define MI_ASSERT(x)
Definition: miavl.h:29
FORCEINLINE VOID RtlpCopyAvlNodeData(IN PRTL_BALANCED_LINKS Node1, IN PRTL_BALANCED_LINKS Node2)
Definition: rtlavl.h:29
enum _RTL_GENERIC_COMPARE_RESULTS RTL_GENERIC_COMPARE_RESULTS
enum _RTL_AVL_BALANCE_FACTOR RTL_AVL_BALANCE_FACTOR
#define OUT
Definition: typedefs.h:40
FORCEINLINE RTL_GENERIC_COMPARE_RESULTS RtlpAvlCompareRoutine(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, IN PVOID UserData)
Definition: rtlavl.h:37
#define RtlInsertAsRightChildAvl
Definition: miavl.h:50
#define RtlParentAvl
Definition: miavl.h:44
#define RtlInsertAsLeftChildAvl
Definition: miavl.h:49
struct _TABLE_ENTRY_HEADER TABLE_ENTRY_HEADER
_RTL_AVL_BALANCE_FACTOR
Definition: avlsupp.c:18
Definition: dlist.c:348