ReactOS  0.4.14-dev-114-gc8cbd56
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  */
24 VOID
25 NTAPI
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  */
44 PVOID
45 NTAPI
47  IN PVOID Buffer,
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,
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 }
97 
98 /*
99  * @implemented
100  */
101 PVOID
102 NTAPI
104  IN PVOID Buffer,
106  OUT PBOOLEAN NewElement OPTIONAL)
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 }
122 
123 /*
124  * @implemented
125  */
126 BOOLEAN
127 NTAPI
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
140 {
141  /* Return the element count */
142  return Table->NumberGenericTableElements;
143 }
144 
145 /*
146  * @implemented
147  */
148 PVOID
149 NTAPI
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
171  IN PVOID Buffer)
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  */
186 PVOID
187 NTAPI
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 */
202 PVOID
203 NTAPI
205  IN PVOID Buffer,
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 */
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 }
241 
242 /*
243  * @unimplemented
244  */
245 PVOID
246 NTAPI
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
286  IN ULONG I)
287 {
289  return NULL;
290 }
291 
292 /*
293  * @implemented
294  */
295 BOOLEAN
296 NTAPI
298  IN PVOID Buffer)
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 }
325 
326 /* EOF */
FORCEINLINE VOID RtlpDeleteAvlTreeNode(IN PRTL_AVL_TABLE Table, IN PRTL_BALANCED_LINKS Node)
Definition: avlsupp.c:295
#define IN
Definition: typedefs.h:38
RTL_AVL_COMPARE_ROUTINE * PRTL_AVL_COMPARE_ROUTINE
Definition: rtltypes.h:381
ASMGENDATA Table[]
Definition: genincdata.c:61
#define TRUE
Definition: types.h:120
NTSYSAPI VOID NTAPI RtlCopyMemory(VOID UNALIGNED *Destination, CONST VOID UNALIGNED *Source, ULONG Length)
#define RtlRealPredecessorAvl(x)
Definition: rtlavl.h:21
enum _TABLE_SEARCH_RESULT TABLE_SEARCH_RESULT
#define RtlRightChildAvl
Definition: miavl.h:45
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE _In_ PRTL_GENERIC_FREE_ROUTINE _In_opt_ PVOID TableContext
Definition: rtlfuncs.h:1089
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
BOOLEAN NTAPI RtlIsGenericTableEmptyAvl(IN PRTL_AVL_TABLE Table)
Definition: avltable.c:128
static void Lookup(RTF_Info *, char *)
Definition: reader.c:2228
NTSTATUS(* NTAPI)(IN PFILE_FULL_EA_INFORMATION EaBuffer, IN ULONG EaLength, OUT PULONG ErrorOffset)
Definition: IoEaTest.cpp:117
union node Node
Definition: types.h:1255
_In_ PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine
Definition: rtlfuncs.h:1089
PVOID NTAPI RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table, IN OUT PVOID *RestartKey)
Definition: avltable.c:247
unsigned char BOOLEAN
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
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE _In_ PRTL_GENERIC_FREE_ROUTINE FreeRoutine
Definition: rtlfuncs.h:1089
Definition: bufpool.h:45
PVOID NTAPI RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table, IN BOOLEAN Restart)
Definition: avltable.c:188
PVOID NTAPI RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table, IN PVOID Buffer)
Definition: avltable.c:170
ULONG NTAPI RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table)
Definition: avltable.c:139
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
char * PBOOLEAN
Definition: retypes.h:11
#define RtlRealSuccessorAvl(x)
Definition: rtlavl.h:22
#define I(s)
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
RTL_AVL_FREE_ROUTINE * PRTL_AVL_FREE_ROUTINE
Definition: rtltypes.h:398
FORCEINLINE TABLE_SEARCH_RESULT RtlpFindAvlTableNodeOrParent(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, OUT PRTL_BALANCED_LINKS *NodeOrParent)
Definition: avlsupp.c:32
#define MAXULONG
Definition: typedefs.h:250
#define RtlLeftChildAvl
Definition: miavl.h:46
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:254
PVOID NTAPI RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, OUT PVOID *RestartKey)
Definition: avltable.c:204
PVOID NTAPI RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table, IN ULONG I)
Definition: avltable.c:285
enum _RTL_GENERIC_COMPARE_RESULTS RTL_GENERIC_COMPARE_RESULTS
BOOLEAN NTAPI RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table, IN PVOID Buffer)
Definition: avltable.c:297
#define OUT
Definition: typedefs.h:39
unsigned int ULONG
Definition: retypes.h:1
#define UNIMPLEMENTED
Definition: debug.h:114
#define RtlZeroMemory(Destination, Length)
Definition: typedefs.h:261
FORCEINLINE RTL_GENERIC_COMPARE_RESULTS RtlpAvlCompareRoutine(IN PRTL_AVL_TABLE Table, IN PVOID Buffer, IN PVOID UserData)
Definition: rtlavl.h:37
RTL_AVL_ALLOCATE_ROUTINE * PRTL_AVL_ALLOCATE_ROUTINE
Definition: rtltypes.h:390
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
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine
Definition: rtlfuncs.h:1089
#define RtlParentAvl
Definition: miavl.h:44
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
Definition: dlist.c:348
PULONG MinorVersion OPTIONAL
Definition: CrossNt.h:68