内核链表1

chenjifeng

               
       
       
       
       
       
       
链表数据结构简介
通常链表数据结构至少应包含两个域：数据域和指针域，数据域用于存储数据，指针域用于建立与下一个节点的联系。按照指针域的组织以及各个节点之间的联系形式，链表又可以分为单链表、双链表、循环链表等多种类型，下面分别给出这几类常见链表类型的示意图：
1．
单链表

图1
单链表
单链表是最简单的一类链表，它的特点是仅有一个指针域指向后继节点（next），因此，对单链表的遍历只能从头至尾（通常是NULL空指针）顺序进行。
2．
双链表

图2
双链表
通
过设计前驱和后继两个指针域，双链表可以从两个方向遍历，这是它区别于单链表的地方。如果打乱前驱、后继的依赖关系，就可以构成"二叉树"；如果再让首节
点的前驱指向链表尾节点、尾节点的后继指向首节点（如图2中虚线部分），就构成了循环链表；如果设计更多的指针域，就可以构成各种复杂的树状数据结构。
3．
循环链表
循环链表的特点是尾节点的后继指向首节点。前面已经给出了双循环链表的示意图，它的特点是从任意一个节点出发，沿两个方向的任何一个，都能找到链表中的任意一个数据。如果去掉前驱指针，就是单循环链表。
在Linux内核中使用了大量的链表结构来组织数据，包括设备列表以及各种功能模块中的数据组织。
        定义以及初始化，来看其中的代码：

21struct
list_head

{

22      
struct
list_head

*
next
,
*
prev
;

23};

24

25#define

LIST_HEAD_INIT
(
name
)
{ &(
name
),
&(
name
)
}

26

27#define

LIST_HEAD
(
name
)
\

28      
struct
list_head


name

=
LIST_HEAD_INIT
(
name
)

29

30static

inline

void
INIT_LIST_HEAD
(struct

list_head

*
list
)

31{

32      

list
->
next

=
list
;

33      

list
->
prev

=
list
;

34}
21—23行，定义list_head结构，包含两个指向list_head结构的指针prev和next，具备了双向链表的功能，实际上一般都是一个双向链表结构。
宏调用：[color="#ff0000"]LIST_HEAD_INIT(name)，用于初始化头指针，用此宏初始化必须先有定义：struct
list_head name;
宏调用：[color="#ff0000"]LIST_HEAD(name)，定义并初始化了一个名为name的指向自己的双向链表头。
函数:
static
inline

void
INIT_LIST_HEAD
(struct

list_head

*
list
)，用于运行时初始化，其指针域也是指向自己。
插入：

42#ifndef

CONFIG_DEBUG_LIST


43static

inline

void
__list_add
(struct

list_head

*
new
,

44         
                   struct
list_head

*
prev
,

45         
                   struct
list_head

*
next
)

46{

47      

next
->
prev

=
new
;

48      

new
->
next

=
next
;

49      

new
->
prev

=
prev
;

50      

prev
->
next

=
new
;

51}

52#else

53extern
void
__list_add
(struct

list_head

*
new
,

54         
                   struct
list_head

*
prev
,

55         
                   struct
list_head

*
next
);

56#endif

57

66#ifndef

CONFIG_DEBUG_LIST


67static

inline

void
list_add
(struct

list_head

*
new
,
struct
list_head

*
head
)

68{

69      

__list_add
(
new
,

head
,

head
->
next
);

70}

71#else

72extern
void
list_add
(struct

list_head

*
new
,
struct
list_head

*
head
);

73#endif

84static

inline

void
list_add_tail
(struct

list_head

*
new
,
struct
list_head

*
head
)

85{

86      

__list_add
(
new
,

head
->
prev
,

head
);

87}
你可能会觉得上边所列代码比较长，其实没多少。一共涉及到三个函数：__list_add()、list_add()、list_add_tail().其中第一个函数被包含在后两个函数中，__list_add()函数也是真正实现插入操作的函数。
List_add()的功能是将struct
list_head *new,插入到head后属于头插法。
list_add_tail(),顾名思义他是将new
插入到尾部，即尾插法。
那么_list_add()怎样实现以上两者的功能了？先来看看_list_add()吧，如
图3
链表的插入

他将给他传入的参数new插入到prev和next之间，具体插入动作为：红—黑—绿—黄。然后再回过头来看怎样实现头插和尾插吧，头插只需将(new,head,head->next)传入即可（69行）把(new,head->pre,head)传入即可（86行）,因为他是循环链表所以head->prev就是尾,是不是很巧妙很简单~
删除：

155static

inline

void
__list_del
(struct

list_head

*
prev
,
struct
list_head

*
next
)

156{

157      

next
->
prev

=
prev
;

158      

prev
->
next

=
next
;

159}
以上代码只有一个函数：_list_del(),这个函数实现了下面的函数，类似与_list_add()。实现很简单，短箭头变成了长箭头。注意这时的绿箭头还未断开。
如图四：


167#ifndef

CONFIG_DEBUG_LIST


168static

inline

void
list_del
(struct

list_head

*
entry
)

169{

170      

__list_del
(
entry
->
prev
,

entry
->
next
);

171      

entry
->
next

=
LIST_POISON1
;

172      

entry
->
prev

=
LIST_POISON2
;

173}

174#else

175extern
void
list_del
(struct

list_head

*
entry
);

176#endif

177
给list_del()传递一个将要删除的元素：entry,然后将entry->prev,和entry->next传给_list_del()即可。下面两句（171、172）将图四未断开的绿色指针指向了不同的两个值LIST_POISON1和POISON2，这样是为了防止有些进程使用了未初始化的链表项（可以看看我们的论坛关于这方面的讨论

西邮论坛
），如果访问将导致段错误。

202static

inline

void
list_del_rcu
(struct

list_head

*
entry
)

203{

204      

__list_del
(
entry
->
prev
,

entry
->
next
);

205      

entry
->
prev

=
LIST_POISON2
;

206}
搬移：

265static

inline

void
list_move
(struct

list_head

*
list
,
struct
list_head

*
head
)

266{

267      

__list_del
(
list
->
prev
,

list
->
next
);

268      

list_add
(
list
,

head
);

269}

270
List_move()函数将链表上的list项先从它的链表上删除（_list_del(list->prev,list->next)），然后将list项添加到另外一个链表上（list_add(list,head)）。

276static

inline

void
list_move_tail
(struct

list_head

*
list
,

277         
                       struct
list_head

*
head
)

278{

279      

__list_del
(
list
->
prev
,

list
->
next
);

280      

list_add_tail
(
list
,

head
);

281}
list_move_tail()类似list_move(),区别是：将删除后的list项，添加到head链表的尾部。
一些关于链表的判断函数：

288static

inline

int
list_is_last
(const
struct
list_head

*
list
,

289         
                     const struct
list_head

*
head
)

290{

291      
return
list
->
next

==
head
;

292}

293
这个简单从名字list_is_last()就可以知道他的功能，判断链表项是否为以head为头的最后一个链表项。是返回真，不是返回假。

298static

inline

int
list_empty
(const
struct
list_head

*
head
)

299{

300      
return
head
->
next

==
head
;

301}

316static

inline

int
list_empty_careful
(const
struct
list_head

*
head
)

317{

318      
struct
list_head

*
next

=
head
->
next
;

319      
return (
next

==
head
)
&& (
next

==
head
->
prev
);

320}
以上两个函数也很简单，判断链表是否为空。如果为空返回真，反之返回假。他们的区别是：list_empty()仅仅是检查是否为空即（return

head
->
next

==

head
），而list_empty_careful()同时判断头指针的next和prev，仅当两者都指向自己时才返回真。这主要是为了应付另一个cpu正在处理同一个链表而造成next、prev不一致的
情况。但代码注释也承认，这一安全保障能力有限：除非其他cpu的链表操作只有list_del_init()，否则仍然不能保证安全，也就是说，还是需
要加锁保护。
链表合并：

322static
[color="#0000ff"]inline
void
[color="#0000ff"]__list_splice
(struct
[color="#0000ff"]list_head
*
[color="#0000ff"]list
,

323
                                struct
[color="#0000ff"]list_head
*
[color="#0000ff"]head
)

324[color="#0000ff"]{

325
       struct
[color="#0000ff"]list_head
*
[color="#0000ff"]first
=
[color="#0000ff"]list
->
[color="#0000ff"]next
;

326
       struct
[color="#0000ff"]list_head
*
[color="#0000ff"]last
=
[color="#0000ff"]list
->
[color="#0000ff"]prev
;

327
       struct
[color="#0000ff"]list_head
*
[color="#0000ff"]at
=
[color="#0000ff"]head
->
[color="#0000ff"]next
;

328[color="#0000ff"]

329
      
[color="#0000ff"]first
->
[color="#0000ff"]prev
=
[color="#0000ff"]head
;

330
      
[color="#0000ff"]head
->
[color="#0000ff"]next
=
[color="#0000ff"]first
;

331[color="#0000ff"]

332
      
[color="#0000ff"]last
->
[color="#0000ff"]next
=
[color="#0000ff"]at
;

333
      
[color="#0000ff"]at
->
[color="#0000ff"]prev
=
[color="#0000ff"]last
;

334[color="#0000ff"]}

341static
[color="#0000ff"]inline
void
[color="#0000ff"]list_splice
(struct
[color="#0000ff"]list_head
*
[color="#0000ff"]list
,
struct
[color="#0000ff"]list_head
*
[color="#0000ff"]head
)

342[color="#0000ff"]{

343
       if (!
[color="#0000ff"]list_empty
(
[color="#0000ff"]list
))

344
               
[color="#0000ff"]__list_splice
(
[color="#0000ff"]list
,
[color="#0000ff"]head
);

345[color="#0000ff"]}

346[color="#0000ff"]
先判断list是否为空，不为不为空则进行合并工作_list(&list1,&list2)。实现步骤如图五：

怎么样，简单吧，仅仅是将两个链表连接起来而已。

354static
[color="#0000ff"]inline
void
[color="#0000ff"]list_splice_init
(struct
[color="#0000ff"]list_head
*
[color="#0000ff"]list
,

355
                                   struct
[color="#0000ff"]list_head
*
[color="#0000ff"]head
)

356[color="#0000ff"]{

357
       if (!
[color="#0000ff"]list_empty
(
[color="#0000ff"]list
))
{

358
               
[color="#0000ff"]__list_splice
(
[color="#0000ff"]list
,
[color="#0000ff"]head
);

359
               
[color="#0000ff"]INIT_LIST_HEAD
(
[color="#0000ff"]list
);

360
       }

361[color="#0000ff"]}

362[color="#0000ff"]
此函数类似于上面的list_splice()，只不过比他多了一步INIT_LIST_HEAD(list)而已，这一步相信大家都明白吧，在前面有介绍。
               
               
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/74234/showart_1287075.html