ellLib.h
A doubly-linked list library.
This provides similar functionality to the VxWorks lstLib library.
- Author
John Winans (ANL)
- Author
Andrew Johnson (ANL)
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.
Defines
-
ELLNODE_INIT
Value of a terminal node.
-
ELLLIST_INIT
Value of an empty list.
-
ellInit(PLIST)
Initialize a list type.
- Parameters:
PLIST – Pointer to list header to be initialized
-
ellCount(PLIST)
Report the number of nodes in a list.
- Parameters:
PLIST – Pointer to list descriptor
- Returns:
Number of nodes in the list
-
ellFirst(PLIST)
Find the first node in list.
- Parameters:
PLIST – Pointer to list descriptor
- Returns:
Pointer to first node in the list
-
ellLast(PLIST)
Find the last node in list.
- Parameters:
PLIST – Pointer to list descriptor
- Returns:
Pointer to last node in the list
-
ellNext(PNODE)
Find the next node in list.
- Parameters:
PNODE – Pointer to node whose successor is to be found
- Returns:
Pointer to the node following
PNODE
-
ellPrevious(PNODE)
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
-
ellFree(PLIST)
Free up the list.
- Parameters:
PLIST – List for which to free all nodes
Typedefs
-
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.
Functions
-
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
-
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
-
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
-
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 extractedpEndNode – Last node in
pSrcList
to be extractedpDstList – Pointer to list where to put extracted list
-
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
-
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
-
void ellInsert(ELLLIST *plist, ELLNODE *pPrev, ELLNODE *pNode)
Inserts a node into a list immediately after a specific node.
Note
If
pPrev
is NULLpNode
will be inserted at the head of the list- 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
-
ELLNODE *ellNth(ELLLIST *pList, int nodeNum)
Find the Nth node in a list.
Note
The first node has index 1.
- 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.
-
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 frompNode
, or NULL if there is no such node in the list.
-
int ellFind(ELLLIST *pList, ELLNODE *pNode)
Find the index of a specific node in a list.
Note
The first node has index 1.
- 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.
-
void ellSortStable(ELLLIST *pList, pListCmp pListCmp)
Stable (MergeSort) of a given list.
Note
The comparison function cmp(A,B) is expected to return -1 for A<B, 0 for A==B, and 1 for A>B.
Note
Use of mergesort algorithm based on analysis by http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
- Parameters:
pList – Pointer to list to be sorted
pListCmp – Compare function to be used
-
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.
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.
- Parameters:
pList – List from which to free all nodes
freeFunc – The free() routine to be called
-
struct ELLNODE
- #include <ellLib.h>
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.
-
struct ELLLIST
- #include <ellLib.h>
List header type.