免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 3238 | 回复: 12

[内存管理] hlist_node 使用问题 [复制链接]

论坛徽章:
9
程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-14 06:20:00程序设计版块每日发帖之星
日期:2016-02-14 06:20:0015-16赛季CBA联赛之吉林
日期:2016-03-23 17:25:0015-16赛季CBA联赛之浙江
日期:2016-04-01 08:25:0615-16赛季CBA联赛之山西
日期:2016-04-01 10:09:1915-16赛季CBA联赛之广夏
日期:2016-06-03 15:58:212016科比退役纪念章
日期:2016-07-28 17:42:5215-16赛季CBA联赛之广东
日期:2017-02-20 23:32:43
发表于 2016-03-13 16:04 |显示全部楼层
本帖最后由 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;
};

论坛徽章:
9
程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-14 06:20:00程序设计版块每日发帖之星
日期:2016-02-14 06:20:0015-16赛季CBA联赛之吉林
日期:2016-03-23 17:25:0015-16赛季CBA联赛之浙江
日期:2016-04-01 08:25:0615-16赛季CBA联赛之山西
日期:2016-04-01 10:09:1915-16赛季CBA联赛之广夏
日期:2016-06-03 15:58:212016科比退役纪念章
日期:2016-07-28 17:42:5215-16赛季CBA联赛之广东
日期:2017-02-20 23:32:43
发表于 2016-03-13 17:27 |显示全部楼层
对于上面这个问题,我写了测试代码之后发现,
当我们要通过一个 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 去转换他们的地址.

论坛徽章:
9
程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-14 06:20:00程序设计版块每日发帖之星
日期:2016-02-14 06:20:0015-16赛季CBA联赛之吉林
日期:2016-03-23 17:25:0015-16赛季CBA联赛之浙江
日期:2016-04-01 08:25:0615-16赛季CBA联赛之山西
日期:2016-04-01 10:09:1915-16赛季CBA联赛之广夏
日期:2016-06-03 15:58:212016科比退役纪念章
日期:2016-07-28 17:42:5215-16赛季CBA联赛之广东
日期:2017-02-20 23:32:43
发表于 2016-03-13 19:28 |显示全部楼层
增加测试用例后面发现:
1. 如果定义为 struct hlist_node {
         struct hlist_node **prev,*next;
};
使用 hlist_del() 无法将节点从 hash list 中删除.

论坛徽章:
9
辰龙
日期:2014-08-18 20:38:42未羊
日期:2014-09-04 08:50:45丑牛
日期:2014-09-06 00:12:55寅虎
日期:2014-12-22 20:50:56摩羯座
日期:2015-01-14 22:28:15巳蛇
日期:2015-01-23 20:39:272015年辞旧岁徽章
日期:2015-03-03 16:54:1515-16赛季CBA联赛之青岛
日期:2016-03-13 23:37:1915-16赛季CBA联赛之深圳
日期:2016-03-29 18:52:38
发表于 2016-03-13 21:57 |显示全部楼层
回复 3# Buddy_Zhang1

你犯一个原则错误和一个习惯的错误。

原则错误:pprev不能和prev节点去关联, 因为他指向的是prev的next对像。只是在你的布局1里,next对象就是节点的第一个对像的第一个成员,所以他们的指针一样,理论上,它还是next对像而非节点。 这令你有结构体成员不能随意动成员的约束,这个约束完全是由于你的错解错误以及不严谨用的用法导致的。

Linux习惯错误:Linux的容器编程风格里,有大量的通过结构体成员指针去推导强结构体指针的实例。这种风格,可以使容器本身彻底与对像解耦,并且对像可以同时在多个容器当中。 hlist就是其中一个实例。


其实,在你的用例中,不管你的布局1还是布局。 采用container_of的做法都能够得到正确的结果。 而且,在实际的使用中,我们一般不是想得到hlist节点,而是想得到真正的对像,就算采用你的布局1, 如果hlist不是这个对像的第一个成员, 我们还得用container_of去转换。
   

论坛徽章:
9
辰龙
日期:2014-08-18 20:38:42未羊
日期:2014-09-04 08:50:45丑牛
日期:2014-09-06 00:12:55寅虎
日期:2014-12-22 20:50:56摩羯座
日期:2015-01-14 22:28:15巳蛇
日期:2015-01-23 20:39:272015年辞旧岁徽章
日期:2015-03-03 16:54:1515-16赛季CBA联赛之青岛
日期:2016-03-13 23:37:1915-16赛季CBA联赛之深圳
日期:2016-03-29 18:52:38
发表于 2016-03-13 22:14 |显示全部楼层
回复 3# Buddy_Zhang1
  1. static inline void __hlist_del(struct hlist_node *n)  
  2. {  
  3.         struct hlist_node *next = n->next;           //得到下一个对像
  4.         struct hlist_node **pprev = n->pprev;      // 得到上一个节点的next指针地址。
  5.         *pprev = next;                                       //把这个next指会的值,改为下一个对像的地址。
  6.         if (next)                                                 //如果下一 个对像非空(有真实对像)
  7.                 next->pprev = pprev;                     // 则下个对像的prev指针也得调整回上一个对像的next指针地址。
  8. }  
复制代码
按个代码逻辑应该不会删不掉呀。无论在布局1还是布局2都应该是能工作的呀。有什么理解错了,请各位指正。

   

论坛徽章:
9
程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-14 06:20:00程序设计版块每日发帖之星
日期:2016-02-14 06:20:0015-16赛季CBA联赛之吉林
日期:2016-03-23 17:25:0015-16赛季CBA联赛之浙江
日期:2016-04-01 08:25:0615-16赛季CBA联赛之山西
日期:2016-04-01 10:09:1915-16赛季CBA联赛之广夏
日期:2016-06-03 15:58:212016科比退役纪念章
日期:2016-07-28 17:42:5215-16赛季CBA联赛之广东
日期:2017-02-20 23:32:43
发表于 2016-03-13 22:30 |显示全部楼层
回复 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;
}
   

论坛徽章:
9
程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-14 06:20:00程序设计版块每日发帖之星
日期:2016-02-14 06:20:0015-16赛季CBA联赛之吉林
日期:2016-03-23 17:25:0015-16赛季CBA联赛之浙江
日期:2016-04-01 08:25:0615-16赛季CBA联赛之山西
日期:2016-04-01 10:09:1915-16赛季CBA联赛之广夏
日期:2016-06-03 15:58:212016科比退役纪念章
日期:2016-07-28 17:42:5215-16赛季CBA联赛之广东
日期:2017-02-20 23:32:43
发表于 2016-03-13 22:33 |显示全部楼层
回复 4# Tinnal


    对于这些的理解,我通过测试程序发现 pprev 和 prev 的地址都是一样,*prev 的地址 current 的一样,所以就通过 container_of 来获得 prev.
    这里这么做的目的就是想通过 current 获得 hlist 的 prev.

论坛徽章:
9
程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-14 06:20:00程序设计版块每日发帖之星
日期:2016-02-14 06:20:0015-16赛季CBA联赛之吉林
日期:2016-03-23 17:25:0015-16赛季CBA联赛之浙江
日期:2016-04-01 08:25:0615-16赛季CBA联赛之山西
日期:2016-04-01 10:09:1915-16赛季CBA联赛之广夏
日期:2016-06-03 15:58:212016科比退役纪念章
日期:2016-07-28 17:42:5215-16赛季CBA联赛之广东
日期:2017-02-20 23:32:43
发表于 2016-03-13 22:39 |显示全部楼层
回复 4# Tinnal


   " Linux习惯错误:Linux的容器编程风格里,有大量的通过结构体成员指针去推导强结构体指针的实例。这种风格,可以使容器本身彻底与对像解耦,并且对像可以同时在多个容器当中。 hlist就是其中一个实例。"

    谢谢您的提示.我想知道这里的所指对象同时在多个容器中如何解释? namespace吗??

论坛徽章:
9
辰龙
日期:2014-08-18 20:38:42未羊
日期:2014-09-04 08:50:45丑牛
日期:2014-09-06 00:12:55寅虎
日期:2014-12-22 20:50:56摩羯座
日期:2015-01-14 22:28:15巳蛇
日期:2015-01-23 20:39:272015年辞旧岁徽章
日期:2015-03-03 16:54:1515-16赛季CBA联赛之青岛
日期:2016-03-13 23:37:1915-16赛季CBA联赛之深圳
日期:2016-03-29 18:52:38
发表于 2016-03-13 22:50 |显示全部楼层
回复 8# Buddy_Zhang1

通俗点,一个结构体加入到两个链表里。  那就是没有办法保证链表结构体的首成员是对像本身的,因为肯定有一个不是。

这里的容器,指泛意的容器。不是C++的容器。 容器,就是用来装在对像的东西。你可放东西进行,也可以从里拿东西出来(检索)。 内核是C语言写的,没有高级语言的概念。但编程思想是普世的。  


   

论坛徽章:
9
辰龙
日期:2014-08-18 20:38:42未羊
日期:2014-09-04 08:50:45丑牛
日期:2014-09-06 00:12:55寅虎
日期:2014-12-22 20:50:56摩羯座
日期:2015-01-14 22:28:15巳蛇
日期:2015-01-23 20:39:272015年辞旧岁徽章
日期:2015-03-03 16:54:1515-16赛季CBA联赛之青岛
日期:2016-03-13 23:37:1915-16赛季CBA联赛之深圳
日期:2016-03-29 18:52:38
发表于 2016-03-13 22:59 |显示全部楼层
Buddy_Zhang1 发表于 2016-03-13 22:33
回复 4# Tinnal


要弄清楚现象背后的本质。  pprev 和 prev 的地址一样, 仅仅是因为next成员在node结构体里是第一个成员。值一样,不代表是同一东西。我是男的,你也是男的,但我不是你。这个表面的里解,导致了你最初对结构体成员布局的忧虑。

好的算法,不应与数据结构的布局耦合。因为一旦一个项目大了,你是没有办法控制数据结构的布局的。例如,以后hlist功能增强了,还是next在pprev前。但在next前再加了个color成员,这样,你的程序1就挂了。而且事后做这种代码的更改是有很大风险的。因此,一开始写算法时,就不应假定局部。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP