[linux] 内核的链表

   Linux内核的链表能适用于多种链表操作！

 

   定义

  

 

/* include/linux/list.h */
struct list_head {
    struct list_head *next, *prev;
};


 

  使用方式

  在Linux内核链表中，需要用链表组织起来的数据通常会包含一个struct list_head成员，各个实体结构都通过这个list成员组织在一个链表中，如：

 

  初始化

/* 初始化：next、prev都指向自己 */
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)


 

    除了用LIST_HEAD()宏在声明的时候初始化一个链表以外，Linux还提供了一个INIT_LIST_HEAD宏用于运行时初始化链表

#define INIT_LIST_HEAD(ptr) do { \
    (ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)


  插入

    对链表的插入操作有两种：在表头插入和在表尾插入。Linux为此提供了两个接口(内部都是使用__list_add()函数实现)

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);


   插入例子1

    假设有一个新nf_sockopt_ops结构变量new_sockopt需要添加到nf_sockopts链表头，我们应当这样操作：

 

/* 注意第一个参数，是new_sockopt的list元素，而不是其本身 */
list_add(&new_sockopt.list, &nf_sockopts);

 

  删除

static inline void list_del(struct list_head *entry);


    删除例子1

/* 删除nf_sockopts链表中添加的new_sockopt项 */
list_del(&new_sockopt.list);

    被剔除下来的new_sockopt.list，prev、next指针分别被设为LIST_POSITION2和LIST_POSITION1两个特殊值，这样设置是为了保证不在链表中的节点项不可访问--对LIST_POSITION1和LIST_POSITION2的访问都将引起页故障。与之相对应，list_del_init()函数将节点从链表中解下来之后，调用LIST_INIT_HEAD()将节点置为空链状态。

  搬移

    将原本属于一个链表的节点移动到另一个链表的操作，并根据插入到新链表的位置分为两类：

 

/* 由于是双向链表，被移动节点不需明确指明它所属的链表 */
static inline void list_move(struct list_head *list, struct list_head *head);
static inline void list_move_tail(struct list_head *list, struct list_head *head);


 

  合并

static inline void list_splice(struct list_head *list, struct list_head *head);


  遍历

  这里只列出最常用的方式 : list_for_each

/* include/linux/list.h */
#define list_for_each(pos, head) \
    for (pos = (head)->next, prefetch(pos->next); pos != (head); \
            pos = pos->next, prefetch(pos->next))


    是一个for循环，利用传入的pos作为循环变量，从表头head开始，逐项向后（next方向）移动pos，直至又回到head（prefetch()可以不考虑，用于预取以提高遍历速度）。

 

    遍历一般是为了获取节点数据，这需要list_entry()支持list_for_each()，如例子：

 

/* 要获取struct nf_sockopt_ops的节点数据 */
struct nf_sockopt_ops *ops = list_entry(i, struct nf_sockopt_ops, list);


    或者用list_for_each_entry()代替两者

#define list_for_each_entry(pos, head, member)    

    有例子：

struct nf_sockopt_ops *ops;
list_for_each_entry(ops,&nf_sockopts,list){
    ……
}


     另外，反向遍历有

 list_for_each_prev()和list_for_each_entry_reverse()

     从非表头开始遍历有

list_for_each_entry_continue(pos,head,member)和

list_prepare_entry(pos,head,member)

    遍历时节点被删除

    调用者完全可以自己缓存next指针使遍历操作能够连贯起来，但为了编程的一致性，Linux链表仍然提供了两个对应于基本遍历操作的"_safe"接口：list_for_each_safe(pos, n, head)、list_for_each_entry_safe(pos, n, head, member)，