A simple allocator wrapper with a free list, sort of, to reuse allocations.

free_list_allocator.zig

// SPDX-License-Identifier: 0BSD
// Copyright (C) 2024 by cancername <[email protected]>
//
// Permission to use, copy, modify, and/or distribute this software for any purpose with or without
// fee is hereby granted.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
// SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
// AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
// NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
// OF THIS SOFTWARE.

const std = @import("std");
const mem = std.mem;
const heap = std.heap;

// TODO: This is lazy.

pub const FreeListAllocator = struct {
    const Allocation = struct {
        len: usize,
        ptr: usize,
        log2_align: u8,
    };

    const max_allocations = 16;

    inner: mem.Allocator = heap.page_allocator,
    allocations: std.BoundedArray(Allocation, max_allocations) = .{},

    pub fn allocator(fla: *FreeListAllocator) mem.Allocator {
        return .{
            .ptr = @ptrCast(fla),
            .vtable = &.{
                .alloc = alloc,
                .resize = resize,
                .free = free,
            },
        };
    }

    pub fn deinit(fla: *FreeListAllocator) void {
        for (fla.allocations.constSlice()) |allocation| {
            fla.inner.rawFree(@as([*]u8, @ptrFromInt(allocation.ptr))[0..allocation.len], allocation.log2_align, 0);
        }
    }

    fn alloc(ctx: *anyopaque, len: usize, log2_align: u8, ret_addr: usize) ?[*]u8 {
        const state: *FreeListAllocator = @ptrCast(@alignCast(ctx));

        for (state.allocations.constSlice(), 0..) |allocation, i| {

            if (allocation.log2_align == log2_align) {
                if(allocation.len == len) {
                    defer _ = state.allocations.swapRemove(i);
                    return @ptrFromInt(allocation.ptr);
                } else if(allocation.len > len) {
                    const sl = @as([*]u8, @ptrFromInt(allocation.ptr))[0..allocation.len];
                    if (state.inner.rawResize(sl, allocation.log2_align, len, ret_addr)) {
                        defer _ = state.allocations.swapRemove(i);
                        return @ptrFromInt(allocation.ptr);
                    }
                }
            }
        }

        const p = state.inner.rawAlloc(len, log2_align, ret_addr);
        return p;
    }

    fn resize(ctx: *anyopaque, buf: []u8, log2_align: u8, new_len: usize, ret_addr: usize) bool {
        const state: *FreeListAllocator = @ptrCast(@alignCast(ctx));
        return state.inner.rawResize(buf, log2_align, new_len, ret_addr);
    }

    fn free(ctx: *anyopaque, buf: []u8, log2_align: u8, ret_addr: usize) void {
        const state: *FreeListAllocator = @ptrCast(@alignCast(ctx));
        state.allocations.append(.{
            .len = buf.len,
            .ptr = @intFromPtr(buf.ptr),
            .log2_align = log2_align,
        }) catch state.inner.rawFree(buf, log2_align, ret_addr);
    }
};