Chinaunix首页 | 论坛 | 博客
  • 博客访问: 408897
  • 博文数量: 47
  • 博客积分: 1488
  • 博客等级: 上尉
  • 技术积分: 729
  • 用 户 组: 普通用户
  • 注册时间: 2010-08-15 11:35
文章分类

全部博文(47)

文章存档

2012年(4)

2011年(22)

2010年(21)

分类: LINUX

2011-08-28 23:37:14

 

linux 内核中的hlist_head和hlist_node结构被用于hash表,定义如下:

  1. struct hlist_head {
  2.    struct hlist_node *first;
  3. };
  4. struct hlist_node {
  5.    struct hlist_node *next, **pprev;
  6. };


hlist_node的pprev域开始没看明白为什么是hlist_node的二级指针,但看到代码中对它的使用是让它指向前一个节点的next域(对于第一个节点,指向表头的first域)。为什么要设计成这样?
一般的单链表通常定义如下:

  1. struct node {
  2.    struct node *next;
  3. };

对于这样的链表,在指定节点pCur后插入节点pNode很容易:

  1. pNode->next = pCur;
  2. pCur->next  = pNode;

但是要在指定节点pCur前插入pNode则很麻烦, 必须找到pCur的前一个结点pPre,然后执行操作:

  1. pPre->next = pNode;
  2. pNode->next = pCur;

也就是花费一定的时间用来搜索pCur的前一个节点, linux 为了提高执行效率, 采用了大家熟知的以空间换时间的方案, 添加pprev域, 指向前一个节点的next域,在执行前向插入时无需搜索, 只需执行如下操作就可以了:

  1. *(pCur->ppre) = pNode;
  2. pNode->next = pCur;

Linux 的确是在很多地方都注意提高效率。

阅读(5415) | 评论(7) | 转发(1) |
给主人留下些什么吧!~~

vacing2015-04-29 09:47:21

http://blog.csdn.net/zhanglei4214/article/details/6767288

vacing2015-04-29 09:47:16

http://blog.csdn.net/zhanglei4214/article/details/6767288

wukui10082012-02-11 18:41:11

你讲的是单向链表 跟双向链表  
这个好明白
我觉得你应该帮我们分析一下
**pprev   为什么要二级指针,而不用一级指针

sudoers2011-09-08 22:57:08

sunjiangang-ok: 博主解释的很有道理,但是我觉得下面的分析有些不对劲:

对于这样的链表,在指定节点pCur后插入节点pNode很容易:
pNode->next = pCur;
pCur->next  = p.....
我明白你的意思, 严格按照实际逻辑讲是你写的那样,我那样写没去考虑原来pCur->next 是为了简单示意而已

kingyueyang2011-08-30 13:42:35

同意sunjiangang-ok 看法