Linux KernelのLinked Listの実装が面白い件

最近、Robert Love先生の本を暇な時にダラーと読んでいたりするわけですが、それの中にLinux Kernel内部で使われているLinked Listの実装が書いてあって面白かったので共有。

まず、Linked Listの一個一個のエントリを表すstructを定義します。

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

いやいやいやいや。いかにC力の低い僕でも流石にこれはあきません。騙されませんよ。前後のエントリへのポインタは確かにあるけれども、これにはデータを指すためのポインタがないじゃないの。おじいちゃんまたデータ忘れてきちゃったの？いやあねえ。

おじいちゃんは言った。「それはお前の短見というものじゃ。このLinked Listは以下のコードのようにデータ構造に埋め込んで使うものなんじゃよ。」そしてそれは正しかった。

struct item {
    int value;
    struct list_head list;
};

そっかー！Linked Listのエントリーの中にデータを持つんじゃなくて、データ構造の中にLinked Listを埋め込むという逆転の発想なんだね！やったねおじいちゃん！これで万事解決だ。

...いやいやいや騙されないぞ。これだと、item1->list->next->next ... って辿っていっても見つかるのはlist_headへのポインタだけで、永遠にstruct itemに辿りつけないじゃないか！やっぱり僕らのおじいちゃんはボケていたのか？

おじいちゃん「list_entry」孫「え？」おじいちゃん「container_of」孫「」

/**
 * list_entry - get the struct for this entry
 * @ptr:    the &struct list_head pointer.
 * @type:   the type of the struct this is embedded in.
 * @member: the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

/*
 * 'kernel.h' contains some often-used function prototypes etc
 */
#define container_of(ptr, type, member) ({              \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})


＿人人 人人人人人＿
＞ 突然の黒魔術 ＜
￣Y^Y^Y^Y^Y^Y^Y￣