hlistハッシュ・リスト

hlistハッシュ・チェーンはカーネルの中でよく使われるデータ構造です.普通のチェーンとは違って、ここでhlistハッシュ・チェーンを分析してみます.include/Linux/list.hにはリストリストリストとhlistハッシュ・チェーン構造の定義があります.以下にそれらの定義を並べて、比較してみてもいいです.
struct hlist_head{struct hlistherst}
struct hlist_node{struct hlistinxt*next、**pprev;;;
ダブルヘッド(next、prev)のダブルチェーンは、Hashテーブルにとっては「もったいない」ため、別にHashテーブル専用のhlistデータ構造を設計しました.単一のポインタの先頭の二重循環チェーンは、hlistの先頭が最初のノードを指すポインタだけであり、最後のノードのポインタを指していません.これにより、大容量の可能性のあるHashテーブルに格納されているヘッダは、半分の空間消費を削減することができる.pprevはhlistが完全なサイクルチェーンではないので使わざるを得ません.リストでは、ヘッダとノードは同じデータ構造であり、直接prevで大丈夫です.hlistの中で、表の頭はprevがなくて、nextもなくて、1つのfirstだけあります.表ヘッドのfirstポインタ、すなわち、表ヘッドのfirstポインタを統一的に修正するためには、新たに挿入されるノードに向けて修正しなければならず、hlistはpprevを設計した.hlistノードのpprevは、前のノードを指すポインタではなく、前のノードのnext(先頭に対してはfirst)ポインタ(struct listuhead*pprev)を指すので、先頭に挿入される動作は一致する「*(node-pprev)」によって、前のノードのnext(first)ポインタ(またはfirstポインタ)にアクセスすることができます.注:pprevは前のノードのnextポインタを指し、nextはhlist_を指す.nodeの針ですので、pprevはhlist_を指します.nodeの針の針.
注意:pprevはlistのprevと同じで、hlist_を指すと理解できます.nodeの針は、またhlist_によってnodeの一番目の要素nextはhlist_を指します.nodeの針、pprevはnextを指す指針でもあります.つまりpprevはhlist_を指します.nodeの針の針.struct list_head {
struct list_head *next, *prev;
};以下はhlistでよく使われるいくつかのマクロです.struct hlist_node Prev;
struct hlist_node *pprev = (struct hlist_node *) Prev = (struct hlist_node *) (struct hlist_node * next) = struct hlist_node ** next;下にはhlist_だけ書いてあります.add_before操作関数、その他のhlistチェーン操作関数の操作方法は類似しています.この関数のパラメータnextは空にできません.nextの前にnノードを追加しました.関数の実現はリスト中の対応関数と類似している.#define HLIST_HEAD_INIT { .first = NULL }
#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)static inline void hlist_add_before(struct hlistuunode*n,struct hlistement){n->pprev=next->pprev;n->next=next;next->pprev=&n->next;*(n->pprev)=n;entry(ptr,type,member)container_of(ptr,type,member)
萼define hlist_for_each(pos,head)/
for(pos=(head)->first;pos&({prefetch(pos->next);/
pos=pos->next)
 
 原文の住所http://blog.chinaunix.net/u/12592/showart.php?id=451619