container

動的配列、リスト、ハッシュマップのような、データの集まりを表現するデータ構造をコンテナと呼びます。Zenの標準ライブラリではstd.containerで、次のコンテナを提供しています。

Buffer、BufMap、BufSetを除くと、これらのコンテナはジェネリックです。つまり、特定の型に依存しておらず、任意型のコンテナを作り出すことができます。

全てのコンテナ型はメモリアロケータを要求します。要素を追加する操作では、メモリ確保に失敗するとerror.OutOfMemoryが返ります。

よく使うコンテナであるArrayList、AutoHashMap、TailQueueについて説明します。

ArrayList

ArrayList(T)はT型の値を格納する動的配列です。

ArrayListの主要なメソッドは次のとおりです。新しく要素を追加するメソッドでは、メモリ確保失敗時に、error.OutOfMemoryが返ります。

• deinit() void: インスタンスの後始末をします。確保したメモリを解放します。
• len() usize: 現在保有している要素数を取得します。
• at(i: usize) *mut T: i番目の要素のポインタを取得します。
• toSlice() Slice: リストをスライスとして取得します。メモリ領域の所有権はArrayList側にあります。
• append(item: T) !void: リストの一番後ろに要素を1つ追加します。
• appendSlice(items: SliceConst) !void: リストの一番後ろに要素を複数個追加します。
• insert(n: usize, item: T) !void: n番目に要素を1つ追加します。
• insertSlice(n: usize, items: SliceConst) !void: n番目に要素を複数個追加します。
• pop() T: 要素を1つリストから削除して、取得します。リストが空の場合、安全性保護付き未定義動作を引き起こします。
• popOrNull() ?T: pop()と似ていますが、リストが空の場合、nullが返ります。
• orderedRemove(i: usize) T: i番目の要素を取り除き、その値を返します。取り除く要素以外の順番は保証されます。計算量はO(n)です。
• swapRemove(i: usize) T: i番目の要素を取り除き、その値を返します。i番目の要素には、代わりに末尾の要素が入ります。計算量はO(1)です。

ArrayListの利用例を示します。

examples/ch09-std/container/src/array_list.zen:4:39

const heap = std.heap;
const ArrayList = std.container.ArrayList;
test "ArrayList" {
    // アロケータの準備
    var bytes: [1024]u8 = undefined;
    var allocator = heap.FixedBufferAllocator{ .buffer = bytes[0..] };

    // `usize`を格納するArrayListの初期化。`deinit`でメモリを解放
    var list = ArrayList(usize){ .allocator = &mut allocator };
    defer list.deinit();

    // リストの後ろに要素を追加
    try list.append(1);
    try list.append(5);

    // `len`で現在の要素数を取得、`at`で要素アクセス
    ok(list.len() == @to(usize, 2));
    ok(list.at(0).* == @to(usize, 1));

    // `insert`で`1`番目に`10`を挿入
    try list.insert(1, 10);
    ok(list.len() == @to(usize, 3));
    ok(list.at(1).* == @to(usize, 10));

    // `pop`で後ろから要素を取り出す
    ok(list.pop() == 5);
    ok(list.len() == 2);

    // `popOrNull`ではコンテナがからの場合、`null`が返る
    var sum_of_remained: usize = 0;
    while (list.popOrNull()) |value| {
        sum_of_remained += value;
    } else {
        ok(sum_of_remained == 11);
    }
}

下記の2つのメソッドは、動的配列の容量に関連するメソッドです。実際に値を保有しているかどうかとは別に、ArrayListが確保しているメモリ領域の大きさを容量と呼びます。appendごとに新しくメモリ領域を割り当てるのは、非効率的です。そのため、ArrayListではappend時に容量が不足する場合、ある計算式に基づいて多めにメモリ領域を確保します。

• capacity() usize: メモリの再割当てなしに、Tの値を格納できる個数を返します。
• ensureCapacity(new_capacity: usize) !void: new_capacity以上の容量を確保します。

examples/ch09-std/container/src/array_list.zen:41:60

test "ArrayList capacity" {
    // アロケータの準備
    var bytes: [1024]u8 = undefined;
    var allocator = heap.FixedBufferAllocator{ .buffer = bytes[0..] };

    // `usize`を格納するArrayListの初期化。`deinit`でメモリを解放
    var list = ArrayList(usize){ .allocator = &mut allocator };
    defer list.deinit();

    // 初期化時点では容量は`0`
    ok(list.capacity() == 0);

    // 一度メモリを確保すると容量は`8`
    try list.append(1);
    ok(list.capacity() == 8);

    // `16`以上の容量を確保、容量計算により`20`になる
    try list.ensureCapacity(16);
    ok(list.capacity() == 20);
}

次の2つのメソッドは、確保したメモリの所有権が移動するメソッドです。メモリ解放の責任は、メモリの所有権を受け取る側になります。

• fromOwnedSlice(allocator: Allocator, slice: Slice) @This(): allocatorによって確保されたsliceの所有権を取得し、ArrayListを作成します。
• toOwnedSlice() Slice: 保有しているメモリの所有権を手放し、スライスを返します。

examples/ch09-std/container/src/array_list.zen:62:85

test "Ownership" {
    // アロケータの準備
    var bytes: [1024]u8 = undefined;
    var allocator = heap.FixedBufferAllocator{ .buffer = bytes[0..] };

    // メモリを動的確保し、使用 (初期化) する
    var owned = try heap.alloc(&mut allocator, usize, 10);
    for (owned) |*v, i| {
        v.* = i;
    }

    // 動的確保されたメモリから`ArrayList`のインスタンスを作成する
    var list = ArrayList(usize).fromOwnedSlice(&mut allocator, owned);
    ok(list.len() == 10);
    ok(list.at(9).* == 9);

    // 所有権を手放して、スライスを返す
    var owned_again = list.toOwnedSlice();
    ok(list.len() == 0);
    for (owned_again) |*v, i| {
        ok(v.* == i);
    }
    heap.free(&mut allocator, owned_again);
}

AutoHashMap

ハッシュ関数としてwyhashを使用するハッシュマップです。

AutoHashMapの主要なメソッドを以下に示します。新しくエントリを作成するメソッドでは、メモリ確保失敗時に、error.OutOfMemoryが返ります。

ここで、Kは任意のキーを表す型、Vは任意のデータを表す型、KVはstruct { key: K, value: V }です。

• deinit() void: インスタンスの後始末をします。確保したメモリを解放します。
• clear() void: 全てのエントリを削除します。
• count() usize: 保有しているエントリ数を取得します
• ensureCapacity(expected_count: usize) !void: expected_count以上の容量を確保します。
• put(key: K, value: V) !?KV: 新しいエントリを追加します。キーが同じエントリが既にある場合、古い値を返します。
• putNoClobber(key: K, value: V) !void: キーが登録されていなければ、新しいエントリを追加します。キーの登録がないことをアサーションで検査しています。
• get(key: K) ?*mut KV: キーが一致するエントリのデータを取得します。
• contains(key: K) bool: キーが登録されていればtrue、そうでなければfalseが返ります。
• remove(key: K) ?KV: 与えたキーを持つエントリを削除します。キーが一致するエントリがあれば削除したエントリが、そうでなければnullが返ります。

AutoHashMapの利用例を示します。

examples/ch09-std/container/src/hash_map.zen:5:42

const heap = std.heap;
const AutoHashMap = std.container.AutoHashMap;
test "AutoHashMap" {
    // アロケータの準備
    var bytes: [1024]u8 = undefined;
    var allocator = heap.FixedBufferAllocator{ .buffer = bytes[0..] };

    // キーが`i32`、データが`[]u8`のハッシュマップ
    var map = AutoHashMap(i32, [:0]u8){ .allocator = &mut allocator };
    // `deinit`でメモリを解放
    defer map.deinit();

    ok(map.count() == 0);
    var previous = try map.put(1, "one");
    // 重複するキーがなければ`null`が返る
    ok(previous == null);
    ok(map.count() == 1);

    // 既にキーが登録されている`1`を登録する
    previous = try map.put(1, "1");
    // 前回登録したキーとデータのペアが返ってくる
    ok(previous.?.key == 1);
    equalSlices(u8, "one", previous.?.value);

    // キーが登録されていれば`true`が返る
    ok(map.contains(1));
    // キーに紐づくデータを取得する。キーが登録されていなければ`null`が返る
    equalSlices(u8, "1", map.getValue(1).?);
    ok(map.getValue(2) == null);

    // マップから登録を削除する
    var removed = map.remove(1);
    // 削除されたキーとデータのペアが返ってくる
    ok(removed.?.key == 1);
    equalSlices(u8, "1", removed.?.value);

    ok(map.count() == 0);
}

TailQueue

双方向リストです。ArrayListやAutoHashMapと違い、内部にアロケータを持ちません。これはノードの所有権が常に、TailQueue側ではなく、呼び出し側にあることを意味します。

TailQueueのフィールドは下記の通りです。

• first: リストの先頭ノードです。
• last: リストの末尾ノードです。

TailQueueの主要なメソッドを以下に示します。ここでTは格納するデータ型、Nodeは双方向リストのノードstruct { prev: ?*mut Node, next: ?*mut Node, data: T }です。

• allocateNode(allocator: heap.Allocator) !*mut Node: 新しいノードを作成します。
• destroyNode(node: *mut Node, allocator: heap.Allocator) void: ノードを解放します。
• createNode(data: T, allocator: heap.Allocator) !*mut Node: 新しいノードを作成し、dataで初期化します。
• append(new_node: *mut Node) void: リストの末尾にノードを追加します。
• prepend(new_node: *mut Node) void: リストの先頭にノードを追加します。
• insertAfter(node: *mut Node, new_node: *mut Node) void: nodeの後ろにnew_nodeを挿入します。
• insertBefore(node: *mut Node, new_node: *mut Node) void: nodeの前にnew_nodeを挿入します。
• remove(node: *mut Node) void: nodeを削除します。
• pop() ?*mut Node: リストの末尾ノードを取り除きます。
• popFirst() ?*mut Node: リストの先頭ノードを取り除きます。
• concatByMoving(list1: *mut Self, list2: *mut Self) void: list1の後ろにlist2を連結します。list2のノードは空になります。
• getLen() usize: リストのノード数を取得します。

examples/ch09-std/container/src/linked_list.zen:7:62

test "TailQueue" {
    var bytes: [1024]u8 = undefined;
    var allocator = heap.FixedBufferAllocator{ .buffer = bytes[0..] };

    // `u32`のノードを持つ`TailQueue`を作成
    var list = TailQueue(u32){};

    // ノード作成
    var one = try list.createNode(1, &mut allocator);
    var two = try list.createNode(2, &mut allocator);
    var three = try list.createNode(3, &mut allocator);
    var four = try list.createNode(4, &mut allocator);
    var five = try list.createNode(5, &mut allocator);
    // ノード解放
    defer {
        list.destroyNode(one, &mut allocator);
        list.destroyNode(two, &mut allocator);
        list.destroyNode(three, &mut allocator);
        list.destroyNode(four, &mut allocator);
        list.destroyNode(five, &mut allocator);
    }

    list.append(two); // {2}
    list.append(five); // {2, 5}
    list.prepend(one); // {1, 2, 5}
    list.insertBefore(five, four); // {1, 2, 4, 5}
    list.insertAfter(two, three); // {1, 2, 3, 4, 5}

    // 前から順番に探索
    {
        var it = list.first; // ?*Node
        var index: u32 = 1;
        while (it) |node| : (it = node.next) {
            ok(node.data == index);
            index += 1;
        }
    }

    // 後ろから逆順に探索
    {
        var it = list.last; // ?*Node
        var index: u32 = 1;
        while (it) |node| : (it = node.prev) {
            ok(node.data == 6 - index);
            index += 1;
        }
    }

    var first = list.popFirst(); // {2, 3, 4, 5}
    var last = list.pop(); // {2, 3, 4}
    list.remove(three); // {2, 4}

    ok(list.first.?.data == 2);
    ok(list.last.?.data == 4);
    ok(list.getLen() == 2);
}