随笔-118  评论-133  文章-4  trackbacks-0
近日研究vfs文件系统,继而研究hlist链表,曾经一度给迷惑,好不容易弄明白。本想写个帖子,可是发现已经有很好的贴可供参考了。自问写不出这么好的帖子,还是转一下好了^_^
注:
    原文出处:http://blog.chinaunix.net/u/12592/showart.php?id=451619

王耀(wangyao@cs.hit.edu.cn)

hlist哈希链表是内核中常用的一个数据结构,由于它不同于普通的链表,所以这里对hlist哈希链表进行一下分析,希望对大家有所帮助。
在include/Linux/list.h中有list链表与hlist哈希链表结构的定义,下面都列出它们的定义,可以对比一下:
struct list_head {
struct list_head *next, *prev;
};

struct hlist_head {
struct hlist_node *first;
};

struct hlist_node {
struct hlist_node *next, **pprev;
};

双头(next,prev)的双链表对于Hash表来说“过于浪费”,因而另行设计了一套Hash表专用的hlist数据结构——单指针表头双循环 链表,hlist的表头仅有一个指向首节点的指针,而没有指向尾节点的指针,这样在可能是海量的Hash表中存储的表头就能减少一半的空间消耗。
pprev因为hlist不是一个完整的循环链表而不得不使用。在list中,表头和节点是同一个数据结构,直接用prev没问题;在hlist中,表头 没有prev,也没有next,只有一个first。为了能统一地修改表头的first指针,即表头的first指针必须修改指向新插入的节点, hlist就设计了pprev。hlist节点的pprev不再是指向前一个节点的指针,而是指向前一个节点(可能是表头)中的next(对于表头则是 first)指针(struct list_head **pprev),从而在表头插入的操作可以通过一致的“*(node->pprev)”访问和修改前节点的next(或first)指针。
注:pprev是指向前一个节点中的next指针,next是指向hlist_node的指针,所以pprev是一个指向hlist_node的指针的指针。


注意:
pprev可以理解成向list的prev一样,是一个指向hlist_node的指针,又由于hlist_node的第一个元素next是一个指向 hlist_node的指针,pprev也是一个指向next的指针,即pprev是一个指向hlist_node的指针的指针。
struct hlist_node Prev;
struct hlist_node *pprev = (struct hlist_node *) Prev = (struct hlist_node *) (struct hlist_node * next) = struct hlist_node ** next;

下面是hlist中常用的几个宏:
#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
#define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)

下面只列出hlist_add_before操作函数,其他hlist链表操作函数操作方法类似。这个函数中的参数next不能为空。它在next前面加入了n节点。函数的实现与list中对应函数类似。
static inline void __hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next;
struct hlist_node **pprev = n->pprev;
*pprev = next;
if (next)
next->pprev = pprev;
}

static inline void hlist_add_before(struct hlist_node *n,struct hlist_node *next)
{
n->pprev = next->pprev;
n->next = next;
next->pprev = &n->next;
*(n->pprev) = n;
}

#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
#define hlist_for_each(pos, head) \
for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \
pos = pos->next)
posted on 2008-01-17 17:32 lfc 阅读(6910) 评论(6)  编辑 收藏 引用

评论:
# re: [转]hlist哈希链表 2008-02-12 21:03 | todaygood
呵呵,正需要这个哈西链表。


luo兄 看来一直在搞 开发板子阿 , 你所在公司是干什么行业的?  回复  更多评论
  
# re: [转]hlist哈希链表 2008-03-07 14:28 | luofuchong
@todaygood
开发板公司,不过我的部门是做一下linux的小项目的,平时有空的时候可以研究一下linux的东西。  回复  更多评论
  
# re: [转]hlist哈希链表 2011-11-13 22:25 | tek-life
这个图没有画完整啊。  回复  更多评论
  
# re: [转]hlist哈希链表 2012-06-17 17:28 | 为何
不完整  回复  更多评论
  
# re: [转]hlist哈希链表 2012-06-17 17:29 | 为何
感谢  回复  更多评论
  
# re: [转]hlist哈希链表 2012-12-21 15:55 | 内核菜菜鸟
首节点的pprev指向头节点的first,尾节点的next指针为NULL.
应该是这样的。  回复  更多评论
  
只有注册用户登录后才能发表评论。