doubly linked list library

Myth丶恋晨 2021-12-01 14:08 219阅读 0赞

lstLib.h

/* lstLib.h - doubly linked list library header */
    
    /* Copyright 1984-1993 Wind River Systems, Inc. */
    
    /*
    modification history
    --------------------
    01m,02apr93,edm  ifdef'd out non-ASMLANGUAGE portions
    01l,22sep92,rrr  added support for c++
    01k,04jul92,jcf  cleaned up.
    01j,26may92,rrr  the tree shuffle
    01i,04oct91,rrr  passed through the ansification filter
    		  -changed VOID to void
    		  -changed copyright notice
    01h,23oct90,shl  included "vxWorks.h" so include file order isn't crucial.
    01g,05oct90,shl  added ANSI function prototypes.
                     made #endif ANSI style.
                     added copyright notice.
    01f,10aug90,dnw  added declaration of lstInsert().
    01e,07aug90,shl  added IMPORT type to function declarations.
    01d,21may86,llk	 added forward declaration of lstNStep.
    01c,03jun84,dnw  changed list.{head,tail} to list.node.
    		 added declarations of lst{First,Last,Next,Previous}.
    01b,27jan84,ecs  added inclusion test.
    01b,15mar83,dnw  changed name from lstlb to lstLib
    */
    
    #ifndef __INClstLibh
    #define __INClstLibh
    
    #ifndef _ASMLANGUAGE
    
    #ifdef __cplusplus
    extern "C" {
    #endif
    
    
    /* type definitions */
    
    typedef struct node		/* Node of a linked list. */
        {
        struct node *next;		/* Points at the next node in the list */
        struct node *previous;	/* Points at the previous node in the list */
        } NODE;
    
    
    /* HIDDEN */
    
    typedef struct			/* Header for a linked list. */
        {
        NODE node;			/* Header list node */
        int count;			/* Number of nodes in list */
        } LIST;
    
    /* END_HIDDEN */
    
    
    extern NODE *	lstFirst (LIST *pList);
    extern NODE *	lstGet (LIST *pList);
    extern NODE *	lstLast (LIST *pList);
    extern NODE *	lstNStep (NODE *pNode, int nStep);
    extern NODE *	lstNext (NODE *pNode);
    extern NODE *	lstNth (LIST *pList, int nodenum);
    extern NODE *	lstPrevious (NODE *pNode);
    extern int 	lstCount (LIST *pList);
    extern int 	lstFind (LIST *pList, NODE *pNode);
    extern void 	lstAdd (LIST *pList, NODE *pNode);
    extern void 	lstConcat (LIST *pDstList, LIST *pAddList);
    extern void 	lstDelete (LIST *pList, NODE *pNode);
    extern void 	lstExtract (LIST *pSrcList, NODE *pStartNode, NODE *pEndNode,
    	  		    LIST *pDstList);
    extern void 	lstFree (LIST *pList);
    extern void 	lstInit (LIST *pList);
    extern void 	lstInsert (LIST *pList, NODE *pPrev, NODE *pNode);
    
    
    #ifdef __cplusplus
    }
    #endif
    
    #endif /* ~ _ASMLANGUAGE */
    
    #endif /* __INClstLibh */

tmsTypes.h

/* tmsTypes.h - Types portable application programming interface. */
    
    /* Copyright 1998-2000 Wind River Systems, Inc. */
    
    /*
    modification history
    --------------------
    01b,12jun00,kw   Added the lstLib.h include.
    01a,12dec98,kw   Created.
    */
    
    #ifndef __INCtmsTypesh
    #define __INCtmsTypesh
    
    #ifdef __cplusplus
    extern "C" {
    #endif /* __cplusplus */
    
    typedef unsigned char   uchar_t;
    typedef unsigned short  ushort_t;
    typedef unsigned int    uint_t;
    typedef unsigned long   ulong_t;
    #ifndef __BOOLEAN_DEFINED__
    #define __BOOLEAN_DEFINED__
    typedef  ulong_t        Boolean; 
    #endif 
    
    enum { False = 0, True = 1};
    #define FAST    register
    
    #define _ALLOC_ALIGN_SIZE 8 /* 4 byte boundary */
    
    #ifdef __cplusplus
    }
    #endif
    
    #endif /* __INCtmsTypesh */

lstLib.c

/* lstLib.c - doubly linked list subroutine library */
    
    /*
    modification history
    --------------------
    01z,05oct98,jmp  doc: cleanup.
    01y,14oct95,jdi  doc: fixed typo in lstNth().
    01x,13feb95,jdi  doc format change.
    01w,20jan93,jdi  documentation cleanup for 5.1.
    01v,09jul92,hdn  put an optimized lstGet()
    01u,26may92,rrr  the tree shuffle
    01t,25nov91,rrr  cleanup of some ansi warnings.
    01s,04oct91,rrr  passed through the ansification filter
                      -changed functions to ansi style
    		  -changed VOID to void
    		  -changed copyright notice
    01r,30apr91,jdi	 documentation tweaks.
    01q,05apr91,jdi	 documentation -- removed header parens and x-ref numbers;
    		 doc review by dnw.
    01p,11feb91,jaa	 documentation cleanup.
    01o,05nov87,jlf  documentation
    01n,02apr87,ecs  hushed lint in lstFree.
    01m,25mar87,jlf  documentation
    01l,21dec86,dnw  changed to not get include files from default directories.
    01k,01jul86,jlf  documentation.
    01j,21may86,llk	 added lstFree and lstNStep.
    01i,09apr86,rdc  added lstFind.
    01h,20jul85,jlf  documentation.
    01g,19sep84,jlf  fixed spacing in comments by adding .ne's.
    01f,08sep84,jlf  added comments and copyright notice.
    01e,29jun84,dnw  added lstConcat and lstExtract.
    01d,03jun84,dnw  added lstFirst, lstLast.
    		 changed list.{head,tail} to list.node.{next,previous}.
    		 cleaned up comments, etc.
    01c,07may84,ecs  added lstNext, lstPrevious, and lstCount.
    01b,09jun83,ecs  modified the documentation
    01a,06aug82,dnw  created from old singly-linked-list lib which is now "slllb".
    */
    
    
    /*
    DESCRIPTION
    This subroutine library supports the creation and maintenance of a
    doubly linked list.  The user supplies a list descriptor (type LIST)
    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.
    
    The linked-list library simply manipulates the linked-list data structures;
    no kernel functions are invoked.  In particular, linked lists by themselves
    provide no task synchronization or mutual exclusion.  If multiple tasks will
    access a single linked list, that list must be guarded with some
    mutual-exclusion mechanism (e.g., a mutual-exclusion semaphore).
    
    NON-EMPTY LIST:
    .CS
       ---------             --------          --------
       | head--------------->| next----------->| next---------
       |       |             |      |          |      |      |
       |       |       ------- prev |<---------- prev |      |
       |       |       |     |      |          |      |      |
       | tail------    |     | ...  |    ----->| ...  |      |
       |       |  |    v                 |                   v
       |count=2|  |  -----               |                 -----
       ---------  |   ---                |                  ---
                  |    -                 |                   -
                  |                      |
                  ------------------------
    .CE
    
    EMPTY LIST:
    .CS
    	-----------
            |  head------------------
            |         |             |
            |  tail----------       |
            |         |     |       v
            | count=0 |   -----   -----
            -----------    ---     ---
                            -	-
    .CE
    
    INCLUDE FILES: lstLib.h
    */
    
    
    /* LINTLIBRARY */
    
    #include "lstlib.h"
    #include "stdlib.h"
    #include "rosmid.h"
    #include "msan_type.h"
    #include "tmstypes.h"
    
    #define HEAD    node.next		/* the first node in list */
    #define TAIL	node.previous	/* the last node in list */
    
    /*********************************************************************
    * lstInit - initialize a list descriptor
    * This routine initializes a specified list to an empty list.
    * RETURNS: N/A
    */
    
    void lstInit(FAST LIST *pList)  
        {
        pList->TAIL  = NULL;
        pList->HEAD	 = NULL;
        pList->count = 0;
        }
        
    /*************************************************************************
    * lstAdd - add a node to the end of a list
    * This routine adds a specified node to the end of a specified list.
    * RETURNS: N/A
    */
    
    void lstAdd(LIST *pList, NODE *pNode)
        {
        lstInsert (pList, pList->TAIL, pNode);
        }
    /**************************************************************************
    * lstConcat - concatenate two lists
    * This routine concatenates the second list to the end of the first list.
    * The second list is left empty.  Either list (or both) can be
    * empty at the beginning of the operation.
    * RETURNS: N/A
    */
    
    void lstConcat (FAST LIST *pDstList, FAST LIST *pAddList)
        {
        if (pAddList->count == 0)		/* nothing to do if AddList is empty */
    	{
    	    return;
    	}
    
        if (pDstList->count == 0)
    	{
    	    *pDstList = *pAddList;
    	}
        else
    	{
    	/* both lists non-empty; update DstList pointers */
        	pDstList->TAIL->next     = pAddList->HEAD;
        	pAddList->HEAD->previous = pDstList->TAIL;
        	pDstList->TAIL           = pAddList->TAIL;
        	pDstList->count += pAddList->count;
    	}
    
        lstInit (pAddList);
        }
        
    void lstDelete(FAST LIST *pList, FAST NODE *pNode)
        {
        if (pNode->previous == NULL)
    	    pList->HEAD = pNode->next;
        else
    	    pNode->previous->next = pNode->next;
    
        if (pNode->next == NULL)
    	    pList->TAIL = pNode->previous;
        else
    	    pNode->next->previous = pNode->previous;
    
        pList->count--;
        }
    
    int lstCount(LIST *pList)  
        {
            return (pList->count);
        }
    
    void lstExtract(FAST LIST *pSrcList, FAST NODE *pStartNode, FAST NODE *pEndNode, FAST LIST *pDstList)
        {
        FAST NODE *pNode;
        FAST int i;
    
        if (pStartNode->previous == NULL)
    	    pSrcList->HEAD = pEndNode->next;
        else
    	    pStartNode->previous->next = pEndNode->next;
    
        if (pEndNode->next == NULL)
    	    pSrcList->TAIL = pStartNode->previous;
        else
    	    pEndNode->next->previous = pStartNode->previous;
    
        /* fix the pointers in extracted list */
        pDstList->TAIL = pEndNode;
        pDstList->HEAD = pStartNode;
        
        pEndNode->next       = NULL;  
        pStartNode->previous = NULL;
    
        /* count number of nodes in extracted list and update counts in lists */
    
        i = 0;
    
        for (pNode = pStartNode; pNode != NULL; pNode = pNode->next)
    	    i++;
    
        pSrcList->count -= i;
        /* fix the number */
        pDstList->count = i;
        /* fix the number */
        }
        
    /************************************************************************
    * lstFirst - find first node in list
    * This routine finds the first node in a linked list.
    * RETURNS
    * A pointer to the first node in a list, or
    * NULL if the list is empty.
    */
    
    NODE *lstFirst(LIST *pList) /* find first node in list */
        {
        return (pList->HEAD);
        }
        
    /************************************************************************
    * lstGet - delete and return the first node from a list
    * This routine gets the first node from a specified list, deletes the node
    * from the list, and returns a pointer to the node gotten.
    * RETURNS
    * A pointer to the node gotten, or
    * NULL if the list is empty.
    */
    
    NODE *lstGet(FAST LIST *pList)
        {
        FAST NODE *pNode = pList->HEAD;
    
        if (pNode != NULL)
    	{
    	pList->HEAD = pNode->next;          
        /* make next node be 1st */
    	if (pNode->next == NULL)            
    	    pList->TAIL = NULL;
    	else
    	    pNode->next->previous = NULL;
    
    	pList->count--;                     
    	/* update node number */
    	}
    
        return (pNode);
        }
        
    /************************************************************************
    * lstInsert - insert a node in a list after a specified node
    * This routine inserts a specified node in a specified list.
    * The new node is placed following the list node <pPrev>.
    * If <pPrev> is NULL, the node is inserted at the head of the list.
    * RETURNS: N/A
    */
    
    void lstInsert(FAST LIST *pList, FAST NODE *pPrev, FAST NODE *pNode)
        {
        /*insert a node in a list after a specified node*/
        FAST NODE *pNext;
    
        if (pPrev == NULL)
    	{				
    	/* new node be first in list */
    	pNext = pList->HEAD;
    	pList->HEAD = pNode;
    	}
        else
    	{				
    	/* make prev node point forward to new */
    	pNext = pPrev->next;
    	pPrev->next = pNode;
    	}
    
        if (pNext == NULL)
    	    pList->TAIL = pNode;		/* new node be last in list */
        else
    	    pNext->previous = pNode;	/* make next node point to new */
    
    
        /* set new node, and update node num */
        pNode->previous	= pPrev;
        pNode->next		= pNext;
        pList->count++;
        }
        
    /************************************************************************
    * lstLast - find the last node in a list
    * This routine finds the last node in a list.
    * RETURNS
    * A pointer to the last node in the list, or
    * NULL if the list is empty.
    */
    
    NODE *lstLast(LIST *pList)
        {
        return (pList->TAIL);
        }
        
    /************************************************************************
    * lstNext - find the next node in a list
    * This routine locates the node immediately following a specified node.
    * RETURNS:
    * A pointer to the next node in the list, or
    * NULL if there is no next node.
    */
    
    NODE *lstNext(NODE *pNode)
        {
        return (pNode->next);
        }
        
    /************************************************************************
    * lstNth - find the Nth node in a list
    * This routine returns a pointer to the node specified by a number <nodenum>
    * where the first node in list is numbered 1.
    * Note that the search is optimized by searching forward from the beginning
    * if the node is closer to the head, and searching back from the end
    * if it is closer to the tail.
    * RETURNS:
    * A pointer to the Nth node, or
    * NULL if there is no Nth node.
    */
    
    NODE *lstNth(FAST LIST *pList, FAST int nodenum)
        {
        FAST NODE *pNode;
    
        /* verify node number */
        if ((nodenum > pList->count) || (nodenum < 1))
    	    return (NULL);
    
        if (nodenum < (pList->count >> 1))
    	{
    	/*look forward from beginning*/
    	pNode = pList->HEAD;
    	while (--nodenum > 0)
    	    pNode = pNode->next;
    	}
    
        else
    	{
    	/*otherwise look back from end */
    	pNode = pList->TAIL;
    	nodenum -= pList->count;
    	
    	while (nodenum++ < 0)
    	    pNode = pNode->previous;
    	}
    
        return (pNode);
        }
        
    
    
    NODE *lstPrevious(NODE *pNode)
        {
        return (pNode->previous);
        }
        
    
    NODE *lstNStep(FAST NODE *pNode, int nStep)
        {
        /*find a list node <nStep> steps away from a specified node*/
        int j;
        for (j = 0; j < abs(nStep); j++)
    	{
    	if (nStep > 0)
    	    pNode = pNode->next;
    	else if (nStep < 0)
    	    pNode = pNode->previous;
    	if (NULL == pNode)
    	    break;
    	}
        return (pNode);
        }
    
    /************************************************************************
    * lstFind - find a node in a list
    * This routine returns the node number of a specified node (the 
    * first node is 1).
    * RETURNS:
    * The node number, or
    * ERROR if the node is not found.
    */
    
    int lstFind(LIST *pList, FAST NODE *pNode)
        {
        /*find a node in a list*/
        FAST int index = 1;
        FAST NODE *pNextNode;
    
        pNextNode = lstFirst (pList);
    
        while ((NULL != pNextNode) && (pNextNode != pNode))
    	{
    	pNextNode = lstNext (pNextNode);
    	index++;
    	}
    
        if (NULL == pNextNode)
    	    return (ERROR);
        else
    	    return (index);
        }
    
    /************************************************************************
    * lstFree - free up a list
    * This routine turns any list into an empty list.
    * It also frees up memory used for nodes.
    * RETURNS: N/A
    * SEE ALSO: free()
    */
    
    void lstFree(LIST *pList)
        {
        NODE *p1, *p2;
    
        if (pList->count > 0)
    	{
    	p1 = pList->HEAD;
    	while (NULL != p1)
        {
            p2 = p1->next;
            OsFree((char*)p1, MID_MSAN_LIB);
            p1 = p2;
        }
    	pList->HEAD = pList->TAIL = NULL;
    	pList->count = 0;
    	}
        }
    
    
    #ifndef LIST_FREE_FUNC_DEFINDED
    #define LIST_FREE_FUNC_DEFINDED
    typedef void (*LIST_FREE_FUNC)(NODE *);
    #endif
    
    void lstFreeWithFunc(LIST *pList, LIST_FREE_FUNC v_Func)
    {
        NODE *p1, *p2;
    
        if (NULL == v_Func)
            return;
            
        if (pList->count > 0)
        {
            p1 = pList->HEAD;
            while (NULL != p1)
            {
                p2 = p1->next;
                v_Func(p1);
                p1 = p2;
            }
            pList->HEAD = pList->TAIL = NULL;    
            pList->count = 0;
        }
    }