linux 内核链表

链表和内核链表的区别

一．通常链表包含两个域，数据域和指针域，数据域用于存储数据，指针域用于建立连接，按照指针域的不同，可以分为各式链表，单链表只能指向下一个链表的地址，双链表有钱去和后继。

二．在linux2.6中，链表的数据结构在include/linux/list.h中：struct list_head结构包含两个指向list_head结构包含两个指向list_head结构的指针prev和next，内核链表具有双链表功能，一般都为双向循环链表，list_head看似指向头部，其实指向普通节点的结构体。

三．Struct list_node{} 对于Elemtype的缘故，对每一种数据项类型都需要定义各自的链表结构，并且对每种的数据结构定义相应的操作函数，比如插入，删除，排序等。

四．内核链表的好处

尽可能的代码重用，化大堆的链表设计为单个链表，如果需要构造某对象的特定列表，则在其结构中定义一个类型为list_head指针的成员，通过这个成员将这类对象链接起来，形成所需要的列表，并通过通用链表函数对其进行操作。其优点是只需要编写通用链表函数，即可构造和操作不同对象的列表。而无需为每类对象的每种列表编写专门函数，实现了代码的重用，如果想对某种类型创建链表，就把一个list_head类型的变量嵌入到该类型中，用list_head中的成员和相对应的处理函数来对链表进行便利，如果想得到相应的结构的指针，使用list_entry可以算出来。

五．新建链表

实际上linux只定义了链表节点，并没有专门定义链表头。那么一个链表结构是如何建立的，在list_head中的成员

#define List_head_init(name){&(name),&(name)}

#define list_head(name) struct list_head name =list_head_init(name)

其中的name是struct list_head结构的变量的地址，而不是包含struct list_head的数据结构的变量的地址

六．插入删除移动合并

插入：在链表头插入和链表尾插入 linux提供了两套接口

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)

删除：

Static inline void list_del(struct list_head *entry)

搬除

Linux提供了将原本属于一个链表的节点移动到另一个链表的操作，并根据插入到新链表的位置分为两类：
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)

合并

除了针对节点的插入，删除操作，linux链表还提供了整个链表的插入功能

Static inline void list_splice（struct list_head *list,struct list_head *head）;

遍历

遍历是链表最常用的操作，为了方便核心应用遍历链表，linux链表将遍历操作抽象成几个宏，在介绍遍历宏之前，我们先看看如何从链表中访问到我们真正需要的数据项。

1.由链表节点到数据项变量

Linux_entry宏是用来根据list_head指针查找链表所嵌入的结构体地址，具体实现是以来宏container_of

#define list_entry(ptr,type,member)  container_of(ptr,type,member)

#define container_of(ptr,type,member)({const typeof(((type *)0)->member)*__mptr=()ptr});

(type *)(char *)__mptr-offsetof(type,member);})

#define offset(type,member)(size_t)&(type *)0)->member

Container_of有三个参数，ptr是成员变量的指针，type是指结构体的类型，member是成员的名字，container_of的作用就是在已知某一个成员变量的名字，指针和结构体类型的情况下，计算结构体的指针，也就是计算结构体的起始地址。计算的方法比较简单，用该成员变量的指针减去它的type结构体起始地址的偏移量。在这个定义中，typeof（（type *）0）->member)就是获得member的类型，然后定义了一个临时的常量指针 _mptr，指向char *类型，因为ofsetof

         Offsetof在这里，TYPE表示一个结构体的类型。MEMBER是结构体中的一个成员变量的名字。Offsetof宏的作用是计算成员变量MEMBER相对于结构体起始位置的内存便宜，以字节（BYTE）为单位。

遍历宏

函数首先定义（struct list_head *）指针变量i，然后调用list_for_each（I,&nf_sockopts）进行遍历。在[includelinux/list.h]中，list_for_each（）宏的定义是

#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，在大多数情况下，遍历链表的时候都需要获得链表的节点数据项，也就是list_for_each()和list_entry()总是同时使用，对此linux给出了一个list_for_each_entry()宏，与list_for_each()不同，这里的pos是数据项结构指针类型，而不是（struct list_head*）

#definelist_for_each_entry（pos，head，member）

如需反向遍历链表，linux提供了list_for_each_prev()和list_each_entry_reverse()来完成，

 

 感谢http://www.cnblogs.com/Daniel-G/archive/2013/09/06/3305834.html