<!--StartFragment-->
推荐博文:Linux内核“问题门”——学习问题、经验集锦
<!--EndFragment-->
推荐下载:《Linux内核修炼之道》精华版之方法论
早上上班坐地铁要排队,到了公司楼下等电梯要排队,中午吃饭要排队,下班了追求一个女孩子也要排队,甚至在网上下载个什么门的短片也要排队,每次看见人群排成一条长龙时,才真正意识到自己是龙的传人。那么下面咱们就说说队列(链表)。
使用链表的目的很明确,因为有很多事情要做,于是就把它放进链表里,一件事一件事的处理。比如在USB子系统里,U盘不停的提交urb请求,USB键盘也提交,USB鼠标也提交,那USB主机控制器咋应付得过来呢?很简单,建一个链表,然后你每次提交就是往里边插入,然后USB主机控制器再统一去调度,一个一个来执行。这里有力得证明了,谭浩强大哥的C程序设计是我们学习Linux的有力武器,书中对链表的介绍无疑是英明的,谭大哥,您不是一个人在战斗!
内核中链表的实现位于include/linux/list.h文件,链表数据结构的定义也很简单。
21 struct list_head {
22 struct list_head *next, *prev;
23 };
list_head结构包含两个指向list_head结构的指针prev和next,由此可见,内核中的链表实际上都是双链表(通常都是双循环链表)。
通常,我们在数据结构课堂上所了解的链表定义方式是这样的(以单链表为例):
struct list_node {
struct list_node *next;
ElemType data;
};
通过这种方式使用链表,对每一种数据类型,都要定义它们各自的链表结构。而内核中的链表却与此不同,它并没有数据域,不是在链表结构中包含数据,而是在描述数据类型的结构中包含链表。
比如在hub驱动中使用struct usb_hub来描述hub设备,hub需要处理一系列的事件,比如当探测到一个设备连进来时,就会执行一些代码去初始化该设备,所以hub就创建了一个链表来处理各种事件,这个链表的结构如下图。
(1)声明与初始化。
链表的声明可以使用两种方式,一种为使用LIST_HEAD宏在编译时静态初始化,一种为使用INIT_LIST_HEAD()在运行时进行初始化。
25 #define LIST_HEAD_INIT(name) { &(name), &(name) }
26
27 #define LIST_HEAD(name) /
28 struct list_head name = LIST_HEAD_INIT(name)
29
30 static inline void INIT_LIST_HEAD(struct list_head *list)
31 {
32 list->next = list;
33 list->prev = list;
34 }
无论采用哪种方式,新生成的链表头的两个指针next、prev都初始化为指向自己。
(2)判断链表是否为空。
298 static inline int list_empty(const struct list_head *head)
299 {
300 return head->next == head;
301 }
(3)插入。
有了链表,自然就要往里面加东西、减东西。就像我们每个人每天都在不停的走进去,又走出来,似是梦境又不是梦境。一切都是不经意的。走进去是一年四季,走出来是春夏秋冬。list_add()和list_add_tail()这两个函数就是往队列里加东西。
67 static inline void list_add(struct list_head *new, struct list_head *head)
68 {
69 __list_add(new, head, head->next);
70 }
84 static inline void list_add_tail(struct list_head *new, struct list_head *head)
85 {
86 __list_add(new, head ->prev, head);
87 }
其中,list_add()将数据插入在head之后,list_add_tail()将数据插入在head->prev之后。其实对于循环链表来说,表头的next、prev分别指向链表中的第一个和最后一个节点,所以,list_add()和list_add_tail()的区别并不大。
(4)删除。
搞懂谭浩强那本书之后看这些链表的代码那就是小菜一碟。再来看下一个 list_del_init(),里的元素不能只加不减,没用了的元素就该删除掉,把空间腾出来给别人。郭敬明说过,我生命里的温暖就那么多,我全部给了你,但是你离开了我,你叫我以后怎么再对别人笑……
链表里的元素不能只加不减,没用了的元素就应该删除掉。
254 static inline void list_del_init(struct list_head *entry)
255 {
256 __list_del(entry->prev, entry->next);
257 INIT_LIST_HEAD(entry);
258 }
list_del_init()从链表里删除一个元素,并且将其初始化。
(5)遍历。
内核中的链表仅仅保存了list_head结构的地址,我们如何通过它或取一个链表节点真正的数据项?这就要提到有关链表的所有操作里面,最为重要超级经典的list_entry宏了,我们可以通过它很容易地获得一个链表节点的数据。
425 #define list_entry(ptr, type, member) /
426 container_of(ptr, type, member)
我相信,list_entry()这个宏在Linux内核代码中的地位,就相当于广告词中的任静付笛生的洗洗更健康,相当于大美女关之琳的一分钟轻松做女人,这都是耳熟能详妇孺皆知的,是经典中的经典。如果你说你不知道list_entry(),那你千万别跟人说你懂Linux内核,就好比你不知道陈文登不知道任汝芬你就根本不好意思跟人说你考过研,要知道每个考研人都是左手一本陈文登右手一本任汝芬。
可惜,关于list_entry,这个谭浩强老师的书里就没有了,当然你不能指责谭浩强的书不行,再好的书也不可能包罗万象。
关于list_entry(),让我们结合实例来看,还是hub驱动的那个例子,当我们真的要处理hub的事件的时候,我们当然需要知道具体是哪个hub触发了这起事件。而list_entry的作用就是,从struct list_head event_list得到它所对应的struct usb_hub结构体变量。比如以下四行代码:
struct list_head *tmp;
struct usb_hub *hub;
tmp = hub_event_list.next;
hub = list_entry(tmp, struct usb_hub, event_list);
从全局链表hub_event_list中取出一个来,叫做tmp,然后通过tmp,获得它所对应的struct usb_hub。
分享到:
相关推荐
《LINUX内核修炼之道》精华分享与讨论(14)——内核中的链表..........................................76 《LINUX内核修炼之道》精华分享与讨论(15)——子系统的初始化:内核选项解析...........83 《LINUX内核...
Linux内核问题门..........................................................................................................................13 缅怀已逝的十八年(1991~1998) ...............................
将linux内核源码中list.h拿出来, 增删与遍历部分写了详细注释, 关于链表合并, 没用过所以没写. 源码版本是2.6.32, 不过链表的源码改动应该不是很大. 我的邮箱2253238252@qq.com, 代码有什么不对的欢迎发邮件给我
详细的介绍了Linux内核中使用的最频繁的双向链表
linux内核链表的实现,包括内核链表的定义,以及内核链表相关的操作
一、linux内核链表 1、普通链表的数据区域的局限性 之前定义数据区域时直接int data,我们认为我们的链表中需要存储的是一个int类型的数。但是实际上现实编程中链接中的节点不可能这么简单,而是多种多样的。 一般...
linux内核链表源代码,是list.h是链表的实现,有兴趣的朋友可以下载分析。
对linux内核的链表结构和对内核链表的操作进行超详细讲解
剖析linux 内核 linux内核链表
博客详细讲解Linux内核链表,教你看懂Linux内核链表与普通链表有什么不一样,并且有测试代码
Linux内核链表移植和测试代码
Linux内核中链表和散列表的实现原理揭秘.pdf blog:http://blog.csdn.net/shendl/article/details/6605207 因为blog格式难看,所以把pdf版本上传在这里。 Linux内核的实现,大量使用了数据结构,包括了数组、链表和...
相对于数组,链表具有更好的动态性,建立链表时无需预先知道数据总量,可以随机分配空间,可以高效地在链表中的任意位置实时插入或删除数据。链表的开销主要是访问的顺序性和组织链的空间损失。
linux内核中有关于list 、kfifo等数据结构的实现,从源码中抽取出list部分,可以在linux应用编程中使用。有详细的抽取过程原理,ubunt12.04上完成
linux2.4.18版本源码 内核链表 用户态移植 vc6.0下测试
吐血奉献,忍痛共享! 【最强悍的链表】Linux 内核链表源码
内核链表的构造与操作: 在Linux内核中使用了大量的链表结构来组织数据。这些链表大多数采用了include。/linux/list.h中实现的一套精彩的链表数据结构。 内核的链表具备双链表功能,实际上,通常它都的组织成双向...
在写了内核链表后,写了这段代码,以便自己和他人易于理解和使用链表。
博客详细讲解Linux内核链表,教你看懂Linux内核链表与普通链表有什么不一样
linux内核链表插入,排序函数库,库里面包含了一些宏。可以进行链表的插入,,删减。与一般链表不同的是,可以连接不同类型的数据。