singlelist.c

多任务下的数据结构与算法的源码

/*
 * Copyright (c) 2000-2008
 * Author: Weiming Zhou
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  
 */

#include <stdlib.h>
#include <string.h>
#include "CapiGlobal.h"
#include "SingleList.h"

 
/**	单向链表的创建函数，创建完后链表还是空的没有节点在里面

	@param	void - 无	
	@return	SINGLELIST * - 失败返回NULL, 成功时返回一个单向链表结构体指针	
*/
SINGLELIST * SingleList_Create( void )
{
    SINGLELIST  *pSingleList;

    /* 分配内存操作 */
    pSingleList = (SINGLELIST *)malloc(sizeof(SINGLELIST));
    if ( pSingleList != NULL )
    {
        /* 初始化链表结构体各指针成员为空，链表节点个数为0 */
        pSingleList->pCur = NULL;
        pSingleList->pHead = NULL;
        pSingleList->pTail = NULL;
        pSingleList->uCount = 0;
    }

    return pSingleList;
}


/**	单向链表的释放函数

	@param	SINGLELIST *pSingleList - 要释放的单向链表的指针	
	@param	DESTROYFUNC pDestroyFunc - 链表节点数据释放回调函数	
	@return	void - 无	
*/
void SingleList_Destroy( SINGLELIST *pSingleList, DESTROYFUNC DestroyFunc )
{
    SINGLENODE  *pNode;

    if ( pSingleList )
    {
        /* 从头节点开始，一个接一个释放链表节点及节点数据 */
        pNode = pSingleList->pHead;
        while ( pNode != NULL )
        {
            SINGLENODE  *pDelNode;

            pDelNode = pNode;
            pNode = pNode->pNext;

            if ( DestroyFunc != NULL && pDelNode->pData != NULL )
            {
                /* 释放数据 */
                (*DestroyFunc)( pDelNode->pData );
            }
            free( pDelNode ); /* 释放节点 */
        }
        /* 释放链表结构体 */ 
        free( pSingleList );
    }
}


/**	单向链表的添加节点函数，添加的节点放在单向链表的头部

	@param	SINGLELIST *pSingleList - 要添加的单向链表指针	
	@param	void *pData - 要添加的节点的数据指针	
	@return	INT - 失败返回CAPI_FAILED，成功返回CAPI_SUCCESS	
*/
INT	SingleList_InsertHead( SINGLELIST *pSingleList, void *pData )
{
    SINGLENODE  *pNode;

    /* 参数校验 */
    if ( pSingleList == NULL || pData == NULL )
    {
        return CAPI_FAILED;
    }

    /* 新建一个节点 */
    pNode = (SINGLENODE *)malloc( sizeof(SINGLENODE) );
    if ( pNode == NULL )
    {
        return CAPI_FAILED;
    }
    pNode->pData = pData;  /* 将节点数据指针指向传进来的数据 */

    /* 将新建节点的下一节点指针指向头节点，并将头节点改为新建的节点 */
    pNode->pNext = pSingleList->pHead;
    pSingleList->pHead = pNode;

    /*
     * 判断是否尾节点指针为空，如果为空表示原来链表中没有节点，
     * 此时应该将尾节点指向新加入的节点 
     */
    if ( pSingleList->pTail == NULL )
    {
        pSingleList->pTail = pNode;
    }

    /* 将链表节点数据加1 */
    pSingleList->uCount++;
    
    return CAPI_SUCCESS;
}


/**	单向链表的添加节点函数，添加的节点放在单向链表的尾部

	@param	SINGLELIST *pSingleList - 要添加的单向链表指针	
	@param	void *pData - 要添加的节点的数据指针
	@return	INT - 失败返回CAPI_FAILED，成功返回CAPI_SUCCESS	
*/
INT	SingleList_InsertTail( SINGLELIST *pSingleList, void *pData )
{
    SINGLENODE  *pNode;

    /* 参数校验 */
    if ( pSingleList == NULL || pData == NULL )
    {
        return CAPI_FAILED;
    }

    /* 新建一个节点 */
    pNode = (SINGLENODE *)malloc( sizeof(SINGLENODE) );
    if ( pNode == NULL )
    {
        return CAPI_FAILED;
    }
    pNode->pData = pData;  /* 将节点数据指针指向传进来的数据 */
    pNode->pNext = NULL;   /* 将节点的下一节点赋为空指针NULL */

    /*
     * 判断是否尾节点指针为空，如果为空表示原来链表中没有节点，
     * 此时应该将尾节点指向新加入的节点, 并且头节点指针也应该指向新节点 
     */
    if ( pSingleList->pTail == NULL )
    {
        pSingleList->pTail = pNode;
        pSingleList->pHead = pNode;
    }
    else
    {
        /*
         * 如果尾节点指针不为空，此时应该将尾节点下一节点指针指向新加入的节点, 
         * 并且尾节点指针也应该指向新节点 
         */
        pSingleList->pTail->pNext = pNode;
        pSingleList->pTail = pNode;
    }

    /* 将链表节点数据加1 */
    pSingleList->uCount++;
    
    return CAPI_SUCCESS;
}


/**	单向链表的弹出头节点函数

	@param	SINGLELIST *pSingleList - 要操作的单向链表指针	
	@return	void * - 失败返回NULL, 成功返回要弹出的头节点的数据指针	
*/
void *	SingleList_PopHead( SINGLELIST *pSingleList )
{
	SINGLENODE	*pPopNode;   /* 用来指向要弹出数据的节点的指针 */
	void		*pPopData;   /* 用来指向要弹出的数据的指针 */

    /* 参数校验 */
    if ( pSingleList == NULL || pSingleList->pHead == NULL ) 
    {
		return NULL;
    }

    /* 将要弹出数据的节点指针指向链表头节点，弹出数据指针指向头节点的数据 */
    pPopNode = pSingleList->pHead;
    pPopData = pPopNode->pData;

    /* 
     * 判断当前节点指针是否指向头节点，如果指向头节点的话则需要将其
     * 指向头节点的下一节点 
     */
    if ( pSingleList->pCur == pSingleList->pHead )
    {
        pSingleList->pCur = pSingleList->pHead->pNext;
    }

    /* 将头节点指针指向头节点的下一节点 */
    pSingleList->pHead = pSingleList->pHead->pNext;
	
    /* 将链表节点数量减1 */
    pSingleList->uCount--;

    /* 如果链表的节点数量已经为0则表示原来只有一个节点，弹出头节点后，
     * 此时链表已经为空，没有节点在里面，此时应该将尾节点指针赋空
     * 当前节点指针由于前面已经处理过了，如果只有一个节点的话肯定为空
     * 所以这里不需要处理当前节点指针
     */
    if ( pSingleList->uCount == 0 ) {
		pSingleList->pTail = NULL;
	}
	
    /* 释放弹出的节点, 注意这里并没有释放节点数据指针 */
    free( pPopNode );

    return pPopData;    /* 返回头节点的数据指针 */
}


/** 单向链表的弹出尾节点函数
    这个函数由于要查找尾节点的前一节点，因此效率很低

    @param	SINGLELIST *pSingleList - 要操作的单向链表指针	
    @return	void * -  失败返回NULL, 成功返回要弹出的尾节点的数据指针	
*/
void *	SingleList_PopTail( SINGLELIST *pSingleList )
{
    SINGLENODE	*pPopNode;   /* 用来指向要弹出数据的节点的指针 */
    SINGLENODE	*pTailPrevNode;   /* 用来指向尾节点的上一节点的指针 */
    void		*pPopData;   /* 用来指向要弹出的数据的指针 */

    /* 参数校验 */
    if ( pSingleList == NULL || pSingleList->pHead == NULL ) 
    {
        return NULL;
	}

    /* 将要弹出数据的节点指针指向链表头节点，弹出数据指针指向头节点的数据 */
    pPopNode = pSingleList->pTail;
    pPopData = pPopNode->pData;

    pTailPrevNode = pSingleList->pHead;

    /* 如果链表的头节点和尾节点相同则表示原来只有一个节点，弹出尾节点后，
     * 此时链表已经为空，没有节点在里面，此时应该将头节点指针赋空
     * 当前节点指针由于前面已经处理过了，如果只有一个节点的话肯定为空
     * 所以这里不需要处理当前节点指针
     */
    if ( pSingleList->pTail == pSingleList->pHead )
    {
        pTailPrevNode = NULL;
	    pSingleList->pHead = NULL;
    }
    else 
    {
        while ( pTailPrevNode != NULL )
        {
            if ( pTailPrevNode->pNext == pSingleList->pTail )
            {
                break;
            }
            pTailPrevNode = pTailPrevNode->pNext;
        }
    }

    /* 
     * 判断当前节点指针是否指向尾节点，如果指向头节点的话则需要将其
     * 指向尾节点的前一节点 
     */
    if ( pSingleList->pCur == pSingleList->pTail )
    {
        pSingleList->pCur = pTailPrevNode;
    }

    /* 将尾节点指针指向尾节点的前一节点 */
    pSingleList->pTail = pTailPrevNode;

    if ( pTailPrevNode != NULL )
    {
        pTailPrevNode->pNext = NULL;
    }
    
    /* 将链表节点数量减1 */
    pSingleList->uCount--;

    /* 释放弹出的节点, 注意这里并没有释放节点数据指针 */
    free( pPopNode );

    return pPopData;    /* 返回头节点的数据指针 */    
}


/**	链表的删除节点函数，它将删除和pMatchData参数有相同数据的节点
    如果有许多有相同数据的节点它将只删除第一个有相同数据的节点

	@param	SINGLELIST *pSingleList - 要操作的单向链表指针	
	@param	void *pMatchData - 要删除节点的匹配数据	
	@param	COMPAREFUNC CompareFunc - 数据比较函数用来比较pMatchData参数和链表
                                      节点参数是否相等	
	@param	DESTROYFUNC DestroyFunc - 链表节点的数据释放函数	
	@return	INT (by default) - CAPI_FAILED表示失败或链表中没有匹配的数据，CAPI_SUCCESS表示成功删除	
*/
INT	 SingleList_Delete( SINGLELIST *pSingleList,  
                        void *pMatchData, 
                        COMPAREFUNC CompareFunc, 
                        DESTROYFUNC DestroyFunc )
{
    SINGLENODE  *pNode;
    SINGLENODE  *pPrevNode;

    /* 参数校验 */
    if ( pSingleList == NULL || CompareFunc == NULL )
    {
        return CAPI_FAILED;
    }

    pNode = pSingleList->pHead;
    pPrevNode = pNode;

    while ( pNode != NULL )
    {
        /* 比较节点数据是否和匹配数据匹配 */
        if ( (*CompareFunc)( pNode->pData, pMatchData ) == 0 )
        {
            if ( pPrevNode == pNode )
            {
                /* 头节点匹配上了，需要删除头节点 */
                pSingleList->pHead = pNode->pNext;
                if ( pSingleList->pTail == pNode )
                {
                    /* 
                     * 如果尾节点和pNode相同，表明链表里只有一个节点
                     * 此时需要将链表尾节点指针和链表当前节点指针赋空
                     */
                    pSingleList->pTail = NULL;
                    pSingleList->pCur = NULL;
                }
            }
            else
            {
                pPrevNode->pNext = pNode->pNext;
                if ( pSingleList->pTail == pNode )
                {
                    /* 
                     * 如果尾节点和pNode相同，表明删除的是尾节点
                     * 此时需要将尾节点指针指向要删除节点的前一个节点
                     */
                    pSingleList->pTail = pPrevNode;
                }

                if ( pSingleList->pCur == pNode )
                {
                    /* 
                     * 如果链表当前节点和pNode相同，表明删除的是当前节点
                     * 此时需要将当前节点指针指向要删除节点的下一个节点
                     */