A simple Set implementation

Showcase
1

As a spin-off of banging my head with Advent of Code, here’s a simple Set implemented in Zig. It surely isn’t the most efficient, bullet-proof impl, but it’s passing the basic functionality tests. :^)

2

vim build.exe?.. Why does this file have exe suffix, not zig?

3

OMG, that’s what Advent of Code does to your brain. lol. Thanks for the good catch!

4

Another misprint in README.md:

exe.addPackagePath("set", "libs/set/src/set.zig");

Must be

exe.addPackagePath("set", "libs/set/src/Set.zig");
5

I tried to build a set of structures with 3 f32 fields:

const std = @import("std");
const set = @import("set");

const Object = struct {
    x: f32,
    y: f32,
    z: f32,
};

const ObjectSet = set.Set(Object);

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer std.debug.print("leakage?.. {}\n", .{gpa.deinit()});
    const allocator = gpa.allocator();

    var set_1 = try ObjectSet.fromSlice(
        allocator,
        &[_]Object{
            .{.x = 1.1, .y = 2.2, .z = 3.3},
            .{.x = 4.4, .y = 5.5, .z = 6.6},
        }
    );

    const b = set_1.contains(.{.x = 1.1, .y = 2.2, .z = 3.3});
    std.debug.print("b = {}\n", .{b});
}

Compiler says

/opt/zig-0.10/lib/std/hash/auto_hash.zig:84:12: error: unable to hash type f32
        => @compileError("unable to hash type " ++ @typeName(Key)),
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
referenced by:
    hash__anon_7769: /opt/zig-0.10/lib/std/hash/auto_hash.zig:127:17
    autoHash__anon_6976: /opt/zig-0.10/lib/std/hash/auto_hash.zig:193:5
6

However it works with a set of

const Object = struct {
    x: i32,
    y: i32,
    z: i32,
};
7

set.zig is actually correct. It’s just that I did a normal mv instead of using git mv. I pushed the correction to the repo. Zig convention recommends lowercase if the namespace in question doesn’t have any fields as is the case here.

8

Yes, that’s the normal rules for a Zig hash map; you can’t have keys with floats. I believe it has to do with the fact that comparing floats is imprecise and in a hash map comparing keys (their hashes to be exact) is the critical step in their functionality.

9

We have to compare keys directly in case of conflicts, that’s the reason, I think. Calculating hash/index is not a problem by itself.

10

A couple of articles about using floats as keys in hash tables.
https://diego.assencio.com/?index=67e5393c40a627818513f9bcacd6a70d

1 Like