东莞网站建设优化排名永久免费自动建站
不一样的双向链表
- 链表初识别
- 遍历双向链表
- 参考链接
链表初识别
最近看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 long UINTPTR;
//获取指定结构体内的成员相对于结构体起始地址的偏移量
#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 <iostream>
#include<string>
#include<string.h>
using namespace std;
typedef unsigned long UINTPTR;//获取指定结构体内的成员相对于结构体起始地址的偏移量
#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 <iostream>
#include<string>
#include<string.h>
using namespace std;
typedef unsigned long UINTPTR;//获取指定结构体内的成员相对于结构体起始地址的偏移量
#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