xref: /reactos/sdk/lib/rtl/avltable.c (revision c2c66aff) 
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
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
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
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
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
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
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
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
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
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
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
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
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