不一样的双向链表

• 链表初识别
• 遍历双向链表
• 参考链接

链表初识别

最近看openharmony的内核源码时看到一个有意思的双向链表，结构如下

typedef struct LOS_DL_LIST{    struct LOS_DL_LIST *pstPrev; //前驱节点    struct LOS_DL_LIST *pstNext; //后继节点}LOS_DL_LIST;

不知道大家看上面的结构体有没有发现诡异的地方？
没错，这个双向链表咋没有数据呢？？？
其实LOS_DL_LIST不能单独拿来用，他需要放置于内容结构体上，如下图

现在有个任务，给你一个LOS_DL_LIST，如何获得内容结构体的首地址?
具体如何做，我们看看下面的两个宏，并结合实际的例子来进行分析

typedef unsigned longUINTPTR;//获取指定结构体内的成员相对于结构体起始地址的偏移量#define LOS_OFF_SET_OF(type, member) ((UINTPTR)&((type *)0)->member)//根据结构体成员地址、结构体类型、结构体成员名，推出结构体的首地址并强制转换#define LOS_DL_LIST_ENTRY(item, type, member) \    ((type *)((void*)((char*)(item) - LOS_OFF_SET_OF(type, member))))

LOS_OFF_SET_OF的用法可以看看我的这篇博客:c语言取结构体的偏移量

#include #include#includeusing namespace std;typedef unsigned longUINTPTR;//获取指定结构体内的成员相对于结构体起始地址的偏移量#define LOS_OFF_SET_OF(type, member) ((UINTPTR)&((type *)0)->member)//根据结构体成员地址、结构体类型、结构体成员名，推出结构体的首地址并强制转换#define LOS_DL_LIST_ENTRY(item, type, member) \    ((type *)((void*)((char*)(item) - LOS_OFF_SET_OF(type, member))))typedef struct LOS_DL_LIST{    struct LOS_DL_LIST *pstPrev;    struct LOS_DL_LIST *pstNext;}LOS_DL_LIST;//定义一个简单的结构体typedef struct Book{    char name[20];    char author[20];    double price;    LOS_DL_LIST otherBook;} Book;//输出结构体信息void print_book(Book *book){    cout<<"书名:"<<book->name<<" ,作者:"<<book->author<<" ,价格:"<<book->price<<endl;}int main(){    Book book = {"三国演义", "罗贯中",100.5};    Book * book_ = LOS_DL_LIST_ENTRY(&book.otherBook,Book,otherBook);    cout<<(book_ == &book)<<endl;print_book(&book);    print_book(book_);}

从上面的结果可以看出，使用LOS_DL_LIST_ENTRY也是可以获得内容结构体的首地址

遍历双向链表

直接看我写的demo吧

#include #include#includeusing namespace std;typedef unsigned longUINTPTR;//获取指定结构体内的成员相对于结构体起始地址的偏移量#define LOS_OFF_SET_OF(type, member) ((UINTPTR)&((type *)0)->member)//根据结构体成员地址、结构体类型、结构体成员名，推出结构体的首地址并强制转换#define LOS_DL_LIST_ENTRY(item, type, member) \    ((type *)((void*)((char*)(item) - LOS_OFF_SET_OF(type, member))))typedef struct LOS_DL_LIST{    struct LOS_DL_LIST *pstPrev;    struct LOS_DL_LIST *pstNext;}LOS_DL_LIST;//定义一个简单的结构体typedef struct Book{    char name[20];    char author[20];    double price;    LOS_DL_LIST otherBook;} Book;//输出结构体信息void print_book(Book *book){    cout<<"书名:"<<book->name<<" ,作者:"<<book->author<<" ,价格:"<<book->price<<endl;}//头插法添加节点void LOS_ListAdd(LOS_DL_LIST *list, LOS_DL_LIST *node){    node->pstNext = list->pstNext;    node->pstPrev = list;    list->pstNext->pstPrev = node;    list->pstNext = node;}//初始化头节点void LOS_ListInit(LOS_DL_LIST *list){    list->pstNext = list;    list->pstPrev = list;}//定义一个节点并初始化为双向链表节点#define LOS_DL_LIST_HEAD(list) LOS_DL_LIST list = { &(list), &(list) }//获取双向链表中指定链表节点的下一个节点所在的结构体地址。//接口的第一个入参表示的是链表中的头节点，第二个入参是指定的链表节点，//第三个入参是要获取的结构体名称，第四个入参是链表在该结构体中的名称。//如果链表节点下一个为链表头结点为空，返回NULL。#define LOS_ListNextType(list, item, type, element) ({    \    type *__t;  \    if ((item)->pstNext == list) {   \ __t = NULL;    \    } else {    \ __t = LOS_DL_LIST_ENTRY((item)->pstNext, type, element); \    }    \    __t; \})//获取双向链表中第一个链表节点所在的结构体地址，接口的第一个入参表示的是链表中的头节点，//第二个入参是要获取的结构体名称，第三个入参是链表在该结构体中的名称。如果链表为空，返回NULL。#define LOS_ListPeekHeadType(list, type, element) ({      \    type *__t;  \    if ((list)->pstNext == list) {   \ __t = NULL;    \    } else {    \ __t = LOS_DL_LIST_ENTRY((list)->pstNext, type, element); \    }    \    __t; \})///遍历双向链表，并存储当前节点的后继节点用于安全校验#define LOS_DL_LIST_FOR_EACH_SAFE(item, next, list)      \    for (item = (list)->pstNext, next = (item)->pstNext; \  (item) != (list);   \  item = next, next = (item)->pstNext) //遍历双向链表#define LOS_DL_LIST_FOR_EACH(item, list) \    for (item = (list)->pstNext;  \  (item) != (list); \  item = (item)->pstNext)//遍历指定双向链表，获取包含该链表节点的结构体地址，并存储包含当前节点的后继节点的结构体地址#define LOS_DL_LIST_FOR_EACH_ENTRY_SAFE(item, next, list, type, member) \    for (item = LOS_DL_LIST_ENTRY((list)->pstNext, type, member),\  next = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member);\  &(item)->member != (list);  \  item = next, next = LOS_DL_LIST_ENTRY((item)->member.pstNext, type, member)) void initBook(LOS_DL_LIST *head){    Book *book1 = (Book*)malloc(sizeof(Book));  //堆上分配    Book *book2 = (Book*)malloc(sizeof(Book));    Book *book3 = (Book*)malloc(sizeof(Book));    Book *book4 = (Book*)malloc(sizeof(Book));    memset(book1,0,sizeof(Book));    memset(book2,0,sizeof(Book));    memset(book3,0,sizeof(Book));    memset(book4,0,sizeof(Book));    strcpy(book1->author,"罗贯中");    strcpy(book1->name,"三国演义");    book1->price = 45.99;    strcpy(book2->author,"曹雪芹");    strcpy(book2->name,"红楼梦");    book2->price = 30.3;    strcpy(book3->author,"吴承恩");    strcpy(book3->name,"西游记");    book3->price = 50.38;    strcpy(book4->author,"施耐庵");    strcpy(book4->name,"水浒传");    book4->price = 66.3;    LOS_ListAdd(head,&(book1->otherBook));    LOS_ListAdd(head,&(book2->otherBook));    LOS_ListAdd(head,&(book3->otherBook));    LOS_ListAdd(head,&(book4->otherBook));    LOS_DL_LIST *item = NULL;    LOS_DL_LIST *next = NULL;    LOS_DL_LIST_FOR_EACH_SAFE(item, next, head){ Book *bookbook = LOS_DL_LIST_ENTRY(item,Book,otherBook); print_book(bookbook);    }}int main(){ LOS_DL_LIST *head= (LOS_DL_LIST*)malloc(sizeof(LOS_DL_LIST));    LOS_ListInit(head);    initBook(head); cout<<"======================\n";    LOS_DL_LIST pBook;    LOS_ListInit(&pBook);    Book book = {"三国演艺", "罗贯中",100.5};    Book book1 = {"红楼梦", "曹雪芹",200.5};    Book book2 = {"西游记",  "吴承恩",150.1};    Book book3 = {"水浒传", "施耐庵",180.4};    Book * book_ = LOS_DL_LIST_ENTRY(&book.otherBook,Book,otherBook);    cout<<(book_ == &book)<<endl; LOS_ListAdd(&pBook,&(book.otherBook));    LOS_ListAdd(&pBook,&(book1.otherBook));    LOS_ListAdd(&pBook,&(book2.otherBook));    LOS_ListAdd(&pBook,&(book3.otherBook));    cout<<"获取双向链表下一个数据节点:\n";    Book *b = LOS_ListNextType(&pBook, &book3.otherBook, Book, otherBook);    if(b != NULL)print_book(b);    cout<<"获取双向链表下一个数据节点结束\n\n";    cout<<"获取双向链表第一个数据节点:\n";    Book *firstBook = LOS_ListPeekHeadType(&pBook,Book,otherBook);    print_book(firstBook);    cout<<"获取双向链表第一个数据节点结束\n\n";    cout<<"while 遍历：\n";    LOS_DL_LIST *book_item = pBook.pstNext;    while(book_item != &pBook){ Book *bookbook = LOS_DL_LIST_ENTRY(book_item,Book,otherBook); print_book(bookbook); book_item = book_item->pstNext;    }    cout<<"while 遍历结束：\n\n"; cout<<"宏定义遍历\n";    LOS_DL_LIST* item = NULL;    LOS_DL_LIST*next = NULL;    LOS_DL_LIST_FOR_EACH_SAFE(item, next, &pBook){ Book *bookbook = LOS_DL_LIST_ENTRY(item,Book,otherBook); print_book(bookbook);    }    cout<<"宏定义遍历结束\n\n";    cout<<"for each 遍历\n";    LOS_DL_LIST_FOR_EACH(item,&pBook){ Book *bookbook = LOS_DL_LIST_ENTRY(item,Book,otherBook); print_book(bookbook);    }    cout<<"for each 遍历结束\n\n\n";    Book* book_item_item = NULL;    Book* book_next = NULL;    LOS_DL_LIST_FOR_EACH_ENTRY_SAFE(book_item_item, book_next, &pBook, Book, otherBook){ print_book(book_item_item);    }}

参考链接

http://weharmonyos.com/blog/01.html