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ï¿£

おじいちゃん「めんどうくさいから説明は省くが、構造体のメンバーのアドレスと構造体の型宣言と構造体のメンバーの名前を渡せば構造体そのもののアドレスを返してくれるマクロがあるんじゃよ」孫「えー」

＿人人＿
＞ 完 ＜
ï¿£Y^Y^ï¿£

しかしよくこんなの思いつくなー

Linux Kernel Development (Developer's Library)