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.

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

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 extracted

  • pEndNode – Last node in pSrcList to be extracted

  • pDstList – 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 NULL pNode 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 from pNode, 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

void ellVerify(ELLLIST *pList)

Verifies that the list is consistent.

Parameters:

pList – List to be verified

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.

Public Members

struct ELLNODE *next

Pointer to next node in list.

struct ELLNODE *previous

Pointer to previous node in list.

struct ELLLIST
#include <ellLib.h>

List header type.

Public Members

ELLNODE node

Pointers to the first and last nodes on list.

int count

Number of nodes on the list.