ReactOS 0.4.15-dev-8135-g1bc6c90
avltable.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/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 */
24VOID
31{
32 /* Setup the 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 */
49 OUT PBOOLEAN NewElement OPTIONAL,
50 IN OUT PVOID NodeOrParent,
51 IN OUT TABLE_SEARCH_RESULT SearchResult)
52{
53 PRTL_BALANCED_LINKS NewNode;
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,
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 */
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 */
101PVOID
102NTAPI
106 OUT PBOOLEAN NewElement OPTIONAL)
107{
108 PRTL_BALANCED_LINKS NodeOrParent = NULL;
110
111 /* Get the balanced links and table search result immediately */
113
114 /* Now call the routine to do the full insert */
116 Buffer,
118 NewElement,
119 NodeOrParent,
120 Result);
121}
122
123/*
124 * @implemented
125 */
127NTAPI
129{
130 /* If there's no elements, the table is empty */
131 return Table->NumberGenericTableElements == 0;
132}
133
134/*
135 * @implemented
136 */
137ULONG
138NTAPI
140{
141 /* Return the element count */
142 return Table->NumberGenericTableElements;
143}
144
145/*
146 * @implemented
147 */
148PVOID
149NTAPI
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 */
168PVOID
169NTAPI
172{
173 PRTL_BALANCED_LINKS NodeOrParent;
175
176 /* Call the full function */
178 Buffer,
179 (PVOID*)&NodeOrParent,
180 &Lookup);
181}
182
183/*
184 * @implemented
185 */
186PVOID
187NTAPI
190{
191 /* Reset the restart key if needed */
192 if (Restart) Table->RestartKey = NULL;
193
194 /* Call the full function */
196 (PVOID*)&Table->RestartKey);
197}
198
199/*
200* @implemented
201*/
202PVOID
203NTAPI
206 OUT PVOID *RestartKey)
207{
208 PRTL_BALANCED_LINKS Node, PreviousNode;
209 TABLE_SEARCH_RESULT SearchResult;
211
212 /* Assume failure */
213 *RestartKey = NULL;
214
215 /* Find the 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 */
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 */
245PVOID
246NTAPI
248 IN OUT PVOID *RestartKey)
249{
250 PRTL_BALANCED_LINKS CurrentNode;
251
252 /* Skip an empty tree */
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 */
283PVOID
284NTAPI
286 IN ULONG I)
287{
289 return NULL;
290}
291
292/*
293 * @implemented
294 */
296NTAPI
299{
301 TABLE_SEARCH_RESULT SearchResult;
302
303 /* Find the 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++;
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 */
unsigned char BOOLEAN
struct _TABLE_ENTRY_HEADER * PTABLE_ENTRY_HEADER
VOID 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)
Definition: avltable.c:26
PVOID NTAPI RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table, IN OUT PVOID *RestartKey)
Definition: avltable.c:247
BOOLEAN NTAPI RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table, IN PVOID Buffer)
Definition: avltable.c:297
PVOID NTAPI RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table, IN PVOID Buffer)
Definition: avltable.c:170
PVOID 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)
Definition: avltable.c:46
PVOID NTAPI RtlInsertElementGenericTableAvl(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, IN ULONG BufferSize, OUT PBOOLEAN NewElement OPTIONAL)
Definition: avltable.c:103
PVOID NTAPI RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, OUT PVOID *RestartKey)
Definition: avltable.c:204
ULONG NTAPI RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table)
Definition: avltable.c:139
PVOID NTAPI RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table, IN BOOLEAN Restart)
Definition: avltable.c:188
BOOLEAN NTAPI RtlIsGenericTableEmptyAvl(IN PRTL_AVL_TABLE Table)
Definition: avltable.c:128
PVOID NTAPI RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table, IN ULONG I)
Definition: avltable.c:285
PVOID NTAPI RtlLookupElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, IN OUT PVOID *NodeOrParent, IN OUT TABLE_SEARCH_RESULT *SearchResult)
Definition: avltable.c:150
#define UNIMPLEMENTED
Definition: debug.h:118
Definition: bufpool.h:45
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
union node Node
Definition: types.h:1255
static void Lookup(RTF_Info *, char *)
Definition: reader.c:2228
ASMGENDATA Table[]
Definition: genincdata.c:61
#define I(s)
#define RtlpFindAvlTableNodeOrParent
Definition: miavl.h:32
#define RtlpAvlCompareRoutine
Definition: miavl.h:40
#define RtlpInsertAvlTreeNode
Definition: miavl.h:35
#define RtlRightChildAvl
Definition: miavl.h:45
#define RtlParentAvl
Definition: miavl.h:44
#define RtlLeftChildAvl
Definition: miavl.h:46
#define RtlpDeleteAvlTreeNode
Definition: miavl.h:36
#define ASSERT(a)
Definition: mode.c:44
struct tagUserData UserData
#define RtlRealSuccessorAvl(x)
Definition: rtlavl.h:22
#define RtlRealPredecessorAvl(x)
Definition: rtlavl.h:21
@ Restart
Definition: sacdrv.h:269
PULONG MinorVersion OPTIONAL
Definition: CrossNt.h:68
Definition: avlsupp.c:13
#define MAXULONG
Definition: typedefs.h:251
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:255
unsigned char * PBOOLEAN
Definition: typedefs.h:53
#define NTAPI
Definition: typedefs.h:36
#define RtlCopyMemory(Destination, Source, Length)
Definition: typedefs.h:263
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:262
#define IN
Definition: typedefs.h:39
uint32_t ULONG
Definition: typedefs.h:59
#define OUT
Definition: typedefs.h:40
Definition: dlist.c:348
_In_ WDFMEMORY _Out_opt_ size_t * BufferSize
Definition: wdfmemory.h:254
_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:409
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE _In_ PRTL_GENERIC_FREE_ROUTINE _In_opt_ PVOID TableContext
Definition: rtlfuncs.h:1091
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE _In_ PRTL_GENERIC_FREE_ROUTINE FreeRoutine
Definition: rtlfuncs.h:1090
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine
Definition: rtlfuncs.h:1089
_In_ PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine
Definition: rtlfuncs.h:1088
RTL_AVL_FREE_ROUTINE * PRTL_AVL_FREE_ROUTINE
Definition: rtltypes.h:408
TABLE_SEARCH_RESULT
Definition: rtltypes.h:373
RTL_AVL_ALLOCATE_ROUTINE * PRTL_AVL_ALLOCATE_ROUTINE
Definition: rtltypes.h:400
@ GenericEqual
Definition: rtltypes.h:378
RTL_AVL_COMPARE_ROUTINE * PRTL_AVL_COMPARE_ROUTINE
Definition: rtltypes.h:391
enum _RTL_GENERIC_COMPARE_RESULTS RTL_GENERIC_COMPARE_RESULTS