linux内核list.h之链表hlist

1、数据结构

//hash桶的头结点
struct hlist_head
{
    struct hlist_node *first;//指向每一个hash桶的第一个结点的指针
};

//hash桶的普通结点
struct hlist_node
{
    struct hlist_node *next, **pprev;
};
next指向下一个结点的指针
pprev指向上一个结点的next指针的地址

hlist_head结构体只有一个域，即first。 first指针指向该hlist链表的第一个节点。
hlist_node结构体有两个域，next 和pprev。 next指针很容易理解，它指向下个hlist_node结点，倘若该节点是链表的最后一个节点，next指向NULL。
pprev是一个二级指针，它指向前一个节点的next指针的地址。

为什么我们需要这样一个指针呢？它的好处是什么？

在回答这个问题之前，我们先研究另一个问题：为什么哈希表的实现需要两个不同的数据结构？
哈希表的目的是为了方便快速的查找，所以哈希表中hash桶的数量通常比较大，否则“冲突”的概率会非常大，这样也就失去了哈希表的意义。如何做到既能维护一张大表，又能不使用过多的内存呢？就只能从数据结构上下功夫了。所以对于哈希表的每个hash桶，它的结构体中只存放一个指针，解决了占用空间的问题。现在又出现了另一个问题：数据结构不一致。显然，如果hlist_node采用传统的next,prev指针，对于第一个节点和后面其他节点的处理会不一致。这样并不优雅，而且效率上也有损失。
hlist_node巧妙地将pprev指向上一个节点的next指针的地址，由于hlist_head的first域指向的结点类型和hlist_node指向的下一个结点的结点类型相同，这样就解决了通用性！

2、API接口
（1）初始化头和节点

#define HLIST_HEAD_INIT { .first = NULL }
#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }
#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)

static inline void INIT_HLIST_NODE(struct hlist_node *h)
{
    h->next = NULL;
    h->pprev = NULL;
}

（2）判断一个结点是否已经存在于hash桶中

static inline int hlist_unhashed(const struct hlist_node *h)
{
    return !h->pprev;
}

（3）判断一个hash桶是否为空

static inline int hlist_empty(const struct hlist_head *h)
{
    return !h->first;
}

（4）节点删除

内部删除接口
static inline void __hlist_del(struct hlist_node *n)
{
     struct hlist_node *next = n->next;//获取指向待删除结点的下一个结点的指针
     struct hlist_node **pprev = n->pprev;//保留待删除结点的pprev域
     *pprev = next;//修改待删除结点的pprev域，逻辑上使待删除结点的前驱结点指向待删除结点的后继结点
     if (next)
      next->pprev = pprev;//设置待删除结点的下一个结点的pprev域，保持hlist的结构
}
用户删除接口
static inline void hlist_del(struct hlist_node *n)
{
     __hlist_del(n);//删除结点之后，需要将其next域和pprev域设置为无用值
     n->next = LIST_POISON1;
     n->pprev = LIST_POISON2;
}
带初始化的删除
static inline void hlist_del_init(struct hlist_node *n)
{
    if (!hlist_unhashed(n)) {
        __hlist_del(n);
        INIT_HLIST_NODE(n);
    }
}

（5）将普通结点n插入到头结点h对应的hash桶的第一个结点的位置

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;
}

（6）在next结点之前插入结点n，即使next结点是hash桶中的第一个结点也可以

/* next must be != NULL */
static inline void hlist_add_before(struct hlist_node *n,
                    struct hlist_node *next)
{
    n->pprev = next->pprev;
    n->next = next;
    next->pprev = &n->next;
    *(n->pprev) = n;
}

（7）在结点n之后插入结点next

static inline void hlist_add_after(struct hlist_node *n,
                    struct hlist_node *next)
{
    next->next = n->next;
    n->next = next;
    next->pprev = &n->next;

    if(next->next)
        next->next->pprev  = &next->next;
}

（8）hlist的搬移操作

将new指向old所指向的那个链表。搬移之后，如果new的第一个元素不为空，则修改它的pprev值。
/*
 * Move a list from one list head to another. Fixup the pprev
 * reference of the first entry if it exists.
 */
static inline void hlist_move_list(struct hlist_head *old,
                   struct hlist_head *new)
{
    new->first = old->first;
    if (new->first)
        new->first->pprev = &new->first;
    old->first = NULL;
}

（9）通过一个结构体内部一个成员的地址获取结构体的首地址

#define hlist_entry(ptr, type, member) container_of(ptr,type,member)

（10）遍历链表节点

#define hlist_for_each(pos, head) \
    for (pos = (head)->first; pos ; pos = pos->next)

#define hlist_for_each_safe(pos, n, head) \
    for (pos = (head)->first; pos && ({ n = pos->next; 1; }); \
         pos = n)

（11）遍历链表节点所在的元素

/**
 * hlist_for_each_entry    - iterate over list of given type
 * @tpos:    the type * to use as a loop cursor.
 * @pos:    the &struct hlist_node to use as a loop cursor.
 * @head:    the head for your list.
 * @member:    the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry(tpos, pos, head, member)             \
    for (pos = (head)->first;                     \
         pos &&                             \
        ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
         pos = pos->next)

/**
 * hlist_for_each_entry_continue - iterate over a hlist continuing after current point
 * @tpos:    the type * to use as a loop cursor.
 * @pos:    the &struct hlist_node to use as a loop cursor.
 * @member:    the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry_continue(tpos, pos, member)         \
    for (pos = (pos)->next;                         \
         pos &&                             \
        ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
         pos = pos->next)

/**
 * hlist_for_each_entry_from - iterate over a hlist continuing from current point
 * @tpos:    the type * to use as a loop cursor.
 * @pos:    the &struct hlist_node to use as a loop cursor.
 * @member:    the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry_from(tpos, pos, member)             \
    for (; pos &&                             \
        ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
         pos = pos->next)

/**
 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 * @tpos:    the type * to use as a loop cursor.
 * @pos:    the &struct hlist_node to use as a loop cursor.
 * @n:        another &struct hlist_node to use as temporary storage
 * @head:    the head for your list.
 * @member:    the name of the hlist_node within the struct.
 */
#define hlist_for_each_entry_safe(tpos, pos, n, head, member)          \
    for (pos = (head)->first;                     \
         pos && ({ n = pos->next; 1; }) &&                  \
        ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1;}); \
         pos = n)

#endif

4、内核list.h
　list.h

参考文献 http://blog.csdn.net/hs794502825/article/details/24597773

一	二	三	四	五	六	日
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

C/C++ Learning

添加新评论

个人资料

最新文章

最新回复

标签

归档

统计