赤黒木

(後々の正規表現ライブラリ改善のため)組み込みの文字セットを入れようと考えているのだが、ハッシュテーブルをセットとしてもつより、平衡二分木を持った方がメモリ効率的にいいかなぁと思い、赤黒木を調べ中。(長い)

調べてみると、実装が難儀とあって、LLRBなるものを発見。Javaで200行程度で実装できるらしい。とりあえずこいつを実装して、後から実装を変更するのもありか。
となると、他の二分木も実装(AVL木とか)も試してみたくなるよなぁと思うのが人間で、そうするとインターフェースだけ定義して実装は別にしたい。何を持つべきだろう？
正直、どこまでやるかということになるが、一応Schemeからも実装できるようにしたいなぁと思うと以下のようになるだろうか？

typedef struct tree_map_rec
{
  int type; /* CかSchemeか*/
  union {
    struct {
      int (*insert)(struct tree_map_rec *tree, node_t *node);
      /* so on */
    } c_procs;
    struct {
      /* scheme procs on C object*/
    } scheme_procs;
  } impl;
} tree_map;

問題になりそうなのはnode_tの定義か？まぁ、とりあえずintptr_tの別名にして、実装毎に適当に定義してキャストすればOKだろうか？
あとは、実装ごとにイテレータをどう用意するかとかその辺を煮詰めないとなぁ。この辺C++だともう少し簡単に書けそうだよなぁ。ABIの問題さえなければ・・・