Linux双向链表(四)——宏

╰半橙微兮° 2022-09-18 13:54 189阅读 0赞

通过前第一，二，三篇双向链表的博文，已经对双链表的基础操作函数做了文字与图片的说明。此博文将要展现操作链表的NB的宏，而且这些宏是最常用的操纵链表的接口，几乎是只要有双链表的地方，就有这些操作宏的使用——而且这群hack，对写宏老专业了，写的很漂亮。不信，往下看！

### 1、获取包含双链表结点的结构体基地址 ###

换言之，结构体通过嵌入双链表结点实例这种方式组织在一起，就必须能通过嵌入的双链表结点访问整个结构体。而访问整个结构体，就必须知道结构体基地址。

/**
     * list_entry - get the struct for this entry
     * @ptr:	the &struct list_head pointer.
     * @type:	the type of the struct this is embedded in.
     * @member:	the name of the list_struct within the struct.
     */
    #define list_entry(ptr, type, member) \
    	container_of(ptr, type, member)

通过以下方法得到结构体基地址

1.需要已知三个数据：指向链表结点指针ptr，用户数据类型，用户数据结构中成员变量名。

2.获知用户结构体成员变量在结构体中偏移量

3.依据ptr，计算用户数据数据结构的基址

这里container\_of就是干做这个工作的。

<scripts/kconfig/list.h>
    #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
    
    /**
     * container_of - cast a member of a structure out to the containing structure
     * @ptr:        the pointer to the member.
     * @type:       the type of the container struct this is embedded in.
     * @member:     the name of the member within the struct.
     *
     */
    #define container_of(ptr, type, member) ({                      \
    	const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    	(type *)( (char *)__mptr - offsetof(type,member) );})
    定义一个member类型指针变量__mptr，赋值为ptr

((size\_t) &((TYPE\*)0)->MEMBER)

把0强制转化为TYPE指针类型，即0是一个地址，为段基址。取以0为结构体基址的结构体的成员变量MEMBER的地址，那么这个地址就等于MEMBER域到结构体基地址的偏移字节数，并用size\_t约束为非负整数.

typeof( ((type \*)0)->member )\*\_\_mptr = (ptr);

typeof不是标准里面的，是GCC的扩展功能，它能够根据已知变量名来定义和已知变量名数据类型一致的变量。具体使用方式查看[GCC手册typeof][GCC_typeof],这里不详细介绍了。

定义指向 “数据类型和member一致的” 指针变量\_\_mptr,并初始化为ptr值——在双链表这里，由于ptr指向结构体中的链表结点域，因此\_\_mptr也同样指向结构体中的链表结点

(type \*)( (char \*)\_\_mptr - offsetof(type,member) );

指向结构体链表结点域的指针减去链表结点域相对结构体基地址偏移字节数得到结构体基地址，然后转换成type\*类型就得到结构体基地址了！

注意：使用的时候ptr务必是the pointer to the member.

### 2、获取第一个元素 ###

说明：为了便于讨论，这里说的“元素”即代表包含双链表结点的结构体实例，下同！

/**
     * list_first_entry - get the first element from a list
     * @ptr:	the list head to take the element from.
     * @type:	the type of the struct this is embedded in.
     * @member:	the name of the list_struct within the struct.
     *
     * Note, that list is expected to be not empty.
     */
    #define list_first_entry(ptr, type, member) \
    	list_entry((ptr)->next, type, member)

如果ptr是head，ptr->next就是第一个元素，你完全可以这样理解。因为前文已经提到，无序链表任何一个结点都可以是头。

#### 2.1、获取第一个元素“升级版”——带安全机制 ####

/**
     * list_first_entry_or_null - get the first element from a list
     * @ptr:	the list head to take the element from.
     * @type:	the type of the struct this is embedded in.
     * @member:	the name of the list_struct within the struct.
     *
     * Note that if the list is empty, it returns NULL.
     */
    #define list_first_entry_or_null(ptr, type, member) \
    	(!list_empty(ptr) ? list_first_entry(ptr, type, member) : NULL)

如果链表空，则NULL。否则为第一个元素基址。

### 3、遍历（迭代）链表结点 ###

iterate over迭代的意思——大白话来说——逐个，挨个，从头到尾重复某个过程^\_^

#### 3.1、正向遍历 ####

令沿着next 顺序访问为“正向”访问；以沿着prev 顺序访问为“逆向”访问，下同！

**3.1.1、外部**

/**
     * list_for_each	-	iterate over a list
     * @pos:	the &struct list_head to use as a loop cursor(循环游标).
     * @head:	the head for your list.
     */
    #define list_for_each(pos, head) \
    	for (pos = (head)->next; pos != (head); pos = pos->next)

它从head之后一个元素开始，循环回来，到head（不包含）结束。

由于它是一个for循环语句，后面都要跟语句块\{..\}，因此导致函数中出现类似函数定义，又类似于函数调用的编码风格。比如下面kernel中一片代码

list_for_each(p, &hci_dev_list) {
                     count++;
    }

刚开始觉得有点别扭，说不上好坏，只是一个风格而已！习惯了，也就觉得很自然了！

**3.1.2 内部**

/**
     * __list_for_each	-	iterate over a list
     * @pos:	the &struct list_head to use as a loop cursor.
     * @head:	the head for your list.
     *
     * This variant doesn't differ from list_for_each() any more.
     * We don't do prefetching in either case.
     */
    #define __list_for_each(pos, head) \
    	for (pos = (head)->next; pos != (head); pos = pos->next)

此变体和3.1.1一致，没有区别，但不要作为首要选择，因为前面带两杠的

#### 3.2、逆向遍历 ####

/**
     * list_for_each_prev	-	iterate over a list backwards
     * @pos:	the &struct list_head to use as a loop cursor.
     * @head:	the head for your list.
     */
    #define list_for_each_prev(pos, head) \
    	for (pos = (head)->prev; pos != (head); pos = pos->prev)

1,2的区别如下：

for (pos = (head)->next; pos != (head); pos = pos->next)

for (pos = (head)->prev; pos != (head); pos = pos->prev)

一目了然！~\_0

### 4、迭代方式安全删除链表结点 ###

这里虽然有“删除”两个字眼，但是它自身没有删除功能，只是用于“removal（移除）”表结点

#### 4.1、从head的next开始正向删除 ####

/**
     * list_for_each_safe - iterate over a list safe against removal of list entry
     * @pos:	the &struct list_head to use as a loop cursor.
     * @n:		another &struct list_head to use as temporary storage
     * @head:	the head for your list.
     */
    #define list_for_each_safe(pos, n, head) \
    	for (pos = (head)->next, n = pos->next; pos != (head); \
    		pos = n, n = pos->next)

####    4.2、从head的prev开始逆向删除 ####

/**
     * list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry
     * @pos:	the &struct list_head to use as a loop cursor.
     * @n:		another &struct list_head to use as temporary storage
     * @head:	the head for your list.
     */
    #define list_for_each_prev_safe(pos, n, head) \
    	for (pos = (head)->prev, n = pos->prev; \
    	     pos != (head); \
    	     pos = n, n = pos->prev)

1,2区别如下：

for (pos = (head)->next, n =pos->next; pos != (head);pos= n, n = pos->next)

for (pos = (head)->prev, n =pos->prev;pos != (head);pos = n, n = pos->prev)

###    5、遍历给定类型的链表元素 ###

这里和上文的“结点”不同，访问的是“元素”——pos是结构体基地址

#### 5.1、从head的next开始正向遍历 ####

/**
     * list_for_each_entry	-	iterate over list of given type
     * @pos:	the type * to use as a loop cursor.
     * @head:	the head for your list.
     * @member:	the name of the list_struct within the struct.
     */
    #define list_for_each_entry(pos, head, member)				\
    	for (pos = list_entry((head)->next, typeof(*pos), member);	\
    	     &pos->member != (head); 	\
    	     pos = list_entry(pos->member.next, typeof(*pos), member))

使用这个遍历宏，使得遍历操作变得更加简洁，可读性好，而不必在循环内部调用list\_entry()

#### 5.2、从head的prev开始逆向遍历 ####

/**
     * list_for_each_entry_reverse - iterate backwards over list of given type.
     * @pos:	the type * to use as a loop cursor.
     * @head:	the head for your list.
     * @member:	the name of the list_struct within the struct.
     */
    #define list_for_each_entry_reverse(pos, head, member)			\
    	for (pos = list_entry((head)->prev, typeof(*pos), member);	\
    	     &pos->member != (head); 	\
    	     pos = list_entry(pos->member.prev, typeof(*pos), member))

1,2区别也是一目了然！

#### 5.3、从pos的next开始正向遍历 ####

/**
     * list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()
     * @pos:	the type * to use as a start point
     * @head:	the head of the list
     * @member:	the name of the list_struct within the struct.
     *
     * Prepares a pos entry for use as a start point in list_for_each_entry_continue().
     */
    #define list_prepare_entry(pos, head, member) \
    	((pos) ? : list_entry(head, typeof(*pos), member))

/**
     * list_for_each_entry_continue - continue iteration over list of given type
     * @pos:	the type * to use as a loop cursor.
     * @head:	the head for your list.
     * @member:	the name of the list_struct within the struct.
     *
     * Continue to iterate over list of given type, continuing after
     * the current position.
     */
    #define list_for_each_entry_continue(pos, head, member) 		\
    	for (pos = list_entry(pos->member.next, typeof(*pos), member);	\
    	     &pos->member != (head);	\
    	     pos = list_entry(pos->member.next, typeof(*pos), member))

#### 5.4、从pos的prev开始逆向遍历 ####

/**
     * list_for_each_entry_continue_reverse - iterate backwards from the given point
     * @pos:	the type * to use as a loop cursor.
     * @head:	the head for your list.
     * @member:	the name of the list_struct within the struct.
     *
     * Start to iterate over list of given type backwards, continuing after
     * the current position.
     */
    #define list_for_each_entry_continue_reverse(pos, head, member)		\
    	for (pos = list_entry(pos->member.prev, typeof(*pos), member);	\
    	     &pos->member != (head);	\
    	     pos = list_entry(pos->member.prev, typeof(*pos), member))

####    5.5、从pos开始正向遍历 ####

/**
     * list_for_each_entry_from - iterate over list of given type from the current point
     * @pos:	the type * to use as a loop cursor.
     * @head:	the head for your list.
     * @member:	the name of the list_struct within the struct.
     *
     * Iterate over list of given type, continuing from current position.
     */
    #define list_for_each_entry_from(pos, head, member) 			\
    	for (; &pos->member != (head);	\
    	     pos = list_entry(pos->member.next, typeof(*pos), member))

区别：

list\_for\_each\_entry\_continue()中，指向了当前pos结构指针的next一个，遍历从pos的next元素开始；而在define list\_for\_each\_entry\_from()，省略第一个语句，则遍历从当前pos开始

###    6、迭代方式安全删除链表元素 ###

不能使用list\_for\_each\_entry()循环方式删除元素，而应该使用下面的\*\_safe函数

#### 6.1、从head的next开始正向删除 ####

/**
     * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
     * @pos:	the type * to use as a loop cursor.
     * @n:		another type * to use as temporary storage
     * @head:	the head for your list.
     * @member:	the name of the list_struct within the struct.
     */
    #define list_for_each_entry_safe(pos, n, head, member)			\
    	for (pos = list_entry((head)->next, typeof(*pos), member),	\
    		n = list_entry(pos->member.next, typeof(*pos), member);	\
    	     &pos->member != (head); 					\
    	     pos = n, n = list_entry(n->member.next, typeof(*n), member))

#### 6.2、从head的prev开始逆向删除 ####

/**
     * list_for_each_entry_safe_reverse - iterate backwards over list safe against removal
     * @pos:	the type * to use as a loop cursor.
     * @n:		another type * to use as temporary storage
     * @head:	the head for your list.
     * @member:	the name of the list_struct within the struct.
     *
     * Iterate backwards over list of given type, safe against removal
     * of list entry.
     */
    #define list_for_each_entry_safe_reverse(pos, n, head, member)		\
    	for (pos = list_entry((head)->prev, typeof(*pos), member),	\
    		n = list_entry(pos->member.prev, typeof(*pos), member);	\
    	     &pos->member != (head); 					\
    	     pos = n, n = list_entry(n->member.prev, typeof(*n), member))

#### 6.3、从pos的next开始正向删除 ####

/**
     * list_for_each_entry_safe_continue - continue list iteration safe against removal
     * @pos:	the type * to use as a loop cursor.
     * @n:		another type * to use as temporary storage
     * @head:	the head for your list.
     * @member:	the name of the list_struct within the struct.
     *
     * Iterate over list of given type, continuing after current point,
     * safe against removal of list entry.
     */
    #define list_for_each_entry_safe_continue(pos, n, head, member) 		\
    	for (pos = list_entry(pos->member.next, typeof(*pos), member), 		\
    		n = list_entry(pos->member.next, typeof(*pos), member);		\
    	     &pos->member != (head);						\
    	     pos = n, n = list_entry(n->member.next, typeof(*n), member))

#### 6.4、从pos开始正向删除 ####

/**
     * list_for_each_entry_safe_from - iterate over list from current point safe against removal
     * @pos:	the type * to use as a loop cursor.
     * @n:		another type * to use as temporary storage
     * @head:	the head for your list.
     * @member:	the name of the list_struct within the struct.
     *
     * Iterate over list of given type from current point, safe against
     * removal of list entry.
     */
    #define list_for_each_entry_safe_from(pos, n, head, member) 			\
    	for (n = list_entry(pos->member.next, typeof(*pos), member);		\
    	     &pos->member != (head);						\
    	     pos = n, n = list_entry(n->member.next, typeof(*n), member))

### 7、重设 ###

/**
     * list_safe_reset_next - reset a stale list_for_each_entry_safe loop
     * @pos:	the loop cursor used in the list_for_each_entry_safe loop
     * @n:		temporary storage used in list_for_each_entry_safe
     * @member:	the name of the list_struct within the struct.
     *
     * list_safe_reset_next is not safe to use in general if the list may be
     * modified concurrently (eg. the lock is dropped in the loop body). An
     * exception to this is if the cursor element (pos) is pinned in the list,
     * and list_safe_reset_next is called after re-taking the lock and before
     * completing the current iteration of the loop body.
     */
    #define list_safe_reset_next(pos, n, member)				\
    	n = list_entry(pos->member.next, typeof(*pos), member)

双向链表的API大致介绍完毕！

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>声明<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

>>     知识要传播，劳动要尊重! 受益于开源，回馈于社会! 大家共参与，服务全人类!

>>     本博文由my\_live\_123原创(http://blog.csdn.net/cwcmcw)，转载请注明出处!

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>^\_^<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

[GCC_typeof]: http://gcc.gnu.org/onlinedocs/gcc/Typeof.html