// dl_list.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#define OS_OK (1)
#define OS_FAIL (0)
#define OS_ERROR (~1)
typedef unsigned long UINT32;
#define OS_PRINT printf
#define OS_OFF_SET_OF(type, member) ((long)&(((type *)0)->member))
#define OS_DL_LIST_ENTRY(item, type, member) \
((type *)((char *)item - OS_OFF_SET_OF(type, member))) \
#pragma pack(1)
typedef struct OS_DL_LIST {//双向链表，内核最重要结构体
#ifdef _DEBUG
struct OS_DL_LIST *self;
#endif
struct OS_DL_LIST *pstPrev; /**< Current node's pointer to the previous node *///前驱节点(左手)
struct OS_DL_LIST *pstNext; /**< Current node's pointer to the next node *///后继节点(右手)
} OS_DL_LIST;
#pragma pack()
#ifdef _DEBUG
#define OS_DL_LIST_STATIC(name) OS_DL_LIST name = {&name,NULL,NULL}
#else
#define OS_DL_LIST_STATIC(name) OS_DL_LIST name = {NULL,NULL}
#endif
//初始化链表：对链表进行初始化。
void OS_ListInit(OS_DL_LIST *list)
{
#ifdef _DEBUG
list->self = list;
#endif
list->pstNext = list;
list->pstPrev = list;
}
//增加节点：将新节点添加到链表中。
void OS_ListAdd(OS_DL_LIST *list, OS_DL_LIST *node)
{
#ifdef _DEBUG
node->self = node;
#endif
node->pstNext = list->pstNext;
node->pstPrev = list;
list->pstNext->pstPrev = node;
list->pstNext = node;
}
//删除节点：将指定的节点从链表中删除。
void OS_ListDelete(OS_DL_LIST *node)
{
node->pstNext->pstPrev = node->pstPrev;
node->pstPrev->pstNext = node->pstNext;
node->pstNext = NULL;
node->pstPrev = NULL;
}
//判断双向链表是否为空：判断链表是否为空
int OS_ListEmpty(OS_DL_LIST *list)
{
if ((list->pstPrev==NULL)||(list->pstNext==NULL))
return OS_ERROR;
else if ((list->pstPrev==list)&&(list->pstNext==list))
return OS_OK;
else
return OS_FAIL;
}
//删除节点并初始化链表：将指定的节点从链表中删除，使用该节点初始化链表。
void OS_ListDelInit(OS_DL_LIST *node)
{
node->pstNext->pstPrev = node->pstPrev;
node->pstPrev->pstNext = node->pstNext;
node->pstNext = node;
node->pstPrev = node;
}
//链表中插入节点：从头部插入节点。
void OS_ListHeadInsert(OS_DL_LIST *list, OS_DL_LIST *node)
{
OS_ListAdd(list,node);
}
//在链表尾端出插入节点：将节点插入到双向链表尾端。
void OS_ListTailInsert(OS_DL_LIST *list, OS_DL_LIST *node)
{
OS_ListAdd(list->pstPrev, node);
}
//链表中插入链表：两个循环链表合成一个大循环链表。
void OS_ListAddList(OS_DL_LIST *oldList, OS_DL_LIST *newList)
{
newList->pstPrev->pstNext = oldList->pstNext;
oldList->pstNext->pstPrev = newList->pstPrev;
newList->pstPrev = oldList;
oldList->pstNext = newList;
}
//链表中插入链表：从头部插入链表。
void OS_ListHeadInsertList(OS_DL_LIST *oldList, OS_DL_LIST *newList)
{
OS_ListAddList(oldList, newList);
}
//链表中插入节点：从尾端插入链表。
void OS_ListTailInsertList(OS_DL_LIST *oldList, OS_DL_LIST *newList)
{
OS_ListAddList(oldList->pstPrev, newList);
}
static UINT32 DLlist_sample()
{
OS_DL_LIST_STATIC(DLlist);
OS_DL_LIST_STATIC(DLlistNode01);
OS_DL_LIST_STATIC(DLlistNode02);
OS_DL_LIST_STATIC(DLlistNode03);
OS_PRINT("Initial head\n");
OS_ListInit(&DLlist);
OS_ListAdd(&DLlist,&DLlistNode01);
if (DLlistNode01.pstNext == &DLlist && DLlistNode01.pstPrev == &DLlist)
{
OS_PRINT("Add DLlistNode01 success \n");
}
OS_ListTailInsert(&DLlist,&DLlistNode02);
if (DLlistNode02.pstNext == &DLlist && DLlistNode02.pstPrev == &DLlistNode01)
{
OS_PRINT("Tail insert DLlistNode02 success \n");
}
OS_ListHeadInsert(&DLlistNode02,&DLlistNode03);
if (DLlistNode03.pstNext == &DLlist && DLlistNode03.pstPrev == &DLlistNode02)
{
OS_PRINT("Head insert DLlistNode03 success \n");
}
OS_ListDelInit(&DLlistNode03);
OS_ListDelete(&DLlistNode01);
OS_ListDelete(&DLlistNode02);
if (OS_ListEmpty(&DLlist)==OS_OK)
{
OS_PRINT("Delete success \n");
}
return OS_OK;
}
static UINT32 DLlist_sample_2()
{
OS_DL_LIST_STATIC(DLlist01);
OS_DL_LIST_STATIC(DLlist01Node01);
OS_DL_LIST_STATIC(DLlist01Node02);
OS_DL_LIST_STATIC(DLlist01Node03);
OS_DL_LIST_STATIC(DLlist02);
OS_DL_LIST_STATIC(DLlist02Node01);
OS_DL_LIST_STATIC(DLlist02Node02);
OS_DL_LIST_STATIC(DLlist02Node03);
OS_PRINT("Initial head 2\n");
OS_ListInit(&DLlist01);
OS_ListAdd(&DLlist01,&DLlist01Node01);
OS_ListAdd(&DLlist01,&DLlist01Node02);
OS_ListAdd(&DLlist01,&DLlist01Node03);
OS_ListInit(&DLlist02);
OS_ListAdd(&DLlist02,&DLlist02Node01);
OS_ListAdd(&DLlist02,&DLlist02Node02);
OS_ListAdd(&DLlist02,&DLlist02Node03);
OS_ListAddList(&DLlist01,&DLlist02);
if (DLlist01.pstNext == &DLlist02 && DLlist02.pstPrev == &DLlist01)
{
OS_PRINT("DLlist01 insert DLlist02 success \n");
}
/*OS_ListTailInsertList(&DLlist01,&DLlist02);
if (DLlist01.pstPrev == &DLlist02Node03 && DLlist02.pstPrev == &DLlist01Node03)
{
OS_PRINT("DLlist01 insert DLlist02 success \n");
}*/
OS_DL_LIST *curr = &DLlist01;
do
{
OS_PRINT("curr = 0x%x\n", curr);
curr = curr->pstNext;
} while (curr != &DLlist01);
OS_PRINT("\\\\\\\\\\\\\\\\\\\\\\\n");
do
{
OS_PRINT("curr = 0x%x\n", curr);
curr = curr->pstPrev;
} while (curr != &DLlist01);
return OS_OK;
}
typedef struct Student_Struct
{
OS_DL_LIST dlist;
char name[16];
} stStudent;
static UINT32 DLlist_sample_3()
{
stStudent st;
stStudent *p = NULL;
OS_DL_LIST_STATIC(DLlist);
OS_PRINT("Initial head 3\n");
OS_ListInit(&DLlist);
strcpy(st.name, "DLlist");
OS_ListAdd(&DLlist,&st.dlist);
p = OS_DL_LIST_ENTRY(DLlist.pstNext, stStudent, dlist);
OS_PRINT("name = %s\n", p->name);
return OS_OK;
}
int _tmain(int argc, _TCHAR* argv[])
{
DLlist_sample();
DLlist_sample_2();
DLlist_sample_3();
return 0;
}
显示结果：
Initial head Add DLlistNode01 success Tail insert DLlistNode02 success Head insert DLlistNode03 success Delete success Initial head 2 DLlist01 insert DLlist02 success curr = 0x19fe34 curr = 0x19fde4 curr = 0x19fda8 curr = 0x19fdbc curr = 0x19fdd0 curr = 0x19fdf8 curr = 0x19fe0c curr = 0x19fe20 \\\\\\\\\\\ curr = 0x19fe34 curr = 0x19fe20 curr = 0x19fe0c curr = 0x19fdf8 curr = 0x19fdd0 curr = 0x19fdbc curr = 0x19fda8 curr = 0x19fde4 Initial head 3 name = DLlist