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_HEADER *	PTABLE_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

typedef struct _TABLE_ENTRY_HEADER * PTABLE_ENTRY_HEADER

TABLE_ENTRY_HEADER

typedef struct _TABLE_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.

{
    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;
}

RtlEnumerateGenericTable()

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

Definition at line 327 of file generictable.c.

{
    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;
}

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.

{
    UNIMPLEMENTED;
    return 0;
}

RtlEnumerateGenericTableWithoutSplaying()

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

Definition at line 366 of file generictable.c.

{
    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;
}

RtlGetElementGenericTable()

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

Definition at line 421 of file generictable.c.

{
    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;
}

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.

{
    /* 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;
}

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.

{
    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);
}

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.

{
    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;
}

Referenced by RtlInsertElementGenericTable().

RtlIsGenericTableEmpty()

BOOLEAN NTAPI RtlIsGenericTableEmpty

(

IN PRTL_GENERIC_TABLE

Table

)

Definition at line 226 of file generictable.c.

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

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.

{
    PRTL_SPLAY_LINKS NodeOrParent;
    TABLE_SEARCH_RESULT Result;
 
    /* Call the full version */
    return RtlLookupElementGenericTableFull(Table,
                                            Buffer,
                                            (PVOID)&NodeOrParent,
                                            &Result);
}

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.

{
    /* 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;
}

Referenced by RtlLookupElementGenericTable().

RtlNumberGenericTableElements()

ULONG NTAPI RtlNumberGenericTableElements

(

IN PRTL_GENERIC_TABLE

Table

)

Definition at line 237 of file generictable.c.

{
    /* Return the number of elements */
    return Table->NumberGenericTableElements;
}

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.

{
    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;
        }
    }
}

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