2 * PROJECT: ReactOS Runtime Library
3 * LICENSE: BSD - See COPYING.ARM in the top level directory
4 * FILE: lib/rtl/avltable.c
5 * PURPOSE: AVL Tree Generic Table Implementation
6 * PROGRAMMERS: ReactOS Portable Systems Group
9 /* INCLUDES ******************************************************************/
15 /* Include RTL version of AVL support */
19 /* AVL FUNCTIONS *************************************************************/
26 RtlInitializeGenericTableAvl(IN OUT PRTL_AVL_TABLE Table
,
27 IN PRTL_AVL_COMPARE_ROUTINE CompareRoutine
,
28 IN PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine
,
29 IN PRTL_AVL_FREE_ROUTINE FreeRoutine
,
30 IN PVOID TableContext
)
33 RtlZeroMemory(Table
, sizeof(RTL_AVL_TABLE
));
34 Table
->BalancedRoot
.Parent
= &Table
->BalancedRoot
;
35 Table
->CompareRoutine
= CompareRoutine
;
36 Table
->AllocateRoutine
= AllocateRoutine
;
37 Table
->FreeRoutine
= FreeRoutine
;
38 Table
->TableContext
= TableContext
;
46 RtlInsertElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table
,
49 OUT PBOOLEAN NewElement OPTIONAL
,
50 IN OUT PVOID NodeOrParent
,
51 IN OUT TABLE_SEARCH_RESULT SearchResult
)
53 PRTL_BALANCED_LINKS NewNode
;
56 /* Check if the entry wasn't already found */
57 if (SearchResult
!= TableFoundNode
)
59 /* We're doing an allocation, sanity check */
60 ASSERT(Table
->NumberGenericTableElements
!= (MAXULONG
- 1));
63 NewNode
= Table
->AllocateRoutine(Table
,
65 FIELD_OFFSET(TABLE_ENTRY_HEADER
,
69 /* No memory or other allocation error, fail */
70 if (NewElement
) *NewElement
= FALSE
;
74 /* Data to return to user */
75 UserData
= &((PTABLE_ENTRY_HEADER
)NewNode
)->UserData
;
77 /* Insert the node in the tree */
78 RtlZeroMemory(NewNode
, sizeof(RTL_BALANCED_LINKS
));
79 RtlpInsertAvlTreeNode(Table
, NewNode
, NodeOrParent
, SearchResult
);
81 /* Copy user buffer */
82 RtlCopyMemory(UserData
, Buffer
, BufferSize
);
86 /* Return the node we already found */
87 NewNode
= NodeOrParent
;
88 UserData
= &((PTABLE_ENTRY_HEADER
)NewNode
)->UserData
;
92 if (NewElement
) *NewElement
= (SearchResult
!= TableFoundNode
);
94 /* Return pointer to user data */
103 RtlInsertElementGenericTableAvl(IN PRTL_AVL_TABLE Table
,
106 OUT PBOOLEAN NewElement OPTIONAL
)
108 PRTL_BALANCED_LINKS NodeOrParent
= NULL
;
109 TABLE_SEARCH_RESULT Result
;
111 /* Get the balanced links and table search result immediately */
112 Result
= RtlpFindAvlTableNodeOrParent(Table
, Buffer
, &NodeOrParent
);
114 /* Now call the routine to do the full insert */
115 return RtlInsertElementGenericTableFullAvl(Table
,
128 RtlIsGenericTableEmptyAvl(IN PRTL_AVL_TABLE Table
)
130 /* If there's no elements, the table is empty */
131 return Table
->NumberGenericTableElements
== 0;
139 RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table
)
141 /* Return the element count */
142 return Table
->NumberGenericTableElements
;
150 RtlLookupElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table
,
152 IN OUT PVOID
*NodeOrParent
,
153 IN OUT TABLE_SEARCH_RESULT
*SearchResult
)
156 *SearchResult
= RtlpFindAvlTableNodeOrParent(Table
,
158 (PRTL_BALANCED_LINKS
*)NodeOrParent
);
159 if (*SearchResult
!= TableFoundNode
) return NULL
;
161 /* Node found, return the user data */
162 return &((PTABLE_ENTRY_HEADER
)*NodeOrParent
)->UserData
;
170 RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table
,
173 PRTL_BALANCED_LINKS NodeOrParent
;
174 TABLE_SEARCH_RESULT Lookup
;
176 /* Call the full function */
177 return RtlLookupElementGenericTableFullAvl(Table
,
179 (PVOID
*)&NodeOrParent
,
188 RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table
,
191 /* Reset the restart key if needed */
192 if (Restart
) Table
->RestartKey
= NULL
;
194 /* Call the full function */
195 return RtlEnumerateGenericTableWithoutSplayingAvl(Table
,
196 (PVOID
*)&Table
->RestartKey
);
204 RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table
,
206 OUT PVOID
*RestartKey
)
208 PRTL_BALANCED_LINKS Node
, PreviousNode
;
209 TABLE_SEARCH_RESULT SearchResult
;
210 RTL_GENERIC_COMPARE_RESULTS Result
= GenericEqual
;
216 SearchResult
= RtlpFindAvlTableNodeOrParent(Table
, Buffer
, &Node
);
217 if (SearchResult
!= TableFoundNode
) return NULL
;
219 /* Scan each predecessor until a match is found */
221 while (Result
== GenericEqual
)
226 /* Get the predecessor */
227 PreviousNode
= RtlRealPredecessorAvl(Node
);
228 if ((!PreviousNode
) || (RtlParentAvl(PreviousNode
) == PreviousNode
)) break;
230 /* Check if this node matches */
231 Result
= RtlpAvlCompareRoutine(Table
,
233 &((PTABLE_ENTRY_HEADER
)PreviousNode
)->
237 /* Save the node as the restart key, and return its data */
239 return &((PTABLE_ENTRY_HEADER
)Node
)->UserData
;
247 RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table
,
248 IN OUT PVOID
*RestartKey
)
250 PRTL_BALANCED_LINKS CurrentNode
;
252 /* Skip an empty tree */
253 if (RtlIsGenericTableEmptyAvl(Table
)) return NULL
;
255 /* Check if we have a starting point */
258 /* We'll have to find it, keep going until the leftmost child */
259 for (CurrentNode
= RtlRightChildAvl(&Table
->BalancedRoot
);
260 RtlLeftChildAvl(CurrentNode
);
261 CurrentNode
= RtlLeftChildAvl(CurrentNode
));
264 *RestartKey
= CurrentNode
;
268 /* We already had a child, keep going by getting its successor */
269 CurrentNode
= RtlRealSuccessorAvl(*RestartKey
);
271 /* If there was one, update the restart key */
272 if (CurrentNode
) *RestartKey
= CurrentNode
;
275 /* Return the node's data if it was found, otherwise return NULL */
276 if (CurrentNode
) return &((PTABLE_ENTRY_HEADER
)CurrentNode
)->UserData
;
285 RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table
,
297 RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table
,
300 PRTL_BALANCED_LINKS Node
;
301 TABLE_SEARCH_RESULT SearchResult
;
304 SearchResult
= RtlpFindAvlTableNodeOrParent(Table
, Buffer
, &Node
);
305 if (SearchResult
!= TableFoundNode
) return FALSE
;
307 /* If this node was the key, update it */
308 if (Node
== Table
->RestartKey
) Table
->RestartKey
= RtlRealPredecessorAvl(Node
);
311 Table
->DeleteCount
++;
312 RtlpDeleteAvlTreeNode(Table
, Node
);
313 Table
->NumberGenericTableElements
--;
315 /* Reset accounting */
316 Table
->WhichOrderedElement
= 0;
317 Table
->OrderedPointer
= NULL
;
319 /* Free the node's data */
320 Table
->FreeRoutine(Table
, Node
);