カーネルの赤黒木

linux

自分エントリを探してみたら setitimer 云々で以下なエントリを投入していた。

上記エントリによれば、kernel/itimer.c で云々なのか。do_setitimer 手続きの先頭で以下なローカル変数の定義がありますね。

	struct task_struct *tsk = current;
	struct hrtimer *timer;
	ktime_t expires;

ええと、struct hrtimer 型の定義は include/linux/hrtimer.h で以下。

 *
 * The hrtimer structure must be initialized by hrtimer_init()
 */
struct hrtimer {
	struct timerqueue_node		node;

struct timerqueue_node 型の定義は include/linux/timerqueue.h で以下。

struct timerqueue_node {
	struct rb_node node;
	ktime_t expires;
};

この struct rb_node 型が赤黒木のソレですね。ちなみに直下にこんな構造体宣言があります。

struct timerqueue_head {
	struct rb_root head;
	struct timerqueue_node *next;
};

あと、struct rb_node 型などの宣言は include/linux/rbtree.h で以下。

struct rb_node {
	unsigned long  __rb_parent_color;
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
    /* The alignment might seem pointless, but allegedly CRIS needs it */

struct rb_root {
	struct rb_node *rb_node;
};

つうか __rb_parent_color って何だば、って思ったらこの直下に以下なマクロ定義がありました。

#define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))

わはは的。これ ruby とか scheme でもナニされてるテクだな。ちなみに実装なんですが、lib/rbtree.c で一連のソレが定義されているようですが今は読むリキが無い。
つうか、左右を boolean で表現して色々と抽象化してる rui さんの scheme 実装は色々な意味で凄いなぁ、と思います。