Chinaunix首页 | 论坛 | 博客
  • 博客访问: 299294
  • 博文数量: 94
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 202
  • 用 户 组: 普通用户
  • 注册时间: 2014-08-08 20:07
文章分类

全部博文(94)

文章存档

2017年(19)

2016年(30)

2015年(12)

2014年(33)

我的朋友

分类: C/C++

2014-08-31 10:14:27

hlist概述
在前面分析了的list,hlist和list是不相同的,在list中每个节点都是一样的,不管头结点还是其他节点,使用同一个结构体表示,但是hlist不是这样表示的。在hlist中,头结点使用的是struct hlist_head来表示的,而对于其他节点使用的是struct hlist_node这个数据结构来表示的。另外,还有一点hlist和list是不相同的,hlist不是双向循环链表,至于为什么要这么设计hlist,原因就是为了去掉list头结点中的prev变量,这样就可以节省空间资源。
具体的有关hlist的空间表示,请参阅图1所示。
 
图1 hlist的空间表示
首先我们要彻底理解struct hlist_node **prev中的二级指针表示的含义。pprev首先也是一个指针,不过它是指向指针的指针(这点请仔细体会),在hlist中pprev指向的是当前hlist_node变量中的前一个变量的next的地址,如果是第一个元素的话,这个值指向的是first的地址,如果是最后一个节点的话,指向的是NULL。如果再深入理解一下,其实*pprev和next这两个变量分别表示指向自己的指针和指向其他节点的指针。
(一)hlist的定义与初始化
下面看一下hlist节点的定义
  1. struct hlist_head {
  2.     struct hlist_node *first;
  3. };
  4. struct hlist_node {
  5.     struct hlist_node *next, **pprev;
  6. };
#define HLIST_HEAD_INIT { .first = NULL }
这个宏定义是用来给struct hlist_head变量来进行初始化的。
#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
这个宏就不用多说了吧,就是定一个一个struct hlist_head节点,并且给其初始化为NULL。
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)
这个宏是给struct hlist_head节点进行初始化的。
  1. static inline void INIT_HLIST_NODE(struct hlist_node *h)
  2. {
  3.     h->next = NULL;
  4.     h->pprev = NULL;
  5. }
这个宏函数是对struct hlist_node节点的一个变量进行初始化的操作。这个宏用在删除节点之后对节点的操作当中。
这么来设计链表结构可能还有另外一个好处:
给pCur的当前节点节点的前面增加一个节点pNode是比较方便的
pNode->next = pCur;
*(pCur->pprev) = pNode;

(二)判断链表是不是空链,节点是不是空节点。
h:struct hlist_node节点指针。
判断h->prev是不是为空,如果pprev的指向是空的话,表示这个节点没有添加到这个链表当中来,如果是空,返回true,否则返回false。这个宏在删除操作当中使用了,在其他许多地方也有调用这个判断。
  1. static inline int hlist_unhashed(const struct hlist_node *h)
  2. {
  3.     return !h->pprev;
  4. }
h:struct hlist_head节点指针(hlist链表的头节点)。
判断hlist链表是不是空链表,如果是,返回true,否则返回false。
  1. static inline int hlist_empty(const struct hlist_head *h)
  2. {
  3.     return !h->first;
  4. }
(三)hlist的删除节点的操作
注:如果对于删除操作理解不是很好时,建议先看下面的增加节点的操作,我是按照内核代码中的顺序进行分析的。
在删除操作这里提供了两个接口:
static inline void hlist_del(struct hlist_node *n)
static inline void hlist_del_init(struct hlist_node *n)
其中第一个接口是将n这个节点删除后不可用指向LIST_POSION,但是后者的话,将删除之后的节点调用了INIT_HLIST_NODE(n)操作,这样就使删除的这个节点中的元素指向了NULL。
真正的删除操作是在static inline void __hlist_del(struct hlist_node *n)中实现的。

n:要删除的节点。
对于删除操作的话,要注意n是不是末尾节点,如果是末尾节点的话,next就是NULL,所以就没有指向的pprev,就更不能进行相应的修改了,否则进行修改。
  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;
  5.     *pprev = next;
  6.     if (next)
  7.         next->pprev = pprev;
  8. }
n:要删除的节点。
在这个函数中首先删除了n节点,之后将n节点的两个指针指向了LIST_POSION,表示不可使用的地方。
  1. static inline void hlist_del(struct hlist_node *n)
  2. {
  3.     __hlist_del(n);
  4.     n->next = LIST_POISON1;
  5.     n->pprev = LIST_POISON2;
  6. }
n:要删除的节点。
首先判断要删除的pprev是不是空,如果是,则不能删除,否则进行删除操作,删除完成之后,将n节点的next和pprev都指向NULL(初始化节点)。
至于这里为什么要判断,我也没有搞清楚。
  1. static inline void hlist_del_init(struct hlist_node *n)
  2. {
  3.     if (!hlist_unhashed(n)) {
  4.         __hlist_del(n);
  5.         INIT_HLIST_NODE(n);
  6.     }
  7. }
(四)hlist增加节点的操作
在增加操作中提供了三个接口:
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
static inline void hlist_add_before(struct hlist_node *n,
struct hlist_node *next)
static inline void hlist_add_after(struct hlist_node *n,
struct hlist_node *next)
下面我们一一来分析:
n:要添加的新的节点。
h:hlist链表的表头节点。
这个函数是给h的下一个和first节点中添加一个新的hlist_node节点,类似与头插。
  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;
  5.     if (first)
  6.         first->pprev = &n->next;
  7.     h->first = n;
  8.     n->pprev = &h->first;
  9. }

n:要添加的新的节点。
next:在next节点之前添加n。
在next节点的前面添加一个新的节点n,在使用这个函数中要特别注意,next不能为NULL。
  1. static inline void hlist_add_before(struct hlist_node *n,
  2.                     struct hlist_node *next)
  3. {
  4.     n->pprev = next->pprev;
  5.     n->next = next;
  6.     next->pprev = &n->next;
  7.     *(n->pprev) = n;
  8. }
对于这段代码的前三句都比较好理解一些,对于*(n->pprev) = n这句,其实就是将添加之前时的next的前面那个节点的next指针指向n这个新增加的节点。

n:表示在n节点之后添加next。
next:要添加的新的节点。
在n节点的后面添加一个新的节点next,这里也要求n不能为NULL。
  1. static inline void hlist_add_after(struct hlist_node *n,
  2.                     struct hlist_node *next)
  3. {
  4.     next->next = n->next;
  5.     n->next = next;
  6.     next->pprev = &n->next;

  7.     if(next->next)
  8.         next->next->pprev = &next->next;
  9. }
总的来说,对于hlist添加一个节点要把握4个指针的指向。
阅读(1654) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~