IstrSet can resize now.

1 files changed, 48 insertions, 23 deletions

diff --git a/src/zisp/gc/IstrSet.zig b/src/zisp/gc/IstrSet.zig
index 0176291..05a2911 100644
--- a/src/zisp/gc/IstrSet.zig
+++ b/src/zisp/gc/IstrSet.zig
@@ -38,20 +38,20 @@ const Set = @This();
 
 const Bucket = [2][4]u64;
 
-// This is really just the head of the sector, but contains functions to
-// manipulate the entire contents.
-const Sector = *align(8) packed union {
+const SectorPtr = *align(8) SectorHead;
+
+const SectorHead = packed union {
     hash: u64,
     meta: packed struct(u64) {
         len: u8,
         _: u56,
     },
 
-    fn bufU64(self: *@This()) [*]u64 {
+    fn bufU64(self: SectorPtr) [*]u64 {
         return @ptrCast(self);
     }
 
-    fn getIstrPtr(self: *@This()) IstrPtr {
+    fn getIstrPtr(self: SectorPtr) IstrPtr {
         if (self.meta.len <= 24) {
             return @ptrCast(self);
         } else {
@@ -59,7 +59,7 @@ const Sector = *align(8) packed union {
         }
     }
 
-    pub fn match(self: *@This(), hash: u64, s: []const u8) ?IstrPtr {
+    pub fn match(self: SectorPtr, hash: u64, s: []const u8) ?IstrPtr {
         if (self.hash != hash) {
             return null;
         }
@@ -72,7 +72,7 @@ const Sector = *align(8) packed union {
     }
 
     pub fn insert(
-        self: *@This(),
+        self: SectorPtr,
         alloc: Alloc,
         hash: u64,
         s: []const u8,
@@ -88,9 +88,13 @@ const Sector = *align(8) packed union {
             return istr;
         }
     }
+
+    pub fn copy(self: SectorPtr, dest: SectorPtr) void {
+        @memcpy(dest.bufU64()[0..4], self.bufU64()[0..4]);
+    }
 };
 
-buckets: []Bucket = &.{},
+buckets: []Bucket,
 
 const default_bcount = 512;
 
@@ -99,23 +103,21 @@ pub fn init(alloc: Alloc) !Set {
 }
 
 pub fn initCustom(alloc: Alloc, bcount: usize) !Set {
-    var set = Set{};
-    try set.realloc(alloc, bcount);
-    return set;
+    return Set{ .buckets = try allocBuckets(alloc, bcount) };
 }
 
-fn realloc(self: *Set, alloc: Alloc, bcount: usize) !void {
-    alloc.free(self.buckets);
-    self.buckets = try alloc.alloc(Bucket, bcount);
-    @memset(self.buckets, std.mem.zeroes(Bucket));
+fn allocBuckets(alloc: Alloc, bcount: usize) ![]Bucket {
+    const bs = try alloc.alloc(Bucket, bcount);
+    @memset(bs, std.mem.zeroes(Bucket));
+    return bs;
 }
 
 pub fn deinit(self: *Set, alloc: Alloc) void {
     alloc.free(self.buckets);
 }
 
-fn sector(set: *Set, b_idx: usize, s_idx: usize) Sector {
-    return @ptrCast(&set.buckets[b_idx][s_idx]);
+fn sector(bs: []Bucket, b_idx: usize, s_idx: usize) SectorPtr {
+    return @ptrCast(&bs[b_idx][s_idx]);
 }
 
 /// Add, or get existing, string.
@@ -134,22 +136,45 @@ pub fn add(self: *Set, alloc: Alloc, s: []const u8) !IstrPtr {
     var idx = @as(usize, @truncate(hash & idx_mask));
     const s_idx = b: while (true) : (idx = (idx + 1) & idx_mask) {
         inline for (0..1) |i| {
-            const sec = sector(self, idx, i);
+            const sec = sector(self.buckets, idx, i);
             if (sec.hash == 0) break :b i;
             if (sec.match(hash, s)) |istr| return istr;
         }
         probes += 1;
         if (probes > probe_limit) {
-            self.resize();
+            try self.resize(alloc);
             return self.add(alloc, s);
         }
     };
 
-    const sec = sector(self, idx, s_idx);
+    const sec = sector(self.buckets, idx, s_idx);
     return sec.insert(alloc, hash, s);
 }
 
-fn resize(self: *Set) void {
-    _ = self;
-    @panic("IstrSet resize not implemented.");
+fn resize(self: *Set, alloc: Alloc) !void {
+    const new_bc = self.buckets.len << 1;
+    const new_bs = try allocBuckets(alloc, new_bc);
+    @memset(new_bs, std.mem.zeroes(Bucket));
+
+    const idx_mask = new_bc - 1;
+
+    for (self.buckets, 0..) |_, idx| {
+        inline for (0..1) |s_idx| {
+            const sec = sector(self.buckets, idx, s_idx);
+            if (sec.hash != 0) transfer(sec, new_bs, idx_mask);
+        }
+    }
+
+    alloc.free(self.buckets);
+    self.buckets = new_bs;
+}
+
+fn transfer(sec: SectorPtr, new_bs: []Bucket, idx_mask: usize) void {
+    var new_idx = @as(usize, @truncate(sec.hash & idx_mask));
+    while (true) : (new_idx = (new_idx + 1) & idx_mask) {
+        inline for (0..1) |new_s_idx| {
+            const new_sec = sector(new_bs, new_idx, new_s_idx);
+            if (new_sec.hash == 0) return sec.copy(new_sec);
+        }
+    }
 }