ellLib.c File Reference

#include <stdlib.h>
#include "epicsAssert.h"
#include "ellLib.h"

Include dependency graph for ellLib.c:

Go to the source code of this file.

Functions
void	ellAdd (ELLLIST *pList, ELLNODE *pNode)
	Adds a node to the end of a list. More...
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...
void	ellDelete (ELLLIST *pList, ELLNODE *pNode)
	Deletes a node from a list. More...
void	ellExtract (ELLLIST *pSrcList, ELLNODE *pStartNode, ELLNODE *pEndNode, ELLLIST *pDstList)
	Extract a sublist from a list. More...
ELLNODE *	ellGet (ELLLIST *pList)
	Deletes and returns the first node from a list. More...
ELLNODE *	ellPop (ELLLIST *pList)
	Deletes and returns the last node from a list. More...
void	ellInsert (ELLLIST *plist, ELLNODE *pPrev, ELLNODE *pNode)
	Inserts a node into a list immediately after a specific node. More...
ELLNODE *	ellNth (ELLLIST *pList, int nodeNum)
	Find the Nth node in a list. More...
ELLNODE *	ellNStep (ELLNODE *pNode, int nStep)
	Find the list node nStep steps away from a specified node. More...
int	ellFind (ELLLIST *pList, ELLNODE *pNode)
	Find the index of a specific node in a list. More...
void	ellFree2 (ELLLIST *pList, FREEFUNC freeFunc)
	Free all the nodes in a list. More...
void	ellVerify (ELLLIST *pList)
	Verifies that the list is consistent. More...

Function Documentation

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

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

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

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

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

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

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

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

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

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

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

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