libgit2の内部データ構造: strmap

libgit2の内部ではハッシュテーブルが使われていたりしますが、C言語標準ライブラリにはハッシュテーブルはありません。ここで公開されている外部のライブラリkhash.hをラップして作られています。コードリーディングメモです。

khashとは何か

MITライセンスですが、著者はプロフィールを隠しています。

このブログはanonymousなブログだ ... 
俺は完璧主義者だ。もし、読者がこのブログを書いている私を知っているなら、
私は出来る限りすべてを完璧にし続けたいと思うだろう。
それは私を神経質にして、何を書くにしても疲れ果ててしまうだろう。
もし読者が私が誰かを知らないのであれば、自分を解放することができて、
心が赴くままに書き続けられるだろう。 (意訳)

こういう厨二病な感じ、嫌いじゃないです。とはいえ、ちょっと古いですがここのエントリーに書かれているベンチマークの結果を見ると、トップクラスに高速で、メモリ使用量もトップクラスに少ない高性能なライブラリであることが分かります。

Library	Mac-intCPU (sec)	Mac-strCPU (sec)	Mac PeakMem (MB)	Linux-intCPU (sec)	Linux-strCPU (sec)	Linux PeakMem (MB)
glib	1.904	2.436	11.192	3.490	4.720	24.968
ghthash	2.593	2.869	29.0/39.0	3.260	3.460	61.232
CC’s hashtable	2.740	3.424	59.756	3.040	4.050	129.020
TR1	1.371	2.571	16.140	1.750	3.300	28.648
STL hash_set	1.631	2.698	14.592	2.070	3.430	25.764
google-sparse	2.957	6.098	4.800	2.560	6.930	5.42/8.54
google-dense	0.700	2.833	24.616	0.550	2.820	24.7/49.3
khash (C++)	1.089	2.372	6.772	1.100	2.900	6.88/13.1
khash (C)	0.987	2.294	6.780	1.140	2.940	6.91/13.1
STL set (RB)	5.898	12.978	19.868	7.840	18.620	29.388
kbtree (C)	3.080	13.413	3.268	4.260	17.620	4.86/9.59
NP’s splaytree	8.455	23.369	8.936	11.180	27.610	19.024

ブログのやつは少しバージョンが古く、最新のものはgithub上にあります。libgit2もこちらのバージョンを使っています。

内部はC言語のマクロを駆使して書かれています。.cはなく、ヘッダファイルのみのライブラリです。マクロを使っているからといって見にくいコードというわけではなく、型の柔軟性を持たせるというC++のテンプレートっぽいことをさせたいだけに見えます。実際にC++の文字列で使えるかは試してませんが、以下の宣言がほぼ等価です。

typedef std::map<int, std::string> > ZipTable;

KHASH_DECLARE(ZipTable, int, std::string)

KHASH_DECLAREを呼ぶと、構造体などが作られます。最初のパラメータが名前で、この名前の数だけ型が作られます。同じ型ごとにいくつもインスタンスは作れますが、かならずすべてのマクロの引数の先頭にこれを入れます。

khash_t(ZipTable) *h = kh_init(ZipTable);

こんな感じです。値の挿入や参照は直接ハッシュに格納するのではなく、一度イテレータを取得してから入れるスタイルです。

int ret;
// イテレータ型
khiter_t k;

// 値の挿入もイテレータを取ってきてから
k = kh_put(ZipTable, h, 1508510, &ret);
kh_value(h, k) = "渋谷ヒカリエ";

// 値の参照もイテレータ経由
k = kh_get(ZipTable, h, 1508510);

他にも、存在チェック、クリア、格納されている要素を参照する外部イテレータなど、よくある機能は網羅されているようです。また、キーの同一性比較の関数を入れ替える初期化宣言などもあり、C言語では == で比較できない文字列をキーに入れることもできるようになっています。

libgit2での使い方

KHASH_DECLARE が内部で呼んでいるマクロをばらして以下のように呼んでいます。名前はstr、キーはconst char*、値は void * です。

__KHASH_TYPE(str, const char *, void *)
__KHASH_IMPL(str, static kh_inline, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal)

libgit2ではkhashのAPIはすべての内部に押し込められていて、外に露出はしていません。

#define git_strmap_lookup_index(h, k)  kh_get(str, h, k) 

とはいえ、マクロを使った薄いラッパーなので、困ったらkhash.hを読めばなんとかなりそうです。

これはlibgit2の内部APIなので、libgit2を使うユーザはこのあたりを知る必要はありません。