Zig言語用コンテナライブラリ llrbtree-zig を実装しました - ::Eldesh a b = LEFT a

序

Zig 言語の標準ライブラリにはジェネリックなキーバリューコンテナが含まれません。
このためZig言語用に Red-Black treeを用いた(当然ジェネリックな)コンテナライブラリ GitHub - eldesh/llrbtree-zig: A container library with llrbtree written in Zig. を実装しました。

順序の付いた値の集合である LLRBTreeSet(T) と、順序の付いたキーに値を紐付ける LLRTTreeMap(K,V) を提供します。

アルゴリズム

このライブラリはRed-Black tree(RB tree)の中でもinvariantをより強くした Left-Leaning Red-Black tree(LLRB tree)を実装しています。

RB treeでは 3-node に対応するノードの構成が二つ存在するのに対して、LLRB tree では一つ(左傾版)に正規化されます。

アルゴリズムの作者である Robert Sedgewick は分岐が少なるため速くなると主張していますが、多分それほど変わらないと思います。気分です。(あと、著者の実装はバグっています。)

LLRB tree は RB tree なので計算量はそれに倣います。つまり検索、挿入、破棄はそれぞれノード数 n に対して O(log n) です。

使い方

このライブラリの使い方は Rust の BTreeSet/Map におおよそ準拠します。

ただし、削除されたエントリなどは caller 側(の変数)に所有権が戻るので明示的に削除する必要があります。

Set of u32

u32 の集合を使用する例を示します。

var set = llrbtree.llrbset.LLRBTreeSet(u32).new(alloc, .{});
defer set.destroy();
// 値を追加するには insert 関数を使います。
// 同じ値が存在する場合は、古い値が返値として返されます。
_ = try set.insert(5);
// 古い値である 5 が返されます。
assert((try set.insert(5)).? == 5);
assert((try set.insert(7)) == null);

// 集合から値を検索するには `get` 関数を使います。
// 存在しない場合は `null` が返ります。
assert(set.get(&@as(u32, 5)).?.* == 5);
assert(set.get(&@as(u32, 10)) == null);

// 値を削除するには `delete` 関数を使います。
// 削除された値が戻り値として返されます。
assert(set.delete(&@as(u32, 5)).? == 5);
// '5' は既に削除されています。
assert(set.delete(&@as(u32, 5)) == null);

_ = try set.insert(5);
_ = try set.insert(9);
// イテレータは値を昇順で列挙します
var items = set.to_iter();
assert(items.next().?.* == 5);
assert(items.next().?.* == 7);
assert(items.next().?.* == 9);

Map of u32 → []u8

キーとして u32、値として []u8 を使用する場合を以下に示します。

var map = llrbtree.llrbmap.LLRBTreeMap(u32, []u8).new(alloc, .{});
defer map.destroy();
// key/value ペアを追加するには `insert` 関数を使います。
// 既に同じキーについて値が存在する場合は古い値が返されます。
_ = try map.insert(5, try alloc.dupe(u8, "25"));

// 古い値である "25" が返されます。
var old = (try map.insert(5, try alloc.dupe(u8, "20"))).?;
defer alloc.free(old);
assert(mem.eql(u8, old, "25"));
assert((try map.insert(7, try alloc.dupe(u8, "28"))) == null);

// あるキーに紐付いた値を検索するには `get` 関数を使います。
// 値が紐付けられていない場合は `null` が返されます。
assert(mem.eql(u8, map.get(&@as(u32, 5)).?.*, "20"));
assert(map.get(&@as(u32, 10)) == null);

// エントリを削除するには `delete` 関数を使います。
// そのキーに紐付けされた値が返されます。
var deleted = map.delete(&@as(u32, 5)).?;
defer alloc.free(deleted);
assert(mem.eql(u8, deleted, "20"));
// '5' に紐付けされた値は既に削除されています。
assert(map.delete(&@as(u32, 5)) == null);

_ = try map.insert(5, try alloc.dupe(u8, "20"));
_ = try map.insert(9, try alloc.dupe(u8, "36"));
// イテレータはキーの昇順でエントリを列挙します。
var kvs = map.to_iter();
var k0 = kvs.next().?;
assert(k0.key().* == 5 and mem.eql(u8, k0.value().*, "20"));
var k1 = kvs.next().?;
assert(k1.key().* == 7 and mem.eql(u8, k1.value().*, "28"));
var k2 = kvs.next().?;
assert(k2.key().* == 9 and mem.eql(u8, k2.value().*, "36"));

イテレータ

上の例で使用しているイテレータは GitHub - eldesh/iter-zig: A basic iterator library written in Zig で定義されているイテレータであり、map、filter、fold などの操作をすることができます。

イテレータについては Zig 言語用のイテレータライブラリを書きました - ::Eldesh a b = LEFT a | RIGHT b で説明しています。

注意点として、llrbtree-zig が提供しているイテレータは所有権を持たないもののみということがあります。つまり現状ではイテレータだけを持ち運んでツリー本体を破棄することは出来ません。(それ以前に他の書き換え操作全てが出来ません)

// これは出来ない
var iter = map.to_iter();
map.destroy(); // この時点で iter の参照している値も破棄される
while (iter.next()) |item| {}

所有権管理

Zig では(文脈無しで使用できる)標準のアロケータというものが存在しません。このためコンテナでも何らかの方法でアロケータを指定出来る必要があります。ついでに型からvalidなインスタンスを得る一般的な方法も存在しません*1

このため LLRBTreeSet/Map ではコンストラクタ(new関数)で動的にアロケータを受け取ります。

new 関数のシグネチャは Set/Map のいずれも以下のようになっています。

pub fn new(alloc: Allocator, cfg: Self.Config) Self;

第一引数でツリーノードのアロケータを指定します。

第二引数の Config では(必要であれば)キーやバリューのアロケータを独立に指定できます。

またキー、バリューそれぞれについてコンテナが所有権を持たないように指定することも出来ます。

Config の実体は Set の場合は:

pub const Config: type = struct {
    item: Ownership = Ownership.owned(),
};

Map の場合は:

pub const Config: type = struct {
    key: Ownership = Ownership.owned(),
    value: Ownership = Ownership.owned(),
};

となっています。

Ownershipは所有権の有無と用いるアロケータを指定する型で、以下のように定義されています。

pub const Ownership: type = union(enum) {
    OwnedAlloc: std.mem.Allocator,
    Owned: void,
    NotOwned: void,
    ...
};

各バリアントはそれぞれ以下のような意味を表しています。

OwnedAlloc: 指定したアロケータによって管理されるメモリ上に所有する
Owned: デフォルトアロケータ(newの第1引数)によって管理するメモリ上に所有する
NotOwned: コンテナによって所有されない

例えば LLRBtreeMap を以下のように構成すると、所有権を持たない文字列リテラルをバリューとしてコンテナに管理させることが出来ます。

var map = LLRBTreeMap(u32, []const u8).new(alloc, .{ .value = .NotOwned });
defer map.destroy();

コード中にあるようにコンテナ自体の破棄については所有権がある場合と変わりなく destroy() を呼ぶことで行えます。

他のプロジェクトからの参照方法

llrbtree-zig は依存プロジェクトを zigmod で管理しており、自身も zigmod で参照することを想定しています。

依存関係の指定には例えば以下のように記述すれば使用できます。

root_dependencies:
  - src: git git@github.com:eldesh/llrbtree-zig commit-v1.0
dependencies:
  - src: git git@github.com:eldesh/llrbtree-zig commit-v1.0

Cite

Robert Sedgewick. Left-leaning Red-Black Trees https://sedgewick.io/wp-content/themes/sedgewick/papers/2008LLRB.pdf

*1:馬鹿なの？