ReactOS 0.4.16-dev-306-g647d351
avltable.c File Reference
#include <rtl.h>
#include <debug.h>
#include "rtlavl.h"
#include "avlsupp.c"
Include dependency graph for avltable.c:

Go to the source code of this file.

Macros

#define NDEBUG
 

Functions

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)
 
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)
 
PVOID NTAPI RtlInsertElementGenericTableAvl (IN PRTL_AVL_TABLE Table, IN PVOID Buffer, IN ULONG BufferSize, OUT PBOOLEAN NewElement OPTIONAL)
 
BOOLEAN NTAPI RtlIsGenericTableEmptyAvl (IN PRTL_AVL_TABLE Table)
 
ULONG NTAPI RtlNumberGenericTableElementsAvl (IN PRTL_AVL_TABLE Table)
 
PVOID NTAPI RtlLookupElementGenericTableFullAvl (IN PRTL_AVL_TABLE Table, IN PVOID Buffer, IN OUT PVOID *NodeOrParent, IN OUT TABLE_SEARCH_RESULT *SearchResult)
 
PVOID NTAPI RtlLookupElementGenericTableAvl (IN PRTL_AVL_TABLE Table, IN PVOID Buffer)
 
PVOID NTAPI RtlEnumerateGenericTableAvl (IN PRTL_AVL_TABLE Table, IN BOOLEAN Restart)
 
PVOID NTAPI RtlLookupFirstMatchingElementGenericTableAvl (IN PRTL_AVL_TABLE Table, IN PVOID Buffer, OUT PVOID *RestartKey)
 
PVOID NTAPI RtlEnumerateGenericTableWithoutSplayingAvl (IN PRTL_AVL_TABLE Table, IN OUT PVOID *RestartKey)
 
PVOID NTAPI RtlGetElementGenericTableAvl (IN PRTL_AVL_TABLE Table, IN ULONG I)
 
BOOLEAN NTAPI RtlDeleteElementGenericTableAvl (IN PRTL_AVL_TABLE Table, IN PVOID Buffer)
 

Macro Definition Documentation

◆ NDEBUG

#define NDEBUG

Definition at line 12 of file avltable.c.

Function Documentation

◆ RtlDeleteElementGenericTableAvl()

BOOLEAN NTAPI RtlDeleteElementGenericTableAvl ( IN PRTL_AVL_TABLE  Table,
IN PVOID  Buffer 
)

Definition at line 297 of file avltable.c.

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}
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
ASMGENDATA Table[]
Definition: genincdata.c:61
#define RtlpFindAvlTableNodeOrParent
Definition: miavl.h:32
#define RtlpDeleteAvlTreeNode
Definition: miavl.h:36
#define RtlRealPredecessorAvl(x)
Definition: rtlavl.h:21
Definition: dlist.c:348
TABLE_SEARCH_RESULT
Definition: rtltypes.h:386

◆ RtlEnumerateGenericTableAvl()

PVOID NTAPI RtlEnumerateGenericTableAvl ( IN PRTL_AVL_TABLE  Table,
IN BOOLEAN  Restart 
)

Definition at line 188 of file avltable.c.

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}
PVOID NTAPI RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table, IN OUT PVOID *RestartKey)
Definition: avltable.c:247
@ Restart
Definition: sacdrv.h:269

◆ RtlEnumerateGenericTableWithoutSplayingAvl()

PVOID NTAPI RtlEnumerateGenericTableWithoutSplayingAvl ( IN PRTL_AVL_TABLE  Table,
IN OUT PVOID RestartKey 
)

Definition at line 247 of file avltable.c.

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}
struct _TABLE_ENTRY_HEADER * PTABLE_ENTRY_HEADER
BOOLEAN NTAPI RtlIsGenericTableEmptyAvl(IN PRTL_AVL_TABLE Table)
Definition: avltable.c:128
#define RtlRightChildAvl
Definition: miavl.h:45
#define RtlLeftChildAvl
Definition: miavl.h:46
#define RtlRealSuccessorAvl(x)
Definition: rtlavl.h:22

Referenced by RtlEnumerateGenericTableAvl().

◆ RtlGetElementGenericTableAvl()

PVOID NTAPI RtlGetElementGenericTableAvl ( IN PRTL_AVL_TABLE  Table,
IN ULONG  I 
)

Definition at line 285 of file avltable.c.

287{
289 return NULL;
290}
#define UNIMPLEMENTED
Definition: ntoskrnl.c:15

◆ RtlInitializeGenericTableAvl()

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 at line 26 of file avltable.c.

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}
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:262
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE _In_ PRTL_GENERIC_FREE_ROUTINE _In_opt_ PVOID TableContext
Definition: rtlfuncs.h:1108
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE _In_ PRTL_GENERIC_FREE_ROUTINE FreeRoutine
Definition: rtlfuncs.h:1107
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine
Definition: rtlfuncs.h:1106
_In_ PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine
Definition: rtlfuncs.h:1105

Referenced by ApphelpCacheInitialize(), PpInitializeDeviceReferenceTable(), and RtlpPageHeapCreate().

◆ RtlInsertElementGenericTableAvl()

PVOID NTAPI RtlInsertElementGenericTableAvl ( IN PRTL_AVL_TABLE  Table,
IN PVOID  Buffer,
IN ULONG  BufferSize,
OUT PBOOLEAN NewElement  OPTIONAL 
)

Definition at line 103 of file avltable.c.

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}
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
_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

◆ RtlInsertElementGenericTableFullAvl()

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 at line 46 of file avltable.c.

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}
#define RtlpInsertAvlTreeNode
Definition: miavl.h:35
#define ASSERT(a)
Definition: mode.c:44
struct tagUserData UserData
Definition: avlsupp.c:13
#define MAXULONG
Definition: typedefs.h:251
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:255
#define RtlCopyMemory(Destination, Source, Length)
Definition: typedefs.h:263

Referenced by RtlInsertElementGenericTableAvl().

◆ RtlIsGenericTableEmptyAvl()

BOOLEAN NTAPI RtlIsGenericTableEmptyAvl ( IN PRTL_AVL_TABLE  Table)

Definition at line 128 of file avltable.c.

129{
130 /* If there's no elements, the table is empty */
131 return Table->NumberGenericTableElements == 0;
132}

Referenced by RtlEnumerateGenericTableWithoutSplayingAvl().

◆ RtlLookupElementGenericTableAvl()

PVOID NTAPI RtlLookupElementGenericTableAvl ( IN PRTL_AVL_TABLE  Table,
IN PVOID  Buffer 
)

Definition at line 170 of file avltable.c.

172{
173 PRTL_BALANCED_LINKS NodeOrParent;
175
176 /* Call the full function */
178 Buffer,
179 (PVOID*)&NodeOrParent,
180 &Lookup);
181}
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
static void Lookup(RTF_Info *, char *)
Definition: reader.c:2228

◆ RtlLookupElementGenericTableFullAvl()

PVOID NTAPI RtlLookupElementGenericTableFullAvl ( IN PRTL_AVL_TABLE  Table,
IN PVOID  Buffer,
IN OUT PVOID NodeOrParent,
IN OUT TABLE_SEARCH_RESULT SearchResult 
)

Definition at line 150 of file avltable.c.

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}

Referenced by RtlLookupElementGenericTableAvl().

◆ RtlLookupFirstMatchingElementGenericTableAvl()

PVOID NTAPI RtlLookupFirstMatchingElementGenericTableAvl ( IN PRTL_AVL_TABLE  Table,
IN PVOID  Buffer,
OUT PVOID RestartKey 
)

Definition at line 204 of file avltable.c.

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}
#define RtlpAvlCompareRoutine
Definition: miavl.h:40
#define RtlParentAvl
Definition: miavl.h:44
@ GenericEqual
Definition: rtltypes.h:391
enum _RTL_GENERIC_COMPARE_RESULTS RTL_GENERIC_COMPARE_RESULTS

◆ RtlNumberGenericTableElementsAvl()

ULONG NTAPI RtlNumberGenericTableElementsAvl ( IN PRTL_AVL_TABLE  Table)

Definition at line 139 of file avltable.c.

140{
141 /* Return the element count */
142 return Table->NumberGenericTableElements;
143}