ReactOS 0.4.15-dev-5669-g09dde2c
generictable.c File Reference
#include <rtl.h>
#include <debug.h>
Include dependency graph for generictable.c:

Go to the source code of this file.

Classes

struct  _TABLE_ENTRY_HEADER
 

Macros

#define NDEBUG
 

Typedefs

typedef struct _TABLE_ENTRY_HEADER TABLE_ENTRY_HEADER
 
typedef struct _TABLE_ENTRY_HEADERPTABLE_ENTRY_HEADER
 

Functions

TABLE_SEARCH_RESULT NTAPI RtlpFindGenericTableNodeOrParent (IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, OUT PRTL_SPLAY_LINKS *NodeOrParent)
 
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)
 
PVOID NTAPI RtlInsertElementGenericTable (IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, IN ULONG BufferSize, OUT PBOOLEAN NewElement OPTIONAL)
 
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)
 
BOOLEAN NTAPI RtlIsGenericTableEmpty (IN PRTL_GENERIC_TABLE Table)
 
ULONG NTAPI RtlNumberGenericTableElements (IN PRTL_GENERIC_TABLE Table)
 
PVOID NTAPI RtlLookupElementGenericTable (IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer)
 
PVOID NTAPI RtlLookupElementGenericTableFull (IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, OUT PVOID *NodeOrParent, OUT TABLE_SEARCH_RESULT *SearchResult)
 
BOOLEAN NTAPI RtlDeleteElementGenericTable (IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer)
 
PVOID NTAPI RtlEnumerateGenericTable (IN PRTL_GENERIC_TABLE Table, IN BOOLEAN Restart)
 
PVOID NTAPI RtlEnumerateGenericTableWithoutSplaying (IN PRTL_GENERIC_TABLE Table, IN OUT PVOID *RestartKey)
 
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)
 
PVOID NTAPI RtlGetElementGenericTable (IN PRTL_GENERIC_TABLE Table, IN ULONG I)
 

Macro Definition Documentation

◆ NDEBUG

#define NDEBUG

Definition at line 12 of file generictable.c.

Typedef Documentation

◆ PTABLE_ENTRY_HEADER

◆ TABLE_ENTRY_HEADER

Function Documentation

◆ RtlDeleteElementGenericTable()

BOOLEAN NTAPI RtlDeleteElementGenericTable ( IN PRTL_GENERIC_TABLE  Table,
IN PVOID  Buffer 
)

Definition at line 294 of file generictable.c.

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}
Definition: bufpool.h:45
#define TRUE
Definition: types.h:120
#define FALSE
Definition: types.h:117
#define RemoveEntryList(Entry)
Definition: env_spec_w32.h:986
TABLE_SEARCH_RESULT NTAPI RtlpFindGenericTableNodeOrParent(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, OUT PRTL_SPLAY_LINKS *NodeOrParent)
Definition: generictable.c:27
ASMGENDATA Table[]
Definition: genincdata.c:61
Definition: avlsupp.c:13
_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
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlDelete(_In_ PRTL_SPLAY_LINKS Links)
@ TableFoundNode
Definition: rtltypes.h:364
enum _TABLE_SEARCH_RESULT TABLE_SEARCH_RESULT

◆ RtlEnumerateGenericTable()

PVOID NTAPI RtlEnumerateGenericTable ( IN PRTL_GENERIC_TABLE  Table,
IN BOOLEAN  Restart 
)

Definition at line 327 of file generictable.c.

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}
#define NULL
Definition: types.h:112
struct _TABLE_ENTRY_HEADER * PTABLE_ENTRY_HEADER
BOOLEAN NTAPI RtlIsGenericTableEmpty(IN PRTL_GENERIC_TABLE Table)
Definition: generictable.c:226
#define _Analysis_assume_(expr)
Definition: ms_sal.h:2901
@ Restart
Definition: sacdrv.h:269
#define RtlLeftChild(Links)
NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlSplay(_Inout_ PRTL_SPLAY_LINKS Links)
_Must_inspect_result_ NTSYSAPI PRTL_SPLAY_LINKS NTAPI RtlRealSuccessor(_In_ PRTL_SPLAY_LINKS Links)

◆ RtlEnumerateGenericTableLikeADirectory()

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 at line 404 of file generictable.c.

411{
413 return 0;
414}
#define UNIMPLEMENTED
Definition: debug.h:115

◆ RtlEnumerateGenericTableWithoutSplaying()

PVOID NTAPI RtlEnumerateGenericTableWithoutSplaying ( IN PRTL_GENERIC_TABLE  Table,
IN OUT PVOID RestartKey 
)

Definition at line 366 of file generictable.c.

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}

◆ RtlGetElementGenericTable()

PVOID NTAPI RtlGetElementGenericTable ( IN PRTL_GENERIC_TABLE  Table,
IN ULONG  I 
)

Definition at line 421 of file generictable.c.

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}
#define I(s)
Definition: typedefs.h:120
struct _LIST_ENTRY * Blink
Definition: typedefs.h:122
struct _LIST_ENTRY * Flink
Definition: typedefs.h:121
#define MAXULONG
Definition: typedefs.h:251
#define CONTAINING_RECORD(address, type, field)
Definition: typedefs.h:260
uint32_t ULONG
Definition: typedefs.h:59

◆ RtlInitializeGenericTable()

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 at line 100 of file generictable.c.

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}
#define InitializeListHead(ListHead)
Definition: env_spec_w32.h:944
_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
_In_ PRTL_GENERIC_COMPARE_ROUTINE _In_ PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine
Definition: rtlfuncs.h:1089
_In_ PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine
Definition: rtlfuncs.h:1088

Referenced by CdInitializeVcb(), ClasspInitializeRemoveTracking(), FsRtlInitializeBaseMcb(), FsRtlPrivateLock(), MiInitializeSectionPageTable(), NpInitializeVcb(), and RtlSplayTreeTest().

◆ RtlInsertElementGenericTable()

PVOID NTAPI RtlInsertElementGenericTable ( IN PRTL_GENERIC_TABLE  Table,
IN PVOID  Buffer,
IN ULONG  BufferSize,
OUT PBOOLEAN NewElement  OPTIONAL 
)

Definition at line 123 of file generictable.c.

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}
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
_In_ WDFMEMORY _Out_opt_ size_t * BufferSize
Definition: wdfmemory.h:254

◆ RtlInsertElementGenericTableFull()

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 at line 148 of file generictable.c.

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}
#define InsertTailList(ListHead, Entry)
#define ASSERT(a)
Definition: mode.c:44
#define FIELD_OFFSET(t, f)
Definition: typedefs.h:255
#define RtlCopyMemory(Destination, Source, Length)
Definition: typedefs.h:263
#define RtlInsertAsRightChild(ParentLinks, ChildLinks)
#define RtlInitializeSplayLinks(Links)
#define RtlInsertAsLeftChild(ParentLinks, ChildLinks)
@ TableEmptyTree
Definition: rtltypes.h:363
@ TableInsertAsLeft
Definition: rtltypes.h:365

Referenced by RtlInsertElementGenericTable().

◆ RtlIsGenericTableEmpty()

BOOLEAN NTAPI RtlIsGenericTableEmpty ( IN PRTL_GENERIC_TABLE  Table)

Definition at line 226 of file generictable.c.

227{
228 /* Check if the table root is empty */
229 return (Table->TableRoot) ? FALSE: TRUE;
230}

Referenced by RtlEnumerateGenericTable(), RtlEnumerateGenericTableWithoutSplaying(), and RtlpFindGenericTableNodeOrParent().

◆ RtlLookupElementGenericTable()

PVOID NTAPI RtlLookupElementGenericTable ( IN PRTL_GENERIC_TABLE  Table,
IN PVOID  Buffer 
)

Definition at line 248 of file generictable.c.

250{
251 PRTL_SPLAY_LINKS NodeOrParent;
253
254 /* Call the full version */
256 Buffer,
257 (PVOID)&NodeOrParent,
258 &Result);
259}
PVOID NTAPI RtlLookupElementGenericTableFull(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, OUT PVOID *NodeOrParent, OUT TABLE_SEARCH_RESULT *SearchResult)
Definition: generictable.c:266

◆ RtlLookupElementGenericTableFull()

PVOID NTAPI RtlLookupElementGenericTableFull ( IN PRTL_GENERIC_TABLE  Table,
IN PVOID  Buffer,
OUT PVOID NodeOrParent,
OUT TABLE_SEARCH_RESULT SearchResult 
)

Definition at line 266 of file generictable.c.

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}

Referenced by RtlLookupElementGenericTable().

◆ RtlNumberGenericTableElements()

ULONG NTAPI RtlNumberGenericTableElements ( IN PRTL_GENERIC_TABLE  Table)

Definition at line 237 of file generictable.c.

238{
239 /* Return the number of elements */
240 return Table->NumberGenericTableElements;
241}

◆ RtlpFindGenericTableNodeOrParent()

TABLE_SEARCH_RESULT NTAPI RtlpFindGenericTableNodeOrParent ( IN PRTL_GENERIC_TABLE  Table,
IN PVOID  Buffer,
OUT PRTL_SPLAY_LINKS NodeOrParent 
)

Definition at line 27 of file generictable.c.

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}
#define RtlRightChild(Links)
@ TableInsertAsRight
Definition: rtltypes.h:366
@ GenericLessThan
Definition: rtltypes.h:370
@ GenericEqual
Definition: rtltypes.h:372
@ GenericGreaterThan
Definition: rtltypes.h:371
enum _RTL_GENERIC_COMPARE_RESULTS RTL_GENERIC_COMPARE_RESULTS

Referenced by RtlDeleteElementGenericTable(), RtlInsertElementGenericTable(), and RtlLookupElementGenericTableFull().