A pool returning indices to be used as pointer substitutes. A limited number of items is kept in a free list to re-use.

indexing_pool.zig

const std = @import("std");

pub const IndexingPoolOptions = struct {
    /// The maximum number of items the pool can hold.
    max_items: usize = std.math.maxInt(u32),
    /// The number of item indices to be kept for re-use. If this is
    /// too low, items will leak until the pool is deinitialized.
    free_list_len: usize = 64,
    log: type = std.log.scoped(.indexing_pool),
};

/// A pool returning indices to be used as pointer substitutes. A
/// limited number of item indices is kept in a free list to re-use.
pub fn IndexingPool(
    comptime T: type,
    comptime options: IndexingPoolOptions,
) type {
    // rounding up to the nearest power of 2 for performance reasons
    const index_bits = std.math.ceilPowerOfTwo(u16, std.math.log2(options.max_items)) catch unreachable;

    return struct {
        const Self = @This();
        const log = std.log.scoped(.indexing_pool);

        const IndexInt = @Type(.{ .int = .{ .bits = index_bits, .signedness = .unsigned } });

        pub const Index = enum(IndexInt) {
            /// An unused index to be used like `null`.
            none = std.math.maxInt(IndexInt),
            _,
        };

        items: std.ArrayListUnmanaged(T) = .empty,
        free_list: std.BoundedArray(Index, options.free_list_len) = .{},

        pub fn deinit(b: *Self, ally: std.mem.Allocator) void {
            std.debug.assert(b.free_list.len <= b.items.items.len);

            if (b.items.items.len - b.free_list.len != 0) {
                options.log.info(
                    "{d} items left in pool, if this happens often consider increasing the length of the free list from {d}",
                    .{ b.items.items.len, options.free_list_len },
                );
            }

            b.items.deinit(ally);
            b.* = undefined;
        }

        pub fn create(b: *Self, ally: std.mem.Allocator) (error{OutOfMemory} || std.mem.Allocator.Error)!Index {
            std.debug.assert(b.free_list.len <= b.items.items.len);

            if (b.items.items.len >= options.max_items) return error.OutOfMemory;

            if (b.free_list.len == 0) {
                const result_index: Index = @enumFromInt(@as(IndexInt, @intCast(b.items.items.len)));
                std.debug.assert(result_index != .none);

                _ = try b.items.addOne(ally);

                return result_index;
            }

            const result_index = b.free_list.pop();
            std.debug.assert(result_index != .none);
            return result_index;
        }

        pub fn destroy(b: *Self, index: Index) void {
            std.debug.assert(b.free_list.len <= b.items.items.len);
            std.debug.assert(index != .none);

            b.get(index).* = undefined;

            if (@intFromEnum(index) == b.items.items.len - 1) {
                b.items.shrinkRetainingCapacity(b.items.items.len - 1);
            } else {
                b.free_list.append(index) catch {
                    options.log.debug("leaking {d}", .{index});
                };
            }
        }

        /// The result of this call is alive until the next `create`
        /// or `destroy`.
        pub fn get(b: *Self, index: Index) *T {
            std.debug.assert(b.free_list.len <= b.items.items.len);
            std.debug.assert(index != .none);

            return &b.items.items[@intFromEnum(index)];
        }
    };
}

test IndexingPool {
    var pool: IndexingPool([128]u8, .{}) = .{};
    defer pool.deinit(std.testing.allocator);

    const a = try pool.create(std.testing.allocator);
    const b = try pool.create(std.testing.allocator);
    const c = try pool.create(std.testing.allocator);
    const d = try pool.create(std.testing.allocator);

    @memset(pool.get(d), 69);
    pool.destroy(d);
    @memset(pool.get(c), 42);
    pool.destroy(c);
    @memset(pool.get(a), 13);
    pool.destroy(a);
    @memset(pool.get(b), 37);
    pool.destroy(b);
}