开源世界中的算法与数据结构 3 -- Linux Kernel List 和GList
List是工程师的基本功,这里并不描述list增删这些细节的内容,仅仅根据我的理解写一下工程中List库的设计和实践考量。
看过几个不同的list库的实现,基本上涉及到如下的设计考量:
1.List数据结构上的差异
有没有头结点,是否循环,是否双向。这样就有多种组合,不罗嗦。
2.list的读写的保护。
3.List直接指针遍历还是仿照STL的Iterator方式遍历。
4.List同实际用户数据是采取一体式还是干湿分离式。
5.系统对于数据结构和算法的影响
1.从数据结构上将,Linux Kernel之中的List是双向无头节点链表。
空链表如下:
非空链表如下:
我觉得维护头结点的理由之一就是可以存放list size,而无需用户在应用部分进行维护。如果没有list size,用户需要在List删减的结束的时候维护list size,如果不愿意如此麻烦,只能悲催的在需要读取链表长度的时候for 循环并“++”一遍。实际上glist库提供get length之类的函数就是遍历list“++”
guint
g_list_length (GList *list)
{
guint length;
length = 0;
while (list)
{
length++;
list = list->next;
}
return length;
}
同样的Linux的kernel list需要的时候也只能如此这般。
2.List的读写保护
我这里提到的读写保护是在多线程之间的访问保护,如果需要在遍历和增删之间要有读写锁,list库不会内部维护锁,因为锁是OS相关的。
linux的list库提供了名为list_for_each_safe的宏也是用于读写访问,起保护范围仅仅在for循环内部,其实现如下:
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
使用n缓存post->next,这样在遍历过程中如果删除pos,不会影响遍历。
3.List直接指针遍历还是仿照STL的Iterator方式遍历。
GList和Linux List都是直接指针进行遍历,我觉得使用迭代子的get next方法间接访问next node可以引入灵活性。
4.有关干湿分离或者一体化
linux的list head定义如下:
struct list_head {
struct list_head *next, *prev;
};
在list库里面没有提供data指针,因此比较适合一体化的方式。
其实干湿分离的优点是可以将任何对象link进来而不用在用户对象内部必须填充list head,不影响用户数据结构,数据的独立性更好,GList就是干湿分离式。
struct _GList
{
gpointer data;
GList *next;
GList *prev;
};
5.系统对于数据结构和算法的影响
我在“有关Cache -(1) linux list之中的Prefetch”提到过:
“linux的list实现之中有如下东东:
#define list_for_each(pos, head) \
for (pos = (head)->next; prefetch(pos->next), pos != (head); \
pos = pos->next)
在遍历过程中使用了prefetch,其功能是数据的预先读取。当你确认后继续要读取某内存的信息的时候,可以采用prefetch将这一块数据读取到cache之中,以便后继快速访问。我的理解是条件不止这些,如果后继读取的内容仅仅被访问一次,那么是否prefetch也就没有意义了。后继访问的内存单元多次被读写才有意义。对于上述的list操作,在循环内部往往还会访问next指向的structure的内容,因此访问多次是可以期待的。”
6.其他
Linux List之中有很多类似“list_for_each”,“list_for_each_entry_safe_reverse”之类的宏。这类的宏在C语言编程中常见,最大的好处就是减少了重复代码书写可能带来的错误。
Linux 2.4 List之中list_for_each定义如下:
#define list_for_each(pos, head) \
for (pos = (head)->next, prefetch(pos->next); pos != (head); \
pos = pos->next, prefetch(pos->next))
建议继续学习:
- 浅谈MySQL索引背后的数据结构及算法 (阅读:9861)
- 浅析linux kernel network之socket创建 (阅读:5682)
- 爱喝啤酒的程序员是如何学习数据结构的 (阅读:5041)
- 分布式系统的数据结构 (阅读:4937)
- stream.js :一个新的JavaScript数据结构 (阅读:4076)
- 浅析Linux Kernel 哈希路由表实现(一) (阅读:3172)
- 浅析Linux Kernel中的那些链表 (阅读:2862)
- Linux kernel 性能压力下的优化实践(V0.1) (阅读:2786)
- 开源世界中的算法与数据结构 2 -- Linux Skbuff实现 (阅读:2702)
- 数据结构之treap (阅读:2664)
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:appleleaf 来源: kernelchina blogs
- 标签: GList Kernel List 数据结构
- 发布时间:2012-02-05 23:19:26
- [66] Go Reflect 性能
- [65] Oracle MTS模式下 进程地址与会话信
- [64] 如何拿下简短的域名
- [59] android 开发入门
- [59] IOS安全–浅谈关于IOS加固的几种方法
- [58] 图书馆的世界纪录
- [58] 【社会化设计】自我(self)部分――欢迎区
- [53] 视觉调整-设计师 vs. 逻辑
- [47] 界面设计速成
- [46] 读书笔记-壹百度:百度十年千倍的29条法则