feat: finish ghostty pane backend integration

1 files changed, 1540 insertions, 0 deletions

diff --git a/vendor/libghostty-vt/src/terminal/hash_map.zig b/vendor/libghostty-vt/src/terminal/hash_map.zig
new file mode 100644
index 00000000..5a38cc17
--- /dev/null
+++ b/vendor/libghostty-vt/src/terminal/hash_map.zig
@@ -0,0 +1,1540 @@
+//! This file contains a fork of the Zig stdlib HashMap implementation tuned
+//! for use with our terminal page representation.
+//!
+//! The main goal we need to achieve that wasn't possible with the stdlib
+//! HashMap is to utilize offsets rather than full pointers so that we can
+//! copy around the entire backing memory and keep the hash map working.
+//!
+//! Additionally, for serialization/deserialization purposes, we need to be
+//! able to create a HashMap instance and manually set the offsets up. The
+//! stdlib HashMap does not export Metadata so this isn't possible.
+//!
+//! Also, I want to be able to understand possible capacity for a given K,V
+//! type and fixed memory amount. The stdlib HashMap doesn't publish its
+//! internal allocation size calculation.
+//!
+//! Finally, I removed many of the APIs that we'll never require for our
+//! usage just so that this file is smaller, easier to understand, and has
+//! less opportunity for bugs.
+//!
+//! Besides these shortcomings, the stdlib HashMap has some great qualities
+//! that we want to keep, namely the fact that it is backed by a single large
+//! allocation rather than pointers to separate allocations. This is important
+//! because our terminal page representation is backed by a single large
+//! allocation so we can give the HashMap a slice of memory to operate in.
+//!
+//! I haven't carefully benchmarked this implementation against other hash
+//! map implementations. It's possible using some of the newer variants out
+//! there would be better. However, I trust the built-in version is pretty good
+//! and its more important to get the terminal page representation working
+//! first then we can measure and improve this later if we find it to be a
+//! bottleneck.
+
+const std = @import("std");
+const assert = @import("../quirks.zig").inlineAssert;
+const autoHash = std.hash.autoHash;
+const math = std.math;
+const mem = std.mem;
+const Allocator = mem.Allocator;
+const Wyhash = std.hash.Wyhash;
+
+const Offset = @import("size.zig").Offset;
+const OffsetBuf = @import("size.zig").OffsetBuf;
+const getOffset = @import("size.zig").getOffset;
+
+pub fn AutoOffsetHashMap(comptime K: type, comptime V: type) type {
+    return OffsetHashMap(K, V, AutoContext(K));
+}
+
+fn AutoHashMapUnmanaged(comptime K: type, comptime V: type) type {
+    return HashMapUnmanaged(K, V, AutoContext(K));
+}
+
+fn AutoContext(comptime K: type) type {
+    return struct {
+        pub const hash = std.hash_map.getAutoHashFn(K, @This());
+        pub const eql = std.hash_map.getAutoEqlFn(K, @This());
+    };
+}
+
+/// A HashMap type that uses offsets rather than pointers, making it
+/// possible to efficiently move around the backing memory without
+/// invalidating the HashMap.
+pub fn OffsetHashMap(
+    comptime K: type,
+    comptime V: type,
+    comptime Context: type,
+) type {
+    return struct {
+        const Self = @This();
+
+        /// This is the pointer-based map that we're wrapping.
+        pub const Unmanaged = HashMapUnmanaged(K, V, Context);
+        pub const Layout = Unmanaged.Layout;
+
+        /// This is the alignment that the base pointer must have.
+        pub const base_align = Unmanaged.base_align;
+
+        metadata: Offset(Unmanaged.Metadata) = .{},
+
+        /// Returns the total size of the backing memory required for a
+        /// HashMap with the given capacity. The base ptr must also be
+        /// aligned to base_align.
+        pub fn layout(cap: Unmanaged.Size) Layout {
+            return Unmanaged.layoutForCapacity(cap);
+        }
+
+        /// Initialize a new HashMap with the given capacity and backing
+        /// memory. The backing memory must be aligned to base_align.
+        pub fn init(buf: OffsetBuf, l: Layout) Self {
+            assert(base_align.check(@intFromPtr(buf.start())));
+
+            const m = Unmanaged.init(buf, l);
+            return .{ .metadata = getOffset(
+                Unmanaged.Metadata,
+                buf,
+                @ptrCast(m.metadata.?),
+            ) };
+        }
+
+        /// Returns the pointer-based map from a base pointer.
+        pub fn map(self: Self, base: anytype) Unmanaged {
+            return .{ .metadata = self.metadata.ptr(base) };
+        }
+    };
+}
+
+/// Fork of stdlib.HashMap as of Zig 0.12 modified to use offsets for
+/// the key/values pointer. The metadata is still a pointer to limit
+/// the amount of arithmetic required to access it. See the file comment
+/// for full details.
+fn HashMapUnmanaged(
+    comptime K: type,
+    comptime V: type,
+    comptime Context: type,
+) type {
+    return struct {
+        const Self = @This();
+
+        comptime {
+            assert(@alignOf(Metadata) == 1);
+        }
+
+        const header_align = @alignOf(Header);
+        const key_align = if (@sizeOf(K) == 0) 1 else @alignOf(K);
+        const val_align = if (@sizeOf(V) == 0) 1 else @alignOf(V);
+        const base_align: mem.Alignment = .fromByteUnits(@max(
+            header_align,
+            key_align,
+            val_align,
+        ));
+
+        // This is actually a midway pointer to the single buffer containing
+        // a `Header` field, the `Metadata`s and `Entry`s.
+        // At `-@sizeOf(Header)` is the Header field.
+        // At `sizeOf(Metadata) * capacity + offset`, which is pointed to by
+        // self.header().entries, is the array of entries.
+        // This means that the hashmap only holds one live allocation, to
+        // reduce memory fragmentation and struct size.
+        /// Pointer to the metadata.
+        metadata: ?[*]Metadata = null,
+
+        // This is purely empirical and not a /very smart magic constant™/.
+        /// Capacity of the first grow when bootstrapping the hashmap.
+        const minimal_capacity = 8;
+
+        // This hashmap is specially designed for sizes that fit in a u32.
+        pub const Size = u32;
+
+        // u64 hashes guarantee us that the fingerprint bits will never be used
+        // to compute the index of a slot, maximizing the use of entropy.
+        pub const Hash = u64;
+
+        pub const Entry = struct {
+            key_ptr: *K,
+            value_ptr: *V,
+        };
+
+        pub const KV = struct {
+            key: K,
+            value: V,
+        };
+
+        const Header = struct {
+            /// The keys/values offset are relative to the metadata
+            values: Offset(V),
+            keys: Offset(K),
+            capacity: Size,
+            size: Size,
+        };
+
+        /// Metadata for a slot. It can be in three states: empty, used or
+        /// tombstone. Tombstones indicate that an entry was previously used,
+        /// they are a simple way to handle removal.
+        /// To this state, we add 7 bits from the slot's key hash. These are
+        /// used as a fast way to disambiguate between entries without
+        /// having to use the equality function. If two fingerprints are
+        /// different, we know that we don't have to compare the keys at all.
+        /// The 7 bits are the highest ones from a 64 bit hash. This way, not
+        /// only we use the `log2(capacity)` lowest bits from the hash to determine
+        /// a slot index, but we use 7 more bits to quickly resolve collisions
+        /// when multiple elements with different hashes end up wanting to be in the same slot.
+        /// Not using the equality function means we don't have to read into
+        /// the entries array, likely avoiding a cache miss and a potentially
+        /// costly function call.
+        const Metadata = packed struct {
+            const FingerPrint = u7;
+
+            const free: FingerPrint = 0;
+            const tombstone: FingerPrint = 1;
+
+            fingerprint: FingerPrint = free,
+            used: u1 = 0,
+
+            const slot_free = @as(u8, @bitCast(Metadata{ .fingerprint = free }));
+            const slot_tombstone = @as(u8, @bitCast(Metadata{ .fingerprint = tombstone }));
+
+            pub fn isUsed(self: Metadata) bool {
+                return self.used == 1;
+            }
+
+            pub fn isTombstone(self: Metadata) bool {
+                return @as(u8, @bitCast(self)) == slot_tombstone;
+            }
+
+            pub fn isFree(self: Metadata) bool {
+                return @as(u8, @bitCast(self)) == slot_free;
+            }
+
+            pub fn takeFingerprint(hash: Hash) FingerPrint {
+                const hash_bits = @typeInfo(Hash).int.bits;
+                const fp_bits = @typeInfo(FingerPrint).int.bits;
+                return @as(FingerPrint, @truncate(hash >> (hash_bits - fp_bits)));
+            }
+
+            pub fn fill(self: *Metadata, fp: FingerPrint) void {
+                self.used = 1;
+                self.fingerprint = fp;
+            }
+
+            pub fn remove(self: *Metadata) void {
+                self.used = 0;
+                self.fingerprint = tombstone;
+            }
+        };
+
+        comptime {
+            assert(@sizeOf(Metadata) == 1);
+            assert(@alignOf(Metadata) == 1);
+        }
+
+        pub const Iterator = struct {
+            hm: *const Self,
+            index: Size = 0,
+
+            pub fn next(it: *Iterator) ?Entry {
+                assert(it.index <= it.hm.capacity());
+                if (it.hm.header().size == 0) return null;
+
+                const cap = it.hm.capacity();
+                const end = it.hm.metadata.? + cap;
+                var metadata = it.hm.metadata.? + it.index;
+
+                while (metadata != end) : ({
+                    metadata += 1;
+                    it.index += 1;
+                }) {
+                    if (metadata[0].isUsed()) {
+                        const key = &it.hm.keys()[it.index];
+                        const value = &it.hm.values()[it.index];
+                        it.index += 1;
+                        return Entry{ .key_ptr = key, .value_ptr = value };
+                    }
+                }
+
+                return null;
+            }
+        };
+
+        pub const KeyIterator = FieldIterator(K);
+        pub const ValueIterator = FieldIterator(V);
+
+        fn FieldIterator(comptime T: type) type {
+            return struct {
+                len: usize,
+                metadata: [*]const Metadata,
+                items: [*]T,
+
+                pub fn next(self: *@This()) ?*T {
+                    while (self.len > 0) {
+                        self.len -= 1;
+                        const used = self.metadata[0].isUsed();
+                        const item = &self.items[0];
+                        self.metadata += 1;
+                        self.items += 1;
+                        if (used) {
+                            return item;
+                        }
+                    }
+                    return null;
+                }
+            };
+        }
+
+        pub const GetOrPutResult = struct {
+            key_ptr: *K,
+            value_ptr: *V,
+            found_existing: bool,
+        };
+
+        /// Initialize a hash map with a given capacity and a buffer. The
+        /// buffer must fit within the size defined by `layoutForCapacity`.
+        pub fn init(buf: OffsetBuf, layout: Layout) Self {
+            assert(base_align.check(@intFromPtr(buf.start())));
+
+            // Get all our main pointers
+            const metadata_buf = buf.rebase(@sizeOf(Header));
+            const metadata_ptr: [*]Metadata = @ptrCast(metadata_buf.start());
+
+            // Build our map
+            var map: Self = .{ .metadata = metadata_ptr };
+            const hdr = map.header();
+            hdr.capacity = layout.capacity;
+            hdr.size = 0;
+            if (@sizeOf([*]K) != 0) hdr.keys = metadata_buf.member(K, layout.keys_start);
+            if (@sizeOf([*]V) != 0) hdr.values = metadata_buf.member(V, layout.vals_start);
+            map.initMetadatas();
+
+            return map;
+        }
+
+        pub fn ensureTotalCapacity(self: *Self, new_size: Size) Allocator.Error!void {
+            if (new_size > self.header().size) {
+                try self.growIfNeeded(new_size - self.header().size);
+            }
+        }
+
+        pub fn ensureUnusedCapacity(self: *Self, additional_size: Size) Allocator.Error!void {
+            return ensureTotalCapacity(self, self.count() + additional_size);
+        }
+
+        pub fn clearRetainingCapacity(self: *Self) void {
+            if (self.metadata) |_| {
+                self.initMetadatas();
+                self.header().size = 0;
+            }
+        }
+
+        pub fn count(self: *const Self) Size {
+            return self.header().size;
+        }
+
+        fn header(self: *const Self) *Header {
+            return @ptrCast(@as([*]Header, @ptrCast(@alignCast(self.metadata.?))) - 1);
+        }
+
+        fn keys(self: *const Self) [*]K {
+            return self.header().keys.ptr(self.metadata.?);
+        }
+
+        fn values(self: *const Self) [*]V {
+            return self.header().values.ptr(self.metadata.?);
+        }
+
+        pub fn capacity(self: *const Self) Size {
+            if (self.metadata == null) return 0;
+
+            return self.header().capacity;
+        }
+
+        pub fn iterator(self: *const Self) Iterator {
+            return .{ .hm = self };
+        }
+
+        pub fn keyIterator(self: *const Self) KeyIterator {
+            if (self.metadata) |metadata| {
+                return .{
+                    .len = self.capacity(),
+                    .metadata = metadata,
+                    .items = self.keys(),
+                };
+            } else {
+                return .{
+                    .len = 0,
+                    .metadata = undefined,
+                    .items = undefined,
+                };
+            }
+        }
+
+        pub fn valueIterator(self: *const Self) ValueIterator {
+            if (self.metadata) |metadata| {
+                return .{
+                    .len = self.capacity(),
+                    .metadata = metadata,
+                    .items = self.values(),
+                };
+            } else {
+                return .{
+                    .len = 0,
+                    .metadata = undefined,
+                    .items = undefined,
+                };
+            }
+        }
+
+        /// Insert an entry in the map. Assumes it is not already present.
+        pub fn putNoClobber(self: *Self, key: K, value: V) Allocator.Error!void {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putNoClobberContext instead.");
+            return self.putNoClobberContext(key, value, undefined);
+        }
+        pub fn putNoClobberContext(self: *Self, key: K, value: V, ctx: Context) Allocator.Error!void {
+            assert(!self.containsContext(key, ctx));
+            try self.growIfNeeded(1);
+
+            self.putAssumeCapacityNoClobberContext(key, value, ctx);
+        }
+
+        /// Asserts there is enough capacity to store the new key-value pair.
+        /// Clobbers any existing data. To detect if a put would clobber
+        /// existing data, see `getOrPutAssumeCapacity`.
+        pub fn putAssumeCapacity(self: *Self, key: K, value: V) void {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putAssumeCapacityContext instead.");
+            return self.putAssumeCapacityContext(key, value, undefined);
+        }
+        pub fn putAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) void {
+            const gop = self.getOrPutAssumeCapacityContext(key, ctx);
+            gop.value_ptr.* = value;
+        }
+
+        /// Insert an entry in the map. Assumes it is not already present,
+        /// and that no allocation is needed.
+        pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putAssumeCapacityNoClobberContext instead.");
+            return self.putAssumeCapacityNoClobberContext(key, value, undefined);
+        }
+        pub fn putAssumeCapacityNoClobberContext(self: *Self, key: K, value: V, ctx: Context) void {
+            assert(!self.containsContext(key, ctx));
+
+            const hash = ctx.hash(key);
+            const mask = self.capacity() - 1;
+            var idx = @as(usize, @truncate(hash & mask));
+
+            var metadata = self.metadata.? + idx;
+            while (metadata[0].isUsed()) {
+                idx = (idx + 1) & mask;
+                metadata = self.metadata.? + idx;
+            }
+
+            const fingerprint = Metadata.takeFingerprint(hash);
+            metadata[0].fill(fingerprint);
+            self.keys()[idx] = key;
+            self.values()[idx] = value;
+            self.header().size += 1;
+        }
+
+        /// Inserts a new `Entry` into the hash map, returning the previous one, if any.
+        pub fn fetchPut(self: *Self, key: K, value: V) Allocator.Error!?KV {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutContext instead.");
+            return self.fetchPutContext(key, value, undefined);
+        }
+        pub fn fetchPutContext(self: *Self, key: K, value: V, ctx: Context) Allocator.Error!?KV {
+            const gop = try self.getOrPutContext(key, ctx);
+            var result: ?KV = null;
+            if (gop.found_existing) {
+                result = KV{
+                    .key = gop.key_ptr.*,
+                    .value = gop.value_ptr.*,
+                };
+            }
+            gop.value_ptr.* = value;
+            return result;
+        }
+
+        /// Inserts a new `Entry` into the hash map, returning the previous one, if any.
+        /// If insertion happens, asserts there is enough capacity without allocating.
+        pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutAssumeCapacityContext instead.");
+            return self.fetchPutAssumeCapacityContext(key, value, undefined);
+        }
+        pub fn fetchPutAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) ?KV {
+            const gop = self.getOrPutAssumeCapacityContext(key, ctx);
+            var result: ?KV = null;
+            if (gop.found_existing) {
+                result = KV{
+                    .key = gop.key_ptr.*,
+                    .value = gop.value_ptr.*,
+                };
+            }
+            gop.value_ptr.* = value;
+            return result;
+        }
+
+        /// If there is an `Entry` with a matching key, it is deleted from
+        /// the hash map, and then returned from this function.
+        pub fn fetchRemove(self: *Self, key: K) ?KV {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchRemoveContext instead.");
+            return self.fetchRemoveContext(key, undefined);
+        }
+        pub fn fetchRemoveContext(self: *Self, key: K, ctx: Context) ?KV {
+            return self.fetchRemoveAdapted(key, ctx);
+        }
+        pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
+            if (self.getIndex(key, ctx)) |idx| {
+                const old_key = &self.keys()[idx];
+                const old_val = &self.values()[idx];
+                const result = KV{
+                    .key = old_key.*,
+                    .value = old_val.*,
+                };
+                self.metadata.?[idx].remove();
+                old_key.* = undefined;
+                old_val.* = undefined;
+                self.header().size -= 1;
+                return result;
+            }
+
+            return null;
+        }
+
+        /// Find the index containing the data for the given key.
+        /// Whether this function returns null is almost always
+        /// branched on after this function returns, and this function
+        /// returns null/not null from separate code paths.  We
+        /// want the optimizer to remove that branch and instead directly
+        /// fuse the basic blocks after the branch to the basic blocks
+        /// from this function.  To encourage that, this function is
+        /// marked as inline.
+        inline fn getIndex(self: Self, key: anytype, ctx: anytype) ?usize {
+            if (self.header().size == 0) {
+                return null;
+            }
+
+            // If you get a compile error on this line, it means that your generic hash
+            // function is invalid for these parameters.
+            const hash = ctx.hash(key);
+            if (@TypeOf(hash) != Hash) {
+                @compileError("Context " ++ @typeName(@TypeOf(ctx)) ++ " has a generic hash function that returns the wrong type! " ++ @typeName(Hash) ++ " was expected, but found " ++ @typeName(@TypeOf(hash)));
+            }
+            const mask = self.capacity() - 1;
+            const fingerprint = Metadata.takeFingerprint(hash);
+            // Don't loop indefinitely when there are no empty slots.
+            var limit = self.capacity();
+            var idx = @as(usize, @truncate(hash & mask));
+
+            var metadata = self.metadata.? + idx;
+            while (!metadata[0].isFree() and limit != 0) {
+                if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
+                    const test_key = &self.keys()[idx];
+                    // If you get a compile error on this line, it means that your generic eql
+                    // function is invalid for these parameters.
+                    const eql = ctx.eql(key, test_key.*);
+                    // verifyContext can't verify the return type of generic eql functions,
+                    // so we need to double-check it here.
+                    if (@TypeOf(eql) != bool) {
+                        @compileError("Context " ++ @typeName(@TypeOf(ctx)) ++ " has a generic eql function that returns the wrong type! bool was expected, but found " ++ @typeName(@TypeOf(eql)));
+                    }
+                    if (eql) {
+                        return idx;
+                    }
+                }
+
+                limit -= 1;
+                idx = (idx + 1) & mask;
+                metadata = self.metadata.? + idx;
+            }
+
+            return null;
+        }
+
+        pub fn getEntry(self: Self, key: K) ?Entry {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getEntryContext instead.");
+            return self.getEntryContext(key, undefined);
+        }
+        pub fn getEntryContext(self: Self, key: K, ctx: Context) ?Entry {
+            return self.getEntryAdapted(key, ctx);
+        }
+        pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry {
+            if (self.getIndex(key, ctx)) |idx| {
+                return Entry{
+                    .key_ptr = &self.keys()[idx],
+                    .value_ptr = &self.values()[idx],
+                };
+            }
+            return null;
+        }
+
+        /// Insert an entry if the associated key is not already present, otherwise update preexisting value.
+        pub fn put(self: *Self, key: K, value: V) Allocator.Error!void {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putContext instead.");
+            return self.putContext(key, value, undefined);
+        }
+        pub fn putContext(self: *Self, key: K, value: V, ctx: Context) Allocator.Error!void {
+            const result = try self.getOrPutContext(key, ctx);
+            result.value_ptr.* = value;
+        }
+
+        /// Get an optional pointer to the actual key associated with adapted key, if present.
+        pub fn getKeyPtr(self: Self, key: K) ?*K {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getKeyPtrContext instead.");
+            return self.getKeyPtrContext(key, undefined);
+        }
+        pub fn getKeyPtrContext(self: Self, key: K, ctx: Context) ?*K {
+            return self.getKeyPtrAdapted(key, ctx);
+        }
+        pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K {
+            if (self.getIndex(key, ctx)) |idx| {
+                return &self.keys()[idx];
+            }
+            return null;
+        }
+
+        /// Get a copy of the actual key associated with adapted key, if present.
+        pub fn getKey(self: Self, key: K) ?K {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getKeyContext instead.");
+            return self.getKeyContext(key, undefined);
+        }
+        pub fn getKeyContext(self: Self, key: K, ctx: Context) ?K {
+            return self.getKeyAdapted(key, ctx);
+        }
+        pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K {
+            if (self.getIndex(key, ctx)) |idx| {
+                return self.keys()[idx];
+            }
+            return null;
+        }
+
+        /// Get an optional pointer to the value associated with key, if present.
+        pub fn getPtr(self: Self, key: K) ?*V {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getPtrContext instead.");
+            return self.getPtrContext(key, undefined);
+        }
+        pub fn getPtrContext(self: Self, key: K, ctx: Context) ?*V {
+            return self.getPtrAdapted(key, ctx);
+        }
+        pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V {
+            if (self.getIndex(key, ctx)) |idx| {
+                return &self.values()[idx];
+            }
+            return null;
+        }
+
+        /// Get a copy of the value associated with key, if present.
+        pub fn get(self: Self, key: K) ?V {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getContext instead.");
+            return self.getContext(key, undefined);
+        }
+        pub fn getContext(self: Self, key: K, ctx: Context) ?V {
+            return self.getAdapted(key, ctx);
+        }
+        pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V {
+            if (self.getIndex(key, ctx)) |idx| {
+                return self.values()[idx];
+            }
+            return null;
+        }
+
+        pub fn getOrPut(self: *Self, key: K) Allocator.Error!GetOrPutResult {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContext instead.");
+            return self.getOrPutContext(key, undefined);
+        }
+        pub fn getOrPutContext(self: *Self, key: K, ctx: Context) Allocator.Error!GetOrPutResult {
+            const gop = try self.getOrPutContextAdapted(key, ctx);
+            if (!gop.found_existing) {
+                gop.key_ptr.* = key;
+            }
+            return gop;
+        }
+        pub fn getOrPutAdapted(self: *Self, key: anytype, key_ctx: anytype) Allocator.Error!GetOrPutResult {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContextAdapted instead.");
+            return self.getOrPutContextAdapted(key, key_ctx);
+        }
+        pub fn getOrPutContextAdapted(self: *Self, key: anytype, key_ctx: anytype) Allocator.Error!GetOrPutResult {
+            self.growIfNeeded(1) catch |err| {
+                // If allocation fails, try to do the lookup anyway.
+                // If we find an existing item, we can return it.
+                // Otherwise return the error, we could not add another.
+                const index = self.getIndex(key, key_ctx) orelse return err;
+                return GetOrPutResult{
+                    .key_ptr = &self.keys()[index],
+                    .value_ptr = &self.values()[index],
+                    .found_existing = true,
+                };
+            };
+            return self.getOrPutAssumeCapacityAdapted(key, key_ctx);
+        }
+
+        pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutAssumeCapacityContext instead.");
+            return self.getOrPutAssumeCapacityContext(key, undefined);
+        }
+        pub fn getOrPutAssumeCapacityContext(self: *Self, key: K, ctx: Context) GetOrPutResult {
+            const result = self.getOrPutAssumeCapacityAdapted(key, ctx);
+            if (!result.found_existing) {
+                result.key_ptr.* = key;
+            }
+            return result;
+        }
+        pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult {
+            // If you get a compile error on this line, it means that your generic hash
+            // function is invalid for these parameters.
+            const hash = ctx.hash(key);
+            // verifyContext can't verify the return type of generic hash functions,
+            // so we need to double-check it here.
+            if (@TypeOf(hash) != Hash) {
+                @compileError("Context " ++ @typeName(@TypeOf(ctx)) ++ " has a generic hash function that returns the wrong type! " ++ @typeName(Hash) ++ " was expected, but found " ++ @typeName(@TypeOf(hash)));
+            }
+            const mask = self.capacity() - 1;
+            const fingerprint = Metadata.takeFingerprint(hash);
+            var limit = self.capacity();
+            var idx = @as(usize, @truncate(hash & mask));
+
+            var first_tombstone_idx: usize = self.capacity(); // invalid index
+            var metadata = self.metadata.? + idx;
+            while (!metadata[0].isFree() and limit != 0) {
+                if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
+                    const test_key = &self.keys()[idx];
+                    // If you get a compile error on this line, it means that your generic eql
+                    // function is invalid for these parameters.
+                    const eql = ctx.eql(key, test_key.*);
+                    // verifyContext can't verify the return type of generic eql functions,
+                    // so we need to double-check it here.
+                    if (@TypeOf(eql) != bool) {
+                        @compileError("Context " ++ @typeName(@TypeOf(ctx)) ++ " has a generic eql function that returns the wrong type! bool was expected, but found " ++ @typeName(@TypeOf(eql)));
+                    }
+                    if (eql) {
+                        return GetOrPutResult{
+                            .key_ptr = test_key,
+                            .value_ptr = &self.values()[idx],
+                            .found_existing = true,
+                        };
+                    }
+                } else if (first_tombstone_idx == self.capacity() and metadata[0].isTombstone()) {
+                    first_tombstone_idx = idx;
+                }
+
+                limit -= 1;
+                idx = (idx + 1) & mask;
+                metadata = self.metadata.? + idx;
+            }
+
+            if (first_tombstone_idx < self.capacity()) {
+                // Cheap try to lower probing lengths after deletions. Recycle a tombstone.
+                idx = first_tombstone_idx;
+                metadata = self.metadata.? + idx;
+            }
+
+            metadata[0].fill(fingerprint);
+            const new_key = &self.keys()[idx];
+            const new_value = &self.values()[idx];
+            new_key.* = undefined;
+            new_value.* = undefined;
+            self.header().size += 1;
+
+            return GetOrPutResult{
+                .key_ptr = new_key,
+                .value_ptr = new_value,
+                .found_existing = false,
+            };
+        }
+
+        pub fn getOrPutValue(self: *Self, key: K, value: V) Allocator.Error!Entry {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutValueContext instead.");
+            return self.getOrPutValueContext(key, value, undefined);
+        }
+        pub fn getOrPutValueContext(self: *Self, key: K, value: V, ctx: Context) Allocator.Error!Entry {
+            const res = try self.getOrPutAdapted(key, ctx);
+            if (!res.found_existing) {
+                res.key_ptr.* = key;
+                res.value_ptr.* = value;
+            }
+            return Entry{ .key_ptr = res.key_ptr, .value_ptr = res.value_ptr };
+        }
+
+        /// Return true if there is a value associated with key in the map.
+        pub fn contains(self: *const Self, key: K) bool {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call containsContext instead.");
+            return self.containsContext(key, undefined);
+        }
+        pub fn containsContext(self: *const Self, key: K, ctx: Context) bool {
+            return self.containsAdapted(key, ctx);
+        }
+        pub fn containsAdapted(self: *const Self, key: anytype, ctx: anytype) bool {
+            return self.getIndex(key, ctx) != null;
+        }
+
+        fn removeByIndex(self: *Self, idx: usize) void {
+            self.metadata.?[idx].remove();
+            self.keys()[idx] = undefined;
+            self.values()[idx] = undefined;
+            self.header().size -= 1;
+        }
+
+        /// If there is an `Entry` with a matching key, it is deleted from
+        /// the hash map, and this function returns true.  Otherwise this
+        /// function returns false.
+        pub fn remove(self: *Self, key: K) bool {
+            if (@sizeOf(Context) != 0)
+                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call removeContext instead.");
+            return self.removeContext(key, undefined);
+        }
+        pub fn removeContext(self: *Self, key: K, ctx: Context) bool {
+            return self.removeAdapted(key, ctx);
+        }
+        pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool {
+            if (self.getIndex(key, ctx)) |idx| {
+                self.removeByIndex(idx);
+                return true;
+            }
+
+            return false;
+        }
+
+        /// Delete the entry with key pointed to by key_ptr from the hash map.
+        /// key_ptr is assumed to be a valid pointer to a key that is present
+        /// in the hash map.
+        pub fn removeByPtr(self: *Self, key_ptr: *K) void {
+            // TODO: replace with pointer subtraction once supported by zig
+            // if @sizeOf(K) == 0 then there is at most one item in the hash
+            // map, which is assumed to exist as key_ptr must be valid.  This
+            // item must be at index 0.
+            const idx = if (@sizeOf(K) > 0)
+                (@intFromPtr(key_ptr) - @intFromPtr(self.keys())) / @sizeOf(K)
+            else
+                0;
+
+            self.removeByIndex(idx);
+        }
+
+        fn initMetadatas(self: *Self) void {
+            @memset(@as([*]u8, @ptrCast(self.metadata.?))[0 .. @sizeOf(Metadata) * self.capacity()], 0);
+        }
+
+        fn growIfNeeded(self: *Self, new_count: Size) Allocator.Error!void {
+            const available = self.capacity() - self.header().size;
+            if (new_count > available) return error.OutOfMemory;
+        }
+
+        /// The memory layout for the underlying buffer for a given capacity.
+        const Layout = struct {
+            /// The total size of the buffer required. The buffer is expected
+            /// to be aligned to `base_align`.
+            total_size: usize,
+
+            /// The offset to the start of the keys data.
+            keys_start: usize,
+
+            /// The offset to the start of the values data.
+            vals_start: usize,
+
+            /// The capacity that was used to calculate this layout.
+            capacity: Size,
+        };
+
+        /// Returns the memory layout for the buffer for a given capacity.
+        /// The actual size may be able to fit more than the given capacity
+        /// because capacity is rounded up to the next power of two. This is
+        /// a design requirement for this hash map implementation.
+        pub fn layoutForCapacity(new_capacity: Size) Layout {
+            assert(new_capacity == 0 or std.math.isPowerOfTwo(new_capacity));
+
+            // Cast to usize to prevent overflow in size calculations.
+            // See: https://github.com/ziglang/zig/pull/19048
+            const cap: usize = new_capacity;
+
+            // Pack our metadata, keys, and values.
+            const meta_start = @sizeOf(Header);
+            const meta_end = @sizeOf(Header) + cap * @sizeOf(Metadata);
+            const keys_start = std.mem.alignForward(usize, meta_end, key_align);
+            const keys_end = keys_start + cap * @sizeOf(K);
+            const vals_start = std.mem.alignForward(usize, keys_end, val_align);
+            const vals_end = vals_start + cap * @sizeOf(V);
+
+            // Our total memory size required is the end of our values
+            // aligned to the base required alignment.
+            const total_size = std.mem.alignForward(
+                usize,
+                vals_end,
+                base_align.toByteUnits(),
+            );
+
+            // The offsets we actually store in the map are from the
+            // metadata pointer so that we can use self.metadata as
+            // the base.
+            const keys_offset = keys_start - meta_start;
+            const vals_offset = vals_start - meta_start;
+
+            return .{
+                .total_size = total_size,
+                .keys_start = keys_offset,
+                .vals_start = vals_offset,
+                .capacity = new_capacity,
+            };
+        }
+    };
+}
+
+const testing = std.testing;
+const expect = std.testing.expect;
+const expectEqual = std.testing.expectEqual;
+
+test "HashMap basic usage" {
+    const Map = AutoHashMapUnmanaged(u32, u32);
+
+    const alloc = testing.allocator;
+    const cap = 16;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+
+    var map = Map.init(.init(buf), layout);
+
+    const count = 5;
+    var i: u32 = 0;
+    var total: u32 = 0;
+    while (i < count) : (i += 1) {
+        try map.put(i, i);
+        total += i;
+    }
+
+    var sum: u32 = 0;
+    var it = map.iterator();
+    while (it.next()) |kv| {
+        sum += kv.key_ptr.*;
+    }
+    try expectEqual(total, sum);
+
+    i = 0;
+    sum = 0;
+    while (i < count) : (i += 1) {
+        try expectEqual(i, map.get(i).?);
+        sum += map.get(i).?;
+    }
+    try expectEqual(total, sum);
+}
+
+test "HashMap ensureTotalCapacity" {
+    const Map = AutoHashMapUnmanaged(i32, i32);
+    const cap = 32;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    const initial_capacity = map.capacity();
+    try testing.expect(initial_capacity >= 20);
+    var i: i32 = 0;
+    while (i < 20) : (i += 1) {
+        try testing.expect(map.fetchPutAssumeCapacity(i, i + 10) == null);
+    }
+    // shouldn't resize from putAssumeCapacity
+    try testing.expect(initial_capacity == map.capacity());
+}
+
+test "HashMap ensureUnusedCapacity with tombstones" {
+    const Map = AutoHashMapUnmanaged(i32, i32);
+    const cap = 32;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    var i: i32 = 0;
+    while (i < 100) : (i += 1) {
+        try map.ensureUnusedCapacity(1);
+        map.putAssumeCapacity(i, i);
+        _ = map.remove(i);
+    }
+}
+
+test "HashMap clearRetainingCapacity" {
+    const Map = AutoHashMapUnmanaged(u32, u32);
+    const cap = 16;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    map.clearRetainingCapacity();
+
+    try map.put(1, 1);
+    try expectEqual(map.get(1).?, 1);
+    try expectEqual(map.count(), 1);
+
+    map.clearRetainingCapacity();
+    map.putAssumeCapacity(1, 1);
+    try expectEqual(map.get(1).?, 1);
+    try expectEqual(map.count(), 1);
+
+    const actual_cap = map.capacity();
+    try expect(actual_cap > 0);
+
+    map.clearRetainingCapacity();
+    map.clearRetainingCapacity();
+    try expectEqual(map.count(), 0);
+    try expectEqual(map.capacity(), actual_cap);
+    try expect(!map.contains(1));
+}
+
+test "HashMap ensureTotalCapacity with existing elements" {
+    const Map = AutoHashMapUnmanaged(u32, u32);
+    const cap = Map.minimal_capacity;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    try map.put(0, 0);
+    try expectEqual(map.count(), 1);
+    try expectEqual(map.capacity(), Map.minimal_capacity);
+
+    try testing.expectError(error.OutOfMemory, map.ensureTotalCapacity(65));
+    try expectEqual(map.count(), 1);
+    try expectEqual(map.capacity(), Map.minimal_capacity);
+}
+
+test "HashMap remove" {
+    const Map = AutoHashMapUnmanaged(u32, u32);
+    const cap = 32;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    var i: u32 = 0;
+    while (i < 16) : (i += 1) {
+        try map.put(i, i);
+    }
+
+    i = 0;
+    while (i < 16) : (i += 1) {
+        if (i % 3 == 0) {
+            _ = map.remove(i);
+        }
+    }
+    try expectEqual(map.count(), 10);
+    var it = map.iterator();
+    while (it.next()) |kv| {
+        try expectEqual(kv.key_ptr.*, kv.value_ptr.*);
+        try expect(kv.key_ptr.* % 3 != 0);
+    }
+
+    i = 0;
+    while (i < 16) : (i += 1) {
+        if (i % 3 == 0) {
+            try expect(!map.contains(i));
+        } else {
+            try expectEqual(map.get(i).?, i);
+        }
+    }
+}
+
+test "HashMap reverse removes" {
+    const Map = AutoHashMapUnmanaged(u32, u32);
+    const cap = 32;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    var i: u32 = 0;
+    while (i < 16) : (i += 1) {
+        try map.putNoClobber(i, i);
+    }
+
+    i = 16;
+    while (i > 0) : (i -= 1) {
+        _ = map.remove(i - 1);
+        try expect(!map.contains(i - 1));
+        var j: u32 = 0;
+        while (j < i - 1) : (j += 1) {
+            try expectEqual(map.get(j).?, j);
+        }
+    }
+
+    try expectEqual(map.count(), 0);
+}
+
+test "HashMap multiple removes on same metadata" {
+    const Map = AutoHashMapUnmanaged(u32, u32);
+    const cap = 32;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    var i: u32 = 0;
+    while (i < 16) : (i += 1) {
+        try map.put(i, i);
+    }
+
+    _ = map.remove(7);
+    _ = map.remove(15);
+    _ = map.remove(14);
+    _ = map.remove(13);
+    try expect(!map.contains(7));
+    try expect(!map.contains(15));
+    try expect(!map.contains(14));
+    try expect(!map.contains(13));
+
+    i = 0;
+    while (i < 13) : (i += 1) {
+        if (i == 7) {
+            try expect(!map.contains(i));
+        } else {
+            try expectEqual(map.get(i).?, i);
+        }
+    }
+
+    try map.put(15, 15);
+    try map.put(13, 13);
+    try map.put(14, 14);
+    try map.put(7, 7);
+    i = 0;
+    while (i < 16) : (i += 1) {
+        try expectEqual(map.get(i).?, i);
+    }
+}
+
+test "HashMap put and remove loop in random order" {
+    const Map = AutoHashMapUnmanaged(u32, u32);
+    const cap = 64;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    var keys: std.ArrayList(u32) = .empty;
+    defer keys.deinit(alloc);
+
+    const size = 32;
+    const iterations = 100;
+
+    var i: u32 = 0;
+    while (i < size) : (i += 1) {
+        try keys.append(alloc, i);
+    }
+    var prng = std.Random.DefaultPrng.init(0);
+    const random = prng.random();
+
+    while (i < iterations) : (i += 1) {
+        random.shuffle(u32, keys.items);
+
+        for (keys.items) |key| {
+            try map.put(key, key);
+        }
+        try expectEqual(map.count(), size);
+
+        for (keys.items) |key| {
+            _ = map.remove(key);
+        }
+        try expectEqual(map.count(), 0);
+    }
+}
+
+test "HashMap put" {
+    const Map = AutoHashMapUnmanaged(u32, u32);
+    const cap = 32;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    var i: u32 = 0;
+    while (i < 16) : (i += 1) {
+        try map.put(i, i);
+    }
+
+    i = 0;
+    while (i < 16) : (i += 1) {
+        try expectEqual(map.get(i).?, i);
+    }
+
+    i = 0;
+    while (i < 16) : (i += 1) {
+        try map.put(i, i * 16 + 1);
+    }
+
+    i = 0;
+    while (i < 16) : (i += 1) {
+        try expectEqual(map.get(i).?, i * 16 + 1);
+    }
+}
+
+test "HashMap put full load" {
+    const Map = AutoHashMapUnmanaged(usize, usize);
+    const cap = 16;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    for (0..cap) |i| try map.put(i, i);
+    for (0..cap) |i| try expectEqual(map.get(i).?, i);
+
+    try testing.expectError(error.OutOfMemory, map.put(cap, cap));
+}
+
+test "HashMap putAssumeCapacity" {
+    const Map = AutoHashMapUnmanaged(u32, u32);
+    const cap = 32;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    var i: u32 = 0;
+    while (i < 20) : (i += 1) {
+        map.putAssumeCapacityNoClobber(i, i);
+    }
+
+    i = 0;
+    var sum = i;
+    while (i < 20) : (i += 1) {
+        sum += map.getPtr(i).?.*;
+    }
+    try expectEqual(sum, 190);
+
+    i = 0;
+    while (i < 20) : (i += 1) {
+        map.putAssumeCapacity(i, 1);
+    }
+
+    i = 0;
+    sum = i;
+    while (i < 20) : (i += 1) {
+        sum += map.get(i).?;
+    }
+    try expectEqual(sum, 20);
+}
+
+test "HashMap repeat putAssumeCapacity/remove" {
+    const Map = AutoHashMapUnmanaged(u32, u32);
+    const cap = 32;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    const limit = cap;
+
+    var i: u32 = 0;
+    while (i < limit) : (i += 1) {
+        map.putAssumeCapacityNoClobber(i, i);
+    }
+
+    // Repeatedly delete/insert an entry without resizing the map.
+    // Put to different keys so entries don't land in the just-freed slot.
+    i = 0;
+    while (i < 10 * limit) : (i += 1) {
+        try testing.expect(map.remove(i));
+        if (i % 2 == 0) {
+            map.putAssumeCapacityNoClobber(limit + i, i);
+        } else {
+            map.putAssumeCapacity(limit + i, i);
+        }
+    }
+
+    i = 9 * limit;
+    while (i < 10 * limit) : (i += 1) {
+        try expectEqual(map.get(limit + i), i);
+    }
+    try expectEqual(map.count(), limit);
+}
+
+test "HashMap getOrPut" {
+    const Map = AutoHashMapUnmanaged(u32, u32);
+    const cap = 32;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    var i: u32 = 0;
+    while (i < 10) : (i += 1) {
+        try map.put(i * 2, 2);
+    }
+
+    i = 0;
+    while (i < 20) : (i += 1) {
+        _ = try map.getOrPutValue(i, 1);
+    }
+
+    i = 0;
+    var sum = i;
+    while (i < 20) : (i += 1) {
+        sum += map.get(i).?;
+    }
+
+    try expectEqual(sum, 30);
+}
+
+test "HashMap basic hash map usage" {
+    const Map = AutoHashMapUnmanaged(i32, i32);
+    const cap = 32;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    try testing.expect((try map.fetchPut(1, 11)) == null);
+    try testing.expect((try map.fetchPut(2, 22)) == null);
+    try testing.expect((try map.fetchPut(3, 33)) == null);
+    try testing.expect((try map.fetchPut(4, 44)) == null);
+
+    try map.putNoClobber(5, 55);
+    try testing.expect((try map.fetchPut(5, 66)).?.value == 55);
+    try testing.expect((try map.fetchPut(5, 55)).?.value == 66);
+
+    const gop1 = try map.getOrPut(5);
+    try testing.expect(gop1.found_existing == true);
+    try testing.expect(gop1.value_ptr.* == 55);
+    gop1.value_ptr.* = 77;
+    try testing.expect(map.getEntry(5).?.value_ptr.* == 77);
+
+    const gop2 = try map.getOrPut(99);
+    try testing.expect(gop2.found_existing == false);
+    gop2.value_ptr.* = 42;
+    try testing.expect(map.getEntry(99).?.value_ptr.* == 42);
+
+    const gop3 = try map.getOrPutValue(5, 5);
+    try testing.expect(gop3.value_ptr.* == 77);
+
+    const gop4 = try map.getOrPutValue(100, 41);
+    try testing.expect(gop4.value_ptr.* == 41);
+
+    try testing.expect(map.contains(2));
+    try testing.expect(map.getEntry(2).?.value_ptr.* == 22);
+    try testing.expect(map.get(2).? == 22);
+
+    const rmv1 = map.fetchRemove(2);
+    try testing.expect(rmv1.?.key == 2);
+    try testing.expect(rmv1.?.value == 22);
+    try testing.expect(map.fetchRemove(2) == null);
+    try testing.expect(map.remove(2) == false);
+    try testing.expect(map.getEntry(2) == null);
+    try testing.expect(map.get(2) == null);
+
+    try testing.expect(map.remove(3) == true);
+}
+
+test "HashMap ensureUnusedCapacity" {
+    const Map = AutoHashMapUnmanaged(u64, u64);
+    const cap = 64;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    try map.ensureUnusedCapacity(32);
+    try testing.expectError(error.OutOfMemory, map.ensureUnusedCapacity(cap + 1));
+}
+
+test "HashMap removeByPtr" {
+    const Map = AutoHashMapUnmanaged(i32, u64);
+    const cap = 64;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    var i: i32 = undefined;
+    i = 0;
+    while (i < 10) : (i += 1) {
+        try map.put(i, 0);
+    }
+
+    try testing.expect(map.count() == 10);
+
+    i = 0;
+    while (i < 10) : (i += 1) {
+        const key_ptr = map.getKeyPtr(i);
+        try testing.expect(key_ptr != null);
+
+        if (key_ptr) |ptr| {
+            map.removeByPtr(ptr);
+        }
+    }
+
+    try testing.expect(map.count() == 0);
+}
+
+test "HashMap removeByPtr 0 sized key" {
+    const Map = AutoHashMapUnmanaged(i32, u64);
+    const cap = 64;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    try map.put(0, 0);
+
+    try testing.expect(map.count() == 1);
+
+    const key_ptr = map.getKeyPtr(0);
+    try testing.expect(key_ptr != null);
+
+    if (key_ptr) |ptr| {
+        map.removeByPtr(ptr);
+    }
+
+    try testing.expect(map.count() == 0);
+}
+
+test "HashMap repeat fetchRemove" {
+    const Map = AutoHashMapUnmanaged(u64, void);
+    const cap = 64;
+
+    const alloc = testing.allocator;
+    const layout = Map.layoutForCapacity(cap);
+    const buf = try alloc.alignedAlloc(u8, Map.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var map = Map.init(.init(buf), layout);
+
+    map.putAssumeCapacity(0, {});
+    map.putAssumeCapacity(1, {});
+    map.putAssumeCapacity(2, {});
+    map.putAssumeCapacity(3, {});
+
+    // fetchRemove() should make slots available.
+    var i: usize = 0;
+    while (i < 10) : (i += 1) {
+        try testing.expect(map.fetchRemove(3) != null);
+        map.putAssumeCapacity(3, {});
+    }
+
+    try testing.expect(map.get(0) != null);
+    try testing.expect(map.get(1) != null);
+    try testing.expect(map.get(2) != null);
+    try testing.expect(map.get(3) != null);
+}
+
+test "OffsetHashMap basic usage" {
+    const OffsetMap = AutoOffsetHashMap(u32, u32);
+    const cap = 16;
+
+    const alloc = testing.allocator;
+    const layout = OffsetMap.layout(cap);
+    const buf = try alloc.alignedAlloc(u8, OffsetMap.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var offset_map = OffsetMap.init(.init(buf), layout);
+    var map = offset_map.map(buf.ptr);
+
+    const count = 5;
+    var i: u32 = 0;
+    var total: u32 = 0;
+    while (i < count) : (i += 1) {
+        try map.put(i, i);
+        total += i;
+    }
+
+    var sum: u32 = 0;
+    var it = map.iterator();
+    while (it.next()) |kv| {
+        sum += kv.key_ptr.*;
+    }
+    try expectEqual(total, sum);
+
+    i = 0;
+    sum = 0;
+    while (i < count) : (i += 1) {
+        try expectEqual(i, map.get(i).?);
+        sum += map.get(i).?;
+    }
+    try expectEqual(total, sum);
+}
+
+test "OffsetHashMap remake map" {
+    const OffsetMap = AutoOffsetHashMap(u32, u32);
+    const cap = 16;
+
+    const alloc = testing.allocator;
+    const layout = OffsetMap.layout(cap);
+    const buf = try alloc.alignedAlloc(u8, OffsetMap.base_align, layout.total_size);
+    defer alloc.free(buf);
+    var offset_map = OffsetMap.init(.init(buf), layout);
+
+    {
+        var map = offset_map.map(buf.ptr);
+        try map.put(5, 5);
+    }
+
+    {
+        var map = offset_map.map(buf.ptr);
+        try expectEqual(5, map.get(5).?);
+    }
+}
+
+test "layoutForCapacity no overflow for large capacity" {
+    // Test that layoutForCapacity correctly handles large capacities without overflow.
+    // Prior to the fix, new_capacity (u32) was multiplied before widening to usize,
+    // causing overflow when new_capacity * @sizeOf(K) exceeded 2^32.
+    // See: https://github.com/ghostty-org/ghostty/issues/9862
+    const Map = AutoHashMapUnmanaged(u64, u64);
+
+    // Use 2^30 capacity - this would overflow in u32 when multiplied by @sizeOf(u64)=8
+    // 0x40000000 * 8 = 0x2_0000_0000 which wraps to 0 in u32
+    const large_cap: Map.Size = 1 << 30;
+    const layout = Map.layoutForCapacity(large_cap);
+
+    // With the fix, total_size should be at least cap * (sizeof(K) + sizeof(V))
+    // = 2^30 * 16 = 2^34 bytes = 16 GiB
+    // Without the fix, this would wrap and produce a much smaller value.
+    const min_expected: usize = @as(usize, large_cap) * (@sizeOf(u64) + @sizeOf(u64));
+    try expect(layout.total_size >= min_expected);
+
+    // Also verify the individual offsets don't wrap
+    try expect(layout.keys_start > 0);
+    try expect(layout.vals_start > layout.keys_start);
+}