lib::table.zig (7504B)
1 const std = @import("std"); 2 3 const utils = @import("lib::utils.zig"); 4 5 pub fn Table(K: type, V: type, hash_fn: fn (K) u32, cmp_fn: fn (K, K) bool) type { 6 return struct { 7 const Self = @This(); 8 const MaxLoad: f32 = 0.75; 9 10 pub const Error = error{ OutOfMemory, KeyError }; 11 12 pub const Key = K; 13 pub const Value = V; 14 15 pub const Entry = union(enum) { 16 const Some = struct { 17 key: K, 18 value: V, 19 }; 20 some: Some, 21 none, 22 tomb, 23 }; 24 25 count: usize, 26 entries: []Entry, 27 allocator: std.mem.Allocator, 28 29 pub fn init(allocator: std.mem.Allocator) Self { 30 return Self{ .count = 0, .entries = &.{}, .allocator = allocator }; 31 } 32 33 fn growCapacity(self: *const Self) usize { 34 return if (self.entries.len > 0) 35 self.entries.len * 2 36 else 37 10; 38 } 39 40 fn adjustCapacity(self: *Self, newsize: usize) Error!void { 41 const entries = try self.allocator.alloc(Entry, newsize); 42 for (entries) |*entry| { 43 entry.* = .none; 44 } 45 self.count = 0; 46 for (self.entries) |entry| { 47 switch (entry) { 48 .some => |some| { 49 find(entries, some.key).* = entry; 50 self.count += 1; 51 }, 52 else => {}, 53 } 54 } 55 self.allocator.free(self.entries); 56 self.entries = entries; 57 } 58 pub fn find_check(key: K) struct { 59 k: K, 60 pub fn check(self: *const @This(), k2: K) bool { 61 return cmp_fn(self.k, k2); 62 } 63 } { 64 return @TypeOf(find_check(key)){ .k = key }; 65 } 66 67 pub fn find(entries: []Entry, key: K) *Entry { 68 return find_(entries, hash_fn(key), find_check(key)); 69 } 70 71 pub fn find_(entries: []Entry, hash: u32, check: anytype) *Entry { 72 var idx = hash % entries.len; 73 var tomb: ?*Entry = null; 74 75 while (true) { 76 const entry = &entries[idx]; 77 switch (entry.*) { 78 .some => |some| if (check.check(some.key)) return entry, 79 .tomb => tomb = if (tomb) |t| t else entry, 80 .none => return if (tomb) |t| t else entry, 81 } 82 idx = (idx + 1) % entries.len; 83 } 84 } 85 86 pub fn addAll(self: *Self, other: *const Self) Error!void { 87 for (other.entries) |entry| { 88 switch (entry) { 89 .some => |some| _ = try self.set(some.key, some.value), 90 else => {}, 91 } 92 } 93 } 94 95 pub fn for_each(self: *const Self, arg: anytype, fun: if (@TypeOf(arg) == void) fn (K, V) void else fn (@TypeOf(arg), K, V) void) void { 96 for (self.entries) |entry| { 97 switch (entry) { 98 .some => |some| if (@TypeOf(arg) == void) 99 fun(some.key, some.value) 100 else 101 fun(arg, some.key, some.value), 102 else => {}, 103 } 104 } 105 } 106 107 pub fn for_each_try(self: *const Self, arg: anytype, fun: anytype) utils.fn_error(fun).?!void { 108 for (self.entries) |entry| { 109 switch (entry) { 110 .some => |some| if (@TypeOf(arg) == void) 111 try fun(some.key, some.value) 112 else 113 try fun(arg, some.key, some.value), 114 else => {}, 115 } 116 } 117 } 118 119 pub fn set_(self: *Self, entry: *Entry, key: K, val: V) bool { 120 const isNewKey = switch (entry.*) { 121 .none => blk: { 122 self.count += 1; 123 break :blk true; 124 }, 125 .tomb => true, 126 .some => false, 127 }; 128 129 entry.* = Entry{ .some = Entry.Some{ .key = key, .value = val } }; 130 return isNewKey; 131 } 132 133 pub fn eql(self: *const Self, other: *const Self, cmpval_fn: fn (V, V) bool) bool { 134 for (self.entries) |entry| { 135 switch (entry) { 136 .some => |some| { 137 switch (find(other.entries, some.key).*) { 138 .some => |some2| if (!cmpval_fn(some.value, some2.value)) { 139 return false; 140 }, 141 else => return false, 142 } 143 }, 144 else => {}, 145 } 146 } 147 return true; 148 } 149 150 pub fn checkCapacity(self: *Self) Error!void { 151 const len: f32 = @floatFromInt(self.entries.len); 152 const count: f32 = @floatFromInt(self.count); 153 if (count + 1.0 > len * MaxLoad) { 154 try self.adjustCapacity(self.growCapacity()); 155 } 156 } 157 158 pub fn set(self: *Self, key: K, val: V) Error!bool { 159 try self.checkCapacity(); 160 return self.set_(find(self.entries, key), key, val); 161 } 162 163 pub fn retset(self: *Self, key: K, val: V) Error!V { 164 try self.checkCapacity(); 165 _ = self.set_(find(self.entries, key), key, val); 166 return val; 167 } 168 169 pub fn replace(self: *Self, key: K, val: V) Error!void { 170 if (self.entries.len == 0) 171 return Error.KeyError; 172 173 const entry = find(self.entries, key); 174 switch (entry.*) { 175 .some => _ = self.set_(entry, key, val), 176 else => return Error.KeyError, 177 } 178 } 179 180 pub fn replace_if(self: *Self, key: K, val: V, fun: fn (V) bool) Error!bool { 181 if (self.entries.len == 0) 182 return Error.KeyError; 183 184 const entry = find(self.entries, key); 185 switch (entry.*) { 186 .some => |some| return fun(some.value) and !self.set_(entry, key, val), 187 else => return Error.KeyError, 188 } 189 } 190 191 pub fn get(self: *const Self, key: K) Error!V { 192 if (self.entries.len == 0) 193 return Error.KeyError; 194 195 return switch (find(self.entries, key).*) { 196 .some => |some| some.value, 197 else => Error.KeyError, 198 }; 199 } 200 201 pub fn gorset(self: *Self, key: K, val: V) Error!V { 202 return self.get(key) catch |err| switch (err) { 203 Error.KeyError => blk: { 204 _ = try self.set(key, val); 205 break :blk val; 206 }, 207 else => err, 208 }; 209 } 210 211 pub fn delete(self: *Self, key: K) bool { 212 if (self.entries.len == 0) return false; 213 214 const entry = find(self.entries, key); 215 switch (entry.*) { 216 .some => entry.* = .tomb, 217 else => return false, 218 } 219 220 return true; 221 } 222 223 pub fn deinit(self: *@This()) void { 224 if (self.entries.len > 0) { 225 self.allocator.free(self.entries); 226 self.entries = &.{}; 227 self.count = 0; 228 } 229 } 230 }; 231 }