※ このエントリーは、VOYAGE GROUPエンジニアblog Advent Calendarの12/21分です。
こんにちは、VGエンジニアのポール（@pank7）です。
こんにちは、VGエンジニアのポール（@pank7）です。
多分知ってる人はいらっしゃいますが、半年前にvgtechブログを書いた際にはまだ日本語がまだダメなので、英語で書きました。今回はできるだけ頑張って日本語で書きます。ご指導よろしくお願いいたします。
何を書きますか
何を書きますか
私が書ける言語はそんな多くないですけど、普段自分が好きな言語だといえば、C言語はその中の１つです。Cのメリットとしてはやはり多いと思います。シンプルや移植性が良いや効率的やUNIX系OSと仲良いなどというのがあります。でも今の仕事で使っている言語のPHP、Perl、Python、Shellとかと比べて、正直なところ面倒なデメリットも少なくないと思われています。標準のライブラリーが少ないや標準のデータ構造が弱いやメモリー管理地獄や指針が危険などもいろいろあります。好きな言語なのに、残念ながら、社会人になって職場では一回使ったこともありません。
先ほど言った通りに、C言語のデメリットの１つは標準のデータ構造は確かに弱すぎると自分も強く感じています。PHPやPythonならば、配列（list）や連想配列（map）や集合（set）やソート関数などの基本的に必要なものは必ず提供されていますが、C++でもSTLにいろいろ入っています（そんなに使いやすくもないですけど）。何で私が好きなC言語では何も無いんですか(；´Д｀)？！使う際には真っ白から作らなければいけないんですか？という気持ちがどんどん強くなってきて、では、良いコードを探して参考して、自分のライブラリーを暇な時に作らないのと思い始めました。
今回は中途半端に作ったものをみんなに見せて、指摘をいただきくために、ブログを書いてみることにしました。ぜひ興味のある方はご指導よろしくお願いいたします。
先ず考えなければいけないことは、良いコードはなんですか？誰の何のコードを参考すればいいですか？違う人の標準は多分異なっていますが、自分のスタンダードからすると、一つ目は多くのところでよく使われているこどです。使われているC言語だと考えたら、Linuxのカーネルはやはり良い選択肢ですね。そういうふうに思いながら、Linuxカーネルのコード少し探しました。結果として、予想どおりいつくかが出てきました。
linux/include/linux/list.h
これはLinuxカーネルでどこでも使ってリンクリスト（linked list）です。それをぐぐるすれば、概論的な文章はいっぱい出てきます。またコードを読むと、使い方もシンプルで、struct list_headというデータ構造を自分のデータ構造に埋め込んで、いくつかのマクロと関数で、どのタイプのデータもリンクリストとして使えるようになれます。
初めて知った際に、面白いと思っていたコードは下３つのマクロです
#ifndef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE, MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif
#endif /* offsetof */
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
0を自分のタイプのアドレスにキャストして、構造体のアドレスからlist_headメンバーまでの距離が分かれます。それで、list_headメンバーのアドレスから構造体のアドレスを推測できています。
linux/include/linux/rbtree.h
これはLinuxカーネルの汎用の赤黒木（red-black tree）のデータ構造とアルゴリズムです。これもネット上では紹介文が多いと思います。デザインのせいで、list.hと比べて少し使いにくいですけど、メリットとしては、メモリの使用は非常に効率です。下のはrbtree.hの基本的なデータ構造で、使い方もlist_headと一緒で、自分のデータ構造に埋め込んで（こちらでもcontainer_ofマクロが使われてる）から、関数を呼ぶことだけです。
struct rb_node
{
unsigned long rb_parent_color;
#define RB_RED 0
#define RB_BLACK 1
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
赤黒木の節点では色が付いていますが、この構造を見ると、rb_parent_colorメンバーのこの名前がおかしくないですか？原因は”__attribute__((aligned(sizeof(long))));”のせいで、この構造体のアドレスは必ず8（64ビットX86のCPUなら）の倍数になるので、アドレスの一番右からの3つのビットは絶対0になります。それで、一番右にビットを節点の色として使うことなるので、rb_parent_colorという名前になりました。
linux/include/linux/sort.h
これはLinuxカーネルの汎用のソート関数です。アルゴリズム的には普通のヒープソートですから、時間計算量はO(n log n)です。インターフェース関数を見ればわかります。
void
sort (void *base, unsigned int *index, size_t num, size_t size,
int (*cmp) (const void *, const void *),
void (*swap) (void *, void *, int size));
用意する必要なのもはデータの比較関数とデータの取り替え関数だけです。
自分が何を少しやったかというと（https://github.com/pank7/pank7-lib）
1、上の３つの部分のコードを切り出して、Linuxカーネルコードの外でもC++でも使える形にしました
2、そして、intタイプのスタック（int_stack_type）と双方向キュー（int_queue_type）と集合（int_set_type）、この3つの基本的なデータ構造のサンプルコードを書いたことです。
- int_stack_type: https://github.com/pank7/pank7-lib/blob/master/int_stack.h
- スタックですから、プッシュ、ポップ、ヘッドと空判定関数があります。
- int_queue_type: https://github.com/pank7/pank7-lib/blob/master/int_queue.h
- 双方向キューでは両頭でもプッシュ、ポップできます。
- 双方向キューでは両頭でもプッシュ、ポップできます。
- int_set_type: https://github.com/pank7/pank7-lib/blob/master/int_set.h
- 集合ですから、存在判定とインサートとリムーブ関数しかありません。
- 集合ですから、存在判定とインサートとリムーブ関数しかありません。
テスト用の使い方を表すサンプルコードもいくつかがあります。中途半端なのも、多分完璧ではありませんが、ぜひC言語を書いてる方や興味のある方は使ってみれば嬉しいです、ご指摘よろしくお願いいたします。
終わりに
- linux/include/linuxの下に他の良いデータ構造とアルゴリズムでもいっぱいあります…
- 他の強い言語でよく使われてる基本的なデータ構造はそれだけではないんですけど、伝えたいこととしては、C言語でも使いやすいデータ構造は多くあるので、C言語のデメリットを改善して、メリットがちゃんと発揮できるということです。では、今回はここまでです。
次回予告
次回のAdvent Calendar担当は@_zooです。
