const std = @import("std"); const assert = std.debug.assert; const mem = std.mem; const testing = std.testing; /// An array that efficiently tracks which elements are in use. /// The pointers are intended to be stable /// Sorta related to https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2021/p0447r15.html pub fn HiveArray(comptime T: type, comptime capacity: u16) type { return struct { const Self = @This(); buffer: [capacity]T = undefined, available: std.bit_set.IntegerBitSet(capacity) = std.bit_set.IntegerBitSet(capacity).initFull(), pub const size = capacity; pub fn init() Self { return .{}; } pub fn get(self: *Self) ?*T { const index = self.available.findFirstSet() orelse return null; self.available.unset(index); return &self.buffer[index]; } pub fn at(self: *Self, index: u16) *T { assert(index < capacity); return &self.buffer[index]; } pub fn claim(self: *Self, index: u16) void { assert(index < capacity); assert(self.available.isSet(index)); self.available.unset(index); } pub fn indexOf(self: *const Self, value: *const T) ?u32 { const start = &self.buffer; const end = @ptrCast([*]const T, start) + capacity; if (!(@intFromPtr(value) >= @intFromPtr(start) and @intFromPtr(value) < @intFromPtr(end))) return null; // aligned to the size of T const index = (@intFromPtr(value) - @intFromPtr(start)) / @sizeOf(T); assert(index < capacity); assert(&self.buffer[index] == value); return @intCast(u32, index); } pub fn in(self: *const Self, value: *const T) bool { const start = &self.buffer; const end = @ptrCast([*]const T, start) + capacity; return (@intFromPtr(value) >= @intFromPtr(start) and @intFromPtr(value) < @intFromPtr(end)); } pub fn put(self: *Self, value: *T) bool { const index = self.indexOf(value) orelse return false; assert(!self.available.isSet(index)); assert(&self.buffer[index] == value); value.* = undefined; self.available.set(index); return true; } pub const Fallback = struct { hive: HiveArray(T, capacity), allocator: std.mem.Allocator, pub const This = @This(); pub fn init(allocator: std.mem.Allocator) This { return .{ .allocator = allocator, .hive = HiveArray(T, capacity).init(), }; } pub fn get(self: *This) *T { if (self.hive.get()) |value| { return value; } return self.allocator.create(T) catch unreachable; } pub fn tryGet(self: *This) !*T { if (self.hive.get()) |value| { return value; } return try self.allocator.create(T); } pub fn put(self: *This, value: *T) void { if (self.hive.put(value)) return; self.allocator.destroy(value); } }; }; } test "HiveArray" { const size = 64; // Choose an integer with a weird alignment const Int = u127; var a = HiveArray(Int, size).init(); { var b = a.get().?; try testing.expect(a.get().? != b); try testing.expectEqual(a.indexOf(b), 0); try testing.expect(a.put(b)); try testing.expect(a.get().? == b); var c = a.get().?; c.* = 123; var d: Int = 12345; try testing.expect(a.put(&d) == false); try testing.expect(a.in(&d) == false); } a.available = @TypeOf(a.available).initFull(); { var i: u63 = 0; while (i < size) { var b = a.get().?; try testing.expectEqual(a.indexOf(b), i); try testing.expect(a.put(b)); try testing.expect(a.get().? == b); i = i + 1; } i = 0; while (i < size) : (i += 1) { try testing.expect(a.get() == null); } } } ption Unnamed repository; edit this file 'description' to name the repository.
aboutsummaryrefslogtreecommitdiff
path: root/src/bun.js/builtins/cpp/ReadableStreamBuiltins.cpp (unfollow)
AgeCommit message (Expand)AuthorFilesLines
2023-01-21Handle string subclasses and new String() in new BufferGravatar Jarred Sumner 1-2/+11
2023-01-21Make Buffer.alloc* 3ns fasterGravatar Jarred Sumner 1-11/+17
2023-01-21[buffer] Make Buffer.from pass more testsGravatar Jarred Sumner 4-92/+179
2023-01-20constructor parameter properties in class expressions (#1867)Gravatar Dylan Conway 2-8/+48
2023-01-20Update transpiler.test.jsbun-v0.5.1Gravatar Jarred Sumner 1-1/+1
2023-01-20Update transpiler.test.jsGravatar Jarred Sumner 1-1/+1
2023-01-20push super before generated statements (#1856)Gravatar Dylan Conway 2-29/+53
2023-01-20Clear the errorsGravatar Jarred Sumner 1-0/+2
2023-01-20one less hash tableGravatar Jarred Sumner 1-2/+13
2023-01-20Add another testGravatar Jarred Sumner 2-1/+11
2023-01-20fix hanging testGravatar Jarred Sumner 1-38/+42
2023-01-20Further cleanup buffer encodingGravatar Jarred Sumner 1-48/+26
2023-01-20Fixes #1855Gravatar Jarred Sumner 2-5/+57
2023-01-20Fix assertion failure with boringssl messagesGravatar Jarred Sumner 3-5/+132
2023-01-19Revert "ignore sighup"Gravatar Jarred Sumner 1-45/+10
2023-01-19ignore sighupGravatar Jarred Sumner 1-10/+45
2023-01-19make this code easier to readGravatar Jarred Sumner 3-29/+26
2023-01-19Update types.zigGravatar Jarred Sumner 1-4/+0
2023-01-19BumpGravatar Jarred Sumner 2-2/+2
2023-01-19Fix buffer encoding bugGravatar Jarred Sumner 2-4/+17
2023-01-19use `String.from()` (#1850)Gravatar Alex Lam S.L 4-5/+12
2023-01-19Bump zigGravatar Jarred Sumner 2-2/+2
2023-01-19make it packedGravatar Jarred Sumner 1-2/+2
2023-01-20Bugfixes to install (#1848)Gravatar Jarred Sumner 5-26/+119
2023-01-19repopulate `alias_map` correctly (#1847)Gravatar Alex Lam S.L 5-70/+240
2023-01-19Add a commentGravatar Jarred Sumner 1-0/+6
2023-01-19Add a debug safety check for UAF in AST nodesGravatar Jarred Sumner 1-0/+5
2023-01-19Fix UAF when opening workspacesGravatar Jarred Sumner 1-2/+0
2023-01-19Improve error message when a workspace is not foundGravatar Jarred Sumner 2-9/+97