说明：
本文章旨在总结备份、方便以后查询，由于是个人总结，如有不对，欢迎指正；另外，内容大部分来自网络、书籍、和各类手册，如若侵权请告知，马上删帖致歉。
QQ 群 号：513683159 【相互学习】
内容来源：
用到在修正
0、container_of 宏的理解
/**
* @brief 通过“结构体成员”的地址与“结构体”的类型推导出“结构体”的首地址
*
* @ptr: “结构体成员”的地址
* @type: “结构体”的类型
* @member: “结构体成员”的名字
*/
#ifndef container_of
#define container_of(ptr, type, member) \
({ \
const typeof(((type *)NULL)->member) *__mptr = (ptr); \
(type *)((char *)__mptr - offsetof(type, member)); \
})
#endif
/*
(1).typeof()返回传入数据的类型，如int a = 3;typeof(a) = int
(2.offsetof(type, member)：在类型为type的结构体中member成员，在该结构体中的偏移量
type:结构体类型，member：结构体中某个成员
分析：
A = ((type *) NULL)表示：type类型的指针地址为0，
B = (A->member)表示：该结构体类型（地址为0）的成员member
C = typeof(B)表示：返回结构体成员member的数据类型
D = const C* __mptr = (ptr)表示：__mptr的地址为ptr的成员地址（数据类型统一的成员地址）
E = offsetof(type, member)表示：类型为type的结构体中member成员，member在该结构体中的偏移量
F = (type *) ((char *)__mptr - E
= ptr - E （忽略类型） = 成员的地址 - 成员的偏移量 = 结构体的的初始地址 = 结构体指针地址
*/
若已知结构体中对应成员名和地址与结构体类型，可得到结构体的指针地址。
查看源文件测试过程可查看：函数简介篇——container_of 宏的理解
常见使用场景：
已知某对象结构体中含有双链表结构体且有其地址和变量名，可得到对象结构体的指针。
1、双链表结构体定义
/* 双链表结构体 */
struct list_head
{
struct list_head *next; /* 后继指针 */
struct list_head *prev; /* 前驱指针 */
};
传统的双链表形态常常会将数据和链表结构体指针放在一个结构体中，这样的结构通用性差，只能建立单一的链表，不能在多个链表中共同存在，减少实际可用性。
作为通用双链表结构体，双链表结构体中并未定义数据变量，使用者根据具体使用再进行定义。
2、双链表初始化
（1）双链表创建并初始化（宏定义）: LIST_HEAD(name)
创建一个双链表并初始化，双链表对象为：name。
/* 双链表初始化(宏定义) */
#define LIST_HEAD_INIT(name) \
{ \
&(name), &(name) \
}
#undef LIST_HEAD /* 取消之前LIST_HEAD的宏定义 */
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)
/*
声明一个为name的链表头，next于prev指针指向自己，即：创建一个空链表。
LIST_HEAD(DList)
等效于
struct list_head DList
{
&DList,
&DList
}
等效于
struct list_head DList;
DList.prev = &DList;
DList.next = &DList;
*/
（2）双链表初始化（内联函数）:INIT_LIST_HEAD()
双链表对象list初始化。
/**
* @brief 链表初始化（内联函数）
* @param list 双链表对象
*/
static inline void
INIT_LIST_HEAD(struct list_head *list)
{
list->next = list->prev = list;
}
3、双链表的判断
（1）判断该节点A下一节点是不是本身:list_empty()
一般参数head传入的是头结点地址，用于判断链表为不为空。
若返回true则表示链表为空。
若返回false则表示链表不为空。
/**
* @brief 判断链表为不为空
* 若链表的下一个节点指向自己则表示该链表为空
* @param head ：链表节点
* @return true ：该链表为空
* @return false：该链表不为空
*/
static inline bool
list_empty(const struct list_head *head)
{
return (head->next == head);
}
（2）判断节点A的上一结点是不是节点B:list_is_first()
一般参数head传入的是头结点地址，list为链表某结点，用于判断该链表结点为不为头结点。
若返回true则表示该结点为头结点。
若返回false则表示该结点不为头结点。
/**
* @brief 判断head节点是不是list节点的前节点
* 判断链表list节点的前一节点是不是head节点
* @param list ：参考的节点
* @param head ：想判断的节点
* @return true ：head节点是list节点的前节点
* @return false：head节点不是list节点的前节点
*/
static inline bool
list_is_first(const struct list_head *list,
const struct list_head *head)
{
return list->prev == head;
}
（3）判断节点A的下一结点是不是节点B:list_is_last()
一般参数head传入的是头结点地址，list为链表某结点，用于判断该链表结点为不为尾结点。
若返回true则表示该结点为尾结点。
若返回false则表示该结点不为尾结点。
/**
* @brief 判断head节点是不是list节点的后节点
* 判断链表list节点的后一节点是不是head节点
* @param list ：参考的节点
* @param head ：想判断的节点
* @return true ：head节点是list节点的后节点
* @return false：head节点不是list节点的后节点
*/
static inline bool
list_is_last(const struct list_head *list,
const struct list_head *head)
{
return list->next == head;
}
4、双链表的结点操作
（1）双链表的结点插入:_list_add()
/**
* @brief 在prev与next链表节点中插入_new链表节点
*
* @param _new： 新的链表节点
* @param prev： 前链表节点
* @param next： 后链表节点
*/
static inline void
_list_add(struct list_head *_new, struct list_head *prev,
struct list_head *next)
{
next->prev = _new;
_new->next = next;
_new->prev = prev;
prev->next = _new;
}
<1>尾插法:list_add_tail()
/**
* @brief 将_new节点插在head节点前面
*
* @param _new：新节点
* @param head：目标节点
*/
static inline void
list_add_tail(struct list_head *_new, struct list_head *head)
{
_list_add(_new, head->prev, head);
}
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
#include "dlist_test.h"
/* 链表节点 */
typedef struct _TestStruct
{
struct list_head list;
int num;
bool pending;
char name;
void *pointer;
}struct_node;
static struct list_head dlist = LIST_HEAD_INIT(dlist); /* 初始化链表： */
int main(int argc, char *argv[])
{
struct_node *tmp; /* 暂存链表节点结构体 */
struct list_head *head = &dlist; /* 链表表头 */
int i = 0;
//插入5个数据
for (i = 0; i < 5; i++)
{
tmp = (struct_node *)malloc(sizeof(struct_node));
tmp->num = i;
list_add_tail(&tmp->list, head);
}
for( i=0 ; i<5 ;i++)
{
tmp = list_first_entry(head, struct_node, list);
printf("%d , %p , %d\n", i,tmp,tmp->num);
head = head->next;
}
}
xsndz@Linux:~/Desktop/list$ ./test
0 , 0x1384010 , 0
1 , 0x1384040 , 1
2 , 0x1384070 , 2
3 , 0x13840a0 , 3
4 , 0x13840d0 , 4
<2>头插法:list_add()
/**
* @brief 将_new节点插在head节点后面
*
* @param _new：新节点
* @param head：目标节点
*/
static inline void
list_add(struct list_head *_new, struct list_head *head)
{
_list_add(_new, head, head->next);
}
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
#include "dlist_test.h"
/* 链表节点 */
typedef struct _TestStruct
{
struct list_head list;
int num;
bool pending;
char name;
void *pointer;
}struct_node;
static struct list_head dlist = LIST_HEAD_INIT(dlist); /* 初始化链表： */
int main(int argc, char *argv[])
{
struct_node *tmp; /* 暂存链表节点结构体 */
struct list_head *head = &dlist; /* 链表表头 */
int i = 0;
//插入5个数据
for (i = 0; i < 5; i++)
{
tmp = (struct_node *)malloc(sizeof(struct_node));
tmp->num = i;
list_add(&tmp->list, head);
}
for( i=0 ; i<5 ;i++)
{
tmp = list_first_entry(head, struct_node, list);
printf("%d , %p , %d\n", i,tmp,tmp->num);
head = head->next;
}
}
xsndz@Linux:~/Desktop/list$ ./test
0 , 0x1a05010 , 0
1 , 0x1a05040 , 1
2 , 0x1a05070 , 2
3 , 0x1a050a0 , 3
4 , 0x1a050d0 , 4
5 , 0x601040 , 0
（2）双链表的结点删除:_list_del()
/**
* @brief 删除entry节点
*
* @param entry： 要删除的节点
*/
static inline void
_list_del(struct list_head *entry)
{
entry->next->prev = entry->prev;
entry->prev->next = entry->next;
}
<1>删除并节点初始化:list_del()
/**
* @brief 删除entry节点，并清空指针
*
* @param entry： 要删除的节点
*/
static inline void
list_del(struct list_head *entry)
{
_list_del(entry);
entry->next = entry->prev = NULL;
}
<2>删除并链表初始化:list_del_init()
/**
* @brief 链表删除节点并初始化该节点
*
* @param entry ： 要删除的节点
*/
static inline void
list_del_init(struct list_head *entry)
{
_list_del(entry);
INIT_LIST_HEAD(entry);
}
（3）双链表的结点替换:replace_node()
/**
* @brief 将old节点替换为new节点
*
* @param old 被替换的链表节点
* @param new 新的链表节点
*/
static inline void
replace_node(struct list_head *old, struct list_head *new)
{
old->next->prev = new;
old->prev->next = new;
new->prev = old->prev;
new->next = old->next;
}
（4）双链表的结点移动
<1>移到目标结点后:list_move()
/**
* @brief 将list节点移到head节点后面
* 从链表中删除list项后将其插入head的后面
* @param list：要移动的节点
* @param head：目标节点
*/
static inline void
list_move(struct list_head *list, struct list_head *head)
{
_list_del(list);
list_add(list, head);
}
<2>移到目标结点前:list_move_tail()
/**
* @brief 将entry节点移到head节点前面
* 从链表中删除entry项后将其插入head的前面
* @param entry：要移动的节点
* @param head： 目标节点
*/
static inline void
list_move_tail(struct list_head *entry, struct list_head *head)
{
_list_del(entry);
list_add_tail(entry, head);
}
（5）链表拼接
<1>拼接函数:_list_splice()
/**
* @brief 将双循环链表从list节点处分割，
* list节点前接上next节点链表，list节点后街上prev节点链表
* 【注意】：合并好的新链表是不包含list节点，且未构成循环
* @param list ：要插入的两条链表的节点位置
* @param prev ：要插入的前一条链表节点
* @param next ：要插入的后一条链表节点
*/
static inline void
_list_splice(const struct list_head *list, struct list_head *prev,
struct list_head *next)
{
struct list_head *first;
struct list_head *last;
/* 若list链表为空则无需合并直接退出 */
if (list_empty(list))
return;
first = list->next; /* list节点的后一节点 */
last = list->prev; /* list节点的前一节点 */
first->prev = prev; /* 后一节点的前驱指针指向prev链表 */
prev->next = first; /* prev链表的后继指针指向后一节点 */
last->next = next; /* 前一节点的后继指针指向next链表 */
next->prev = last; /* next链表的前驱指针指向last链表 */
}
<2>拼接函数:list_splice()
/**
* @brief 将head节点及其【后】的节点分别接在list节点的两端(拼接函数【后】)
*
* 将双循环链表从list节点处分割，
* list节点前接上head->next节点链表，list节点后接上head节点链表
* 【注意】：合并好的新链表是不包含list节点，且未构成循环
* @param list：要插入的两条链表的节点位置
* @param head：想要拆接的head节点
*/
static inline void
list_splice(const struct list_head *list, struct list_head *head)
{
_list_splice(list, head, head->next);
}
<3>拼接函数:list_splice_tail()
/**
* @brief 将head节点及其【前】的节点分别接在list节点的两端(拼接函数【前】)
*
* 将双循环链表从list节点处分割，
* list节点前接上headt节点链表，list节点后接上head->prev节点链表
* 【注意】：合并好的新链表是不包含list节点，且未构成循环
* @param list：要插入的两条链表的节点位置
* @param head：想要拆接的head节点
*/
static inline void
list_splice_tail(struct list_head *list, struct list_head *head)
{
_list_splice(list, head->prev, head);
}
<4>拼接函数并初始化该节点:list_splice_init()
/**
* @brief 拼接函数【后】并初始化该节点
*
* @param list：要插入的两条链表的节点位置
* @param head：想要拆接的head节点
*/
static inline void
list_splice_init(struct list_head *list, struct list_head *head)
{
_list_splice(list, head, head->next);
INIT_LIST_HEAD(list);
}
5.获取链表结点数据：list_entry、list_first_entry、list_last_entry
内核双链表篇:list.h——获取链表结点数据：list_entry、list_first_entry、list_last_entry
list_entry：获取链表某结点指针中的结构体。
list_first_entry：获取链表结点p的下一个结点的数据。p常为头结点，表示获取头结点下一个数据（第一个数据）。
list_last_entry：获取链表结点p的上一个结点的数据。p常为头结点，表示获取头结点上一个数据（最后一个数据）。
/****** 获取含有链表的结构体的指针 ******/
#define list_entry(ptr, type, field) container_of(ptr, type, field) /* 从链表指针ptr中获得包含该链表的结构体指针 */
#define list_first_entry(ptr, type, field) list_entry((ptr)->next, type, field) /* 从链表指针ptr的下一指针中获得包含该链表的结构体指针 */
#define list_last_entry(ptr, type, field) list_entry((ptr)->prev, type, field) /* 从链表指针ptr的上一指针中获得包含该链表的结构体指针 */
/*
ptr: 表示和member同为相同类型的链表，此处ptr表示指向链表中的一个节点（list_head指针）
type： 表示需要寻找的结构体类型（包含ptr的结构体类型）
field：表示type类型的结构体里面的成员（结构体中链表字段的名字）
*/
6.链表的遍历
内核双链表篇:list.h——遍历链表：list_for_each、list_for_each_safe、list_for_each_entry
参数p：链表节点指针，用于当前循环遍历的节点。
参数head、h：链表节点指针，通常为头结点。
参数n：链表节点指针，用于暂存循环遍历的结点。
参数field：数据结构,常为list
（1）遍历循环双链表：list_for_each()
#define list_for_each(p, head) \
for ((p) = (head)->next; (p) != (head); (p) = (p)->next)
p为循环双链表遍历的节点，head为双链表的遍历开始的节点。
从head结点开始遍历，一直回到head结点。
（2）安全遍历循环双链表（有删除操作时使用）：list_for_each_safe()
#define list_for_each_safe(p, n, head) \
for ((p) = (head)->next, n = (p)->next; (p) != (head); \
(p) = n, n = (p)->next)
相较与list_for_each，多一个参数n，
在最开始时遍历前先将，该结点的下下结点先保存到n上。
每次遍历都直接将n值直接给p，并让n接着指向下下结点，避免删除结点所导致的节点找不到的情形。
（3）遍历链表的同时获取对应链表结点的数据结点：list_for_each_entry()
#define list_for_each_entry(p, h, field) \
for ((p) = list_first_entry(h, typeof(*(p)), field); \
&(p)->field != (h); \
(p) = list_entry((p)->field.next, typeof(*(p)), field))
（4）遍历链表的同时获取对应链表结点的数据结点（有删除操作时使用）：list_for_each_entry_safe()
#define list_for_each_entry_safe(p, n, h, field) \
for ((p) = list_first_entry(h, typeof(*(p)), field), \
n = list_entry((p)->field.next, typeof(*(p)), field); \
&(p)->field != (h); \
(p) = n, n = list_entry(n->field.next, typeof(*n), field))
（5）：list_for_each_entry_reverse()
#define list_for_each_entry_reverse(p, h, field) \
for ((p) = list_last_entry(h, typeof(*(p)), field); \
&(p)->field != (h); \
(p) = list_entry((p)->field.prev, typeof(*(p)), field))
（6）：list_for_each_prev()
#define list_for_each_prev(p, h) \
for ((p) = (h)->prev; (p) != (h); (p) = (p)->prev)
（7）：list_for_each_prev_safe()
#define list_for_each_prev_safe(p, n, h) \
for ((p) = (h)->prev, n = (p)->prev; \
(p) != (h); (p) = n, n = (p)->prev)
（8）：list_for_each_entry_continue()
#define list_for_each_entry_continue(pos, head, member) \
list_for_each_entry(pos, head, member)
评论（0）
您还未登录，请登录后发表或查看评论