ReactOS  0.4.14-dev-323-g6fe6a88
generictable.c
Go to the documentation of this file.
1 /*
2  * PROJECT: ReactOS Runtime Library
3  * LICENSE: GPL - See COPYING in the top level directory
4  * FILE: lib/rtl/generictable.c
5  * PURPOSE: Splay Tree Generic Table Implementation
6  * PROGRAMMERS: Alex Ionescu (alex.ionescu@reactos.org)
7  */
8 
9 /* INCLUDES ******************************************************************/
10 
11 #include <rtl.h>
12 #define NDEBUG
13 #include <debug.h>
14 
15 /* Internal header for table entries */
16 typedef struct _TABLE_ENTRY_HEADER
17 {
22 
23 /* PRIVATE FUNCTIONS *********************************************************/
24 
26 NTAPI
28  IN PVOID Buffer,
29  OUT PRTL_SPLAY_LINKS *NodeOrParent)
30 {
31  PRTL_SPLAY_LINKS CurrentNode, ChildNode;
33 
34  /* Quick check to see if the table is empty */
36  {
37  return TableEmptyTree;
38  }
39 
40  /* Set the current node */
41  CurrentNode = Table->TableRoot;
42 
43  /* Start compare loop */
44  while (TRUE)
45  {
46  /* Do the compare */
47  Result = Table->CompareRoutine(Table,
48  Buffer,
49  &((PTABLE_ENTRY_HEADER)CurrentNode)->
50  UserData);
51  if (Result == GenericLessThan)
52  {
53  /* We're less, check if this is the left child */
54  if ((ChildNode = RtlLeftChild(CurrentNode)))
55  {
56  /* Continue searching from this node */
57  CurrentNode = ChildNode;
58  }
59  else
60  {
61  /* Otherwise, the element isn't in this tree */
62  *NodeOrParent = CurrentNode;
63  return TableInsertAsLeft;
64  }
65  }
66  else if (Result == GenericGreaterThan)
67  {
68  /* We're more, check if this is the right child */
69  if ((ChildNode = RtlRightChild(CurrentNode)))
70  {
71  /* Continue searching from this node */
72  CurrentNode = ChildNode;
73  }
74  else
75  {
76  /* Otherwise, the element isn't in this tree */
77  *NodeOrParent = CurrentNode;
78  return TableInsertAsRight;
79  }
80  }
81  else
82  {
83  /* We should've found the node */
85 
86  /* Return node found */
87  *NodeOrParent = CurrentNode;
88  return TableFoundNode;
89  }
90  }
91 }
92 
93 /* SPLAY FUNCTIONS ***********************************************************/
94 
95 /*
96  * @implemented
97  */
98 VOID
99 NTAPI
105 {
106  /* Initialize the table to default and passed values */
107  InitializeListHead(&Table->InsertOrderList);
108  Table->TableRoot = NULL;
109  Table->NumberGenericTableElements = 0;
110  Table->WhichOrderedElement = 0;
111  Table->OrderedPointer = &Table->InsertOrderList;
112  Table->CompareRoutine = CompareRoutine;
113  Table->AllocateRoutine = AllocateRoutine;
114  Table->FreeRoutine = FreeRoutine;
115  Table->TableContext = TableContext;
116 }
117 
118 /*
119  * @implemented
120  */
121 PVOID
122 NTAPI
124  IN PVOID Buffer,
126  OUT PBOOLEAN NewElement OPTIONAL)
127 {
128  PRTL_SPLAY_LINKS NodeOrParent;
130 
131  /* Get the splay links and table search result immediately */
133 
134  /* Now call the routine to do the full insert */
136  Buffer,
137  BufferSize,
138  NewElement,
139  NodeOrParent,
140  Result);
141 }
142 
143 /*
144  * @implemented
145  */
146 PVOID
147 NTAPI
149  IN PVOID Buffer,
151  OUT PBOOLEAN NewElement OPTIONAL,
152  IN PVOID NodeOrParent,
153  IN TABLE_SEARCH_RESULT SearchResult)
154 {
155  PRTL_SPLAY_LINKS NewNode;
156 
157  /* Check if the entry wasn't already found */
158  if (SearchResult != TableFoundNode)
159  {
160  /* We're doing an allocation, sanity check */
161  ASSERT(Table->NumberGenericTableElements != (MAXULONG - 1));
162 
163  /* Allocate a node */
164  NewNode = Table->AllocateRoutine(Table,
165  BufferSize +
167  UserData));
168  if (!NewNode)
169  {
170  /* No memory or other allocation error, fail */
171  if (NewElement) *NewElement = FALSE;
172  return NULL;
173  }
174 
175  /* Initialize the new inserted element */
176  RtlInitializeSplayLinks(NewNode);
177  InsertTailList(&Table->InsertOrderList,
178  &((PTABLE_ENTRY_HEADER)NewNode)->ListEntry);
179 
180  /* Increase element count */
181  Table->NumberGenericTableElements++;
182 
183  /* Check where we should insert the entry */
184  if (SearchResult == TableEmptyTree)
185  {
186  /* This is the new root node */
187  Table->TableRoot = NewNode;
188  }
189  else if (SearchResult == TableInsertAsLeft)
190  {
191  /* Insert it left */
192  RtlInsertAsLeftChild(NodeOrParent, NewNode);
193  }
194  else
195  {
196  /* Right node */
197  RtlInsertAsRightChild(NodeOrParent, NewNode);
198  }
199 
200  /* Copy user buffer */
202  Buffer,
203  BufferSize);
204  }
205  else
206  {
207  /* Return the node we already found */
208  NewNode = NodeOrParent;
209  }
210 
211  /* Splay the tree */
212  Table->TableRoot = RtlSplay(NewNode);
213 
214  /* Return status */
215  if (NewElement) *NewElement = (SearchResult != TableFoundNode);
216 
217  /* Return pointer to user data */
218  return &((PTABLE_ENTRY_HEADER)NewNode)->UserData;
219 }
220 
221 /*
222  * @implemented
223  */
224 BOOLEAN
225 NTAPI
227 {
228  /* Check if the table root is empty */
229  return (Table->TableRoot) ? FALSE: TRUE;
230 }
231 
232 /*
233  * @implemented
234  */
235 ULONG
236 NTAPI
238 {
239  /* Return the number of elements */
240  return Table->NumberGenericTableElements;
241 }
242 
243 /*
244  * @implemented
245  */
246 PVOID
247 NTAPI
249  IN PVOID Buffer)
250 {
251  PRTL_SPLAY_LINKS NodeOrParent;
253 
254  /* Call the full version */
256  Buffer,
257  (PVOID)&NodeOrParent,
258  &Result);
259 }
260 
261 /*
262  * @implemented
263  */
264 PVOID
265 NTAPI
267  IN PVOID Buffer,
268  OUT PVOID *NodeOrParent,
269  OUT TABLE_SEARCH_RESULT *SearchResult)
270 {
271  /* Do the initial lookup */
272  *SearchResult = RtlpFindGenericTableNodeOrParent(Table,
273  Buffer,
274  (PRTL_SPLAY_LINKS *)
275  NodeOrParent);
276 
277  /* Check if we found anything */
278  if ((*SearchResult == TableEmptyTree) || (*SearchResult != TableFoundNode))
279  {
280  /* Nothing found */
281  return NULL;
282  }
283 
284  /* Otherwise, splay the tree and return this entry */
285  Table->TableRoot = RtlSplay(*NodeOrParent);
286  return &((PTABLE_ENTRY_HEADER)*NodeOrParent)->UserData;
287 }
288 
289 /*
290  * @implemented
291  */
292 BOOLEAN
293 NTAPI
295  IN PVOID Buffer)
296 {
297  PRTL_SPLAY_LINKS NodeOrParent;
299 
300  /* Get the splay links and table search result immediately */
302  if (Result != TableFoundNode)
303  {
304  /* Nothing to delete */
305  return FALSE;
306  }
307 
308  /* Delete the entry */
309  Table->TableRoot = RtlDelete(NodeOrParent);
310  RemoveEntryList(&((PTABLE_ENTRY_HEADER)NodeOrParent)->ListEntry);
311 
312  /* Update accounting data */
313  Table->NumberGenericTableElements--;
314  Table->WhichOrderedElement = 0;
315  Table->OrderedPointer = &Table->InsertOrderList;
316 
317  /* Free the entry */
318  Table->FreeRoutine(Table, NodeOrParent);
319  return TRUE;
320 }
321 
322 /*
323  * @implemented
324  */
325 PVOID
326 NTAPI
329 {
330  PRTL_SPLAY_LINKS FoundNode;
331 
332  /* Check if the table is empty */
333  if (RtlIsGenericTableEmpty(Table)) return NULL;
334 
335  /* Check if we have to restart */
336  if (Restart)
337  {
338  /* Then find the leftmost element */
339  FoundNode = Table->TableRoot;
340  while(RtlLeftChild(FoundNode))
341  {
342  /* Get the left child */
343  FoundNode = RtlLeftChild(FoundNode);
344  }
345 
346  /* Splay it */
347  _Analysis_assume_(FoundNode != NULL);
348  Table->TableRoot = RtlSplay(FoundNode);
349  }
350  else
351  {
352  /* Otherwise, try using the real successor */
353  FoundNode = RtlRealSuccessor(Table->TableRoot);
354  if (FoundNode) Table->TableRoot = RtlSplay(FoundNode);
355  }
356 
357  /* Check if we found the node and return it */
358  return FoundNode ? &((PTABLE_ENTRY_HEADER)FoundNode)->UserData : NULL;
359 }
360 
361 /*
362  * @implemented
363  */
364 PVOID
365 NTAPI
367  IN OUT PVOID *RestartKey)
368 {
369  PRTL_SPLAY_LINKS FoundNode;
370 
371  /* Check if the table is empty */
372  if (RtlIsGenericTableEmpty(Table)) return NULL;
373 
374  /* Check if we have to restart */
375  if (!(*RestartKey))
376  {
377  /* Then find the leftmost element */
378  FoundNode = Table->TableRoot;
379  while(RtlLeftChild(FoundNode))
380  {
381  /* Get the left child */
382  FoundNode = RtlLeftChild(FoundNode);
383  }
384 
385  /* Splay it */
386  *RestartKey = FoundNode;
387  }
388  else
389  {
390  /* Otherwise, try using the real successor */
391  FoundNode = RtlRealSuccessor(*RestartKey);
392  if (FoundNode) *RestartKey = FoundNode;
393  }
394 
395  /* Check if we found the node and return it */
396  return FoundNode ? &((PTABLE_ENTRY_HEADER)FoundNode)->UserData : NULL;
397 }
398 
399 /*
400  * @unimplemented
401  */
402 PVOID
403 NTAPI
405  IN PRTL_AVL_MATCH_FUNCTION MatchFunction,
407  IN ULONG NextFlag,
408  IN OUT PVOID *RestartKey,
409  IN OUT PULONG DeleteCount,
410  IN OUT PVOID Buffer)
411 {
413  return 0;
414 }
415 
416 /*
417  * @implemented
418  */
419 PVOID
420 NTAPI
422  IN ULONG I)
423 {
424  ULONG OrderedElement, ElementCount;
425  PLIST_ENTRY OrderedNode;
426  ULONG DeltaUp, DeltaDown;
427  ULONG NextI = I + 1;
428 
429  /* Setup current accounting data */
430  OrderedNode = Table->OrderedPointer;
431  OrderedElement = Table->WhichOrderedElement;
432  ElementCount = Table->NumberGenericTableElements;
433 
434  /* Sanity checks */
435  if ((I == MAXULONG) || (NextI > ElementCount)) return NULL;
436 
437  /* Check if we already found the entry */
438  if (NextI == OrderedElement)
439  {
440  /* Return it */
441  return &CONTAINING_RECORD(OrderedNode,
443  ListEntry)->UserData;
444  }
445 
446  /* Now check if we're farther behind */
447  if (OrderedElement > NextI)
448  {
449  /* Find out if the distance is more then the half-way point */
450  if (NextI > (OrderedElement / 2))
451  {
452  /* Do the search backwards, since this takes less iterations */
453  DeltaDown = OrderedElement - NextI;
454  while (DeltaDown)
455  {
456  /* Get next node */
457  OrderedNode = OrderedNode->Blink;
458  DeltaDown--;
459  }
460  }
461  else
462  {
463  /* Follow the list directly instead */
464  OrderedNode = &Table->InsertOrderList;
465  while (NextI)
466  {
467  /* Get next node */
468  OrderedNode = OrderedNode->Flink;
469  NextI--;
470  }
471  }
472  }
473  else
474  {
475  /* We are farther ahead, calculate distances */
476  DeltaUp = NextI - OrderedElement;
477  DeltaDown = (ElementCount - NextI) + 1;
478 
479  /* Check if the up distance is smaller then the down distance */
480  if (DeltaUp <= DeltaDown)
481  {
482  /* Do the search forwards, since this takes less iterations */
483  while (DeltaUp)
484  {
485  /* Get next node */
486  OrderedNode = OrderedNode->Blink;
487  DeltaUp--;
488  }
489  }
490  else
491  {
492  /* Do the search downwards, since this takes less iterations */
493  OrderedNode = &Table->InsertOrderList;
494  while (DeltaDown)
495  {
496  /* Get next node */
497  OrderedNode = OrderedNode->Blink;
498  DeltaDown--;
499  }
500  }
501  }
502 
503  /* Got the element, save it */
504  Table->OrderedPointer = OrderedNode;
505  Table->WhichOrderedElement = NextI;
506 
507  /* Return the element */
508  return &CONTAINING_RECORD(OrderedNode,
510  ListEntry)->UserData;
511 }
512 
513 /* EOF */
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlSplay(_Inout_ PRTL_SPLAY_LINKS Links)
RTL_GENERIC_COMPARE_ROUTINE * PRTL_GENERIC_COMPARE_ROUTINE
Definition: rtltypes.h:448
PVOID NTAPI RtlEnumerateGenericTableLikeADirectory(IN PRTL_AVL_TABLE Table, IN PRTL_AVL_MATCH_FUNCTION MatchFunction, IN PVOID MatchData, IN ULONG NextFlag, IN OUT PVOID *RestartKey, IN OUT PULONG DeleteCount, IN OUT PVOID Buffer)
Definition: generictable.c:404
#define IN
Definition: typedefs.h:38
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)
RTL_GENERIC_ALLOCATE_ROUTINE * PRTL_GENERIC_ALLOCATE_ROUTINE
Definition: rtltypes.h:457
PVOID NTAPI RtlEnumerateGenericTableWithoutSplaying(IN PRTL_GENERIC_TABLE Table, IN OUT PVOID *RestartKey)
Definition: generictable.c:366
PVOID NTAPI RtlInsertElementGenericTableFull(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, IN ULONG BufferSize, OUT PBOOLEAN NewElement OPTIONAL, IN PVOID NodeOrParent, IN TABLE_SEARCH_RESULT SearchResult)
Definition: generictable.c:148
struct _LIST_ENTRY * Blink
Definition: typedefs.h:120
#define RtlInsertAsRightChild(ParentLinks, ChildLinks)
enum _TABLE_SEARCH_RESULT TABLE_SEARCH_RESULT
PVOID NTAPI RtlGetElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN ULONG I)
Definition: generictable.c:421
LONGLONG UserData
Definition: avlsupp.c:15
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE _In_ PRTL_GENERIC_FREE_ROUTINE _In_opt_ PVOID TableContext
Definition: rtlfuncs.h:1089
#define InsertTailList(ListHead, Entry)
VOID NTAPI RtlInitializeGenericTable(IN PRTL_GENERIC_TABLE Table, IN PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine, IN PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine, IN PRTL_GENERIC_FREE_ROUTINE FreeRoutine, IN PVOID TableContext)
Definition: generictable.c:100
#define RtlInsertAsLeftChild(ParentLinks, ChildLinks)
FORCEINLINE BOOLEAN RemoveEntryList(_In_ PLIST_ENTRY Entry)
Definition: rtlfuncs.h:105
PVOID NTAPI RtlInsertElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, IN ULONG BufferSize, OUT PBOOLEAN NewElement OPTIONAL)
Definition: generictable.c:123
PVOID NTAPI RtlLookupElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer)
Definition: generictable.c:248
NTSTATUS(* NTAPI)(IN PFILE_FULL_EA_INFORMATION EaBuffer, IN ULONG EaLength, OUT PULONG ErrorOffset)
Definition: IoEaTest.cpp:117
_In_ PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine
Definition: rtlfuncs.h:1089
RTL_GENERIC_FREE_ROUTINE * PRTL_GENERIC_FREE_ROUTINE
Definition: rtltypes.h:465
#define RtlInitializeSplayLinks(Links)
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
PVOID NTAPI RtlEnumerateGenericTable(IN PRTL_GENERIC_TABLE Table, IN BOOLEAN Restart)
Definition: generictable.c:327
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE _In_ PRTL_GENERIC_FREE_ROUTINE FreeRoutine
Definition: rtlfuncs.h:1089
Definition: bufpool.h:45
PFLT_MESSAGE_WAITER_QUEUE CONTAINING_RECORD(Csq, DEVICE_EXTENSION, IrpQueue)) -> WaiterQ.mLock) _IRQL_raises_(DISPATCH_LEVEL) VOID NTAPI FltpAcquireMessageWaiterLock(_In_ PIO_CSQ Csq, _Out_ PKIRQL Irql)
Definition: Messaging.c:560
BOOLEAN NTAPI RtlDeleteElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer)
Definition: generictable.c:294
int64_t LONGLONG
Definition: typedefs.h:66
struct _LIST_ENTRY * Flink
Definition: typedefs.h:119
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlDelete(_In_ PRTL_SPLAY_LINKS Links)
struct _TABLE_ENTRY_HEADER * PTABLE_ENTRY_HEADER
Definition: avlsupp.c:12
#define BufferSize
Definition: classpnp.h:419
#define RtlLeftChild(Links)
RTL_AVL_MATCH_FUNCTION * PRTL_AVL_MATCH_FUNCTION
Definition: rtltypes.h:407
ASSERT((InvokeOnSuccess||InvokeOnError||InvokeOnCancel) ?(CompletionRoutine !=NULL) :TRUE)
ULONG NTAPI RtlNumberGenericTableElements(IN PRTL_GENERIC_TABLE Table)
Definition: generictable.c:237
char * PBOOLEAN
Definition: retypes.h:11
LIST_ENTRY ListEntry
Definition: generictable.c:19
#define I(s)
Definition: typedefs.h:117
BOOLEAN NTAPI RtlIsGenericTableEmpty(IN PRTL_GENERIC_TABLE Table)
Definition: generictable.c:226
#define MAXULONG
Definition: typedefs.h:250
TABLE_SEARCH_RESULT NTAPI RtlpFindGenericTableNodeOrParent(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, OUT PRTL_SPLAY_LINKS *NodeOrParent)
Definition: generictable.c:27
#define InitializeListHead(ListHead)
Definition: env_spec_w32.h:944
_IRQL_requires_same_ _In_ PVOID _In_ PVOID MatchData
Definition: rtltypes.h:405
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:254
unsigned int * PULONG
Definition: retypes.h:1
RTL_SPLAY_LINKS SplayLinks
Definition: generictable.c:18
enum _RTL_GENERIC_COMPARE_RESULTS RTL_GENERIC_COMPARE_RESULTS
#define OUT
Definition: typedefs.h:39
unsigned int ULONG
Definition: retypes.h:1
#define UNIMPLEMENTED
Definition: debug.h:114
#define RtlRightChild(Links)
_Must_inspect_result_ NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlRealSuccessor(_In_ PRTL_SPLAY_LINKS Links)
PVOID NTAPI RtlLookupElementGenericTableFull(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, OUT PVOID *NodeOrParent, OUT TABLE_SEARCH_RESULT *SearchResult)
Definition: generictable.c:266
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine
Definition: rtlfuncs.h:1089
struct _TABLE_ENTRY_HEADER TABLE_ENTRY_HEADER
#define _Analysis_assume_(expr)
Definition: no_sal2.h:10
PULONG MinorVersion OPTIONAL
Definition: CrossNt.h:68