ReactOS  0.4.14-dev-358-gbef841c
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 */
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++;
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 }
FORCEINLINE VOID RtlpDeleteAvlTreeNode(IN PRTL_AVL_TABLE Table, IN PRTL_BALANCED_LINKS Node)
Definition: avlsupp.c:295
ASMGENDATA Table[]
Definition: genincdata.c:61
#define TRUE
Definition: types.h:120
#define RtlRealPredecessorAvl(x)
Definition: rtlavl.h:21
enum _TABLE_SEARCH_RESULT TABLE_SEARCH_RESULT
union node Node
Definition: types.h:1255
smooth NULL
Definition: ftsmooth.c:416
Definition: bufpool.h:45
FORCEINLINE TABLE_SEARCH_RESULT RtlpFindAvlTableNodeOrParent(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, OUT PRTL_BALANCED_LINKS *NodeOrParent)
Definition: avlsupp.c:32
Definition: dlist.c:348

◆ 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 }
ASMGENDATA Table[]
Definition: genincdata.c:61
PVOID NTAPI RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table, IN OUT PVOID *RestartKey)
Definition: avltable.c:247
smooth NULL
Definition: ftsmooth.c:416

◆ 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 */
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 }
ASMGENDATA Table[]
Definition: genincdata.c:61
#define RtlRightChildAvl
Definition: miavl.h:45
BOOLEAN NTAPI RtlIsGenericTableEmptyAvl(IN PRTL_AVL_TABLE Table)
Definition: avltable.c:128
smooth NULL
Definition: ftsmooth.c:416
struct _TABLE_ENTRY_HEADER * PTABLE_ENTRY_HEADER
#define RtlRealSuccessorAvl(x)
Definition: rtlavl.h:22
#define RtlLeftChildAvl
Definition: miavl.h:46

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 }
smooth NULL
Definition: ftsmooth.c:416
#define UNIMPLEMENTED
Definition: debug.h:114

◆ 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 }
ASMGENDATA Table[]
Definition: genincdata.c:61
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE _In_ PRTL_GENERIC_FREE_ROUTINE _In_opt_ PVOID TableContext
Definition: rtlfuncs.h:1089
_In_ PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine
Definition: rtlfuncs.h:1089
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE _In_ PRTL_GENERIC_FREE_ROUTINE FreeRoutine
Definition: rtlfuncs.h:1089
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine
Definition: rtlfuncs.h:1089

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 */
112  Result = RtlpFindAvlTableNodeOrParent(Table, Buffer, &NodeOrParent);
113 
114  /* Now call the routine to do the full insert */
116  Buffer,
117  BufferSize,
118  NewElement,
119  NodeOrParent,
120  Result);
121 }
ASMGENDATA Table[]
Definition: genincdata.c:61
enum _TABLE_SEARCH_RESULT TABLE_SEARCH_RESULT
smooth NULL
Definition: ftsmooth.c:416
_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:426
Definition: bufpool.h:45
#define BufferSize
Definition: classpnp.h:419
FORCEINLINE TABLE_SEARCH_RESULT RtlpFindAvlTableNodeOrParent(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, OUT PRTL_BALANCED_LINKS *NodeOrParent)
Definition: avlsupp.c:32
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

◆ 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,
64  BufferSize +
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 }
ASMGENDATA Table[]
Definition: genincdata.c:61
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
FORCEINLINE VOID RtlpInsertAvlTreeNode(IN PRTL_AVL_TABLE Table, IN PRTL_BALANCED_LINKS NewNode, IN OUT PVOID NodeOrParent, IN OUT TABLE_SEARCH_RESULT SearchResult)
Definition: avlsupp.c:208
smooth NULL
Definition: ftsmooth.c:416
Definition: bufpool.h:45
struct tagUserData UserData
Definition: avlsupp.c:12
#define BufferSize
Definition: classpnp.h:419
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
struct _TABLE_ENTRY_HEADER * PTABLE_ENTRY_HEADER
#define MAXULONG
Definition: typedefs.h:250
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:254
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261

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 }
ASMGENDATA Table[]
Definition: genincdata.c:61

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 }
ASMGENDATA Table[]
Definition: genincdata.c:61
enum _TABLE_SEARCH_RESULT TABLE_SEARCH_RESULT
static void Lookup(RTF_Info *, char *)
Definition: reader.c:2228
Definition: bufpool.h:45
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

◆ 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 }
ASMGENDATA Table[]
Definition: genincdata.c:61
smooth NULL
Definition: ftsmooth.c:416
Definition: bufpool.h:45
struct _TABLE_ENTRY_HEADER * PTABLE_ENTRY_HEADER
FORCEINLINE TABLE_SEARCH_RESULT RtlpFindAvlTableNodeOrParent(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, OUT PRTL_BALANCED_LINKS *NodeOrParent)
Definition: avlsupp.c:32

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 */
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 */
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 }
ASMGENDATA Table[]
Definition: genincdata.c:61
#define RtlRealPredecessorAvl(x)
Definition: rtlavl.h:21
enum _TABLE_SEARCH_RESULT TABLE_SEARCH_RESULT
union node Node
Definition: types.h:1255
smooth NULL
Definition: ftsmooth.c:416
_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:426
Definition: bufpool.h:45
Definition: avlsupp.c:12
struct _TABLE_ENTRY_HEADER * PTABLE_ENTRY_HEADER
FORCEINLINE TABLE_SEARCH_RESULT RtlpFindAvlTableNodeOrParent(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, OUT PRTL_BALANCED_LINKS *NodeOrParent)
Definition: avlsupp.c:32
enum _RTL_GENERIC_COMPARE_RESULTS RTL_GENERIC_COMPARE_RESULTS
FORCEINLINE RTL_GENERIC_COMPARE_RESULTS RtlpAvlCompareRoutine(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, IN PVOID UserData)
Definition: rtlavl.h:37
#define RtlParentAvl
Definition: miavl.h:44
Definition: dlist.c:348

◆ 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 }
ASMGENDATA Table[]
Definition: genincdata.c:61