Something went wrong. Try again.
Reactos
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514/* * PROJECT: ReactOS Runtime Library * LICENSE: GPL - See COPYING in the top level directory * FILE: lib/rtl/generictable.c * PURPOSE: Splay Tree Generic Table Implementation * PROGRAMMERS: Alex Ionescu (alex.ionescu@reactos.org) */
/* INCLUDES ******************************************************************/
#include <rtl.h>#define NDEBUG#include <debug.h>
/* Internal header for table entries */typedef struct _TABLE_ENTRY_HEADER{ RTL_SPLAY_LINKS SplayLinks; LIST_ENTRY ListEntry; LONGLONG UserData;} TABLE_ENTRY_HEADER, *PTABLE_ENTRY_HEADER;
/* PRIVATE FUNCTIONS *********************************************************/
TABLE_SEARCH_RESULTNTAPIRtlpFindGenericTableNodeOrParent(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, OUT PRTL_SPLAY_LINKS *NodeOrParent){ PRTL_SPLAY_LINKS CurrentNode, ChildNode; RTL_GENERIC_COMPARE_RESULTS Result;
/* Quick check to see if the table is empty */ if (RtlIsGenericTableEmpty(Table)) { return TableEmptyTree; }
/* Set the current node */ CurrentNode = Table->TableRoot;
/* Start compare loop */ while (TRUE) { /* Do the compare */ Result = Table->CompareRoutine(Table, Buffer, &((PTABLE_ENTRY_HEADER)CurrentNode)-> UserData); if (Result == GenericLessThan) { /* We're less, check if this is the left child */ if ((ChildNode = RtlLeftChild(CurrentNode))) { /* Continue searching from this node */ CurrentNode = ChildNode; } else { /* Otherwise, the element isn't in this tree */ *NodeOrParent = CurrentNode; return TableInsertAsLeft; } } else if (Result == GenericGreaterThan) { /* We're more, check if this is the right child */ if ((ChildNode = RtlRightChild(CurrentNode))) { /* Continue searching from this node */ CurrentNode = ChildNode; } else { /* Otherwise, the element isn't in this tree */ *NodeOrParent = CurrentNode; return TableInsertAsRight; } } else { /* We should've found the node */ ASSERT(Result == GenericEqual);
/* Return node found */ *NodeOrParent = CurrentNode; return TableFoundNode; } }}
/* SPLAY FUNCTIONS ***********************************************************/
/* * @implemented */VOIDNTAPIRtlInitializeGenericTable(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){ /* Initialize the table to default and passed values */ InitializeListHead(&Table->InsertOrderList); Table->TableRoot = NULL; Table->NumberGenericTableElements = 0; Table->WhichOrderedElement = 0; Table->OrderedPointer = &Table->InsertOrderList; Table->CompareRoutine = CompareRoutine; Table->AllocateRoutine = AllocateRoutine; Table->FreeRoutine = FreeRoutine; Table->TableContext = TableContext;}
/* * @implemented */PVOIDNTAPIRtlInsertElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, IN ULONG BufferSize, OUT PBOOLEAN NewElement OPTIONAL){ PRTL_SPLAY_LINKS NodeOrParent; TABLE_SEARCH_RESULT Result;
/* Get the splay links and table search result immediately */ Result = RtlpFindGenericTableNodeOrParent(Table, Buffer, &NodeOrParent);
/* Now call the routine to do the full insert */ return RtlInsertElementGenericTableFull(Table, Buffer, BufferSize, NewElement, NodeOrParent, Result);}
/* * @implemented */PVOIDNTAPIRtlInsertElementGenericTableFull(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, IN ULONG BufferSize, OUT PBOOLEAN NewElement OPTIONAL, IN PVOID NodeOrParent, IN TABLE_SEARCH_RESULT SearchResult){ PRTL_SPLAY_LINKS NewNode;
/* Check if the entry wasn't already found */ if (SearchResult != TableFoundNode) { /* We're doing an allocation, sanity check */ ASSERT(Table->NumberGenericTableElements != (MAXULONG - 1));
/* Allocate a node */ NewNode = Table->AllocateRoutine(Table, BufferSize + FIELD_OFFSET(TABLE_ENTRY_HEADER, UserData)); if (!NewNode) { /* No memory or other allocation error, fail */ if (NewElement) *NewElement = FALSE; return NULL; }
/* Initialize the new inserted element */ RtlInitializeSplayLinks(NewNode); InsertTailList(&Table->InsertOrderList, &((PTABLE_ENTRY_HEADER)NewNode)->ListEntry);
/* Increase element count */ Table->NumberGenericTableElements++;
/* Check where we should insert the entry */ if (SearchResult == TableEmptyTree) { /* This is the new root node */ Table->TableRoot = NewNode; } else if (SearchResult == TableInsertAsLeft) { /* Insert it left */ RtlInsertAsLeftChild(NodeOrParent, NewNode); } else { /* Right node */ RtlInsertAsRightChild(NodeOrParent, NewNode); }
/* Copy user buffer */ RtlCopyMemory(&((PTABLE_ENTRY_HEADER)NewNode)->UserData, Buffer, BufferSize); } else { /* Return the node we already found */ NewNode = NodeOrParent; }
/* Splay the tree */ Table->TableRoot = RtlSplay(NewNode);
/* Return status */ if (NewElement) *NewElement = (SearchResult != TableFoundNode);
/* Return pointer to user data */ return &((PTABLE_ENTRY_HEADER)NewNode)->UserData;}
/* * @implemented */BOOLEANNTAPIRtlIsGenericTableEmpty(IN PRTL_GENERIC_TABLE Table){ /* Check if the table root is empty */ return (Table->TableRoot) ? FALSE: TRUE;}
/* * @implemented */ULONGNTAPIRtlNumberGenericTableElements(IN PRTL_GENERIC_TABLE Table){ /* Return the number of elements */ return Table->NumberGenericTableElements;}
/* * @implemented */PVOIDNTAPIRtlLookupElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer){ PRTL_SPLAY_LINKS NodeOrParent; TABLE_SEARCH_RESULT Result;
/* Call the full version */ return RtlLookupElementGenericTableFull(Table, Buffer, (PVOID)&NodeOrParent, &Result);}
/* * @implemented */PVOIDNTAPIRtlLookupElementGenericTableFull(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer, OUT PVOID *NodeOrParent, OUT TABLE_SEARCH_RESULT *SearchResult){ /* Do the initial lookup */ *SearchResult = RtlpFindGenericTableNodeOrParent(Table, Buffer, (PRTL_SPLAY_LINKS *) NodeOrParent);
/* Check if we found anything */ if ((*SearchResult == TableEmptyTree) || (*SearchResult != TableFoundNode)) { /* Nothing found */ return NULL; }
/* Otherwise, splay the tree and return this entry */ Table->TableRoot = RtlSplay(*NodeOrParent); return &((PTABLE_ENTRY_HEADER)*NodeOrParent)->UserData;}
/* * @implemented */BOOLEANNTAPIRtlDeleteElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN PVOID Buffer){ PRTL_SPLAY_LINKS NodeOrParent; TABLE_SEARCH_RESULT Result;
/* Get the splay links and table search result immediately */ Result = RtlpFindGenericTableNodeOrParent(Table, Buffer, &NodeOrParent); if (Result != TableFoundNode) { /* Nothing to delete */ return FALSE; }
/* Delete the entry */ Table->TableRoot = RtlDelete(NodeOrParent); RemoveEntryList(&((PTABLE_ENTRY_HEADER)NodeOrParent)->ListEntry);
/* Update accounting data */ Table->NumberGenericTableElements--; Table->WhichOrderedElement = 0; Table->OrderedPointer = &Table->InsertOrderList;
/* Free the entry */ Table->FreeRoutine(Table, NodeOrParent); return TRUE;}
/* * @implemented */PVOIDNTAPIRtlEnumerateGenericTable(IN PRTL_GENERIC_TABLE Table, IN BOOLEAN Restart){ PRTL_SPLAY_LINKS FoundNode;
/* Check if the table is empty */ if (RtlIsGenericTableEmpty(Table)) return NULL;
/* Check if we have to restart */ if (Restart) { /* Then find the leftmost element */ FoundNode = Table->TableRoot; while(RtlLeftChild(FoundNode)) { /* Get the left child */ FoundNode = RtlLeftChild(FoundNode); }
/* Splay it */ _Analysis_assume_(FoundNode != NULL); Table->TableRoot = RtlSplay(FoundNode); } else { /* Otherwise, try using the real successor */ FoundNode = RtlRealSuccessor(Table->TableRoot); if (FoundNode) Table->TableRoot = RtlSplay(FoundNode); }
/* Check if we found the node and return it */ return FoundNode ? &((PTABLE_ENTRY_HEADER)FoundNode)->UserData : NULL;}
/* * @implemented */PVOIDNTAPIRtlEnumerateGenericTableWithoutSplaying(IN PRTL_GENERIC_TABLE Table, IN OUT PVOID *RestartKey){ PRTL_SPLAY_LINKS FoundNode;
/* Check if the table is empty */ if (RtlIsGenericTableEmpty(Table)) return NULL;
/* Check if we have to restart */ if (!(*RestartKey)) { /* Then find the leftmost element */ FoundNode = Table->TableRoot; while(RtlLeftChild(FoundNode)) { /* Get the left child */ FoundNode = RtlLeftChild(FoundNode); }
/* Splay it */ *RestartKey = FoundNode; } else { /* Otherwise, try using the real successor */ FoundNode = RtlRealSuccessor(*RestartKey); if (FoundNode) *RestartKey = FoundNode; }
/* Check if we found the node and return it */ return FoundNode ? &((PTABLE_ENTRY_HEADER)FoundNode)->UserData : NULL;}
/* * @unimplemented */PVOIDNTAPIRtlEnumerateGenericTableLikeADirectory(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){ UNIMPLEMENTED; return 0;}
/* * @implemented */PVOIDNTAPIRtlGetElementGenericTable(IN PRTL_GENERIC_TABLE Table, IN ULONG I){ ULONG OrderedElement, ElementCount; PLIST_ENTRY OrderedNode; ULONG DeltaUp, DeltaDown; ULONG NextI = I + 1;
/* Setup current accounting data */ OrderedNode = Table->OrderedPointer; OrderedElement = Table->WhichOrderedElement; ElementCount = Table->NumberGenericTableElements;
/* Sanity checks */ if ((I == MAXULONG) || (NextI > ElementCount)) return NULL;
/* Check if we already found the entry */ if (NextI == OrderedElement) { /* Return it */ return &CONTAINING_RECORD(OrderedNode, TABLE_ENTRY_HEADER, ListEntry)->UserData; }
/* Now check if we're farther behind */ if (OrderedElement > NextI) { /* Find out if the distance is more then the half-way point */ if (NextI > (OrderedElement / 2)) { /* Do the search backwards, since this takes less iterations */ DeltaDown = OrderedElement - NextI; while (DeltaDown) { /* Get next node */ OrderedNode = OrderedNode->Blink; DeltaDown--; } } else { /* Follow the list directly instead */ OrderedNode = &Table->InsertOrderList; while (NextI) { /* Get next node */ OrderedNode = OrderedNode->Flink; NextI--; } } } else { /* We are farther ahead, calculate distances */ DeltaUp = NextI - OrderedElement; DeltaDown = (ElementCount - NextI) + 1;
/* Check if the up distance is smaller then the down distance */ if (DeltaUp <= DeltaDown) { /* Do the search forwards, since this takes less iterations */ while (DeltaUp) { /* Get next node */ OrderedNode = OrderedNode->Blink; DeltaUp--; } } else { /* Do the search downwards, since this takes less iterations */ OrderedNode = &Table->InsertOrderList; while (DeltaDown) { /* Get next node */ OrderedNode = OrderedNode->Blink; DeltaDown--; } } }
/* Got the element, save it */ Table->OrderedPointer = OrderedNode; Table->WhichOrderedElement = NextI;
/* Return the element */ return &CONTAINING_RECORD(OrderedNode, TABLE_ENTRY_HEADER, ListEntry)->UserData;}
/* EOF */