Light-weight alternative to ArrayList in std

Brainstorming
1

It could be useful, I think, to have functions in the standard that let you use a plain-o slice pointer in the manner of an ArrayList. Happens quite often when you’re building some kind of a tree, where there’s variation in the number elements but it’s small.

I’m thinking something like this:

fn calcCapacity(len: usize) usize {
    return if (len > 0) std.math.ceilPowerOfTwo(usize, len) catch unreachable else 0;
}

fn GrandchildOf(comptime T: type) type {
    return switch (@typeInfo(T)) {
        .pointer => |pt| check: {
            if (pt.is_const) @compileError("Cannot make modification through a const pointer");
            break :check switch (@typeInfo(pt.child)) {
                .pointer => |pt2| check2: {
                    if (pt2.is_const) @compileError("Slice is const");
                    break :check2 pt2.child;
                },
                else => @compileError("Not a pointer to a slice"),
            };
        },
        else => @compileError("Not a pointer"),
    };
}

fn append(allocator: std.mem.Allocator, slice_ptr: anytype, value: GrandchildOf(@TypeOf(slice_ptr))) !void {
    const len = slice_ptr.*.len;
    const capacity = calcCapacity(len);
    const new_len = len + 1;
    const new_capacity = calcCapacity(new_len);
    if (new_capacity != capacity) {
        const slice_before = slice_ptr.*.ptr[0..capacity];
        slice_ptr.* = try allocator.realloc(slice_before, new_capacity);
    }
    slice_ptr.*.len = new_len;
    slice_ptr.*[len] = value;
}

fn remove(allocator: std.mem.Allocator, slice_ptr: anytype, index: usize) void {
    _ = GrandchildOf(@TypeOf(slice_ptr));
    const len = slice_ptr.*.len;
    var i: usize = index;
    while (i + 1 < len) : (i += 1) {
        slice_ptr.*[i] = slice_ptr.*[i + 1];
    }
    const capacity = calcCapacity(len);
    const new_len = len - 1;
    const new_capacity = calcCapacity(new_len);
    if (new_capacity != capacity) {
        const slice_before = slice_ptr.*.ptr[0..capacity];
        slice_ptr.* = allocator.realloc(slice_before, new_capacity) catch unreachable;
    }
    slice_ptr.*.len = new_len;
}
2 Likes
2

Wouldn’t it be easier to just use 2 u32s, one for length, one for capacity? Then you wouldn’t need to downsize the allocation on removal and you could still supports functions like reserve and shrinkToCapacity.

3

Then you’d need extra fields in the structs, which aren’t meaningful or useful to on the consuming side.

There were talks of removing managed data struct. The only difference between a ArrayList and a slice would then be just the capacity field. As part of the change, perhaps we can add a comptime option for using inferred capacity. When we need to append to a slice, we’d cast the slice into such an ArrayList. Something like this:

const NodeList = ArrayList(*Node, .{ .capacity = .inferred });
try NodeList.fromSlice(&node.children).append(allocator, child);