本節在上節單向鏈表的基礎上看看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); }