※　このエントリーは、VOYAGE GROUPエンジニアblog Advent Calendarの12/21分です。

こんにちは、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つの基本的なデータ構造のサンプルコードを書いたことです。


テスト用の使い方を表すサンプルコードもいくつかがあります。中途半端なのも、多分完璧ではありませんが、ぜひC言語を書いてる方や興味のある方は使ってみれば嬉しいです、ご指摘よろしくお願いいたします。

終わりに

  • linux/include/linuxの下に他の良いデータ構造とアルゴリズムでもいっぱいあります…
  • 他の強い言語でよく使われてる基本的なデータ構造はそれだけではないんですけど、伝えたいこととしては、C言語でも使いやすいデータ構造は多くあるので、C言語のデメリットを改善して、メリットがちゃんと発揮できるということです。では、今回はここまでです。

次回予告

次回のAdvent Calendar担当は@_zooです。