一、linux内核链表与普通链表
内核链表的实现不同于普通链表，内核链表节点中不包含数据，只有前驱和后继指针，使用内核双向链表时需要将双向链表节点嵌套在其它的结构体中。
内核链表节点
struct list_head {
struct list_head *next, *prev;
};
链表节点嵌入到其他结构体中使用
struct input_handler {
void *private;
void (*events)(struct input_handle *handle,
const struct input_value *vals, unsigned int count);
const char *name;
const struct input_device_id *id_table;
struct list_head h_list;
struct list_head node;
};
内核链表图示
二、链表的操作接口
1、声明和初始化
当我们用LIST_HEAD(input_handler_list)声明一个名为input_handler_list的链表头时，它的next、prev指针都初始化为指向自己，这样，我们就有了一个空链表，因为Linux用头指针的next是否指向自己来判断链表是否为空
/*仅初始化*/
#define LIST_HEAD_INIT(name) { &(name), &(name) }
/*声明并初始化*/
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
static LIST_HEAD(input_handler_list);
2、链表的判空
定义
static inline int list_empty(const struct list_head *head)
{
return head->next == head;
}
使用
list_empty(&handler->h_list)
3、链表的插入
接口
static inline void list_add(struct list_head *new, struct list_head *head);
static inline void list_add_tail(struct list_head *new, struct list_head *head);
因为链表是环形的，list_add实现的是将元素插入head, head->next之间，因此可以认为是插在链表的头部；list_add_tail实现的是将元素插入head->prev, head之间，可以认为是插在链表的尾部。
定义
/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
if (!__list_add_valid(new, prev, next))
return;
next->prev = new;
new->next = next;
new->prev = prev;
WRITE_ONCE(prev->next, new);
}
/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
/**
* list_add_tail - add a new entry
* @new: new entry to be added
* @head: list head to add it before
*
* Insert a new entry before the specified head.
* This is useful for implementing queues.
*/
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
使用
list_add_tail(&handler->node, &input_handler_list);
__list_add示意图
4、链表的删除
定义
static inline void list_del(struct list_head *entry)
{
__list_del_entry(entry);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
使用
list_del(&fhandler->link);
5、获取节点
list_entry(ptr, type, member) 实际上是调用的container_of宏。
它的作用是：根据"结构体(type)变量"中的"域成员变量(member)的指针(ptr)"来获取指向整个结构体变量的指针。
参考：
https://blog.csdn.net/s2603898260/article/details/79371024
#define list_entry(ptr, type, member) \
container_of(ptr, type, 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) \
(type *)((char *)(ptr) - (char *) &((type *)0)->member)
使用1
void mwifiex_dfs_cac_work_queue(struct work_struct *work)
{
struct cfg80211_chan_def chandef;
struct delayed_work *delayed_work = to_delayed_work(work);
struct mwifiex_private *priv =
container_of(delayed_work, struct mwifiex_private,
dfs_cac_work);
chandef = priv->dfs_chandef;
if (priv->wdev.cac_started) {
mwifiex_dbg(priv->adapter, MSG,
"CAC timer finished; No radar detected\n");
cfg80211_cac_event(priv->netdev, &chandef,
NL80211_RADAR_CAC_FINISHED,
GFP_KERNEL);
}
}
其中结构体
struct mwifiex_private {
......
struct delayed_work dfs_cac_work;
......
}
使用2
struct evdev *evdev = container_of(dev, struct evdev, dev);
list_entry解析
6、遍历节点
list_for_each_entry遍历链表，并返回结构体地址。
list_for_each 仅仅遍历链表。
list_for_each_entry
/**
* 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_head within the struct.
*/
#define list_for_each_entry(pos, head, member) \
for (pos = list_first_entry(head, typeof(*pos), member); \
&pos->member != (head); \
pos = list_next_entry(pos, member))
/**
* list_next_entry - get the next element in list
* @pos: the type * to cursor
* @member: the name of the list_head within the struct.
*/
#define list_next_entry(pos, member) \
list_entry((pos)->member.next, typeof(*(pos)), member)
list_for_each
/**
* 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)
/**
* 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)
使用
list_for_each_entry(handler, &input_handler_list, node)
input_attach_handler(dev, handler);
当我们采用list__for_each()函数遍历list时，如果我们删除元素，就会导致pos指向的元素的prev=LIST_POISON1，next=LIST_POISON2，当执行到pos=pos->next时，就会出现错误。
但是当我们使用list_for_each_safe()函数遍历list时，如果我们也删除元素后，会执行pos=n，而n=pos->next，注意：n=pos->next中的pos是删除的那个元素，所以虽然删除了元素pos，但是执行了pos=n后，pos指向了正确的遍历位置，所以使用list_for_each_safe()函数遍历list时并不会出现错误。list_for_each_safe()在遍历时之所以不会出现错误，是因为我们使用了n暂时保存了pos，也就是被删除元素所指向的下一个元素，所以用这个函数，准确来说是宏定义，不会出现遍历时删除元素的错误。
