Chinaunix首页 | 论坛 | 博客
  • 博客访问: 391905
  • 博文数量: 469
  • 博客积分: 50
  • 博客等级: 民兵
  • 技术积分: 1495
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-15 21:04
文章分类

全部博文(469)

文章存档

2015年(81)

2014年(125)

2013年(261)

2012年(2)

分类: LINUX

2015-01-26 15:03:19

在阅读代码的过程中经常出现采用宏定义数据结构的问题,这种宏定义的方式简化了临时类型的定时,能够快速的定义新的类型:

点击(此处)折叠或打开

  1. #define TAILQ_ENTRY(type)                        \
  2. struct {                                \
  3.     struct type *tqe_next;    /* next element */            \
  4.     struct type **tqe_prev;    /* address of previous next element */    \
  5. }

  6. #define TAILQ_HEAD(name, type)            \
  7. struct name {                    \
  8.     struct type *tqh_first;            \
  9.     struct type **tqh_last;            \
  10. }
以上代码能够通过传递不同的类型快速的创建新的数据结构,并不需要进行相关的定义,快速简洁,这种编码的方式也是很多开源代码中经常使用的形式,不是说明这种形式的优势,而是记录一下为什么采用了指向该对象的指针(**tqe_prev),而不是通常情况下采用的前一个对象的指针。由该结构体的形式,回忆起了linux内核源码list.h中的hlist_node结构体,如下所示:

点击(此处)折叠或打开

  1. struct hlist_head {
  2.     struct hlist_node *first;
  3. };

  4. struct hlist_node {
  5.     struct hlist_node *next, **pprev;
  6. };
在这个结构体中为什么不采用prev,而是定义一个pprev指针呢?原因主要是这个对象的使用场景使用这种方式能够较好的实现管理,hlist通常被用来实现hash链表,也就是在某个hash节点中保存一个hlist_head,然后映射到该节点下的对象采用链表的方式管理。通常情况下这种映射不会很多,也就是这个链表中的节点不会很多,如果很多说明对应的hash算法存在问题。这种方式减少了双向链表的内存需求,虽然不能执行快速的双向查找,但在较少节点成员的情况下,对性能影响并不大。
hlist_node中的next是指向下一个对象的指针,而pprev则是指向前一个对象指针的指针,前一个对象的指针的指针实际也就是next指针的指针(有点儿绕)。prev指向了前一个对象,也就是一个hlist_node, pprev则是指向了这个对象的指针,也就是pprev实际上指向了&list_node,实际上&list_node和第一个成员的取地址实际上是一样的,因此&list_node取地址,也可以认为是&next,也就是next指针的指针

在hlist_head中只定义了一个first,这比list_head中少了一个成员,这就简化了数据成员的添加操作,在list_head中添加成员通常需要判断当前链表中是否存在节点,而hlist则不需要,如下所示:

点击(此处)折叠或打开

  1. static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
  2. {
  3.     struct hlist_node *first = h->first;
  4.     n->next = first;//添加到头部,next执行当前head的first
  5.     if (first) //如果当前list中有成员,则将frist的pprev指向需要添加的成员指针
  6.         first->pprev = &n->next;
  7.     h->first = n;//更新head的first成员
  8.     n->pprev = &h->first; //新添加的成员执行first的指针
  9. }
在链表中删除对象实际上也不需要list_head,这个在list的操作中需要无处不在的head。

点击(此处)折叠或打开

  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;  //*prev实际是前一个对象的next,因此*pprev就是前一个对象的next执行了当前对象的next
  6.     if (next)
  7.         next->pprev = pprev;  //下一个节点的prev执行当前节点的pprev
  8. }

  9. static inline void hlist_del(struct hlist_node *n)
  10. {
  11.     __hlist_del(n);
  12.     n->next = LIST_POISON1;
  13.     n->pprev = LIST_POISON2;
  14. }
这种hlist的节点删除相比list的删除要更加的方便。

这边进行简单的分析,仅仅用于记录。
更贱详细的分析可以参见http://blog.csdn.net/hs794502825/article/details/24597773.

TAILQ_ENTRY的定义方式实际是将hlist_node更加的实例化,基本的思路还是一样。
阅读(343) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~