aboutsummaryrefslogtreecommitdiff
path: root/vendor/libghostty-vt/src/datastruct
diff options
context:
space:
mode:
authorCan Celik <ogulcancelik@gmail.com>2026-09-10 21:51:57 +0300
committerGitHub <noreply@github.com>2026-09-10 21:51:57 +0300
commit425c86179791cd32e2d4ce0ae7f269940b4b0663 (patch)
treee52c4383a6d69216cbe2a32638bf90841d7e2189 /vendor/libghostty-vt/src/datastruct
parent90e947a6e26e02f10ec7f1694c4eb5b78a86406b (diff)
chore: upgrade libghostty and preserve terminal behavior (#3906)
Diffstat (limited to 'vendor/libghostty-vt/src/datastruct')
-rw-r--r--vendor/libghostty-vt/src/datastruct/array_list_collection.zig44
-rw-r--r--vendor/libghostty-vt/src/datastruct/blocking_queue.zig83
-rw-r--r--vendor/libghostty-vt/src/datastruct/circ_buf.zig67
-rw-r--r--vendor/libghostty-vt/src/datastruct/comparison.zig6
-rw-r--r--vendor/libghostty-vt/src/datastruct/limited_allocator.zig124
-rw-r--r--vendor/libghostty-vt/src/datastruct/lru.zig349
-rw-r--r--vendor/libghostty-vt/src/datastruct/main.zig6
-rw-r--r--vendor/libghostty-vt/src/datastruct/segmented_list.zig533
-rw-r--r--vendor/libghostty-vt/src/datastruct/segmented_pool.zig95
-rw-r--r--vendor/libghostty-vt/src/datastruct/split_tree.zig12
-rw-r--r--vendor/libghostty-vt/src/datastruct/untouched_pool.zig297
-rw-r--r--vendor/libghostty-vt/src/datastruct/wasm_page_pool.zig162
12 files changed, 1244 insertions, 534 deletions
diff --git a/vendor/libghostty-vt/src/datastruct/array_list_collection.zig b/vendor/libghostty-vt/src/datastruct/array_list_collection.zig
deleted file mode 100644
index d3fbddb1..00000000
--- a/vendor/libghostty-vt/src/datastruct/array_list_collection.zig
+++ /dev/null
@@ -1,44 +0,0 @@
-const std = @import("std");
-const Allocator = std.mem.Allocator;
-
-/// A collection of ArrayLists with methods for bulk operations.
-pub fn ArrayListCollection(comptime T: type) type {
- return struct {
- const Self = ArrayListCollection(T);
- const ArrayListT = std.ArrayListUnmanaged(T);
-
- // An array containing the lists that belong to this collection.
- lists: []ArrayListT,
-
- // The collection will be initialized with empty ArrayLists.
- pub fn init(
- alloc: Allocator,
- list_count: usize,
- initial_capacity: usize,
- ) Allocator.Error!Self {
- const self: Self = .{
- .lists = try alloc.alloc(ArrayListT, list_count),
- };
-
- for (self.lists) |*list| {
- list.* = try .initCapacity(alloc, initial_capacity);
- }
-
- return self;
- }
-
- pub fn deinit(self: *Self, alloc: Allocator) void {
- for (self.lists) |*list| {
- list.deinit(alloc);
- }
- alloc.free(self.lists);
- }
-
- /// Clear all lists in the collection, retaining capacity.
- pub fn reset(self: *Self) void {
- for (self.lists) |*list| {
- list.clearRetainingCapacity();
- }
- }
- };
-}
diff --git a/vendor/libghostty-vt/src/datastruct/blocking_queue.zig b/vendor/libghostty-vt/src/datastruct/blocking_queue.zig
index 3185d98d..89ce57d8 100644
--- a/vendor/libghostty-vt/src/datastruct/blocking_queue.zig
+++ b/vendor/libghostty-vt/src/datastruct/blocking_queue.zig
@@ -3,6 +3,7 @@
const std = @import("std");
const Allocator = std.mem.Allocator;
+const compat_thread = @import("../lib/compat/thread.zig");
/// Returns a blocking queue implementation for type T.
///
@@ -62,12 +63,12 @@ pub fn BlockingQueue(
len: Size = 0,
/// The big mutex that must be held to read/write.
- mutex: std.Thread.Mutex = .{},
+ mutex: std.Io.Mutex = .init,
/// A CV for being notified when the queue is no longer full. This is
/// used for writing. Note we DON'T have a CV for waiting on the
/// queue not being EMPTY because we use external notifiers for that.
- cond_not_full: std.Thread.Condition = .{},
+ cond_not_full: std.Io.Condition = .init,
not_full_waiters: usize = 0,
/// Allocate the blocking queue on the heap.
@@ -80,8 +81,8 @@ pub fn BlockingQueue(
.len = 0,
.write = 0,
.read = 0,
- .mutex = .{},
- .cond_not_full = .{},
+ .mutex = .init,
+ .cond_not_full = .init,
.not_full_waiters = 0,
};
@@ -98,9 +99,9 @@ pub fn BlockingQueue(
/// Push a value to the queue. This returns the total size of the
/// queue (unread items) after the push. A return value of zero
/// means that the push failed.
- pub fn push(self: *Self, value: T, timeout: Timeout) Size {
- self.mutex.lock();
- defer self.mutex.unlock();
+ pub fn push(self: *Self, io: std.Io, value: T, timeout: Timeout) Size {
+ self.mutex.lockUncancelable(io);
+ defer self.mutex.unlock(io);
// The
if (self.full()) {
@@ -111,13 +112,23 @@ pub fn BlockingQueue(
.forever => {
self.not_full_waiters += 1;
defer self.not_full_waiters -= 1;
- self.cond_not_full.wait(&self.mutex);
+ self.cond_not_full.waitUncancelable(io, &self.mutex);
},
.ns => |ns| {
self.not_full_waiters += 1;
defer self.not_full_waiters -= 1;
- self.cond_not_full.timedWait(&self.mutex, ns) catch return 0;
+ compat_thread.waitTimeout(
+ &self.cond_not_full,
+ io,
+ &self.mutex,
+ .{
+ .duration = .{
+ .raw = .fromNanoseconds(ns),
+ .clock = .awake,
+ },
+ },
+ ) catch return 0;
},
}
@@ -136,9 +147,9 @@ pub fn BlockingQueue(
}
/// Pop a value from the queue without blocking.
- pub fn pop(self: *Self) ?T {
- self.mutex.lock();
- defer self.mutex.unlock();
+ pub fn pop(self: *Self, io: std.Io) ?T {
+ self.mutex.lockUncancelable(io);
+ defer self.mutex.unlock(io);
// If we're empty we have nothing
if (self.len == 0) return null;
@@ -151,7 +162,7 @@ pub fn BlockingQueue(
self.len -= 1;
// If we have consumers waiting on a full queue, notify.
- if (self.not_full_waiters > 0) self.cond_not_full.signal();
+ if (self.not_full_waiters > 0) self.cond_not_full.signal(io);
return self.data[n];
}
@@ -160,8 +171,8 @@ pub fn BlockingQueue(
/// until `deinit` is called on the return value. This is used if
/// you know you're going to "pop" and utilize all the values
/// quickly to avoid many locks, bounds checks, and cv signals.
- pub fn drain(self: *Self) DrainIterator {
- self.mutex.lock();
+ pub fn drain(self: *Self, io: std.Io) DrainIterator {
+ self.mutex.lockUncancelable(io);
return .{ .queue = self };
}
@@ -180,12 +191,12 @@ pub fn BlockingQueue(
return self.queue.data[n];
}
- pub fn deinit(self: *DrainIterator) void {
+ pub fn deinit(self: *DrainIterator, io: std.Io) void {
// If we have consumers waiting on a full queue, notify.
- if (self.queue.not_full_waiters > 0) self.queue.cond_not_full.signal();
+ if (self.queue.not_full_waiters > 0) self.queue.cond_not_full.signal(io);
// Unlock
- self.queue.mutex.unlock();
+ self.queue.mutex.unlock(io);
}
};
@@ -200,49 +211,51 @@ pub fn BlockingQueue(
test "basic push and pop" {
const testing = std.testing;
const alloc = testing.allocator;
+ const io = testing.io;
const Q = BlockingQueue(u64, 4);
const q = try Q.create(alloc);
defer q.destroy(alloc);
// Should have no values
- try testing.expect(q.pop() == null);
+ try testing.expect(q.pop(io) == null);
// Push until we're full
- try testing.expectEqual(@as(Q.Size, 1), q.push(1, .{ .instant = {} }));
- try testing.expectEqual(@as(Q.Size, 2), q.push(2, .{ .instant = {} }));
- try testing.expectEqual(@as(Q.Size, 3), q.push(3, .{ .instant = {} }));
- try testing.expectEqual(@as(Q.Size, 4), q.push(4, .{ .instant = {} }));
- try testing.expectEqual(@as(Q.Size, 0), q.push(5, .{ .instant = {} }));
+ try testing.expectEqual(@as(Q.Size, 1), q.push(io, 1, .{ .instant = {} }));
+ try testing.expectEqual(@as(Q.Size, 2), q.push(io, 2, .{ .instant = {} }));
+ try testing.expectEqual(@as(Q.Size, 3), q.push(io, 3, .{ .instant = {} }));
+ try testing.expectEqual(@as(Q.Size, 4), q.push(io, 4, .{ .instant = {} }));
+ try testing.expectEqual(@as(Q.Size, 0), q.push(io, 5, .{ .instant = {} }));
// Pop!
- try testing.expect(q.pop().? == 1);
- try testing.expect(q.pop().? == 2);
- try testing.expect(q.pop().? == 3);
- try testing.expect(q.pop().? == 4);
- try testing.expect(q.pop() == null);
+ try testing.expect(q.pop(io).? == 1);
+ try testing.expect(q.pop(io).? == 2);
+ try testing.expect(q.pop(io).? == 3);
+ try testing.expect(q.pop(io).? == 4);
+ try testing.expect(q.pop(io) == null);
// Drain does nothing
- var it = q.drain();
+ var it = q.drain(io);
try testing.expect(it.next() == null);
- it.deinit();
+ it.deinit(io);
// Verify we can still push
- try testing.expectEqual(@as(Q.Size, 1), q.push(1, .{ .instant = {} }));
+ try testing.expectEqual(@as(Q.Size, 1), q.push(io, 1, .{ .instant = {} }));
}
test "timed push" {
const testing = std.testing;
const alloc = testing.allocator;
+ const io = testing.io;
const Q = BlockingQueue(u64, 1);
const q = try Q.create(alloc);
defer q.destroy(alloc);
// Push
- try testing.expectEqual(@as(Q.Size, 1), q.push(1, .{ .instant = {} }));
- try testing.expectEqual(@as(Q.Size, 0), q.push(2, .{ .instant = {} }));
+ try testing.expectEqual(@as(Q.Size, 1), q.push(io, 1, .{ .instant = {} }));
+ try testing.expectEqual(@as(Q.Size, 0), q.push(io, 2, .{ .instant = {} }));
// Timed push should fail
- try testing.expectEqual(@as(Q.Size, 0), q.push(2, .{ .ns = 1000 }));
+ try testing.expectEqual(@as(Q.Size, 0), q.push(io, 2, .{ .ns = 1000 }));
}
diff --git a/vendor/libghostty-vt/src/datastruct/circ_buf.zig b/vendor/libghostty-vt/src/datastruct/circ_buf.zig
index 3e373cb9..41a16832 100644
--- a/vendor/libghostty-vt/src/datastruct/circ_buf.zig
+++ b/vendor/libghostty-vt/src/datastruct/circ_buf.zig
@@ -167,18 +167,18 @@ pub fn CircBuf(comptime T: type, comptime default: T) type {
const prev_len = self.len();
const prev_cap = self.storage.len;
self.storage = try alloc.realloc(self.storage, size);
+ const retained_len = @min(prev_len, size);
// If we grew, we need to set our new defaults. We can add it
// at the end since we rotated to start.
if (size > prev_cap) {
@memset(self.storage[prev_cap..], default);
-
- // Fix up our head/tail
- if (self.full) {
- self.head = prev_len;
- self.full = false;
- }
}
+
+ // Fix up our head/tail for the new capacity.
+ self.head = if (retained_len == size) 0 else retained_len;
+ self.tail = 0;
+ self.full = retained_len == size;
}
/// Rotate the data so that it is zero-aligned.
@@ -793,6 +793,61 @@ test "CircBuf resize shrink" {
}
}
+test "CircBuf resize shrink partially full" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ const Buf = CircBuf(u8, 0);
+ var buf = try Buf.init(alloc, 5);
+ defer buf.deinit(alloc);
+
+ try buf.append(1);
+ try buf.append(2);
+ try buf.append(3);
+
+ try buf.resize(alloc, 2);
+ try testing.expect(buf.full);
+ try testing.expectEqual(@as(usize, 2), buf.len());
+ try testing.expectEqual(@as(usize, 2), buf.capacity());
+
+ var it = buf.iterator(.forward);
+ try testing.expectEqual(@as(u8, 1), it.next().?.*);
+ try testing.expectEqual(@as(u8, 2), it.next().?.*);
+ try testing.expect(it.next() == null);
+ try testing.expectError(error.OutOfMemory, buf.append(4));
+}
+
+test "CircBuf resize shrink to length" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ const Buf = CircBuf(u8, 0);
+ var buf = try Buf.init(alloc, 5);
+ defer buf.deinit(alloc);
+
+ try buf.append(1);
+ try buf.append(2);
+ try buf.resize(alloc, 2);
+
+ try testing.expect(buf.full);
+ try testing.expectEqual(@as(usize, 2), buf.len());
+ try testing.expectEqual(@as(usize, 2), buf.capacity());
+}
+
+test "CircBuf resize empty to zero" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ const Buf = CircBuf(u8, 0);
+ var buf = try Buf.init(alloc, 5);
+ defer buf.deinit(alloc);
+
+ try buf.resize(alloc, 0);
+ try testing.expect(buf.full);
+ try testing.expectEqual(@as(usize, 0), buf.len());
+ try testing.expectEqual(@as(usize, 0), buf.capacity());
+}
+
test "CircBuf append empty slice" {
const testing = std.testing;
const alloc = testing.allocator;
diff --git a/vendor/libghostty-vt/src/datastruct/comparison.zig b/vendor/libghostty-vt/src/datastruct/comparison.zig
index 6a862bb9..73f0a5bd 100644
--- a/vendor/libghostty-vt/src/datastruct/comparison.zig
+++ b/vendor/libghostty-vt/src/datastruct/comparison.zig
@@ -130,10 +130,12 @@ fn expectApproxEqualInner(comptime T: type, expected: T, actual: T) !void {
},
.vector => |info| {
var i: usize = 0;
+ const expected_array: [info.len]info.child = expected;
+ const actual_array: [info.len]info.child = actual;
while (i < info.len) : (i += 1) {
- expectApproxEqual(expected[i], actual[i]) catch {
+ expectApproxEqual(expected_array[i], actual_array[i]) catch {
print("index {d} incorrect. expected approximately {any}, found {any}\n", .{
- i, expected[i], actual[i],
+ i, expected_array[i], actual_array[i],
});
return error.TestExpectedApproxEqual;
};
diff --git a/vendor/libghostty-vt/src/datastruct/limited_allocator.zig b/vendor/libghostty-vt/src/datastruct/limited_allocator.zig
new file mode 100644
index 00000000..11c4fbea
--- /dev/null
+++ b/vendor/libghostty-vt/src/datastruct/limited_allocator.zig
@@ -0,0 +1,124 @@
+const std = @import("std");
+const Allocator = std.mem.Allocator;
+
+/// An allocator that rejects any single allocation or resize larger than a
+/// configured byte limit. The limit applies to each request independently,
+/// not to the total amount of memory currently allocated.
+pub const LimitedAllocator = struct {
+ child: Allocator,
+ limit: usize,
+
+ /// Set after an allocation, resize, or remap is rejected for exceeding
+ /// the limit. This remains set until the caller clears it.
+ limit_exceeded: bool = false,
+
+ pub fn init(child: Allocator, limit: usize) LimitedAllocator {
+ return .{
+ .child = child,
+ .limit = limit,
+ };
+ }
+
+ pub fn allocator(self: *LimitedAllocator) Allocator {
+ return .{
+ .ptr = self,
+ .vtable = &.{
+ .alloc = alloc,
+ .resize = resize,
+ .remap = remap,
+ .free = free,
+ },
+ };
+ }
+
+ fn check(self: *LimitedAllocator, size: usize) bool {
+ if (size <= self.limit) return true;
+ self.limit_exceeded = true;
+ return false;
+ }
+
+ fn alloc(
+ ctx: *anyopaque,
+ len: usize,
+ alignment: std.mem.Alignment,
+ ret_addr: usize,
+ ) ?[*]u8 {
+ const self: *LimitedAllocator = @ptrCast(@alignCast(ctx));
+ if (!self.check(len)) return null;
+ return self.child.rawAlloc(len, alignment, ret_addr);
+ }
+
+ fn resize(
+ ctx: *anyopaque,
+ memory: []u8,
+ alignment: std.mem.Alignment,
+ new_len: usize,
+ ret_addr: usize,
+ ) bool {
+ const self: *LimitedAllocator = @ptrCast(@alignCast(ctx));
+ if (!self.check(new_len)) return false;
+ return self.child.rawResize(memory, alignment, new_len, ret_addr);
+ }
+
+ fn remap(
+ ctx: *anyopaque,
+ memory: []u8,
+ alignment: std.mem.Alignment,
+ new_len: usize,
+ ret_addr: usize,
+ ) ?[*]u8 {
+ const self: *LimitedAllocator = @ptrCast(@alignCast(ctx));
+ if (!self.check(new_len)) return null;
+ return self.child.rawRemap(memory, alignment, new_len, ret_addr);
+ }
+
+ fn free(
+ ctx: *anyopaque,
+ memory: []u8,
+ alignment: std.mem.Alignment,
+ ret_addr: usize,
+ ) void {
+ const self: *LimitedAllocator = @ptrCast(@alignCast(ctx));
+ self.child.rawFree(memory, alignment, ret_addr);
+ }
+};
+
+test "LimitedAllocator allows allocations through the limit" {
+ const testing = std.testing;
+
+ var limited: LimitedAllocator = .init(testing.allocator, 8);
+ const alloc = limited.allocator();
+ const data = try alloc.alloc(u8, 8);
+ defer alloc.free(data);
+
+ try testing.expect(!limited.limit_exceeded);
+}
+
+test "LimitedAllocator rejects allocations before the child" {
+ const testing = std.testing;
+
+ var failing = testing.FailingAllocator.init(testing.allocator, .{
+ .fail_index = 0,
+ });
+ var limited: LimitedAllocator = .init(failing.allocator(), 8);
+
+ try testing.expectError(error.OutOfMemory, limited.allocator().alloc(u8, 9));
+ try testing.expect(limited.limit_exceeded);
+ try testing.expect(!failing.has_induced_failure);
+}
+
+test "LimitedAllocator rejects oversized resize and remap" {
+ const testing = std.testing;
+
+ var limited: LimitedAllocator = .init(testing.allocator, 8);
+ const alloc = limited.allocator();
+ const data = try alloc.alloc(u8, 8);
+ defer alloc.free(data);
+
+ try testing.expect(!alloc.resize(data, 9));
+ try testing.expect(limited.limit_exceeded);
+
+ limited.limit_exceeded = false;
+ try testing.expect(alloc.remap(data, 9) == null);
+ try testing.expect(limited.limit_exceeded);
+}
diff --git a/vendor/libghostty-vt/src/datastruct/lru.zig b/vendor/libghostty-vt/src/datastruct/lru.zig
deleted file mode 100644
index 83d2cf8e..00000000
--- a/vendor/libghostty-vt/src/datastruct/lru.zig
+++ /dev/null
@@ -1,349 +0,0 @@
-const std = @import("std");
-const assert = @import("../quirks.zig").inlineAssert;
-const Allocator = std.mem.Allocator;
-
-/// Create a HashMap for a key type that can be automatically hashed.
-/// If you want finer-grained control, use HashMap directly.
-pub fn AutoHashMap(comptime K: type, comptime V: type) type {
- return HashMap(
- K,
- V,
- std.hash_map.AutoContext(K),
- std.hash_map.default_max_load_percentage,
- );
-}
-
-/// HashMap implementation that supports least-recently-used eviction.
-///
-/// Beware of the Zig bug where a hashmap gets slower over time
-/// (https://github.com/ziglang/zig/issues/17851). This LRU uses a hashmap
-/// and evictions will cause this issue to appear. Callers should keep
-/// track of eviction counts and periodically reinitialize the LRU to
-/// avoid this issue. The LRU itself can't do this because it doesn't
-/// know how to free values.
-///
-/// Note: This is a really elementary CS101 version of an LRU right now.
-/// This is done initially to get something working. Once we have it working,
-/// we can benchmark and improve if this ends up being a source of slowness.
-pub fn HashMap(
- comptime K: type,
- comptime V: type,
- comptime Context: type,
- comptime max_load_percentage: u64,
-) type {
- return struct {
- const Self = @This();
- const Queue = std.DoublyLinkedList;
- const Map = std.HashMapUnmanaged(
- K,
- *Entry,
- Context,
- max_load_percentage,
- );
-
- /// Map to maintain our entries.
- map: Map,
-
- /// Queue to maintain LRU order.
- queue: Queue,
-
- /// The capacity of our map. If this capacity is reached, cache
- /// misses will begin evicting entries.
- capacity: Map.Size,
-
- const Entry = struct {
- data: KV,
- node: Queue.Node,
-
- fn fromNode(node: *Queue.Node) *Entry {
- return @fieldParentPtr("node", node);
- }
- };
-
- pub const KV = struct {
- key: K,
- value: V,
- };
-
- /// The result of a getOrPut operation.
- pub const GetOrPutResult = struct {
- /// The entry that was retrieved. If found_existing is false,
- /// then this is a pointer to allocated space to store a V.
- /// If found_existing is true, the pointer value is valid, but
- /// can be overwritten.
- value_ptr: *V,
-
- /// Whether an existing value was found or not.
- found_existing: bool,
-
- /// If another entry had to be evicted to make space for this
- /// put operation, then this is the value that was evicted.
- evicted: ?KV,
- };
-
- pub fn init(capacity: Map.Size) Self {
- return .{
- .map = .{},
- .queue = .{},
- .capacity = capacity,
- };
- }
-
- pub fn deinit(self: *Self, alloc: Allocator) void {
- // Important: use our queue as a source of truth for dealloc
- // because we might keep items in the queue around that aren't
- // present in our LRU anymore to prevent future allocations.
- var it = self.queue.first;
- while (it) |node| {
- it = node.next;
- alloc.destroy(Entry.fromNode(node));
- }
-
- self.map.deinit(alloc);
- self.* = undefined;
- }
-
- /// Get or put a value for a key. See GetOrPutResult on how to check
- /// if an existing value was found, if an existing value was evicted,
- /// etc.
- pub fn getOrPut(self: *Self, allocator: Allocator, key: K) Allocator.Error!GetOrPutResult {
- if (@sizeOf(Context) != 0)
- @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContext instead.");
- return self.getOrPutContext(allocator, key, undefined);
- }
-
- /// See getOrPut
- pub fn getOrPutContext(
- self: *Self,
- alloc: Allocator,
- key: K,
- ctx: Context,
- ) Allocator.Error!GetOrPutResult {
- const map_gop = try self.map.getOrPutContext(alloc, key, ctx);
- if (map_gop.found_existing) {
- // Move to end to mark as most recently used
- self.queue.remove(&map_gop.value_ptr.*.node);
- self.queue.append(&map_gop.value_ptr.*.node);
-
- return GetOrPutResult{
- .found_existing = true,
- .value_ptr = &map_gop.value_ptr.*.data.value,
- .evicted = null,
- };
- }
- errdefer _ = self.map.remove(key);
-
- // We're evicting if our map insertion increased our capacity.
- const evict = self.map.count() > self.capacity;
-
- // Get our entry. If we're not evicting then we allocate a new
- // entry. If we are evicting then we avoid allocation by just
- // reusing the entry we would've evicted.
- const entry: *Entry = if (!evict) try alloc.create(Entry) else entry: {
- // Our first node is the least recently used.
- const least_used_node = self.queue.popFirst().?;
- const least_used_entry: *Entry = .fromNode(least_used_node);
-
- // Remove the least used from the map
- _ = self.map.remove(least_used_entry.data.key);
-
- break :entry least_used_entry;
- };
- errdefer if (!evict) alloc.destroy(entry);
-
- // Store our entry in the map.
- map_gop.value_ptr.* = entry;
-
- // Mark the entry as most recently used
- self.queue.append(&entry.node);
-
- // Set our key
- entry.data.key = key;
-
- return .{
- .found_existing = map_gop.found_existing,
- .value_ptr = &entry.data.value,
- .evicted = if (!evict) null else entry.data,
- };
- }
-
- /// Get a value for a key.
- pub fn get(self: *const Self, key: K) ?V {
- if (@sizeOf(Context) != 0) {
- @compileError("getContext must be used.");
- }
- return self.getContext(key, undefined);
- }
-
- /// See get
- pub fn getContext(self: *const Self, key: K, ctx: Context) ?V {
- const node = self.map.getContext(key, ctx) orelse return null;
- return node.data.value;
- }
-
- /// Resize the LRU. If this shrinks the LRU then LRU items will be
- /// deallocated. The deallocated items are returned in the slice. This
- /// slice must be freed by the caller.
- pub fn resize(self: *Self, alloc: Allocator, capacity: Map.Size) Allocator.Error!?[]V {
- // Fastest
- if (capacity >= self.capacity) {
- self.capacity = capacity;
- return null;
- }
-
- // If we're shrinking but we're smaller than the new capacity,
- // then we don't have to do anything.
- if (self.map.count() <= capacity) {
- self.capacity = capacity;
- return null;
- }
-
- // We're shrinking and we have more items than the new capacity
- const delta = self.map.count() - capacity;
- var evicted = try alloc.alloc(V, delta);
-
- var i: Map.Size = 0;
- while (i < delta) : (i += 1) {
- const node = self.queue.popFirst().?;
- const entry: *Entry = .fromNode(node);
- evicted[i] = entry.data.value;
- self.queue.remove(node);
- _ = self.map.remove(entry.data.key);
- alloc.destroy(entry);
- }
-
- self.capacity = capacity;
- assert(self.map.count() == capacity);
-
- return evicted;
- }
- };
-}
-
-test "getOrPut" {
- const testing = std.testing;
- const alloc = testing.allocator;
-
- const Map = AutoHashMap(u32, u8);
- var m = Map.init(2);
- defer m.deinit(alloc);
-
- // Insert cap values, should be hits
- {
- const gop = try m.getOrPut(alloc, 1);
- try testing.expect(!gop.found_existing);
- try testing.expect(gop.evicted == null);
- gop.value_ptr.* = 1;
- }
- {
- const gop = try m.getOrPut(alloc, 2);
- try testing.expect(!gop.found_existing);
- try testing.expect(gop.evicted == null);
- gop.value_ptr.* = 2;
- }
-
- // 1 is LRU
- try testing.expect((try m.getOrPut(alloc, 1)).found_existing);
- try testing.expect((try m.getOrPut(alloc, 2)).found_existing);
-
- // Next should evict
- {
- const gop = try m.getOrPut(alloc, 3);
- try testing.expect(!gop.found_existing);
- try testing.expect(gop.evicted != null);
- try testing.expect(gop.evicted.?.value == 1);
- gop.value_ptr.* = 3;
- }
-
- // Currently: 2 is LRU, let's make 3 LRU
- try testing.expect((try m.getOrPut(alloc, 2)).found_existing);
-
- // Next should evict
- {
- const gop = try m.getOrPut(alloc, 4);
- try testing.expect(!gop.found_existing);
- try testing.expect(gop.evicted != null);
- try testing.expect(gop.evicted.?.value == 3);
- gop.value_ptr.* = 4;
- }
-}
-
-test "get" {
- const testing = std.testing;
- const alloc = testing.allocator;
-
- const Map = AutoHashMap(u32, u8);
- var m = Map.init(2);
- defer m.deinit(alloc);
-
- // Insert cap values, should be hits
- {
- const gop = try m.getOrPut(alloc, 1);
- try testing.expect(!gop.found_existing);
- try testing.expect(gop.evicted == null);
- gop.value_ptr.* = 1;
- }
-
- try testing.expect(m.get(1) != null);
- try testing.expect(m.get(1).? == 1);
- try testing.expect(m.get(2) == null);
-}
-
-test "resize shrink without removal" {
- const testing = std.testing;
- const alloc = testing.allocator;
-
- const Map = AutoHashMap(u32, u8);
- var m = Map.init(2);
- defer m.deinit(alloc);
-
- // Insert cap values, LRU is 1
- {
- const gop = try m.getOrPut(alloc, 1);
- try testing.expect(!gop.found_existing);
- try testing.expect(gop.evicted == null);
- gop.value_ptr.* = 1;
- }
-
- // Shrink
- const evicted = try m.resize(alloc, 1);
- try testing.expect(evicted == null);
- {
- const gop = try m.getOrPut(alloc, 1);
- try testing.expect(gop.found_existing);
- }
-}
-
-test "resize shrink and remove" {
- const testing = std.testing;
- const alloc = testing.allocator;
-
- const Map = AutoHashMap(u32, u8);
- var m = Map.init(2);
- defer m.deinit(alloc);
-
- // Insert cap values, LRU is 1
- {
- const gop = try m.getOrPut(alloc, 1);
- try testing.expect(!gop.found_existing);
- try testing.expect(gop.evicted == null);
- gop.value_ptr.* = 1;
- }
- {
- const gop = try m.getOrPut(alloc, 2);
- try testing.expect(!gop.found_existing);
- try testing.expect(gop.evicted == null);
- gop.value_ptr.* = 2;
- }
-
- // Shrink
- const evicted = try m.resize(alloc, 1);
- defer alloc.free(evicted.?);
- try testing.expectEqual(@as(usize, 1), evicted.?.len);
- {
- const gop = try m.getOrPut(alloc, 1);
- try testing.expect(!gop.found_existing);
- try testing.expect(gop.evicted.?.value == 2);
- gop.value_ptr.* = 1;
- }
-}
diff --git a/vendor/libghostty-vt/src/datastruct/main.zig b/vendor/libghostty-vt/src/datastruct/main.zig
index bfee2342..9fb0bae9 100644
--- a/vendor/libghostty-vt/src/datastruct/main.zig
+++ b/vendor/libghostty-vt/src/datastruct/main.zig
@@ -5,17 +5,17 @@ const blocking_queue = @import("blocking_queue.zig");
const cache_table = @import("cache_table.zig");
const circ_buf = @import("circ_buf.zig");
const intrusive_linked_list = @import("intrusive_linked_list.zig");
-const segmented_pool = @import("segmented_pool.zig");
const split_tree = @import("split_tree.zig");
-pub const lru = @import("lru.zig");
pub const BlockingQueue = blocking_queue.BlockingQueue;
pub const CacheTable = cache_table.CacheTable;
pub const CircBuf = circ_buf.CircBuf;
pub const IntrusiveDoublyLinkedList = intrusive_linked_list.DoublyLinkedList;
+pub const LimitedAllocator = @import("limited_allocator.zig").LimitedAllocator;
pub const MessageData = @import("message_data.zig").MessageData;
-pub const SegmentedPool = segmented_pool.SegmentedPool;
pub const SplitTree = split_tree.SplitTree;
+pub const UntouchedPool = @import("untouched_pool.zig").UntouchedPool;
+pub const WasmPagePool = @import("wasm_page_pool.zig").WasmPagePool;
test {
@import("std").testing.refAllDecls(@This());
diff --git a/vendor/libghostty-vt/src/datastruct/segmented_list.zig b/vendor/libghostty-vt/src/datastruct/segmented_list.zig
new file mode 100644
index 00000000..5c0601c5
--- /dev/null
+++ b/vendor/libghostty-vt/src/datastruct/segmented_list.zig
@@ -0,0 +1,533 @@
+//! Code taken from 0.15.2 `std.segmented_list` (MIT license). See
+//! lib/compat/README.md for license and details.
+const std = @import("std");
+const assert = @import("../quirks.zig").inlineAssert;
+const testing = std.testing;
+const mem = std.mem;
+const Allocator = std.mem.Allocator;
+
+// Imagine that `fn at(self: *Self, index: usize) &T` is a customer asking for a box
+// from a warehouse, based on a flat array, boxes ordered from 0 to N - 1.
+// But the warehouse actually stores boxes in shelves of increasing powers of 2 sizes.
+// So when the customer requests a box index, we have to translate it to shelf index
+// and box index within that shelf. Illustration:
+//
+// customer indexes:
+// shelf 0: 0
+// shelf 1: 1 2
+// shelf 2: 3 4 5 6
+// shelf 3: 7 8 9 10 11 12 13 14
+// shelf 4: 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
+// shelf 5: 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
+// ...
+//
+// warehouse indexes:
+// shelf 0: 0
+// shelf 1: 0 1
+// shelf 2: 0 1 2 3
+// shelf 3: 0 1 2 3 4 5 6 7
+// shelf 4: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
+// shelf 5: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
+// ...
+//
+// With this arrangement, here are the equations to get the shelf index and
+// box index based on customer box index:
+//
+// shelf_index = floor(log2(customer_index + 1))
+// shelf_count = ceil(log2(box_count + 1))
+// box_index = customer_index + 1 - 2 ** shelf
+// shelf_size = 2 ** shelf_index
+//
+// Now we complicate it a little bit further by adding a preallocated shelf, which must be
+// a power of 2:
+// prealloc=4
+//
+// customer indexes:
+// prealloc: 0 1 2 3
+// shelf 0: 4 5 6 7 8 9 10 11
+// shelf 1: 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
+// shelf 2: 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
+// ...
+//
+// warehouse indexes:
+// prealloc: 0 1 2 3
+// shelf 0: 0 1 2 3 4 5 6 7
+// shelf 1: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
+// shelf 2: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
+// ...
+//
+// Now the equations are:
+//
+// shelf_index = floor(log2(customer_index + prealloc)) - log2(prealloc) - 1
+// shelf_count = ceil(log2(box_count + prealloc)) - log2(prealloc) - 1
+// box_index = customer_index + prealloc - 2 ** (log2(prealloc) + 1 + shelf)
+// shelf_size = prealloc * 2 ** (shelf_index + 1)
+
+/// This is a stack data structure where pointers to indexes have the same lifetime as the data structure
+/// itself, unlike ArrayList where append() invalidates all existing element pointers.
+/// The tradeoff is that elements are not guaranteed to be contiguous. For that, use ArrayList.
+/// Note however that most elements are contiguous, making this data structure cache-friendly.
+///
+/// Because it never has to copy elements from an old location to a new location, it does not require
+/// its elements to be copyable, and it avoids wasting memory when backed by an ArenaAllocator.
+/// Note that the append() and pop() convenience methods perform a copy, but you can instead use
+/// addOne(), at(), setCapacity(), and shrinkCapacity() to avoid copying items.
+///
+/// This data structure has O(1) append and O(1) pop.
+///
+/// It supports preallocated elements, making it especially well suited when the expected maximum
+/// size is small. `prealloc_item_count` must be 0, or a power of 2.
+pub fn SegmentedList(comptime T: type, comptime prealloc_item_count: usize) type {
+ return struct {
+ const Self = @This();
+ const ShelfIndex = std.math.Log2Int(usize);
+
+ const prealloc_exp: ShelfIndex = blk: {
+ // we don't use the prealloc_exp constant when prealloc_item_count is 0
+ // but lazy-init may still be triggered by other code so supply a value
+ if (prealloc_item_count == 0) {
+ break :blk 0;
+ } else {
+ assert(std.math.isPowerOfTwo(prealloc_item_count));
+ const value = std.math.log2_int(usize, prealloc_item_count);
+ break :blk value;
+ }
+ };
+
+ prealloc_segment: [prealloc_item_count]T = undefined,
+ dynamic_segments: [][*]T = &[_][*]T{},
+ len: usize = 0,
+
+ pub const prealloc_count = prealloc_item_count;
+
+ fn AtType(comptime SelfType: type) type {
+ if (@typeInfo(SelfType).pointer.is_const) {
+ return *const T;
+ } else {
+ return *T;
+ }
+ }
+
+ pub fn deinit(self: *Self, allocator: Allocator) void {
+ self.freeShelves(allocator, @as(ShelfIndex, @intCast(self.dynamic_segments.len)), 0);
+ allocator.free(self.dynamic_segments);
+ self.* = undefined;
+ }
+
+ pub fn at(self: anytype, i: usize) AtType(@TypeOf(self)) {
+ assert(i < self.len);
+ return self.uncheckedAt(i);
+ }
+
+ pub fn count(self: Self) usize {
+ return self.len;
+ }
+
+ pub fn append(self: *Self, allocator: Allocator, item: T) Allocator.Error!void {
+ const new_item_ptr = try self.addOne(allocator);
+ new_item_ptr.* = item;
+ }
+
+ pub fn appendSlice(self: *Self, allocator: Allocator, items: []const T) Allocator.Error!void {
+ for (items) |item| {
+ try self.append(allocator, item);
+ }
+ }
+
+ pub fn pop(self: *Self) ?T {
+ if (self.len == 0) return null;
+
+ const index = self.len - 1;
+ const result = uncheckedAt(self, index).*;
+ self.len = index;
+ return result;
+ }
+
+ pub fn addOne(self: *Self, allocator: Allocator) Allocator.Error!*T {
+ const new_length = self.len + 1;
+ try self.growCapacity(allocator, new_length);
+ const result = uncheckedAt(self, self.len);
+ self.len = new_length;
+ return result;
+ }
+
+ /// Reduce length to `new_len`.
+ /// Invalidates pointers for the elements at index new_len and beyond.
+ pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
+ assert(new_len <= self.len);
+ self.len = new_len;
+ }
+
+ /// Invalidates all element pointers.
+ pub fn clearRetainingCapacity(self: *Self) void {
+ self.len = 0;
+ }
+
+ /// Invalidates all element pointers.
+ pub fn clearAndFree(self: *Self, allocator: Allocator) void {
+ self.setCapacity(allocator, 0) catch unreachable;
+ self.len = 0;
+ }
+
+ /// Grows or shrinks capacity to match usage.
+ /// TODO update this and related methods to match the conventions set by ArrayList
+ pub fn setCapacity(self: *Self, allocator: Allocator, new_capacity: usize) Allocator.Error!void {
+ if (prealloc_item_count != 0) {
+ if (new_capacity <= @as(usize, 1) << (prealloc_exp + @as(ShelfIndex, @intCast(self.dynamic_segments.len)))) {
+ return self.shrinkCapacity(allocator, new_capacity);
+ }
+ }
+ return self.growCapacity(allocator, new_capacity);
+ }
+
+ /// Only grows capacity, or retains current capacity.
+ pub fn growCapacity(self: *Self, allocator: Allocator, new_capacity: usize) Allocator.Error!void {
+ const new_cap_shelf_count = shelfCount(new_capacity);
+ const old_shelf_count = @as(ShelfIndex, @intCast(self.dynamic_segments.len));
+ if (new_cap_shelf_count <= old_shelf_count) return;
+
+ const new_dynamic_segments = try allocator.alloc([*]T, new_cap_shelf_count);
+ errdefer allocator.free(new_dynamic_segments);
+
+ var i: ShelfIndex = 0;
+ while (i < old_shelf_count) : (i += 1) {
+ new_dynamic_segments[i] = self.dynamic_segments[i];
+ }
+ errdefer while (i > old_shelf_count) : (i -= 1) {
+ allocator.free(new_dynamic_segments[i][0..shelfSize(i)]);
+ };
+ while (i < new_cap_shelf_count) : (i += 1) {
+ new_dynamic_segments[i] = (try allocator.alloc(T, shelfSize(i))).ptr;
+ }
+
+ allocator.free(self.dynamic_segments);
+ self.dynamic_segments = new_dynamic_segments;
+ }
+
+ /// Only shrinks capacity or retains current capacity.
+ /// It may fail to reduce the capacity in which case the capacity will remain unchanged.
+ pub fn shrinkCapacity(self: *Self, allocator: Allocator, new_capacity: usize) void {
+ if (new_capacity <= prealloc_item_count) {
+ const len = @as(ShelfIndex, @intCast(self.dynamic_segments.len));
+ self.freeShelves(allocator, len, 0);
+ allocator.free(self.dynamic_segments);
+ self.dynamic_segments = &[_][*]T{};
+ return;
+ }
+
+ const new_cap_shelf_count = shelfCount(new_capacity);
+ const old_shelf_count = @as(ShelfIndex, @intCast(self.dynamic_segments.len));
+ assert(new_cap_shelf_count <= old_shelf_count);
+ if (new_cap_shelf_count == old_shelf_count) return;
+
+ // freeShelves() must be called before resizing the dynamic
+ // segments, but we don't know if resizing the dynamic segments
+ // will work until we try it. So we must allocate a fresh memory
+ // buffer in order to reduce capacity.
+ const new_dynamic_segments = allocator.alloc([*]T, new_cap_shelf_count) catch return;
+ self.freeShelves(allocator, old_shelf_count, new_cap_shelf_count);
+ if (allocator.resize(self.dynamic_segments, new_cap_shelf_count)) {
+ // We didn't need the new memory allocation after all.
+ self.dynamic_segments = self.dynamic_segments[0..new_cap_shelf_count];
+ allocator.free(new_dynamic_segments);
+ } else {
+ // Good thing we allocated that new memory slice.
+ @memcpy(new_dynamic_segments, self.dynamic_segments[0..new_cap_shelf_count]);
+ allocator.free(self.dynamic_segments);
+ self.dynamic_segments = new_dynamic_segments;
+ }
+ }
+
+ pub fn shrink(self: *Self, new_len: usize) void {
+ assert(new_len <= self.len);
+ // TODO take advantage of the new realloc semantics
+ self.len = new_len;
+ }
+
+ pub fn writeToSlice(self: *Self, dest: []T, start: usize) void {
+ const end = start + dest.len;
+ assert(end <= self.len);
+
+ var i = start;
+ if (end <= prealloc_item_count) {
+ const src = self.prealloc_segment[i..end];
+ @memcpy(dest[i - start ..][0..src.len], src);
+ return;
+ } else if (i < prealloc_item_count) {
+ const src = self.prealloc_segment[i..];
+ @memcpy(dest[i - start ..][0..src.len], src);
+ i = prealloc_item_count;
+ }
+
+ while (i < end) {
+ const shelf_index = shelfIndex(i);
+ const copy_start = boxIndex(i, shelf_index);
+ const copy_end = @min(shelfSize(shelf_index), copy_start + end - i);
+ const src = self.dynamic_segments[shelf_index][copy_start..copy_end];
+ @memcpy(dest[i - start ..][0..src.len], src);
+ i += (copy_end - copy_start);
+ }
+ }
+
+ pub fn uncheckedAt(self: anytype, index: usize) AtType(@TypeOf(self)) {
+ if (index < prealloc_item_count) {
+ return &self.prealloc_segment[index];
+ }
+ const shelf_index = shelfIndex(index);
+ const box_index = boxIndex(index, shelf_index);
+ return &self.dynamic_segments[shelf_index][box_index];
+ }
+
+ fn shelfCount(box_count: usize) ShelfIndex {
+ if (prealloc_item_count == 0) {
+ return log2_int_ceil(usize, box_count + 1);
+ }
+ return log2_int_ceil(usize, box_count + prealloc_item_count) - prealloc_exp - 1;
+ }
+
+ fn shelfSize(shelf_index: ShelfIndex) usize {
+ if (prealloc_item_count == 0) {
+ return @as(usize, 1) << shelf_index;
+ }
+ return @as(usize, 1) << (shelf_index + (prealloc_exp + 1));
+ }
+
+ fn shelfIndex(list_index: usize) ShelfIndex {
+ if (prealloc_item_count == 0) {
+ return std.math.log2_int(usize, list_index + 1);
+ }
+ return std.math.log2_int(usize, list_index + prealloc_item_count) - prealloc_exp - 1;
+ }
+
+ fn boxIndex(list_index: usize, shelf_index: ShelfIndex) usize {
+ if (prealloc_item_count == 0) {
+ return (list_index + 1) - (@as(usize, 1) << shelf_index);
+ }
+ return list_index + prealloc_item_count - (@as(usize, 1) << ((prealloc_exp + 1) + shelf_index));
+ }
+
+ fn freeShelves(self: *Self, allocator: Allocator, from_count: ShelfIndex, to_count: ShelfIndex) void {
+ var i = from_count;
+ while (i != to_count) {
+ i -= 1;
+ allocator.free(self.dynamic_segments[i][0..shelfSize(i)]);
+ }
+ }
+
+ pub const Iterator = BaseIterator(*Self, *T);
+ pub const ConstIterator = BaseIterator(*const Self, *const T);
+ fn BaseIterator(comptime SelfType: type, comptime ElementPtr: type) type {
+ return struct {
+ list: SelfType,
+ index: usize,
+ box_index: usize,
+ shelf_index: ShelfIndex,
+ shelf_size: usize,
+
+ pub fn next(it: *@This()) ?ElementPtr {
+ if (it.index >= it.list.len) return null;
+ if (it.index < prealloc_item_count) {
+ const ptr = &it.list.prealloc_segment[it.index];
+ it.index += 1;
+ if (it.index == prealloc_item_count) {
+ it.box_index = 0;
+ it.shelf_index = 0;
+ it.shelf_size = prealloc_item_count * 2;
+ }
+ return ptr;
+ }
+
+ const ptr = &it.list.dynamic_segments[it.shelf_index][it.box_index];
+ it.index += 1;
+ it.box_index += 1;
+ if (it.box_index == it.shelf_size) {
+ it.shelf_index += 1;
+ it.box_index = 0;
+ it.shelf_size *= 2;
+ }
+ return ptr;
+ }
+
+ pub fn prev(it: *@This()) ?ElementPtr {
+ if (it.index == 0) return null;
+
+ it.index -= 1;
+ if (it.index < prealloc_item_count) return &it.list.prealloc_segment[it.index];
+
+ if (it.box_index == 0) {
+ it.shelf_index -= 1;
+ it.shelf_size /= 2;
+ it.box_index = it.shelf_size - 1;
+ } else {
+ it.box_index -= 1;
+ }
+
+ return &it.list.dynamic_segments[it.shelf_index][it.box_index];
+ }
+
+ pub fn peek(it: *@This()) ?ElementPtr {
+ if (it.index >= it.list.len)
+ return null;
+ if (it.index < prealloc_item_count)
+ return &it.list.prealloc_segment[it.index];
+
+ return &it.list.dynamic_segments[it.shelf_index][it.box_index];
+ }
+
+ pub fn set(it: *@This(), index: usize) void {
+ it.index = index;
+ if (index < prealloc_item_count) return;
+ it.shelf_index = shelfIndex(index);
+ it.box_index = boxIndex(index, it.shelf_index);
+ it.shelf_size = shelfSize(it.shelf_index);
+ }
+ };
+ }
+
+ pub fn iterator(self: *Self, start_index: usize) Iterator {
+ var it = Iterator{
+ .list = self,
+ .index = undefined,
+ .shelf_index = undefined,
+ .box_index = undefined,
+ .shelf_size = undefined,
+ };
+ it.set(start_index);
+ return it;
+ }
+
+ pub fn constIterator(self: *const Self, start_index: usize) ConstIterator {
+ var it = ConstIterator{
+ .list = self,
+ .index = undefined,
+ .shelf_index = undefined,
+ .box_index = undefined,
+ .shelf_size = undefined,
+ };
+ it.set(start_index);
+ return it;
+ }
+ };
+}
+
+test "basic usage" {
+ try testSegmentedList(0);
+ try testSegmentedList(1);
+ try testSegmentedList(2);
+ try testSegmentedList(4);
+ try testSegmentedList(8);
+ try testSegmentedList(16);
+}
+
+fn testSegmentedList(comptime prealloc: usize) !void {
+ var list = SegmentedList(i32, prealloc){};
+ defer list.deinit(testing.allocator);
+
+ {
+ var i: usize = 0;
+ while (i < 100) : (i += 1) {
+ try list.append(testing.allocator, @as(i32, @intCast(i + 1)));
+ try testing.expect(list.len == i + 1);
+ }
+ }
+
+ {
+ var i: usize = 0;
+ while (i < 100) : (i += 1) {
+ try testing.expect(list.at(i).* == @as(i32, @intCast(i + 1)));
+ }
+ }
+
+ {
+ var it = list.iterator(0);
+ var x: i32 = 0;
+ while (it.next()) |item| {
+ x += 1;
+ try testing.expect(item.* == x);
+ }
+ try testing.expect(x == 100);
+ while (it.prev()) |item| : (x -= 1) {
+ try testing.expect(item.* == x);
+ }
+ try testing.expect(x == 0);
+ }
+
+ {
+ var it = list.constIterator(0);
+ var x: i32 = 0;
+ while (it.next()) |item| {
+ x += 1;
+ try testing.expect(item.* == x);
+ }
+ try testing.expect(x == 100);
+ while (it.prev()) |item| : (x -= 1) {
+ try testing.expect(item.* == x);
+ }
+ try testing.expect(x == 0);
+ }
+
+ try testing.expect(list.pop().? == 100);
+ try testing.expect(list.len == 99);
+
+ try list.appendSlice(testing.allocator, &[_]i32{ 1, 2, 3 });
+ try testing.expect(list.len == 102);
+ try testing.expect(list.pop().? == 3);
+ try testing.expect(list.pop().? == 2);
+ try testing.expect(list.pop().? == 1);
+ try testing.expect(list.len == 99);
+
+ try list.appendSlice(testing.allocator, &[_]i32{});
+ try testing.expect(list.len == 99);
+
+ {
+ var i: i32 = 99;
+ while (list.pop()) |item| : (i -= 1) {
+ try testing.expect(item == i);
+ list.shrinkCapacity(testing.allocator, list.len);
+ }
+ }
+
+ {
+ var control: [100]i32 = undefined;
+ var dest: [100]i32 = undefined;
+
+ var i: i32 = 0;
+ while (i < 100) : (i += 1) {
+ try list.append(testing.allocator, i + 1);
+ control[@as(usize, @intCast(i))] = i + 1;
+ }
+
+ @memset(dest[0..], 0);
+ list.writeToSlice(dest[0..], 0);
+ try testing.expect(mem.eql(i32, control[0..], dest[0..]));
+
+ @memset(dest[0..], 0);
+ list.writeToSlice(dest[50..], 50);
+ try testing.expect(mem.eql(i32, control[50..], dest[50..]));
+ }
+
+ try list.setCapacity(testing.allocator, 0);
+}
+
+test "clearRetainingCapacity" {
+ var list = SegmentedList(i32, 1){};
+ defer list.deinit(testing.allocator);
+
+ try list.appendSlice(testing.allocator, &[_]i32{ 4, 5 });
+ list.clearRetainingCapacity();
+ try list.append(testing.allocator, 6);
+ try testing.expect(list.at(0).* == 6);
+ try testing.expect(list.len == 1);
+ list.clearRetainingCapacity();
+ try testing.expect(list.len == 0);
+}
+
+/// TODO look into why this std.math function was changed in
+/// fc9430f56798a53f9393a697f4ccd6bf9981b970.
+fn log2_int_ceil(comptime T: type, x: T) std.math.Log2Int(T) {
+ assert(x != 0);
+ const log2_val = std.math.log2_int(T, x);
+ if (@as(T, 1) << log2_val == x)
+ return log2_val;
+ return log2_val + 1;
+}
diff --git a/vendor/libghostty-vt/src/datastruct/segmented_pool.zig b/vendor/libghostty-vt/src/datastruct/segmented_pool.zig
deleted file mode 100644
index 328eb239..00000000
--- a/vendor/libghostty-vt/src/datastruct/segmented_pool.zig
+++ /dev/null
@@ -1,95 +0,0 @@
-const std = @import("std");
-const assert = @import("../quirks.zig").inlineAssert;
-const Allocator = std.mem.Allocator;
-const testing = std.testing;
-
-/// A data structure where you can get stable (never copied) pointers to
-/// a type that automatically grows if necessary. The values can be "put back"
-/// but are expected to be put back IN ORDER.
-///
-/// This is implemented specifically for libuv write requests, since the
-/// write requests must have a stable pointer and are guaranteed to be processed
-/// in order for a single stream.
-///
-/// This is NOT thread safe.
-pub fn SegmentedPool(comptime T: type, comptime prealloc: usize) type {
- return struct {
- const Self = @This();
-
- i: usize = 0,
- available: usize = prealloc,
- list: std.SegmentedList(T, prealloc) = .{ .len = prealloc },
-
- pub fn deinit(self: *Self, alloc: Allocator) void {
- self.list.deinit(alloc);
- self.* = undefined;
- }
-
- /// Get the next available value out of the list. This will not
- /// grow the list.
- pub fn get(self: *Self) !*T {
- // Error to not have any
- if (self.available == 0) return error.OutOfValues;
-
- // The index we grab is just i % len, so we wrap around to the front.
- const i = @mod(self.i, self.list.len);
- self.i +%= 1; // Wrapping addition to swe go back to 0
- self.available -= 1;
- return self.list.at(i);
- }
-
- /// Get the next available value out of the list and grow the list
- /// if necessary.
- pub fn getGrow(self: *Self, alloc: Allocator) !*T {
- if (self.available == 0) try self.grow(alloc);
- return try self.get();
- }
-
- fn grow(self: *Self, alloc: Allocator) !void {
- try self.list.growCapacity(alloc, self.list.len * 2);
- self.i = self.list.len;
- self.available = self.list.len;
- self.list.len *= 2;
- }
-
- /// Put a value back. The value put back is expected to be the
- /// in order of get.
- pub fn put(self: *Self) void {
- self.available += 1;
- assert(self.available <= self.list.len);
- }
- };
-}
-
-test "SegmentedPool" {
- var list: SegmentedPool(u8, 2) = .{};
- defer list.deinit(testing.allocator);
- try testing.expectEqual(@as(usize, 2), list.available);
-
- // Get to capacity
- const v1 = try list.get();
- const v2 = try list.get();
- try testing.expect(v1 != v2);
- try testing.expectError(error.OutOfValues, list.get());
-
- // Test writing for later
- v1.* = 42;
-
- // Put a value back
- list.put();
- const temp = try list.get();
- try testing.expect(v1 == temp);
- try testing.expect(temp.* == 42);
- try testing.expectError(error.OutOfValues, list.get());
-
- // Grow
- const v3 = try list.getGrow(testing.allocator);
- try testing.expect(v1 != v3 and v2 != v3);
- _ = try list.get();
- try testing.expectError(error.OutOfValues, list.get());
-
- // Put a value back
- list.put();
- try testing.expect(v1 == try list.get());
- try testing.expectError(error.OutOfValues, list.get());
-}
diff --git a/vendor/libghostty-vt/src/datastruct/split_tree.zig b/vendor/libghostty-vt/src/datastruct/split_tree.zig
index 1dc924ca..012f107f 100644
--- a/vendor/libghostty-vt/src/datastruct/split_tree.zig
+++ b/vendor/libghostty-vt/src/datastruct/split_tree.zig
@@ -183,6 +183,18 @@ pub fn SplitTree(comptime V: type) type {
};
}
+ /// Find the handle within this tree that corresponds
+ /// to the given view. Uses pointer equality.
+ pub fn locate(self: *const Self, view: *const View) ?Node.Handle {
+ var it = self.iterator();
+ while (it.next()) |entry| {
+ if (entry.view == view) {
+ return entry.handle;
+ }
+ }
+ return null;
+ }
+
/// An iterator over all the views in the tree.
pub fn iterator(
self: *const Self,
diff --git a/vendor/libghostty-vt/src/datastruct/untouched_pool.zig b/vendor/libghostty-vt/src/datastruct/untouched_pool.zig
new file mode 100644
index 00000000..a8ed4d31
--- /dev/null
+++ b/vendor/libghostty-vt/src/datastruct/untouched_pool.zig
@@ -0,0 +1,297 @@
+const std = @import("std");
+const assert = std.debug.assert;
+const Allocator = std.mem.Allocator;
+const Alignment = std.mem.Alignment;
+
+/// A fixed-size item pool whose bookkeeping never touches item memory.
+///
+/// std.heap.MemoryPool keeps its free list inside the items intrusively,
+/// meaning it has to touch allocated item memory. For memory that is
+/// demand-paged, that write forces the OS to create a physical page
+/// for nothing (to mark it free!).
+///
+/// This pool keeps the free list in a separate array allocated from a
+/// general-purpose allocator and allocates every item individually from
+/// the item allocator with the requested alignment. The pool never reads
+/// or writes an item until it is needed.
+///
+/// Contracts:
+///
+/// - The pool never zeroes. Callers that need zeroed items must use an
+/// item allocator that returns zeroed memory and must zero (or
+/// decommit) an item before destroy().
+/// - destroy() never allocates and never fails: create() reserves a
+/// free-list slot for every live item before allocating a new one.
+/// - The pool tracks free items only. Every item must be returned with
+/// destroy() or release() before reset() or deinit(), or it leaks.
+/// This is asserted in safe builds.
+///
+/// The tradeoff is that this isn't as fast as std.heap.MemoryPool, its
+/// not as cache friendly. But benchmarks show that the cost is minimal
+/// and if the tradeoff of not touching the memory is important, then
+/// this pays off.
+pub fn UntouchedPool(comptime Item: type, comptime alignment: Alignment) type {
+ return struct {
+ const Self = @This();
+
+ pub const item_size = @sizeOf(Item);
+ pub const item_alignment: Alignment = alignment.max(.of(Item));
+ pub const ItemPtr = *align(item_alignment.toByteUnits()) Item;
+ pub const ResetMode = std.heap.ArenaAllocator.ResetMode;
+
+ /// The allocator items are allocated from.
+ allocator: Allocator,
+
+ /// The general-purpose allocator for the free list.
+ gpa: Allocator,
+
+ /// Free items. The most recently destroyed item is handed out first.
+ free: std.ArrayList(ItemPtr),
+
+ /// Number of items currently allocated from the item allocator,
+ /// free or in use. `free.capacity >= live` always holds so that
+ /// destroy() never has to grow the free list.
+ live: usize,
+
+ /// Create a pool with `preheat` items already allocated.
+ pub fn initCapacity(
+ gpa: Allocator,
+ item_alloc: Allocator,
+ preheat: usize,
+ ) Allocator.Error!Self {
+ var self: Self = .{
+ .allocator = item_alloc,
+ .gpa = gpa,
+ .free = .empty,
+ .live = 0,
+ };
+ errdefer self.deinit();
+
+ try self.free.ensureTotalCapacityPrecise(gpa, preheat);
+ for (0..preheat) |_| {
+ const item = try self.allocItem();
+ self.free.appendAssumeCapacity(item);
+ }
+
+ return self;
+ }
+
+ /// Free all items and the free list. Every item must have been
+ /// returned with destroy() or release().
+ pub fn deinit(self: *Self) void {
+ assert(self.live == self.free.items.len);
+ for (self.free.items) |item| self.allocator.free(bytes(item));
+ self.free.deinit(self.gpa);
+ self.* = undefined;
+ }
+
+ /// Free items so that the retained free items fit `mode`. Every
+ /// item must have been returned with destroy() or release().
+ ///
+ /// This mirrors std.heap.MemoryPool.reset; it always succeeds
+ /// (returns true) because nothing is reallocated.
+ pub fn reset(self: *Self, mode: ResetMode) bool {
+ assert(self.live == self.free.items.len);
+ const retain_bytes: usize = switch (mode) {
+ .free_all => 0,
+ .retain_capacity => return true,
+ .retain_with_limit => |limit| limit,
+ };
+
+ const retain_items = retain_bytes / item_size;
+ while (self.free.items.len > retain_items) {
+ const item = self.free.pop().?;
+ self.allocator.free(bytes(item));
+ self.live -= 1;
+ }
+
+ return true;
+ }
+
+ /// Get an item. This pops a free item without touching it or,
+ /// when none is free, allocates a new one from the item
+ /// allocator.
+ pub fn create(self: *Self) Allocator.Error!ItemPtr {
+ if (self.free.pop()) |item| return item;
+
+ // Reserve the free-list slot for the new item before
+ // allocating it so that destroy() can never fail.
+ try self.free.ensureTotalCapacity(self.gpa, self.live + 1);
+ return try self.allocItem();
+ }
+
+ /// Return an item to the free list for reuse. The item is not
+ /// modified or zeroed so it is up to the caller.
+ pub fn destroy(self: *Self, item: ItemPtr) void {
+ assert(self.free.items.len < self.live);
+ self.free.appendAssumeCapacity(item);
+ }
+
+ /// Return an item straight to the item allocator instead of the
+ /// free list. This is for teardown paths that would otherwise
+ /// have to zero an item only for it to be freed moments later.
+ pub fn release(self: *Self, item: ItemPtr) void {
+ assert(self.free.items.len < self.live);
+ self.allocator.free(bytes(item));
+ self.live -= 1;
+ }
+
+ fn allocItem(self: *Self) Allocator.Error!ItemPtr {
+ assert(self.free.capacity > self.live);
+ const memory = try self.allocator.alignedAlloc(
+ u8,
+ item_alignment,
+ item_size,
+ );
+ self.live += 1;
+ return @ptrCast(memory.ptr);
+ }
+
+ fn bytes(item: ItemPtr) []align(item_alignment.toByteUnits()) u8 {
+ return std.mem.asBytes(item);
+ }
+ };
+}
+
+/// Test item: one minimum OS page, page-aligned, like a terminal page.
+const TestPool = UntouchedPool(
+ [std.heap.page_size_min]u8,
+ .fromByteUnits(std.heap.page_size_min),
+);
+
+test "UntouchedPool: create, destroy, reuse" {
+ const testing = std.testing;
+ var pool: TestPool = try .initCapacity(testing.allocator, testing.allocator, 0);
+ defer pool.deinit();
+
+ const a = try pool.create();
+ const b = try pool.create();
+ const c = try pool.create();
+ try testing.expect(a != b);
+ try testing.expect(a != c);
+ try testing.expect(b != c);
+
+ // Freed items are recycled, most recent first.
+ pool.destroy(a);
+ pool.destroy(b);
+ try testing.expectEqual(b, try pool.create());
+ try testing.expectEqual(a, try pool.create());
+
+ pool.destroy(a);
+ pool.destroy(b);
+ pool.destroy(c);
+}
+
+test "UntouchedPool: create and destroy never touch items" {
+ const testing = std.testing;
+ const preheat = 4;
+
+ // Back the item allocator with memory we can inspect.
+ const backing = try testing.allocator.alignedAlloc(
+ u8,
+ .fromByteUnits(std.heap.page_size_min),
+ preheat * TestPool.item_size,
+ );
+ defer testing.allocator.free(backing);
+ var fba: std.heap.FixedBufferAllocator = .init(backing);
+
+ var pool: TestPool = try .initCapacity(
+ testing.allocator,
+ fba.allocator(),
+ preheat,
+ );
+ defer pool.deinit();
+ try testing.expectEqual(preheat * TestPool.item_size, fba.end_index);
+
+ // Lay the sentinel down after preheat: allocation itself may write
+ // (the Allocator interface fills fresh memory with undefined in
+ // safe builds, which valgrind also tracks). The sentinel must differ
+ // from Zig's 0xAA undefined pattern so that any write is visible.
+ const sentinel: u8 = 0x5A;
+ @memset(backing, sentinel);
+
+ // Every preheated item comes out untouched and without allocating.
+ var items: [preheat]TestPool.ItemPtr = undefined;
+ for (&items) |*item| {
+ item.* = try pool.create();
+ try testing.expectEqual(preheat * TestPool.item_size, fba.end_index);
+ try testing.expect(std.mem.allEqual(u8, item.*, sentinel));
+ }
+
+ // Destroying and re-creating doesn't touch them either.
+ for (items) |item| pool.destroy(item);
+ try testing.expect(std.mem.allEqual(u8, backing, sentinel));
+ for (&items) |*item| {
+ item.* = try pool.create();
+ try testing.expect(std.mem.allEqual(u8, item.*, sentinel));
+ }
+ for (items) |item| pool.destroy(item);
+}
+
+test "UntouchedPool: destroy never allocates from the general allocator" {
+ const testing = std.testing;
+
+ // A general allocator that fails every allocation: after create has
+ // reserved the free-list slot, destroy must not need it.
+ var failing: std.testing.FailingAllocator = .init(testing.allocator, .{
+ .fail_index = 0,
+ });
+
+ var pool: TestPool = try .initCapacity(testing.allocator, testing.allocator, 0);
+ defer pool.deinit();
+
+ // The pool grows the free list through its own gpa, so swap in the
+ // failing one only around destroy.
+ var items: [64]TestPool.ItemPtr = undefined;
+ for (&items) |*item| item.* = try pool.create();
+ const gpa = pool.gpa;
+ pool.gpa = failing.allocator();
+ for (items) |item| pool.destroy(item);
+ pool.gpa = gpa;
+ try testing.expectEqual(items.len, pool.free.items.len);
+}
+
+test "UntouchedPool: reset retains at most the limit" {
+ const testing = std.testing;
+ var pool: TestPool = try .initCapacity(testing.allocator, testing.allocator, 4);
+ defer pool.deinit();
+
+ // Free everything above the limit
+ try testing.expect(pool.reset(.{ .retain_with_limit = 2 * TestPool.item_size }));
+ try testing.expectEqual(2, pool.free.items.len);
+ try testing.expectEqual(2, pool.live);
+
+ // retain_capacity keeps everything
+ try testing.expect(pool.reset(.retain_capacity));
+ try testing.expectEqual(2, pool.free.items.len);
+
+ // Retained items are handed out without allocating; new items
+ // beyond them are allocated as needed.
+ const a = try pool.create();
+ const b = try pool.create();
+ try testing.expectEqual(2, pool.live);
+ const c = try pool.create();
+ try testing.expectEqual(3, pool.live);
+ pool.destroy(a);
+ pool.destroy(b);
+ pool.destroy(c);
+
+ try testing.expect(pool.reset(.free_all));
+ try testing.expectEqual(0, pool.free.items.len);
+ try testing.expectEqual(0, pool.live);
+}
+
+test "UntouchedPool: release frees immediately" {
+ const testing = std.testing;
+ var pool: TestPool = try .initCapacity(testing.allocator, testing.allocator, 1);
+ defer pool.deinit();
+
+ const a = try pool.create();
+ const b = try pool.create();
+ try testing.expectEqual(2, pool.live);
+ pool.release(a);
+ try testing.expectEqual(1, pool.live);
+ try testing.expectEqual(0, pool.free.items.len);
+ pool.destroy(b);
+ try testing.expectEqual(1, pool.free.items.len);
+}
diff --git a/vendor/libghostty-vt/src/datastruct/wasm_page_pool.zig b/vendor/libghostty-vt/src/datastruct/wasm_page_pool.zig
new file mode 100644
index 00000000..0f73eec6
--- /dev/null
+++ b/vendor/libghostty-vt/src/datastruct/wasm_page_pool.zig
@@ -0,0 +1,162 @@
+const std = @import("std");
+const builtin = @import("builtin");
+const assert = std.debug.assert;
+const Allocator = std.mem.Allocator;
+
+/// A memory pool of wasm-page-multiple-sized items backed directly by
+/// wasm linear memory, for wasm targets only.
+///
+/// This is necessary for two reasons: the std.heap.MemoryPool grows 1.5x
+/// at each growth point. The backing allocator for that is usually a GPA
+/// which is the BrkAllocator for wasm. This grows by power-of-two
+/// big-allocation slots. If you pair these together you get a massive
+/// permanent linear memory growth. Native (non-wasm) targets don't care
+/// because unused virtual mappings are effectively free, but this isn't
+/// exactly true for Wasm runtimes.
+///
+/// This pool instead grows exactly @sizeOf(Item) bytes of fresh linear
+/// memory per item with memory.grow (which also guarantees wasm-page
+/// alignment and zeroing) and recycles freed items through a free list
+/// that is container-level, i.e. shared by every pool of the same Item
+/// type in the module instance. Every freed item is immediately
+/// reusable by every pool, and each item costs exactly @sizeOf(Item)
+/// reserved bytes, ever.
+///
+/// The "shared by every pool of the same Item type" is really important:
+/// the normal Ghostty memory pool is per-terminal. This one is per-module.
+/// The Ghostty wasm modules are not multi-threaded so this doesn't require
+/// any synchronization. But this means that all terminals share one pool
+/// so memory doesn't balloon like crazy that way either.
+///
+/// Requirements on Item:
+///
+/// - @sizeOf(Item) must be a nonzero multiple of the wasm page size
+/// (64KiB), since memory.grow allocates in whole pages. This is
+/// also what makes the pool exact-fit: any other size would strand
+/// the remainder of the last page.
+/// - Natural alignment must be at most the wasm page size.
+///
+/// Free-list items are dirty except that their first pointer-size bytes
+/// hold the intrusive free-list node, exactly like the std MemoryPool.
+/// Callers that need zeroed items must zero them (fresh items from
+/// memory.grow are zero by the wasm spec; recycled items retain
+/// whatever the caller left, so zero either on destroy or on create).
+///
+/// The API mirrors the native page pool (datastruct.UntouchedPool:
+/// initCapacity/deinit/reset/create/destroy plus the allocator field),
+/// so PageList can swap them at comptime.
+pub fn WasmPagePool(comptime Item: type) type {
+ return struct {
+ const Self = @This();
+
+ comptime {
+ if (builtin.target.cpu.arch.isWasm()) {
+ // The shared free list (and wasm's single linear
+ // memory) requires a single-threaded target.
+ assert(builtin.single_threaded);
+ // Items are whole wasm pages
+ assert(item_size > 0);
+ assert(item_size % std.heap.page_size_min == 0);
+ assert(@alignOf(Item) <= std.heap.page_size_min);
+ // Free items store the intrusive node in their bytes.
+ assert(item_size >= @sizeOf(std.SinglyLinkedList.Node));
+ }
+ }
+
+ /// The allocator this managed pool was initialized with,
+ /// carried for interface compatibility with the std managed
+ /// memory pools. Pool items never come from it (they come
+ /// from memory.grow), but callers may use it for related
+ /// allocations that don't fit the pool.
+ allocator: Allocator,
+
+ pub const item_size = @sizeOf(Item);
+ pub const ItemPtr = *align(std.heap.page_size_min) Item;
+
+ /// Freed items, shared by every pool of this Item type in the
+ /// module instance.
+ var free_list: std.SinglyLinkedList = .{};
+
+ pub fn initCapacity(
+ gpa: Allocator,
+ allocator: Allocator,
+ preheat: usize,
+ ) Allocator.Error!Self {
+ // The free list is intrusive so we never allocate from the
+ // general purpose allocator.
+ _ = gpa;
+
+ // Preheating is intentionally a no-op: item creation is a
+ // cheap memory.grow or free-list pop. And we want to avoid
+ // the preallocation mem cost.
+ _ = preheat;
+ return .{ .allocator = allocator };
+ }
+
+ pub fn deinit(self: *Self) void {
+ // Items are global to the instance and outlive the pool so
+ // other pools can reuse them. Callers must destroy() any
+ // items they still hold before deinit or they leak.
+ self.* = undefined;
+ }
+
+ pub fn reset(
+ self: *Self,
+ mode: std.heap.ArenaAllocator.ResetMode,
+ ) bool {
+ // There is nothing to trim: linear memory cannot shrink,
+ // so retaining every freed item for reuse is always the
+ // right policy on wasm. As with deinit, live items must be
+ // destroyed by the caller first.
+ _ = self;
+ _ = mode;
+ return true;
+ }
+
+ pub fn create(self: *Self) Allocator.Error!ItemPtr {
+ _ = self;
+
+ // If we have a free item, use it.
+ if (free_list.popFirst()) |node| return @ptrCast(@alignCast(node));
+
+ // Grow linear memory by exactly one item.
+ const pages = comptime item_size / std.heap.page_size_min;
+ const page_index = @wasmMemoryGrow(0, pages);
+ if (page_index == -1) return error.OutOfMemory;
+ return @ptrFromInt(@as(usize, @intCast(page_index)) * std.heap.page_size_min);
+ }
+
+ pub fn destroy(self: *Self, ptr: ItemPtr) void {
+ _ = self;
+ const node: *std.SinglyLinkedList.Node = @ptrCast(ptr);
+ node.* = .{};
+ free_list.prepend(node);
+ }
+ };
+}
+
+test WasmPagePool {
+ if (!comptime builtin.target.cpu.arch.isWasm()) return error.SkipZigTest;
+
+ const testing = std.testing;
+ const Pool = WasmPagePool([64 * 1024]u8);
+ var pool: Pool = try .initCapacity(testing.allocator, testing.allocator, 0);
+ defer pool.deinit();
+
+ const a = try pool.create();
+ const b = try pool.create();
+ try testing.expect(a != b);
+
+ // Freed items are recycled, most recent first.
+ pool.destroy(b);
+ try testing.expectEqual(b, try pool.create());
+
+ // The free list is shared across pools of the same Item type.
+ var pool2: Pool = try .initCapacity(testing.allocator, testing.allocator, 0);
+ defer pool2.deinit();
+ pool.destroy(a);
+ try testing.expectEqual(a, try pool2.create());
+
+ pool.destroy(a);
+ pool.destroy(b);
+}