hlist求教：如何迅速定位hlist的尾节点？

allenlu1212

list:
由于是双向链表，可以很方便从头部或尾部对整个链表进行遍历。

hlist:
由于表头没有prev，也没有next，只有一个first，所以只能从表头开始对整个链表进行遍历。

问题：
如果想迅速定位hlist的尾节点，除了遍历外，有没有更高效的办法？

欢迎大家参与讨论，共同进步！

allenlu1212

从数据结构的角度看，应该是只能通过遍历找到最后一个，不过，这里有两个疑问：

1. 链表中第一个entry的node->pprev指向的是head->next, 为什么不让其指向最后一个entry呢?

2. 大家遇到此类需要在hlist末尾进行操作的时候，有没有什么折中的方法或建议或技巧？

自己先顶下！！！

mars007

如果第一个节点的pprev指向最后一个节点,那么删除一个节点就得考虑节点是不是第一个节点,如果是,那么必须让第二个节点的pprev指向最后一个节点,但是,给你一个节点你无法知道它是不是第一个节点

哈希表本身用于节点不是很多的情况(如果节点太多那肯定是你的算法有问题了),因此遍历的话不会有很大的开销

allenlu1212

有道理，总结下，linux 对hlist设计是基于以下考虑的：
1. hash表中往往有海量的buckets,  需要减少头节点的指针数，故只有一个first指针。
2. hash表中每个List上的entry不是很多，同时为了保证对第一个节点和操作和其他相同，
    故采用pprev指向前一个节点的next。