荆门网站建设服务,外包公司好么,网页制作模板,电商网站开发过程在Linux内核中#xff0c;提供了一个用来创建双向循环链表的结构 list_head。虽然linux内核是用C语言写的#xff0c;但是list_head的引入#xff0c;使得内核数据结构也可以拥有面向对象的特性#xff0c;通过使用操作list_head 的通用接口很容易实现代码的重用#xff0…在Linux内核中提供了一个用来创建双向循环链表的结构 list_head。虽然linux内核是用C语言写的但是list_head的引入使得内核数据结构也可以拥有面向对象的特性通过使用操作list_head 的通用接口很容易实现代码的重用有点类似于C的继承机制。下面就是kernel中的list_head结构定义struct list_head {struct list_head *next, *prev;};list_head是linux kernel中非常重要的一个结构体是双向链表的数据结构体为了减少浪费众多链表都是用list_head以及其相关原语操作list_head这个结构看起来怪怪的它竟没有数据域所以看到这个结构的人第一反应就是我们怎么访问数据其实list_head不是拿来单独用的它一般被嵌到其它结构中比如所有的进程是靠它串联在一起的所有的inode也靠它串联在一起等等。需要注意的一点是头结点head是不使用的这点需要注意。使用list_head组织的链表的结构如下图所示list_head特别注意的是list_head中的指针存放的是另一个list_head的地址而不是含有list_head结构的整个数据结构的地址举例如下struct file_node{char c;struct list_head node;};此时list_head就作为它的父结构中的一个成员了当我们知道list_head的地址(指针)时我们可以通过list.c提供的宏 list_entry 来获得它的父结构的地址。下面我们来看看list_entry的实现:(list_entry: 与container_of功能相同)#define list_entry(ptr,type,member)\container_of(ptr,type,member)#define offsetof(TYPE,MEMBER) ((size_t)((TYPE *)0)-MEMBER)#define container_of(ptr,type,member) ( {\const typeof( ((type*)0)-member ) *__mptr(ptr);\(type*)( (char*)__mptr - offsetof(type,member) );} )这里涉及到三个宏还是有点复杂的我们一个一个来看#define offsetof(TYPE,MEMBER) ( (size_t) ((TYPE *)0)- MEMBER )我们知道 0 地址内容是不能访问的但 0地址的地址我们还是可以访问的 这里用到一个取址运算符(TYPE *)0 它表示将 0地址强制转换为TYPE类型((TYPE *)0)- MEMBER 也就是从0址址找到TYPE 的成员MEMBER 。我们结合上面的结构file_node来看将实参代入 offset( struct file_node, node )最终将变成这样( (size_t) ((struct file_node*)0)- node )这样看的还是不很清楚我们再变变struct file_node *p NULL; p-node;这样应该比较清楚了即求 p 的成员 node的地址只不过p 为0地址从0地址开始算成员node的地址也就是 成员 node 在结构体 struct file_node中的偏移量。offset宏就是算MEMBER在TYPE中的偏移量的。我们再看第二个宏#define container_of(ptr,type,member) ( {\const typeof( ((type*)0)-member ) *__mptr(ptr);\(type*)( (char*)__mptr - offsetof(type,member) );} )这个宏是由两个语句组成最后container_of返回的结果就是第二个表达式的值。这里__mptr为中间变量这就是list_head指针类型它被初始化为ptr的值而ptr就是当前所求的结构体中list_head节点的地址。为什么要用中间变量这是考虑到安全性因素如果传进来一个ptr所有ptr放在一个表达式中会有副作用像 (p)(p)之类。(char*)__mptr 之所以要强制类型转化为char是因为地址是以字节为单位的而char的长度就是一个字节。container_of的值是两个地址相减刚说了__mptr是结构体中list_head节点的地址offset宏求的是list_head节点MEMBER在结构体TYPE中的偏移量那么__mptr减去它所在结构体中的偏移量就是结构体的地址。所以list_entry(ptr,type,member)宏的功能就是由结构体成员地址求结构体地址。其中ptr 是所求结构体中list_head成员指针type是所求结构体类型member是结构体list_head成员名。通过下图来总结一下list列举一些双链表的常用操作双向链表的遍历——list_for_each//注这里prefetch 是gcc的一个优化选项也可以不要#define list_for_each(pos, head) \for (pos (head)-next; prefetch(pos-next), pos ! (head); \pos pos-next)生成双向链表的头结点——LIST_HEAD()//LIST_HEAD() -- 生成一个名为name的双向链表头节点#define LIST_HEAD(name) \struct list_head name LIST_HEAD_INIT(name)static inline void INIT_LIST_HEAD(struct list_head *list){list-next list;list-prev list;}双向链表的插入操作 -- list_add()//将new所代表的结构体插入head所管理的双向链表的头节点head之后: (即插入表头)static inline void list_add(struct list_head *new, struct list_head *head){__list_add(new, head, head-next);}static inline void __list_add( struct list_head *new, struct list_head *prev, struct list_head *next){next-prev new;new-next next;new-prev prev;prev-next new;}从list中删除结点——list_del()static inline void list_del(struct list_head *entry){__list_del(entry-prev, entry-next);entry-next LIST_POISON1;entry-prev LIST_POISON2;}static inline void __list_del(struct list_head * prev, struct list_head * next){next-prev prev;prev-next next;}判断链表是否为空(如果双向链表head为空则返回真否则为假)——list_empty()static inline int list_empty(const struct list_head *head){return head-next head;}
