skiplist.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	_SKIPLIST_NODE
struct	_SKIPLIST

Typedefs
typedef PVOID(WINAPI *	PSKIPLIST_ALLOCATE_ROUTINE) (DWORD)
typedef int(WINAPI *	PSKIPLIST_COMPARE_ROUTINE) (PVOID, PVOID)
typedef void(WINAPI *	PSKIPLIST_FREE_ROUTINE) (PVOID)
typedef struct _SKIPLIST_NODE	SKIPLIST_NODE
typedef struct _SKIPLIST_NODE *	PSKIPLIST_NODE
typedef struct _SKIPLIST	SKIPLIST
typedef struct _SKIPLIST *	PSKIPLIST

Functions
	C_ASSERT (SKIPLIST_LEVELS >=1)
	C_ASSERT (SKIPLIST_LEVELS<=31)
void	InitializeSkiplist (PSKIPLIST Skiplist, PSKIPLIST_ALLOCATE_ROUTINE AllocateRoutine, PSKIPLIST_COMPARE_ROUTINE CompareRoutine, PSKIPLIST_FREE_ROUTINE FreeRoutine)
BOOL	InsertElementSkiplist (PSKIPLIST Skiplist, PVOID Element)
BOOL	InsertTailElementSkiplist (PSKIPLIST Skiplist, PVOID Element)
PVOID	DeleteElementSkiplist (PSKIPLIST Skiplist, PVOID Element)
PVOID	LookupElementSkiplist (PSKIPLIST Skiplist, PVOID Element, PDWORD ElementIndex)
PSKIPLIST_NODE	LookupNodeByIndexSkiplist (PSKIPLIST Skiplist, DWORD ElementIndex)

Typedef Documentation

PSKIPLIST

typedef struct _SKIPLIST * PSKIPLIST

PSKIPLIST_ALLOCATE_ROUTINE

typedef PVOID(WINAPI * PSKIPLIST_ALLOCATE_ROUTINE) (DWORD)

Definition at line 22 of file skiplist.h.

PSKIPLIST_COMPARE_ROUTINE

typedef int(WINAPI * PSKIPLIST_COMPARE_ROUTINE) (PVOID, PVOID)

Definition at line 23 of file skiplist.h.

PSKIPLIST_FREE_ROUTINE

typedef void(WINAPI * PSKIPLIST_FREE_ROUTINE) (PVOID)

Definition at line 24 of file skiplist.h.

PSKIPLIST_NODE

typedef struct _SKIPLIST_NODE * PSKIPLIST_NODE

SKIPLIST

typedef struct _SKIPLIST SKIPLIST

SKIPLIST_NODE

typedef struct _SKIPLIST_NODE SKIPLIST_NODE

Function Documentation

C_ASSERT() [1/2]

C_ASSERT

(

SKIPLIST_LEVELS >=

1

)

C_ASSERT() [2/2]

C_ASSERT

(

SKIPLIST_LEVELS<=

31

)

DeleteElementSkiplist()

PVOID DeleteElementSkiplist	(	PSKIPLIST	Skiplist,
		PVOID	Element
	)

Definition at line 146 of file skiplist.c.

{
    CHAR i;
    PSKIPLIST_NODE pLastComparedNode = NULL;
    PSKIPLIST_NODE pNode = &Skiplist->Head;
    PSKIPLIST_NODE pUpdate[SKIPLIST_LEVELS];
    PVOID pReturnValue;
 
    // Find the node on every currently used level, after which the node to be deleted must follow.
    // This can be done efficiently by starting from the maximum level and going down a level each time a position has been found.
    for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
    {
        while (pNode->Next[i] && pNode->Next[i] != pLastComparedNode && Skiplist->CompareRoutine(pNode->Next[i]->Element, Element) < 0)
            pNode = pNode->Next[i];
 
        // Reduce the number of comparisons by not comparing the same node on different levels twice.
        pLastComparedNode = pNode->Next[i];
        pUpdate[i] = pNode;
    }
 
    // Check if the node we're looking for has been found.
    pNode = pNode->Next[0];
    if (!pNode || Skiplist->CompareRoutine(pNode->Element, Element) != 0)
    {
        // It hasn't been found, so there's nothing to delete.
        return NULL;
    }
 
    // Beginning at the lowest level, remove the node from each level of the list and merge distances.
    // We can stop as soon as we found the first level that doesn't contain the node.
    for (i = 0; i <= Skiplist->MaximumLevel && pUpdate[i]->Next[i] == pNode; i++)
    {
        pUpdate[i]->Distance[i] += pNode->Distance[i] - 1;
        pUpdate[i]->Next[i] = pNode->Next[i];
    }
 
    // Now decrement the distance of the corresponding node in levels higher than the deleted node's level to account for the deleted node.
    while (i <= Skiplist->MaximumLevel)
    {
        --pUpdate[i]->Distance[i];
        i++;
    }
 
    // Return the deleted element (so the caller can free it if necessary) and free the memory for the node itself (allocated by us).
    pReturnValue = pNode->Element;
    Skiplist->FreeRoutine(pNode);
 
    // Find all levels which now contain no more nodes and reduce the maximum level of the entire Skiplist accordingly.
    while (Skiplist->MaximumLevel > 0 && !Skiplist->Head.Next[Skiplist->MaximumLevel])
        --Skiplist->MaximumLevel;
 
    // We've successfully deleted the node :)
    --Skiplist->NodeCount;
    return pReturnValue;
}

Referenced by _LocalSetJobLevel1(), _LocalSetJobLevel2(), FreeJob(), and main().

InitializeSkiplist()

void InitializeSkiplist	(	PSKIPLIST	Skiplist,
		PSKIPLIST_ALLOCATE_ROUTINE	AllocateRoutine,
		PSKIPLIST_COMPARE_ROUTINE	CompareRoutine,
		PSKIPLIST_FREE_ROUTINE	FreeRoutine
	)

Definition at line 220 of file skiplist.c.

{
    // Store the routines.
    Skiplist->AllocateRoutine = AllocateRoutine;
    Skiplist->CompareRoutine = CompareRoutine;
    Skiplist->FreeRoutine = FreeRoutine;
 
    // Initialize the members and pointers.
    // The Distance array is only used when a node is non-NULL, so it doesn't need initialization.
    Skiplist->MaximumLevel = 0;
    Skiplist->NodeCount = 0;
    ZeroMemory(Skiplist->Head.Next, sizeof(Skiplist->Head.Next));
}

Referenced by InitializeGlobalJobList(), InitializePrinterJobList(), InitializePrinterList(), and main().

InsertElementSkiplist()

BOOL InsertElementSkiplist	(	PSKIPLIST	Skiplist,
		PVOID	Element
	)

Definition at line 250 of file skiplist.c.

{
    CHAR i;
    DWORD dwDistance[SKIPLIST_LEVELS + 1] = { 0 };
    PSKIPLIST_NODE pLastComparedNode = NULL;
    PSKIPLIST_NODE pNode = &Skiplist->Head;
    PSKIPLIST_NODE pUpdate[SKIPLIST_LEVELS];
 
    // Find the node on every currently used level, after which the new node needs to be inserted.
    // This can be done efficiently by starting from the maximum level and going down a level each time a position has been found.
    for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
    {
        // When entering this level, we begin at the distance of the last level we walked through.
        dwDistance[i] = dwDistance[i + 1];
 
        while (pNode->Next[i] && pNode->Next[i] != pLastComparedNode && Skiplist->CompareRoutine(pNode->Next[i]->Element, Element) < 0)
        {
            // Save our position in every level when walking through the nodes.
            dwDistance[i] += pNode->Distance[i];
 
            // Advance to the next node.
            pNode = pNode->Next[i];
        }
 
        // Reduce the number of comparisons by not comparing the same node on different levels twice.
        pLastComparedNode = pNode->Next[i];
        pUpdate[i] = pNode;
    }
 
    // Check if the node already exists in the Skiplist.
    pNode = pNode->Next[0];
    if (pNode && Skiplist->CompareRoutine(pNode->Element, Element) == 0)
    {
        // All elements to be inserted mustn't exist in the list, so we see this as a failure.
        return FALSE;
    }
 
    // The rest of the procedure is the same for both insertion functions.
    return _InsertElementSkiplistWithInformation(Skiplist, Element, pUpdate, dwDistance);
}

Referenced by _LocalSetJobLevel1(), _LocalSetJobLevel2(), CreateJob(), InitializeGlobalJobList(), InitializePrinterList(), and main().

InsertTailElementSkiplist()

BOOL InsertTailElementSkiplist	(	PSKIPLIST	Skiplist,
		PVOID	Element
	)

Definition at line 308 of file skiplist.c.

{
    CHAR i;
    DWORD dwDistance[SKIPLIST_LEVELS + 1] = { 0 };
    PSKIPLIST_NODE pNode = &Skiplist->Head;
    PSKIPLIST_NODE pUpdate[SKIPLIST_LEVELS];
 
    // Find the last node on every currently used level, after which the new node needs to be inserted.
    // This can be done efficiently by starting from the maximum level and going down a level each time a position has been found.
    for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
    {
        // When entering this level, we begin at the distance of the last level we walked through.
        dwDistance[i] = dwDistance[i + 1];
 
        while (pNode->Next[i])
        {
            // Save our position in every level when walking through the nodes.
            dwDistance[i] += pNode->Distance[i];
 
            // Advance to the next node.
            pNode = pNode->Next[i];
        }
 
        pUpdate[i] = pNode;
    }
 
    // The rest of the procedure is the same for both insertion functions.
    return _InsertElementSkiplistWithInformation(Skiplist, Element, pUpdate, dwDistance);
}

Referenced by CreateJob().

LookupElementSkiplist()

PVOID LookupElementSkiplist	(	PSKIPLIST	Skiplist,
		PVOID	Element,
		PDWORD	ElementIndex
	)

Definition at line 357 of file skiplist.c.

{
    CHAR i;
    DWORD dwIndex = 0;
    PSKIPLIST_NODE pLastComparedNode = NULL;
    PSKIPLIST_NODE pNode = &Skiplist->Head;
 
    // Do the efficient lookup in Skiplists:
    //    * Start from the maximum level.
    //    * Walk through all nodes on this level that come before the node we're looking for.
    //    * When we have reached such a node, go down a level and continue there.
    //    * Repeat these steps till we're in level 0, right in front of the node we're looking for.
    for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
    {
        while (pNode->Next[i] && pNode->Next[i] != pLastComparedNode && Skiplist->CompareRoutine(pNode->Next[i]->Element, Element) < 0)
        {
            dwIndex += pNode->Distance[i];
            pNode = pNode->Next[i];
        }
 
        // Reduce the number of comparisons by not comparing the same node on different levels twice.
        pLastComparedNode = pNode->Next[i];
    }
 
    // We must be right in front of the node we're looking for now, otherwise it doesn't exist in the Skiplist at all.
    pNode = pNode->Next[0];
    if (!pNode || Skiplist->CompareRoutine(pNode->Element, Element) != 0)
    {
        // It hasn't been found, so there's nothing to return.
        return NULL;
    }
 
    // Return the index of the element if the caller is interested.
    if (ElementIndex)
        *ElementIndex = dwIndex;
 
    // Return the stored element of the found node.
    return pNode->Element;
}

Referenced by _GetNextJobID(), _LocalGetJobLevel1(), _LocalGetJobLevel2(), _LocalOpenPrinterHandle(), LocalGetJob(), LocalScheduleJob(), LocalSetJob(), main(), and ReadJobShadowFile().

LookupNodeByIndexSkiplist()

PSKIPLIST_NODE LookupNodeByIndexSkiplist	(	PSKIPLIST	Skiplist,
		DWORD	ElementIndex
	)

Definition at line 412 of file skiplist.c.

{
    CHAR i;
    DWORD dwIndex = 0;
    PSKIPLIST_NODE pNode = &Skiplist->Head;
 
    // The only way the node can't be found is when the index is out of range.
    if (ElementIndex >= Skiplist->NodeCount)
        return NULL;
 
    // Do the efficient lookup in Skiplists:
    //    * Start from the maximum level.
    //    * Walk through all nodes on this level that come before the node we're looking for.
    //    * When we have reached such a node, go down a level and continue there.
    //    * Repeat these steps till we're in level 0, right in front of the node we're looking for.
    for (i = Skiplist->MaximumLevel + 1; --i >= 0;)
    {
        // We compare with <= instead of < here, because the added distances make up a 1-based index while ElementIndex is zero-based,
        // so we have to jump one node further.
        while (pNode->Next[i] && dwIndex + pNode->Distance[i] <= ElementIndex)
        {
            dwIndex += pNode->Distance[i];
            pNode = pNode->Next[i];
        }
    }
 
    // We are right in front of the node we're looking for now.
    return pNode->Next[0];
}

Referenced by LocalEnumJobs(), and main().