list_head

struct list_headは、画期的な連結リストである。

通常とは全く異なる発想で作られており、このため、予備知識なしで眺めても理解が難しい。予備知識があっても解読が難しい。

具体的には次のように定義されている。

struct list_head{
   struct list_head *prev;
   struct list_head *next;
}

前と次へのポインターしかない。これでどうやって目的のデータを数珠繋ぎにするのか。それが、このstruct list_headの持つ、最大の特徴となる。

普通に連結リストを作ろうとしたなら、普通のプログラマーであれば前と次へのポインターの他に、実際のデータか、またはデータへのポインターを構造体の中に含めるだろう。

こうして、この管理用の構造体の中に繋ぎたいデータを「含む」ことで、データは数珠繋ぎの連結リストとなる。

しかしstruct list_headは違う。

簡単に説明すると、struct list_headは、リストとして繋ぎたい要素を「含む」のではなく、リストとして繋ぎたい要素に「埋め込む」のである。

繋ぎたい構造体の中に、struct list_headを埋め込む。

struct data_struct {
   int id;
   char name[128];
   struct list_head node;
}

通常の発想のものなら構造体の先頭ポインターで管理するところだが、struct list_headの場合は、構造体の中のどこかにあればよい。どこでも良い。

この場合、struct list_head nodeのアドレスがリストに追加されることになる。構造体の先頭アドレスではない。

一つのリストごとに一つ、ソース中のどこかに、先頭(head)に相当するstruct list_headを定義する必要がある。

複数の関数で使うことが多いため、一般にはグローバル変数として定義して用いる。また、定義のためのマクロも用意されている。data_listという名前で登録する場合、次のようになる。

LIST_HEAD(data_list);

この変数は、複数のソースファイルから参照できるようにヘッダーファイル中でextern定義することも多い。

extern struct list_head data_list;

ここで使われるマクロは、linux/list.hで、次のように定義される。

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
        struct list_head name = LIST_HEAD_INIT(name)

LIST_HEADでの定義時点で、prevとnextには先頭(head)それ自身が代入されることが分かる。nextを見て、そのポインターが先頭(head)なら、それ以降はないものとして判断できる。

構造体中のstruct list_headのアドレスから、その構造体の先頭アドレスを得るためのマクロlist_entryが定義されている。従って、struct list_headはどこにあってもよい。

登録するリストがstruct list_head data_list;として定義されているとすると、次のように使う。

struct list_head *ptr;
struct data_struct *entry;
for (ptr = data_list.next; ptr != &data_list; ptr = ptr->next) {
    entry = list_entry(ptr, struct data_struct, node);
    printf("%d\n", entry->id);
}

なお、無限ループしないように順番に見ていく場合は、次のマクロを使うのが便利である。

#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

実体はfor文だが、要素二つだけのマクロとなるため、読みやすくなる。こうなる。

struct list_head *ptr;
struct data_struct *entry;
list_for_each(ptr, &data_list) {
    entry = list_entry(ptr, struct data_struct, node);
    printf("%d\n", entry->id);
}

実際のコーディングでは、構造体の中に構造体がある、ということも珍しくはない。そして、実際にstruct list_headが挿入される構造体は、構造体の中の構造体の中、ということもよくある。

ということは、list_entryから自分の構造体が分かるとして、更にそれが入っている構造体の先頭アドレスを知る方法があるはずである。

Linuxのstruct list_head関連処理は非常にトリッキーな技術が多数使われているが、このためのマクロがcontainer_ofである。実際には、container_ofこそが定義の本体で、先に説明したlist_entryはその別名として定義されていることも多い。つまり、両者の機能は全く同じである。

container_ofの使い方は、list_entryと同様なのは言うまでも無いが、リストから取り出す箇所と、それ以外で使い分けると、見た目がよいのだと思われる。

ここでは、説明のために、外側の構造体をstruct outer_st、内側の構造体をstruct inner_stとし、struct list_headは内側にあるものとする。

struct inner_st {
    int indata;
    struct list_head node;
};
struct outer_st {
    int outdata;
    struct inner_st sin;
};

この時、リストからstruct outer_stの要素を取り出すまでは、次のようにする。

struct list_head *p;
struct inner_st *pin;
struct outer_st *pout;
list_for_each(p, &list)
{
    pin = list_entry(p, struct inner_st, node);
    pout = container_of(pin, struct outer_st, sin);
    if (pout->outdata == 123)
    {
        /* 処理 */
    }
}

リスト中で関連付けられている中から、outer_st.outdata==123の要素を抽出する処理も、このように書くことができる。