0
0

Linux内核中的通用数据结构

liuw 发表于 2010年12月07日 19:33 | Hits: 4257
Tag: UNIX-like | circular buffer | data structure | generic | kernel | link list | linux | radix tree | red-black tree

Linux内核中实现了一些通用的数据结构,目前我所知的有:

  1. 双向链表:include/linux/list.h
  2. 红黑树:include/linux/rbtree.h lib/rbtree.c
  3. 基数树:include/linux/radix-tree.h lib/radix-tree.c
  4. 环形链表:include/linux/circ_buf.h

Linux内核中的通用数据结构,大部分提供的是“关节”连接点(这个是我自造的词)。这样的好处是程序员还是把主要精力放在目标数据结构上,使用通用函数完成基本操作,而不是把目标数据结构嵌入到通用数据结构中。

这两天在改Xen的代码,需要树去存储和查找数据,于是把Linux里面的红黑树移植到了Xen。顺便也把相关的代码写了。内核中的数据结构为了“通用”,通常只提供最小的功能集。链表还好,因为操作比较简单,所以list.h中全部把这些功能全部都实现了。红黑树比较复杂,插入和搜索这些操作要求使用者自己实现。

(原想把Xen改的那部分放出来,但是那样不大合适。这文章一点营养都没有,不用看了。)

Author: Wei LIU
<liuw at liuw dot name>

Date: 2010-12-07 19:30:50 CST

HTML generated by org-mode 6.21b in emacs 23

原文链接: http://blog.liuw.name/872

0     0

我要给这篇文章打分:

可以不填写评论, 而只是打分. 如果发表评论, 你可以给的分值是-5到+5, 否则, 你只能评-1, +1两种分数. 你的评论可能需要审核.

评价列表(0)