2 * PROJECT: ReactOS Kernel
3 * LICENSE: GPL - See COPYING in the top level directory
4 * FILE: lib/rtl/generictable.c
5 * PURPOSE: Splay Tree and AVL Tree Generic Table Implementation
6 * PROGRAMMERS: Alex Ionescu (alex.ionescu@reactos.org)
7 * Art Yerks (ayerkes@speakeasy.net)
10 /* INCLUDES ******************************************************************/
13 #include "austin/avl.h"
17 /* Internal header for table entries */
18 typedef struct _TABLE_ENTRY_HEADER
20 RTL_SPLAY_LINKS SplayLinks
;
23 } TABLE_ENTRY_HEADER
, *PTABLE_ENTRY_HEADER
;
25 /* PRIVATE FUNCTIONS *********************************************************/
29 RtlpFindGenericTableNodeOrParent(IN PRTL_GENERIC_TABLE Table
,
31 OUT PRTL_SPLAY_LINKS
*NodeOrParent
)
33 PRTL_SPLAY_LINKS CurrentNode
, ChildNode
;
34 RTL_GENERIC_COMPARE_RESULTS Result
;
36 /* Quick check to see if the table is empty */
37 if (RtlIsGenericTableEmpty(Table
))
40 return TableEmptyTree
;
43 /* Set the current node */
44 CurrentNode
= Table
->TableRoot
;
46 /* Start compare loop */
50 Result
= Table
->CompareRoutine(Table
,
52 &((PTABLE_ENTRY_HEADER
)CurrentNode
)->
54 if (Result
== GenericLessThan
)
56 /* We're less, check if this is the left child */
57 if ((ChildNode
= RtlLeftChild(CurrentNode
)))
59 /* Continue searching from this node */
60 CurrentNode
= ChildNode
;
64 /* Otherwise, the element isn't in this tree */
65 *NodeOrParent
= CurrentNode
;
66 return TableInsertAsLeft
;
69 else if (Result
== GenericGreaterThan
)
71 /* We're more, check if this is the right child */
72 if ((ChildNode
= RtlRightChild(CurrentNode
)))
74 /* Continue searching from this node */
75 CurrentNode
= ChildNode
;
79 /* Otherwise, the element isn't in this tree */
80 *NodeOrParent
= CurrentNode
;
81 return TableInsertAsRight
;
86 /* We should've found the node */
87 ASSERT(Result
== GenericEqual
);
89 /* Return node found */
90 *NodeOrParent
= CurrentNode
;
91 return TableFoundNode
;
96 /* SPLAY FUNCTIONS ***********************************************************/
103 RtlInitializeGenericTable(IN PRTL_GENERIC_TABLE Table
,
104 IN PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine
,
105 IN PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine
,
106 IN PRTL_GENERIC_FREE_ROUTINE FreeRoutine
,
107 IN PVOID TableContext
)
109 /* Initialize the table to default and passed values */
110 InitializeListHead(&Table
->InsertOrderList
);
111 Table
->TableRoot
= NULL
;
112 Table
->NumberGenericTableElements
= 0;
113 Table
->WhichOrderedElement
= 0;
114 Table
->OrderedPointer
= &Table
->InsertOrderList
;
115 Table
->CompareRoutine
= CompareRoutine
;
116 Table
->AllocateRoutine
= AllocateRoutine
;
117 Table
->FreeRoutine
= FreeRoutine
;
118 Table
->TableContext
= TableContext
;
126 RtlInsertElementGenericTable(IN PRTL_GENERIC_TABLE Table
,
129 OUT PBOOLEAN NewElement OPTIONAL
)
131 PRTL_SPLAY_LINKS NodeOrParent
;
132 TABLE_SEARCH_RESULT Result
;
134 /* Get the splay links and table search result immediately */
135 Result
= RtlpFindGenericTableNodeOrParent(Table
, Buffer
, &NodeOrParent
);
137 /* Now call the routine to do the full insert */
138 return RtlInsertElementGenericTableFull(Table
,
151 RtlInsertElementGenericTableFull(IN PRTL_GENERIC_TABLE Table
,
154 OUT PBOOLEAN NewElement OPTIONAL
,
155 IN PVOID NodeOrParent
,
156 IN TABLE_SEARCH_RESULT SearchResult
)
158 PRTL_SPLAY_LINKS NewNode
;
160 /* Check if the entry wasn't already found */
161 if (SearchResult
!= TableFoundNode
)
163 /* We're doing an allocation, sanity check */
164 ASSERT(Table
->NumberGenericTableElements
!= (MAXULONG
- 1));
166 /* Allocate a node */
167 NewNode
= Table
->AllocateRoutine(Table
,
169 FIELD_OFFSET(TABLE_ENTRY_HEADER
,
173 /* No memory or other allocation error, fail */
174 if (NewElement
) *NewElement
= FALSE
;
178 /* Initialize the new inserted element */
179 RtlInitializeSplayLinks(NewNode
);
180 InsertTailList(&Table
->InsertOrderList
,
181 &((PTABLE_ENTRY_HEADER
)NewNode
)->ListEntry
);
183 /* Increase element count */
184 Table
->NumberGenericTableElements
++;
186 /* Check where we should insert the entry */
187 if (SearchResult
== TableEmptyTree
)
189 /* This is the new root node */
190 Table
->TableRoot
= NewNode
;
192 else if (SearchResult
== TableInsertAsLeft
)
195 RtlInsertAsLeftChild(NodeOrParent
, NewNode
);
200 RtlInsertAsRightChild(NodeOrParent
, NewNode
);
203 /* Copy user buffer */
204 RtlCopyMemory(&((PTABLE_ENTRY_HEADER
)NewNode
)->UserData
,
210 /* Return the node we already found */
211 NewNode
= NodeOrParent
;
215 Table
->TableRoot
= RtlSplay(NewNode
);
218 if (NewElement
) *NewElement
= (SearchResult
== TableFoundNode
);
220 /* Return pointer to user data */
221 return &((PTABLE_ENTRY_HEADER
)NewNode
)->UserData
;
229 RtlIsGenericTableEmpty(IN PRTL_GENERIC_TABLE Table
)
231 /* Check if the table root is empty */
232 return (Table
->TableRoot
) ? FALSE
: TRUE
;
240 RtlNumberGenericTableElements(IN PRTL_GENERIC_TABLE Table
)
242 /* Return the number of elements */
243 return Table
->NumberGenericTableElements
;
251 RtlLookupElementGenericTable(IN PRTL_GENERIC_TABLE Table
,
254 PRTL_SPLAY_LINKS NodeOrParent
;
255 TABLE_SEARCH_RESULT Result
;
257 /* Call the full version */
258 return RtlLookupElementGenericTableFull(Table
,
260 (PVOID
)&NodeOrParent
,
269 RtlLookupElementGenericTableFull(IN PRTL_GENERIC_TABLE Table
,
271 OUT PVOID
*NodeOrParent
,
272 OUT TABLE_SEARCH_RESULT
*SearchResult
)
274 /* Do the initial lookup */
275 *SearchResult
= RtlpFindGenericTableNodeOrParent(Table
,
280 /* Check if we found anything */
281 if ((*SearchResult
== TableEmptyTree
) || (*SearchResult
!= TableFoundNode
))
287 /* Otherwise, splay the tree and return this entry */
288 Table
->TableRoot
= RtlSplay(*NodeOrParent
);
289 return &((PTABLE_ENTRY_HEADER
)*NodeOrParent
)->UserData
;
297 RtlDeleteElementGenericTable(IN PRTL_GENERIC_TABLE Table
,
300 PRTL_SPLAY_LINKS NodeOrParent
;
301 TABLE_SEARCH_RESULT Result
;
303 /* Get the splay links and table search result immediately */
304 Result
= RtlpFindGenericTableNodeOrParent(Table
, Buffer
, &NodeOrParent
);
305 if ((Result
== TableEmptyTree
) || (Result
!= TableFoundNode
))
307 /* Nothing to delete */
311 /* Delete the entry */
312 Table
->TableRoot
= RtlDelete(NodeOrParent
);
313 RemoveEntryList(&((PTABLE_ENTRY_HEADER
)NodeOrParent
)->ListEntry
);
315 /* Update accounting data */
316 Table
->NumberGenericTableElements
--;
317 Table
->WhichOrderedElement
= 0;
318 Table
->OrderedPointer
= &Table
->InsertOrderList
;
321 Table
->FreeRoutine(Table
, NodeOrParent
);
330 RtlEnumerateGenericTable(IN PRTL_GENERIC_TABLE Table
,
333 PRTL_SPLAY_LINKS FoundNode
;
335 /* Check if the table is empty */
336 if (RtlIsGenericTableEmpty(Table
)) return NULL
;
338 /* Check if we have to restart */
341 /* Then find the leftmost element */
342 FoundNode
= Table
->TableRoot
;
345 /* Get the left child */
346 FoundNode
= RtlLeftChild(FoundNode
);
347 } while(RtlLeftChild(FoundNode
));
350 Table
->TableRoot
= RtlSplay(FoundNode
);
354 /* Otherwise, try using the real successor */
355 FoundNode
= RtlRealSuccessor(Table
->TableRoot
);
356 if (FoundNode
) Table
->TableRoot
= RtlSplay(FoundNode
);
359 /* Check if we found the node and return it */
360 return FoundNode
? &((PTABLE_ENTRY_HEADER
)FoundNode
)->UserData
: NULL
;
368 RtlEnumerateGenericTableWithoutSplaying(IN PRTL_GENERIC_TABLE Table
,
369 IN OUT PVOID
*RestartKey
)
371 PRTL_SPLAY_LINKS FoundNode
;
373 /* Check if the table is empty */
374 if (RtlIsGenericTableEmpty(Table
)) return NULL
;
376 /* Check if we have to restart */
379 /* Then find the leftmost element */
380 FoundNode
= Table
->TableRoot
;
383 /* Get the left child */
384 FoundNode
= RtlLeftChild(FoundNode
);
385 } while(RtlLeftChild(FoundNode
));
388 *RestartKey
= FoundNode
;
392 /* Otherwise, try using the real successor */
393 FoundNode
= RtlRealSuccessor(*RestartKey
);
394 if (FoundNode
) *RestartKey
= FoundNode
;
397 /* Check if we found the node and return it */
398 return FoundNode
? &((PTABLE_ENTRY_HEADER
)FoundNode
)->UserData
: NULL
;
406 RtlEnumerateGenericTableLikeADirectory(IN PRTL_AVL_TABLE Table
,
407 IN PRTL_AVL_MATCH_FUNCTION MatchFunction
,
410 IN OUT PVOID
*RestartKey
,
411 IN OUT PULONG DeleteCount
,
423 RtlGetElementGenericTable(IN PRTL_GENERIC_TABLE Table
,
426 ULONG OrderedElement
, ElementCount
;
427 PLIST_ENTRY OrderedNode
;
428 ULONG DeltaUp
, DeltaDown
;
431 /* Setup current accounting data */
432 OrderedNode
= Table
->OrderedPointer
;
433 OrderedElement
= Table
->WhichOrderedElement
;
434 ElementCount
= Table
->NumberGenericTableElements
;
437 if ((I
== MAXULONG
) || (NextI
> ElementCount
)) return NULL
;
439 /* Check if we already found the entry */
440 if (NextI
== OrderedElement
)
443 return &((PTABLE_ENTRY_HEADER
)CONTAINING_RECORD(OrderedNode
,
445 ListEntry
))->UserData
;
448 /* Now check if we're farther behind */
449 if (OrderedElement
> NextI
)
451 /* Find out if the distance is more then the half-way point */
452 if (NextI
> (OrderedElement
/ 2))
454 /* Do the search backwards, since this takes less iterations */
455 DeltaDown
= OrderedElement
- NextI
;
459 OrderedNode
= OrderedNode
->Blink
;
460 } while (--DeltaDown
);
464 /* Follow the list directly instead */
465 OrderedNode
= &Table
->InsertOrderList
;
469 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
;
491 /* Do the search downwards, since this takes less iterations */
492 OrderedNode
= &Table
->InsertOrderList
;
496 OrderedNode
= OrderedNode
->Blink
;
497 } while (--DeltaDown
);
501 /* Got the element, save it */
502 Table
->OrderedPointer
= OrderedNode
;
503 Table
->WhichOrderedElement
= NextI
;
505 /* Return the element */
506 return &((PTABLE_ENTRY_HEADER
)CONTAINING_RECORD(OrderedNode
,
508 ListEntry
))->UserData
;
511 /* AVL FUNCTIONS *************************************************************/
518 RtlLookupElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table
,
520 IN OUT PVOID
*NodeOrParent
,
521 IN OUT TABLE_SEARCH_RESULT
*SearchResult
)
523 PRTL_BALANCED_LINKS OurNodeOrParent
;
524 TABLE_SEARCH_RESULT OurSearchResult
;
526 if( !Table
->NumberGenericTableElements
)
528 *SearchResult
= TableEmptyTree
;
529 *NodeOrParent
= NULL
;
533 OurSearchResult
= avl_search
535 Table
->BalancedRoot
.LeftChild
, &OurNodeOrParent
);
537 if(SearchResult
) *SearchResult
= OurSearchResult
;
538 if(NodeOrParent
) *NodeOrParent
= OurNodeOrParent
;
540 if(OurSearchResult
== TableFoundNode
)
541 return avl_data(OurNodeOrParent
);
551 RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table
,
554 PRTL_BALANCED_LINKS OurNodeOrParent
;
555 TABLE_SEARCH_RESULT OurSearchResult
;
556 return RtlLookupElementGenericTableFullAvl
557 (Table
, Buffer
, (PVOID
*)&OurNodeOrParent
, &OurSearchResult
);
565 RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table
,
568 TABLE_SEARCH_RESULT Result
;
569 PRTL_BALANCED_LINKS Node
;
571 RtlLookupElementGenericTableFullAvl
572 ( Table
, Buffer
, (PVOID
*)&Node
, &Result
);
574 if( Result
== TableFoundNode
)
576 avl_delete_node(Table
, Node
);
577 Table
->FreeRoutine(Table
, Node
);
578 if( Table
->NumberGenericTableElements
== 0 )
593 RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table
,
596 if( Table
->NumberGenericTableElements
== 0 )
601 Table
->RestartKey
= avl_first(Table
);
605 Table
->RestartKey
= avl_next(Table
, Table
->RestartKey
);
607 if( !Table
->RestartKey
)
610 return avl_data(Table
->RestartKey
);
618 RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table
,
619 IN OUT PVOID
*RestartKey
)
622 return RtlEnumerateGenericTableWithoutSplayingAvl(Table
, RestartKey
);
630 RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table
,
633 PRTL_BALANCED_LINKS Node
;
635 if( I
>= Table
->NumberGenericTableElements
) return NULL
;
638 Node
= avl_first(Table
);
639 while(I
--) Node
= avl_next(Table
, Node
);
640 return avl_data(Node
);
649 RtlInitializeGenericTableAvl(IN OUT PRTL_AVL_TABLE Table
,
650 IN PRTL_AVL_COMPARE_ROUTINE CompareRoutine
,
651 IN PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine
,
652 IN PRTL_AVL_FREE_ROUTINE FreeRoutine
,
653 IN PVOID TableContext
)
655 RtlZeroMemory(Table
, sizeof(RTL_AVL_TABLE
));
656 Table
->BalancedRoot
.Parent
= &Table
->BalancedRoot
;
657 Table
->CompareRoutine
= CompareRoutine
;
658 Table
->AllocateRoutine
= AllocateRoutine
;
659 Table
->FreeRoutine
= FreeRoutine
;
660 Table
->TableContext
= TableContext
;
668 RtlInsertElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table
,
671 OUT PBOOLEAN NewElement OPTIONAL
,
672 IN OUT PVOID
*NodeOrParent
,
673 IN OUT TABLE_SEARCH_RESULT
*SearchResult
)
675 PRTL_BALANCED_LINKS OurNodeOrParent
;
676 TABLE_SEARCH_RESULT OurSearchResult
;
678 if(Table
->NumberGenericTableElements
== 0) {
685 OurSearchResult
= avl_search
687 Table
->BalancedRoot
.LeftChild
, &OurNodeOrParent
);
689 if(NodeOrParent
) *NodeOrParent
= OurNodeOrParent
;
690 if(SearchResult
) *SearchResult
= OurSearchResult
;
692 if(OurSearchResult
== TableFoundNode
)
694 RtlDeleteElementGenericTableAvl(Table
, Buffer
);
695 return RtlInsertElementGenericTableFullAvl
696 (Table
, Buffer
, BufferSize
,
697 NewElement
, NodeOrParent
, SearchResult
);
701 PRTL_BALANCED_LINKS NewNode
=
702 Table
->AllocateRoutine
704 BufferSize
+ sizeof(RTL_BALANCED_LINKS
) + BufferSize
);
706 if( !NewNode
) return NULL
;
708 NewNode
->Balance
= 0;
709 RtlCopyMemory(avl_data(NewNode
), Buffer
, BufferSize
);
711 OurNodeOrParent
= NewNode
;
713 avl_insert_node(Table
, NewNode
);
714 return avl_data(NewNode
);
723 RtlInsertElementGenericTableAvl(IN PRTL_AVL_TABLE Table
,
726 OUT PBOOLEAN NewElement OPTIONAL
)
729 TABLE_SEARCH_RESULT SearchResult
;
731 return RtlInsertElementGenericTableFullAvl
732 (Table
, Buffer
, BufferSize
, NewElement
, &NodeOrParent
, &SearchResult
);
740 RtlIsGenericTableEmptyAvl(PRTL_AVL_TABLE Table
)
742 return Table
->NumberGenericTableElements
== 0;
750 RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table
)
752 return Table
->NumberGenericTableElements
;
760 RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table
,
762 OUT PVOID
*RestartKey
)