mirror of
https://github.com/oven-sh/bun
synced 2026-02-13 20:39:05 +00:00
fe8f8242fd
### What does this PR do? - Instead of storing `len` in `BoundedArray` as a `usize`, store it as either a `u8` or ` u16` depending on the `buffer_capacity` - Copy-paste `BoundedArray` from the standard library into Bun's codebase as it was removed in https://github.com/ziglang/zig/pull/24699/files#diff-cbd8cbbc17583cb9ea5cc0f711ce0ad447b446e62ea5ddbe29274696dce89e4f and we will probably continue using it ### How did you verify your code works? Ran `bun run zig:check` --------- Co-authored-by: autofix-ci[bot] <114827586+autofix-ci[bot]@users.noreply.github.com> Co-authored-by: taylor.fish <contact@taylor.fish>
309 lines
12 KiB
Zig
309 lines
12 KiB
Zig
/// Removed from the Zig standard library in https://github.com/ziglang/zig/pull/24699/
|
|
///
|
|
/// Modifications:
|
|
/// - `len` is a field of integer-size instead of usize. This reduces memory usage.
|
|
///
|
|
/// A structure with an array and a length, that can be used as a slice.
|
|
///
|
|
/// Useful to pass around small arrays whose exact size is only known at
|
|
/// runtime, but whose maximum size is known at comptime, without requiring
|
|
/// an `Allocator`.
|
|
///
|
|
/// ```zig
|
|
/// var actual_size = 32;
|
|
/// var a = try BoundedArray(u8, 64).init(actual_size);
|
|
/// var slice = a.slice(); // a slice of the 64-byte array
|
|
/// var a_clone = a; // creates a copy - the structure doesn't use any internal pointers
|
|
/// ```
|
|
pub fn BoundedArray(comptime T: type, comptime buffer_capacity: usize) type {
|
|
return BoundedArrayAligned(T, .fromByteUnits(@alignOf(T)), buffer_capacity);
|
|
}
|
|
|
|
/// A structure with an array, length and alignment, that can be used as a
|
|
/// slice.
|
|
///
|
|
/// Useful to pass around small explicitly-aligned arrays whose exact size is
|
|
/// only known at runtime, but whose maximum size is known at comptime, without
|
|
/// requiring an `Allocator`.
|
|
/// ```zig
|
|
// var a = try BoundedArrayAligned(u8, 16, 2).init(0);
|
|
// try a.append(255);
|
|
// try a.append(255);
|
|
// const b = @ptrCast(*const [1]u16, a.constSlice().ptr);
|
|
// try testing.expectEqual(@as(u16, 65535), b[0]);
|
|
/// ```
|
|
pub fn BoundedArrayAligned(
|
|
comptime T: type,
|
|
comptime alignment: Alignment,
|
|
comptime buffer_capacity: usize,
|
|
) type {
|
|
return struct {
|
|
const Self = @This();
|
|
buffer: [buffer_capacity]T align(alignment.toByteUnits()) = undefined,
|
|
len: Length = 0,
|
|
|
|
const Length = std.math.ByteAlignedInt(std.math.IntFittingRange(0, buffer_capacity));
|
|
|
|
pub const Buffer = @FieldType(Self, "buffer");
|
|
|
|
/// Set the actual length of the slice.
|
|
/// Returns error.Overflow if it exceeds the length of the backing array.
|
|
pub fn init(len: usize) error{Overflow}!Self {
|
|
if (len > buffer_capacity) return error.Overflow;
|
|
return Self{ .len = @intCast(len) };
|
|
}
|
|
|
|
/// View the internal array as a slice whose size was previously set.
|
|
pub fn slice(self: anytype) switch (@TypeOf(&self.buffer)) {
|
|
*align(alignment.toByteUnits()) [buffer_capacity]T => []align(alignment.toByteUnits()) T,
|
|
*align(alignment.toByteUnits()) const [buffer_capacity]T => []align(alignment.toByteUnits()) const T,
|
|
else => unreachable,
|
|
} {
|
|
return self.buffer[0..self.len];
|
|
}
|
|
|
|
/// View the internal array as a constant slice whose size was previously set.
|
|
pub fn constSlice(self: *const Self) []align(alignment.toByteUnits()) const T {
|
|
return self.slice();
|
|
}
|
|
|
|
/// Adjust the slice's length to `len`.
|
|
/// Does not initialize added items if any.
|
|
pub fn resize(self: *Self, len: usize) error{Overflow}!void {
|
|
if (len > buffer_capacity) return error.Overflow;
|
|
self.len = len;
|
|
}
|
|
|
|
/// Remove all elements from the slice.
|
|
pub fn clear(self: *Self) void {
|
|
self.len = 0;
|
|
}
|
|
|
|
/// Copy the content of an existing slice.
|
|
pub fn fromSlice(m: []const T) error{Overflow}!Self {
|
|
var list = try init(m.len);
|
|
@memcpy(list.slice(), m);
|
|
return list;
|
|
}
|
|
|
|
/// Return the element at index `i` of the slice.
|
|
pub fn get(self: Self, i: usize) T {
|
|
return self.constSlice()[i];
|
|
}
|
|
|
|
/// Set the value of the element at index `i` of the slice.
|
|
pub fn set(self: *Self, i: usize, item: T) void {
|
|
self.slice()[i] = item;
|
|
}
|
|
|
|
/// Return the maximum length of a slice.
|
|
pub fn capacity(self: Self) usize {
|
|
return self.buffer.len;
|
|
}
|
|
|
|
/// Check that the slice can hold at least `additional_count` items.
|
|
pub fn ensureUnusedCapacity(self: Self, additional_count: usize) error{Overflow}!void {
|
|
if (self.len + additional_count > buffer_capacity) {
|
|
return error.Overflow;
|
|
}
|
|
}
|
|
|
|
/// Increase length by 1, returning a pointer to the new item.
|
|
pub fn addOne(self: *Self) error{Overflow}!*T {
|
|
try self.ensureUnusedCapacity(1);
|
|
return self.addOneAssumeCapacity();
|
|
}
|
|
|
|
/// Increase length by 1, returning pointer to the new item.
|
|
/// Asserts that there is space for the new item.
|
|
pub fn addOneAssumeCapacity(self: *Self) *T {
|
|
assert(self.len < buffer_capacity);
|
|
self.len += 1;
|
|
return &self.slice()[self.len - 1];
|
|
}
|
|
|
|
/// Resize the slice, adding `n` new elements, which have `undefined` values.
|
|
/// The return value is a pointer to the array of uninitialized elements.
|
|
pub fn addManyAsArray(self: *Self, comptime n: usize) error{Overflow}!*align(alignment.toByteUnits()) [n]T {
|
|
const prev_len = self.len;
|
|
try self.resize(@as(usize, self.len) + n);
|
|
return self.slice()[prev_len..][0..n];
|
|
}
|
|
|
|
/// Resize the slice, adding `n` new elements, which have `undefined` values.
|
|
/// The return value is a slice pointing to the uninitialized elements.
|
|
pub fn addManyAsSlice(self: *Self, n: usize) error{Overflow}![]align(alignment.toByteUnits()) T {
|
|
const prev_len = self.len;
|
|
try self.resize(self.len + n);
|
|
return self.slice()[prev_len..][0..n];
|
|
}
|
|
|
|
/// Remove and return the last element from the slice, or return `null` if the slice is empty.
|
|
pub fn pop(self: *Self) ?T {
|
|
if (self.len == 0) return null;
|
|
const item = self.get(self.len - 1);
|
|
self.len -= 1;
|
|
return item;
|
|
}
|
|
|
|
/// Return a slice of only the extra capacity after items.
|
|
/// This can be useful for writing directly into it.
|
|
/// Note that such an operation must be followed up with a
|
|
/// call to `resize()`
|
|
pub fn unusedCapacitySlice(self: *Self) []align(alignment.toByteUnits()) T {
|
|
return self.buffer[self.len..];
|
|
}
|
|
|
|
/// Insert `item` at index `i` by moving `slice[n .. slice.len]` to make room.
|
|
/// This operation is O(N).
|
|
pub fn insert(
|
|
self: *Self,
|
|
i: usize,
|
|
item: T,
|
|
) error{Overflow}!void {
|
|
if (i > self.len) {
|
|
return error.Overflow;
|
|
}
|
|
_ = try self.addOne();
|
|
var s = self.slice();
|
|
mem.copyBackwards(T, s[i + 1 .. s.len], s[i .. s.len - 1]);
|
|
self.buffer[i] = item;
|
|
}
|
|
|
|
/// Insert slice `items` at index `i` by moving `slice[i .. slice.len]` to make room.
|
|
/// This operation is O(N).
|
|
pub fn insertSlice(self: *Self, i: usize, items: []const T) error{Overflow}!void {
|
|
try self.ensureUnusedCapacity(items.len);
|
|
self.len += @intCast(items.len);
|
|
mem.copyBackwards(T, self.slice()[i + items.len .. self.len], self.constSlice()[i .. self.len - items.len]);
|
|
@memcpy(self.slice()[i..][0..items.len], items);
|
|
}
|
|
|
|
/// Replace range of elements `slice[start..][0..len]` with `new_items`.
|
|
/// Grows slice if `len < new_items.len`.
|
|
/// Shrinks slice if `len > new_items.len`.
|
|
pub fn replaceRange(
|
|
self: *Self,
|
|
start: usize,
|
|
len: usize,
|
|
new_items: []const T,
|
|
) error{Overflow}!void {
|
|
const after_range = start + len;
|
|
var range = self.slice()[start..after_range];
|
|
|
|
if (range.len == new_items.len) {
|
|
@memcpy(range[0..new_items.len], new_items);
|
|
} else if (range.len < new_items.len) {
|
|
const first = new_items[0..range.len];
|
|
const rest = new_items[range.len..];
|
|
@memcpy(range[0..first.len], first);
|
|
try self.insertSlice(after_range, rest);
|
|
} else {
|
|
@memcpy(range[0..new_items.len], new_items);
|
|
const after_subrange = start + new_items.len;
|
|
for (self.constSlice()[after_range..], 0..) |item, i| {
|
|
self.slice()[after_subrange..][i] = item;
|
|
}
|
|
self.len = @intCast(@as(usize, self.len) - @as(usize, len) - @as(usize, new_items.len));
|
|
}
|
|
}
|
|
|
|
/// Extend the slice by 1 element.
|
|
pub fn append(self: *Self, item: T) error{Overflow}!void {
|
|
const new_item_ptr = try self.addOne();
|
|
new_item_ptr.* = item;
|
|
}
|
|
|
|
/// Extend the slice by 1 element, asserting the capacity is already
|
|
/// enough to store the new item.
|
|
pub fn appendAssumeCapacity(self: *Self, item: T) void {
|
|
const new_item_ptr = self.addOneAssumeCapacity();
|
|
new_item_ptr.* = item;
|
|
}
|
|
|
|
/// Remove the element at index `i`, shift elements after index
|
|
/// `i` forward, and return the removed element.
|
|
/// Asserts the slice has at least one item.
|
|
/// This operation is O(N).
|
|
pub fn orderedRemove(self: *Self, i: usize) T {
|
|
const newlen = self.len - 1;
|
|
if (newlen == i) return self.pop().?;
|
|
const old_item = self.get(i);
|
|
for (self.slice()[i..newlen], 0..) |*b, j| b.* = self.get(i + 1 + j);
|
|
self.set(newlen, undefined);
|
|
self.len = newlen;
|
|
return old_item;
|
|
}
|
|
|
|
/// Remove the element at the specified index and return it.
|
|
/// The empty slot is filled from the end of the slice.
|
|
/// This operation is O(1).
|
|
pub fn swapRemove(self: *Self, i: usize) T {
|
|
if (self.len - 1 == i) return self.pop().?;
|
|
const old_item = self.get(i);
|
|
self.set(i, self.pop().?);
|
|
return old_item;
|
|
}
|
|
|
|
/// Append the slice of items to the slice.
|
|
pub fn appendSlice(self: *Self, items: []const T) error{Overflow}!void {
|
|
try self.ensureUnusedCapacity(items.len);
|
|
self.appendSliceAssumeCapacity(items);
|
|
}
|
|
|
|
/// Append the slice of items to the slice, asserting the capacity is already
|
|
/// enough to store the new items.
|
|
pub fn appendSliceAssumeCapacity(self: *Self, items: []const T) void {
|
|
const old_len = self.len;
|
|
const new_len: usize = old_len + @as(usize, items.len);
|
|
self.len = @intCast(new_len);
|
|
@memcpy(self.slice()[old_len..][0..items.len], items);
|
|
}
|
|
|
|
/// Append a value to the slice `n` times.
|
|
/// Allocates more memory as necessary.
|
|
pub fn appendNTimes(self: *Self, value: T, n: usize) error{Overflow}!void {
|
|
const old_len = self.len;
|
|
try self.resize(old_len + n);
|
|
@memset(self.slice()[old_len..self.len], value);
|
|
}
|
|
|
|
/// Append a value to the slice `n` times.
|
|
/// Asserts the capacity is enough.
|
|
pub fn appendNTimesAssumeCapacity(self: *Self, value: T, n: usize) void {
|
|
const old_len: usize = self.len;
|
|
const new_len: usize = old_len + @as(usize, n);
|
|
self.len = @intCast(new_len);
|
|
assert(self.len <= buffer_capacity);
|
|
@memset(self.slice()[old_len..self.len], value);
|
|
}
|
|
|
|
pub const Writer = if (T != u8)
|
|
@compileError("The Writer interface is only defined for BoundedArray(u8, ...) " ++
|
|
"but the given type is BoundedArray(" ++ @typeName(T) ++ ", ...)")
|
|
else
|
|
std.io.GenericWriter(*Self, error{Overflow}, appendWrite);
|
|
|
|
/// Initializes a writer which will write into the array.
|
|
pub fn writer(self: *Self) Writer {
|
|
return .{ .context = self };
|
|
}
|
|
|
|
/// Same as `appendSlice` except it returns the number of bytes written, which is always the same
|
|
/// as `m.len`. The purpose of this function existing is to match `std.io.GenericWriter` API.
|
|
fn appendWrite(self: *Self, m: []const u8) error{Overflow}!usize {
|
|
try self.appendSlice(m);
|
|
return m.len;
|
|
}
|
|
};
|
|
}
|
|
|
|
const bun = @import("bun");
|
|
const assert = bun.assert;
|
|
|
|
const std = @import("std");
|
|
const testing = std.testing;
|
|
|
|
const mem = std.mem;
|
|
const Alignment = std.mem.Alignment;
|