hlist_node 使用问题
本帖最后由 Buddy_Zhang1 于 2016-03-13 17:56 编辑在 Linux 中hash链表的一个数据使用 struct hlist_node 表示,其定义为:
strcut hlist_node {
struct hlist_node *next,**pprev;
};
如果上面的定义变成下面会出现什么问题?????
struct hlist_node {
struct hlist_node **pprev,*next;
}; 对于上面这个问题,我写了测试代码之后发现,
当我们要通过一个 struct hlist_node 获得它的前一个 struct hlist_node 的实现存在差别,测试代码如下:
1. 如果 struct hlist_node {
struct hlist_node *next,**prev;
};
void TestCase(void)
{
struct hlist_node *node; //已知
struct hlist_node *prev_node;
prev_node = (struct hlist_node *)(unsigned long)(node->pprev);
}
通过这种方法就可以获得 struct hlist_node 的前一个 struct hlist_node.
2. 如果 struct hlist_node {
struct hlist_node **pprev,*next;
};
void TestCase(void)
{
struct hlist_node *node; // 已知
struct hlist_node *prev_node;
prev_node = container_of(node->pprev,struct hlist_node,next);
}
通过这种方法可以获得 struct hlist_node 的前一个 struct hlist_node.
归其上面因为 struct hlist_node 成员分布不同导致这个问题的原因是:
void hlist_add_head(struct hlist_node *node,struct hlist_head *head)
{
struct hlist_node *first = head->first;
node->next = first;
if(first)
first->pprev = &node->next; // 因为这里 &node->next 的地址与 struct hlist_node 地址之间关系差别导致上面的差异.
head->first = node;
node->pprev = &head->first;
}
如上面源码所示:
struct hlist_node {
struct hlist_node *next,**pprev;
};
这样的定义结构是 next 的地址和 struct hlist_node 的地址是一样的.
而
struct hlist_node {
struct hlist_node **pprev,*next;
};
这样定义结构是 next 的地址和 struct hlist_node 之间是有差异的,需要使用 container_of 去转换他们的地址. 增加测试用例后面发现:
1. 如果定义为 struct hlist_node {
struct hlist_node **prev,*next;
};
使用 hlist_del() 无法将节点从 hash list 中删除. 回复 3# Buddy_Zhang1
你犯一个原则错误和一个习惯的错误。
原则错误：pprev不能和prev节点去关联， 因为他指向的是prev的next对像。只是在你的布局1里，next对象就是节点的第一个对像的第一个成员，所以他们的指针一样，理论上，它还是next对像而非节点。 这令你有结构体成员不能随意动成员的约束，这个约束完全是由于你的错解错误以及不严谨用的用法导致的。
Linux习惯错误：Linux的容器编程风格里，有大量的通过结构体成员指针去推导强结构体指针的实例。这种风格，可以使容器本身彻底与对像解耦，并且对像可以同时在多个容器当中。 hlist就是其中一个实例。
其实，在你的用例中，不管你的布局1还是布局。 采用container_of的做法都能够得到正确的结果。 而且，在实际的使用中，我们一般不是想得到hlist节点，而是想得到真正的对像，就算采用你的布局1， 如果hlist不是这个对像的第一个成员， 我们还得用container_of去转换。
回复 3# Buddy_Zhang1 static inline void __hlist_del(struct hlist_node *n)
{
struct hlist_node *next = n->next; //得到下一个对像
struct hlist_node **pprev = n->pprev; // 得到上一个节点的next指针地址。
*pprev = next; //把这个next指会的值，改为下一个对像的地址。
if (next) //如果下一 个对像非空（有真实对像）
next->pprev = pprev; // 则下个对像的prev指针也得调整回上一个对像的next指针地址。
}按个代码逻辑应该不会删不掉呀。无论在布局1还是布局2都应该是能工作的呀。有什么理解错了，请各位指正。
回复 4# Tinnal
我这有个地方理解有点不是很明白,代码如下:
static inline void hlist_add_head(struct hlist_node *n,struct hlist_head *h)
{
struct hlist_node *first = h->first;
n->next = first;
if(first)
first->pprev = &n->next; // 对于这里,理解不是很明确,为了验证它的含义,我做了下面修改.修改如下:
h->first = n;
n->pprev = &h->first;
}
修改后:
static inline void hlist_add_head(struct hlist_node *n,struct hlist_head *h)
{
struct hlist_node *first = h->first;
n->next = first;
if(first)
first->pprev = &first;// 这样修改,含义是否会有变??????????????????????????????????????????????????????????
h->first = n;
n->pprev = &h->first;
}
回复 4# Tinnal
对于这些的理解,我通过测试程序发现 pprev 和 prev 的地址都是一样,*prev 的地址 current 的一样,所以就通过 container_of 来获得 prev.
这里这么做的目的就是想通过 current 获得 hlist 的 prev. 回复 4# Tinnal
" Linux习惯错误：Linux的容器编程风格里，有大量的通过结构体成员指针去推导强结构体指针的实例。这种风格，可以使容器本身彻底与对像解耦，并且对像可以同时在多个容器当中。 hlist就是其中一个实例。"
谢谢您的提示.我想知道这里的所指对象同时在多个容器中如何解释? namespace吗??
回复 8# Buddy_Zhang1
通俗点，一个结构体加入到两个链表里。那就是没有办法保证链表结构体的首成员是对像本身的，因为肯定有一个不是。
这里的容器，指泛意的容器。不是C++的容器。 容器，就是用来装在对像的东西。你可放东西进行，也可以从里拿东西出来（检索）。 内核是C语言写的，没有高级语言的概念。但编程思想是普世的。
Buddy_Zhang1 发表于 2016-03-13 22:33 static/image/common/back.gif
回复 4# Tinnal
要弄清楚现象背后的本质。pprev 和 prev 的地址一样， 仅仅是因为next成员在node结构体里是第一个成员。值一样，不代表是同一东西。我是男的，你也是男的，但我不是你。这个表面的里解，导致了你最初对结构体成员布局的忧虑。
好的算法，不应与数据结构的布局耦合。因为一旦一个项目大了，你是没有办法控制数据结构的布局的。例如，以后hlist功能增强了，还是next在pprev前。但在next前再加了个color成员，这样，你的程序1就挂了。而且事后做这种代码的更改是有很大风险的。因此，一开始写算法时，就不应假定局部。
页:
[1]
2