Linuxカーネルのコードを読んでて、なるほど〜と思うことはよくあるけど、その中でも特に今までの考え方をぶち壊してくれたのはなんだっけと思ったところ、やっぱりリスト構造かなと言うところ。
c言語でリスト構造を作る場合、一般的な教科書方式だと↓のようにデータとnextポインタは密結合になってると思います。これの場合、struct foobarのポインタをnext要素に使っているので、他の構造体(例えば、struct hogehoge)で同じことをしようとすると、その構造体ではstruct hogehoge *nextというメンバ変数を持つ必要があります。 ヘッド要素はstruct foobarです。
struct foobar { int n; char s[64]; struct foobar *next; }; struct foobar head;
Linuxカーネルの場合、データとリスト構造の管理が別になっていて、リストはstruct list_headとして独立しているんですよね。
185 struct list_head { 186 struct list_head *next, *prev; 187 };
これのおかげで、リストの管理をデータに非依存で行えるようになってます。
さきのstruct foobarにstruct list_headを適用するとこのようになって、ヘッド要素はstruct list_headになります。
struct foobar { int n; char s[64]; struct list_head *next; }; struct list_head head;
struct list_headを使うと、データのリンクはstruct list_headを使って行うので、このようになります。
データはstruct list_headのnext変数でつながってる感じです。なので、リストを辿る場合はnext変数(双方向リストならprevも)を辿っていきます。struct list_headはprevとnextを持っていて、list_addマクロで登録するときはprev、nextともに設定されます。 では、データにはどうやってアクセスするのか?なると、container_ofマクロを使用します。
823 #define container_of(ptr, type, member) ({ \ 824 const typeof( ((type *)0)->member ) *__mptr = (ptr); \ 825 (type *)( (char *)__mptr - offsetof(type,member) );})
それと、offsetofマクロも必要です。こちらはコンパイラがoffsetofの機能をサポートしていればそれを使うようになってます。機能的には構造体のメンバ変数「MEMBER」が構造体の先頭から何バイト目にあるかを取得するものです。
14 #undef offsetof 15 #ifdef __compiler_offsetof 16 #define offsetof(TYPE, MEMBER) __compiler_offsetof(TYPE, MEMBER) 17 #else 18 #define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER) 19 #endif
この辺は、Linux: inodeからtask_struct構造体を取得 - φ(・・*)ゞ ウーン カーネルとか弄ったりのメモで説明したりしてます。ようは、メモリ上にある構造体のメンバ変数のアドレスから、そのメンバ変数の構造体先頭からのオフセットを引けば、その構造体の先頭アドレスが取得できるという感じです。これにより、struct list_head構造体とデータを粗結合にすることができています。
一般的なリスト構造だとデータとリストが密に結合していたのに、Linuxカーネルの場合はそのへんが上手く抽象化されてて、勉強になったなと思ったわけです。 といっても、これはoffsetofとかcontainer_ofといったテクニックがあった上での実装方法なので、初学者向けではないと思いますが。でも、データとリストを別に管理するという方法は良いですよね。
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆
- 出版社/メーカー: マイナビ出版
- 発売日: 2015/01/30
- メディア: Kindle版
- この商品を含むブログを見る