Rev.1を表示中。最新版はこちら。

hlistは、ハッシュ下の同じハッシュキーのノードリスト管理に特化したリスト構造で、コンセプトはlist構造体と同じですが、ノードのprevをダブルポインタとしています。

ハッシュは同じハッシュキーとなるノード群が発生します。この同一ノード群を配列のハッシュテーブルにリストするため、ハッシュテーブルサイズに応じたリストヘッドで管理します。
多くのヘッドサイズ故、サイズを小さくする必要があります。そのためlistヘッドと異なりprevを排除しています。これはヘッドからtailを辿って走査することはできませんが、ハッシュリストの運用上問題ないはずです。

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

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

void __init inode_init_early(void)
{
       unsigned int loop;

       if (hashdist)
               return;

       inode_hashtable =
               alloc_large_system_hash("Inode-cache",
                                       sizeof(struct hlist_head),
                                       ihash_entries,
                                       14,
                                       HASH_EARLY,
                                       &i_hash_shift,
                                       &i_hash_mask,
                                       0);

       for (loop = 0; loop < (1U << i_hash_shift); loop++)
               INIT_HLIST_HEAD(&inode_hashtable[loop]);
}

従って、ヘッドとノードの構造体が異なることになります。list構造体では両者にかかる処理でもこの違いを考慮する必要はありませんが、hlistでは、あるノードの前にノードを挿入する場合、ノードの前がヘッドかノードかによって、属する構造体が異なることになります。

この違いを意識しなくてもいいように、hlistのノードのpprevはダブルポインタとしているわけです。n->pprevはヘッドかノードかのポインタを指していて、どちらかを指していようが関係なく、そこにノードのnを設定すればいいわけです。もしポインタとすればそれがヘッドかノードかを考慮し、キャストした後first/prevに設定しなければなりません。

struct hlist_head {
       struct hlist_node *first;
};

struct hlist_node {
       struct hlist_node *next, **pprev;
};

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