Weston/Wayland入門④ wl_listとwl_container_of()

Weston/Wayland入門まとめ

Waylandにはリスト構造としてwl_listが用意されている。
このリスト構造は侵入型リンクリスト（intrusive linked list）と呼ばれるものでLinuxカーネルなどでも採用されている有名なリスト構造である。

しかし同じリンクリストであってもよく知られたC++のstd::listなどとは異なった特徴を持っており、構造をよく理解していないプログラマが間違った使い方でリストを破壊してしまうというのはWeston入門におけるもはや風物詩である。

そこで今回はwl_listの使用方法について解説していく。

リストのアイテム

wl_listはリストとして格納したいオブジェクトのフィールドとして埋め込むことで機能する。
そこで今回は以下の構造体をリストのアイテムとして扱う。

struct MyObj {
  int value;
  wl_list link;
};

なおwl_listは以下の通り自身のポインタを持つ構造体となっている。

struct wl_list {
	/** Previous list element */
	struct wl_list *prev;
	/** Next list element */
	struct wl_list *next;
};

リストの初期化

まずは空のリストを用意する。

  wl_list head;

コード中でheadを生成した段階ではwl_listは初期化されておらず、prevもnextも不定値となっている。

これに対してwl_list_init()を呼ぶことでリストを初期化する。初期化によってprev,nextは自身を指すことになる。

  wl_list_init(&head);

課題
linkのprevとnextが自身を指していること確認してみよう。
どのようなログを出力すれば確認できるだろうか。

リストの連結

新しくMyObjのインスタンスを作成しwl_list_insert()を用いてリストを連結してみよう。

  MyObj obj1 = MyObj{ 1 };
  wl_list_init(&obj1.link);

  wl_list_insert(&head, &obj1.link);

これによりリストは下図の構造となる。矢印が複雑になっているが要は「headのnextはobj1, obj1のnextはhead」という循環構造になっている。

課題
ログを出力し、上図のような構造になっていることを確認してみよう。

wl_listによるリストは常に循環することになる。初期化だけおこなったリストもよく見ると「headのnextはhead」という循環構造になっていることがわかるだろう。

wl_list_insert() 解説

wl_list_insert()の実装は以下のとおり。

WL_EXPORT void
wl_list_insert(struct wl_list *list, struct wl_list *elm)
{
	elm->prev = list;
	elm->next = list->next;
	list->next = elm;
	elm->next->prev = elm;
}

上記のリストにさらにobj2を追加してみよう。

  MyObj obj2 = MyObj{ 2 };
  wl_list_init(&obj2.link);

  wl_list_insert(&head, &obj2.link);

wl_list_insert(&head, &obj2.link);となっているのでheadとobj1の間にobj2が入る形になる。

wl_list_insert()のコードを一行ずつ追っていく形で確認してこう。

elm->prev = list

listがheadで、elmがobj2.linkである。
obj2.linkのprevがheadになる。（以降変更は赤線で示す）

elm->next = list->next

list->nextはobj1.linkである。

list->next = elm

head.nextをobj2.linkに設定する。

elm->next->prev = elm

elm->nextはobj1.linkである。つまりobj1.linkのprevがobj2.linkとなる。

これでリストへの挿入完了となる。

課題
wl_list_init(&obj2.link)を呼ばないままwl_list_insert(&head, &obj2.link)を実行したらどうなるだろうか。

wl_listの重大な特徴

ここまでで勘の良い人は察しているかも知れないがwl_listには重大な特徴がある。それは、

「1つのwl_listは１つのリストにしか参加できない」

ということである。

重要
wl_listがすでにリストに挿入されている場合には必ずwl_list_remove()でそのリストから取り除いてから、wl_list_insert()を呼ぶ必要がある。さもないとリストが破壊されてしまう。

Appendix Aにwl_listがリストに参加したまま別のリストに挿入しようとするとどうなるかを記載した。

wl_container_of()

さて今度は以下のことを考えてみる。

「headの次のアイテムのvalueが知りたい」

headの次のアイテムはhead.nextで取得できると思うかも知れないが、head.nextで取得できるのはobj2.linkであってobj2そのものではない。

どうすればobj2を取得してobj2.valueを参照できるだろうか？

wl_container_of()を使用することでこの問題を解決することができる。コード例を以下に示した。

        MyObj* head_next = wl_container_of(head.next, head_next, link);
        weston_log("head_next->value = %d\n", head_next->value);

なんとも不思議なコードである。今まさに定義しようとしている変数(head_next)が右辺に現れ、更に定義していないlinkという変数(?)も引数にある。

実はwl_container_ofは関数でなくマクロである。定義は以下の通り。

#define wl_container_of(ptr, sample, member)				\
	(__typeof__(sample))((char *)(ptr) -				\
			     offsetof(__typeof__(*sample), member))

この定義を適用するとwl_container_of(head.next, head_next, link)は

(MyObj*)((char*)(head.next) - offsetof(MyObj, link))

となる。offsetof()もマクロでoffsetof(型名, フィールド名)で指定したフィールドの型名インスタンスの先頭アドレスからのオフセットが取得できる。

よってhead.next(ここではobj2.link)のアドレスからlinkのオフセットアドレスを引くことでobj2のアドレスが取得できることになる。

wl_container_of()はフィールドアドレス、構造体型名、フィールド名の３つが分かれば利用できるため、wl_listに限らずWestonのコードにおいて広く利用されている。

課題
Westonのソースコード内でwl_list以外でwl_container_of()が使われている例を確認してみよう。

wl_list_for_each()

リストといえば、その要素全てに対して何らかの操作をすると言った反復処理（イテレーション）を頻繁におこなうことになる。C++標準ではfor文であってりstd::for_eachが用意されていたりするが、wl_listにも反復処理が用意されている。それがwl_list_for_each()である。

使い方は以下の通り

        MyObj* obj;
        wl_list_for_each(obj, &head, link) {
            weston_log("obj.value = %d\n", obj->value);
        }

wl_list_for_each()も実はマクロでありforに展開される。

#define wl_list_for_each(pos, head, member)				\
	for (pos = wl_container_of((head)->next, pos, member);	\
	     &pos->member != (head);					\
	     pos = wl_container_of(pos->member.next, pos, member))

課題
wl_listの反復処理にはwl_list_for_each_safe()というものも存在している。
違いについて説明してみよう。何がsafe(安全)なのだろうか。

Appendix

Appendix A. リスト参加中に他のリストに挿入しようとしたら？

[obj2,obj1]と[obj3]の２つのリストを考える。(下図)

obj2に対してwl_list_remove()しないまま、wl_list_insert(&head2, &obj2.link)したらどうなるか。

elm->prev = list

elm->next = list->next

list->next = elm

elm->next->prev = elm

ご覧のように２つのリストが混ざり合ってしまう結果となってしまった。

例えばheadからリスト辿っていくといつの間にか別のリストに入り込むという最悪の状況になることがわかるだろう。特にリストを一周したい場合などはheadから始めてheadに戻ってくるまでnextを辿っていくのだが、headに戻ることはないため無限ループになってしまうことがわかる。