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)
9 /* INCLUDES ******************************************************************/
15 /* Internal header for table entries */
16 typedef struct _TABLE_ENTRY_HEADER
18 RTL_SPLAY_LINKS SplayLinks
;
21 } TABLE_ENTRY_HEADER
, *PTABLE_ENTRY_HEADER
;
23 /* PRIVATE FUNCTIONS *********************************************************/
27 RtlpFindGenericTableNodeOrParent(IN PRTL_GENERIC_TABLE Table
,
29 OUT PRTL_SPLAY_LINKS
*NodeOrParent
)
31 PRTL_SPLAY_LINKS CurrentNode
, ChildNode
;
32 RTL_GENERIC_COMPARE_RESULTS Result
;
34 /* Quick check to see if the table is empty */
35 if (RtlIsGenericTableEmpty(Table
))
37 return TableEmptyTree
;
40 /* Set the current node */
41 CurrentNode
= Table
->TableRoot
;
43 /* Start compare loop */
47 Result
= Table
->CompareRoutine(Table
,
49 &((PTABLE_ENTRY_HEADER
)CurrentNode
)->
51 if (Result
== GenericLessThan
)
53 /* We're less, check if this is the left child */
54 if ((ChildNode
= RtlLeftChild(CurrentNode
)))
56 /* Continue searching from this node */
57 CurrentNode
= ChildNode
;
61 /* Otherwise, the element isn't in this tree */
62 *NodeOrParent
= CurrentNode
;
63 return TableInsertAsLeft
;
66 else if (Result
== GenericGreaterThan
)
68 /* We're more, check if this is the right child */
69 if ((ChildNode
= RtlRightChild(CurrentNode
)))
71 /* Continue searching from this node */
72 CurrentNode
= ChildNode
;
76 /* Otherwise, the element isn't in this tree */
77 *NodeOrParent
= CurrentNode
;
78 return TableInsertAsRight
;
83 /* We should've found the node */
84 ASSERT(Result
== GenericEqual
);
86 /* Return node found */
87 *NodeOrParent
= CurrentNode
;
88 return TableFoundNode
;
93 /* SPLAY FUNCTIONS ***********************************************************/
100 RtlInitializeGenericTable(IN PRTL_GENERIC_TABLE Table
,
101 IN PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine
,
102 IN PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine
,
103 IN PRTL_GENERIC_FREE_ROUTINE FreeRoutine
,
104 IN PVOID TableContext
)
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
;
123 RtlInsertElementGenericTable(IN PRTL_GENERIC_TABLE Table
,
126 OUT PBOOLEAN NewElement OPTIONAL
)
128 PRTL_SPLAY_LINKS NodeOrParent
;
129 TABLE_SEARCH_RESULT Result
;
131 /* Get the splay links and table search result immediately */
132 Result
= RtlpFindGenericTableNodeOrParent(Table
, Buffer
, &NodeOrParent
);
134 /* Now call the routine to do the full insert */
135 return RtlInsertElementGenericTableFull(Table
,
148 RtlInsertElementGenericTableFull(IN PRTL_GENERIC_TABLE Table
,
151 OUT PBOOLEAN NewElement OPTIONAL
,
152 IN PVOID NodeOrParent
,
153 IN TABLE_SEARCH_RESULT SearchResult
)
155 PRTL_SPLAY_LINKS NewNode
;
157 /* Check if the entry wasn't already found */
158 if (SearchResult
!= TableFoundNode
)
160 /* We're doing an allocation, sanity check */
161 ASSERT(Table
->NumberGenericTableElements
!= (MAXULONG
- 1));
163 /* Allocate a node */
164 NewNode
= Table
->AllocateRoutine(Table
,
166 FIELD_OFFSET(TABLE_ENTRY_HEADER
,
170 /* No memory or other allocation error, fail */
171 if (NewElement
) *NewElement
= FALSE
;
175 /* Initialize the new inserted element */
176 RtlInitializeSplayLinks(NewNode
);
177 InsertTailList(&Table
->InsertOrderList
,
178 &((PTABLE_ENTRY_HEADER
)NewNode
)->ListEntry
);
180 /* Increase element count */
181 Table
->NumberGenericTableElements
++;
183 /* Check where we should insert the entry */
184 if (SearchResult
== TableEmptyTree
)
186 /* This is the new root node */
187 Table
->TableRoot
= NewNode
;
189 else if (SearchResult
== TableInsertAsLeft
)
192 RtlInsertAsLeftChild(NodeOrParent
, NewNode
);
197 RtlInsertAsRightChild(NodeOrParent
, NewNode
);
200 /* Copy user buffer */
201 RtlCopyMemory(&((PTABLE_ENTRY_HEADER
)NewNode
)->UserData
,
207 /* Return the node we already found */
208 NewNode
= NodeOrParent
;
212 Table
->TableRoot
= RtlSplay(NewNode
);
215 if (NewElement
) *NewElement
= (SearchResult
!= TableFoundNode
);
217 /* Return pointer to user data */
218 return &((PTABLE_ENTRY_HEADER
)NewNode
)->UserData
;
226 RtlIsGenericTableEmpty(IN PRTL_GENERIC_TABLE Table
)
228 /* Check if the table root is empty */
229 return (Table
->TableRoot
) ? FALSE
: TRUE
;
237 RtlNumberGenericTableElements(IN PRTL_GENERIC_TABLE Table
)
239 /* Return the number of elements */
240 return Table
->NumberGenericTableElements
;
248 RtlLookupElementGenericTable(IN PRTL_GENERIC_TABLE Table
,
251 PRTL_SPLAY_LINKS NodeOrParent
;
252 TABLE_SEARCH_RESULT Result
;
254 /* Call the full version */
255 return RtlLookupElementGenericTableFull(Table
,
257 (PVOID
)&NodeOrParent
,
266 RtlLookupElementGenericTableFull(IN PRTL_GENERIC_TABLE Table
,
268 OUT PVOID
*NodeOrParent
,
269 OUT TABLE_SEARCH_RESULT
*SearchResult
)
271 /* Do the initial lookup */
272 *SearchResult
= RtlpFindGenericTableNodeOrParent(Table
,
277 /* Check if we found anything */
278 if ((*SearchResult
== TableEmptyTree
) || (*SearchResult
!= TableFoundNode
))
284 /* Otherwise, splay the tree and return this entry */
285 Table
->TableRoot
= RtlSplay(*NodeOrParent
);
286 return &((PTABLE_ENTRY_HEADER
)*NodeOrParent
)->UserData
;
294 RtlDeleteElementGenericTable(IN PRTL_GENERIC_TABLE Table
,
297 PRTL_SPLAY_LINKS NodeOrParent
;
298 TABLE_SEARCH_RESULT Result
;
300 /* Get the splay links and table search result immediately */
301 Result
= RtlpFindGenericTableNodeOrParent(Table
, Buffer
, &NodeOrParent
);
302 if (Result
!= TableFoundNode
)
304 /* Nothing to delete */
308 /* Delete the entry */
309 Table
->TableRoot
= RtlDelete(NodeOrParent
);
310 RemoveEntryList(&((PTABLE_ENTRY_HEADER
)NodeOrParent
)->ListEntry
);
312 /* Update accounting data */
313 Table
->NumberGenericTableElements
--;
314 Table
->WhichOrderedElement
= 0;
315 Table
->OrderedPointer
= &Table
->InsertOrderList
;
318 Table
->FreeRoutine(Table
, NodeOrParent
);
327 RtlEnumerateGenericTable(IN PRTL_GENERIC_TABLE Table
,
330 PRTL_SPLAY_LINKS FoundNode
;
332 /* Check if the table is empty */
333 if (RtlIsGenericTableEmpty(Table
)) return NULL
;
335 /* Check if we have to restart */
338 /* Then find the leftmost element */
339 FoundNode
= Table
->TableRoot
;
340 while(RtlLeftChild(FoundNode
))
342 /* Get the left child */
343 FoundNode
= RtlLeftChild(FoundNode
);
347 _Analysis_assume_(FoundNode
!= NULL
);
348 Table
->TableRoot
= RtlSplay(FoundNode
);
352 /* Otherwise, try using the real successor */
353 FoundNode
= RtlRealSuccessor(Table
->TableRoot
);
354 if (FoundNode
) Table
->TableRoot
= RtlSplay(FoundNode
);
357 /* Check if we found the node and return it */
358 return FoundNode
? &((PTABLE_ENTRY_HEADER
)FoundNode
)->UserData
: NULL
;
366 RtlEnumerateGenericTableWithoutSplaying(IN PRTL_GENERIC_TABLE Table
,
367 IN OUT PVOID
*RestartKey
)
369 PRTL_SPLAY_LINKS FoundNode
;
371 /* Check if the table is empty */
372 if (RtlIsGenericTableEmpty(Table
)) return NULL
;
374 /* Check if we have to restart */
377 /* Then find the leftmost element */
378 FoundNode
= Table
->TableRoot
;
379 while(RtlLeftChild(FoundNode
))
381 /* Get the left child */
382 FoundNode
= RtlLeftChild(FoundNode
);
386 *RestartKey
= FoundNode
;
390 /* Otherwise, try using the real successor */
391 FoundNode
= RtlRealSuccessor(*RestartKey
);
392 if (FoundNode
) *RestartKey
= FoundNode
;
395 /* Check if we found the node and return it */
396 return FoundNode
? &((PTABLE_ENTRY_HEADER
)FoundNode
)->UserData
: NULL
;
404 RtlEnumerateGenericTableLikeADirectory(IN PRTL_AVL_TABLE Table
,
405 IN PRTL_AVL_MATCH_FUNCTION MatchFunction
,
408 IN OUT PVOID
*RestartKey
,
409 IN OUT PULONG DeleteCount
,
421 RtlGetElementGenericTable(IN PRTL_GENERIC_TABLE Table
,
424 ULONG OrderedElement
, ElementCount
;
425 PLIST_ENTRY OrderedNode
;
426 ULONG DeltaUp
, DeltaDown
;
429 /* Setup current accounting data */
430 OrderedNode
= Table
->OrderedPointer
;
431 OrderedElement
= Table
->WhichOrderedElement
;
432 ElementCount
= Table
->NumberGenericTableElements
;
435 if ((I
== MAXULONG
) || (NextI
> ElementCount
)) return NULL
;
437 /* Check if we already found the entry */
438 if (NextI
== OrderedElement
)
441 return &((PTABLE_ENTRY_HEADER
)CONTAINING_RECORD(OrderedNode
,
443 ListEntry
))->UserData
;
446 /* Now check if we're farther behind */
447 if (OrderedElement
> NextI
)
449 /* Find out if the distance is more then the half-way point */
450 if (NextI
> (OrderedElement
/ 2))
452 /* Do the search backwards, since this takes less iterations */
453 DeltaDown
= OrderedElement
- NextI
;
457 OrderedNode
= OrderedNode
->Blink
;
463 /* Follow the list directly instead */
464 OrderedNode
= &Table
->InsertOrderList
;
468 OrderedNode
= OrderedNode
->Flink
;
475 /* We are farther ahead, calculate distances */
476 DeltaUp
= NextI
- OrderedElement
;
477 DeltaDown
= (ElementCount
- NextI
) + 1;
479 /* Check if the up distance is smaller then the down distance */
480 if (DeltaUp
<= DeltaDown
)
482 /* Do the search forwards, since this takes less iterations */
486 OrderedNode
= OrderedNode
->Blink
;
492 /* Do the search downwards, since this takes less iterations */
493 OrderedNode
= &Table
->InsertOrderList
;
497 OrderedNode
= OrderedNode
->Blink
;
503 /* Got the element, save it */
504 Table
->OrderedPointer
= OrderedNode
;
505 Table
->WhichOrderedElement
= NextI
;
507 /* Return the element */
508 return &((PTABLE_ENTRY_HEADER
)CONTAINING_RECORD(OrderedNode
,
510 ListEntry
))->UserData
;