ReactOS 0.4.15-dev-7924-g5949c20
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 */
16typedef struct _TABLE_ENTRY_HEADER
17{
22
23/* PRIVATE FUNCTIONS *********************************************************/
24
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);
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 */
98VOID
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 */
121PVOID
122NTAPI
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,
138 NewElement,
139 NodeOrParent,
140 Result);
141}
142
143/*
144 * @implemented
145 */
146PVOID
147NTAPI
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 */
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 */
225NTAPI
227{
228 /* Check if the table root is empty */
229 return (Table->TableRoot) ? FALSE: TRUE;
230}
231
232/*
233 * @implemented
234 */
235ULONG
236NTAPI
238{
239 /* Return the number of elements */
240 return Table->NumberGenericTableElements;
241}
242
243/*
244 * @implemented
245 */
246PVOID
247NTAPI
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 */
264PVOID
265NTAPI
268 OUT PVOID *NodeOrParent,
269 OUT TABLE_SEARCH_RESULT *SearchResult)
270{
271 /* Do the initial lookup */
273 Buffer,
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 */
293NTAPI
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 */
325PVOID
326NTAPI
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 */
364PVOID
365NTAPI
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 */
402PVOID
403NTAPI
405 IN PRTL_AVL_MATCH_FUNCTION MatchFunction,
407 IN ULONG NextFlag,
408 IN OUT PVOID *RestartKey,
409 IN OUT PULONG DeleteCount,
411{
413 return 0;
414}
415
416/*
417 * @implemented
418 */
419PVOID
420NTAPI
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 */
unsigned char BOOLEAN
#define UNIMPLEMENTED
Definition: debug.h:115
Definition: bufpool.h:45
#define NULL
Definition: types.h:112
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
#define RemoveEntryList(Entry)
Definition: env_spec_w32.h:986
#define InsertTailList(ListHead, Entry)
#define InitializeListHead(ListHead)
Definition: env_spec_w32.h:944
BOOLEAN NTAPI RtlDeleteElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer)
Definition: generictable.c:294
ULONG NTAPI RtlNumberGenericTableElements(IN PRTL_GENERIC_TABLE Table)
Definition: generictable.c:237
struct _TABLE_ENTRY_HEADER * PTABLE_ENTRY_HEADER
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
TABLE_SEARCH_RESULT NTAPI RtlpFindGenericTableNodeOrParent(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, OUT PRTL_SPLAY_LINKS *NodeOrParent)
Definition: generictable.c:27
PVOID NTAPI RtlEnumerateGenericTableWithoutSplaying(IN PRTL_GENERIC_TABLE Table, IN OUT PVOID *RestartKey)
Definition: generictable.c:366
BOOLEAN NTAPI RtlIsGenericTableEmpty(IN PRTL_GENERIC_TABLE Table)
Definition: generictable.c:226
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
PVOID NTAPI RtlEnumerateGenericTable(IN PRTL_GENERIC_TABLE Table, IN BOOLEAN Restart)
Definition: generictable.c:327
PVOID NTAPI RtlGetElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN ULONG I)
Definition: generictable.c:421
PVOID NTAPI RtlLookupElementGenericTableFull(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, OUT PVOID *NodeOrParent, OUT TABLE_SEARCH_RESULT *SearchResult)
Definition: generictable.c:266
struct _TABLE_ENTRY_HEADER TABLE_ENTRY_HEADER
PVOID NTAPI RtlLookupElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer)
Definition: generictable.c:248
PVOID NTAPI RtlInsertElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, IN ULONG BufferSize, OUT PBOOLEAN NewElement OPTIONAL)
Definition: generictable.c:123
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
ASMGENDATA Table[]
Definition: genincdata.c:61
#define I(s)
#define ASSERT(a)
Definition: mode.c:44
#define _Analysis_assume_(expr)
Definition: ms_sal.h:2901
@ Restart
Definition: sacdrv.h:269
PULONG MinorVersion OPTIONAL
Definition: CrossNt.h:68
Definition: typedefs.h:120
struct _LIST_ENTRY * Blink
Definition: typedefs.h:122
struct _LIST_ENTRY * Flink
Definition: typedefs.h:121
Definition: avlsupp.c:13
RTL_SPLAY_LINKS SplayLinks
Definition: generictable.c:18
LIST_ENTRY ListEntry
Definition: generictable.c:19
LONGLONG UserData
Definition: avlsupp.c:15
#define MAXULONG
Definition: typedefs.h:251
uint32_t * PULONG
Definition: typedefs.h:59
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:255
unsigned char * PBOOLEAN
Definition: typedefs.h:53
int64_t LONGLONG
Definition: typedefs.h:68
#define NTAPI
Definition: typedefs.h:36
#define RtlCopyMemory(Destination, Source, Length)
Definition: typedefs.h:263
#define IN
Definition: typedefs.h:39
#define CONTAINING_RECORD(address, type, field)
Definition: typedefs.h:260
uint32_t ULONG
Definition: typedefs.h:59
#define OUT
Definition: typedefs.h:40
_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
#define RtlRightChild(Links)
#define RtlLeftChild(Links)
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlSplay(_Inout_ PRTL_SPLAY_LINKS Links)
_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
#define RtlInsertAsRightChild(ParentLinks, ChildLinks)
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine
Definition: rtlfuncs.h:1089
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlDelete(_In_ PRTL_SPLAY_LINKS Links)
_In_ PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine
Definition: rtlfuncs.h:1088
#define RtlInitializeSplayLinks(Links)
#define RtlInsertAsLeftChild(ParentLinks, ChildLinks)
_Must_inspect_result_ NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlRealSuccessor(_In_ PRTL_SPLAY_LINKS Links)
TABLE_SEARCH_RESULT
Definition: rtltypes.h:373
_IRQL_requires_same_ _In_ PVOID _In_ PVOID MatchData
Definition: rtltypes.h:416
RTL_GENERIC_FREE_ROUTINE * PRTL_GENERIC_FREE_ROUTINE
Definition: rtltypes.h:475
RTL_AVL_MATCH_FUNCTION * PRTL_AVL_MATCH_FUNCTION
Definition: rtltypes.h:417
RTL_GENERIC_COMPARE_ROUTINE * PRTL_GENERIC_COMPARE_ROUTINE
Definition: rtltypes.h:458
RTL_GENERIC_ALLOCATE_ROUTINE * PRTL_GENERIC_ALLOCATE_ROUTINE
Definition: rtltypes.h:467
@ GenericLessThan
Definition: rtltypes.h:376
@ GenericEqual
Definition: rtltypes.h:378
@ GenericGreaterThan
Definition: rtltypes.h:377
enum _RTL_GENERIC_COMPARE_RESULTS RTL_GENERIC_COMPARE_RESULTS