Linux内核中链表的使用
上一篇 / 下一篇 2012-08-09 10:23:40 / 个人分类:Linux
链表是存放和操作可变数量元素的数据结构,它可在需要时动态创建结点并插入链表中,在编译时不需知道包含多少个元素,而且它在内存中也无须占用连续内存区。51Testing软件测试网 cc6OF3lv,N:Y.Fyol
"r.HKRFtfI0 内核有许多链表的实现,而且还有其官方内核实现,所以在内核中使用链表时只要使用官方实现即可,可以说是方便、快捷、高效、安全。链表的基础知 识可见K&R经典C程序设计语言。LKD3e对于内核数据结构的讲解无疑是经典的,但没有更实际的例子以至看后印象不是很深,现通过LKD3e为 指明方向,增加实际例子讲解内核链表是如何操作的。51Testing软件测试网5@tP]g'zW
tH\x&V0 1、链表数据结构51Testing软件测试网1T%_S;p M vtoH3L
51Testing软件测试网k KZt$A2RK_&Q o PdoD,G@'n0
头文件<linux/list.h>51Testing软件测试网&y ~._5z*r,?V 数据结构: 51Testing软件测试网V-}sn.zZ&K2P struct list_head {51Testing软件测试网,l"S8N(}@ struct list_head *next; iYAp"l[1U6E&Z,[0 struct list_head *prev; (A HX"sBl s\0 }; |
需要理解的是内核不是将数据结构插进链表,而是将链表节点插入数据结构,也就是说我们自己定义的每个结构体里面都含有一个struct list_head结构体成员,用其指向链表的下一个节点和上一个节点,它并没有把数据本身插入到链表中。而我们其实只对数据感兴趣,对于struct list_head来说只是一个链接前后节点的工具,那么如何取其数据呢?内核实现是把每个struct list_head和一个数据节点挂勾(也就每个节点中包含struct list_head的原因),通过list_entry()宏即可通过struct list_head结构取包含其的节点数据。51Testing软件测试网,zgZ&J)?!p
Ku(mQ` \'N[0 51Testing软件测试网PC.HMpC
51Testing软件测试网*LBQ9yW~.A+A1T #define list_entry(ptr, type, member) \ #define container_of(ptr, type, member) ({ \ |
LKD3e上描述说:在C语言中,一个给定结构中的变量偏移在编译时地址就被ABI固定下来。也就是说定义的一个结构体变量地址再加上偏移地址就能知道各成员的地址了。51Testing软件测试网!N?:E1`Z2r7]B+Q
'Cu7Ok*]c+e4Pne0 2、定义一个链表51Testing软件测试网9IU3Z!L%^${xO,nk'h
51Testing软件测试网/p$|v,G2k)H`L链表使用之前需要初始化。一般使用链表的情况是定义一个全局链表头,并将其初始化。ip地址和时间挂钩的情况很多时候都可用到,所以现以一个包 含ip地址和一个时间的结构体为例演示内核链表是如何操作使用的。题外话,把存放ip地址的成员定义成4个__u32大小的数组是为了支持ipv6地址, 因为ipv6地址是128bit,4*32刚好是128bit,如果是ipv4地址只用数组的第0个成员足够了,本文只讲解v4地址的比较。51Testing软件测试网z{]p%|L!c
$K!V-Nkm0
-L_/u3j!\?6N j0
51Testing软件测试网fnD5|-s|*C.Kv9N typedef unsigned int __u32 h.fTW%tj2NN(A1e0 51Testing软件测试网`@j/Q5m3K2pM struct ipstore{51Testing软件测试网ElIeI*Jg2e y%jJ3q8o0 static LIST_HEAD(addr_list);51Testing软件测试网AA;mzVj1l |
这样就定义了一个名为addr_list链表头,LIST_HEAD本身是宏,它已对addr_list进行了初始化:51Testing软件测试网F+n[z@8g%G_ v
51Testing软件测试网~]a$@a9v51Testing软件测试网`G9hA%v:W5M I:B5Y
p@F4n5WL&^Pg0#define LIST_HEAD_INIT(name) { &(name), &(name) }51Testing软件测试网5c%[H6fa2Wg P8q)?8|-`
l;SHc0 #define LIST_HEAD(name) \51Testing软件测试网i"lLqy~%[ |
3k(_8|%z0~d"{4a0 如果是动态创建链表结点,使用运行时初始化:51Testing软件测试网3f%F B#VeN+{
51Testing软件测试网 |hk.X7ZKMptw7[%n`?0
struct ipstore *ist; 'Kq&d8sBo0 ist = kmalloc(sizeof (*ist), GFP_ATOMIC); SSJ3s9y!_8V-Uy^4o0 if(!ist)51Testing软件测试网I*c(j$j,i5l2v {51Testing软件测试网~p3b?.b2D printk("kmalloc failed.\n"); B5S5k0Bu.f0 return -1; *zFx8]t`;G@0 }51Testing软件测试网.t,Q5{_9m 4w\]0|`R(Z:bjSP$U0 ist->time = jiffies+time*HZ;51Testing软件测试网0erc'W g(Qn e!pnk ist->addr[0] = 0xc0a80101;//IP:192.168.1.1 TY:}C.IB`0 INIT_LIST_HEAD(&ist->list); |
此时ist就是一个指向已初始化完成并有数据的ipstore结构体结点,其struct list_head成员list已初始化。
P5eEb,p#i0b3Q k;n0*IZ!Ih S.O051Testing软件测试网]&F"x8d_~ @
3、在链表中增加一个节点
G;bf/GAC0 51Testing软件测试网h Q8BBeLh%ei1P4O5KE#a0
static inline void list_add(struct list_head *new, struct list_head *head) "{4e$f$U bM0 { 51Testing软件测试网^*Q~J x%CHL __list_add(new, head, head->next);51Testing软件测试网 f-S&l+Qb"P5{5J5t G } |
要调用此函数,只要在上一步后面接上:51Testing软件测试网 P$d E6C:gN
+Zbox$~bg\#c }0
+~.i3s/g7kXM"K0list_add(&ist->list, &addr_list); |
gJ(w9]1?-p]5o RO0 完整的增加操作:51Testing软件测试网WNkOi!s.@.\X
ZOp_5Qz;}/YF0 51Testing软件测试网1|m(nv-u
struct ipstore *ist; l+R/n-og(G0 ist = kmalloc(sizeof (*ist), GFP_ATOMIC);51Testing软件测试网 v+tpE2i%~H if(!ist) s(zZV6R O(y]8O0 { |