hlist


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

最終更新 2014/03/27 19:15:01 - north
(2014/03/27 19:15:01 作成)


検索

アクセス数
3574950
最近のコメント
コアダンプファイル - sakaia
list_head構造体 - yocto_no_yomikata
勧告ロックと強制ロック - wataash
LKMからのファイル出力 - 重松 宏昌
kprobe - ななし
ksetの実装 - スーパーコピー
カーネルスレッドとは - ノース
カーネルスレッドとは - nbyst
asmlinkageってなに? - ノース
asmlinkageってなに? - よろしく
Adsense
広告情報が設定されていません。