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 RtlpInsertAvlTreeNode(Table
, NewNode
, NodeOrParent
, SearchResult
);
80 /* Copy user buffer */
81 RtlCopyMemory(UserData
, Buffer
, BufferSize
);
85 /* Return the node we already found */
86 NewNode
= NodeOrParent
;
87 UserData
= &((PTABLE_ENTRY_HEADER
)NewNode
)->UserData
;
91 if (NewElement
) *NewElement
= (SearchResult
== TableFoundNode
);
93 /* Return pointer to user data */
102 RtlInsertElementGenericTableAvl(IN PRTL_AVL_TABLE Table
,
105 OUT PBOOLEAN NewElement OPTIONAL
)
107 PRTL_BALANCED_LINKS NodeOrParent
= NULL
;
108 TABLE_SEARCH_RESULT Result
;
110 /* Get the balanced links and table search result immediately */
111 Result
= RtlpFindAvlTableNodeOrParent(Table
, Buffer
, &NodeOrParent
);
113 /* Now call the routine to do the full insert */
114 return RtlInsertElementGenericTableFullAvl(Table
,
127 RtlIsGenericTableEmptyAvl(IN PRTL_AVL_TABLE Table
)
129 /* If there's no elements, the table is empty */
130 return Table
->NumberGenericTableElements
== 0;
138 RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table
)
140 /* Return the element count */
141 return Table
->NumberGenericTableElements
;
149 RtlLookupElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table
,
151 IN OUT PVOID
*NodeOrParent
,
152 IN OUT TABLE_SEARCH_RESULT
*SearchResult
)
155 *SearchResult
= RtlpFindAvlTableNodeOrParent(Table
,
157 (PRTL_BALANCED_LINKS
*)NodeOrParent
);
158 if (*SearchResult
!= TableFoundNode
) return NULL
;
160 /* Node found, return the user data */
161 return &((PTABLE_ENTRY_HEADER
)*NodeOrParent
)->UserData
;
169 RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table
,
172 PRTL_BALANCED_LINKS NodeOrParent
;
173 TABLE_SEARCH_RESULT Lookup
;
175 /* Call the full function */
176 return RtlLookupElementGenericTableFullAvl(Table
,
178 (PVOID
*)&NodeOrParent
,
187 RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table
,
190 /* Reset the restart key if needed */
191 if (Restart
) Table
->RestartKey
= NULL
;
193 /* Call the full function */
194 return RtlEnumerateGenericTableWithoutSplayingAvl(Table
,
195 (PVOID
*)&Table
->RestartKey
);
203 RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table
,
205 OUT PVOID
*RestartKey
)
207 PRTL_BALANCED_LINKS Node
, PreviousNode
;
208 TABLE_SEARCH_RESULT SearchResult
;
209 RTL_GENERIC_COMPARE_RESULTS Result
= GenericEqual
;
215 SearchResult
= RtlpFindAvlTableNodeOrParent(Table
, Buffer
, &Node
);
216 if (SearchResult
!= TableFoundNode
) return NULL
;
218 /* Scan each predecessor until a match is found */
220 while (Result
== GenericEqual
)
225 /* Get the predecessor */
226 PreviousNode
= RtlRealPredecessorAvl(Node
);
227 if ((!PreviousNode
) || (RtlParentAvl(PreviousNode
) == PreviousNode
)) break;
229 /* Check if this node matches */
230 Result
= RtlpAvlCompareRoutine(Table
,
232 &((PTABLE_ENTRY_HEADER
)PreviousNode
)->
236 /* Save the node as the restart key, and return its data */
238 return &((PTABLE_ENTRY_HEADER
)Node
)->UserData
;
246 RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table
,
247 IN OUT PVOID
*RestartKey
)
249 PRTL_BALANCED_LINKS CurrentNode
;
251 /* Skip an empty tree */
252 if (RtlIsGenericTableEmptyAvl(Table
)) return NULL
;
254 /* Check if we have a starting point */
257 /* We'll have to find it, keep going until the leftmost child */
258 for (CurrentNode
= RtlRightChildAvl(&Table
->BalancedRoot
);
259 RtlLeftChildAvl(CurrentNode
);
260 CurrentNode
= RtlLeftChildAvl(CurrentNode
));
263 *RestartKey
= CurrentNode
;
267 /* We already had a child, keep going by getting its successor */
268 CurrentNode
= RtlRealSuccessorAvl(*RestartKey
);
270 /* If there was one, update the restart key */
271 if (CurrentNode
) *RestartKey
= CurrentNode
;
274 /* Return the node's data if it was found, otherwise return NULL */
275 if (CurrentNode
) return &((PTABLE_ENTRY_HEADER
)CurrentNode
)->UserData
;
284 RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table
,
296 RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table
,