doublelist.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 <windows.h>

#include "CapiGlobal.h"
#include "DoubleList.h"


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

	@param	void - 无	
	@return	DOUBLELIST * - 失败返回NULL, 成功时返回一个双向链表结构体指针	
*/
DOUBLELIST * DoubleList_Create( void )
{
    DOUBLELIST  *pList;

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

    return pList;
}


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

	@param	DOUBLELIST *pList - 要释放的双向链表的指针	
	@param	DESTROYFUNC pDestroyFunc - 链表节点数据释放回调函数	
	@return	void - 无	
*/
void DoubleList_Destroy( DOUBLELIST *pList, DESTROYFUNC DestroyFunc )
{
    DOUBLENODE  *pNode;

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

            pDelNode = pNode;
            pNode = pNode->pNext;

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


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

	@param	DOUBLELIST *pList - 要添加的双向链表指针	
	@param	void *pData - 要添加的节点的数据指针	
	@return	INT - 失败返回CAPI_FAILED，成功返回CAPI_SUCCESS	
*/
INT	DoubleList_InsertHead( DOUBLELIST *pList, void *pData )
{
    DOUBLENODE  *pNode;

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

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

    /* 将新建节点的下一节点指针指向头节点，并将头节点改为新建的节点 */
    pNode->pNext = pList->pHead;
    pNode->pPrev = NULL;
    if ( pList->pHead != NULL )
    {
        pList->pHead->pPrev = pNode;
    }
    pList->pHead = pNode;

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

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


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

	@param	DOUBLELIST *pList - 要添加的双向链表指针	
	@param	void *pData - 要添加的节点的数据指针
	@return	INT - 失败返回CAPI_FAILED，成功返回CAPI_SUCCESS	
*/
INT	DoubleList_InsertTail( DOUBLELIST *pList, void *pData )
{
    DOUBLENODE  *pNode;

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

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

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

    pList->pTail = pNode;

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


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

	@param	DOUBLELIST *pList - 要操作的双向链表指针	
	@return	void * - 失败返回NULL, 成功返回要弹出的头节点的数据指针	
*/
void *	DoubleList_PopHead( DOUBLELIST *pList )
{
	DOUBLENODE	*pPopNode;   /* 用来指向要弹出数据的节点的指针 */
	void		*pPopData;   /* 用来指向要弹出的数据的指针 */

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

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

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

    /* 将头节点指针指向头节点的下一节点 */
    pList->pHead = pList->pHead->pNext;
    if ( pList->pHead != NULL )
    {
        pList->pHead->pPrev = NULL;
    }
	
    /* 将链表节点数量减1 */
    pList->uCount--;

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

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


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

    @param	DOUBLELIST *pList - 要操作的双向链表指针	
    @return	void * -  失败返回NULL, 成功返回要弹出的尾节点的数据指针	
*/
void *	DoubleList_PopTail( DOUBLELIST *pList )
{
    DOUBLENODE	*pPopNode;   /* 用来指向要弹出数据的节点的指针 */
    void		*pPopData;   /* 用来指向要弹出的数据的指针 */

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

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

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

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

   
    /* 将链表节点数量减1 */
    pList->uCount--;

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

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



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

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

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

    pNode = pList->pHead;
    pPrevNode = pNode;

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

                if ( pList->pTail == pNode )
                {
                    /* 
                     * 如果尾节点和pNode相同，表明删除的是尾节点
                     * 此时需要将尾节点指针指向要删除节点的前一个节点
                     */
                    pList->pTail = pPrevNode;
                }

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

            /* 释放节点数据和节点占用的内存 */
            if ( DestroyFunc != NULL && pNode->pData != NULL )
            {
                (*DestroyFunc)( pNode->pData );
            }
            free( pNode );

            break;
        }
        pPrevNode = pNode;
        pNode = pNode->pNext;
    }

    return CAPI_SUCCESS;
}


/**	双向链表的获取链表节点数量函数

	@param	DOUBLELIST *pList - 要操作的双向链表指针	
	@return	UINT - 链表节点数量，为0表示链表是空的没有节点在链表里面
                   或者参数非法	
*/
UINT DoubleList_GetCount(DOUBLELIST *pList)
{
    if ( pList == NULL )
    {
        return 0;
    }
    return pList->uCount;
}


/**	双向链表的获取头节点函数

	@param	DOUBLELIST *pList - 要操作的双向链表指针	
	@return	void * - 头节点的数据指针	
*/
void *	DoubleleList_GetHead( DOUBLELIST *pList )
{
    if ( pList == NULL )
    {
        return NULL;
    }

    if ( pList->pHead == NULL )
    {
        return NULL;
    }

    return pList->pHead->pData;
}


/**	双向链表的获取尾节点函数

	@param	DOUBLELIST *pList - 要操作的双向链表指针	
	@return	void * - 尾节点的数据指针	
*/
void * 	DoubleList_GetTail( DOUBLELIST *pList )
{
    if ( pList == NULL )
    {
        return NULL;
    }

    if ( pList->pTail != NULL )
    {
        return pList->pTail->pData;
    }
    else
    {
        return NULL;
    }
}

/**	双向链表的查找函数

	@param	DOUBLELIST *pList - 双向链表指针	
	@param	void *pMatchData - 要查找的匹配数据	
	@param	COMPAREFUNC CompareFunc - 数据匹配比较函数	
	@return	void * - 查找到的在双向链表中的匹配数据	
*/
void * DoubleList_Find( DOUBLELIST *pList, void *pMatchData, 
                       COMPAREFUNC CompareFunc )
{
	DOUBLENODE	*pNode;

    pNode = pList->pHead;
	while ( pNode )
	{
		if ( (*CompareFunc)( pNode->pData, pMatchData ) == 0  )
		{
			void * pData;
			pData = pNode->pData;

			return pData;
		}
		pNode = pNode->pNext;
	}
	return NULL;
}

/**	双向链表的枚举初始化函数

	@param	SINGLELIST *pSingleList - 要操作的双向链表指针
	@return	void - 无	
*/
void DoubleList_EnumBegin( DOUBLELIST *pList )
{
    pList->pCur = pList->pHead;
    return;
}


/**	双向链表枚举下一个节点的函数，第一次调用此函数前必须
    先调用DoubleList_EnumBegin()函数

	@param	DOUBLELIST *pList - 要操作的双向链表的指针	
	@return	void * - 枚举到的节点数据指针	
*/
void * DoubleList_EnumNext( DOUBLELIST *pList )
{
    DOUBLENODE  *pCur;
    
    pCur = pList->pCur;
    if ( pCur != NULL )
    {
        pList->pCur = pCur->pNext;
        
        return pCur->pData;
    }
    return NULL;
}


/**	双向链表的枚举节点函数，第1次调用此函数前要先调用DoubleList_EnumBegin()函数

	@param	DOUBLELIST *pList - 双向链表指针	
	@return	DOUBLENODE * - 从双向链表中枚举到的节点指针	
*/