Generic structure - unable to evaluate comptime expression

Help
1

I’m trying to create a FixedSizeMap, which will have:

  1. I can provide a hash that is absolutely conflict-free.
  2. I know the maximum number of elements in advance, with some extra space for elements, and there is no need to support dynamic memory space increase.

And I make some code as below, but it doesn’t compile.

const std = @import("std");

pub fn HashFn(comptime K: type) type {
    return fn (K) u64;
}

pub const FixedSizeMapError = error{
    OutOfSize, // 超过预定义 max_size
};

pub fn FixedSizeMap(
    comptime K: type,
    comptime V: type,
) type {
    return struct {
        allocator: std.mem.Allocator = undefined,
        hash: HashFn(K) = undefined,
        entries: []Entry = undefined,
        header: usize = 0,

        pub const KeyType = K;
        pub const ValueType = V;

        pub const Entry = struct {
            hash: u64,
            key: K,
            value: V,
        };

        const Self = @This();

        pub fn init(
            allocator: std.mem.Allocator,
            max_size: usize,
            hashFn: HashFn(K),
        ) Self {
            const entries = allocator.alloc(Entry, max_size) catch |err| {
                std.debug.print("alloc error {}\n", .{err});
                @panic("bad alloc");
            };
            return .{
                .allocator = allocator,
                .hash = hashFn,
                .header = 0,
                .entries = entries,
            };
        }

        pub fn put(self: *Self, key: K, value: V) !void {
            if (self.header + 1 >= self.entries.len) {
                return FixedSizeMapError.OutOfSize;
            }
            self.entries[self.header] = .{
                .key = key,
                .hash = self.hash(key),
                .value = value,
            };
            self.header += 1;
        }

        pub fn get(self: *Self, key: K) ?V {
            const key_hash = self.hash(key);
            for (self.entries[0..self.header]) |entry| {
                if (key_hash == entry.hash) {
                    return entry.value;
                }
            }
            return null;
        }
    };
}

pub fn main() !void {
    const allocator = std.heap.page_allocator;
    const U32FixedSizeMap = FixedSizeMap(u32, u32);

    var fixed_map = U32FixedSizeMap.init(allocator, 100, hashU32);

    for (50..100) |i| {
        const i_u32 = @as(u32, i);
        try fixed_map.put(i_u32, i_u32);
    }
    for (0..50) |i| {
        const i_u32 = @as(u32, i);
        try fixed_map.put(i_u32, i_u32);
    }
    for (fixed_map.entries, 0..) |entry, i| {
        std.debug.print("i {d} value {d}", .{ i, entry.key });
    }
}

fn hashU32(v: u32) u64 {
    return @as(u64, v);
}

error log:

src % zig run FixedSizeMap.zig -freference-trace=20
/Users/mac/dev/zig-macos-x86_64-0.14.0-dev.2273+73dcd1914/lib/std/heap/PageAllocator.zig:38:18: error: unable to evaluate comptime expression
    const hint = @atomicLoad(@TypeOf(std.heap.next_mmap_addr_hint), &std.heap.next_mmap_addr_hint, .unordered);
                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/mac/dev/zig-macos-x86_64-0.14.0-dev.2273+73dcd1914/lib/std/heap/PageAllocator.zig:38:69: note: operation is runtime due to this operand
    const hint = @atomicLoad(@TypeOf(std.heap.next_mmap_addr_hint), &std.heap.next_mmap_addr_hint, .unordered);
                                                                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/mac/dev/zig-macos-x86_64-0.14.0-dev.2273+73dcd1914/lib/std/mem/Allocator.zig:86:29: note: called from here
    return self.vtable.alloc(self.ptr, len, ptr_align, ret_addr);
           ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/mac/dev/zig-macos-x86_64-0.14.0-dev.2273+73dcd1914/lib/std/mem/Allocator.zig:225:35: note: called from here
    const byte_ptr = self.rawAlloc(byte_count, log2a(alignment), return_address) orelse return Error.OutOfMemory;
                     ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/mac/dev/zig-macos-x86_64-0.14.0-dev.2273+73dcd1914/lib/std/mem/Allocator.zig:211:40: note: called from here
    return self.allocBytesWithAlignment(alignment, byte_count, return_address);
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/mac/dev/zig-macos-x86_64-0.14.0-dev.2273+73dcd1914/lib/std/mem/Allocator.zig:205:75: note: called from here
    const ptr: [*]align(a) T = @ptrCast(try self.allocWithSizeAndAlignment(@sizeOf(T), a, n, return_address));
                                            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/mac/dev/zig-macos-x86_64-0.14.0-dev.2273+73dcd1914/lib/std/mem/Allocator.zig:129:41: note: called from here
    return self.allocAdvancedWithRetAddr(T, null, n, @returnAddress());
           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
FixedSizeMap.zig:39:44: note: called from here
            const entries = allocator.alloc(Entry, max_size) catch |err| {
                            ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
FixedSizeMap.zig:79:41: note: called from here
    var fixed_map = U32FixedSizeMap.init(allocator, 100, hashU32);
                    ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Thanks for your time.

2

HashFn returns an object of type Fn, which is comptime-only. In order for this to be valid at runtime, you need to use pointers to functions.

pub fn FixedSizeMap(
    comptime K: type,
    comptime V: type,
) type {
    return struct {
        allocator: std.mem.Allocator = undefined,
        - hash: HashFn(K) = undefined,
        + hash: *const HashFn(K) = undefined,
   
       //...

        pub fn init(
            allocator: std.mem.Allocator,
            max_size: usize,
            - hashFn: HashFn(K),
            + hashFn: * const HashFn(K),
        ) Self {

As a side note, it’s bad practice to default initialize fields to undefined like this, if they are actually required for the type to function. This makes it easy for someone to forget to initialize something.

3 Likes
3

Because your data structure is fixed size you could use an array + a length, or a std.BoundedArray I think this would simplify it and allow users of the data structure to use it with and without allocators, on the stack and on the heap.

1 Like
4

Yes, I will try BoundedArray for this. Thank you