comptime{allocator,array}.zig

comptimealloc.zig

const std = @import("std");

const Error = std.mem.Allocator.Error;

pub const Allocator = struct {
    const Self = @This();

    end_index: usize,
    buffer: []u8,

    pub fn init(buffer: []u8) Allocator {
        return .{
            .buffer = buffer,
            .end_index = 0,
        };
    }

    pub fn alloc(self: *Self, comptime T: type, n: usize) Error![]T {
        const size = @sizeOf(T) * n;
        if ((self.end_index + size) > self.buffer.len) {
            return error.OutOfMemory;
        }
        const start = self.end_index;
        self.end_index += size;
        const slice = self.buffer[start..self.end_index];
        return std.mem.bytesAsSlice(T, @alignCast(@alignOf(T), slice));
    }

    pub fn free(self: Self, memory: anytype) void {
        _ = self;
        _ = memory;
    }

    pub fn create(self: *Self, comptime T: type) Error!*T {
        var val = try self.alloc(T, 1);
        return &val[0];
    }

    pub fn destroy(self: *Self, ptr: anytype) void {
        _ = self;
        _ = ptr;
    }

    pub fn resize(self: Self, old_mem: anytype, new_n: usize) bool {
        _ = self;
        _ = old_mem;
        _ = new_n;
        return false;
    }

    pub fn alignedAlloc(
        self: *Self,
        comptime T: type,
        /// null means naturally aligned
        comptime alignment: ?u29,
        n: usize,
    ) Error![]T {
        _ = alignment;
        return self.alloc(T, n);
    }
};

test "alloc" {
    var buf: [1024]u8 = undefined;
    var allocator = Allocator.init(&buf);
    {
        const val = try allocator.create(u8);
        val.* = 10;
        try std.testing.expectEqual(val.* + 1, 11);
        allocator.destroy(val);
    }
    {
        var val = try allocator.alloc(u8, 5);
        _ = try std.fmt.bufPrint(val, "{s}", .{"hello"});
        try std.testing.expect(std.mem.eql(u8, val, "hello"));
        allocator.free(val);
    }
}

comptimearray.zig

const std = @import("std");
const mem = std.mem;
const Allocator = @import("comptimealloc.zig").Allocator;

pub fn ArrayList(comptime T: type) type {
    return packed struct {
        const Self = @This();
        const Slice = []T;

        items: [*]T = &[_]T{},
        items_len: usize = 0,
        capacity: usize = 0,
        allocator: *Allocator,

        pub fn init(allocator: *Allocator) Self {
            return .{
                .allocator = allocator,
            };
        }

        pub fn deinit(self: Self) void {
            self.allocator.free(self.allocatedSlice());
        }

        pub fn allocatedSlice(self: Self) Slice {
            return self.items[0..self.capacity];
        }

        pub fn insert(self: *Self, n: usize, item: T) !void {
            try self.ensureTotalCapacity(self.items_len + 1);
            self.insertAssumeCapacity(n, item);
        }

        pub fn ensureTotalCapacity(self: *Self, new_capacity: usize) !void {
            if (@sizeOf(T) == 0) {
                self.capacity = std.math.maxInt(usize);
                return;
            }

            if (self.capacity >= new_capacity) return;

            var better_capacity = self.capacity;
            while (true) {
                better_capacity +|= better_capacity / 2 + 8;
                if (better_capacity >= new_capacity) break;
            }

            return self.ensureTotalCapacityPrecise(better_capacity);
        }

        pub fn ensureTotalCapacityPrecise(self: *Self, new_capacity: usize) !void {
            if (@sizeOf(T) == 0) {
                self.capacity = std.math.maxInt(usize);
                return;
            }

            if (self.capacity >= new_capacity) return;
            const new_memory = try self.allocator.alignedAlloc(T, null, new_capacity);
            mem.copy(T, new_memory, self.currentItems());
            self.allocator.free(self.allocatedSlice());
            self.items = new_memory.ptr;
            self.capacity = new_memory.len;
        }

        pub fn insertAssumeCapacity(self: *Self, n: usize, item: T) void {
            if (!(self.items_len < self.capacity)) @panic("out of capacity");
            self.items_len += 1;

            mem.copyBackwards(T, self.items[n + 1 .. self.items_len], self.items[n .. self.items_len - 1]);
            self.items[n] = item;
        }

        pub fn append(self: *Self, item: T) !void {
            try self.ensureTotalCapacity(self.items_len + 1);
            self.insertAssumeCapacity(self.items_len, item);
        }

        fn currentItems(self: Self) Slice {
            return self.items[0..self.items_len];
        }
    };
}

test "u8" {
    comptime {
        var buf: [1024]u8 = undefined;
        var allocator = Allocator.init(&buf);
        var list = ArrayList(u8).init(&allocator);
        defer list.deinit();
        try list.append(7);
        try list.append(8);
        try list.append(9);
        try std.testing.expectEqual(list.items_len, 3);
        try std.testing.expectEqual(list.items[1], 8);
    }
}

test "struct" {
    comptime {
        const A = packed struct {
            i: usize,
        };

        var buf: [1024]u8 = undefined;
        var allocator = Allocator.init(&buf);
        var list = ArrayList(A).init(&allocator);
        defer list.deinit();

        try list.append(A{.i=0});
        try list.append(A{.i=1});
        try list.append(A{.i=2});
        try std.testing.expectEqual(list.items_len, 3);
        try std.testing.expectEqual(list.items[2].i, 2);
    }
}

test "nested" {
    comptime {
        const B = packed struct {
            i: usize,            
        };

        const A = packed struct {
            list: ArrayList(B),
        };

        var buf: [1024]u8 = undefined;
        var allocator = Allocator.init(&buf);
        var a = A{.list = ArrayList(B).init(&allocator)};
        try a.list.append(B{.i=0});
        try a.list.append(B{.i=1});
        try a.list.append(B{.i=2});
    }
}