jemallocを読んでみる(その6)

今日のまとめ

jemallocではmix-inみたいな事をCでやっています

本題

今回はstruct arena_chunk_sのうち、赤黒木を実現する部分を見てみます。struct arena_chunk_sは、その5(http://d.hatena.ne.jp/miura1729/20080407/1207556671)で説明した、struct arena_sのメンバーのchunksを実現する構造体です。
struct arena_chunk_sのメンバーは、大きく赤黒木を実現するためのメンバーとその他のメンバーに分かれます。

赤黒木を実現するためのメンバーの宣言は以下の通りです。

	/* Linkage for the arena's chunk tree. */
	RB_ENTRY(arena_chunk_s) link;

一見わけが分からない書き方ですが、RB_ENTRYがマクロだと分かると解読の手がかりが得られます。RB_ENTRYはjemalloc.cでは無く、tree.hで定義されています。RB_ENTRYの定義は以下の通りです。

#define RB_ENTRY(type)							\
struct {								\
	struct type *rbe_left;		/* left element */		\
	struct type *rbe_right;		/* right element */		\
	struct type *rbe_parent;	/* parent element */		\
	int rbe_color;			/* node color */		\
}

結局、RB_ENTRY(型)とすると、その型の赤黒木を実現するデータ構造の構造体の宣言に置き換えられます。使う人は赤黒木がどういった構造か知らなくてもRB_ENTRY(型) link;とメンバーに加えることで、赤黒木のデータ構造が定義できてしまいます。もちろん、データ構造が定義できただけで、万事OKとなるほど甘くないです。例えば、赤黒木の操作(挿入、削除など)も定義する必要があります。これらも、型を渡すと操作を行う関数を定義するマクロが用意されていますが、これは次回にしたいと思います。

このように、すでにある構造体にRB_ENTRYマクロを加えることで、赤黒木になってしまうのはmix-inを連想したのですが、ちょっと違うような気もします。いずれにしても美しいと思います。実際まねしようとするとはまりそうですが・・・。

赤黒木についてはこのページが分かりやすいと思います。
http://www.geocities.jp/h2fujimura/mutter/tree/red-black-tree.html

つづく