Linux核心hlist資料結構分析

     和hlist相關的資料結構例如以下，桶中存儲的 hlist_head 是具有同樣hash值的entry構成的連結清單。每一個entry包括一個 hlist_node 成員，通過它鍊入到這個哈希連結清單中。

struct hlist_head {

      struct hlist_node * first;

};

//next指向下一個節點

// pprev指向前一個節點的next域

struct hlist_node {

      struct hlist_node * next, ** pprev;

結構圖為：

因為頭結點和其它節點的類型不一緻。這樣就不能使用普通的prev指針指向前一個節點（否則處理的時候還要讨論是否是第一個節點，沒有通用性），這裡設計者的巧妙之處就是pprev指針指向前一個節點的next，統一了興許全部的節點。

一些實用的宏：

//頭結點初始化

#define HLIST_HEAD_INIT { .first = NULL }

//構造一個名為name的頭結點

#define HLIST_HEAD(name) struct hlist_head name = {  .first = NULL }

//初始化頭指針，連結清單指針

#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)

#define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)

1.删除節點

next得到目前節點的下一個節點。pprev是前一個節點的next字段的位址，那麼*pprev就指向的是目前這個節點，那麼 *pprev=next 就把目前節點更新為下一個節點了。假設n不是最後一個節點，還要設定next->pprev.

static inline void __hlist_del (struct hlist_node *n)

{

      struct hlist_node *next = n-> next;

      struct hlist_node **pprev = n-> pprev;

     *pprev = next;

      if (next)

          next-> pprev = pprev;

}

static inline void hlist_del (struct hlist_node *n)

     __hlist_del(n);

     n-> next = LIST_POISON1;

     n-> pprev = LIST_POISON2;

2.插入節點

（1）頭插入：讓插入的節點成為連結清單的第一個節點，依次更新對應的指針。示意圖例如以下。

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;

（2）在已知節點next之前/之後插入，通過自己繪圖。非常easy了解清楚。

/* 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;

static inline void hlist_add_after (struct hlist_node *n,

     next-> next = n-> next;

      if(next-> next)

          next-> next-> pprev  = &next-> next;

3.通過看一個節點h的pprev是否為空。推斷其是否在哈希連結清單中。

static inline int hlist_unhashed (const struct hlist_node *h)

      return !h-> pprev;

4.哈希連結清單的周遊（iterate）相關代碼

//通過一個字段member的位址 ptr。得到包括它的容器的位址

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

//用 pos作為遊标來周遊這個連結清單， prefetch是資料預取

#define hlist_for_each(pos, head) \

      for (pos = (head)->first; pos && ({ prefetch(pos->next); 1; }); \

          pos = pos->next)

#define hlist_for_each_safe(pos, n, head) \

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

          pos = n)

//通用的哈希連結清單周遊，當中 pos指向目前節點。 tpos指向的包括hlist_node的目前結構體的指針

#define hlist_for_each_entry(tpos, pos, head, member)               \

      for (pos = (head)->first;                        \

          pos && ({ prefetch(pos->next); 1;}) &&           \

          ({ tpos = hlist_entry(pos, typeof (*tpos), member); 1;}); \

/**

 * hlist_for_each_entry_continue - iterate over a hlist continuing after existing point

 * @ tpos: the type * to use as a loop counter.

 * @ pos:  the &struct hlist_node to use as a loop counter.

 * @member:   the name of the hlist_node within the struct.

 */

#define hlist_for_each_entry_continue(tpos, pos, member)           \

      for (pos = (pos)->next;                          \

 * hlist_for_each_entry_from - iterate over a hlist continuing from existing point

#define hlist_for_each_entry_from(tpos, pos, member)            \

      for (; pos && ({ prefetch(pos->next); 1;}) &&              \

 * hlist_for_each_entry_safe - iterate over list of given type safe against removal of list entry

 * @n:        another &struct hlist_node to use as temporary storage

 * @head: the head for your list.

#define hlist_for_each_entry_safe(tpos, pos, n, head, member)        \

          pos && ({ n = pos->next; 1; }) &&                     \

本文轉自mfrbuaa部落格園部落格，原文連結：http://www.cnblogs.com/mfrbuaa/p/5394727.html，如需轉載請自行聯系原作者