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

今日のまとめ

　tree.hはjemallocとは独立したライブラリです。ちょっと癖がありますが(それはCのせいでtree.hのせいじゃないのですが)、なかなか便利そうです。

追記
調べてみたら*BSDには標準で(/usr/include/sysに)tree.hは入っているみたいです。*BSD恐るべし！！

本題

　よく見るとtree.hはJason Evansさんではなく、Niels Provosさんが作者でした。そしてjemallocと同様にBSDライセンスで再配布の際にはコピーライトを明示するという条件のようなので、コピーライトを載せておきます。

/*-
 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

そういうことで、tree.hはjemallocのために書いたものじゃなくて独立したライブラリだったみたいです。jemallocでのtree.hの使い方を見てみます。なお、jemallocでは赤黒木しか使っていませんが、RB_の代わりにSPLAY_に置き換えることでSPLAY木版に出来ます。

struct ノード構造体名 {
	RB_ENTRY(ノード構造体名) link;

しつこいようですが、これでノード構造体を宣言します。例えば、整数型の赤黒木は

struct inode_s {
       RB_ENTRY(itree_s) link;
       int data;
};

とすればいいのではないかと思います。

RB_HEAD(木構造体名, ノード構造体名);

これで、木全体のデータ構造を宣言します。現状では、赤黒木、SPLAY木どちらも、ルートノードへのポインタだけをメンバーに持つ構造体を宣言しています。

RB_INIT(木のポインタ);

RB_HEADで宣言した木構造体型の変数の初期化を行います。

RB_INSERT(木構造体名, 木のポインタ, ノードへのポインタ);

木にノードを挿入します。

RB_FOREACH(変数, 木構造体名, 木のポインタ) {
  処理
}

変数に木のノードを代入して処理を行います。木全体を走査するイテレータです。

ほかにも、ノードを削除したり、ノードを検索したりすることも出来ますがめんどくさくなったので省略します。整数型のRB木を定義したサンプルを作りました。0から99までのノードを作って、表示するだけです。

#include <stdio.h>
#include <stdlib.h>
#include "tree.h"

struct inode_s {
  RB_ENTRY(inode_s) link;
  int data;
};

RB_HEAD(itree_s, inode_s);

static inline int
cmp(struct inode_s *a, struct inode_s *b)
{
	return ((a->data > b->data) - (a->data < b->data));
}

RB_GENERATE(itree_s, inode_s, link, cmp);

main(void)
{
  int i;
  struct itree_s foo;
  struct inode_s *node, *nd;

  RB_INIT(&foo);
  
  for(i = 0; i < 100; i++) {
    node = malloc(sizeof(struct inode_s));
    node->data = i;
    RB_INSERT(itree_s, &foo, node);
  }

  RB_FOREACH(nd, itree_s, &foo) {
    printf("%d ", nd->data);
  }
}

  

ライセンスに要注意ですが、バグの温床になりがちな木構造が手軽に作れるのでなかなか重宝じゃないかなと思います。

つづく