IndexHeader

const IndexHeader = struct {
    /// This field tracks the total number of items in the arrays following
    /// this header.  It is the bit index of the power of two number of indices.
    /// This value is between min_bit_index and max_bit_index, inclusive.
    bit_index: u8 align(@alignOf(u32)),

    /// Map from an incrementing index to an index slot in the attached arrays.
    fn constrainIndex(header: IndexHeader, i: usize) usize {
        // This is an optimization for modulo of power of two integers;
        // it requires `indexes_len` to always be a power of two.
        return @as(usize, @intCast(i & header.mask()));
    }

    /// Returns the attached array of indexes.  I must match the type
    /// returned by capacityIndexType.
    fn indexes(header: *IndexHeader, comptime I: type) []Index(I) {
        const start_ptr: [*]Index(I) = @ptrCast(@alignCast(@as([*]u8, @ptrCast(header)) + @sizeOf(IndexHeader)));
        return start_ptr[0..header.length()];
    }

    /// Returns the type used for the index arrays.
    fn capacityIndexType(header: IndexHeader) CapacityIndexType {
        return hash_map.capacityIndexType(header.bit_index);
    }

    fn capacity(self: IndexHeader) u32 {
        return index_capacities[self.bit_index];
    }
    fn length(self: IndexHeader) usize {
        return @as(usize, 1) << @as(math.Log2Int(usize), @intCast(self.bit_index));
    }
    fn mask(self: IndexHeader) u32 {
        return @as(u32, @intCast(self.length() - 1));
    }

    fn findBitIndex(desired_capacity: usize) Allocator.Error!u8 {
        if (desired_capacity > max_capacity) return error.OutOfMemory;
        var new_bit_index: u8 = @intCast(std.math.log2_int_ceil(usize, desired_capacity));
        if (desired_capacity > index_capacities[new_bit_index]) new_bit_index += 1;
        if (new_bit_index < min_bit_index) new_bit_index = min_bit_index;
        assert(desired_capacity <= index_capacities[new_bit_index]);
        return new_bit_index;
    }

    /// Allocates an index header, and fills the entryIndexes array with empty.
    /// The distance array contents are undefined.
    fn alloc(gpa: Allocator, new_bit_index: u8) Allocator.Error!*IndexHeader {
        const len = @as(usize, 1) << @as(math.Log2Int(usize), @intCast(new_bit_index));
        const index_size = hash_map.capacityIndexSize(new_bit_index);
        const nbytes = @sizeOf(IndexHeader) + index_size * len;
        const bytes = try gpa.alignedAlloc(u8, .of(IndexHeader), nbytes);
        @memset(bytes[@sizeOf(IndexHeader)..], 0xff);
        const result: *IndexHeader = @ptrCast(@alignCast(bytes.ptr));
        result.* = .{
            .bit_index = new_bit_index,
        };
        return result;
    }

    /// Releases the memory for a header and its associated arrays.
    fn free(header: *IndexHeader, gpa: Allocator) void {
        const index_size = hash_map.capacityIndexSize(header.bit_index);
        const ptr: [*]align(@alignOf(IndexHeader)) u8 = @ptrCast(header);
        const slice = ptr[0 .. @sizeOf(IndexHeader) + header.length() * index_size];
        gpa.free(slice);
    }

    /// Puts an IndexHeader into the state that it would be in after being freshly allocated.
    fn reset(header: *IndexHeader) void {
        const index_size = hash_map.capacityIndexSize(header.bit_index);
        const ptr: [*]align(@alignOf(IndexHeader)) u8 = @ptrCast(header);
        const nbytes = @sizeOf(IndexHeader) + header.length() * index_size;
        @memset(ptr[@sizeOf(IndexHeader)..nbytes], 0xff);
    }

    // Verify that the header has sufficient alignment to produce aligned arrays.
    comptime {
        if (@alignOf(u32) > @alignOf(IndexHeader))
            @compileError("IndexHeader must have a larger alignment than its indexes!");
    }
}