std.array_list.addOrOom
function
Integer addition returning error.OutOfMemory on overflow.
fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize
Parameters
a: usize
b: usize
Errors
- OutOfMemory
std.array_list.Aligned
type-function
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 Aligned(comptime T: type, comptime alignment: ?mem.Alignment) type
Parameters
Fields
items: SliceContents of the list. This field is intended to be accessed directly.
Pointers to elements in this slice are invalidated by various functions of this ArrayList in accordance with the respective documentation. An invalidated pointer may point either to valid or freed memory.
capacity: usizeHow many T values this list can hold without allocating additional memory.
pointer_stability: debug.SafetyLockUsed to detect memory safety violations.
SelfemptySliceSentinelSliceinitCapacityinitBufferdeinitlockPointersunlockPointerstoManagedfromOwnedSlicefromOwnedSliceSentineltoOwnedSlicetoOwnedSliceSentineltoOwnedSliceAsserttoOwnedSliceSentinelAssertcloneinsertinsertAssumeCapacityinsertBoundedaddManyAtaddManyAtAssumeCapacityaddManyAtBoundedinsertSliceinsertSliceAssumeCapacityinsertSliceBoundedreplaceRangereplaceRangeAssumeCapacityreplaceRangeBoundedappendappendAssumeCapacityappendBoundedorderedRemoveorderedRemoveManyswapRemoveappendSliceappendSliceAssumeCapacityappendSliceBoundedappendUnalignedSliceappendUnalignedSliceAssumeCapacityappendUnalignedSliceBoundedprintprintAssumeCapacityprintBoundedappendNTimesappendNTimesAssumeCapacityappendNTimesBoundedresizeshrinkAndFreeshrinkAndFreePreciseshrinkToLenshrinkToLenSentinelshrinkRetainingCapacityclearRetainingCapacityclearAndFreeensureTotalCapacityensureTotalCapacityPreciseensureUnusedCapacityexpandToCapacityaddOneaddOneAssumeCapacityaddOneBoundedaddManyAsArrayaddManyAsArrayAssumeCapacityaddManyAsArrayBoundedaddManyAsSliceaddManyAsSliceAssumeCapacityaddManyAsSliceBoundedpopallocatedSliceunusedCapacitySlicegetLastgetLastOrNulllastlastPtrgrowCapacity
std.array_list.Aligned.addManyAsArray
function
Resize the array, adding n new elements, which have undefined values.
Invalidates element pointers if additional memory is required.
The return value is an array pointing to the newly allocated elements.
The returned pointer may be invalidated by further operations to this list.
pub fn addManyAsArray(self: *Self, gpa: Allocator, comptime n: usize) Allocator.Error!*[n]T
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.addManyAsArrayAssumeCapacity
function
Resize the array, adding n new elements, which have undefined values.
The return value is an array pointing to the newly allocated elements.
Never invalidates element pointers.
The returned pointer may be invalidated by further operations to this list.
Asserts that the list can hold the additional items.
pub fn addManyAsArrayAssumeCapacity(self: *Self, comptime n: usize) *[n]T
Parameters
self: *Self
n: usize
std.array_list.Aligned.addManyAsArrayBounded
function
Resize the array, adding n new elements, which have undefined values.
The return value is an array pointing to the newly allocated elements.
Never invalidates element pointers.
The returned pointer may be invalidated by further operations to this list.
If the list lacks unused capacity for the additional items, returns
error.OutOfMemory.
pub fn addManyAsArrayBounded(self: *Self, comptime n: usize) error{OutOfMemory}!*[n]T
Parameters
self: *Self
n: usize
Errors
- OutOfMemory
std.array_list.Aligned.addManyAsSlice
function
Resize the array, adding n new elements, which have undefined values.
The return value is a slice pointing to the newly allocated elements.
The returned pointer may be invalidated by further operations to this list.
Resizes list if self.capacity is not large enough.
pub fn addManyAsSlice(self: *Self, gpa: Allocator, n: usize) Allocator.Error![]T
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.addManyAsSliceAssumeCapacity
function
Resizes the array, adding n new elements, which have undefined
values, returning a slice pointing to the newly allocated elements.
Never invalidates element pointers.
The returned pointer may be invalidated by further operations to this list.
Asserts that the list can hold the additional items.
pub fn addManyAsSliceAssumeCapacity(self: *Self, n: usize) []T
Parameters
self: *Self
n: usize
std.array_list.Aligned.addManyAsSliceBounded
function
Resizes the array, adding n new elements, which have undefined
values, returning a slice pointing to the newly allocated elements.
Never invalidates element pointers.
The returned pointer may be invalidated by further operations to this list.
If the list lacks unused capacity for the additional items, returns
error.OutOfMemory.
pub fn addManyAsSliceBounded(self: *Self, n: usize) error{OutOfMemory}![]T
Parameters
self: *Self
n: usize
Errors
- OutOfMemory
std.array_list.Aligned.addManyAt
function
Add count new elements at position index, which have
undefined values. Returns a slice pointing to the newly allocated
elements, which becomes invalid after various ArrayList
operations.
Invalidates pre-existing pointers to elements at and after index.
Invalidates all pre-existing element pointers if capacity must be
increased to accommodate the new elements.
Asserts that the index is in bounds or equal to the length.
pub fn addManyAt( self: *Self, gpa: Allocator, index: usize, count: usize, ) Allocator.Error![]T
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.addManyAtAssumeCapacity
function
Add count new elements at position index, which have
undefined values. Returns a slice pointing to the newly allocated
elements, which becomes invalid after various ArrayList
operations.
Invalidates pre-existing pointers to elements at and after index.
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
Parameters
std.array_list.Aligned.addManyAtBounded
function
Add count new elements at position index, which have
undefined values, returning a slice pointing to the newly
allocated elements, which becomes invalid after various ArrayList
operations.
Invalidates pre-existing pointers to elements at and after index.
If the list lacks unused capacity for the additional items, returns
error.OutOfMemory.
Asserts that the index is in bounds or equal to the length.
pub fn addManyAtBounded(self: *Self, index: usize, count: usize) error{OutOfMemory}![]T
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.addOne
function
Increase length by 1, returning pointer to the new item. Invalidates element pointers if additional memory is needed. The returned pointer may be invalidated by further operations to this list.
pub fn addOne(self: *Self, gpa: Allocator) Allocator.Error!*T
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.addOneAssumeCapacity
function
Increase length by 1, returning pointer to the new item. Never invalidates element pointers. The returned pointer may be invalidated by further operations to this list. Asserts that the list can hold one additional item.
pub fn addOneAssumeCapacity(self: *Self) *T
Parameters
self: *Self
std.array_list.Aligned.addOneBounded
function
Increase length by 1, returning pointer to the new item.
Never invalidates element pointers.
The returned pointer may be invalidated by further operations to this list.
If the list lacks unused capacity for the additional item, returns error.OutOfMemory.
pub fn addOneBounded(self: *Self) error{OutOfMemory}!*T
Parameters
self: *Self
Errors
- OutOfMemory
std.array_list.Aligned.allocatedSlice
function
Returns a slice of all the items plus the extra capacity, whose memory
contents are undefined.
The returned pointer may be invalidated by further operations to this list.
pub fn allocatedSlice(self: Self) Slice
Parameters
self: Self
std.array_list.Aligned.append
function
Extend the list by 1 element. Allocates more memory as necessary. Invalidates element pointers if additional memory is needed.
pub fn append(self: *Self, gpa: Allocator, item: T) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.appendAssumeCapacity
function
Extend 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
Parameters
self: *Self
item: T
std.array_list.Aligned.appendBounded
function
Extend the list by 1 element.
Never invalidates element pointers.
If the list lacks unused capacity for the additional item, returns
error.OutOfMemory.
pub fn appendBounded(self: *Self, item: T) error{OutOfMemory}!void
Parameters
self: *Self
item: T
Errors
- OutOfMemory
std.array_list.Aligned.appendNTimes
function
Append a value to the list n times.
Allocates more memory as necessary.
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, gpa: Allocator, value: T, n: usize) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.appendNTimesAssumeCapacity
function
Append a value to the list n times.
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 the additional items.
pub inline fn appendNTimesAssumeCapacity(self: *Self, value: T, n: usize) void
Parameters
std.array_list.Aligned.appendNTimesBounded
function
Append a value to the list n times.
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.
If the list lacks unused capacity for the additional items, returns
error.OutOfMemory.
pub inline fn appendNTimesBounded(self: *Self, value: T, n: usize) error{OutOfMemory}!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.appendSlice
function
Append the slice of items to the list. Allocates more memory as necessary. Invalidates element pointers if additional memory is needed.
pub fn appendSlice(self: *Self, gpa: Allocator, items: []const T) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.appendSliceAssumeCapacity
function
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
Parameters
self: *Self
items: []const T
std.array_list.Aligned.appendSliceBounded
function
Append the slice of items to the list.
Never invalidates element pointers.
If the list lacks unused capacity for the additional items, returns error.OutOfMemory.
pub fn appendSliceBounded(self: *Self, items: []const T) error{OutOfMemory}!void
Parameters
self: *Self
items: []const T
Errors
- OutOfMemory
std.array_list.Aligned.appendUnalignedSlice
function
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 element pointers if additional memory is needed.
pub fn appendUnalignedSlice(self: *Self, gpa: Allocator, items: []align(1) const T) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.appendUnalignedSliceAssumeCapacity
function
Append an unaligned slice of items to the list.
Intended to be used only when appendSliceAssumeCapacity would be
a compile error.
Never invalidates element pointers.
Asserts that the list can hold the additional items.
pub fn appendUnalignedSliceAssumeCapacity(self: *Self, items: []align(1) const T) void
Parameters
self: *Self
items: []align(1) const T
std.array_list.Aligned.appendUnalignedSliceBounded
function
Append an unaligned slice of items to the list.
Intended to be used only when appendSliceAssumeCapacity would be
a compile error.
Never invalidates element pointers.
If the list lacks unused capacity for the additional items, returns
error.OutOfMemory.
pub fn appendUnalignedSliceBounded(self: *Self, items: []align(1) const T) error{OutOfMemory}!void
Parameters
self: *Self
items: []align(1) const T
Errors
- OutOfMemory
std.array_list.Aligned.clearAndFree
function
Invalidates all element pointers.
pub fn clearAndFree(self: *Self, gpa: Allocator) void
Parameters
std.array_list.Aligned.clearRetainingCapacity
function
Reduce length to 0. Invalidates all element pointers.
pub fn clearRetainingCapacity(self: *Self) void
Parameters
self: *Self
std.array_list.Aligned.clone
function
Creates a copy of this ArrayList.
pub fn clone(self: Self, gpa: Allocator) Allocator.Error!Self
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.deinit
function
Release all allocated memory.
pub fn deinit(self: *Self, gpa: Allocator) void
Parameters
std.array_list.Aligned.empty
constant
An ArrayList containing no elements.
Self
std.array_list.Aligned.ensureTotalCapacity
function
Modify the array so that it can hold at least new_capacity items.
Implements super-linear growth to achieve amortized O(1) append operations.
Invalidates element pointers if additional memory is needed.
pub fn ensureTotalCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.ensureTotalCapacityPrecise
function
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 element pointers if additional memory is needed.
pub fn ensureTotalCapacityPrecise(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.ensureUnusedCapacity
function
Modify the array so that it can hold at least additional_count more items.
Invalidates element pointers if additional memory is needed.
pub fn ensureUnusedCapacity( self: *Self, gpa: Allocator, additional_count: usize, ) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.expandToCapacity
function
Increases the array's length to match the full capacity that is already allocated.
The new elements have undefined values.
Never invalidates element pointers.
pub fn expandToCapacity(self: *Self) void
Parameters
self: *Self
std.array_list.Aligned.fromOwnedSlice
function
ArrayList takes ownership of the passed in slice.
Deinitialize with deinit or use toOwnedSlice.
pub fn fromOwnedSlice(slice: Slice) Self
Parameters
slice: Slice
std.array_list.Aligned.fromOwnedSliceSentinel
function
ArrayList takes ownership of the passed in slice.
Deinitialize with deinit or use toOwnedSlice.
pub fn fromOwnedSliceSentinel(comptime sentinel: T, slice: [:sentinel]T) Self
Parameters
sentinel: T
slice: [:sentinel]T
std.array_list.Aligned.getLast
function
Deprecated
pub fn getLast(self: Self) T
Parameters
self: Self
std.array_list.Aligned.getLastOrNull
alias
Deprecated in favor of last
Alias of std.array_list.Aligned.last
std.array_list.Aligned.growCapacity
function
Called when memory growth is necessary. Returns a capacity larger than minimum that grows super-linearly.
pub fn growCapacity(minimum: usize) usize
Parameters
minimum: usize
std.array_list.Aligned.initBuffer
function
Initialize with externally-managed memory. The buffer determines the capacity, and the length is set to zero.
When initialized this way, all functions that accept an Allocator argument cause illegal behavior.
pub fn initBuffer(buffer: Slice) Self
Parameters
buffer: Slice
std.array_list.Aligned.initCapacity
function
Initialize with capacity to hold exactly num elements.
Deinitialize with deinit or toOwnedSlice.
pub fn initCapacity(gpa: Allocator, num: usize) Allocator.Error!Self
Parameters
gpa: Allocator
num: usize
Errors
- OutOfMemory
std.array_list.Aligned.insert
function
Insert item at index index. Moves list[index .. list.len] to higher indices to make room.
If index is equal to the length of the list this operation is equivalent to append.
This operation is O(N).
Invalidates element pointers if additional memory is needed.
Invalidates pre-existing pointers to elements at and after index.
Asserts that the index is in bounds or equal to the length.
pub fn insert(self: *Self, gpa: Allocator, index: usize, item: T) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.insertAssumeCapacity
function
Insert item at index index. Moves list[index .. list.len] to higher indices to make room.
If index is equal to the length of the list this operation is
equivalent to appendAssumeCapacity.
This operation is O(N).
Invalidates pre-existing pointers to elements at and after index.
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, index: usize, item: T) void
Parameters
std.array_list.Aligned.insertBounded
function
Insert item at index index. Moves list[index .. list.len] to higher indices to make room.
If index is equal to the length of the list this operation is
equivalent to appendAssumeCapacity.
This operation is O(N).
Invalidates pre-existing pointers to elements at and after index.
Asserts that the index is in bounds or equal to the length.
If the list lacks unused capacity for the additional item, returns
error.OutOfMemory.
pub fn insertBounded(self: *Self, i: usize, item: T) error{OutOfMemory}!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.insertSlice
function
Insert slice items at index index by moving list[index .. list.len] to make room.
This operation is O(N).
Invalidates pre-existing pointers to elements at and after index.
Invalidates all pre-existing element pointers if capacity must be
increased to accommodate the new elements.
Asserts that the index is in bounds or equal to the length.
pub fn insertSlice( self: *Self, gpa: Allocator, index: usize, items: []const T, ) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.insertSliceAssumeCapacity
function
Insert slice items at index index by moving list[index .. list.len] to make room.
This operation is O(N).
Invalidates pre-existing pointers to elements at and after index.
Asserts that the list has capacity for the additional items.
Asserts that the index is in bounds or equal to the length.
pub fn insertSliceAssumeCapacity( self: *Self, index: usize, items: []const T, ) void
Parameters
std.array_list.Aligned.insertSliceBounded
function
Insert slice items at index index by moving list[index .. list.len] to make room.
This operation is O(N).
Invalidates pre-existing pointers to elements at and after index.
If the list lacks unused capacity for the additional items, returns
error.OutOfMemory.
Asserts that the index is in bounds or equal to the length.
pub fn insertSliceBounded( self: *Self, index: usize, items: []const T, ) error{OutOfMemory}!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.last
function
Returns the last element from the list, or null if the list is
empty.
pub fn last(self: Self) ?T
Parameters
self: Self
std.array_list.Aligned.lastPtr
function
Returns a pointer to the last element from the list, or null if
the list is empty.
The returned pointer may be invalidated by further operations to this list.
pub fn lastPtr(self: Self) ?*T
Parameters
self: Self
std.array_list.Aligned.lockPointers
function
Puts the unmanaged array list into a state where any method call that would cause an existing value pointer to become invalidated will instead trigger an assertion.
lockPointers may be called multiple times. This allows multiple
independent users of the list to keep it locked simultaneously.
unlockPointers restores the list to its previous state when
called the same number of times as lockPointers.
pub fn lockPointers(self: *Self) void
Parameters
self: *Self
std.array_list.Aligned.orderedRemove
function
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 the index is in bounds.
pub fn orderedRemove(self: *Self, i: usize) T
Parameters
self: *Self
i: usize
std.array_list.Aligned.orderedRemoveMany
function
Remove the elements indexed by sorted_indexes. The indexes to be
removed correspond to the array list before deletion.
Asserts:
- Each index to be removed is in bounds.
- The indexes to be removed are sorted ascending.
Duplicates in sorted_indexes are allowed.
This operation is O(N).
Invalidates element pointers beyond the first deleted index.
pub fn orderedRemoveMany(self: *Self, sorted_indexes: []const usize) void
Parameters
self: *Self
sorted_indexes: []const usize
std.array_list.Aligned.pop
function
Remove and return the last element from the list.
If the list is empty, returns null.
Invalidates pointers to last element.
pub fn pop(self: *Self) ?T
Parameters
self: *Self
std.array_list.Aligned.print
function
Prints a formatted string into this list. Invalidates element pointers if additional memory is needed.
pub fn print(self: *Self, gpa: Allocator, comptime fmt: []const u8, args: anytype) error{OutOfMemory}!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.printAssumeCapacity
function
Prints a formatted string into this list. Asserts that there is enough capacity for the write. Never invalidates element pointers.
pub fn printAssumeCapacity(self: *Self, comptime fmt: []const u8, args: anytype) void
Parameters
self: *Self
fmt: []const u8
std.array_list.Aligned.printBounded
function
Prints a formatted string into this list. Returns error.OutOfMemory if additional capacity is needed for the write. Never invalidates element pointers.
pub fn printBounded(self: *Self, comptime fmt: []const u8, args: anytype) error{OutOfMemory}!void
Parameters
self: *Self
fmt: []const u8
Errors
- OutOfMemory
std.array_list.Aligned.replaceRange
function
Grows or shrinks the list as necessary.
Invalidates element pointers if additional capacity is allocated,
Invalidates pointers to elements at and above index start + len
when len and new_items.len are unequal.
Asserts that the range is in bounds.
pub fn replaceRange( self: *Self, gpa: Allocator, start: usize, len: usize, new_items: []const T, ) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.replaceRangeAssumeCapacity
function
Grows or shrinks the list as necessary.
Invalidates pointers to elements at and above index start + len
when len and new_items.len are unequal.
Asserts the capacity is enough for additional items.
pub fn replaceRangeAssumeCapacity( self: *Self, start: usize, len: usize, new_items: []const T, ) void
Parameters
std.array_list.Aligned.replaceRangeBounded
function
Invalidates pointers to elements at and above index start + len
when len and new_items.len are unequal.
If the unused capacity is insufficient for additional items,
returns error.OutOfMemory.
pub fn replaceRangeBounded( self: *Self, start: usize, len: usize, new_items: []const T, ) error{OutOfMemory}!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.resize
function
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, gpa: Allocator, new_len: usize) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.Self
alias
Alias of std.array_list.Aligned
std.array_list.Aligned.SentinelSlice
type-function
pub fn SentinelSlice(comptime s: T) type
Parameters
s: T
std.array_list.Aligned.shrinkAndFree
function
Reduce allocated capacity to new_len.
May invalidate element pointers.
Asserts that the new length is less than or equal to the previous length.
pub fn shrinkAndFree(self: *Self, gpa: Allocator, new_len: usize) void
Parameters
std.array_list.Aligned.shrinkAndFreePrecise
function
Reduce allocated capacity to new_len.
May invalidate element pointers.
Asserts that the new length is less than or equal to the previous length.
If succeds capacity is guaranteed to be equal to the length.
pub fn shrinkAndFreePrecise(self: *Self, gpa: Allocator, new_len: usize) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.shrinkRetainingCapacity
function
Reduce length to new_len.
Invalidates pointers to elements items[new_len..].
Keeps capacity the same.
Asserts that the new length is less than or equal to the previous length.
pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void
Parameters
self: *Self
new_len: usize
std.array_list.Aligned.shrinkToLen
function
Shrinks capacity to match length.
May invalidate element pointers.
If succeds it is safe to call toOwnedSliceAssert.
pub fn shrinkToLen(self: *Self, gpa: Allocator) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.shrinkToLenSentinel
function
Shrinks or expands capacity to match length + 1.
May invalidate element pointers.
If succeds it is safe to call toOwnedSliceSentinelAssert.
pub fn shrinkToLenSentinel(self: *Self, gpa: Allocator) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.Slice
type
std.array_list.Aligned.swapRemove
function
Removes the element at the specified index and returns it. The empty slot is filled from the end of the list. Invalidates pointers to last element. This operation is O(1). Asserts that the index is in bounds.
pub fn swapRemove(self: *Self, i: usize) T
Parameters
self: *Self
i: usize
std.array_list.Aligned.toManaged
function
Convert this list into an analogous memory-managed one. The returned list has ownership of the underlying memory.
pub fn toManaged(self: *Self, gpa: Allocator) AlignedManaged(T, alignment)
Parameters
std.array_list.Aligned.toOwnedSlice
function
The caller owns the returned memory. Empties this ArrayList. Its capacity is cleared, making deinit() safe but unnecessary to call. May invalidate element pointers.
pub fn toOwnedSlice(self: *Self, gpa: Allocator) Allocator.Error!Slice
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.toOwnedSliceAssert
function
The caller owns the returned memory. Empties this ArrayList. Its capacity is cleared, making deinit() safe but unnecessary to call.
Asserts what the capacity is equal to the length. Never invalidates element pointers.
See also:
shrinkToLen
pub fn toOwnedSliceAssert(self: *Self) Slice
Parameters
self: *Self
std.array_list.Aligned.toOwnedSliceSentinel
function
The caller owns the returned memory. ArrayList becomes empty. May invalidate element pointers.
pub fn toOwnedSliceSentinel(self: *Self, gpa: Allocator, comptime sentinel: T) Allocator.Error!SentinelSlice(sentinel)
Parameters
Errors
- OutOfMemory
std.array_list.Aligned.toOwnedSliceSentinelAssert
function
The caller owns the returned memory. ArrayList becomes empty. Asserts what the capacity is equal to the length + 1. Never invalidates element pointers.
pub fn toOwnedSliceSentinelAssert(self: *Self, comptime sentinel: T) SentinelSlice(sentinel)
Parameters
self: *Self
sentinel: T
std.array_list.Aligned.unlockPointers
function
Undoes one call to lockPointers.
pub fn unlockPointers(self: *Self) void
Parameters
self: *Self
std.array_list.Aligned.unusedCapacitySlice
function
Returns a slice of only the extra capacity after items.
This can be useful for writing directly into an ArrayList.
Note that such an operation must be followed up with a direct
modification of self.items.len.
The returned pointer may be invalidated by further operations to this list.
pub fn unusedCapacitySlice(self: Self) []T
Parameters
self: Self
std.array_list.AlignedManaged
type-function
Deprecated.
pub fn AlignedManaged(comptime T: type, comptime alignment: ?mem.Alignment) type
Parameters
Fields
items: SliceContents of the list. This field is intended to be accessed directly.
Pointers to elements in this slice are invalidated by various functions of this ArrayList in accordance with the respective documentation. An invalidated pointer may point either to valid or freed memory.
capacity: usizeHow many T values this list can hold without allocating additional memory.
allocator: Allocator
pointer_stability: debug.SafetyLockUsed to detect memory safety violations.
SelfSliceSentinelSliceinitinitCapacitydeinitlockPointersunlockPointersfromOwnedSlicefromOwnedSliceSentinelmoveToUnmanagedtoOwnedSlicetoOwnedSliceSentinelcloneinsertinsertAssumeCapacityaddManyAtaddManyAtAssumeCapacityinsertSlicereplaceRangereplaceRangeAssumeCapacityappendappendAssumeCapacityorderedRemoveswapRemoveappendSliceappendSliceAssumeCapacityappendUnalignedSliceappendUnalignedSliceAssumeCapacityprintappendNTimesappendNTimesAssumeCapacityresizeshrinkAndFreeshrinkRetainingCapacityclearRetainingCapacityclearAndFreeensureTotalCapacityensureTotalCapacityPreciseensureUnusedCapacityexpandToCapacityaddOneaddOneAssumeCapacityaddManyAsArrayaddManyAsArrayAssumeCapacityaddManyAsSliceaddManyAsSliceAssumeCapacitypopallocatedSliceunusedCapacitySlicegetLastgetLastOrNulllastlastPtr
std.array_list.AlignedManaged.addManyAsArray
function
Resize the array, adding n new elements, which have undefined values.
The return value is an array pointing to the newly allocated elements.
The returned pointer may be invalidated by further operations to this list.
Resizes list if self.capacity is not large enough.
Invalidates element pointers if additional memory is needed.
pub fn addManyAsArray(self: *Self, comptime n: usize) Allocator.Error!*[n]T
Parameters
self: *Self
n: usize
Errors
- OutOfMemory
std.array_list.AlignedManaged.addManyAsArrayAssumeCapacity
function
Resize the array, adding n new elements, which have undefined values.
The return value is an array pointing to the newly allocated elements.
Never invalidates element pointers.
The returned pointer may be invalidated by further operations to this list.
Asserts that the list can hold the additional items.
pub fn addManyAsArrayAssumeCapacity(self: *Self, comptime n: usize) *[n]T
Parameters
self: *Self
n: usize
std.array_list.AlignedManaged.addManyAsSlice
function
Resize the array, adding n new elements, which have undefined values.
The return value is a slice pointing to the newly allocated elements.
The returned pointer may be invalidated by further operations to this list.
Resizes list if self.capacity is not large enough.
Invalidates element pointers if additional memory is needed.
pub fn addManyAsSlice(self: *Self, n: usize) Allocator.Error![]T
Parameters
self: *Self
n: usize
Errors
- OutOfMemory
std.array_list.AlignedManaged.addManyAsSliceAssumeCapacity
function
Resize the array, adding n new elements, which have undefined values.
The return value is a slice pointing to the newly allocated elements.
Never invalidates element pointers.
The returned pointer may be invalidated by further operations to this list.
Asserts that the list can hold the additional items.
pub fn addManyAsSliceAssumeCapacity(self: *Self, n: usize) []T
Parameters
self: *Self
n: usize
std.array_list.AlignedManaged.addManyAt
function
Add count new elements at position index, which have
undefined values. Returns a slice pointing to the newly allocated
elements, which becomes invalid after various ArrayList
operations.
Invalidates pre-existing pointers to elements at and after index.
Invalidates all pre-existing element pointers if capacity must be
increased to accommodate the new elements.
Asserts that the index is in bounds or equal to the length.
pub fn addManyAt(self: *Self, index: usize, count: usize) Allocator.Error![]T
Parameters
Errors
- OutOfMemory
std.array_list.AlignedManaged.addManyAtAssumeCapacity
function
Add count new elements at position index, which have
undefined values. Returns a slice pointing to the newly allocated
elements, which becomes invalid after various ArrayList
operations.
Invalidates pre-existing pointers to elements at and after index.
Asserts that there is enough capacity for the new elements.
Asserts that the index is in bounds or equal to the length.
pub fn addManyAtAssumeCapacity(self: *Self, index: usize, count: usize) []T
Parameters
std.array_list.AlignedManaged.addOne
function
Increase length by 1, returning pointer to the new item. Invalidates element pointers if additional memory is needed. The returned pointer may be invalidated by further operations to this list.
pub fn addOne(self: *Self) Allocator.Error!*T
Parameters
self: *Self
Errors
- OutOfMemory
std.array_list.AlignedManaged.addOneAssumeCapacity
function
Increase length by 1, returning pointer to the new item. The returned pointer may be invalidated by further operations to this list. Never invalidates element pointers. Asserts that the list can hold one additional item.
pub fn addOneAssumeCapacity(self: *Self) *T
Parameters
self: *Self
std.array_list.AlignedManaged.allocatedSlice
function
Returns a slice of all the items plus the extra capacity, whose memory
contents are undefined.
The returned pointer may be invalidated by further operations to this list.
pub fn allocatedSlice(self: Self) Slice
Parameters
self: Self
std.array_list.AlignedManaged.append
function
Extends the list by 1 element. Allocates more memory as necessary. Invalidates element pointers if additional memory is needed.
pub fn append(self: *Self, item: T) Allocator.Error!void
Parameters
self: *Self
item: T
Errors
- OutOfMemory
std.array_list.AlignedManaged.appendAssumeCapacity
function
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
Parameters
self: *Self
item: T
std.array_list.AlignedManaged.appendNTimes
function
Append a value to the list n times.
Allocates more memory as necessary.
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
Parameters
Errors
- OutOfMemory
std.array_list.AlignedManaged.appendNTimesAssumeCapacity
function
Append a value to the list n times.
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 the additional items.
pub inline fn appendNTimesAssumeCapacity(self: *Self, value: T, n: usize) void
Parameters
std.array_list.AlignedManaged.appendSlice
function
Append the slice of items to the list. Allocates more memory as necessary. Invalidates element pointers if additional memory is needed.
pub fn appendSlice(self: *Self, items: []const T) Allocator.Error!void
Parameters
self: *Self
items: []const T
Errors
- OutOfMemory
std.array_list.AlignedManaged.appendSliceAssumeCapacity
function
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
Parameters
self: *Self
items: []const T
std.array_list.AlignedManaged.appendUnalignedSlice
function
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 element pointers if additional memory is needed.
pub fn appendUnalignedSlice(self: *Self, items: []align(1) const T) Allocator.Error!void
Parameters
self: *Self
items: []align(1) const T
Errors
- OutOfMemory
std.array_list.AlignedManaged.appendUnalignedSliceAssumeCapacity
function
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
Parameters
self: *Self
items: []align(1) const T
std.array_list.AlignedManaged.clearAndFree
function
Invalidates all element pointers.
pub fn clearAndFree(self: *Self) void
Parameters
self: *Self
std.array_list.AlignedManaged.clearRetainingCapacity
function
Reduce length to 0. Invalidates all element pointers.
pub fn clearRetainingCapacity(self: *Self) void
Parameters
self: *Self
std.array_list.AlignedManaged.clone
function
Creates a copy of this ArrayList, using the same allocator.
pub fn clone(self: Self) Allocator.Error!Self
Parameters
self: Self
Errors
- OutOfMemory
std.array_list.AlignedManaged.deinit
function
Release all allocated memory.
pub fn deinit(self: Self) void
Parameters
self: Self
std.array_list.AlignedManaged.ensureTotalCapacity
function
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 element pointers if additional memory is needed.
pub fn ensureTotalCapacity(self: *Self, new_capacity: usize) Allocator.Error!void
Parameters
self: *Self
new_capacity: usize
Errors
- OutOfMemory
std.array_list.AlignedManaged.ensureTotalCapacityPrecise
function
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 element pointers if additional memory is needed.
pub fn ensureTotalCapacityPrecise(self: *Self, new_capacity: usize) Allocator.Error!void
Parameters
self: *Self
new_capacity: usize
Errors
- OutOfMemory
std.array_list.AlignedManaged.ensureUnusedCapacity
function
Modify the array so that it can hold at least additional_count more items.
Invalidates element pointers if additional memory is needed.
pub fn ensureUnusedCapacity(self: *Self, additional_count: usize) Allocator.Error!void
Parameters
self: *Self
additional_count: usize
Errors
- OutOfMemory
std.array_list.AlignedManaged.expandToCapacity
function
Increases the array's length to match the full capacity that is already allocated.
The new elements have undefined values.
Never invalidates element pointers.
pub fn expandToCapacity(self: *Self) void
Parameters
self: *Self
std.array_list.AlignedManaged.fromOwnedSlice
function
ArrayList takes ownership of the passed in slice. The slice must have been
allocated with gpa.
Deinitialize with deinit or use toOwnedSlice.
pub fn fromOwnedSlice(gpa: Allocator, slice: Slice) Self
Parameters
std.array_list.AlignedManaged.fromOwnedSliceSentinel
function
ArrayList takes ownership of the passed in slice. The slice must have been
allocated with gpa.
Deinitialize with deinit or use toOwnedSlice.
pub fn fromOwnedSliceSentinel(gpa: Allocator, comptime sentinel: T, slice: [:sentinel]T) Self
Parameters
std.array_list.AlignedManaged.getLast
function
Deprecated
pub fn getLast(self: Self) T
Parameters
self: Self
std.array_list.AlignedManaged.getLastOrNull
alias
Deprecated in favor of last
Alias of std.array_list.AlignedManaged.last
std.array_list.AlignedManaged.init
function
Deinitialize with deinit or use toOwnedSlice.
pub fn init(gpa: Allocator) Self
Parameters
gpa: Allocator
std.array_list.AlignedManaged.initCapacity
function
Initialize with capacity to hold num elements.
The resulting capacity will equal num exactly.
Deinitialize with deinit or use toOwnedSlice.
pub fn initCapacity(gpa: Allocator, num: usize) Allocator.Error!Self
Parameters
gpa: Allocator
num: usize
Errors
- OutOfMemory
std.array_list.AlignedManaged.insert
function
Insert item at index index. Moves list[index .. list.len] to higher indices to make room.
If index is equal to the length of the list this operation is equivalent to append.
This operation is O(N).
Invalidates element pointers if additional memory is needed.
Invalidates pre-existing pointers to elements at and after index.
Asserts that the index is in bounds or equal to the length.
pub fn insert(self: *Self, index: usize, item: T) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.AlignedManaged.insertAssumeCapacity
function
Insert item at index index. Moves list[index .. list.len] to higher indices to make room.
If index is equal to the length of the list this operation is
equivalent to appendAssumeCapacity.
This operation is O(N).
Invalidates pre-existing pointers to elements at and after index.
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, index: usize, item: T) void
Parameters
std.array_list.AlignedManaged.insertSlice
function
Insert slice items at index index by moving list[index .. list.len] to make room.
This operation is O(N).
Invalidates pre-existing pointers to elements at and after index.
Invalidates all pre-existing element pointers if capacity must be
increased to accommodate the new elements.
Asserts that the index is in bounds or equal to the length.
pub fn insertSlice( self: *Self, index: usize, items: []const T, ) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.AlignedManaged.last
function
Returns the last element from the list, or null if the list is
empty.
Never invalidates element pointers.
pub fn last(self: Self) ?T
Parameters
self: Self
std.array_list.AlignedManaged.lastPtr
function
Returns a pointer to the last element from the list, or null if
the list is empty.
The returned pointer may be invalidated by further operations to this list.
pub fn lastPtr(self: Self) ?*T
Parameters
self: Self
std.array_list.AlignedManaged.lockPointers
function
Puts the array list into a state where any method call that would cause an existing value pointer to become invalidated will instead trigger an assertion.
lockPointers may be called multiple times. This allows multiple
independent users of the list to keep it locked simultaneously.
unlockPointers restores the list to its previous state when
called the same number of times as lockPointers.
pub fn lockPointers(self: *Self) void
Parameters
self: *Self
std.array_list.AlignedManaged.moveToUnmanaged
function
Initializes an ArrayList with the items and capacity fields
of this ArrayList. Empties this ArrayList.
pub fn moveToUnmanaged(self: *Self) Aligned(T, alignment)
Parameters
self: *Self
std.array_list.AlignedManaged.orderedRemove
function
Remove the element at index i, shift elements after index
i forward, and return the removed element.
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 the index is in bounds.
Asserts that the list is not empty.
pub fn orderedRemove(self: *Self, i: usize) T
Parameters
self: *Self
i: usize
std.array_list.AlignedManaged.pop
function
Remove and return the last element from the list, or return null if list is empty.
Invalidates element pointers to the removed element.
pub fn pop(self: *Self) ?T
Parameters
self: *Self
std.array_list.AlignedManaged.print
function
Prints a formatted string into this list. Invalidates element pointers if additional memory is needed.
pub fn print(self: *Self, comptime fmt: []const u8, args: anytype) error{OutOfMemory}!void
Parameters
self: *Self
fmt: []const u8
Errors
- OutOfMemory
std.array_list.AlignedManaged.replaceRange
function
Grows or shrinks the list as necessary.
Invalidates element pointers if additional capacity is allocated,
Invalidates pointers to elements at and above index start + len
when len and new_items.len are unequal.
Asserts that the range is in bounds.
pub fn replaceRange(self: *Self, start: usize, len: usize, new_items: []const T) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.array_list.AlignedManaged.replaceRangeAssumeCapacity
function
Grows or shrinks the list as necessary.
Invalidates pointers to elements at and above index start + len
when len and new_items.len are unequal.
Asserts the capacity is enough for additional items.
pub fn replaceRangeAssumeCapacity(self: *Self, start: usize, len: usize, new_items: []const T) void
Parameters
std.array_list.AlignedManaged.resize
function
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
Parameters
self: *Self
new_len: usize
Errors
- OutOfMemory
std.array_list.AlignedManaged.Self
alias
Alias of std.array_list.AlignedManaged
std.array_list.AlignedManaged.SentinelSlice
type-function
pub fn SentinelSlice(comptime s: T) type
Parameters
s: T
std.array_list.AlignedManaged.shrinkAndFree
function
Reduce allocated capacity to new_len.
May invalidate element pointers.
Asserts that the new length is less than or equal to the previous length.
pub fn shrinkAndFree(self: *Self, new_len: usize) void
Parameters
self: *Self
new_len: usize
std.array_list.AlignedManaged.shrinkRetainingCapacity
function
Reduce length to new_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
Parameters
self: *Self
new_len: usize
std.array_list.AlignedManaged.Slice
type
std.array_list.AlignedManaged.swapRemove
function
Removes the element at the specified index and returns it.
The empty slot is filled from the end of the list.
Invalidates pointers to 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 the index is in bounds.
pub fn swapRemove(self: *Self, i: usize) T
Parameters
self: *Self
i: usize
std.array_list.AlignedManaged.toOwnedSlice
function
The caller owns the returned memory. Empties this ArrayList.
Its capacity is cleared, making deinit safe but unnecessary to call.
May invalidate element pointers if remapping memory cannot be done in place.
pub fn toOwnedSlice(self: *Self) Allocator.Error!Slice
Parameters
self: *Self
Errors
- OutOfMemory
std.array_list.AlignedManaged.toOwnedSliceSentinel
function
The caller owns the returned memory. Empties this ArrayList. May invalidate element pointers if remapping memory cannot be done in place.
pub fn toOwnedSliceSentinel(self: *Self, comptime sentinel: T) Allocator.Error!SentinelSlice(sentinel)
Parameters
self: *Self
sentinel: T
Errors
- OutOfMemory
std.array_list.AlignedManaged.unlockPointers
function
Undoes one call to lockPointers.
pub fn unlockPointers(self: *Self) void
Parameters
self: *Self
std.array_list.AlignedManaged.unusedCapacitySlice
function
Returns a slice of only the extra capacity after items.
This can be useful for writing directly into an ArrayList.
Note that such an operation must be followed up with a direct
modification of self.items.len.
The returned pointer may be invalidated by further operations to this list.
pub fn unusedCapacitySlice(self: Self) []T
Parameters
self: Self
std.array_list.Allocator
alias
Alias of std.mem.Allocator
std.array_list.ArrayList
alias
Alias of std.ArrayList
std.array_list.assert
alias
Alias of std.debug.assert
std.array_list.debug
alias
Alias of std.debug
std.array_list.Item
container
Fields
std.array_list.ItemUnmanaged
container
Fields
integer: i32
sub_items: ArrayList(ItemUnmanaged)
std.array_list.Managed
type-function
Deprecated.
pub fn Managed(comptime T: type) type
Parameters
T: type
Fields
items: SliceContents of the list. This field is intended to be accessed directly.
Pointers to elements in this slice are invalidated by various functions of this ArrayList in accordance with the respective documentation. An invalidated pointer may point either to valid or freed memory.
capacity: usizeHow many T values this list can hold without allocating additional memory.
allocator: Allocator
pointer_stability: debug.SafetyLockUsed to detect memory safety violations.
SelfSliceSentinelSliceinitinitCapacitydeinitlockPointersunlockPointersfromOwnedSlicefromOwnedSliceSentinelmoveToUnmanagedtoOwnedSlicetoOwnedSliceSentinelcloneinsertinsertAssumeCapacityaddManyAtaddManyAtAssumeCapacityinsertSlicereplaceRangereplaceRangeAssumeCapacityappendappendAssumeCapacityorderedRemoveswapRemoveappendSliceappendSliceAssumeCapacityappendUnalignedSliceappendUnalignedSliceAssumeCapacityprintappendNTimesappendNTimesAssumeCapacityresizeshrinkAndFreeshrinkRetainingCapacityclearRetainingCapacityclearAndFreeensureTotalCapacityensureTotalCapacityPreciseensureUnusedCapacityexpandToCapacityaddOneaddOneAssumeCapacityaddManyAsArrayaddManyAsArrayAssumeCapacityaddManyAsSliceaddManyAsSliceAssumeCapacitypopallocatedSliceunusedCapacitySlicegetLastgetLastOrNulllastlastPtr
std.array_list.math
alias
Alias of std.math
std.array_list.mem
alias
Alias of std.mem
std.array_list.std
alias
Alias of std
std.array_list.testing
alias
Alias of std.testing
Source code
std/array_list.zig
const std = @import("std.zig");
const debug = std.debug;
const assert = debug.assert;
const testing = std.testing;
const mem = std.mem;
const math = std.math;
const Allocator = mem.Allocator;
const ArrayList = std.ArrayList;
/// Deprecated.
pub fn Managed(comptime T: type) type {
return AlignedManaged(T, null);
}
/// Deprecated.
pub fn AlignedManaged(comptime T: type, comptime alignment: ?mem.Alignment) type {
if (alignment) |a| {
if (a.toByteUnits() == @alignOf(T)) {
return AlignedManaged(T, null);
}
}
return struct {
const Self = @This();
/// Contents of the list. This field is intended to be accessed
/// directly.
///
/// Pointers to elements in this slice are invalidated by various
/// functions of this ArrayList in accordance with the respective
/// documentation.
/// An invalidated pointer may point either to valid or freed memory.
items: Slice,
/// How many T values this list can hold without allocating
/// additional memory.
capacity: usize,
allocator: Allocator,
/// Used to detect memory safety violations.
pointer_stability: debug.SafetyLock,
pub const Slice = if (alignment) |a| ([]align(a.toByteUnits()) T) else []T;
pub fn SentinelSlice(comptime s: T) type {
return if (alignment) |a| ([:s]align(a.toByteUnits()) T) else [:s]T;
}
/// Deinitialize with `deinit` or use `toOwnedSlice`.
pub fn init(gpa: Allocator) Self {
return Self{
.items = &[_]T{},
.capacity = 0,
.allocator = gpa,
.pointer_stability = .{},
};
}
/// Initialize with capacity to hold `num` elements.
/// The resulting capacity will equal `num` exactly.
/// Deinitialize with `deinit` or use `toOwnedSlice`.
pub fn initCapacity(gpa: Allocator, num: usize) Allocator.Error!Self {
var self = Self.init(gpa);
try self.ensureTotalCapacityPrecise(num);
return self;
}
/// Release all allocated memory.
pub fn deinit(self: Self) void {
self.pointer_stability.assertUnlocked();
if (@sizeOf(T) > 0) {
self.allocator.free(self.allocatedSlice());
}
}
/// Puts the array list into a state where any method call that would
/// cause an existing value pointer to become invalidated will
/// instead trigger an assertion.
///
/// `lockPointers` may be called multiple times. This allows multiple
/// independent users of the list to keep it locked simultaneously.
///
/// `unlockPointers` restores the list to its previous state when
/// called the same number of times as `lockPointers`.
pub fn lockPointers(self: *Self) void {
self.pointer_stability.lockShared();
}
/// Undoes one call to `lockPointers`.
pub fn unlockPointers(self: *Self) void {
self.pointer_stability.unlockShared();
}
/// ArrayList takes ownership of the passed in slice. The slice must have been
/// allocated with `gpa`.
/// Deinitialize with `deinit` or use `toOwnedSlice`.
pub fn fromOwnedSlice(gpa: Allocator, slice: Slice) Self {
return Self{
.items = slice,
.capacity = slice.len,
.allocator = gpa,
.pointer_stability = .{},
};
}
/// ArrayList takes ownership of the passed in slice. The slice must have been
/// allocated with `gpa`.
/// Deinitialize with `deinit` or use `toOwnedSlice`.
pub fn fromOwnedSliceSentinel(gpa: Allocator, comptime sentinel: T, slice: [:sentinel]T) Self {
return Self{
.items = slice,
.capacity = slice.len + 1,
.allocator = gpa,
.pointer_stability = .{},
};
}
/// Initializes an ArrayList with the `items` and `capacity` fields
/// of this ArrayList. Empties this ArrayList.
pub fn moveToUnmanaged(self: *Self) Aligned(T, alignment) {
const allocator = self.allocator;
const result: Aligned(T, alignment) = .{
.items = self.items,
.capacity = self.capacity,
.pointer_stability = self.pointer_stability,
};
self.* = init(allocator);
return result;
}
/// The caller owns the returned memory. Empties this ArrayList.
/// Its capacity is cleared, making `deinit` safe but unnecessary to call.
/// May invalidate element pointers if remapping memory cannot be done in place.
pub fn toOwnedSlice(self: *Self) Allocator.Error!Slice {
self.pointer_stability.assertUnlocked();
const allocator = self.allocator;
const old_memory = self.allocatedSlice();
if (allocator.remap(old_memory, self.items.len)) |new_items| {
self.* = init(allocator);
return new_items;
}
const new_memory = try allocator.alignedAlloc(T, alignment, self.items.len);
@memcpy(new_memory, self.items);
self.clearAndFree();
return new_memory;
}
/// The caller owns the returned memory. Empties this ArrayList.
/// May invalidate element pointers if remapping memory cannot be done in place.
pub fn toOwnedSliceSentinel(self: *Self, comptime sentinel: T) Allocator.Error!SentinelSlice(sentinel) {
// This addition can never overflow because `self.items` can never occupy the whole address space
try self.ensureTotalCapacityPrecise(self.items.len + 1);
self.appendAssumeCapacity(sentinel);
const result = try self.toOwnedSlice();
return result[0 .. result.len - 1 :sentinel];
}
/// Creates a copy of this ArrayList, using the same allocator.
pub fn clone(self: Self) Allocator.Error!Self {
var cloned = try Self.initCapacity(self.allocator, self.capacity);
cloned.appendSliceAssumeCapacity(self.items);
return cloned;
}
/// Insert `item` at index `index`. Moves `list[index .. list.len]` to higher indices to make room.
/// If `index` is equal to the length of the list this operation is equivalent to append.
/// This operation is O(N).
/// Invalidates element pointers if additional memory is needed.
/// Invalidates pre-existing pointers to elements at and after `index`.
/// Asserts that the index is in bounds or equal to the length.
pub fn insert(self: *Self, index: usize, item: T) Allocator.Error!void {
self.pointer_stability.assertUnlocked();
const dst = try self.addManyAt(index, 1);
dst[0] = item;
}
/// Insert `item` at index `index`. Moves `list[index .. list.len]` to higher indices to make room.
/// If `index` is equal to the length of the list this operation is
/// equivalent to appendAssumeCapacity.
/// This operation is O(N).
/// Invalidates pre-existing pointers to elements at and after `index`.
/// 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, index: usize, item: T) void {
self.pointer_stability.assertUnlocked();
assert(self.items.len < self.capacity);
self.items.len += 1;
@memmove(self.items[index + 1 .. self.items.len], self.items[index .. self.items.len - 1]);
self.items[index] = item;
}
/// Add `count` new elements at position `index`, which have
/// `undefined` values. Returns a slice pointing to the newly allocated
/// elements, which becomes invalid after various `ArrayList`
/// operations.
/// Invalidates pre-existing pointers to elements at and after `index`.
/// Invalidates all pre-existing element pointers if capacity must be
/// increased to accommodate the new elements.
/// 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);
self.pointer_stability.assertUnlocked();
if (self.capacity >= new_len)
return addManyAtAssumeCapacity(self, index, count);
// Here we avoid copying allocated but unused bytes by
// attempting a resize in place, and falling back to allocating
// a new buffer and doing our own copy. With a realloc() call,
// the allocator implementation would pointlessly copy our
// extra capacity.
const new_capacity = Aligned(T, alignment).growCapacity(new_len);
const old_memory = self.allocatedSlice();
if (self.allocator.remap(old_memory, new_capacity)) |new_memory| {
self.items.ptr = new_memory.ptr;
self.capacity = new_memory.len;
return addManyAtAssumeCapacity(self, index, count);
}
// Make a new allocation, avoiding `ensureTotalCapacity` in order
// to avoid extra memory copies.
const new_memory = try self.allocator.alignedAlloc(T, alignment, new_capacity);
const to_move = self.items[index..];
@memcpy(new_memory[0..index], self.items[0..index]);
@memcpy(new_memory[index + count ..][0..to_move.len], to_move);
self.allocator.free(old_memory);
self.items = new_memory[0..new_len];
self.capacity = new_memory.len;
// The inserted elements at `new_memory[index..][0..count]` have
// already been set to `undefined` by memory allocation.
return new_memory[index..][0..count];
}
/// Add `count` new elements at position `index`, which have
/// `undefined` values. Returns a slice pointing to the newly allocated
/// elements, which becomes invalid after various `ArrayList`
/// operations.
/// Invalidates pre-existing pointers to elements at and after `index`.
/// Asserts that there is enough capacity for the new elements.
/// Asserts that the index is in bounds or equal to the length.
pub fn addManyAtAssumeCapacity(self: *Self, index: usize, count: usize) []T {
self.pointer_stability.assertUnlocked();
const new_len = self.items.len + count;
assert(self.capacity >= new_len);
const to_move = self.items[index..];
self.items.len = new_len;
@memmove(self.items[index + count ..][0..to_move.len], to_move);
const result = self.items[index..][0..count];
@memset(result, undefined);
return result;
}
/// Insert slice `items` at index `index` by moving `list[index .. list.len]` to make room.
/// This operation is O(N).
/// Invalidates pre-existing pointers to elements at and after `index`.
/// Invalidates all pre-existing element pointers if capacity must be
/// increased to accommodate the new elements.
/// Asserts that the index is in bounds or equal to the length.
pub fn insertSlice(
self: *Self,
index: usize,
items: []const T,
) Allocator.Error!void {
const dst = try self.addManyAt(index, items.len);
@memcpy(dst, items);
}
/// Grows or shrinks the list as necessary.
/// Invalidates element pointers if additional capacity is allocated,
/// Invalidates pointers to elements at and above index `start + len`
/// when `len` and `new_items.len` are unequal.
/// Asserts that the range is in bounds.
pub fn replaceRange(self: *Self, start: usize, len: usize, new_items: []const T) Allocator.Error!void {
var unmanaged = self.moveToUnmanaged();
defer self.* = unmanaged.toManaged(self.allocator);
return unmanaged.replaceRange(self.allocator, start, len, new_items);
}
/// Grows or shrinks the list as necessary.
/// Invalidates pointers to elements at and above index `start + len`
/// when `len` and `new_items.len` are unequal.
/// Asserts the capacity is enough for additional items.
pub fn replaceRangeAssumeCapacity(self: *Self, start: usize, len: usize, new_items: []const T) void {
var unmanaged = self.moveToUnmanaged();
defer self.* = unmanaged.toManaged(self.allocator);
return unmanaged.replaceRangeAssumeCapacity(start, len, new_items);
}
/// Extends the list by 1 element. Allocates more memory as necessary.
/// 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.
/// Never invalidates element pointers.
/// Asserts that the list can hold one additional item.
pub fn appendAssumeCapacity(self: *Self, item: T) void {
self.addOneAssumeCapacity().* = item;
}
/// Remove the element at index `i`, shift elements after index
/// `i` forward, and return the removed element.
/// 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 the index is in bounds.
/// Asserts that the list is not empty.
pub fn orderedRemove(self: *Self, i: usize) T {
const old_item = self.items[i];
self.replaceRangeAssumeCapacity(i, 1, &.{});
return old_item;
}
/// Removes the element at the specified index and returns it.
/// The empty slot is filled from the end of the list.
/// Invalidates pointers to 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 the index is in bounds.
pub fn swapRemove(self: *Self, i: usize) T {
self.pointer_stability.assertUnlocked();
const val = self.items[i];
self.items[i] = self.items[self.items.len - 1];
self.items[self.items.len - 1] = undefined;
self.items.len -= 1;
return val;
}
/// Append the slice of items to the list. Allocates more
/// memory as necessary.
/// 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.
/// 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;
assert(new_len <= self.capacity);
self.items.len = new_len;
@memcpy(self.items[old_len..][0..items.len], items);
}
/// 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 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.
/// 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;
assert(new_len <= self.capacity);
self.items.len = new_len;
@memcpy(self.items[old_len..][0..items.len], items);
}
/// Prints a formatted string into this list.
/// Invalidates element pointers if additional memory is needed.
pub fn print(self: *Self, comptime fmt: []const u8, args: anytype) error{OutOfMemory}!void {
const gpa = self.allocator;
var unmanaged = self.moveToUnmanaged();
defer self.* = unmanaged.toManaged(gpa);
try unmanaged.print(gpa, fmt, args);
}
/// Append a value to the list `n` times.
/// Allocates more memory as necessary.
/// 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(old_len, n));
@memset(self.items[old_len..self.items.len], value);
}
/// Append a value to the list `n` times.
/// 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 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);
@memset(self.items.ptr[self.items.len..new_len], value);
self.items.len = new_len;
}
/// 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;
}
/// Reduce allocated capacity to `new_len`.
/// May invalidate element pointers.
/// 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);
self.* = unmanaged.toManaged(self.allocator);
}
/// Reduce length to `new_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 {
self.pointer_stability.assertUnlocked();
assert(new_len <= self.items.len);
@memset(self.items[new_len..], undefined);
self.items.len = new_len;
}
/// Reduce length to 0.
/// Invalidates all element pointers.
pub fn clearRetainingCapacity(self: *Self) void {
self.pointer_stability.assertUnlocked();
@memset(self.items, undefined);
self.items.len = 0;
}
/// Invalidates all element pointers.
pub fn clearAndFree(self: *Self) void {
self.pointer_stability.assertUnlocked();
self.allocator.free(self.allocatedSlice());
self.items.len = 0;
self.capacity = 0;
}
/// 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 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);
return;
}
// Protects growing unnecessarily since better_capacity will be larger.
if (self.capacity >= new_capacity) return;
const better_capacity = Aligned(T, alignment).growCapacity(new_capacity);
return self.ensureTotalCapacityPrecise(better_capacity);
}
/// 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 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);
return;
}
if (self.capacity >= new_capacity) return;
self.pointer_stability.assertUnlocked();
// Here we avoid copying allocated but unused bytes by
// attempting a remap, and falling back to allocating
// a new buffer and doing our own copy. With a realloc() call,
// the allocator implementation would pointlessly copy our
// extra capacity.
const old_memory = self.allocatedSlice();
if (self.allocator.remap(old_memory, new_capacity)) |new_memory| {
self.items.ptr = new_memory.ptr;
self.capacity = new_memory.len;
} else {
const new_memory = try self.allocator.alignedAlloc(T, alignment, new_capacity);
@memcpy(new_memory[0..self.items.len], self.items);
self.allocator.free(old_memory);
self.items.ptr = new_memory.ptr;
self.capacity = new_memory.len;
}
}
/// Modify the array so that it can hold at least `additional_count` **more** items.
/// 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.
/// 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.
/// Invalidates element pointers if additional memory is needed.
/// The returned pointer may be invalidated by further operations to this list.
pub fn addOne(self: *Self) Allocator.Error!*T {
// This can never overflow because `self.items` can never occupy the whole address space
const newlen = self.items.len + 1;
try self.ensureTotalCapacity(newlen);
return self.addOneAssumeCapacity();
}
/// Increase length by 1, returning pointer to the new item.
/// The returned pointer may be invalidated by further operations to this list.
/// 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;
return &self.items[self.items.len - 1];
}
/// Resize the array, adding `n` new elements, which have `undefined` values.
/// The return value is an array pointing to the newly allocated elements.
/// The returned pointer may be invalidated by further operations to this list.
/// Resizes list if `self.capacity` is not large enough.
/// Invalidates element pointers if additional memory is needed.
pub fn addManyAsArray(self: *Self, comptime n: usize) Allocator.Error!*[n]T {
const prev_len = self.items.len;
try self.resize(try addOrOom(self.items.len, n));
return self.items[prev_len..][0..n];
}
/// Resize the array, adding `n` new elements, which have `undefined` values.
/// The return value is an array pointing to the newly allocated elements.
/// Never invalidates element pointers.
/// The returned pointer may be invalidated by further operations to this list.
/// 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;
self.items.len += n;
return self.items[prev_len..][0..n];
}
/// Resize the array, adding `n` new elements, which have `undefined` values.
/// The return value is a slice pointing to the newly allocated elements.
/// The returned pointer may be invalidated by further operations to this list.
/// Resizes list if `self.capacity` is not large enough.
/// Invalidates element pointers if additional memory is needed.
pub fn addManyAsSlice(self: *Self, n: usize) Allocator.Error![]T {
const prev_len = self.items.len;
try self.resize(try addOrOom(self.items.len, n));
return self.items[prev_len..][0..n];
}
/// Resize the array, adding `n` new elements, which have `undefined` values.
/// The return value is a slice pointing to the newly allocated elements.
/// Never invalidates element pointers.
/// The returned pointer may be invalidated by further operations to this list.
/// 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;
self.items.len += n;
return self.items[prev_len..][0..n];
}
/// Remove and return the last element from the list, or return `null` if list is empty.
/// Invalidates element pointers to the removed element.
pub fn pop(self: *Self) ?T {
if (self.items.len == 0) return null;
self.pointer_stability.assertUnlocked();
const val = self.items[self.items.len - 1];
self.items[self.items.len - 1] = undefined;
self.items.len -= 1;
return val;
}
/// Returns a slice of all the items plus the extra capacity, whose memory
/// contents are `undefined`.
/// The returned pointer may be invalidated by further operations to this list.
pub fn allocatedSlice(self: Self) Slice {
// `items.len` is the length, not the capacity.
return self.items.ptr[0..self.capacity];
}
/// Returns a slice of only the extra capacity after items.
/// This can be useful for writing directly into an ArrayList.
/// Note that such an operation must be followed up with a direct
/// modification of `self.items.len`.
/// The returned pointer may be invalidated by further operations to this list.
pub fn unusedCapacitySlice(self: Self) []T {
return self.allocatedSlice()[self.items.len..];
}
/// Deprecated
pub fn getLast(self: Self) T {
return self.items[self.items.len - 1];
}
/// Deprecated in favor of `last`
pub const getLastOrNull = last;
/// Returns the last element from the list, or `null` if the list is
/// empty.
/// Never invalidates element pointers.
pub fn last(self: Self) ?T {
if (self.items.len == 0) return null;
return self.items[self.items.len - 1];
}
/// Returns a pointer to the last element from the list, or `null` if
/// the list is empty.
/// The returned pointer may be invalidated by further operations to this list.
pub fn lastPtr(self: Self) ?*T {
if (self.items.len == 0) return null;
return &self.items[self.items.len - 1];
}
};
}
/// 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 Aligned(comptime T: type, comptime alignment: ?mem.Alignment) type {
if (alignment) |a| {
if (a.toByteUnits() == @alignOf(T)) {
return Aligned(T, null);
}
}
return struct {
const Self = @This();
/// Contents of the list. This field is intended to be accessed
/// directly.
///
/// Pointers to elements in this slice are invalidated by various
/// functions of this ArrayList in accordance with the respective
/// documentation.
/// An invalidated pointer may point either to valid or freed memory.
items: Slice,
/// How many T values this list can hold without allocating
/// additional memory.
capacity: usize,
/// Used to detect memory safety violations.
pointer_stability: debug.SafetyLock,
/// An ArrayList containing no elements.
pub const empty: Self = .{
.items = &.{},
.capacity = 0,
.pointer_stability = .{},
};
pub const Slice = if (alignment) |a| ([]align(a.toByteUnits()) T) else []T;
pub fn SentinelSlice(comptime s: T) type {
return if (alignment) |a| ([:s]align(a.toByteUnits()) T) else [:s]T;
}
/// Initialize with capacity to hold exactly `num` elements.
/// Deinitialize with `deinit` or `toOwnedSlice`.
pub fn initCapacity(gpa: Allocator, num: usize) Allocator.Error!Self {
var self: Self = .empty;
try self.ensureTotalCapacityPrecise(gpa, num);
return self;
}
/// Initialize with externally-managed memory. The buffer determines the
/// capacity, and the length is set to zero.
///
/// 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],
.capacity = buffer.len,
.pointer_stability = .{},
};
}
/// Release all allocated memory.
pub fn deinit(self: *Self, gpa: Allocator) void {
self.pointer_stability.assertUnlocked();
gpa.free(self.allocatedSlice());
self.* = undefined;
}
/// Puts the unmanaged array list into a state where any method call that would
/// cause an existing value pointer to become invalidated will
/// instead trigger an assertion.
///
/// `lockPointers` may be called multiple times. This allows multiple
/// independent users of the list to keep it locked simultaneously.
///
/// `unlockPointers` restores the list to its previous state when
/// called the same number of times as `lockPointers`.
pub fn lockPointers(self: *Self) void {
self.pointer_stability.lockShared();
}
/// Undoes one call to `lockPointers`.
pub fn unlockPointers(self: *Self) void {
self.pointer_stability.unlockShared();
}
/// Convert this list into an analogous memory-managed one.
/// The returned list has ownership of the underlying memory.
pub fn toManaged(self: *Self, gpa: Allocator) AlignedManaged(T, alignment) {
return .{
.items = self.items,
.capacity = self.capacity,
.allocator = gpa,
.pointer_stability = self.pointer_stability,
};
}
/// ArrayList takes ownership of the passed in slice.
/// Deinitialize with `deinit` or use `toOwnedSlice`.
pub fn fromOwnedSlice(slice: Slice) Self {
return Self{
.items = slice,
.capacity = slice.len,
.pointer_stability = .{},
};
}
/// ArrayList takes ownership of the passed in slice.
/// Deinitialize with `deinit` or use `toOwnedSlice`.
pub fn fromOwnedSliceSentinel(comptime sentinel: T, slice: [:sentinel]T) Self {
return Self{
.items = slice,
.capacity = slice.len + 1,
.pointer_stability = .{},
};
}
/// The caller owns the returned memory. Empties this ArrayList.
/// Its capacity is cleared, making deinit() safe but unnecessary to call.
/// May invalidate element pointers.
pub fn toOwnedSlice(self: *Self, gpa: Allocator) Allocator.Error!Slice {
const old_memory = self.allocatedSlice();
self.pointer_stability.assertUnlocked();
if (gpa.remap(old_memory, self.items.len)) |new_items| {
self.* = .empty;
return new_items;
}
const new_memory = try gpa.alignedAlloc(T, alignment, self.items.len);
@memcpy(new_memory, self.items);
self.clearAndFree(gpa);
return new_memory;
}
/// The caller owns the returned memory. ArrayList becomes empty.
/// May invalidate element pointers.
pub fn toOwnedSliceSentinel(self: *Self, gpa: Allocator, comptime sentinel: T) Allocator.Error!SentinelSlice(sentinel) {
self.pointer_stability.assertUnlocked();
// This addition can never overflow because `self.items` can never occupy the whole address space.
try self.ensureTotalCapacityPrecise(gpa, self.items.len + 1);
self.appendAssumeCapacity(sentinel);
errdefer self.items.len -= 1;
const result = try self.toOwnedSlice(gpa);
return result[0 .. result.len - 1 :sentinel];
}
/// The caller owns the returned memory. Empties this ArrayList.
/// Its capacity is cleared, making deinit() safe but unnecessary to call.
///
/// Asserts what the capacity is equal to the length.
/// Never invalidates element pointers.
///
/// See also:
/// * `shrinkToLen`
pub fn toOwnedSliceAssert(self: *Self) Slice {
assert(self.items.len == self.capacity);
const items = self.items;
self.* = .empty;
return items;
}
/// The caller owns the returned memory. ArrayList becomes empty.
/// Asserts what the capacity is equal to the length + 1.
/// Never invalidates element pointers.
pub fn toOwnedSliceSentinelAssert(self: *Self, comptime sentinel: T) SentinelSlice(sentinel) {
std.debug.assert(self.items.len + 1 == self.capacity);
self.appendAssumeCapacity(sentinel);
const result = self.toOwnedSliceAssert();
return result[0 .. result.len - 1 :sentinel];
}
/// Creates a copy of this ArrayList.
pub fn clone(self: Self, gpa: Allocator) Allocator.Error!Self {
var cloned = try Self.initCapacity(gpa, self.capacity);
cloned.appendSliceAssumeCapacity(self.items);
return cloned;
}
/// Insert `item` at index `index`. Moves `list[index .. list.len]` to higher indices to make room.
/// If `index` is equal to the length of the list this operation is equivalent to append.
/// This operation is O(N).
/// Invalidates element pointers if additional memory is needed.
/// Invalidates pre-existing pointers to elements at and after `index`.
/// Asserts that the index is in bounds or equal to the length.
pub fn insert(self: *Self, gpa: Allocator, index: usize, item: T) Allocator.Error!void {
self.pointer_stability.assertUnlocked();
const dst = try self.addManyAt(gpa, index, 1);
dst[0] = item;
}
/// Insert `item` at index `index`. Moves `list[index .. list.len]` to higher indices to make room.
/// If `index` is equal to the length of the list this operation is
/// equivalent to appendAssumeCapacity.
/// This operation is O(N).
/// Invalidates pre-existing pointers to elements at and after `index`.
/// 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, index: usize, item: T) void {
self.pointer_stability.assertUnlocked();
assert(self.items.len < self.capacity);
self.items.len += 1;
@memmove(self.items[index + 1 .. self.items.len], self.items[index .. self.items.len - 1]);
self.items[index] = item;
}
/// Insert `item` at index `index`. Moves `list[index .. list.len]` to higher indices to make room.
/// If `index` is equal to the length of the list this operation is
/// equivalent to appendAssumeCapacity.
/// This operation is O(N).
/// Invalidates pre-existing pointers to elements at and after `index`.
/// Asserts that the index is in bounds or equal to the length.
/// If the list lacks unused capacity for the additional item, returns
/// `error.OutOfMemory`.
pub fn insertBounded(self: *Self, i: usize, item: T) error{OutOfMemory}!void {
if (self.capacity - self.items.len == 0) return error.OutOfMemory;
return insertAssumeCapacity(self, i, item);
}
/// Add `count` new elements at position `index`, which have
/// `undefined` values. Returns a slice pointing to the newly allocated
/// elements, which becomes invalid after various `ArrayList`
/// operations.
/// Invalidates pre-existing pointers to elements at and after `index`.
/// Invalidates all pre-existing element pointers if capacity must be
/// increased to accommodate the new elements.
/// Asserts that the index is in bounds or equal to the length.
pub fn addManyAt(
self: *Self,
gpa: Allocator,
index: usize,
count: usize,
) Allocator.Error![]T {
const new_len = try addOrOom(self.items.len, count);
self.pointer_stability.assertUnlocked();
if (self.capacity >= new_len)
return addManyAtAssumeCapacity(self, index, count);
// Here we avoid copying allocated but unused bytes by
// attempting a resize in place, and falling back to allocating
// a new buffer and doing our own copy. With a realloc() call,
// the allocator implementation would pointlessly copy our
// extra capacity.
const new_capacity = Aligned(T, alignment).growCapacity(new_len);
const old_memory = self.allocatedSlice();
if (gpa.remap(old_memory, new_capacity)) |new_memory| {
self.items.ptr = new_memory.ptr;
self.capacity = new_memory.len;
return addManyAtAssumeCapacity(self, index, count);
}
// Make a new allocation, avoiding `ensureTotalCapacity` in order
// to avoid extra memory copies.
const new_memory = try gpa.alignedAlloc(T, alignment, new_capacity);
const to_move = self.items[index..];
@memcpy(new_memory[0..index], self.items[0..index]);
@memcpy(new_memory[index + count ..][0..to_move.len], to_move);
gpa.free(old_memory);
self.items = new_memory[0..new_len];
self.capacity = new_memory.len;
// The inserted elements at `new_memory[index..][0..count]` have
// already been set to `undefined` by memory allocation.
return new_memory[index..][0..count];
}
/// Add `count` new elements at position `index`, which have
/// `undefined` values. Returns a slice pointing to the newly allocated
/// elements, which becomes invalid after various `ArrayList`
/// operations.
/// Invalidates pre-existing pointers to elements at and after `index`.
/// 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 {
self.pointer_stability.assertUnlocked();
const new_len = self.items.len + count;
assert(self.capacity >= new_len);
const to_move = self.items[index..];
self.items.len = new_len;
@memmove(self.items[index + count ..][0..to_move.len], to_move);
const result = self.items[index..][0..count];
@memset(result, undefined);
return result;
}
/// Add `count` new elements at position `index`, which have
/// `undefined` values, returning a slice pointing to the newly
/// allocated elements, which becomes invalid after various `ArrayList`
/// operations.
/// Invalidates pre-existing pointers to elements at and after `index`.
/// If the list lacks unused capacity for the additional items, returns
/// `error.OutOfMemory`.
/// Asserts that the index is in bounds or equal to the length.
pub fn addManyAtBounded(self: *Self, index: usize, count: usize) error{OutOfMemory}![]T {
if (self.capacity - self.items.len < count) return error.OutOfMemory;
return addManyAtAssumeCapacity(self, index, count);
}
/// Insert slice `items` at index `index` by moving `list[index .. list.len]` to make room.
/// This operation is O(N).
/// Invalidates pre-existing pointers to elements at and after `index`.
/// Invalidates all pre-existing element pointers if capacity must be
/// increased to accommodate the new elements.
/// Asserts that the index is in bounds or equal to the length.
pub fn insertSlice(
self: *Self,
gpa: Allocator,
index: usize,
items: []const T,
) Allocator.Error!void {
const dst = try self.addManyAt(
gpa,
index,
items.len,
);
@memcpy(dst, items);
}
/// Insert slice `items` at index `index` by moving `list[index .. list.len]` to make room.
/// This operation is O(N).
/// Invalidates pre-existing pointers to elements at and after `index`.
/// Asserts that the list has capacity for the additional items.
/// Asserts that the index is in bounds or equal to the length.
pub fn insertSliceAssumeCapacity(
self: *Self,
index: usize,
items: []const T,
) void {
const dst = self.addManyAtAssumeCapacity(index, items.len);
@memcpy(dst, items);
}
/// Insert slice `items` at index `index` by moving `list[index .. list.len]` to make room.
/// This operation is O(N).
/// Invalidates pre-existing pointers to elements at and after `index`.
/// If the list lacks unused capacity for the additional items, returns
/// `error.OutOfMemory`.
/// Asserts that the index is in bounds or equal to the length.
pub fn insertSliceBounded(
self: *Self,
index: usize,
items: []const T,
) error{OutOfMemory}!void {
const dst = try self.addManyAtBounded(index, items.len);
@memcpy(dst, items);
}
/// Grows or shrinks the list as necessary.
/// Invalidates element pointers if additional capacity is allocated,
/// Invalidates pointers to elements at and above index `start + len`
/// when `len` and `new_items.len` are unequal.
/// Asserts that the range is in bounds.
pub fn replaceRange(
self: *Self,
gpa: Allocator,
start: usize,
len: usize,
new_items: []const T,
) Allocator.Error!void {
try self.ensureTotalCapacity(gpa, try addOrOom(self.items.len - len, new_items.len));
self.replaceRangeAssumeCapacity(start, len, new_items);
}
/// Grows or shrinks the list as necessary.
/// Invalidates pointers to elements at and above index `start + len`
/// when `len` and `new_items.len` are unequal.
/// Asserts the capacity is enough for additional items.
pub fn replaceRangeAssumeCapacity(
self: *Self,
start: usize,
len: usize,
new_items: []const T,
) void {
std.debug.assert(self.capacity - self.items.len >= new_items.len -| len);
self.pointer_stability.assertUnlocked();
const tail = self.items[start + len ..];
const vacated = self.items[self.items.len - (len -| new_items.len) ..];
self.items.len = self.items.len - len + new_items.len;
@memmove(self.items[start + new_items.len ..], tail);
@memcpy(self.items[start..][0..new_items.len], new_items);
@memset(vacated, undefined);
}
/// Invalidates pointers to elements at and above index `start + len`
/// when `len` and `new_items.len` are unequal.
/// If the unused capacity is insufficient for additional items,
/// returns `error.OutOfMemory`.
pub fn replaceRangeBounded(
self: *Self,
start: usize,
len: usize,
new_items: []const T,
) error{OutOfMemory}!void {
if (self.capacity - self.items.len < new_items.len -| len) return error.OutOfMemory;
return replaceRangeAssumeCapacity(self, start, len, new_items);
}
/// Extend the list by 1 element. Allocates more memory as necessary.
/// Invalidates element pointers if additional memory is needed.
pub fn append(self: *Self, gpa: Allocator, item: T) Allocator.Error!void {
const new_item_ptr = try self.addOne(gpa);
new_item_ptr.* = item;
}
/// Extend 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 {
self.addOneAssumeCapacity().* = item;
}
/// Extend the list by 1 element.
///
/// Never invalidates element pointers.
///
/// If the list lacks unused capacity for the additional item, returns
/// `error.OutOfMemory`.
pub fn appendBounded(self: *Self, item: T) error{OutOfMemory}!void {
if (self.capacity - self.items.len == 0) return error.OutOfMemory;
return appendAssumeCapacity(self, item);
}
/// 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 the index is in bounds.
pub fn orderedRemove(self: *Self, i: usize) T {
const old_item = self.items[i];
self.replaceRangeAssumeCapacity(i, 1, &.{});
return old_item;
}
/// Remove the elements indexed by `sorted_indexes`. The indexes to be
/// removed correspond to the array list before deletion.
///
/// Asserts:
/// * Each index to be removed is in bounds.
/// * The indexes to be removed are sorted ascending.
///
/// Duplicates in `sorted_indexes` are allowed.
///
/// This operation is O(N).
///
/// Invalidates element pointers beyond the first deleted index.
pub fn orderedRemoveMany(self: *Self, sorted_indexes: []const usize) void {
self.pointer_stability.assertUnlocked();
if (sorted_indexes.len == 0) return;
var shift: usize = 1;
for (sorted_indexes[0 .. sorted_indexes.len - 1], sorted_indexes[1..]) |removed, end| {
if (removed == end) continue; // allows duplicates in `sorted_indexes`
const start = removed + 1;
const len = end - start; // safety checks `sorted_indexes` are sorted
@memmove(self.items[start - shift ..][0..len], self.items[start..][0..len]); // safety checks initial `sorted_indexes` are in range
shift += 1;
}
const start = sorted_indexes[sorted_indexes.len - 1] + 1;
const end = self.items.len;
const len = end - start; // safety checks final `sorted_indexes` are in range
@memmove(self.items[start - shift ..][0..len], self.items[start..][0..len]);
self.items.len = end - shift;
}
/// Removes the element at the specified index and returns it.
/// The empty slot is filled from the end of the list.
/// Invalidates pointers to last element.
/// This operation is O(1).
/// Asserts that the index is in bounds.
pub fn swapRemove(self: *Self, i: usize) T {
self.pointer_stability.assertUnlocked();
const val = self.items[i];
self.items[i] = self.items[self.items.len - 1];
self.items[self.items.len - 1] = undefined;
self.items.len -= 1;
return val;
}
/// Append the slice of items to the list. Allocates more
/// memory as necessary.
/// Invalidates element pointers if additional memory is needed.
pub fn appendSlice(self: *Self, gpa: Allocator, items: []const T) Allocator.Error!void {
try self.ensureUnusedCapacity(gpa, items.len);
self.appendSliceAssumeCapacity(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;
assert(new_len <= self.capacity);
self.items.len = new_len;
@memcpy(self.items[old_len..][0..items.len], items);
}
/// Append the slice of items to the list.
/// Never invalidates element pointers.
/// If the list lacks unused capacity for the additional items, returns `error.OutOfMemory`.
pub fn appendSliceBounded(self: *Self, items: []const T) error{OutOfMemory}!void {
if (self.capacity - self.items.len < items.len) return error.OutOfMemory;
return appendSliceAssumeCapacity(self, items);
}
/// 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 element pointers if additional memory is needed.
pub fn appendUnalignedSlice(self: *Self, gpa: Allocator, items: []align(1) const T) Allocator.Error!void {
try self.ensureUnusedCapacity(gpa, items.len);
self.appendUnalignedSliceAssumeCapacity(items);
}
/// Append an unaligned slice of items to the list.
///
/// Intended to be used only when `appendSliceAssumeCapacity` would be
/// a compile error.
/// Never invalidates element pointers.
/// 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;
assert(new_len <= self.capacity);
self.items.len = new_len;
@memcpy(self.items[old_len..][0..items.len], items);
}
/// Append an unaligned slice of items to the list.
///
/// Intended to be used only when `appendSliceAssumeCapacity` would be
/// a compile error.
/// Never invalidates element pointers.
/// If the list lacks unused capacity for the additional items, returns
/// `error.OutOfMemory`.
pub fn appendUnalignedSliceBounded(self: *Self, items: []align(1) const T) error{OutOfMemory}!void {
if (self.capacity - self.items.len < items.len) return error.OutOfMemory;
return appendUnalignedSliceAssumeCapacity(self, items);
}
/// Prints a formatted string into this list.
/// Invalidates element pointers if additional memory is needed.
pub fn print(self: *Self, gpa: Allocator, comptime fmt: []const u8, args: anytype) error{OutOfMemory}!void {
comptime assert(T == u8);
try self.ensureUnusedCapacity(gpa, fmt.len);
var aw: std.Io.Writer.Allocating = .fromArrayList(gpa, self);
defer self.* = aw.toArrayList();
return aw.writer.print(fmt, args) catch |err| switch (err) {
error.WriteFailed => return error.OutOfMemory,
};
}
/// Prints a formatted string into this list.
/// Asserts that there is enough capacity for the write.
/// Never invalidates element pointers.
pub fn printAssumeCapacity(self: *Self, comptime fmt: []const u8, args: anytype) void {
comptime assert(T == u8);
var w: std.Io.Writer = .fixed(self.unusedCapacitySlice());
w.print(fmt, args) catch unreachable;
self.items.len += w.end;
}
/// Prints a formatted string into this list.
/// Returns error.OutOfMemory if additional capacity is needed for the write.
/// Never invalidates element pointers.
pub fn printBounded(self: *Self, comptime fmt: []const u8, args: anytype) error{OutOfMemory}!void {
comptime assert(T == u8);
var w: std.Io.Writer = .fixed(self.unusedCapacitySlice());
w.print(fmt, args) catch return error.OutOfMemory;
self.items.len += w.end;
}
/// Append a value to the list `n` times.
/// Allocates more memory as necessary.
/// 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, gpa: Allocator, value: T, n: usize) Allocator.Error!void {
const old_len = self.items.len;
try self.resize(gpa, try addOrOom(old_len, n));
@memset(self.items[old_len..self.items.len], value);
}
/// Append a value to the list `n` times.
///
/// 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 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);
@memset(self.items.ptr[self.items.len..new_len], value);
self.items.len = new_len;
}
/// Append a value to the list `n` times.
///
/// 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.
///
/// If the list lacks unused capacity for the additional items, returns
/// `error.OutOfMemory`.
pub inline fn appendNTimesBounded(self: *Self, value: T, n: usize) error{OutOfMemory}!void {
const new_len = self.items.len + n;
if (self.capacity < new_len) return error.OutOfMemory;
@memset(self.items.ptr[self.items.len..new_len], value);
self.items.len = new_len;
}
/// 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, gpa: Allocator, new_len: usize) Allocator.Error!void {
try self.ensureTotalCapacity(gpa, new_len);
self.items.len = new_len;
}
/// Reduce allocated capacity to `new_len`.
/// May invalidate element pointers.
/// Asserts that the new length is less than or equal to the previous length.
pub fn shrinkAndFree(self: *Self, gpa: Allocator, new_len: usize) void {
self.shrinkAndFreePrecise(gpa, new_len) catch |e| switch (e) {
error.OutOfMemory => {
// No problem, capacity is still correct then.
self.items.len = new_len;
return;
},
};
}
/// Reduce allocated capacity to `new_len`.
/// May invalidate element pointers.
/// Asserts that the new length is less than or equal to the previous length.
/// If succeds capacity is guaranteed to be equal to the length.
pub fn shrinkAndFreePrecise(self: *Self, gpa: Allocator, new_len: usize) Allocator.Error!void {
self.pointer_stability.assertUnlocked();
assert(new_len <= self.items.len);
if (@sizeOf(T) == 0) {
self.items.len = new_len;
return;
}
const old_memory = self.allocatedSlice();
if (gpa.remap(old_memory, new_len)) |new_items| {
self.capacity = new_items.len;
self.items = new_items;
return;
}
const new_memory = try gpa.alignedAlloc(T, alignment, new_len);
@memcpy(new_memory, self.items[0..new_len]);
gpa.free(old_memory);
self.items = new_memory;
self.capacity = new_memory.len;
}
/// Shrinks capacity to match length.
/// May invalidate element pointers.
/// If succeds it is safe to call `toOwnedSliceAssert`.
pub fn shrinkToLen(self: *Self, gpa: Allocator) Allocator.Error!void {
try self.shrinkAndFreePrecise(gpa, self.items.len);
}
/// Shrinks or expands capacity to match length + 1.
/// May invalidate element pointers.
/// If succeds it is safe to call `toOwnedSliceSentinelAssert`.
pub fn shrinkToLenSentinel(self: *Self, gpa: Allocator) Allocator.Error!void {
std.debug.assert(self.items.len <= self.capacity);
const required_len = self.items.len + 1;
switch (std.math.order(required_len, self.capacity)) {
.eq => return,
.gt => {
try self.ensureTotalCapacityPrecise(gpa, required_len);
},
.lt => {
self.items.len += 1;
defer self.items.len -= 1;
try self.shrinkToLen(gpa);
},
}
}
/// Reduce length to `new_len`.
/// Invalidates pointers to elements `items[new_len..]`.
/// Keeps capacity the same.
/// Asserts that the new length is less than or equal to the previous length.
pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
self.pointer_stability.assertUnlocked();
assert(new_len <= self.items.len);
@memset(self.items[new_len..], undefined);
self.items.len = new_len;
}
/// Reduce length to 0.
/// Invalidates all element pointers.
pub fn clearRetainingCapacity(self: *Self) void {
self.pointer_stability.assertUnlocked();
@memset(self.items, undefined);
self.items.len = 0;
}
/// Invalidates all element pointers.
pub fn clearAndFree(self: *Self, gpa: Allocator) void {
self.pointer_stability.assertUnlocked();
gpa.free(self.allocatedSlice());
self.items.len = 0;
self.capacity = 0;
}
/// Modify the array so that it can hold at least `new_capacity` items.
/// Implements super-linear growth to achieve amortized O(1) append operations.
/// Invalidates element pointers if additional memory is needed.
pub fn ensureTotalCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
if (self.capacity >= new_capacity) return;
return self.ensureTotalCapacityPrecise(gpa, growCapacity(new_capacity));
}
/// 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 element pointers if additional memory is needed.
pub fn ensureTotalCapacityPrecise(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
self.pointer_stability.assertUnlocked();
if (@sizeOf(T) == 0) {
self.capacity = math.maxInt(usize);
return;
}
if (self.capacity >= new_capacity) return;
// Here we avoid copying allocated but unused bytes by
// attempting a resize in place, and falling back to allocating
// a new buffer and doing our own copy. With a realloc() call,
// the allocator implementation would pointlessly copy our
// extra capacity.
const old_memory = self.allocatedSlice();
if (gpa.remap(old_memory, new_capacity)) |new_memory| {
self.items.ptr = new_memory.ptr;
self.capacity = new_memory.len;
} else {
const new_memory = try gpa.alignedAlloc(T, alignment, new_capacity);
@memcpy(new_memory[0..self.items.len], self.items);
gpa.free(old_memory);
self.items.ptr = new_memory.ptr;
self.capacity = new_memory.len;
}
}
/// Modify the array so that it can hold at least `additional_count` **more** items.
/// Invalidates element pointers if additional memory is needed.
pub fn ensureUnusedCapacity(
self: *Self,
gpa: Allocator,
additional_count: usize,
) Allocator.Error!void {
return self.ensureTotalCapacity(gpa, 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.
/// 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.
/// Invalidates element pointers if additional memory is needed.
/// The returned pointer may be invalidated by further operations to this list.
pub fn addOne(self: *Self, gpa: Allocator) Allocator.Error!*T {
// This can never overflow because `self.items` can never occupy the whole address space
const newlen = self.items.len + 1;
try self.ensureTotalCapacity(gpa, newlen);
return self.addOneAssumeCapacity();
}
/// Increase length by 1, returning pointer to the new item.
/// Never invalidates element pointers.
/// The returned pointer may be invalidated by further operations to this list.
/// 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;
return &self.items[self.items.len - 1];
}
/// Increase length by 1, returning pointer to the new item.
/// Never invalidates element pointers.
/// The returned pointer may be invalidated by further operations to this list.
/// If the list lacks unused capacity for the additional item, returns `error.OutOfMemory`.
pub fn addOneBounded(self: *Self) error{OutOfMemory}!*T {
if (self.capacity - self.items.len < 1) return error.OutOfMemory;
return addOneAssumeCapacity(self);
}
/// Resize the array, adding `n` new elements, which have `undefined` values.
/// Invalidates element pointers if additional memory is required.
/// The return value is an array pointing to the newly allocated elements.
/// The returned pointer may be invalidated by further operations to this list.
pub fn addManyAsArray(self: *Self, gpa: Allocator, comptime n: usize) Allocator.Error!*[n]T {
const prev_len = self.items.len;
try self.resize(gpa, try addOrOom(self.items.len, n));
return self.items[prev_len..][0..n];
}
/// Resize the array, adding `n` new elements, which have `undefined` values.
/// The return value is an array pointing to the newly allocated elements.
/// Never invalidates element pointers.
/// The returned pointer may be invalidated by further operations to this list.
/// 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;
self.items.len += n;
return self.items[prev_len..][0..n];
}
/// Resize the array, adding `n` new elements, which have `undefined` values.
/// The return value is an array pointing to the newly allocated elements.
/// Never invalidates element pointers.
/// The returned pointer may be invalidated by further operations to this list.
/// If the list lacks unused capacity for the additional items, returns
/// `error.OutOfMemory`.
pub fn addManyAsArrayBounded(self: *Self, comptime n: usize) error{OutOfMemory}!*[n]T {
if (self.capacity - self.items.len < n) return error.OutOfMemory;
return addManyAsArrayAssumeCapacity(self, n);
}
/// Resize the array, adding `n` new elements, which have `undefined` values.
/// The return value is a slice pointing to the newly allocated elements.
/// The returned pointer may be invalidated by further operations to this list.
/// Resizes list if `self.capacity` is not large enough.
pub fn addManyAsSlice(self: *Self, gpa: Allocator, n: usize) Allocator.Error![]T {
const prev_len = self.items.len;
try self.resize(gpa, try addOrOom(self.items.len, n));
return self.items[prev_len..][0..n];
}
/// Resizes the array, adding `n` new elements, which have `undefined`
/// values, returning a slice pointing to the newly allocated elements.
/// Never invalidates element pointers.
/// The returned pointer may be invalidated by further operations to this list.
/// 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;
self.items.len += n;
return self.items[prev_len..][0..n];
}
/// Resizes the array, adding `n` new elements, which have `undefined`
/// values, returning a slice pointing to the newly allocated elements.
/// Never invalidates element pointers.
/// The returned pointer may be invalidated by further operations to this list.
/// If the list lacks unused capacity for the additional items, returns
/// `error.OutOfMemory`.
pub fn addManyAsSliceBounded(self: *Self, n: usize) error{OutOfMemory}![]T {
if (self.capacity - self.items.len < n) return error.OutOfMemory;
return addManyAsSliceAssumeCapacity(self, n);
}
/// Remove and return the last element from the list.
/// If the list is empty, returns `null`.
/// Invalidates pointers to last element.
pub fn pop(self: *Self) ?T {
if (self.items.len == 0) return null;
self.pointer_stability.assertUnlocked();
const val = self.items[self.items.len - 1];
self.items[self.items.len - 1] = undefined;
self.items.len -= 1;
return val;
}
/// Returns a slice of all the items plus the extra capacity, whose memory
/// contents are `undefined`.
/// The returned pointer may be invalidated by further operations to this list.
pub fn allocatedSlice(self: Self) Slice {
return self.items.ptr[0..self.capacity];
}
/// Returns a slice of only the extra capacity after items.
/// This can be useful for writing directly into an ArrayList.
/// Note that such an operation must be followed up with a direct
/// modification of `self.items.len`.
/// The returned pointer may be invalidated by further operations to this list.
pub fn unusedCapacitySlice(self: Self) []T {
return self.allocatedSlice()[self.items.len..];
}
/// Deprecated
pub fn getLast(self: Self) T {
return self.items[self.items.len - 1];
}
/// Deprecated in favor of `last`
pub const getLastOrNull = last;
/// Returns the last element from the list, or `null` if the list is
/// empty.
pub fn last(self: Self) ?T {
if (self.items.len == 0) return null;
return self.items[self.items.len - 1];
}
/// Returns a pointer to the last element from the list, or `null` if
/// the list is empty.
/// The returned pointer may be invalidated by further operations to this list.
pub fn lastPtr(self: Self) ?*T {
if (self.items.len == 0) return null;
return &self.items[self.items.len - 1];
}
/// Called when memory growth is necessary. Returns a capacity larger than
/// minimum that grows super-linearly.
pub fn growCapacity(minimum: usize) usize {
if (@sizeOf(T) == 0) return math.maxInt(usize);
const init_capacity: comptime_int = @max(1, std.atomic.cache_line / @sizeOf(T));
return minimum +| (minimum / 2 + init_capacity);
}
};
}
/// Integer addition returning `error.OutOfMemory` on overflow.
fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize {
const result, const overflow = @addWithOverflow(a, b);
if (overflow != 0) return error.OutOfMemory;
return result;
}
test "init" {
{
var list = Managed(i32).init(testing.allocator);
defer list.deinit();
try testing.expect(list.items.len == 0);
try testing.expect(list.capacity == 0);
}
{
const list: ArrayList(i32) = .empty;
try testing.expect(list.items.len == 0);
try testing.expect(list.capacity == 0);
}
}
test "initCapacity" {
const a = testing.allocator;
{
var list = try Managed(i8).initCapacity(a, 200);
defer list.deinit();
try testing.expect(list.items.len == 0);
try testing.expect(list.capacity >= 200);
}
{
var list = try ArrayList(i8).initCapacity(a, 200);
defer list.deinit(a);
try testing.expect(list.items.len == 0);
try testing.expect(list.capacity >= 200);
}
}
test "clone" {
const a = testing.allocator;
{
var array = Managed(i32).init(a);
try array.append(-1);
try array.append(3);
try array.append(5);
const cloned = try array.clone();
defer cloned.deinit();
try testing.expectEqualSlices(i32, array.items, cloned.items);
try testing.expectEqual(array.allocator, cloned.allocator);
try testing.expect(cloned.capacity >= array.capacity);
array.deinit();
try testing.expectEqual(@as(i32, -1), cloned.items[0]);
try testing.expectEqual(@as(i32, 3), cloned.items[1]);
try testing.expectEqual(@as(i32, 5), cloned.items[2]);
}
{
var array: ArrayList(i32) = .empty;
try array.append(a, -1);
try array.append(a, 3);
try array.append(a, 5);
var cloned = try array.clone(a);
defer cloned.deinit(a);
try testing.expectEqualSlices(i32, array.items, cloned.items);
try testing.expect(cloned.capacity >= array.capacity);
array.deinit(a);
try testing.expectEqual(@as(i32, -1), cloned.items[0]);
try testing.expectEqual(@as(i32, 3), cloned.items[1]);
try testing.expectEqual(@as(i32, 5), cloned.items[2]);
}
}
test "basic" {
const a = testing.allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
{
var i: usize = 0;
while (i < 10) : (i += 1) {
list.append(@as(i32, @intCast(i + 1))) catch unreachable;
}
}
{
var i: usize = 0;
while (i < 10) : (i += 1) {
try testing.expect(list.items[i] == @as(i32, @intCast(i + 1)));
}
}
for (list.items, 0..) |v, i| {
try testing.expect(v == @as(i32, @intCast(i + 1)));
}
try testing.expect(list.pop() == 10);
try testing.expect(list.items.len == 9);
list.appendSlice(&[_]i32{ 1, 2, 3 }) catch unreachable;
try testing.expect(list.items.len == 12);
try testing.expect(list.pop() == 3);
try testing.expect(list.pop() == 2);
try testing.expect(list.pop() == 1);
try testing.expect(list.items.len == 9);
var unaligned: [3]i32 align(1) = [_]i32{ 4, 5, 6 };
list.appendUnalignedSlice(&unaligned) catch unreachable;
try testing.expect(list.items.len == 12);
try testing.expect(list.pop() == 6);
try testing.expect(list.pop() == 5);
try testing.expect(list.pop() == 4);
try testing.expect(list.items.len == 9);
list.appendSlice(&[_]i32{}) catch unreachable;
try testing.expect(list.items.len == 9);
// can only set on indices < self.items.len
list.items[7] = 33;
list.items[8] = 42;
try testing.expect(list.pop() == 42);
try testing.expect(list.pop() == 33);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
{
var i: usize = 0;
while (i < 10) : (i += 1) {
list.append(a, @as(i32, @intCast(i + 1))) catch unreachable;
}
}
{
var i: usize = 0;
while (i < 10) : (i += 1) {
try testing.expect(list.items[i] == @as(i32, @intCast(i + 1)));
}
}
for (list.items, 0..) |v, i| {
try testing.expect(v == @as(i32, @intCast(i + 1)));
}
try testing.expect(list.pop() == 10);
try testing.expect(list.items.len == 9);
list.appendSlice(a, &[_]i32{ 1, 2, 3 }) catch unreachable;
try testing.expect(list.items.len == 12);
try testing.expect(list.pop() == 3);
try testing.expect(list.pop() == 2);
try testing.expect(list.pop() == 1);
try testing.expect(list.items.len == 9);
var unaligned: [3]i32 align(1) = [_]i32{ 4, 5, 6 };
list.appendUnalignedSlice(a, &unaligned) catch unreachable;
try testing.expect(list.items.len == 12);
try testing.expect(list.pop() == 6);
try testing.expect(list.pop() == 5);
try testing.expect(list.pop() == 4);
try testing.expect(list.items.len == 9);
list.appendSlice(a, &[_]i32{}) catch unreachable;
try testing.expect(list.items.len == 9);
// can only set on indices < self.items.len
list.items[7] = 33;
list.items[8] = 42;
try testing.expect(list.pop() == 42);
try testing.expect(list.pop() == 33);
}
}
test "appendNTimes" {
const a = testing.allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendNTimes(2, 10);
try testing.expectEqual(@as(usize, 10), list.items.len);
for (list.items) |element| {
try testing.expectEqual(@as(i32, 2), element);
}
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendNTimes(a, 2, 10);
try testing.expectEqual(@as(usize, 10), list.items.len);
for (list.items) |element| {
try testing.expectEqual(@as(i32, 2), element);
}
}
}
test "appendNTimes with failing allocator" {
const a = testing.failing_allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
try testing.expectError(error.OutOfMemory, list.appendNTimes(2, 10));
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try testing.expectError(error.OutOfMemory, list.appendNTimes(a, 2, 10));
}
}
test "orderedRemove" {
const a = testing.allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.append(1);
try list.append(2);
try list.append(3);
try list.append(4);
try list.append(5);
try list.append(6);
try list.append(7);
//remove from middle
try testing.expectEqual(@as(i32, 4), list.orderedRemove(3));
try testing.expectEqual(@as(i32, 5), list.items[3]);
try testing.expectEqual(@as(usize, 6), list.items.len);
//remove from end
try testing.expectEqual(@as(i32, 7), list.orderedRemove(5));
try testing.expectEqual(@as(usize, 5), list.items.len);
//remove from front
try testing.expectEqual(@as(i32, 1), list.orderedRemove(0));
try testing.expectEqual(@as(i32, 2), list.items[0]);
try testing.expectEqual(@as(usize, 4), list.items.len);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.append(a, 1);
try list.append(a, 2);
try list.append(a, 3);
try list.append(a, 4);
try list.append(a, 5);
try list.append(a, 6);
try list.append(a, 7);
//remove from middle
try testing.expectEqual(@as(i32, 4), list.orderedRemove(3));
try testing.expectEqual(@as(i32, 5), list.items[3]);
try testing.expectEqual(@as(usize, 6), list.items.len);
//remove from end
try testing.expectEqual(@as(i32, 7), list.orderedRemove(5));
try testing.expectEqual(@as(usize, 5), list.items.len);
//remove from front
try testing.expectEqual(@as(i32, 1), list.orderedRemove(0));
try testing.expectEqual(@as(i32, 2), list.items[0]);
try testing.expectEqual(@as(usize, 4), list.items.len);
}
{
// remove last item
var list = Managed(i32).init(a);
defer list.deinit();
try list.append(1);
try testing.expectEqual(@as(i32, 1), list.orderedRemove(0));
try testing.expectEqual(@as(usize, 0), list.items.len);
}
{
// remove last item
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.append(a, 1);
try testing.expectEqual(@as(i32, 1), list.orderedRemove(0));
try testing.expectEqual(@as(usize, 0), list.items.len);
}
}
test "swapRemove" {
const a = testing.allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.append(1);
try list.append(2);
try list.append(3);
try list.append(4);
try list.append(5);
try list.append(6);
try list.append(7);
//remove from middle
try testing.expect(list.swapRemove(3) == 4);
try testing.expect(list.items[3] == 7);
try testing.expect(list.items.len == 6);
//remove from end
try testing.expect(list.swapRemove(5) == 6);
try testing.expect(list.items.len == 5);
//remove from front
try testing.expect(list.swapRemove(0) == 1);
try testing.expect(list.items[0] == 5);
try testing.expect(list.items.len == 4);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.append(a, 1);
try list.append(a, 2);
try list.append(a, 3);
try list.append(a, 4);
try list.append(a, 5);
try list.append(a, 6);
try list.append(a, 7);
//remove from middle
try testing.expect(list.swapRemove(3) == 4);
try testing.expect(list.items[3] == 7);
try testing.expect(list.items.len == 6);
//remove from end
try testing.expect(list.swapRemove(5) == 6);
try testing.expect(list.items.len == 5);
//remove from front
try testing.expect(list.swapRemove(0) == 1);
try testing.expect(list.items[0] == 5);
try testing.expect(list.items.len == 4);
}
}
test "insert" {
const a = testing.allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.insert(0, 1);
try list.append(2);
try list.insert(2, 3);
try list.insert(0, 5);
try testing.expect(list.items[0] == 5);
try testing.expect(list.items[1] == 1);
try testing.expect(list.items[2] == 2);
try testing.expect(list.items[3] == 3);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.insert(a, 0, 1);
try list.append(a, 2);
try list.insert(a, 2, 3);
try list.insert(a, 0, 5);
try testing.expect(list.items[0] == 5);
try testing.expect(list.items[1] == 1);
try testing.expect(list.items[2] == 2);
try testing.expect(list.items[3] == 3);
}
{
var list: ArrayList(struct {}) = .empty;
defer list.deinit(a);
try list.insert(a, 0, .{});
try list.append(a, .{});
try testing.expect(list.items.len == 2);
}
}
test "insertSlice" {
const a = testing.allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.append(1);
try list.append(2);
try list.append(3);
try list.append(4);
try list.insertSlice(1, &[_]i32{ 9, 8 });
try testing.expect(list.items[0] == 1);
try testing.expect(list.items[1] == 9);
try testing.expect(list.items[2] == 8);
try testing.expect(list.items[3] == 2);
try testing.expect(list.items[4] == 3);
try testing.expect(list.items[5] == 4);
const items = [_]i32{1};
try list.insertSlice(0, items[0..0]);
try testing.expect(list.items.len == 6);
try testing.expect(list.items[0] == 1);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.append(a, 1);
try list.append(a, 2);
try list.append(a, 3);
try list.append(a, 4);
try list.insertSlice(a, 1, &[_]i32{ 9, 8 });
try testing.expect(list.items[0] == 1);
try testing.expect(list.items[1] == 9);
try testing.expect(list.items[2] == 8);
try testing.expect(list.items[3] == 2);
try testing.expect(list.items[4] == 3);
try testing.expect(list.items[5] == 4);
const items = [_]i32{1};
try list.insertSlice(a, 0, items[0..0]);
try testing.expect(list.items.len == 6);
try testing.expect(list.items[0] == 1);
}
}
test "Managed.replaceRange" {
const a = testing.allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(1, 0, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 2, 3, 4, 5 }, list.items);
}
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(1, 1, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(
i32,
&[_]i32{ 1, 0, 0, 0, 3, 4, 5 },
list.items,
);
}
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(1, 2, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 4, 5 }, list.items);
}
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(1, 3, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 5 }, list.items);
}
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(1, 4, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0 }, list.items);
}
}
test "Managed.replaceRangeAssumeCapacity" {
const a = testing.allocator;
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 0, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 2, 3, 4, 5 }, list.items);
}
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 1, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(
i32,
&[_]i32{ 1, 0, 0, 0, 3, 4, 5 },
list.items,
);
}
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 2, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 4, 5 }, list.items);
}
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 3, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 5 }, list.items);
}
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendSlice(&[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 4, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0 }, list.items);
}
}
test "ArrayList.replaceRange" {
const a = testing.allocator;
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(a, 1, 0, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 2, 3, 4, 5 }, list.items);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(a, 1, 1, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(
i32,
&[_]i32{ 1, 0, 0, 0, 3, 4, 5 },
list.items,
);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(a, 1, 2, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 4, 5 }, list.items);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(a, 1, 3, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 5 }, list.items);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
try list.replaceRange(a, 1, 4, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0 }, list.items);
}
}
test "ArrayList.replaceRangeAssumeCapacity" {
const a = testing.allocator;
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 0, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 2, 3, 4, 5 }, list.items);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 1, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(
i32,
&[_]i32{ 1, 0, 0, 0, 3, 4, 5 },
list.items,
);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 2, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 4, 5 }, list.items);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 3, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0, 5 }, list.items);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.appendSlice(a, &[_]i32{ 1, 2, 3, 4, 5 });
list.replaceRangeAssumeCapacity(1, 4, &[_]i32{ 0, 0, 0 });
try testing.expectEqualSlices(i32, &[_]i32{ 1, 0, 0, 0 }, list.items);
}
}
const Item = struct {
integer: i32,
sub_items: Managed(Item),
};
const ItemUnmanaged = struct {
integer: i32,
sub_items: ArrayList(ItemUnmanaged),
};
test "Managed(T) of struct T" {
const a = std.testing.allocator;
{
var root = Item{ .integer = 1, .sub_items = .init(a) };
defer root.sub_items.deinit();
try root.sub_items.append(Item{ .integer = 42, .sub_items = .init(a) });
try testing.expect(root.sub_items.items[0].integer == 42);
}
{
var root = ItemUnmanaged{ .integer = 1, .sub_items = .empty };
defer root.sub_items.deinit(a);
try root.sub_items.append(a, ItemUnmanaged{ .integer = 42, .sub_items = .empty });
try testing.expect(root.sub_items.items[0].integer == 42);
}
}
test "shrink still sets length when resizing is disabled" {
var failing_allocator = testing.FailingAllocator.init(testing.allocator, .{ .resize_fail_index = 0 });
const a = failing_allocator.allocator();
{
var list = Managed(i32).init(a);
defer list.deinit();
try list.append(1);
try list.append(2);
try list.append(3);
list.shrinkAndFree(1);
try testing.expect(list.items.len == 1);
}
{
var list: ArrayList(i32) = .empty;
defer list.deinit(a);
try list.append(a, 1);
try list.append(a, 2);
try list.append(a, 3);
list.shrinkAndFree(a, 1);
try testing.expect(list.items.len == 1);
}
}
test "shrinkAndFree with a copy" {
var failing_allocator = testing.FailingAllocator.init(testing.allocator, .{ .resize_fail_index = 0 });
const a = failing_allocator.allocator();
var list = Managed(i32).init(a);
defer list.deinit();
try list.appendNTimes(3, 16);
list.shrinkAndFree(4);
try testing.expect(mem.eql(i32, list.items, &.{ 3, 3, 3, 3 }));
}
test "shrinkAndFreePrecise without resize succeeds" {
var failing_allocator = testing.FailingAllocator.init(testing.allocator, .{ .resize_fail_index = 0 });
const a = failing_allocator.allocator();
var list: Aligned(i32, null) = .empty;
defer list.deinit(a);
try list.appendNTimes(a, 3, 16);
try list.shrinkAndFreePrecise(a, 4);
try testing.expectEqualSlices(i32, &.{ 3, 3, 3, 3 }, list.items);
try testing.expectEqual(list.items.len, list.capacity);
}
test "shrinkAndFreePrecise without resize and no copy failes" {
var failing_allocator = testing.FailingAllocator.init(testing.allocator, .{ .resize_fail_index = 0, .fail_index = 1 });
const a = failing_allocator.allocator();
var list: Aligned(i32, null) = .empty;
defer list.deinit(a);
try list.appendNTimes(a, 3, 16);
try std.testing.expectError(error.OutOfMemory, list.shrinkAndFreePrecise(a, 4));
}
test "addManyAsArray" {
const a = std.testing.allocator;
{
var list = Managed(u8).init(a);
defer list.deinit();
(try list.addManyAsArray(4)).* = "aoeu".*;
try list.ensureTotalCapacity(8);
list.addManyAsArrayAssumeCapacity(4).* = "asdf".*;
try testing.expectEqualSlices(u8, list.items, "aoeuasdf");
}
{
var list: ArrayList(u8) = .empty;
defer list.deinit(a);
(try list.addManyAsArray(a, 4)).* = "aoeu".*;
try list.ensureTotalCapacity(a, 8);
list.addManyAsArrayAssumeCapacity(4).* = "asdf".*;
try testing.expectEqualSlices(u8, list.items, "aoeuasdf");
}
}
test "growing memory preserves contents" {
// Shrink the list after every insertion to ensure that a memory growth
// will be triggered in the next operation.
const a = std.testing.allocator;
{
var list = Managed(u8).init(a);
defer list.deinit();
(try list.addManyAsArray(4)).* = "abcd".*;
list.shrinkAndFree(4);
try list.appendSlice("efgh");
try testing.expectEqualSlices(u8, list.items, "abcdefgh");
list.shrinkAndFree(8);
try list.insertSlice(4, "ijkl");
try testing.expectEqualSlices(u8, list.items, "abcdijklefgh");
}
{
var list: ArrayList(u8) = .empty;
defer list.deinit(a);
(try list.addManyAsArray(a, 4)).* = "abcd".*;
list.shrinkAndFree(a, 4);
try list.appendSlice(a, "efgh");
try testing.expectEqualSlices(u8, list.items, "abcdefgh");
list.shrinkAndFree(a, 8);
try list.insertSlice(a, 4, "ijkl");
try testing.expectEqualSlices(u8, list.items, "abcdijklefgh");
}
}
test "fromOwnedSlice" {
const a = testing.allocator;
{
var orig_list = Managed(u8).init(a);
defer orig_list.deinit();
try orig_list.appendSlice("foobar");
const slice = try orig_list.toOwnedSlice();
var list = Managed(u8).fromOwnedSlice(a, slice);
defer list.deinit();
try testing.expectEqualStrings(list.items, "foobar");
}
{
var list = Managed(u8).init(a);
defer list.deinit();
try list.appendSlice("foobar");
const slice = try list.toOwnedSlice();
var unmanaged = ArrayList(u8).fromOwnedSlice(slice);
defer unmanaged.deinit(a);
try testing.expectEqualStrings(unmanaged.items, "foobar");
}
}
test "fromOwnedSliceSentinel" {
const a = testing.allocator;
{
var orig_list = Managed(u8).init(a);
defer orig_list.deinit();
try orig_list.appendSlice("foobar");
const sentinel_slice = try orig_list.toOwnedSliceSentinel(0);
var list = Managed(u8).fromOwnedSliceSentinel(a, 0, sentinel_slice);
defer list.deinit();
try testing.expectEqualStrings(list.items, "foobar");
}
{
var list = Managed(u8).init(a);
defer list.deinit();
try list.appendSlice("foobar");
const sentinel_slice = try list.toOwnedSliceSentinel(0);
var unmanaged = ArrayList(u8).fromOwnedSliceSentinel(0, sentinel_slice);
defer unmanaged.deinit(a);
try testing.expectEqualStrings(unmanaged.items, "foobar");
}
}
test "toOwnedSliceSentinel" {
const a = testing.allocator;
{
var list = Managed(u8).init(a);
defer list.deinit();
try list.appendSlice("foobar");
const result = try list.toOwnedSliceSentinel(0);
defer a.free(result);
try testing.expectEqualStrings(result, mem.sliceTo(result.ptr, 0));
}
{
var list: ArrayList(u8) = .empty;
defer list.deinit(a);
try list.appendSlice(a, "foobar");
const result = try list.toOwnedSliceSentinel(a, 0);
defer a.free(result);
try testing.expectEqualStrings(result, mem.sliceTo(result.ptr, 0));
}
}
test "toOwnedSliceAssert" {
var failing_allocator: testing.FailingAllocator = .init(testing.allocator, .{
.fail_index = 2,
});
const a = failing_allocator.allocator();
var list: Aligned(u8, null) = try .initCapacity(a, 6); // first alloc
list.appendSliceAssumeCapacity(&.{ 1, 2, 3 });
try list.shrinkToLen(a); // first resize
try std.testing.expectEqual(list.items.len, list.capacity);
try list.shrinkToLen(a); // no alloc or resize
const slice = list.toOwnedSliceAssert();
defer a.free(slice);
try std.testing.expectEqual(Aligned(u8, null).empty, list);
try std.testing.expectEqualSlices(u8, &.{ 1, 2, 3 }, slice);
}
test "toOwnedSliceSentinelAssert" {
const a = testing.allocator;
var list: Aligned(u8, null) = try .initCapacity(a, 6);
list.appendSliceAssumeCapacity(&.{ 1, 2, 3 });
// shrinkToLenSentinel shrinks array
try list.shrinkToLenSentinel(a);
// shrinkToLenSentinel expands array
try list.shrinkToLen(a);
try list.shrinkToLenSentinel(a);
const slice = list.toOwnedSliceSentinelAssert(10);
defer a.free(slice);
try std.testing.expectEqualSentinel(u8, 10, &.{ 1, 2, 3 }, slice);
}
test "accepts unaligned slices" {
const a = testing.allocator;
{
var list = AlignedManaged(u8, .@"8").init(a);
defer list.deinit();
try list.appendSlice(&.{ 0, 1, 2, 3 });
try list.insertSlice(2, &.{ 4, 5, 6, 7 });
try list.replaceRange(1, 3, &.{ 8, 9 });
try testing.expectEqualSlices(u8, list.items, &.{ 0, 8, 9, 6, 7, 2, 3 });
}
{
var list: Aligned(u8, .@"8") = .empty;
defer list.deinit(a);
try list.appendSlice(a, &.{ 0, 1, 2, 3 });
try list.insertSlice(a, 2, &.{ 4, 5, 6, 7 });
try list.replaceRange(a, 1, 3, &.{ 8, 9 });
try testing.expectEqualSlices(u8, list.items, &.{ 0, 8, 9, 6, 7, 2, 3 });
}
}
test "Managed(u0)" {
// An Managed on zero-sized types should not need to allocate
const a = testing.failing_allocator;
var list = Managed(u0).init(a);
defer list.deinit();
try list.append(0);
try list.append(0);
try list.append(0);
try testing.expectEqual(list.items.len, 3);
var count: usize = 0;
for (list.items) |x| {
try testing.expectEqual(x, 0);
count += 1;
}
try testing.expectEqual(count, 3);
const ownedSlice = try list.toOwnedSlice();
defer a.free(ownedSlice);
try testing.expectEqualSlices(u0, ownedSlice, &.{ 0, 0, 0 });
}
test "Managed(?u32).pop()" {
const a = testing.allocator;
var list = Managed(?u32).init(a);
defer list.deinit();
try list.append(null);
try list.append(1);
try list.append(2);
try testing.expectEqual(list.items.len, 3);
try testing.expect(list.pop().? == @as(u32, 2));
try testing.expect(list.pop().? == @as(u32, 1));
try testing.expect(list.pop().? == null);
try testing.expect(list.pop() == null);
}
test "last" {
const a = testing.allocator;
var list: ArrayList(u32) = .empty;
defer list.deinit(a);
try testing.expectEqual(list.last(), null);
try list.append(a, 2);
try testing.expectEqual(list.last().?, 2);
}
test "return OutOfMemory when capacity would exceed maximum usize integer value" {
const a = testing.allocator;
const new_item: u32 = 42;
const items = &.{ 42, 43 };
{
var list: ArrayList(u32) = .{
.items = undefined,
.capacity = math.maxInt(usize) - 1,
.pointer_stability = .{},
};
list.items.len = math.maxInt(usize) - 1;
try testing.expectError(error.OutOfMemory, list.appendSlice(a, items));
try testing.expectError(error.OutOfMemory, list.appendNTimes(a, new_item, 2));
try testing.expectError(error.OutOfMemory, list.appendUnalignedSlice(a, &.{ new_item, new_item }));
try testing.expectError(error.OutOfMemory, list.addManyAt(a, 0, 2));
try testing.expectError(error.OutOfMemory, list.addManyAsArray(a, 2));
try testing.expectError(error.OutOfMemory, list.addManyAsSlice(a, 2));
try testing.expectError(error.OutOfMemory, list.insertSlice(a, 0, items));
try testing.expectError(error.OutOfMemory, list.ensureUnusedCapacity(a, 2));
}
{
var list: Managed(u32) = .{
.items = undefined,
.capacity = math.maxInt(usize) - 1,
.allocator = a,
.pointer_stability = .{},
};
list.items.len = math.maxInt(usize) - 1;
try testing.expectError(error.OutOfMemory, list.appendSlice(items));
try testing.expectError(error.OutOfMemory, list.appendNTimes(new_item, 2));
try testing.expectError(error.OutOfMemory, list.appendUnalignedSlice(&.{ new_item, new_item }));
try testing.expectError(error.OutOfMemory, list.addManyAt(0, 2));
try testing.expectError(error.OutOfMemory, list.addManyAsArray(2));
try testing.expectError(error.OutOfMemory, list.addManyAsSlice(2));
try testing.expectError(error.OutOfMemory, list.insertSlice(0, items));
try testing.expectError(error.OutOfMemory, list.ensureUnusedCapacity(2));
}
}
test "orderedRemoveMany" {
const gpa = testing.allocator;
var list: Aligned(usize, null) = .empty;
defer list.deinit(gpa);
for (0..10) |n| {
try list.append(gpa, n);
}
list.orderedRemoveMany(&.{ 1, 5, 5, 7, 9 });
try testing.expectEqualSlices(usize, &.{ 0, 2, 3, 4, 6, 8 }, list.items);
list.orderedRemoveMany(&.{0});
try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, list.items);
list.orderedRemoveMany(&.{});
try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, list.items);
list.orderedRemoveMany(&.{ 1, 2, 3, 4 });
try testing.expectEqualSlices(usize, &.{2}, list.items);
list.orderedRemoveMany(&.{0});
try testing.expectEqualSlices(usize, &.{}, list.items);
}
test "insertSlice*" {
var buf: [10]u8 = undefined;
var list: ArrayList(u8) = .initBuffer(&buf);
list.appendSliceAssumeCapacity("abcd");
list.insertSliceAssumeCapacity(2, "ef");
try testing.expectEqualStrings("abefcd", list.items);
try list.insertSliceBounded(4, "gh");
try testing.expectEqualStrings("abefghcd", list.items);
try testing.expectError(error.OutOfMemory, list.insertSliceBounded(6, "ijkl"));
try testing.expectEqualStrings("abefghcd", list.items); // ensure no elements were changed before the return of error.OutOfMemory
list.insertSliceAssumeCapacity(6, "ij");
try testing.expectEqualStrings("abefghijcd", list.items);
}