频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
AMPS:双向链表源码解读
2013-01-21 08:20:29      个评论      
收藏   我要投稿
本节在上节单向链表的基础上看看AMPS中对双向链表的实现,与单向链表相同,双向链表在软件中的使用也相对比较广泛,在后面要讲到的Hash表、定时器、内存管理等模块中都会见到以双向链表作为基本数据结构。其实,双向链表在实现上使用了很多单向链表的操作,仅在插入、删除结点时需要多操作几步,所以理解了单向链表,这块就比较好理解了。

 

  同样,AMPS提供了以下API对双向链表进行操作:

 

  \

 

AMPS_LinkList.h

 

 

 

[cpp]  

#ifndef __HEADER_AMPS_LINKLIST_H__   

#define __HEADER_AMPS_LINKLIST_H__   

  

#ifdef __cplusplus   

extern "C"  

{  

#endif   

  

#include "AMPS_API.h"   

#include "AMPS_Defines.h"   

  

typedef struct _AMPSSList       t_AMPSSList;  

typedef struct _AMPSDList       t_AMPSDList;  

  

/*单向链表结构*/  

struct _AMPSSList  

{  

    void*           pvData;  

    t_AMPSSList*    poAMPSSListNext;  

    t_AMPSSList*    poAMPSSListPrev;  

};  

  

/*双向链表结构*/  

struct _AMPSDList  

{  

    unsigned char   uchCount;        /*结点个数*/  

    t_AMPSSList*    poAMPSSListHead;  

};  

  

t_AMPSDList* DList_Init(t_AMPSDList** r_ppoDList);  

int DList_Concat(t_AMPSDList** r_ppoDListSrc, t_AMPSDList* r_poDListDst);  

t_AMPSSList* DList_Append(t_AMPSDList* list, void* r_pvData);  

t_AMPSSList* DList_Prepend(t_AMPSDList* r_poDList, void* r_pvData);  

void DList_PrependGivenNode(t_AMPSDList* r_poDList, void* r_pvData, t_AMPSSList* r_poSListNode);  

void DList_AppendGivenNode(t_AMPSDList* r_poDList, void* r_pvData, t_AMPSSList* r_poSListNode);  

t_AMPSSList* DList_Search(t_AMPSDList* r_poDList, AMPS_LListCompareLinkDataCallback r_pfAMPS_LListCompareCallback, void* r_pvData);  

t_AMPSSList* DList_Find (t_AMPSDList* r_poDList, t_AMPSSList* r_poSListNode);  

int DList_Remove(t_AMPSDList** r_ppoDList, t_AMPSSList* r_poSListNode, AMPS_LListRemoveLinkDataCallback r_pfAMPS_LListRemoveLinkDataCallback);  

int DList_Sort(t_AMPSDList** r_ppoDList, AMPS_LListCompareLinkDataCallback r_pfAMPS_LListCompareCallback);  

void DList_SwapNodesData(t_AMPSSList* r_poNodeOne, t_AMPSSList* r_poNodeTwo);  

int DList_RemoveFirstNode(t_AMPSDList** r_ppoDList, AMPS_LListRemoveLinkDataCallback AMPS_LListRemoveLinkDataCallback);  

void DList_RemoveNthNode(t_AMPSDList** r_ppoDList, int r_nLocation, AMPS_LListRemoveLinkDataCallback AMPS_LListRemoveLinkDataCallback);  

t_AMPSSList* DList_InsertAfter (t_AMPSDList* r_poDList, t_AMPSSList* r_poSListPositionNode, void* r_pvData);  

t_AMPSSList* DList_InsertBefore (t_AMPSDList* r_poDList, t_AMPSSList* r_poSListPositionNode, void* r_pvData);  

void DList_Free(t_AMPSDList** r_ppoDList, AMPS_LListRemoveLinkDataCallback AMPS_LListRemoveLinkDataCallback);  

void DList_FreeEx(t_AMPSDList** r_ppoDList, AMPS_LListProcessCallback r_pfAMPS_LListProcessCallback, void* r_pvData);  

void DList_FreeNodes(t_AMPSDList** r_ppoDList, AMPS_LListRemoveLinkDataCallback AMPS_LListRemoveLinkDataCallback);  

void DList_Traverse(t_AMPSDList* r_poDList, AMPS_LListProcessCallback r_fpDList_ProcessCallback, void* r_pvArg);  

int DList_RemoveWithOutFree(t_AMPSDList* r_poDList, t_AMPSSList* r_poSListNode);  

int SList_RemoveWithOutFree(t_AMPSSList** r_ppoAMPSSListHead, t_AMPSSList* r_poAMPSSListNode);  

  

void* DList_GetNthNode(t_AMPSDList* r_poAMPSDList, int r_nNodeLocation);  

int DList_Copy(t_AMPSDList* r_poAMPSDListSrc, t_AMPSDList* r_poAMPSDListDest, AMPS_LListDuplicate r_pfAMPS_LListDuplicate);  

int DList_RemoveFromData(t_AMPSDList* r_poDList, void* r_pvData, AMPS_LListRemoveLinkDataCallback r_pfAMPS_LListRemoveLinkDataCallback);  

  

#ifdef __cplusplus   

  

}  

#endif   

  

#endif /* __HEADER_AMPS_LINKLIST_H__ */  

 

#ifndef __HEADER_AMPS_LINKLIST_H__

#define __HEADER_AMPS_LINKLIST_H__

 

#ifdef __cplusplus

extern "C"

{

#endif

 

#include "AMPS_API.h"

#include "AMPS_Defines.h"

 

typedef struct _AMPSSList t_AMPSSList;

typedef struct _AMPSDList t_AMPSDList;

 

/*单向链表结构*/

struct _AMPSSList

{

void* pvData;

t_AMPSSList* poAMPSSListNext;

t_AMPSSList* poAMPSSListPrev;

};

 

/*双向链表结构*/

struct _AMPSDList

{

unsigned char uchCount;        /*结点个数*/

t_AMPSSList* poAMPSSListHead;

};

 

t_AMPSDList* DList_Init(t_AMPSDList** r_ppoDList);

int DList_Concat(t_AMPSDList** r_ppoDListSrc, t_AMPSDList* r_poDListDst);

t_AMPSSList* DList_Append(t_AMPSDList* list, void* r_pvData);

t_AMPSSList* DList_Prepend(t_AMPSDList* r_poDList, void* r_pvData);

void DList_PrependGivenNode(t_AMPSDList* r_poDList, void* r_pvData, t_AMPSSList* r_poSListNode);

void DList_AppendGivenNode(t_AMPSDList* r_poDList, void* r_pvData, t_AMPSSList* r_poSListNode);

t_AMPSSList* DList_Search(t_AMPSDList* r_poDList, AMPS_LListCompareLinkDataCallback r_pfAMPS_LListCompareCallback, void* r_pvData);

t_AMPSSList* DList_Find (t_AMPSDList* r_poDList, t_AMPSSList* r_poSListNode);

int DList_Remove(t_AMPSDList** r_ppoDList, t_AMPSSList* r_poSListNode, AMPS_LListRemoveLinkDataCallback r_pfAMPS_LListRemoveLinkDataCallback);

int DList_Sort(t_AMPSDList** r_ppoDList, AMPS_LListCompareLinkDataCallback r_pfAMPS_LListCompareCallback);

void DList_SwapNodesData(t_AMPSSList* r_poNodeOne, t_AMPSSList* r_poNodeTwo);

int DList_RemoveFirstNode(t_AMPSDList** r_ppoDList, AMPS_LListRemoveLinkDataCallback AMPS_LListRemoveLinkDataCallback);

void DList_RemoveNthNode(t_AMPSDList** r_ppoDList, int r_nLocation, AMPS_LListRemoveLinkDataCallback AMPS_LListRemoveLinkDataCallback);

t_AMPSSList* DList_InsertAfter (t_AMPSDList* r_poDList, t_AMPSSList* r_poSListPositionNode, void* r_pvData);

t_AMPSSList* DList_InsertBefore (t_AMPSDList* r_poDList, t_AMPSSList* r_poSListPositionNode, void* r_pvData);

void DList_Free(t_AMPSDList** r_ppoDList, AMPS_LListRemoveLinkDataCallback AMPS_LListRemoveLinkDataCallback);

void DList_FreeEx(t_AMPSDList** r_ppoDList, AMPS_LListProcessCallback r_pfAMPS_LListProcessCallback, void* r_pvData);

void DList_FreeNodes(t_AMPSDList** r_ppoDList, AMPS_LListRemoveLinkDataCallback AMPS_LListRemoveLinkDataCallback);

void DList_Traverse(t_AMPSDList* r_poDList, AMPS_LListProcessCallback r_fpDList_ProcessCallback, void* r_pvArg);

int DList_RemoveWithOutFree(t_AMPSDList* r_poDList, t_AMPSSList* r_poSListNode);

int SList_RemoveWithOutFree(t_AMPSSList** r_ppoAMPSSListHead, t_AMPSSList* r_poAMPSSListNode);

 

void* DList_GetNthNode(t_AMPSDList* r_poAMPSDList, int r_nNodeLocation);

int DList_Copy(t_AMPSDList* r_poAMPSDListSrc, t_AMPSDList* r_poAMPSDListDest, AMPS_LListDuplicate r_pfAMPS_LListDuplicate);

int DList_RemoveFromData(t_AMPSDList* r_poDList, void* r_pvData, AMPS_LListRemoveLinkDataCallback r_pfAMPS_LListRemoveLinkDataCallback);

 

#ifdef __cplusplus

 

}

#endif

 

#endif /* __HEADER_AMPS_LINKLIST_H__ */

 

 

AMPS_LinkList.c

 

 

/***************************************************************** 

文件名称: AMPS_LinkList.c 

功能描述: 链表操作API函数(单向链表和双向链表) 

 

*****************************************************************/  

#include "AMPS_LinkList.h"   

#include "AMPS_MemMgt.h"   

  

/***************************************************************** 

函数名称: DList_Init 

功能描述: 双向链表初始化 

入参:: 

      t_AMPSDList** new_list 原链表 

       

出参: 

      NA 

返回值: 

      t_AMPSDList* 原链表 

 

*****************************************************************/  

t_AMPSDList* DList_Init(t_AMPSDList** new_list)  

{  

    *new_list = AMPS_InternalMalloc(sizeof(t_AMPSDList));  

  

    if (*new_list != NULL)  

    {  

        (*new_list)->uchCount = 0;  

        (*new_list)->poAMPSSListHead = NULL;  

    }  

    return *new_list;  

}  

  

/***************************************************************** 

函数名称: DList_Concat 

功能描述: 连接两个双向链表 

入参:: 

      t_AMPSDList** src 链表1 

      t_AMPSDList* dst  链表2 

       

出参: 

      t_AMPSDList** src 连接后的链表 

返回值: 

      int 

 

*****************************************************************/  

int DList_Concat(t_AMPSDList** src, t_AMPSDList* dst)  

{  

    /*使用单向链表连接函数*/  

    if (AMPS_SUCCESS != SList_Concat(&(*src)->poAMPSSListHead, dst->poAMPSSListHead))  

    {  

        return AMPS_ERROR_FAILURE;  

    }  

  

    /*目的链表结点个数*/  

    (*src)->uchCount += dst->uchCount;  

  

    AMPS_InternalFree(dst);  

  

    return AMPS_SUCCESS;  

}  

  

/***************************************************************** 

函数名称: DList_Append 

功能描述: 向双向链表中追加结点 

入参:: 

      t_AMPSDList** src 原链表 

      void* pvData      待追加结点 

       

出参: 

      NA 

返回值: 

      t_AMPSDList** src 追加后的链表 

 

*****************************************************************/  

t_AMPSSList* DList_Append(t_AMPSDList* list, void* pvData)  

{  

    t_AMPSSList *new_list = NULL;  // pointer to newly created node    

    t_AMPSSList *last = NULL;      // pointer to last node of link list    

    t_AMPSSList *list_ptr = list->poAMPSSListHead;  

  

    new_list = AMPS_InternalMalloc(sizeof(t_AMPSSList));  

    if (NULL == new_list)  

    {  

        return NULL;  

    }  

    new_list->pvData = pvData;  

    new_list->poAMPSSListNext = NULL;  

    new_list->poAMPSSListPrev = NULL;  

    if (list_ptr)  

    {  

        /*找到结尾*/  

        last = SList_Last(list_ptr);  

        if (NULL == last)  

        {  

            AMPS_InternalFree(new_list);  

            return NULL;  

        }  

          

        /*增加结点*/  

        last->poAMPSSListNext = new_list;  

        new_list->poAMPSSListPrev = last;  

    } else  

    {  

        list->poAMPSSListHead = new_list;  

    }  

    /*结点个数加1*/  

    list->uchCount += 1;  

    return new_list;  

}  

  

/***************************************************************** 

函数名称: DList_Prepend 

功能描述: 向双向链表中前向插入结点 

入参:: 

      t_AMPSDList** src 原链表 

      void* pvData      待追加结点 

       

出参: 

      NA  

返回值: 

      t_AMPSDList** src 追加后的链表 

 

*****************************************************************/  

t_AMPSSList* DList_Prepend(t_AMPSDList* list, void* pvData)  

{  

    t_AMPSSList *new_list = NULL;  

    t_AMPSSList *list_ptr = list->poAMPSSListHead;  

  

    new_list = AMPS_InternalMalloc(sizeof(t_AMPSSList));  

    if (NULL == new_list)  

    {  

        return NULL;  

    }  

    new_list->pvData = pvData;  

    new_list->poAMPSSListNext = list_ptr;  

    new_list->poAMPSSListPrev = NULL;  

  

    if (list_ptr)  

    {  

        list_ptr->poAMPSSListPrev = new_list;    

    }  

  

    list->poAMPSSListHead = new_list;  

    list->uchCount += 1;  

    return new_list;  

}  

  

/***************************************************************** 

函数名称: DList_Search 

功能描述: 在双向链表中查找指定内容的结点 

入参:: 

      t_AMPSDList* list 原链表 

      AMPS_LListCompareLinkDataCallback func_ptr 结点比较回调函数 

      void* pvData 待查找结点内容 

       

出参: 

      NA 

返回值: 

      t_AMPSDList* 返回找到的结点指针 

 

*****************************************************************/  

t_AMPSSList* DList_Search(t_AMPSDList* list, AMPS_LListCompareLinkDataCallback func_ptr, void* pvData)  

{  

    return(SList_Search (list->poAMPSSListHead, func_ptr ,pvData));  

}   

  

/***************************************************************** 

函数名称: DList_Find 

功能描述: 在双向链表中查找指定内容的结点 

入参:: 

      t_AMPSDList* list 原链表 

      t_AMPSSList *node 待查找结点 

       

出参: 

      NA 

返回值: 

      t_AMPSDList* 返回找到的结点指针 

 

*****************************************************************/  

t_AMPSSList* DList_Find (t_AMPSDList *list, t_AMPSSList *node)  

{  

    return(SList_Find (list->poAMPSSListHead, node));  

}  

  

/***************************************************************** 

函数名称: DList_Remove 

功能描述: 在双向链表中删除指定的结点 

入参:: 

      t_AMPSDList* list 原链表 

      t_AMPSSList *node 待删除结点 

      AMPS_LListRemoveLinkDataCallback func_ptr 删除前结点处理回调函数 

       

出参: 

      t_AMPSDList** 返回找到的结点指针 

返回值: 

      int 

 

*****************************************************************/  

int DList_Remove(t_AMPSDList **list, t_AMPSSList *node, AMPS_LListRemoveLinkDataCallback func_ptr)  

{  

    if ((list == NULL) || (*list == NULL) || (node == NULL))  

    {  

        return AMPS_ERROR_FAILURE;  

    }  

  

    if (func_ptr)  

    {  

        if (func_ptr(&(node->pvData)))  

        {  

            return AMPS_ERROR_FAILURE;  

        }  

    }  

  

    // If first element is found to be the element to be deleted   

    if (NULL == node->poAMPSSListPrev)  

    {  

        if ((*list)->poAMPSSListHead != node)  

        {  

            // //printfslist_remove: list corrupted: poAMPSSListPrev pointer NULL but node is not the first element in list\n");   

            return AMPS_ERROR_FAILURE;  

        }  

        if (NULL != node->poAMPSSListNext)  

        {  

            (*list)->poAMPSSListHead = node->poAMPSSListNext;       

            (*list)->poAMPSSListHead->poAMPSSListPrev = NULL;  

        } else  

        {  

            (*list)->poAMPSSListHead = NULL;  

        }  

        (*list)->uchCount--;  

        AMPS_InternalFree(node);  

        return AMPS_SUCCESS;        

    }  

  

    node->poAMPSSListPrev->poAMPSSListNext = node->poAMPSSListNext;  

    if (node->poAMPSSListNext)  

    {  

        node->poAMPSSListNext->poAMPSSListPrev = node->poAMPSSListPrev;  

    }  

  

    AMPS_InternalFree(node);  

  

    (*list)->uchCount--;  

  

    return AMPS_SUCCESS;  

}  

  

/***************************************************************** 

函数名称: DList_Sort 

功能描述: 双向链表排序 

入参:: 

      t_AMPSDList* list 原链表 

      AMPS_LListCompareLinkDataCallback func_ptr 排序函数回调 

       

出参: 

      t_AMPSDList** 返回找到的结点指针 

返回值: 

      int 

 

*****************************************************************/  

int DList_Sort(t_AMPSDList **list, AMPS_LListCompareLinkDataCallback func_ptr)  

{  

    t_AMPSDList* poListToSort = (t_AMPSDList*)*list;  

    int nCountOuter = 0;  

    t_AMPSSList* poNode = NULL;  

    t_AMPSSList* poNextNode = NULL;  

  

    if ((list == NULL) || (*list == NULL) || (func_ptr == NULL))  

    {  

        return AMPS_ERROR_FAILURE;  

    }  

  

    if (poListToSort->uchCount <= 1)  

    {  

        return AMPS_SUCCESS;  

    }  

  

    /*冒泡排序*/  

    poNode = poListToSort->poAMPSSListHead;  

    poNextNode = poNode->poAMPSSListNext;  

    for (nCountOuter = 0; nCountOuter < (poListToSort->uchCount - 1); nCountOuter++)  

    {  

        while(poNextNode)  

        {  

            if (!func_ptr(poNode->pvData, poNextNode->pvData))  

            {  

                //swap elements   

                DList_SwapNodesData(poNode, poNextNode);  

            }  

            poNextNode = poNextNode->poAMPSSListNext;  

        }  

        poNode = poNode->poAMPSSListNext;  

        poNextNode = poNode->poAMPSSListNext;  

    }  

    return AMPS_SUCCESS;  

}  

  

/***************************************************************** 

函数名称: DList_Sort 

功能描述: 双向链表交换结点 

入参:: 

      t_AMPSSList* r_poNodeOne 结点1 

      At_AMPSSList* r_poNodeTwo 结点2 

       

出参: 

      t_AMPSSList* r_poNodeOne 结点2 

      t_AMPSSList* r_poNodeTwo 结点1 

       

返回值: 

      int 

 

*****************************************************************/  

void DList_SwapNodesData(t_AMPSSList* r_poNodeOne, t_AMPSSList* r_poNodeTwo)  

{  

    void* poData = NULL;  

    poData = r_poNodeOne->pvData;  

    r_poNodeOne->pvData = r_poNodeTwo->pvData;  

    r_poNodeTwo->pvData = poData;  

}  

  

/***************************************************************** 

函数名称: DList_RemoveFirstNode 

功能描述: 删除双向链表的头结点 

入参:: 

      t_AMPSDList* list 原链表 

      AMPS_LListRemoveLinkDataCallback func_ptr 结点操作函数回调 

       

出参: 

      t_AMPSDList** 操作后的链表 

返回值: 

      int 

 

*****************************************************************/  

int DList_RemoveFirstNode(t_AMPSDList **list, AMPS_LListRemoveLinkDataCallback func_ptr)  

{  

    t_AMPSSList* node = NULL;  

    if ((list == NULL) || (*list == NULL))  

    {  

        return AMPS_ERROR_FAILURE;  

    }  

  

    node = (*list)->poAMPSSListHead;  

    if (NULL == node->poAMPSSListPrev)  

    {  

        if ((*list)->poAMPSSListHead != node)  

        {  

            // //printfslist_remove: list corrupted: poAMPSSListPrev pointer NULL but node is not the first element in list\n");   

            return AMPS_ERROR_FAILURE;  

        }  

        if (func_ptr)  

        {  

            if (AMPS_ERROR_FAILURE == func_ptr(&(node->pvData)))  

            {  

                return AMPS_ERROR_FAILURE;  

            }  

        }  

  

        /*删除头结点*/  

        if (NULL != node->poAMPSSListNext)  

        {  

            (*list)->poAMPSSListHead = node->poAMPSSListNext;       

            (*list)->poAMPSSListHead->poAMPSSListPrev = NULL;  

        } else  

        {  

            (*list)->poAMPSSListHead = NULL;  

        }  

        (*list)->uchCount--;  

        AMPS_InternalFree(node);  

        return AMPS_SUCCESS;        

    }  

    return AMPS_SUCCESS;  

}   

  

/***************************************************************** 

函数名称: DList_RemoveFirstNode 

功能描述: 删除双向链表中指定位置的结点 

入参:: 

      t_AMPSDList* list 原链表 

      int r_nNodeLocation 指定的结点位置 

      AMPS_LListRemoveLinkDataCallback func_ptr 结点操作函数回调 

       

出参: 

      t_AMPSDList** 操作后的链表 

返回值: 

      int 

 

*****************************************************************/  

void DList_RemoveNthNode(t_AMPSDList** r_ppoDList, int r_nNodeLocation, AMPS_LListRemoveLinkDataCallback AMPS_LListRemoveLinkDataCallback)  

{  

    t_AMPSSList* poSList = (*r_ppoDList)->poAMPSSListHead;  

    t_AMPSSList* poSListTemp1 = NULL;  

    t_AMPSSList* poSListTemp2 = NULL;  

  

    if(!poSList)  

    {  

        return;  

    }  

      

    if(r_nNodeLocation < (*r_ppoDList)->uchCount)  

    {  

        int nLocation = 0;  

          

        /*遍历链表*/  

        for(poSListTemp1 = poSList; poSListTemp1; )  

        {  

            if(nLocation == r_nNodeLocation)  

            {  

                //AMPS_LListRemoveLinkDataCallback(poSListTemp1->pvData, r_pvArg);   

                break;  

            }  

            poSListTemp2 = poSListTemp1->poAMPSSListNext;  

            poSListTemp1 = poSListTemp2;  

            nLocation++;  

        }  

    }  

    return;  

}  

  

/***************************************************************** 

函数名称: DList_RemoveFirstNode 

功能描述: 在双向链表指定结点后插入一个新结点 

入参:: 

      t_AMPSDList* list 原链表 

      t_AMPSSList *positionNode 指定的结点 

      t_AMPSSList *positionNode 待插入的新结点数据 

       

出参: 

      NA 

返回值: 

      t_AMPSDList* 操作后的链表 

 

*****************************************************************/  

t_AMPSSList* DList_InsertAfter (t_AMPSDList *list, t_AMPSSList *positionNode, t_AMPSSList *positionNode)  

{  

    t_AMPSSList *pNewNode = NULL;  

    t_AMPSSList *pPosNode = positionNode;  

  

    if (NULL == positionNode)  

    {  

        //printfdlist_insertafter: input parameters are invalid \n");   

        return NULL;  

    }  

  

    /*构造新结点*/  

    pNewNode = AMPS_InternalMalloc(sizeof(t_AMPSSList));  

    pNewNode->pvData = pvData;  

  

    /*把新结点连接到指定结点之后*/  

    pNewNode->poAMPSSListNext = pPosNode->poAMPSSListNext;  

    pNewNode->poAMPSSListPrev = pPosNode;  

  

    /*断开指定结点与之前结点(向后)的连接,并指向新结点*/  

    if (NULL != pPosNode->poAMPSSListNext)  

        pPosNode->poAMPSSListNext->poAMPSSListPrev = pNewNode;  

    pPosNode->poAMPSSListNext = pNewNode;  

    list->uchCount++;  

  

    return pNewNode;  

  

}  

  

/***************************************************************** 

函数名称: DList_RemoveFirstNode 

功能描述: 在双向链表指定结点前插入一个新结点 

入参:: 

      t_AMPSDList* list 原链表 

      t_AMPSSList *positionNode 指定的结点 

      t_AMPSSList *positionNode 待插入的新结点数据 

       

出参: 

      NA 

返回值: 

      t_AMPSDList* 操作后的链表 

 

*****************************************************************/  

t_AMPSSList* DList_InsertBefore (t_AMPSDList *list, t_AMPSSList *positionNode, void *pvData)  

{  

    t_AMPSSList *pNewNode = NULL;  

    t_AMPSSList *pPosNode = positionNode;  

  

    if (NULL == positionNode)  

    {  

        //printf("DList_InsertAfter: input parameters are invalid \n");   

        return NULL;  

    }  

  

    pNewNode = AMPS_InternalMalloc(sizeof(t_AMPSSList));  

    pNewNode->pvData = pvData;  

  

    pNewNode->poAMPSSListPrev = pPosNode->poAMPSSListPrev;  

    pNewNode->poAMPSSListNext = pPosNode;  

  

    if (NULL != pPosNode->poAMPSSListPrev)  

        pPosNode->poAMPSSListPrev->poAMPSSListNext = pNewNode;  

    pPosNode->poAMPSSListPrev = pNewNode;  

  

    list->uchCount++;  

  

    return pNewNode;  

  

}  

  

/***************************************************************** 

函数名称: DList_Free 

功能描述: 释放双向链表 

入参:: 

      t_AMPSDList** list 原链表 

      AMPS_LListRemoveLinkDataCallback func_ptr 结点操作回调 

 

       

出参: 

      t_AMPSDList** 操作后的链表 

返回值: 

      NA 

 

*****************************************************************/  

void DList_Free(t_AMPSDList **list, AMPS_LListRemoveLinkDataCallback func_ptr)  

{  

    t_AMPSDList* dlist = *list;  

    t_AMPSSList *list_ptr = NULL;  

    if (NULL != dlist)  

    {  

        list_ptr = dlist->poAMPSSListHead;  

    }  

      

    /*使用单向链表释放函数*/  

    SList_Free(&list_ptr, func_ptr);  

    AMPS_InternalFree(dlist);  

    dlist = NULL;     

}  

  

/***************************************************************** 

函数名称: DList_Free 

功能描述: 释放双向链表(释放前可对结点进行操作) 

入参:: 

      t_AMPSDList** list 原链表 

      AMPS_LListRemoveLinkDataCallback func_ptr 

      void* r_pvData 回调函数参数 

 

       

出参: 

      t_AMPSDList** 操作后的链表 

返回值: 

      NA 

 

*****************************************************************/  

void DList_FreeEx(t_AMPSDList** r_ppoDList, AMPS_LListProcessCallback r_pfAMPS_LListProcessCallback, void* r_pvData)  

{  

    t_AMPSDList* dlist = *r_ppoDList;  

    t_AMPSSList *list_ptr = NULL;  

    if (NULL != dlist)  

    {  

        list_ptr = dlist->poAMPSSListHead;  

    }  

    SList_FreeEx(&list_ptr, r_pfAMPS_LListProcessCallback, r_pvData);  

    AMPS_InternalFree(dlist);  

    dlist = NULL;     

}  

  

/***************************************************************** 

函数名称: DList_FreeNodes 

功能描述: 释放双向链表结点 

入参:: 

      t_AMPSDList** list 原链表 

      AMPS_LListRemoveLinkDataCallback func_ptr 

 

       

出参: 

      t_AMPSDList** 操作后的链表 

返回值: 

      NA 

 

*****************************************************************/  

void DList_FreeNodes(t_AMPSDList **list, AMPS_LListRemoveLinkDataCallback func_ptr)  

{  

    SList_Free(&(*list)->poAMPSSListHead, func_ptr);  

    (*list)->poAMPSSListHead = NULL;  

    (*list)->uchCount = 0;  

}  

  

/***************************************************************** 

函数名称: DList_Traverse 

功能描述: 遍历双向链表,在遍历中能过回调函数可对结点进行逐一处理 

入参:: 

      t_AMPSDList** list 原链表 

      AMPS_LListProcessCallback r_fpDList_ProcessCallback 结点处理函数 

      void* r_pvArg 回调函数参数 

 

       

出参: 

      t_AMPSDList* 操作后的链表 

返回值: 

      NA 

 

*****************************************************************/  

void DList_Traverse(t_AMPSDList* r_poDList, AMPS_LListProcessCallback r_fpDList_ProcessCallback, void* r_pvArg)  

{  

    t_AMPSSList* poSList = r_poDList->poAMPSSListHead;  

    t_AMPSSList* poSListTemp1 = NULL;  

    t_AMPSSList* poSListTemp2 = NULL;  

  

    if(!poSList)  

    {  

        return;  

    }  

  

    for(poSListTemp1 = poSList; poSListTemp1; )  

    {  

        poSListTemp2 = poSListTemp1->poAMPSSListNext;  

        r_fpDList_ProcessCallback(poSListTemp1->pvData, r_pvArg);      

        poSListTemp1 = poSListTemp2;  

    }  

}  

  

/***************************************************************** 

函数名称: DList_RemoveWithOutFree 

功能描述: 释放双向链表指定结点,但不释放各节点内容 

入参:: 

      t_AMPSDList* r_poDList 原链表 

      t_AMPSSList* r_poSListNode 指定的结点 

 

       

出参: 

       

返回值: 

      int 

 

*****************************************************************/  

int DList_RemoveWithOutFree(t_AMPSDList* r_poDList, t_AMPSSList* r_poSListNode)  

{  

    if(AMPS_SUCCESS != SList_RemoveWithOutFree(&r_poDList->poAMPSSListHead, r_poSListNode))  

    {  

        return AMPS_ERROR_FAILURE;  

    }  

    r_poDList->uchCount--;  

  

    return AMPS_SUCCESS;  

}  

  

/***************************************************************** 

函数名称: DList_PrependGivenNode 

功能描述: 前向插入指定结点,并为结点赋值 

入参:: 

      t_AMPSDList* r_poDList 原链表 

      void* pvData 结点内容 

      t_AMPSSList* r_poSListNode 指定的结点,通常内容为空,在外层分配空间 

 

       

出参: 

       

返回值: 

      int 

 

*****************************************************************/  

void DList_PrependGivenNode(t_AMPSDList* r_poAMPSDList, void* pvData, t_AMPSSList* r_poAMPSSListNode)  

{  

    t_AMPSSList* poAMPSSListHead = r_poAMPSDList->poAMPSSListHead;  

  

    r_poAMPSSListNode->pvData = pvData;  

    r_poAMPSSListNode->poAMPSSListNext = poAMPSSListHead;  

    r_poAMPSSListNode->poAMPSSListPrev = NULL;  

  

    if(NULL != poAMPSSListHead)  

    {  

        poAMPSSListHead->poAMPSSListPrev = r_poAMPSSListNode;    

    }  

  

    r_poAMPSDList->poAMPSSListHead = r_poAMPSSListNode;  

    r_poAMPSDList->uchCount += 1;  

}  

  

/***************************************************************** 

函数名称: DList_AppendGivenNode 

功能描述: 后向追加指定结点,并为结点赋值 

入参:: 

      t_AMPSDList* r_poDList 原链表 

      void* pvData 结点内容 

      t_AMPSSList* r_poSListNode 指定的结点,通常内容为空,在外层分配空间 

 

       

出参: 

       

返回值: 

      int 

 

*****************************************************************/  

void DList_AppendGivenNode(t_AMPSDList* r_poAMPSDList, void* pvData, t_AMPSSList* r_poAMPSSListNode)  

{  

    t_AMPSSList *poAMPSSListLastNode = NULL;      // pointer to last node of link list    

    t_AMPSSList* poAMPSSListHead = r_poAMPSDList->poAMPSSListHead;  

  

    r_poAMPSSListNode->pvData = pvData;  

    r_poAMPSSListNode->poAMPSSListNext = NULL;  

    r_poAMPSSListNode->poAMPSSListPrev = NULL;  

    if (poAMPSSListHead)  

    {  

        poAMPSSListLastNode = SList_Last(poAMPSSListHead);  

        if (poAMPSSListLastNode)  

        {  

            poAMPSSListLastNode->poAMPSSListNext = r_poAMPSSListNode;  

            r_poAMPSSListNode->poAMPSSListPrev = poAMPSSListLastNode;  

        }  

    } else  

    {  

        r_poAMPSDList->poAMPSSListHead = r_poAMPSSListNode;  

    }  

    r_poAMPSDList->uchCount += 1;  

}  

  

/***************************************************************** 

函数名称: DList_GetNthNode 

功能描述: 获取指定位置的结点 

入参:: 

      t_AMPSDList* poDList_i 原链表 

      int nNodeLocation_i 指定的位置 

 

       

出参: 

       

返回值: 

      void* 找到的结点指针 

 

*****************************************************************/  

void* DList_GetNthNode( t_AMPSDList* poDList_i, int nNodeLocation_i )  

{  

    t_AMPSSList* poListNode = NULL;  

    t_AMPSSList* poLastListNode = NULL;  

    int nCurrentLocation = 1;  

  

    switch( nNodeLocation_i )  

    {  

    case 0:     // first node   

        poListNode = poDList_i->poAMPSSListHead;  

        break;  

  

    case -1:    // last node   

        poListNode = poDList_i->poAMPSSListHead;  

        poLastListNode = poListNode;  

  

        /*遍历找到最后一个结点,此处可用SList_Last*/  

        while( NULL != poListNode )  

        {  

            poLastListNode = poListNode;  

            poListNode = poListNode->poAMPSSListNext;  

        }  

        poListNode = poLastListNode;  

        break;  

  

    default:    // node at location (1-based)   

  

        poListNode = poDList_i->poAMPSSListHead;  

        if( nNodeLocation_i > poDList_i->uchCount && nNodeLocation_i < 0 )  

        {  

            poListNode = NULL;  

        }  

        else  

        {  

            while( NULL != poListNode )  

            {  

                if( nCurrentLocation == nNodeLocation_i )  

                {  

                    break;  

                }  

                nCurrentLocation++;  

                poListNode = poListNode->poAMPSSListNext;  

            }  

        }  

    }  

  

    return (poListNode);  

}  

  

/***************************************************************** 

函数名称: DList_Copy 

功能描述: 链表复制函数,在复制过程中可以处理结点,并将处理后的结点存放在 

          目标链表中 

入参:: 

      t_AMPSDList* pSrcList_i 原链表 

      t_AMPSDList* pDestList_i 目标链表 

      AMPS_LListDuplicate pfnDup_i 复制结点的回调函数 

 

       

出参: 

      void* 找到的结点指针 

返回值: 

      int 

 

*****************************************************************/  

int DList_Copy(t_AMPSDList* pSrcList_i, t_AMPSDList* pDestList_i, AMPS_LListDuplicate pfnDup_i)  

{  

    int nRetVal = AMPS_SUCCESS;  

    void* pvDupData = NULL;  

  

    t_AMPSSList* poNode = NULL;  

  

    for( poNode = pSrcList_i->poAMPSSListHead; poNode != NULL; poNode = poNode->poAMPSSListNext )  

    {  

        pvDupData = (pfnDup_i)(poNode->pvData);  

        if( NULL == pvDupData )  

        {  

            nRetVal = AMPS_ERROR_FAILURE;  

            break;  

        }  

        AMPS_DListAppend( pDestList_i, pvDupData );  

    }  

    return (nRetVal);  

}  

  

/***************************************************************** 

函数名称: DList_RemoveFromData 

功能描述: 从双向链表中删除指定内容的结点 

入参:: 

      t_AMPSDList* pSrcList_i 原链表 

      void* pvData_i  指定的内容 

      AMPS_LListRemoveLinkDataCallback pfRemovDataCb_i 节点处理回调函数 

 

       

出参: 

       

返回值: 

      int 

 

*****************************************************************/  

int DList_RemoveFromData( t_AMPSDList* poDList_i, void* pvData_i, AMPS_LListRemoveLinkDataCallback pfRemovDataCb_i )  

{  

    int nRetVal = AMPS_SUCCESS;  

    t_AMPSSList* poListNode = NULL;  

  

    for( poListNode = poDList_i->poAMPSSListHead; poListNode != NULL; poListNode = poListNode->poAMPSSListNext )  

    {  

        if( poListNode->pvData == pvData_i )  

        {  

            break;  

        }  

    }  

    if( NULL != poListNode )  

    {  

        nRetVal =  AMPS_DListRemove( &poDList_i, poListNode, pfRemovDataCb_i );  

    }  

    else  

    {  

        nRetVal = AMPS_ERROR_FAILURE;  

    }  

    return (nRetVal);  

}  

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 双向 源码
上一篇:节约空间的筛素数方法
下一篇:CF 264A(向内的双向队列)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站