commit 178c73563c5c855333dc303d829d01cb337846b9
parent 3555a25bf3df78d6be744a9d00b752d590208e6c
Author: Ashymad <szymon.mikulicz@posteo.net>
Date: Fri, 29 Mar 2024 03:13:06 +0100
hash table work
Diffstat:
4 files changed, 161 insertions(+), 4 deletions(-)
diff --git a/zlox/src/hash.zig b/zlox/src/hash.zig
@@ -0,0 +1,26 @@
+const Obj = @import("obj.zig").Obj;
+
+pub fn hash_t(T: type) fn (T) u32 {
+ return switch (T) {
+ []const u8, [*]const u8, []u8, [*]u8 => struct {
+ pub fn fun(key: T) u32 {
+ var ret: u32 = 2166136261;
+ for (key) |char| {
+ ret ^= char;
+ ret *= 16777619;
+ }
+ return ret;
+ }
+ }.fun,
+ Obj, *Obj, *const Obj => struct {
+ pub fn fun(key: T) u32 {
+ return key.hash;
+ }
+ }.fun,
+ else => @compileError("Unsupported type"),
+ };
+}
+
+pub fn hash(val: anytype) u32 {
+ return hash_t(@TypeOf(val))(val);
+}
diff --git a/zlox/src/obj.zig b/zlox/src/obj.zig
@@ -1,5 +1,6 @@
const std = @import("std");
const utils = @import("comptime_utils.zig");
+const hash = @import("hash.zig").hash;
pub const Obj = packed struct {
const Super = @This();
@@ -7,6 +8,7 @@ pub const Obj = packed struct {
type: Type,
next: ?*Super = null,
+ hash: u32,
pub const List = struct {};
@@ -25,17 +27,22 @@ pub const Obj = packed struct {
const ret: *Self = @ptrCast(try allocator.alignedAlloc(u8, @alignOf(Self), @sizeOf(Self) + len));
ret.* = Self{ .obj = Super{
.type = Super.Type.String,
+ .hash = 0,
}, .len = len };
return ret;
}
+ fn rehash(self: *Self) void {
+ self.obj.hash = hash(self.slice());
+ }
pub fn slice(self: *const Self) []const u8 {
return self.data()[0..self.len];
}
pub fn cat(self: *const Self, other: *const Self, allocator: std.mem.Allocator) !*Self {
- const ret = try new(self.len + other.len, allocator);
+ var ret = try new(self.len + other.len, allocator);
@memcpy(ret.data(), self.slice());
@memcpy(ret.data() + self.len, other.slice());
+ ret.rehash();
return ret;
}
@@ -46,11 +53,12 @@ pub const Obj = packed struct {
std.debug.print("\"{s}\"", .{self.slice()});
}
pub fn eql(self: *const Self, other: *const Self) bool {
- return std.mem.eql(u8, self.slice(), other.slice());
+ return @intFromPtr(self) == @intFromPtr(other);
}
pub fn init(string: Arg, allocator: std.mem.Allocator) !*Self {
- const ret = try new(string.len, allocator);
+ var ret = try new(string.len, allocator);
@memcpy(ret.data(), string);
+ ret.rehash();
return ret;
}
fn free(self: *const Self, allocator: std.mem.Allocator) void {
diff --git a/zlox/src/table.zig b/zlox/src/table.zig
@@ -0,0 +1,123 @@
+const std = @import("std");
+
+pub const TableError = error{ OutOfMemory, KeyError };
+
+pub fn Table(K: type, V: type, hash_fn: fn (K) u32, cmp_fn: fn (K, K) bool) type {
+ return struct {
+ const Self = @This();
+ const MaxLoad = 0.75;
+
+ const Entry = union(enum) {
+ const Some = struct {
+ key: K,
+ value: V,
+ };
+ some: Some,
+ none,
+ tomb,
+ };
+
+ count: usize,
+ entries: []Entry,
+ allocator: std.mem.Allocator,
+
+ pub fn init(allocator: std.mem.Allocator) Self {
+ return Self{ .count = 0, .entries = &.{}, .allocator = allocator };
+ }
+
+ fn growCapacity(self: *const Self) usize {
+ return if (self.entries.len > 0)
+ self.entries.len * 2
+ else
+ 10;
+ }
+
+ fn adjustCapacity(self: *Self, newsize: usize) TableError!void {
+ const entries = try self.allocator.alloc(Entry, newsize);
+ for (entries) |entry| {
+ entry = .none;
+ }
+ self.count = 0;
+ for (self.entries) |entry| {
+ switch (entry) {
+ .some => |some| {
+ (find(entries, some.key)) = entry;
+ self.count += 1;
+ },
+ else => {},
+ }
+ }
+ self.allocator.free(self.entries);
+ self.entries = entries;
+ }
+
+ fn find(entries: []Entry, key: K) *Entry {
+ const idx = hash_fn(key) % entries.len;
+ var tomb: ?*Entry = null;
+
+ while (true) {
+ const entry = &entries[idx];
+ switch (entry) {
+ .some => |some| if (cmp_fn(some.key, key)) return entry,
+ .tomb => tomb = if (tomb) |_| tomb else entry,
+ .none => return if (tomb) |_| tomb else entry,
+ }
+ idx = (idx + 1) % entries.len;
+ }
+ }
+
+ pub fn addAll(self: *Self, other: *const Self) TableError!void {
+ for (other.entries) |entry| {
+ switch (entry) {
+ .some => |some| self.set(some.key, some.value),
+ else => {},
+ }
+ }
+ }
+
+ pub fn set(self: *Self, key: K, val: V) TableError!bool {
+ if (self.count + 1 > self.entries.len * MaxLoad) {
+ try self.adjustCapacity(self.growCapacity());
+ }
+ var entry = find(self.entries, key);
+ const isNewKey = switch (entry) {
+ .none => self.count += 1 or true,
+ .tomb => true,
+ .some => false,
+ };
+
+ entry.some = Entry.Some{ .key = key, .value = val };
+ return isNewKey;
+ }
+
+ pub fn get(self: *const Self, key: K) TableError!V {
+ if (self.entries.len == 0)
+ return TableError.KeyError;
+
+ return switch (find(self.entries, key)) {
+ .some => |some| some.value,
+ else => TableError.KeyError,
+ };
+ }
+
+ pub fn delete(self: *Self, key: K) bool {
+ if (self.entries.len == 0) return false;
+
+ var entry = find(self.entries, key);
+ switch (entry) {
+ .some => entry = .tomb,
+ else => return false,
+ }
+
+ return true;
+ }
+
+ pub fn deinit(self: *@This()) void {
+ if (self.entries.len > 0) {
+ self.allocator.free(self.entries);
+ self.entries = &.{};
+ self.count = 0;
+ }
+ }
+ };
+}
diff --git a/zlox/src/value.zig b/zlox/src/value.zig
@@ -25,7 +25,7 @@ pub const Value = union(enum) {
return @unionInit(@This(), field.name, val);
}
}
- @compileError("Invalid union type");
+ @compileError("Invalid Value type");
}
fn toTag(comptime from: anytype) Tag {
