今日も重複排除機能を引き続き実装していきます。そろそろ src/main.c にすべての実装を書くのがつらくなってきたので，ファイルを分けます。

• src/main.c: メインルーチンなど
• src/ramblock.c: ブロックデバイスの操作

昨日説明した通り，ブロックの重複検出はSHA-384のハッシュ値により行います。このハッシュ値の重複を高速に探索するために，ハッシュをキーとした二分木によりブロックを管理します。もちろん赤黒木などのバランス木やブロックデバイスに最適化されたB-Tree系のアルゴリズムの方が良いのですが，赤黒木からのノードの削除は何度やってもはまる気しかしないので今回は普通の二分木で実装します。

二分木の探索は _block_search() として実装します。第1引数には advfs_t 構造体へのポインタ，第2引数には検索対象のハッシュ値を指定します。二分木の探索は再帰関数として実装すると簡単なため，ルートから再帰的に木を辿る _block_search_rec() 関数を以下のように実装します。単純な二分木なので，ハッシュの値を比較して，一致していればそのノード，検索対象のハッシュ値が小さければ左のサブツリー，大きければ右のサブツリーを再帰的に探索します。

static uint64_t
_block_search_rec(advfs_t *advfs, uint64_t parent, const unsigned char *hash)
{
    int ret;
    advfs_block_mgt_t *mgt;

    mgt = _get_block_mgt(advfs, parent);

    /* Compare the hash value */
    ret = memcmp(mgt->hash, hash, sizeof(mgt->hash));
    if ( 0 == ret ) {
        /* Found */
        return parent;
    } else if ( ret < 0 ) {
        /* Search right */
        return _block_search_rec(advfs, mgt->right, hash);
    } else {
        /* Search left */
        return _block_search_rec(advfs, mgt->left, hash);
    }
}
static uint64_t
_block_search(advfs_t *advfs, const unsigned char *hash)
{
    uint64_t root;

    root = advfs->superblock->block_mgt_root;

    return _block_search_rec(advfs, root, hash);
}

二分木へのノードの挿入は _block_add() 関数として実装します。こちらも探索と同様に再帰関数として実装します。探索と違うのは，挿入場所は木構造の葉まで探索したときに該当ノードが見つからなかった場合に，この葉にノードを追加するため，親ノードからの参照をポインタとして渡すことで，挿入を容易にしています。この再帰関数は _block_add_rec() として以下の通り実装しま す。

static int
_block_add_rec(advfs_t *advfs, uint64_t *parent, uint64_t b)
{
    advfs_block_mgt_t *mgt;
    advfs_block_mgt_t *tmp;
    int ret;

    if ( *parent == 0 ) {
        *parent = b;
        return 0;
    }

    mgt = _get_block_mgt(advfs, *parent);
    tmp = _get_block_mgt(advfs, b);

    /* Compare the hash value */
    ret = memcmp(mgt->hash, tmp->hash, sizeof(mgt->hash));
    if ( 0 == ret ) {
        /* Hash value conflict */
        return -1;
    } else if ( ret < 0 ) {
        /* Search right */
        return _block_add_rec(advfs, &mgt->right, b);
    } else {
        /* Search left */
        return _block_add_rec(advfs, &mgt->left, b);
    }
}
static int
_block_add(advfs_t *advfs, uint64_t b)
{
    return _block_add_rec(advfs, &advfs->superblock->block_mgt_root, b);
}

二分木からのノードの削除は多少複雑です。と言っても普通の二分木なので，コード量も大きくはなりません。こちらもこれまでの探索・追加と同様に再帰関数として実装します。まず，二分木からブロック番号 b を削除するための関数 _block_delete() を以下のように実装します。この関数から再帰関数 _block_delete_rec() を呼び出します。

static int
_block_delete(advfs_t *advfs, uint64_t b)
{
    return _block_delete_rec(advfs, &advfs->superblock->block_mgt_root, b);
}

_block_delete_rec() の実装は以下の通りです。追加のときと同様に，削除した後にノードの再配置（中間のノードを削除した場合にサブツリーを再構成）するため，木構造を辿るときの現在ノードを示す第2引数のブロック番号はポインタとして渡します。現在のノードが第3引数で指定されたブロックと一致する場合，このノードの木構造からの削除を実施します。現在のノードと第3引数が一致しない場合は，探索と同様，ハッシュ値を元に削除対象ノードを探索します。

削除対象のノードの子が高々1のときは非常に単純で，存在する子ノードのブロック番号（子が存在しない場合はノードが存在しないことを表す 0）を現在のノードまで引き上げます。つまり， *parent に子ノードのブロック番号を代入します。

static int
_block_delete_rec(advfs_t *advfs, uint64_t *parent, uint64_t b)
{
    advfs_block_mgt_t *mgt;
    advfs_block_mgt_t *tmp;
    uint64_t maxc;
    int ret;

    if ( *parent == 0 ) {
        /* Not found */
        return -1;
    }

    if ( *parent == b ) {
        /* Found, then pull one of the children of the  */
        mgt = _get_block_mgt(advfs, b);
        if ( 0 != mgt->left && 0 != mgt->right ) {
            /* Both children */
            maxc = _block_remove_max(advfs, &mgt->left);
            *parent = maxc;
            tmp = _get_block_mgt(advfs, maxc);
            tmp->left = mgt->left;
            tmp->right = mgt->right;
        } else if ( 0 != mgt->left ) {
            /* Only left child */
            *parent = mgt->left;
        } else if ( 0 != mgt->left ) {
            *parent = mgt->right;
        } else {
            /* No children */
            *parent = 0;
        }

        return 0;
    } else {
        mgt = _get_block_mgt(advfs, *parent);
        tmp = _get_block_mgt(advfs, b);
        ret = memcmp(mgt->hash, tmp->hash, sizeof(mgt->hash));
        if ( ret < 0 ) {
            /* Right */
            return _block_delete_rec(advfs, &mgt->right, b);
        } else if ( ret > 0 ) {
            /* Left */
            return _block_delete_rec(advfs, &mgt->left, b);
        } else {
            /* Found the hash but not the same block number */
            return -1;
        }
    }
}

両方の子ノードが存在する場合が少し複雑ですが，原理を説明すれば簡単に実装できると思います。子ノードが両方とも存在する場合は，左のサブツリーの最大，つまりサブツリーの右の子を辿って見つかるノードをこのサブツリーから削除し，このノードを削除対象のノードと入れ替えます。左のサブツリーの最大であるため，左のサブツリーのどのノードよりも大きく，かつ右のサブツリーのどのノードよりも小さいことが担保されているため，この入れ替え操作で木構造の再構築ができます。このサブツリーの最大ノードを探索して削除する関数を _block_remove_max() として実装し， _block_delete_rec() から呼んでいます。

static uint64_t
_block_remove_max(advfs_t *advfs, uint64_t *parent)
{
    advfs_block_mgt_t *mgt;
    uint64_t maxc;

    mgt = _get_block_mgt(advfs, *parent);
    while ( 0 != mgt->right ) {
        parent = &mgt->right;
        mgt = _get_block_mgt(advfs, *parent);
    }

    maxc = *parent;
    if ( 0 != mgt->left ) {
        *parent = mgt->left;
    }

    return maxc;
}

今日はブロックのハッシュ値を管理する構造体をハッシュ値をキーとした木構造として実装することで，ハッシュ値に対応する（つまり重複する）ブロックを高速に（O(log(n))で）探索できるように，木構造に対する操作関数を実装しました。明日は引き続き重複排除の実装を進めていきます。