Commit f2721a4cbc
Changed files (1)
lib
lib/std/array_list.zig
@@ -10,7 +10,7 @@ const Allocator = mem.Allocator;
/// This is a wrapper around an array of T values. Initialize with `init`.
///
/// This struct internally stores a `std.mem.Allocator` for memory management.
-/// To manually specify an allocator with each method call see `ArrayListUnmanaged`.
+/// To manually specify an allocator with each function call see `ArrayListUnmanaged`.
pub fn ArrayList(comptime T: type) type {
return ArrayListAligned(T, null);
}
@@ -21,7 +21,7 @@ pub fn ArrayList(comptime T: type) type {
/// Initialize with `init`.
///
/// This struct internally stores a `std.mem.Allocator` for memory management.
-/// To manually specify an allocator with each method call see `ArrayListAlignedUnmanaged`.
+/// To manually specify an allocator with each function call see `ArrayListAlignedUnmanaged`.
pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
if (alignment) |a| {
if (a == @alignOf(T)) {
@@ -30,15 +30,13 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
}
return struct {
const Self = @This();
- /// Contents of the list. Pointers to elements in this slice are
- /// **invalid after resizing operations** on the ArrayList unless the
- /// operation explicitly either: (1) states otherwise or (2) lists the
- /// invalidated pointers.
+ /// Contents of the list. This field is intended to be accessed
+ /// directly.
///
- /// The allocator used determines how element pointers are
- /// invalidated, so the behavior may vary between lists. To avoid
- /// illegal behavior, take into account the above paragraph plus the
- /// explicit statements given in each method.
+ /// Pointers to elements in this slice are invalidated by various
+ /// functions of this ArrayList in accordance with the respective
+ /// documentation. In all cases, "invalidated" means that the memory
+ /// has been passed to this allocator's resize or free function.
items: Slice,
/// How many T values this list can hold without allocating
/// additional memory.
@@ -144,18 +142,19 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// Insert `item` at index `i`. Moves `list[i .. list.len]` to higher indices to make room.
/// If `i` is equal to the length of the list this operation is equivalent to append.
/// This operation is O(N).
- /// Invalidates pointers if additional memory is needed.
- /// **Asserts that `i <= self.items.len`.**
+ /// Invalidates element pointers if additional memory is needed.
+ /// Asserts that the index is in bounds or equal to the length.
pub fn insert(self: *Self, i: usize, item: T) Allocator.Error!void {
const dst = try self.addManyAt(i, 1);
dst[0] = item;
}
/// Insert `item` at index `i`. Moves `list[i .. list.len]` to higher indices to make room.
- /// If `i` is equal to the length of the list this operation is equivalent to appendAssumeCapacity.
+ /// If `i` is equal to the length of the list this operation is
+ /// equivalent to appendAssumeCapacity.
/// This operation is O(N).
- /// **Asserts that `i <= self.items.len`.**
- /// **Asserts that `self.items.len < self.capacity` .**
+ /// Asserts that there is enough capacity for the new item.
+ /// Asserts that the index is in bounds or equal to the length.
pub fn insertAssumeCapacity(self: *Self, i: usize, item: T) void {
assert(self.items.len < self.capacity);
self.items.len += 1;
@@ -171,7 +170,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// Invalidates pre-existing pointers to elements at and after `index`.
/// Invalidates all pre-existing element pointers if capacity must be
/// increased to accomodate the new elements.
- /// **Asserts that `index <= self.items.len`.**
+ /// Asserts that the index is in bounds or equal to the length.
pub fn addManyAt(self: *Self, index: usize, count: usize) Allocator.Error![]T {
const new_len = try addOrOom(self.items.len, count);
@@ -208,10 +207,10 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// `undefined` values. Returns a slice pointing to the newly allocated
/// elements, which becomes invalid after various `ArrayList`
/// operations.
+ /// Asserts that there is enough capacity for the new elements.
/// Invalidates pre-existing pointers to elements at and after `index`, but
/// does not invalidate any before that.
- /// **Asserts that `index <= self.items.len`.**
- /// **Asserts that the list can hold `count` additional items.**
+ /// Asserts that the index is in bounds or equal to the length.
pub fn addManyAtAssumeCapacity(self: *Self, index: usize, count: usize) []T {
const new_len = self.items.len + count;
assert(self.capacity >= new_len);
@@ -228,7 +227,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// Invalidates pre-existing pointers to elements at and after `index`.
/// Invalidates all pre-existing element pointers if capacity must be
/// increased to accomodate the new elements.
- /// **Asserts that `index <= self.items.len`.**
+ /// Asserts that the index is in bounds or equal to the length.
pub fn insertSlice(
self: *Self,
index: usize,
@@ -241,8 +240,8 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// Replace range of elements `list[start..][0..len]` with `new_items`.
/// Grows list if `len < new_items.len`.
/// Shrinks list if `len > new_items.len`.
- /// Invalidates pointers if this ArrayList is resized.
- /// **Asserts that `start <= self.items.len`.**
+ /// Invalidates element pointers if this ArrayList is resized.
+ /// Asserts that the start index is in bounds or equal to the length.
pub fn replaceRange(self: *Self, start: usize, len: usize, new_items: []const T) Allocator.Error!void {
const after_range = try addOrOom(start, len);
const range = self.items[start..after_range];
@@ -268,15 +267,15 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
}
/// Extends the list by 1 element. Allocates more memory as necessary.
- /// Invalidates pointers if additional memory is needed.
+ /// Invalidates element pointers if additional memory is needed.
pub fn append(self: *Self, item: T) Allocator.Error!void {
const new_item_ptr = try self.addOne();
new_item_ptr.* = item;
}
- /// Extends the list by 1 element. Does not
- /// invalidate pointers.
- /// **Asserts that the list can hold one additional item.**
+ /// Extends the list by 1 element.
+ /// Never invalidates element pointers.
+ /// Asserts that the list can hold one additional item.
pub fn appendAssumeCapacity(self: *Self, item: T) void {
const new_item_ptr = self.addOneAssumeCapacity();
new_item_ptr.* = item;
@@ -284,11 +283,11 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// Remove the element at index `i`, shift elements after index
/// `i` forward, and return the removed element.
- /// Invalidates pointers to end of list.
+ /// Invalidates element pointers to end of list.
/// This operation is O(N).
/// This preserves item order. Use `swapRemove` if order preservation is not important.
- /// **Asserts that `i < self.items.len`.**
- /// **Asserts that the list is not empty.**
+ /// Asserts that the index is in bounds.
+ /// Asserts that the list is not empty.
pub fn orderedRemove(self: *Self, i: usize) T {
const newlen = self.items.len - 1;
if (newlen == i) return self.pop();
@@ -304,8 +303,8 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// The empty slot is filled from the end of the list.
/// This operation is O(1).
/// This may not preserve item order. Use `orderedRemove` if you need to preserve order.
- /// **Asserts that `i < self.items.len`.**
- /// **Asserts that the list is not empty.**
+ /// Asserts that the list is not empty.
+ /// Asserts that the index is in bounds.
pub fn swapRemove(self: *Self, i: usize) T {
if (self.items.len - 1 == i) return self.pop();
@@ -316,14 +315,15 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// Append the slice of items to the list. Allocates more
/// memory as necessary.
- /// Invalidates pointers if additional memory is needed.
+ /// Invalidates element pointers if additional memory is needed.
pub fn appendSlice(self: *Self, items: []const T) Allocator.Error!void {
try self.ensureUnusedCapacity(items.len);
self.appendSliceAssumeCapacity(items);
}
- /// Append the slice of items to the list. Does not invalidate pointers.
- /// **Asserts that the list can hold `items.len` additional items.**
+ /// Append the slice of items to the list.
+ /// Never invalidates element pointers.
+ /// Asserts that the list can hold the additional items.
pub fn appendSliceAssumeCapacity(self: *Self, items: []const T) void {
const old_len = self.items.len;
const new_len = old_len + items.len;
@@ -335,16 +335,18 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// Append an unaligned slice of items to the list. Allocates more
/// memory as necessary. Only call this function if calling
/// `appendSlice` instead would be a compile error.
- /// Invalidates pointers if additional memory is needed.
+ /// Invalidates element pointers if additional memory is needed.
pub fn appendUnalignedSlice(self: *Self, items: []align(1) const T) Allocator.Error!void {
try self.ensureUnusedCapacity(items.len);
self.appendUnalignedSliceAssumeCapacity(items);
}
- /// Append the slice of items to the list. **Does not** invalidate pointers.
- /// Only call this function if calling `appendSliceAssumeCapacity` instead
- /// would be a compile error.
- /// **Asserts that the list can hold `items.len` additional items.**
+ /// Append the slice of items to the list.
+ /// Never invalidates element pointers.
+ /// This function is only needed when calling
+ /// `appendSliceAssumeCapacity` instead would be a compile error due to the
+ /// alignment of the `items` parameter.
+ /// Asserts that the list can hold the additional items.
pub fn appendUnalignedSliceAssumeCapacity(self: *Self, items: []align(1) const T) void {
const old_len = self.items.len;
const new_len = old_len + items.len;
@@ -366,7 +368,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// Same as `append` 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.Writer` API.
- /// Invalidates pointers if additional memory is needed.
+ /// Invalidates element pointers if additional memory is needed.
fn appendWrite(self: *Self, m: []const u8) Allocator.Error!usize {
try self.appendSlice(m);
return m.len;
@@ -374,20 +376,20 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// Append a value to the list `n` times.
/// Allocates more memory as necessary.
- /// Invalidates pointers if additional memory is needed.
+ /// Invalidates element pointers if additional memory is needed.
/// The function is inline so that a comptime-known `value` parameter will
/// have a more optimal memset codegen in case it has a repeated byte pattern.
pub inline fn appendNTimes(self: *Self, value: T, n: usize) Allocator.Error!void {
const old_len = self.items.len;
- try self.resize(try addOrOom(self.items.len, n));
+ try self.resize(try addOrOom(old_len, n));
@memset(self.items[old_len..self.items.len], value);
}
/// Append a value to the list `n` times.
- /// Does not invalidate pointers.
+ /// Never invalidates element pointers.
/// The function is inline so that a comptime-known `value` parameter will
/// have a more optimal memset codegen in case it has a repeated byte pattern.
- /// **Asserts that the list can hold `n` additional items.**
+ /// Asserts that the list can hold the additional items.
pub inline fn appendNTimesAssumeCapacity(self: *Self, value: T, n: usize) void {
const new_len = self.items.len + n;
assert(new_len <= self.capacity);
@@ -395,9 +397,9 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
self.items.len = new_len;
}
- /// Adjust the list's length to `new_len`.
- /// Does not initialize added items if any.
- /// Invalidates pointers if additional memory is needed.
+ /// Adjust the list length to `new_len`.
+ /// Additional elements contain the value `undefined`.
+ /// Invalidates element pointers if additional memory is needed.
pub fn resize(self: *Self, new_len: usize) Allocator.Error!void {
try self.ensureTotalCapacity(new_len);
self.items.len = new_len;
@@ -405,7 +407,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// Reduce allocated capacity to `new_len`.
/// May invalidate element pointers.
- /// **Asserts that `new_len <= self.items.len`.**
+ /// Asserts that the new length is less than or equal to the previous length.
pub fn shrinkAndFree(self: *Self, new_len: usize) void {
var unmanaged = self.moveToUnmanaged();
unmanaged.shrinkAndFree(self.allocator, new_len);
@@ -413,8 +415,8 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
}
/// Reduce length to `new_len`.
- /// Invalidates pointers for the elements `items[new_len..]`.
- /// **Asserts that `new_len <= self.items.len`.**
+ /// Invalidates element pointers for the elements `items[new_len..]`.
+ /// Asserts that the new length is less than or equal to the previous length.
pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
assert(new_len <= self.items.len);
self.items.len = new_len;
@@ -434,7 +436,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// If the current capacity is less than `new_capacity`, this function will
/// modify the array so that it can hold at least `new_capacity` items.
- /// Invalidates pointers if additional memory is needed.
+ /// Invalidates element pointers if additional memory is needed.
pub fn ensureTotalCapacity(self: *Self, new_capacity: usize) Allocator.Error!void {
if (@sizeOf(T) == 0) {
self.capacity = math.maxInt(usize);
@@ -449,7 +451,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// If the current capacity is less than `new_capacity`, this function will
/// modify the array so that it can hold exactly `new_capacity` items.
- /// Invalidates pointers if additional memory is needed.
+ /// Invalidates element pointers if additional memory is needed.
pub fn ensureTotalCapacityPrecise(self: *Self, new_capacity: usize) Allocator.Error!void {
if (@sizeOf(T) == 0) {
self.capacity = math.maxInt(usize);
@@ -476,13 +478,14 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
}
/// Modify the array so that it can hold at least `additional_count` **more** items.
- /// Invalidates pointers if additional memory is needed.
+ /// Invalidates element pointers if additional memory is needed.
pub fn ensureUnusedCapacity(self: *Self, additional_count: usize) Allocator.Error!void {
return self.ensureTotalCapacity(try addOrOom(self.items.len, additional_count));
}
/// Increases the array's length to match the full capacity that is already allocated.
- /// The new elements have `undefined` values. **Does not** invalidate pointers.
+ /// The new elements have `undefined` values.
+ /// Never invalidates element pointers.
pub fn expandToCapacity(self: *Self) void {
self.items.len = self.capacity;
}
@@ -496,8 +499,8 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// Increase length by 1, returning pointer to the new item.
/// The returned pointer becomes invalid when the list is resized.
- /// Does not invalidate element pointers.
- /// **Asserts that the list can hold one additional item.**
+ /// Never invalidates element pointers.
+ /// Asserts that the list can hold one additional item.
pub fn addOneAssumeCapacity(self: *Self) *T {
assert(self.items.len < self.capacity);
self.items.len += 1;
@@ -516,9 +519,9 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// Resize the array, adding `n` new elements, which have `undefined` values.
/// The return value is an array pointing to the newly allocated elements.
- /// Does not invalidate element pointers.
+ /// Never invalidates element pointers.
/// The returned pointer becomes invalid when the list is resized.
- /// **Asserts that the list can hold `n` additional items.**
+ /// Asserts that the list can hold the additional items.
pub fn addManyAsArrayAssumeCapacity(self: *Self, comptime n: usize) *[n]T {
assert(self.items.len + n <= self.capacity);
const prev_len = self.items.len;
@@ -538,9 +541,9 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// Resize the array, adding `n` new elements, which have `undefined` values.
/// The return value is a slice pointing to the newly allocated elements.
- /// Does not invalidate element pointers.
+ /// Never invalidates element pointers.
/// The returned pointer becomes invalid when the list is resized.
- /// **Asserts that the list can hold `n` additional items.**
+ /// Asserts that the list can hold the additional items.
pub fn addManyAsSliceAssumeCapacity(self: *Self, n: usize) []T {
assert(self.items.len + n <= self.capacity);
const prev_len = self.items.len;
@@ -549,8 +552,8 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
}
/// Remove and return the last element from the list.
- /// Invalidates pointers to the removed element.
- /// **Asserts that the list is not empty.**
+ /// Invalidates element pointers to the removed element.
+ /// Asserts that the list is not empty.
pub fn pop(self: *Self) T {
const val = self.items[self.items.len - 1];
self.items.len -= 1;
@@ -559,7 +562,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
/// Remove and return the last element from the list, or
/// return `null` if list is empty.
- /// Invalidates pointers to the removed element, if any.
+ /// Invalidates element pointers to the removed element, if any.
pub fn popOrNull(self: *Self) ?T {
if (self.items.len == 0) return null;
return self.pop();
@@ -581,7 +584,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
}
/// Returns the last element from the list.
- /// **Asserts that the list is not empty.**
+ /// Asserts that the list is not empty.
pub fn getLast(self: Self) T {
const val = self.items[self.items.len - 1];
return val;
@@ -596,17 +599,20 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type {
}
/// An ArrayList, but the allocator is passed as a parameter to the relevant functions
-/// rather than stored in the struct itself. The same allocator **must** be used throughout
+/// rather than stored in the struct itself. The same allocator must be used throughout
/// the entire lifetime of an ArrayListUnmanaged. Initialize directly or with
/// `initCapacity`, and deinitialize with `deinit` or use `toOwnedSlice`.
pub fn ArrayListUnmanaged(comptime T: type) type {
return ArrayListAlignedUnmanaged(T, null);
}
-/// An ArrayListAligned, but the allocator is passed as a parameter to the relevant
-/// functions rather than stored in the struct itself. The same allocator **must**
-/// be used throughout the entire lifetime of an ArrayListAlignedUnmanaged.
-/// Initialize directly or with `initCapacity`, and deinitialize with `deinit` or use `toOwnedSlice`.
+/// A contiguous, growable list of arbitrarily aligned items in memory.
+/// This is a wrapper around an array of T values aligned to `alignment`-byte
+/// addresses. If the specified alignment is `null`, then `@alignOf(T)` is used.
+///
+/// Functions that potentially allocate memory accept an `Allocator` parameter.
+/// Initialize directly or with `initCapacity`, and deinitialize with `deinit`
+/// or use `toOwnedSlice`.
pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) type {
if (alignment) |a| {
if (a == @alignOf(T)) {
@@ -615,15 +621,13 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
}
return struct {
const Self = @This();
- /// Contents of the list. Pointers to elements in this slice are
- /// **invalid after resizing operations** on the ArrayList unless the
- /// operation explicitly either: (1) states otherwise or (2) lists the
- /// invalidated pointers.
+ /// Contents of the list. This field is intended to be accessed
+ /// directly.
///
- /// The allocator used determines how element pointers are
- /// invalidated, so the behavior may vary between lists. To avoid
- /// illegal behavior, take into account the above paragraph plus the
- /// explicit statements given in each method.
+ /// Pointers to elements in this slice are invalidated by various
+ /// functions of this ArrayList in accordance with the respective
+ /// documentation. In all cases, "invalidated" means that the memory
+ /// has been passed to an allocator's resize or free function.
items: Slice = &[_]T{},
/// How many T values this list can hold without allocating
/// additional memory.
@@ -646,8 +650,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Initialize with externally-managed memory. The buffer determines the
/// capacity, and the length is set to zero.
- /// **When initialized this way, all methods that accept an Allocator
- /// argument cause illegal behavior**.
+ /// When initialized this way, all functions that accept an Allocator
+ /// argument cause illegal behavior.
pub fn initBuffer(buffer: Slice) Self {
return .{
.items = buffer[0..0],
@@ -722,8 +726,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Insert `item` at index `i`. Moves `list[i .. list.len]` to higher indices to make room.
/// If `i` is equal to the length of the list this operation is equivalent to append.
/// This operation is O(N).
- /// Invalidates pointers if additional memory is needed.
- /// **Asserts that `i < self.items.len`.**
+ /// Invalidates element pointers if additional memory is needed.
+ /// Asserts that the index is in bounds or equal to the length.
pub fn insert(self: *Self, allocator: Allocator, i: usize, item: T) Allocator.Error!void {
const dst = try self.addManyAt(allocator, i, 1);
dst[0] = item;
@@ -732,8 +736,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Insert `item` at index `i`. Moves `list[i .. list.len]` to higher indices to make room.
/// If in` is equal to the length of the list this operation is equivalent to append.
/// This operation is O(N).
- /// **Asserts that `i < self.items.len`.**
- /// **Asserts that the list can hold one additional item.**
+ /// Asserts that the list has capacity for one additional item.
+ /// Asserts that the index is in bounds or equal to the length.
pub fn insertAssumeCapacity(self: *Self, i: usize, item: T) void {
assert(self.items.len < self.capacity);
self.items.len += 1;
@@ -749,7 +753,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Invalidates pre-existing pointers to elements at and after `index`.
/// Invalidates all pre-existing element pointers if capacity must be
/// increased to accomodate the new elements.
- /// **Asserts that `index <= self.items.len`.**
+ /// Asserts that the index is in bounds or equal to the length.
pub fn addManyAt(
self: *Self,
allocator: Allocator,
@@ -767,8 +771,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// operations.
/// Invalidates pre-existing pointers to elements at and after `index`, but
/// does not invalidate any before that.
- /// **Asserts that `index <= self.items.len`.**
- /// **Asserts that the list can hold `count` additional items.**
+ /// Asserts that the list has capacity for the additional items.
+ /// Asserts that the index is in bounds or equal to the length.
pub fn addManyAtAssumeCapacity(self: *Self, index: usize, count: usize) []T {
const new_len = self.items.len + count;
assert(self.capacity >= new_len);
@@ -785,7 +789,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Invalidates pre-existing pointers to elements at and after `index`.
/// Invalidates all pre-existing element pointers if capacity must be
/// increased to accomodate the new elements.
- /// **Asserts that `index <= self.items.len`.**
+ /// Asserts that the index is in bounds or equal to the length.
pub fn insertSlice(
self: *Self,
allocator: Allocator,
@@ -803,8 +807,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Replace range of elements `list[start..][0..len]` with `new_items`
/// Grows list if `len < new_items.len`.
/// Shrinks list if `len > new_items.len`
- /// Invalidates pointers if this ArrayList is resized.
- /// **Asserts that `start <= self.items.len`.**
+ /// Invalidates element pointers if this ArrayList is resized.
+ /// Asserts that the start index is in bounds or equal to the length.
pub fn replaceRange(
self: *Self,
allocator: Allocator,
@@ -818,14 +822,15 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
}
/// Extend the list by 1 element. Allocates more memory as necessary.
- /// Invalidates pointers if additional memory is needed.
+ /// Invalidates element pointers if additional memory is needed.
pub fn append(self: *Self, allocator: Allocator, item: T) Allocator.Error!void {
const new_item_ptr = try self.addOne(allocator);
new_item_ptr.* = item;
}
/// Extend the list by 1 element.
- /// **Asserts that the list can hold one additional item.**
+ /// Never invalidates element pointers.
+ /// Asserts that the list can hold one additional item.
pub fn appendAssumeCapacity(self: *Self, item: T) void {
const new_item_ptr = self.addOneAssumeCapacity();
new_item_ptr.* = item;
@@ -834,8 +839,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Remove the element at index `i` from the list and return its value.
/// Invalidates pointers to the last element.
/// This operation is O(N).
- /// **Asserts that `i < self.items.len`.**
- /// **Asserts that the list is not empty.**
+ /// Asserts that the list is not empty.
+ /// Asserts that the index is in bounds.
pub fn orderedRemove(self: *Self, i: usize) T {
const newlen = self.items.len - 1;
if (newlen == i) return self.pop();
@@ -851,8 +856,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// The empty slot is filled from the end of the list.
/// Invalidates pointers to last element.
/// This operation is O(1).
- /// **Asserts that `i < self.items.len`.**
- /// **Asserts that the list is not empty.**
+ /// Asserts that the list is not empty.
+ /// Asserts that the index is in bounds.
pub fn swapRemove(self: *Self, i: usize) T {
if (self.items.len - 1 == i) return self.pop();
@@ -863,14 +868,14 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Append the slice of items to the list. Allocates more
/// memory as necessary.
- /// Invalidates pointers if additional memory is needed.
+ /// Invalidates element pointers if additional memory is needed.
pub fn appendSlice(self: *Self, allocator: Allocator, items: []const T) Allocator.Error!void {
try self.ensureUnusedCapacity(allocator, items.len);
self.appendSliceAssumeCapacity(items);
}
/// Append the slice of items to the list.
- /// **Asserts that the list can hold `items.len` additional items.**
+ /// Asserts that the list can hold the additional items.
pub fn appendSliceAssumeCapacity(self: *Self, items: []const T) void {
const old_len = self.items.len;
const new_len = old_len + items.len;
@@ -882,7 +887,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Append the slice of items to the list. Allocates more
/// memory as necessary. Only call this function if a call to `appendSlice` instead would
/// be a compile error.
- /// Invalidates pointers if additional memory is needed.
+ /// Invalidates element pointers if additional memory is needed.
pub fn appendUnalignedSlice(self: *Self, allocator: Allocator, items: []align(1) const T) Allocator.Error!void {
try self.ensureUnusedCapacity(allocator, items.len);
self.appendUnalignedSliceAssumeCapacity(items);
@@ -891,7 +896,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Append an unaligned slice of items to the list.
/// Only call this function if a call to `appendSliceAssumeCapacity`
/// instead would be a compile error.
- /// **Asserts that the list can hold `items.len` additional items.**
+ /// Asserts that the list can hold the additional items.
pub fn appendUnalignedSliceAssumeCapacity(self: *Self, items: []align(1) const T) void {
const old_len = self.items.len;
const new_len = old_len + items.len;
@@ -918,7 +923,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Same as `append` 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.Writer` API.
- /// Invalidates pointers if additional memory is needed.
+ /// Invalidates element pointers if additional memory is needed.
fn appendWrite(context: WriterContext, m: []const u8) Allocator.Error!usize {
try context.self.appendSlice(context.allocator, m);
return m.len;
@@ -926,20 +931,20 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Append a value to the list `n` times.
/// Allocates more memory as necessary.
- /// Invalidates pointers if additional memory is needed.
+ /// Invalidates element pointers if additional memory is needed.
/// The function is inline so that a comptime-known `value` parameter will
/// have a more optimal memset codegen in case it has a repeated byte pattern.
pub inline fn appendNTimes(self: *Self, allocator: Allocator, value: T, n: usize) Allocator.Error!void {
const old_len = self.items.len;
- try self.resize(allocator, try addOrOom(self.items.len, n));
+ try self.resize(allocator, try addOrOom(old_len, n));
@memset(self.items[old_len..self.items.len], value);
}
/// Append a value to the list `n` times.
- /// **Does not** invalidate pointers.
+ /// Never invalidates element pointers.
/// The function is inline so that a comptime-known `value` parameter will
/// have better memset codegen in case it has a repeated byte pattern.
- /// **Asserts that the list can hold `n` additional items.**
+ /// Asserts that the list can hold the additional items.
pub inline fn appendNTimesAssumeCapacity(self: *Self, value: T, n: usize) void {
const new_len = self.items.len + n;
assert(new_len <= self.capacity);
@@ -947,9 +952,9 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
self.items.len = new_len;
}
- /// Adjust the list's length to `new_len`.
- /// Does not initialize added items, if any.
- /// Invalidates pointers if additional memory is needed.
+ /// Adjust the list length to `new_len`.
+ /// Additional elements contain the value `undefined`.
+ /// Invalidates element pointers if additional memory is needed.
pub fn resize(self: *Self, allocator: Allocator, new_len: usize) Allocator.Error!void {
try self.ensureTotalCapacity(allocator, new_len);
self.items.len = new_len;
@@ -957,7 +962,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Reduce allocated capacity to `new_len`.
/// May invalidate element pointers.
- /// **Asserts that `new_len <= self.items.len`.**
+ /// Asserts that the new length is less than or equal to the previous length.
pub fn shrinkAndFree(self: *Self, allocator: Allocator, new_len: usize) void {
assert(new_len <= self.items.len);
@@ -990,7 +995,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Reduce length to `new_len`.
/// Invalidates pointers to elements `items[new_len..]`.
/// Keeps capacity the same.
- /// **Asserts that `new_len <= self.items.len`.**
+ /// Asserts that the new length is less than or equal to the previous length.
pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
assert(new_len <= self.items.len);
self.items.len = new_len;
@@ -1010,7 +1015,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// If the current capacity is less than `new_capacity`, this function will
/// modify the array so that it can hold at least `new_capacity` items.
- /// Invalidates pointers if additional memory is needed.
+ /// Invalidates element pointers if additional memory is needed.
pub fn ensureTotalCapacity(self: *Self, allocator: Allocator, new_capacity: usize) Allocator.Error!void {
if (self.capacity >= new_capacity) return;
@@ -1020,7 +1025,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// If the current capacity is less than `new_capacity`, this function will
/// modify the array so that it can hold exactly `new_capacity` items.
- /// Invalidates pointers if additional memory is needed.
+ /// Invalidates element pointers if additional memory is needed.
pub fn ensureTotalCapacityPrecise(self: *Self, allocator: Allocator, new_capacity: usize) Allocator.Error!void {
if (@sizeOf(T) == 0) {
self.capacity = math.maxInt(usize);
@@ -1047,7 +1052,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
}
/// Modify the array so that it can hold at least `additional_count` **more** items.
- /// Invalidates pointers if additional memory is needed.
+ /// Invalidates element pointers if additional memory is needed.
pub fn ensureUnusedCapacity(
self: *Self,
allocator: Allocator,
@@ -1058,13 +1063,13 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Increases the array's length to match the full capacity that is already allocated.
/// The new elements have `undefined` values.
- /// Does not invalidate pointers.
+ /// Never invalidates element pointers.
pub fn expandToCapacity(self: *Self) void {
self.items.len = self.capacity;
}
/// Increase length by 1, returning pointer to the new item.
- /// The returned pointer becomes invalid when the list resized.
+ /// The returned element pointer becomes invalid when the list is resized.
pub fn addOne(self: *Self, allocator: Allocator) Allocator.Error!*T {
const newlen = try addOrOom(self.items.len, 1);
try self.ensureTotalCapacity(allocator, newlen);
@@ -1072,9 +1077,9 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
}
/// Increase length by 1, returning pointer to the new item.
- /// **Does not** invalidate pointers.
- /// The returned pointer becomes invalid when the list resized.
- /// **Asserts that the list can hold one additional item.**
+ /// Never invalidates element pointers.
+ /// The returned element pointer becomes invalid when the list is resized.
+ /// Asserts that the list can hold one additional item.
pub fn addOneAssumeCapacity(self: *Self) *T {
assert(self.items.len < self.capacity);
@@ -1093,9 +1098,9 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Resize the array, adding `n` new elements, which have `undefined` values.
/// The return value is an array pointing to the newly allocated elements.
- /// **Does not** invalidate pointers.
+ /// Never invalidates element pointers.
/// The returned pointer becomes invalid when the list is resized.
- /// **Asserts that the list can hold `n` additional items.**
+ /// Asserts that the list can hold the additional items.
pub fn addManyAsArrayAssumeCapacity(self: *Self, comptime n: usize) *[n]T {
assert(self.items.len + n <= self.capacity);
const prev_len = self.items.len;
@@ -1115,9 +1120,9 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Resize the array, adding `n` new elements, which have `undefined` values.
/// The return value is a slice pointing to the newly allocated elements.
- /// Does not invalidate element pointers.
+ /// Never invalidates element pointers.
/// The returned pointer becomes invalid when the list is resized.
- /// **Asserts that the list can hold `n` additional items.**
+ /// Asserts that the list can hold the additional items.
pub fn addManyAsSliceAssumeCapacity(self: *Self, n: usize) []T {
assert(self.items.len + n <= self.capacity);
const prev_len = self.items.len;
@@ -1127,7 +1132,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
/// Remove and return the last element from the list.
/// Invalidates pointers to last element.
- /// **Asserts that the list is not empty.**
+ /// Asserts that the list is not empty.
pub fn pop(self: *Self) T {
const val = self.items[self.items.len - 1];
self.items.len -= 1;
@@ -1157,7 +1162,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ
}
/// Return the last element from the list.
- /// **Asserts that the list is not empty.**
+ /// Asserts that the list is not empty.
pub fn getLast(self: Self) T {
const val = self.items[self.items.len - 1];
return val;
@@ -1183,12 +1188,11 @@ fn growCapacity(current: usize, minimum: usize) usize {
}
}
-/// Adds a and b, returning `error.OutOfMemory` if overflow occurred.
-/// This is equivalent to `math.add`. See #18467 for why it is used.
+/// Integer addition returning `error.OutOfMemory` on overflow.
fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize {
- const ov = @addWithOverflow(a, b);
- if (ov[1] != 0) return error.OutOfMemory;
- return ov[0];
+ const result, const overflow = @addWithOverflow(a, b);
+ if (overflow != 0) return error.OutOfMemory;
+ return result;
}
test "std.ArrayList/ArrayListUnmanaged.init" {
@@ -1985,47 +1989,49 @@ test "std.ArrayList(u32).getLastOrNull()" {
}
test "return OutOfMemory when capacity would exceed maximum usize integer value" {
- // Because a portable way to create maxInt(usize)-sized slices does not seem to exist yet, this
- // will have to do.
-
const a = testing.allocator;
+ const new_item: u32 = 42;
- var alu = ArrayListUnmanaged(u32){
- .items = undefined,
- .capacity = math.maxInt(usize),
- };
- alu.items.len = math.maxInt(usize);
-
- try testing.expectError(error.OutOfMemory, alu.append(a, undefined));
- try testing.expectError(error.OutOfMemory, alu.appendSlice(a, &.{undefined}));
- try testing.expectError(error.OutOfMemory, alu.appendNTimes(a, undefined, 1));
- try testing.expectError(error.OutOfMemory, alu.appendUnalignedSlice(a, &.{undefined}));
- try testing.expectError(error.OutOfMemory, alu.addOne(a));
- try testing.expectError(error.OutOfMemory, alu.addManyAt(a, 0, 1));
- try testing.expectError(error.OutOfMemory, alu.addManyAsArray(a, 1));
- try testing.expectError(error.OutOfMemory, alu.addManyAsSlice(a, 1));
- try testing.expectError(error.OutOfMemory, alu.insert(a, 0, undefined));
- try testing.expectError(error.OutOfMemory, alu.insertSlice(a, 0, &.{undefined}));
- try testing.expectError(error.OutOfMemory, alu.toOwnedSliceSentinel(a, 0));
- try testing.expectError(error.OutOfMemory, alu.ensureUnusedCapacity(a, 1));
-
- var al = ArrayList(u32){
- .items = undefined,
- .capacity = math.maxInt(usize),
- .allocator = a,
- };
- al.items.len = math.maxInt(usize);
-
- try testing.expectError(error.OutOfMemory, al.append(undefined));
- try testing.expectError(error.OutOfMemory, al.appendSlice(&.{undefined}));
- try testing.expectError(error.OutOfMemory, al.appendNTimes(undefined, 1));
- try testing.expectError(error.OutOfMemory, al.appendUnalignedSlice(&.{undefined}));
- try testing.expectError(error.OutOfMemory, al.addOne());
- try testing.expectError(error.OutOfMemory, al.addManyAt(0, 1));
- try testing.expectError(error.OutOfMemory, al.addManyAsArray(1));
- try testing.expectError(error.OutOfMemory, al.addManyAsSlice(1));
- try testing.expectError(error.OutOfMemory, al.insert(0, undefined));
- try testing.expectError(error.OutOfMemory, al.insertSlice(0, &.{undefined}));
- try testing.expectError(error.OutOfMemory, al.toOwnedSliceSentinel(0));
- try testing.expectError(error.OutOfMemory, al.ensureUnusedCapacity(1));
+ {
+ var list: ArrayListUnmanaged(u32) = .{
+ .items = undefined,
+ .capacity = math.maxInt(usize),
+ };
+ list.items.len = math.maxInt(usize);
+
+ try testing.expectError(error.OutOfMemory, list.append(a, new_item));
+ try testing.expectError(error.OutOfMemory, list.appendSlice(a, &.{new_item}));
+ try testing.expectError(error.OutOfMemory, list.appendNTimes(a, new_item, 1));
+ try testing.expectError(error.OutOfMemory, list.appendUnalignedSlice(a, &.{new_item}));
+ try testing.expectError(error.OutOfMemory, list.addOne(a));
+ try testing.expectError(error.OutOfMemory, list.addManyAt(a, 0, 1));
+ try testing.expectError(error.OutOfMemory, list.addManyAsArray(a, 1));
+ try testing.expectError(error.OutOfMemory, list.addManyAsSlice(a, 1));
+ try testing.expectError(error.OutOfMemory, list.insert(a, 0, new_item));
+ try testing.expectError(error.OutOfMemory, list.insertSlice(a, 0, &.{new_item}));
+ try testing.expectError(error.OutOfMemory, list.toOwnedSliceSentinel(a, 0));
+ try testing.expectError(error.OutOfMemory, list.ensureUnusedCapacity(a, 1));
+ }
+
+ {
+ var list: ArrayList(u32) = .{
+ .items = undefined,
+ .capacity = math.maxInt(usize),
+ .allocator = a,
+ };
+ list.items.len = math.maxInt(usize);
+
+ try testing.expectError(error.OutOfMemory, list.append(new_item));
+ try testing.expectError(error.OutOfMemory, list.appendSlice(&.{new_item}));
+ try testing.expectError(error.OutOfMemory, list.appendNTimes(new_item, 1));
+ try testing.expectError(error.OutOfMemory, list.appendUnalignedSlice(&.{new_item}));
+ try testing.expectError(error.OutOfMemory, list.addOne());
+ try testing.expectError(error.OutOfMemory, list.addManyAt(0, 1));
+ try testing.expectError(error.OutOfMemory, list.addManyAsArray(1));
+ try testing.expectError(error.OutOfMemory, list.addManyAsSlice(1));
+ try testing.expectError(error.OutOfMemory, list.insert(0, new_item));
+ try testing.expectError(error.OutOfMemory, list.insertSlice(0, &.{new_item}));
+ try testing.expectError(error.OutOfMemory, list.toOwnedSliceSentinel(0));
+ try testing.expectError(error.OutOfMemory, list.ensureUnusedCapacity(1));
+ }
}