#ifndef __STDLIST_H__
#define __STDLIST_H__
typedef struct tagSTDNODE STDNODE, *LPSTDNODE;
typedef struct tagSTDLIST STDLIST, *LPSTDLIST;
// 链表数据结构
struct tagSTDNODE {
LPSTDNODE lpPrev;
LPSTDNODE lpNext;
};
// 链表节点结构
struct tagSTDLIST {
LPSTDNODE lpHead;
LPSTDNODE lpTail;
};
// 用于链表扩展的宏
#define NODE_INITIALIZER ((STDNODE){ .lpPrev = NULL, .lpNext = NULL, })
#define LIST_INITIALIZER ((STDLIST){ .lpHead = NULL, .lpTail = NULL, })
#define DECLARELISTNODE()STDNODE __snStdNode
#define INIT_LISTNODE() __snStdNode = NODE_INITIALIZER
// 初始化链表
STATIC INLINE
LPSTDLIST TWINAPI StdListInit(
LPSTDLIST lpList
) {
lpList->lpHead = NULL;
lpList->lpTail = NULL;
return lpList;
}
// 获取链表头部节点
STATIC INLINE
LPSTDNODE TWINAPI StdListGetHeadNode(
LPSTDLIST lpList
) {
return lpList->lpHead;
}
// 获取链表尾部节点
STATIC INLINE
LPSTDNODE TWINAPI StdListGetTailNode(
LPSTDLIST lpList
) {
return lpList->lpTail;
}
// 获取给定节点的下一个节点
STATIC INLINE
LPSTDNODE TWINAPI StdListGetNextNode(
LPSTDNODE lpNode
) {
return lpNode->lpNext;
}
// 获取给定节点的上一个节点
STATIC INLINE
LPSTDNODE TWINAPI StdListGetPrevNode(
LPSTDNODE lpNode
) {
return lpNode->lpPrev;
}
// 在链表头部插入一个节点
STATIC INLINE
VOID TWINAPI StdListPushFront(
LPSTDLIST lpList,
LPSTDNODE lpNode
) {
lpNode->lpPrev = NULL;
lpNode->lpNext = lpList->lpHead;
if(lpList->lpHead)
lpList->lpHead->lpPrev = lpNode;
else
lpList->lpTail = lpNode;
lpList->lpHead = lpNode;
}
// 在链表尾部插入一个节点
STATIC INLINE
VOID TWINAPI StdListPushBack(
LPSTDLIST lpList,
LPSTDNODE lpNode
) {
lpNode->lpNext = NULL;
lpNode->lpPrev = lpList->lpTail;
if(lpList->lpTail)
lpList->lpTail->lpNext = lpNode;
else
lpList->lpHead = lpNode;
lpList->lpTail = lpNode;
}
// 在指定节点后插入一个节点
STATIC INLINE
VOID TWINAPI StdListInsert(
LPSTDLIST lpList,
LPSTDNODE lpAfter,
LPSTDNODE lpNode
) {
if(lpAfter) {
if(lpAfter->lpNext)
lpAfter->lpNext->lpPrev = lpNode;
else
lpList->lpTail = lpNode;
lpNode->lpPrev = lpAfter;
lpNode->lpNext = lpAfter->lpNext;
lpAfter->lpNext = lpNode;
} else {
StdListPushFront(lpList, lpNode);
}
}
// 从链表头部弹出一个节点
STATIC INLINE
LPSTDNODE TWINAPI StdListPopFront(
LPSTDLIST lpList
) {
if(lpList->lpHead) {
LPSTDNODE lpNode = lpList->lpHead;
if(lpList->lpHead->lpNext)
lpList->lpHead->lpNext->lpPrev = NULL;
else
lpList->lpTail = NULL;
lpList->lpHead = lpList->lpHead->lpNext;
lpNode->lpPrev = lpNode->lpNext = NULL;
return lpNode;
} else {
return NULL;
}
}
// 从链表尾部弹出一个节点
STATIC INLINE
LPSTDNODE TWINAPI StdListPopBack(
LPSTDLIST lpList
) {
if(lpList->lpTail) {
LPSTDNODE lpNode = lpList->lpTail;
if(lpList->lpTail->lpPrev)
lpList->lpTail->lpPrev->lpNext = NULL;
else
lpList->lpHead = NULL;
lpList->lpTail = lpList->lpTail->lpPrev;
lpNode->lpPrev = lpNode->lpNext = NULL;
return lpNode;
} else {
return NULL;
}
}
// 从链表中删除给定节点
STATIC INLINE
LPSTDNODE TWINAPI StdListRemove(
LPSTDLIST lpList,
LPSTDNODE lpNode
) {
if(lpNode->lpPrev)
lpNode->lpPrev->lpNext = lpNode->lpNext;
else
lpList->lpHead = lpNode->lpNext;
if(lpNode->lpNext)
lpNode->lpNext->lpPrev = lpNode->lpPrev;
else
lpList->lpTail = lpNode->lpPrev;
return lpNode;
}
// 检查链表是否为空
STATIC INLINE
BOOL TWINAPI StdListIsEmpty(
LPSTDLIST lpList
) {
if(lpList->lpHead || lpList->lpTail)
return FALSE;
else
return TRUE;
}
// 获取链表中的节点数
STATIC INLINE
LONG TWINAPI StdListGetSize(
LPSTDLIST lpList
) {
LONG lnSize = 0;
LPSTDNODE lpNode = StdListGetHeadNode(lpList);
while(lpNode) {
++ lnSize;
lpNode = StdListGetNextNode(lpNode);
}
return lnSize;
}
// 合并两个链表
STATIC INLINE
LPSTDLIST TWINAPI StdListCombine(
LPSTDLIST lpList1,
LPSTDLIST lpList2
) {
if(!StdListIsEmpty(lpList2)) {
if(!StdListIsEmpty(lpList1)) {
lpList1->lpTail->lpNext = lpList2->lpHead;
lpList2->lpHead->lpPrev = lpList1->lpTail;
lpList1->lpTail = lpList2->lpTail;
} else {
lpList1->lpHead = lpList2->lpHead;
lpList1->lpTail = lpList2->lpTail;
}
lpList2->lpHead = lpList2->lpTail = NULL;
}
return lpList1;
}
#endif//__STDLIST_H__
算法本身没有什么特别的地方，为什么说这是一个通用双向链表呢？奥妙就在那四个用于扩展的宏。利用这几个宏你可以将这个双向链表扩展到任意结构。
例如，我们要实现一个消息队列，那么我们可以这样定义消息节点：
typedef struct tagMSGNODE {
DECLARELISTNODE();
HWND hWnd;
UINT uMsg;
WPARAM wParam;
LPARAM lParam;
} MSGNODE, *LPMSGNODE;
而消息队列则可以直接用LISTNODE结构来表示：
STDLIST lstMsgQueue;
这样我们就可以用刚刚定义的函数来对这个消息队列进行操作了：
// 向消息队列插入一个消息
LPMSGNODE lpMsgNode = MemAlloc(SIZEOF(MSGNODE));
lpMsgNode->INIT_LISTNODE();
lpMsgNode->hWnd = hWnd;
lpMsgNode->uMsg = WM_PAINT;
lpMsgNode->wParam = NULL;
lpMsgNode->lParam = NULL;
StdListPushBack(&lstMsgQueue, (LPSTDNODE)lpMsgNode);
// 从消息队列取出一个消息
LPMSGNODE lpMsgNode = (LPMSGNODE)StdListPopFront(&lstMsgQueue);
// 删除所有属于hWnd的消息
LPMSGNODE lpTemp = (LPMSGNODE)StdListGetHeadNode(&lstMsgQueue);
while(lpTemp) {
LPMSGNODE lpNext = (LPMSGNODE)StdListGetNextNode(&lstMsgQueue, (LPSTDNODE)lpTemp);
if(lpTemp->hWnd == hWnd) {
StdListRemove(&lstMsgQueue, (LPSTDNODE)lpTemp);
MemFree(lpTemp);
}
lpTemp = lpNext;
}
