kernel list实现技巧
-
kernel list
实现技巧偶然间,翻到了一篇帖子下的评论说内核中的链表官方实现很巧妙,具有强大的通用性。于是我动手打开源码开始研究,内核链表实现通用性的方法与
kfifo
不仅异曲同工,甚至更加简洁优雅,实在是令我叹为观止。内核中维护的链表节点定义如下,非常简洁:
struct list_head { struct list_head *next, *prev; };
那么这个链表节点如何使用呢?巧妙之处又在哪里呢?
这里总结一下最朴素的链表实现方法,假设现在我们需要维护一个元素类型为
apple
的链表,我们一般会将链表元素定义为如下结构体:struct apple { unsigned int weight; char name[30]; ... struct apple *next, *prev; };
这样实现有什么问题呢?
-
通用性和代码可复用性。这样一来我们每定义一个类型的链表元素类型,都需要重新写一套新的API提供链表操作(插入,删除等)。
-
链表元素不能多样化。这样的实现方法就不可能满足链表元素多样化的需求。
Think outside the box! 这是我对内核链表官方实现的概括。这个implementation并不像
kfifo
一样exploit编译器的功能,相反,它是源自于算法层面的思考。我们一般的链表实现都是将元素插入链表里,但是内核链表官方实现的原理却是将共同的部分提取出来作为list_head
,而每个list_head
就相当于一个个衣架,而我们想要存储的元素就是一件件衣服,整个链表就是一个晾衣绳上用衣架挂着很多衣服。如何从
kernel list
中获得元素?内核中提供了
list_entry
这个API用来访问某个list_head
对应的链表元素。其定义如下:#define list_entry(ptr, type, member) container_of(ptr, type, member)
其中
ptr
是从内核链表中获得的一个list_head
指针;type
是链表元素的结构体类型;member
是list_head
在链表元素的结构体类型中定义的字段名称。对于内核中的通用性处理,我也会继续更新不同的内容。拜读大师们的作品,岂不乐乎?
-
-
-
此回复已被删除!