分类: LINUX
2011-08-28 23:37:14
linux 内核中的hlist_head和hlist_node结构被用于hash表,定义如下:
hlist_node的pprev域开始没看明白为什么是hlist_node的二级指针,但看到代码中对它的使用是让它指向前一个节点的next域(对于第一个节点,指向表头的first域)。为什么要设计成这样?
一般的单链表通常定义如下:
对于这样的链表,在指定节点pCur后插入节点pNode很容易:
但是要在指定节点pCur前插入pNode则很麻烦, 必须找到pCur的前一个结点pPre,然后执行操作:
也就是花费一定的时间用来搜索pCur的前一个节点, linux 为了提高执行效率, 采用了大家熟知的以空间换时间的方案, 添加pprev域, 指向前一个节点的next域,在执行前向插入时无需搜索, 只需执行如下操作就可以了:
Linux 的确是在很多地方都注意提高效率。