for循环 链表 内核中的链表

早上上班坐地铁要排队，到了公司楼下等电梯要排队，中午吃饭要排队，下班了追求一个女孩子也要排队，甚至在网上下载个什么门的短片也要排队，每次看见人群排成一条长龙时，才真正意识到自己是龙的传人。那么下面咱们就说说队列（链表）。

使用链表的目的很明确，因为有很多事情要做，于是就把它放进链表里，一件事一件事的处理。比如在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)

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-78237-1.html