1 /*
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
7 */
8
9 /* INCLUDES ******************************************************************/
10
11 #include <rtl.h>
12 #define NDEBUG
13 #include <debug.h>
14
15 /* Include RTL version of AVL support */
16 #include "rtlavl.h"
17 #include "avlsupp.c"
18
19 /* AVL FUNCTIONS *************************************************************/
20
21 /*
22 * @implemented
23 */
24 VOID
25 NTAPI
RtlInitializeGenericTableAvl(IN OUT PRTL_AVL_TABLE Table,IN PRTL_AVL_COMPARE_ROUTINE CompareRoutine,IN PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine,IN PRTL_AVL_FREE_ROUTINE FreeRoutine,IN PVOID TableContext)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)
31 {
32 /* Setup the table */
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;
39 }
40
41 /*
42 * @implemented
43 */
44 PVOID
45 NTAPI
RtlInsertElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,IN PVOID Buffer,IN ULONG BufferSize,OUT PBOOLEAN NewElement OPTIONAL,IN OUT PVOID NodeOrParent,IN OUT TABLE_SEARCH_RESULT SearchResult)46 RtlInsertElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,
47 IN PVOID Buffer,
48 IN ULONG BufferSize,
49 OUT PBOOLEAN NewElement OPTIONAL,
50 IN OUT PVOID NodeOrParent,
51 IN OUT TABLE_SEARCH_RESULT SearchResult)
52 {
53 PRTL_BALANCED_LINKS NewNode;
54 PVOID UserData;
55
56 /* Check if the entry wasn't already found */
57 if (SearchResult != TableFoundNode)
58 {
59 /* We're doing an allocation, sanity check */
60 ASSERT(Table->NumberGenericTableElements != (MAXULONG - 1));
61
62 /* Allocate a node */
63 NewNode = Table->AllocateRoutine(Table,
64 BufferSize +
65 FIELD_OFFSET(TABLE_ENTRY_HEADER,
66 UserData));
67 if (!NewNode)
68 {
69 /* No memory or other allocation error, fail */
70 if (NewElement) *NewElement = FALSE;
71 return NULL;
72 }
73
74 /* Data to return to user */
75 UserData = &((PTABLE_ENTRY_HEADER)NewNode)->UserData;
76
77 /* Insert the node in the tree */
78 RtlZeroMemory(NewNode, sizeof(RTL_BALANCED_LINKS));
79 RtlpInsertAvlTreeNode(Table, NewNode, NodeOrParent, SearchResult);
80
81 /* Copy user buffer */
82 RtlCopyMemory(UserData, Buffer, BufferSize);
83 }
84 else
85 {
86 /* Return the node we already found */
87 NewNode = NodeOrParent;
88 UserData = &((PTABLE_ENTRY_HEADER)NewNode)->UserData;
89 }
90
91 /* Return status */
92 if (NewElement) *NewElement = (SearchResult != TableFoundNode);
93
94 /* Return pointer to user data */
95 return UserData;
96 }
97
98 /*
99 * @implemented
100 */
101 PVOID
102 NTAPI
RtlInsertElementGenericTableAvl(IN PRTL_AVL_TABLE Table,IN PVOID Buffer,IN ULONG BufferSize,OUT PBOOLEAN NewElement OPTIONAL)103 RtlInsertElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
104 IN PVOID Buffer,
105 IN ULONG BufferSize,
106 OUT PBOOLEAN NewElement OPTIONAL)
107 {
108 PRTL_BALANCED_LINKS NodeOrParent = NULL;
109 TABLE_SEARCH_RESULT Result;
110
111 /* Get the balanced links and table search result immediately */
112 Result = RtlpFindAvlTableNodeOrParent(Table, Buffer, &NodeOrParent);
113
114 /* Now call the routine to do the full insert */
115 return RtlInsertElementGenericTableFullAvl(Table,
116 Buffer,
117 BufferSize,
118 NewElement,
119 NodeOrParent,
120 Result);
121 }
122
123 /*
124 * @implemented
125 */
126 BOOLEAN
127 NTAPI
RtlIsGenericTableEmptyAvl(IN PRTL_AVL_TABLE Table)128 RtlIsGenericTableEmptyAvl(IN PRTL_AVL_TABLE Table)
129 {
130 /* If there's no elements, the table is empty */
131 return Table->NumberGenericTableElements == 0;
132 }
133
134 /*
135 * @implemented
136 */
137 ULONG
138 NTAPI
RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table)139 RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table)
140 {
141 /* Return the element count */
142 return Table->NumberGenericTableElements;
143 }
144
145 /*
146 * @implemented
147 */
148 PVOID
149 NTAPI
RtlLookupElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,IN PVOID Buffer,IN OUT PVOID * NodeOrParent,IN OUT TABLE_SEARCH_RESULT * SearchResult)150 RtlLookupElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table,
151 IN PVOID Buffer,
152 IN OUT PVOID *NodeOrParent,
153 IN OUT TABLE_SEARCH_RESULT *SearchResult)
154 {
155 /* Find the node */
156 *SearchResult = RtlpFindAvlTableNodeOrParent(Table,
157 Buffer,
158 (PRTL_BALANCED_LINKS*)NodeOrParent);
159 if (*SearchResult != TableFoundNode) return NULL;
160
161 /* Node found, return the user data */
162 return &((PTABLE_ENTRY_HEADER)*NodeOrParent)->UserData;
163 }
164
165 /*
166 * @implemented
167 */
168 PVOID
169 NTAPI
RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table,IN PVOID Buffer)170 RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
171 IN PVOID Buffer)
172 {
173 PRTL_BALANCED_LINKS NodeOrParent;
174 TABLE_SEARCH_RESULT Lookup;
175
176 /* Call the full function */
177 return RtlLookupElementGenericTableFullAvl(Table,
178 Buffer,
179 (PVOID*)&NodeOrParent,
180 &Lookup);
181 }
182
183 /*
184 * @implemented
185 */
186 PVOID
187 NTAPI
RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table,IN BOOLEAN Restart)188 RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table,
189 IN BOOLEAN Restart)
190 {
191 /* Reset the restart key if needed */
192 if (Restart) Table->RestartKey = NULL;
193
194 /* Call the full function */
195 return RtlEnumerateGenericTableWithoutSplayingAvl(Table,
196 (PVOID*)&Table->RestartKey);
197 }
198
199 /*
200 * @implemented
201 */
202 PVOID
203 NTAPI
RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table,IN PVOID Buffer,OUT PVOID * RestartKey)204 RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
205 IN PVOID Buffer,
206 OUT PVOID *RestartKey)
207 {
208 PRTL_BALANCED_LINKS Node, PreviousNode;
209 TABLE_SEARCH_RESULT SearchResult;
210 RTL_GENERIC_COMPARE_RESULTS Result = GenericEqual;
211
212 /* Assume failure */
213 *RestartKey = NULL;
214
215 /* Find the node */
216 SearchResult = RtlpFindAvlTableNodeOrParent(Table, Buffer, &Node);
217 if (SearchResult != TableFoundNode) return NULL;
218
219 /* Scan each predecessor until a match is found */
220 PreviousNode = Node;
221 while (Result == GenericEqual)
222 {
223 /* Save the node */
224 Node = PreviousNode;
225
226 /* Get the predecessor */
227 PreviousNode = RtlRealPredecessorAvl(Node);
228 if ((!PreviousNode) || (RtlParentAvl(PreviousNode) == PreviousNode)) break;
229
230 /* Check if this node matches */
231 Result = RtlpAvlCompareRoutine(Table,
232 Buffer,
233 &((PTABLE_ENTRY_HEADER)PreviousNode)->
234 UserData);
235 }
236
237 /* Save the node as the restart key, and return its data */
238 *RestartKey = Node;
239 return &((PTABLE_ENTRY_HEADER)Node)->UserData;
240 }
241
242 /*
243 * @unimplemented
244 */
245 PVOID
246 NTAPI
RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table,IN OUT PVOID * RestartKey)247 RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table,
248 IN OUT PVOID *RestartKey)
249 {
250 PRTL_BALANCED_LINKS CurrentNode;
251
252 /* Skip an empty tree */
253 if (RtlIsGenericTableEmptyAvl(Table)) return NULL;
254
255 /* Check if we have a starting point */
256 if (!*RestartKey)
257 {
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));
262
263 /* Found it */
264 *RestartKey = CurrentNode;
265 }
266 else
267 {
268 /* We already had a child, keep going by getting its successor */
269 CurrentNode = RtlRealSuccessorAvl(*RestartKey);
270
271 /* If there was one, update the restart key */
272 if (CurrentNode) *RestartKey = CurrentNode;
273 }
274
275 /* Return the node's data if it was found, otherwise return NULL */
276 if (CurrentNode) return &((PTABLE_ENTRY_HEADER)CurrentNode)->UserData;
277 return NULL;
278 }
279
280 /*
281 * @unimplemented
282 */
283 PVOID
284 NTAPI
RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table,IN ULONG I)285 RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
286 IN ULONG I)
287 {
288 UNIMPLEMENTED;
289 return NULL;
290 }
291
292 /*
293 * @implemented
294 */
295 BOOLEAN
296 NTAPI
RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table,IN PVOID Buffer)297 RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table,
298 IN PVOID Buffer)
299 {
300 PRTL_BALANCED_LINKS Node;
301 TABLE_SEARCH_RESULT SearchResult;
302
303 /* Find the node */
304 SearchResult = RtlpFindAvlTableNodeOrParent(Table, Buffer, &Node);
305 if (SearchResult != TableFoundNode) return FALSE;
306
307 /* If this node was the key, update it */
308 if (Node == Table->RestartKey) Table->RestartKey = RtlRealPredecessorAvl(Node);
309
310 /* Do the delete */
311 Table->DeleteCount++;
312 RtlpDeleteAvlTreeNode(Table, Node);
313 Table->NumberGenericTableElements--;
314
315 /* Reset accounting */
316 Table->WhichOrderedElement = 0;
317 Table->OrderedPointer = NULL;
318
319 /* Free the node's data */
320 Table->FreeRoutine(Table, Node);
321
322 /* It's done */
323 return TRUE;
324 }
325
326 /* EOF */
327