[ion] 24540: - Organize file by AVL/Splay routines. - Add RtlLookupFirstMatchingElementGenericTableAvl stub. - Fixup some formatting/tag spacing and prototype definitions.
Author: ion Date: Mon Oct 16 06:49:23 2006 New Revision: 24540
URL: http://svn.reactos.org/svn/reactos?rev=24540&view=rev Log: - Organize file by AVL/Splay routines. - Add RtlLookupFirstMatchingElementGenericTableAvl stub. - Fixup some formatting/tag spacing and prototype definitions.
Modified: trunk/reactos/lib/rtl/generictable.c
Modified: trunk/reactos/lib/rtl/generictable.c URL: http://svn.reactos.org/svn/reactos/trunk/reactos/lib/rtl/generictable.c?rev=... ============================================================================== --- trunk/reactos/lib/rtl/generictable.c (original) +++ trunk/reactos/lib/rtl/generictable.c Mon Oct 16 06:49:23 2006 @@ -1,281 +1,33 @@ -/* COPYRIGHT: See COPYING in the top level directory - * PROJECT: ReactOS system libraries - * PURPOSE: Generic Table Implementation - * FILE: lib/rtl/genertictbl.c - * PROGRAMMERS: arty - */ - -/* INCLUDES *****************************************************************/ +/* +* PROJECT: ReactOS Kernel +* LICENSE: GPL - See COPYING in the top level directory +* FILE: lib/rtl/generictable.c +* PURPOSE: Splay Tree and AVL Tree Generic Table Implementation +* PROGRAMMERS: Alex Ionescu (alex.ionescu@reactos.org) +* Art Yerks (ayerkes@speakeasy.net) +*/ + +/* INCLUDES ******************************************************************/
#include <rtl.h> #include "austin/avl.h" - #define NDEBUG #include <debug.h>
/* FUNCTIONS *****************************************************************/
/* -* @unimplemented -*/ -PVOID -NTAPI -RtlLookupElementGenericTable ( - PRTL_GENERIC_TABLE Table, - PVOID Buffer - ) -{ - UNIMPLEMENTED; - return 0; -} - -/* -* @unimplemented -*/ -PVOID -NTAPI -RtlLookupElementGenericTableFull ( - PRTL_GENERIC_TABLE Table, - PVOID Buffer, - OUT PVOID *NodeOrParent, - OUT TABLE_SEARCH_RESULT *SearchResult - ) -{ - UNIMPLEMENTED; - return 0; -} - -/* -* @implemented -*/ -PVOID -NTAPI -RtlLookupElementGenericTableFullAvl ( - PRTL_AVL_TABLE Table, - PVOID Buffer, - OUT PVOID *NodeOrParent, - OUT TABLE_SEARCH_RESULT *SearchResult - ) -{ - PRTL_BALANCED_LINKS OurNodeOrParent; - TABLE_SEARCH_RESULT OurSearchResult; - - if( !Table->NumberGenericTableElements ) - { - *SearchResult = TableEmptyTree; - *NodeOrParent = NULL; - return NULL; - } - - OurSearchResult = avl_search - (Table, Buffer, - Table->BalancedRoot.LeftChild, &OurNodeOrParent); - - if(SearchResult) *SearchResult = OurSearchResult; - if(NodeOrParent) *NodeOrParent = OurNodeOrParent; - - if(OurSearchResult == TableFoundNode) - return avl_data(OurNodeOrParent); - else - return NULL; -} - - -/* -* @implemented -*/ -PVOID -NTAPI -RtlLookupElementGenericTableAvl ( - PRTL_AVL_TABLE Table, - PVOID Buffer - ) -{ - PRTL_BALANCED_LINKS OurNodeOrParent; - TABLE_SEARCH_RESULT OurSearchResult; - return RtlLookupElementGenericTableFullAvl - (Table, Buffer, (PVOID *)&OurNodeOrParent, &OurSearchResult); -} - - -/* -* @unimplemented -*/ -BOOLEAN -NTAPI -RtlDeleteElementGenericTable ( - PRTL_GENERIC_TABLE Table, - PVOID Buffer - ) -{ - UNIMPLEMENTED; - return FALSE; -} - -/* -* @implemented -*/ -BOOLEAN -NTAPI -RtlDeleteElementGenericTableAvl ( - PRTL_AVL_TABLE Table, - PVOID Buffer - ) -{ - TABLE_SEARCH_RESULT Result; - PRTL_BALANCED_LINKS Node; - - RtlLookupElementGenericTableFullAvl - ( Table, Buffer, (PVOID *)&Node, &Result ); - - if( Result == TableFoundNode ) - { - avl_delete_node(Table, Node); - Table->FreeRoutine(Table, Node); - if( Table->NumberGenericTableElements == 0 ) - avl_deinit(Table); - return TRUE; - } - else - { - return FALSE; - } -} - -/* -* @unimplemented -*/ -PVOID -NTAPI -RtlEnumerateGenericTable ( - PRTL_GENERIC_TABLE Table, - BOOLEAN Restart - ) -{ - UNIMPLEMENTED; - return 0; -} - -/* -* @implemented -*/ -PVOID -NTAPI -RtlEnumerateGenericTableAvl ( - PRTL_AVL_TABLE Table, - BOOLEAN Restart - ) -{ - if( Table->NumberGenericTableElements == 0 ) - return NULL; - - if( Restart ) - { - Table->RestartKey = avl_first(Table); - } - else - { - Table->RestartKey = avl_next(Table, Table->RestartKey); - } - if( !Table->RestartKey ) - return NULL; - else - return avl_data(Table->RestartKey); -} - -/* -* @unimplemented -*/ -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 - ) -{ - UNIMPLEMENTED; - return 0; -} - -/* -* @unimplemented -*/ -PVOID -NTAPI -RtlEnumerateGenericTableWithoutSplaying ( - PRTL_GENERIC_TABLE Table, - PVOID *RestartKey - ) -{ - UNIMPLEMENTED; - return 0; -} - -/* -* @implemented -*/ -PVOID -NTAPI -RtlEnumerateGenericTableWithoutSplayingAvl ( - PRTL_AVL_TABLE Table, - PVOID *RestartKey - ) -{ - return RtlEnumerateGenericTableWithoutSplayingAvl(Table, RestartKey); -} - -/* -* @unimplemented -*/ -PVOID -NTAPI -RtlGetElementGenericTable( - PRTL_GENERIC_TABLE Table, - ULONG I - ) -{ - UNIMPLEMENTED; - return 0; -} - -/* -* @implemented -*/ -PVOID -NTAPI -RtlGetElementGenericTableAvl ( - PRTL_AVL_TABLE Table, - ULONG I - ) -{ - PRTL_BALANCED_LINKS Node; - - if( I >= Table->NumberGenericTableElements ) return NULL; - else - { - Node = avl_first(Table); - while(I--) Node = avl_next(Table, Node); - return avl_data(Node); - } -} - -/* -* @implemented -*/ + * @implemented + */ VOID NTAPI -RtlInitializeGenericTable(PRTL_GENERIC_TABLE Table, - PRTL_GENERIC_COMPARE_ROUTINE CompareRoutine, - PRTL_GENERIC_ALLOCATE_ROUTINE AllocateRoutine, - PRTL_GENERIC_FREE_ROUTINE FreeRoutine, - PVOID TableContext) -{ - /* Initialize the table to default and passed values */ +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) +{ + /* Initialize the table to default and passed values */ InitializeListHead(&Table->InsertOrderList); Table->TableRoot = NULL; Table->NumberGenericTableElements = 0; @@ -287,74 +39,308 @@ Table->TableContext = TableContext; }
- -/* - * @implemented - */ -VOID NTAPI +/* + * @unimplemented + */ +PVOID +NTAPI +RtlInsertElementGenericTable(IN PRTL_GENERIC_TABLE Table, + IN PVOID Buffer, + IN ULONG BufferSize, + OUT PBOOLEAN NewElement OPTIONAL) +{ + UNIMPLEMENTED; + return 0; +} + +/* + * @unimplemented + */ +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) +{ + UNIMPLEMENTED; + return 0; +} + +/* + * @unimplemented + */ +BOOLEAN +NTAPI +RtlIsGenericTableEmpty(IN PRTL_GENERIC_TABLE Table) +{ + UNIMPLEMENTED; + return FALSE; +} + +/* + * @implemented + */ +ULONG +NTAPI +RtlNumberGenericTableElements(IN PRTL_GENERIC_TABLE Table) +{ + return Table->NumberGenericTableElements; +} + +/* + * @unimplemented + */ +PVOID +NTAPI +RtlLookupElementGenericTable(IN PRTL_GENERIC_TABLE Table, + IN PVOID Buffer) +{ + UNIMPLEMENTED; + return 0; +} + +/* + * @unimplemented + */ +PVOID +NTAPI +RtlLookupElementGenericTableFull(IN PRTL_GENERIC_TABLE Table, + IN PVOID Buffer, + OUT PVOID *NodeOrParent, + OUT TABLE_SEARCH_RESULT *SearchResult) +{ + UNIMPLEMENTED; + return 0; +} + +/* + * @unimplemented + */ +BOOLEAN +NTAPI +RtlDeleteElementGenericTable(IN PRTL_GENERIC_TABLE Table, + IN PVOID Buffer) +{ + UNIMPLEMENTED; + return FALSE; +} + +/* + * @unimplemented + */ +PVOID +NTAPI +RtlEnumerateGenericTable(IN PRTL_GENERIC_TABLE Table, + IN BOOLEAN Restart) +{ + UNIMPLEMENTED; + return 0; +} + +/* + * @unimplemented + */ +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) +{ + UNIMPLEMENTED; + return 0; +} + +/* + * @unimplemented + */ +PVOID +NTAPI +RtlEnumerateGenericTableWithoutSplaying(IN PRTL_GENERIC_TABLE Table, + IN OUT PVOID *RestartKey) +{ + UNIMPLEMENTED; + return 0; +} + +/* + * @unimplemented + */ +PVOID +NTAPI +RtlGetElementGenericTable(IN PRTL_GENERIC_TABLE Table, + IN ULONG I) +{ + UNIMPLEMENTED; + return 0; +} + +/* + * @implemented + */ +PVOID +NTAPI +RtlLookupElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table, + IN PVOID Buffer, + IN OUT PVOID *NodeOrParent, + IN OUT TABLE_SEARCH_RESULT *SearchResult) +{ + PRTL_BALANCED_LINKS OurNodeOrParent; + TABLE_SEARCH_RESULT OurSearchResult; + + if( !Table->NumberGenericTableElements ) + { + *SearchResult = TableEmptyTree; + *NodeOrParent = NULL; + return NULL; + } + + OurSearchResult = avl_search + (Table, Buffer, + Table->BalancedRoot.LeftChild, &OurNodeOrParent); + + if(SearchResult) *SearchResult = OurSearchResult; + if(NodeOrParent) *NodeOrParent = OurNodeOrParent; + + if(OurSearchResult == TableFoundNode) + return avl_data(OurNodeOrParent); + else + return NULL; +} + +/* + * @implemented + */ +PVOID +NTAPI +RtlLookupElementGenericTableAvl(IN PRTL_AVL_TABLE Table, + IN PVOID Buffer) +{ + PRTL_BALANCED_LINKS OurNodeOrParent; + TABLE_SEARCH_RESULT OurSearchResult; + return RtlLookupElementGenericTableFullAvl + (Table, Buffer, (PVOID *)&OurNodeOrParent, &OurSearchResult); +} + +/* + * @implemented + */ +BOOLEAN +NTAPI +RtlDeleteElementGenericTableAvl(IN PRTL_AVL_TABLE Table, + IN PVOID Buffer) +{ + TABLE_SEARCH_RESULT Result; + PRTL_BALANCED_LINKS Node; + + RtlLookupElementGenericTableFullAvl + ( Table, Buffer, (PVOID *)&Node, &Result ); + + if( Result == TableFoundNode ) + { + avl_delete_node(Table, Node); + Table->FreeRoutine(Table, Node); + if( Table->NumberGenericTableElements == 0 ) + avl_deinit(Table); + return TRUE; + } + else + { + return FALSE; + } +} + +/* + * @implemented + */ +PVOID +NTAPI +RtlEnumerateGenericTableAvl(IN PRTL_AVL_TABLE Table, + IN BOOLEAN Restart) +{ + if( Table->NumberGenericTableElements == 0 ) + return NULL; + + if( Restart ) + { + Table->RestartKey = avl_first(Table); + } + else + { + Table->RestartKey = avl_next(Table, Table->RestartKey); + } + if( !Table->RestartKey ) + return NULL; + else + return avl_data(Table->RestartKey); +} + +/* + * @implemented + */ +PVOID +NTAPI +RtlEnumerateGenericTableWithoutSplayingAvl(IN PRTL_AVL_TABLE Table, + IN OUT PVOID *RestartKey) +{ + return RtlEnumerateGenericTableWithoutSplayingAvl(Table, RestartKey); +} + +/* + * @implemented + */ +PVOID +NTAPI +RtlGetElementGenericTableAvl(IN PRTL_AVL_TABLE Table, + IN ULONG I) +{ + PRTL_BALANCED_LINKS Node; + + if( I >= Table->NumberGenericTableElements ) return NULL; + else + { + Node = avl_first(Table); + while(I--) Node = avl_next(Table, Node); + return avl_data(Node); + } +} + +/* + * @implemented + */ +VOID +NTAPI RtlInitializeGenericTableAvl(IN OUT PRTL_AVL_TABLE Table, IN PRTL_AVL_COMPARE_ROUTINE CompareRoutine, IN PRTL_AVL_ALLOCATE_ROUTINE AllocateRoutine, IN PRTL_AVL_FREE_ROUTINE FreeRoutine, IN PVOID TableContext) { - RtlZeroMemory(Table, - sizeof(RTL_AVL_TABLE)); - Table->BalancedRoot.Parent = &Table->BalancedRoot; - Table->CompareRoutine = CompareRoutine; - Table->AllocateRoutine = AllocateRoutine; - Table->FreeRoutine = FreeRoutine; - Table->TableContext = TableContext; -} - - -/* -* @unimplemented -*/ -PVOID -NTAPI -RtlInsertElementGenericTable ( - PRTL_GENERIC_TABLE Table, - PVOID Buffer, - ULONG BufferSize, - PBOOLEAN NewElement OPTIONAL - ) -{ - UNIMPLEMENTED; - return 0; -} - -/* -* @unimplemented -*/ -PVOID -NTAPI -RtlInsertElementGenericTableFull ( - PRTL_GENERIC_TABLE Table, - PVOID Buffer, - ULONG BufferSize, - PBOOLEAN NewElement OPTIONAL, - PVOID NodeOrParent, - TABLE_SEARCH_RESULT SearchResult - ) -{ - UNIMPLEMENTED; - return 0; -} - -/* -* @implemented -*/ -PVOID -NTAPI -RtlInsertElementGenericTableFullAvl ( - PRTL_AVL_TABLE Table, - PVOID Buffer, - ULONG BufferSize, - PBOOLEAN NewElement OPTIONAL, - PVOID *NodeOrParent, - TABLE_SEARCH_RESULT *SearchResult - ) + RtlZeroMemory(Table, sizeof(RTL_AVL_TABLE)); + Table->BalancedRoot.Parent = &Table->BalancedRoot; + Table->CompareRoutine = CompareRoutine; + Table->AllocateRoutine = AllocateRoutine; + Table->FreeRoutine = FreeRoutine; + Table->TableContext = TableContext; +} + +/* + * @implemented + */ +PVOID +NTAPI +RtlInsertElementGenericTableFullAvl(IN PRTL_AVL_TABLE Table, + IN PVOID Buffer, + IN ULONG BufferSize, + OUT PBOOLEAN NewElement OPTIONAL, + IN OUT PVOID *NodeOrParent, + IN OUT TABLE_SEARCH_RESULT *SearchResult) { PRTL_BALANCED_LINKS OurNodeOrParent; TABLE_SEARCH_RESULT OurSearchResult; @@ -400,16 +386,14 @@ }
/* -* @implemented -*/ -PVOID -NTAPI -RtlInsertElementGenericTableAvl ( - PRTL_AVL_TABLE Table, - PVOID Buffer, - ULONG BufferSize, - PBOOLEAN NewElement OPTIONAL - ) + * @implemented + */ +PVOID +NTAPI +RtlInsertElementGenericTableAvl(IN PRTL_AVL_TABLE Table, + IN PVOID Buffer, + IN ULONG BufferSize, + OUT PBOOLEAN NewElement OPTIONAL) { PVOID NodeOrParent; TABLE_SEARCH_RESULT SearchResult; @@ -418,50 +402,37 @@ (Table, Buffer, BufferSize, NewElement, &NodeOrParent, &SearchResult); }
+/* + * @implemented + */ +BOOLEAN +NTAPI +RtlIsGenericTableEmptyAvl(PRTL_AVL_TABLE Table) +{ + return Table->NumberGenericTableElements == 0; +} + +/* + * @implemented + */ +ULONG +NTAPI +RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table) +{ + return Table->NumberGenericTableElements; +}
/* * @unimplemented */ -BOOLEAN -NTAPI -RtlIsGenericTableEmpty ( - PRTL_GENERIC_TABLE Table - ) -{ - UNIMPLEMENTED; - return FALSE; -} - -/* -* @unimplemented -*/ -BOOLEAN -NTAPI -RtlIsGenericTableEmptyAvl ( - PRTL_AVL_TABLE Table - ) -{ - return Table->NumberGenericTableElements == 0; -} - - -/* - * @implemented - */ -ULONG NTAPI -RtlNumberGenericTableElements(IN PRTL_GENERIC_TABLE Table) -{ - return Table->NumberGenericTableElements; -} - - -/* - * @implemented - */ -ULONG NTAPI -RtlNumberGenericTableElementsAvl(IN PRTL_AVL_TABLE Table) -{ - return Table->NumberGenericTableElements; +PVOID +NTAPI +RtlLookupFirstMatchingElementGenericTableAvl(IN PRTL_AVL_TABLE Table, + IN PVOID Buffer, + OUT PVOID *RestartKey) +{ + UNIMPLEMENTED; + return NULL; }
/* EOF */
-
ion＠svn.reactos.org