Linux 内核链表（2）
之前描述了如何创建内核链表（INIT_LIST_HEAD）向链表中添加节点（list_add）删除一个链表节点（list_del）获取一个链表节点对应的结构体（list_entry）等
接下来会介绍几种操作
替换一个链表节点，合并两个链表，将一个链表分成两段，遍历链表。
替换链表节点
替换节点很好理解，就是将新的节点替换老节点，将新的节点的对应的prev,next指针指向老节点的prev,next。后将老节点prev->next指向新节点，老节点的next->prev指向新节点
[cpp] view plaincopyprint?
- static inline void list_replace(struct list_head *old,
- struct list_head *new)
- {
- new->next = old->next;
- new->next->prev = new;
- new->prev = old->prev;
- new->prev->next = new;
- }
此时old节点的next 与prev指针还是指向 原来的节点，可以使用以下函数重新初始化old节点使其指向 他自身
[cpp] view plaincopyprint?
- static inline void list_replace_init(struct list_head *old,
- struct list_head *new)
- {
- list_replace(old, new);
- INIT_LIST_HEAD(old);
- }
...
更为一般的情况：我们替换链表节点大多都在链表头或者链表尾，所以就有了以下函数
[cpp] view plaincopyprint?
- static inline void list_move(struct list_head *list, struct list_head *head)
替换链表头
[cpp] view plaincopyprint?
- static inline void list_move_tail(struct list_head *list,
- struct list_head *head)
替换链表尾
链表的判断
有时候我们需要判断链表是否为空，或者是否已经到了链表的末尾
内核链表已经为我们实现了这些判断函数。
检查链表是否为空
[cpp] view plaincopyprint?
- static inline int list_empty(const struct list_head *head)
- {
- return head->next == head;
- }
类似的检查是否已经到了链表尾部函数：
[cpp] view plaincopyprint?
- static inline int list_is_last(const struct list_head *list,
- const struct list_head *head)
此外还有一个检测链表是否为空的函数
[cpp] view plaincopyprint?
- static inline int list_empty_careful(const struct list_head *head)
检查链表为空，并且没有另外的处理器回去操作它
合并两个链表
合并链表跟添加一个链表节点差不多，在链表头或链表尾添加新链表均会调用到__list_splice
[cpp] view plaincopyprint?
- static inline void __list_splice(const struct list_head *list,
- struct list_head *prev,
- struct list_head *next)
- {
- struct list_head *first = list->next;
- struct list_head *last = list->prev;
-
- first->prev = prev;
- prev->next = first;
-
- last->next = next;
- next->prev = last;
- }
即将list 链表加到 prev 与 next之间
在链表头添加新链表:
[cpp] view plaincopyprint?
- static inline void list_splice(const struct list_head *list,
- struct list_head *head)
在链表尾部添加新链表调用：
[cpp] view plaincopyprint?
- static inline void list_splice_tail(struct list_head *list,
- struct list_head *head)
拆分一个链表
[cpp] view plaincopyprint?
- static inline void list_cut_position(struct list_head *list,
- struct list_head *head, struct list_head *entry)
以entry为节点拆分以head为头的链表，拆分后list保存从head到entry的链表。head报链表是从entry->next 到链表尾。
遍历链表
创建的链表的目的是为了能够遍历链表得到链表结构中的有效数据。
上一篇文中提到 list_entry他只能获得一个链表节点对应的结构体。
我们可以自己使用for 循环来遍历链表：
[cpp] view plaincopyprint?
- for (pos = head->next; pos != head; pos = pos->next){
- struct data_struct *data = list_entry(pos, struct data_struct, list);
- ...
- }
当然内核已经为我们提供了一套接口（本质就是上边的 for循环）
[cpp] view plaincopyprint?
- list_for_each(pos, head)
到这里 我们想要一个更简单的： 在循环的同时 就用list_entry为我们拿到链表节点对应的数据结构体。所以内核工程师给我们一个接口：
[cpp] view plaincopyprint?
- list_for_each_entry(pos, head, member)
pos:是数据结构体指针， head是链表头，member指在数据结构中链表成员的名字
例如现在定义
[cpp] view plaincopyprint?
- struct data_struct{
- struct list_head list;
- Data data;
- };
我们要遍历链表获得 此结构
[cpp] view plaincopyprint?
- {
- ...
- struct data_struct *pdata;
- list_for_each_entry(pdata, head, list){
- Data tmp = pdata->data;
- ....
- }
- }
在这些版本的遍历中我们不能在循环内删除节点,如果有删除操作怎会导致内核崩溃（因为删除节点时候 node->next被置为了空，如果进行操作.....）,但有时候需要在遍历过程中删除节点，所以内核NB工程师帮我们做了一个 for_safe的版本，他保存一个节点的副本，在节点被删除后，副本仍有效。
[cpp] view plaincopyprint?
- list_for_each_safe(pos, n, head)
[cpp] view plaincopyprint?
- list_for_each_entry_safe(pos, n, head, member)
此处 n用来保存副本
此外还有逆序遍历等再次不再赘述……
请自行查看include/linux/list.h
