ellLib.h File Reference

A doubly-linked list library. More...

#include "libComAPI.h"

Include dependency graph for ellLib.h:

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

Go to the source code of this file.

Classes
struct	ELLNODE
	List node type. More...
struct	ELLLIST
	List header type. More...

Macros
#define	ELLNODE_INIT   {NULL, NULL}
	Value of a terminal node. More...
#define	ELLLIST_INIT   {ELLNODE_INIT, 0}
	Value of an empty list. More...
#define	ellInit(PLIST)
	Initialize a list type. More...
#define	ellCount(PLIST)   ((PLIST)->count)
	Report the number of nodes in a list. More...
#define	ellFirst(PLIST)   ((PLIST)->node.next)
	Find the first node in list. More...
#define	ellLast(PLIST)   ((PLIST)->node.previous)
	Find the last node in list. More...
#define	ellNext(PNODE)   ((PNODE)->next)
	Find the next node in list. More...
#define	ellPrevious(PNODE)   ((PNODE)->previous)
	Find the previous node in list. More...
#define	ellFree(PLIST)   ellFree2(PLIST, free)
	Free up the list. More...

Typedefs
typedef struct ELLNODE	ELLNODE
	List node type. More...
typedef struct ELLLIST	ELLLIST
	List header type. More...
typedef void(*	FREEFUNC) (void *)
	Pointer to free() for use by ellFree() macro. More...
typedef int(*	pListCmp) (const ELLNODE *A, const ELLNODE *B)

Functions
LIBCOM_API void	ellAdd (ELLLIST *pList, ELLNODE *pNode)
	Adds a node to the end of a list. More...
LIBCOM_API void	ellConcat (ELLLIST *pDstList, ELLLIST *pAddList)
	Concatenates a list to the end of another list. The list to be added is left empty. Either list (or both) can be empty at the beginning of the operation. More...
LIBCOM_API void	ellDelete (ELLLIST *pList, ELLNODE *pNode)
	Deletes a node from a list. More...
LIBCOM_API void	ellExtract (ELLLIST *pSrcList, ELLNODE *pStartNode, ELLNODE *pEndNode, ELLLIST *pDstList)
	Extract a sublist from a list. More...
LIBCOM_API ELLNODE *	ellGet (ELLLIST *pList)
	Deletes and returns the first node from a list. More...
LIBCOM_API ELLNODE *	ellPop (ELLLIST *pList)
	Deletes and returns the last node from a list. More...
LIBCOM_API void	ellInsert (ELLLIST *plist, ELLNODE *pPrev, ELLNODE *pNode)
	Inserts a node into a list immediately after a specific node. More...
LIBCOM_API ELLNODE *	ellNth (ELLLIST *pList, int nodeNum)
	Find the Nth node in a list. More...
LIBCOM_API ELLNODE *	ellNStep (ELLNODE *pNode, int nStep)
	Find the list node nStep steps away from a specified node. More...
LIBCOM_API int	ellFind (ELLLIST *pList, ELLNODE *pNode)
	Find the index of a specific node in a list. More...
LIBCOM_API void	ellSortStable (ELLLIST *pList, pListCmp pListCmp)
	Stable (MergeSort) of a given list. More...
LIBCOM_API void	ellFree2 (ELLLIST *pList, FREEFUNC freeFunc)
	Free all the nodes in a list. More...
LIBCOM_API void	ellVerify (ELLLIST *pList)
	Verifies that the list is consistent. More...

Detailed Description

A doubly-linked list library.

Author

John Winans (ANL)

Andrew Johnson (ANL)

This provides similar functionality to the VxWorks lstLib library.

Supports the creation and maintenance of a doubly-linked list. The user supplies a list descriptor (type ELLLIST) that will contain pointers to the first and last nodes in the list, and a count of the number of nodes in the list. The nodes in the list can be any user-defined structure, but they must reserve space for two pointers as their first elements. Both the forward and backward chains are terminated with a NULL pointer.

Definition in file ellLib.h.

Macro Definition Documentation

#define ellCount

(

PLIST

)

((PLIST)->count)

Report the number of nodes in a list.

Parameters

PLIST

Pointer to list descriptor

Returns

Number of nodes in the list

Definition at line 84 of file ellLib.h.

#define ellFirst

(

PLIST

)

((PLIST)->node.next)

Find the first node in list.

Parameters

PLIST

Pointer to list descriptor

Returns

Pointer to first node in the list

Definition at line 89 of file ellLib.h.

#define ellFree

(

PLIST

)

ellFree2(PLIST, free)

Free up the list.

Parameters

PLIST

List for which to free all nodes

Definition at line 108 of file ellLib.h.

#define ellInit

(

PLIST

)

Value:

{\
    (PLIST)->node.next = (PLIST)->node.previous = NULL;\
    (PLIST)->count = 0;\
}

Initialize a list type.

Parameters

PLIST

Pointer to list header to be initialized

Definition at line 76 of file ellLib.h.

#define ellLast

(

PLIST

)

((PLIST)->node.previous)

Find the last node in list.

Parameters

PLIST

Pointer to list descriptor

Returns

Pointer to last node in the list

Definition at line 94 of file ellLib.h.

#define ELLLIST_INIT   {ELLNODE_INIT, 0}

Value of an empty list.

Definition at line 63 of file ellLib.h.

#define ellNext

(

PNODE

)

((PNODE)->next)

Find the next node in list.

Parameters

PNODE

Pointer to node whose successor is to be found

Returns

Pointer to the node following PNODE

Definition at line 99 of file ellLib.h.

#define ELLNODE_INIT   {NULL, NULL}

Value of a terminal node.

Definition at line 52 of file ellLib.h.

#define ellPrevious

(

PNODE

)

((PNODE)->previous)

Find the previous node in list.

Parameters

PNODE

Pointer to node whose predecessor is to be found

Returns

Pointer to the node prior to PNODE

Definition at line 104 of file ellLib.h.

Typedef Documentation

typedef struct ELLLIST ELLLIST

List header type.

typedef struct ELLNODE ELLNODE

List node type.

A list node (an ELLNODE) must be embedded in the structure to be placed on the list, ideally as the first member of that structure.

If the node is elsewhere in the structure, care must be taken to convert between the structure pointer and the node pointer and back every time when calling routines in the ellLib API. The ellFree() and ellFree2() routines cannot be used with such a list.

typedef void(* FREEFUNC) (void *)

Pointer to free() for use by ellFree() macro.

This is required for use on Windows, where each DLL has its own free() function. The ellFree() macro passes the application's version of free() to the ellFree2() function.

Definition at line 71 of file ellLib.h.

typedef int(* pListCmp) (const ELLNODE *A, const ELLNODE *B)

Definition at line 184 of file ellLib.h.

Function Documentation

LIBCOM_API void ellAdd	(	ELLLIST *	pList,
		ELLNODE *	pNode
	)

Adds a node to the end of a list.

Parameters

pList	Pointer to list descriptor
pNode	Pointer to node to be added

Definition at line 24 of file ellLib.c.

{
    pNode->next = NULL;
    pNode->previous = pList->node.previous;

    if (pList->count)
        pList->node.previous->next = pNode;
    else
        pList->node.next = pNode;

    pList->node.previous = pNode;
    pList->count++;

    return;
}

LIBCOM_API void ellConcat	(	ELLLIST *	pDstList,
		ELLLIST *	pAddList
	)

Concatenates a list to the end of another list. The list to be added is left empty. Either list (or both) can be empty at the beginning of the operation.

Parameters

pDstList	Destination list
pAddList	List to be added to pDstList

Definition at line 46 of file ellLib.c.

{
    if (pAddList->count == 0)
        return; /* Add list is empty, nothing to add. */

    if (pDstList->count == 0) {
        /* Destination list is empty... just transfer the add list over. */
        pDstList->node.next = pAddList->node.next;
        pDstList->node.previous = pAddList->node.previous;
        pDstList->count = pAddList->count;
    } else {
        /* Destination list not empty... append the add list. */
        pDstList->node.previous->next = pAddList->node.next;
        pAddList->node.next->previous = pDstList->node.previous;
        pDstList->node.previous = pAddList->node.previous;
        pDstList->count += pAddList->count;
    }

    pAddList->count = 0;
    pAddList->node.next = NULL;
    pAddList->node.previous = NULL;

    return;
}

LIBCOM_API void ellDelete	(	ELLLIST *	pList,
		ELLNODE *	pNode
	)

Deletes a node from a list.

Parameters

pList	Pointer to list descriptor
pNode	Pointer to node to be deleted

Definition at line 75 of file ellLib.c.

{
    if (pList->node.previous == pNode)
        pList->node.previous = pNode->previous;
    else
        pNode->next->previous = pNode->previous;

    if (pList->node.next == pNode)
        pList->node.next = pNode->next;
    else
        pNode->previous->next = pNode->next;

    pList->count--;

    return;
}

LIBCOM_API void ellExtract	(	ELLLIST *	pSrcList,
		ELLNODE *	pStartNode,
		ELLNODE *	pEndNode,
		ELLLIST *	pDstList
	)

Extract a sublist from a list.

Parameters

pSrcList	Pointer to source list
pStartNode	First node in pSrcList to be extracted
pEndNode	Last node in pSrcList to be extracted
pDstList	Pointer to list where to put extracted list

Definition at line 101 of file ellLib.c.

{
    ELLNODE *pnode;
    int count;

    /* Cut the list out of the source list (update count later) */
    if (pStartNode->previous != NULL)
        pStartNode->previous->next = pEndNode->next;
    else
        pSrcList->node.next = pEndNode->next;

    if (pEndNode->next != NULL) {
        pEndNode->next->previous = pStartNode->previous;
        pEndNode->next = NULL;
    }
    else
        pSrcList->node.previous = pStartNode->previous;

    /* Place the sublist into the destination list */
    pStartNode->previous = pDstList->node.previous;
    if (pDstList->count)
        pDstList->node.previous->next = pStartNode;
    else
        pDstList->node.next = pStartNode;

    pDstList->node.previous = pEndNode;

    /* Adjust the counts */
    pnode = pStartNode;
    count = 1;
    while(pnode != pEndNode)
    {
        pnode = pnode->next;
        count++;
    }
    pSrcList->count -= count;
    pDstList->count += count;

    return;
}

LIBCOM_API int ellFind	(	ELLLIST *	pList,
		ELLNODE *	pNode
	)

Find the index of a specific node in a list.

Parameters

pList	Pointer to list to search
pNode	Pointer to node to search for

Returns

The node's index, or -1 if it cannot be found on the list.

Note

The first node has index 1.

Definition at line 258 of file ellLib.c.

{
    ELLNODE *got = pList->node.next;
    int count = 1;

    while ((got != pNode) && (got != NULL)) {
        got = got->next;
        count++;
    }
    if (got == NULL)
        return -1;

    return count;
}

LIBCOM_API void ellFree2	(	ELLLIST *	pList,
		FREEFUNC	freeFunc
	)

Free all the nodes in a list.

This routine empties a list, calling freeFunc() for every node on it.

Parameters

pList	List from which to free all nodes
freeFunc	The free() routine to be called

Note

The nodes in the list are free()'d on the assumption that the node structures were malloc()'d one-at-a-time and that the ELLNODE structure is the first member of the parent structure.

Definition at line 282 of file ellLib.c.

{
    ELLNODE *nnode = pList->node.next;
    ELLNODE *pnode;

    while (nnode != NULL)
    {
        pnode = nnode;
        nnode = nnode->next;
        freeFunc(pnode);
    }
    pList->node.next = NULL;
    pList->node.previous = NULL;
    pList->count = 0;
}

LIBCOM_API ELLNODE* ellGet

(

ELLLIST *

pList

)

Deletes and returns the first node from a list.

Parameters

pList

Pointer to list from which to get node

Returns

Pointer to the first node from the list, or NULL if the list is empty

Definition at line 147 of file ellLib.c.

{
    ELLNODE *pnode = pList->node.next;

    if (pnode != NULL)
        ellDelete(pList, pnode);

    return pnode;
}

LIBCOM_API void ellInsert	(	ELLLIST *	plist,
		ELLNODE *	pPrev,
		ELLNODE *	pNode
	)

Inserts a node into a list immediately after a specific node.

Parameters

plist	Pointer to list into which to insert node
pPrev	Pointer to the node after which to insert
pNode	Pointer to the node to be inserted

Note

If pPrev is NULL pNode will be inserted at the head of the list

Definition at line 178 of file ellLib.c.

{
    if (pPrev != NULL) {
        pNode->previous = pPrev;
        pNode->next = pPrev->next;
        pPrev->next = pNode;
    } else {
        pNode->previous = NULL;
        pNode->next = plist->node.next;
        plist->node.next = pNode;
    }

    if (pNode->next == NULL)
        plist->node.previous = pNode;
    else
        pNode->next->previous = pNode;

    plist->count++;

    return;
}

LIBCOM_API ELLNODE* ellNStep	(	ELLNODE *	pNode,
		int	nStep
	)

Find the list node nStep steps away from a specified node.

Parameters

pNode	The known node
nStep	How many steps to take, may be negative to step backwards

Returns

Pointer to the node nStep nodes from pNode, or NULL if there is no such node in the list.

Definition at line 237 of file ellLib.c.

{
    if (nStep > 0) {
        while ((pNode != NULL) && nStep) {
            pNode = pNode->next;
            nStep--;
        }
    } else {
        while ((pNode != NULL) && nStep) {
            pNode = pNode->previous;
            nStep++;
        }
    }
    return pNode;
}

LIBCOM_API ELLNODE* ellNth	(	ELLLIST *	pList,
		int	nodeNum
	)

Find the Nth node in a list.

Parameters

pList	Pointer to list from which to find node
nodeNum	Index of the node to be found

Returns

Pointer to the element at index nodeNum in pList, or NULL if there is no such node in the list.

Note

The first node has index 1.

Definition at line 205 of file ellLib.c.

{
    ELLNODE *pnode;

    if ((nodeNum < 1) || (pList->count == 0))
        return NULL;

    if (nodeNum > pList->count/2) {
        if (nodeNum > pList->count)
            return NULL;

        pnode = pList->node.previous;
        nodeNum = pList->count - nodeNum;
        while(nodeNum) {
            pnode = pnode->previous;
            nodeNum--;
        }
        return pnode;
    }

    pnode = pList->node.next;
    while (--nodeNum > 0)
        pnode = pnode->next;

    return pnode;
}

LIBCOM_API ELLNODE* ellPop

(

ELLLIST *

pList

)

Deletes and returns the last node from a list.

Parameters

pList

Pointer to list from which to get node

Returns

Pointer to the last node from the list, or NULL if the list is empty

Definition at line 162 of file ellLib.c.

{
   ELLNODE *pnode = pList->node.previous;

   if (pnode != NULL)
       ellDelete(pList, pnode);

   return pnode;
}

LIBCOM_API void ellSortStable	(	ELLLIST *	pList,
		pListCmp	pListCmp
	)

Stable (MergeSort) of a given list.

Parameters

pList	Pointer to list to be sorted
pListCmp	Compare function to be used

Note

The comparison function cmp(A,B) is expected to return -1 for A<B, 0 for A==B, and 1 for A>B.

Use of mergesort algorithm based on analysis by http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

Definition at line 30 of file ellSort.c.

{
    ELLLIST INP, P, Q;
    size_t insize = 1; /* initial sub-list size */
    if(ellCount(pList)<=1)
        return;

    ellInit(&INP);
    ellInit(&P);
    ellInit(&Q);

    /* Process is to iteratively sort
     * a sequence of sub-lists of size 'insize'
     */

    while(insize < ellCount(pList)) {

        assert(ellCount(&INP)==0);

        /* shift previous results to inputs */
        ellConcat(&INP, pList);

        while(ellCount(&INP))
        {
            ELLNODE *p, *q;

            /* Pull out the next pair of sub-lists */
            ellMoveN(&Q, &INP, insize);
            ellMoveN(&P, &INP, insize);

            /* merge these sub-lists */
            while((p=ellFirst(&P)) && (q=ellFirst(&Q)))
            {
                if((*cmp)(p,q) < 0) {
                    ellAdd(pList, ellGet(&P));
                } else {
                    ellAdd(pList, ellGet(&Q));
                }
            }

            /* concatenate any remaining to result */
            if(ellFirst(&P))
                ellConcat(pList, &P);
            else if(ellFirst(&Q))
                ellConcat(pList, &Q);

            assert(!ellFirst(&P) && !ellFirst(&Q));
        }

        insize *= 2;
    }

}

LIBCOM_API void ellVerify

(

ELLLIST *

pList

)

Verifies that the list is consistent.

Parameters

pList

List to be verified

Definition at line 304 of file ellLib.c.

{
    ELLNODE *pNode;
    ELLNODE *pNext;
    int count = 0;

    assert (pList);

    pNode = ellFirst(pList);
    if (pNode) {
        assert (ellPrevious(pNode) == NULL);
        while (1) {
            count++;
            pNext = ellNext(pNode);
            if (pNext) {
                assert (ellPrevious(pNext) == pNode);
            } else {
                break;
            }
            pNode = pNext;
        }
        assert (ellNext(pNode) == NULL);
    }

    assert (pNode == ellLast(pList));
    assert (count == ellCount(pList));
}