Skip to content
Standard libraryZig 0.17.1Official documentation
Sourcestd/array_list.zig

Source line 1

std.array_list.addOrOom

function

Source line 1559

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

Source line 632

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

T: type
alignment: ?mem.Alignment

Fields

items: Slice

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.

capacity: usize

How many T values this list can hold without allocating additional memory.

pointer_stability: debug.SafetyLock

Used to detect memory safety violations.

std.array_list.Aligned.addManyAsArray

function

Source line 1434

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

self: *Self
gpa: Allocator
n: usize

Errors

OutOfMemory

std.array_list.Aligned.addManyAsArrayAssumeCapacity

function

Source line 1445

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

Source line 1458

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

Source line 1467

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

self: *Self
gpa: Allocator
n: usize

Errors

OutOfMemory

std.array_list.Aligned.addManyAsSliceAssumeCapacity

function

Source line 1478

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

Source line 1491

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

Source line 854

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

self: *Self
gpa: Allocator
index: usize
count: usize

Errors

OutOfMemory

std.array_list.Aligned.addManyAtAssumeCapacity

function

Source line 900

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

self: *Self
index: usize
count: usize

std.array_list.Aligned.addManyAtBounded

function

Source line 920

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

self: *Self
index: usize
count: usize

Errors

OutOfMemory

std.array_list.Aligned.addOne

function

Source line 1403

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

self: *Self
gpa: Allocator

Errors

OutOfMemory

std.array_list.Aligned.addOneAssumeCapacity

function

Source line 1414

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

Source line 1425

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

Source line 1512

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

Source line 1026

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

self: *Self
gpa: Allocator
item: T

Errors

OutOfMemory

std.array_list.Aligned.appendAssumeCapacity

function

Source line 1036

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

Source line 1046

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

Source line 1204

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

self: *Self
gpa: Allocator
value: T
n: usize

Errors

OutOfMemory

std.array_list.Aligned.appendNTimesAssumeCapacity

function

Source line 1218

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

self: *Self
value: T
n: usize

std.array_list.Aligned.appendNTimesBounded

function

Source line 1234

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

self: *Self
value: T
n: usize

Errors

OutOfMemory

std.array_list.Aligned.appendSlice

function

Source line 1108

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

self: *Self
gpa: Allocator
items: []const T

Errors

OutOfMemory

std.array_list.Aligned.appendSliceAssumeCapacity

function

Source line 1116

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

Source line 1127

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

Source line 1136

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

self: *Self
gpa: Allocator
items: []align(1) const T

Errors

OutOfMemory

std.array_list.Aligned.appendUnalignedSliceAssumeCapacity

function

Source line 1147

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

Source line 1162

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

Source line 1337

Invalidates all element pointers.

pub fn clearAndFree(self: *Self, gpa: Allocator) void

Parameters

self: *Self
gpa: Allocator

std.array_list.Aligned.clearRetainingCapacity

function

Source line 1330

Reduce length to 0. Invalidates all element pointers.

pub fn clearRetainingCapacity(self: *Self) void

Parameters

self: *Self

std.array_list.Aligned.clone

function

Source line 800

Creates a copy of this ArrayList.

pub fn clone(self: Self, gpa: Allocator) Allocator.Error!Self

Parameters

self: Self
gpa: Allocator

Errors

OutOfMemory

std.array_list.Aligned.deinit

function

Source line 690

Release all allocated memory.

pub fn deinit(self: *Self, gpa: Allocator) void

Parameters

self: *Self
gpa: Allocator

std.array_list.Aligned.empty

constant

Source line 656

An ArrayList containing no elements.

Self

std.array_list.Aligned.ensureTotalCapacity

function

Source line 1347

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

self: *Self
gpa: Allocator
new_capacity: usize

Errors

OutOfMemory

std.array_list.Aligned.ensureTotalCapacityPrecise

function

Source line 1355

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

self: *Self
gpa: Allocator
new_capacity: usize

Errors

OutOfMemory

std.array_list.Aligned.ensureUnusedCapacity

function

Source line 1385

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

self: *Self
gpa: Allocator
additional_count: usize

Errors

OutOfMemory

std.array_list.Aligned.expandToCapacity

function

Source line 1396

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

Source line 727

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

Source line 737

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

Source line 1526

Deprecated

pub fn getLast(self: Self) T

Parameters

self: Self

std.array_list.Aligned.getLastOrNull

alias

Source line 1531

Deprecated in favor of last

Alias of std.array_list.Aligned.last

std.array_list.Aligned.growCapacity

function

Source line 1550

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

Source line 681

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

Source line 670

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

Source line 812

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

self: *Self
gpa: Allocator
index: usize
item: T

Errors

OutOfMemory

std.array_list.Aligned.insertAssumeCapacity

function

Source line 825

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

self: *Self
index: usize
item: T

std.array_list.Aligned.insertBounded

function

Source line 841

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

self: *Self
i: usize
item: T

Errors

OutOfMemory

std.array_list.Aligned.insertSlice

function

Source line 931

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

self: *Self
gpa: Allocator
index: usize
items: []const T

Errors

OutOfMemory

std.array_list.Aligned.insertSliceAssumeCapacity

function

Source line 950

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

self: *Self
index: usize
items: []const T

std.array_list.Aligned.insertSliceBounded

function

Source line 965

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

self: *Self
index: usize
items: []const T

Errors

OutOfMemory

std.array_list.Aligned.last

function

Source line 1535

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

Source line 1543

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

Source line 705

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

Source line 1055

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

Source line 1073

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

Source line 1499

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

Source line 1169

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

self: *Self
gpa: Allocator
fmt: []const u8

Errors

OutOfMemory

std.array_list.Aligned.printAssumeCapacity

function

Source line 1182

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

Source line 1192

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

Source line 979

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

self: *Self
gpa: Allocator
start: usize
len: usize
new_items: []const T

Errors

OutOfMemory

std.array_list.Aligned.replaceRangeAssumeCapacity

function

Source line 994

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

self: *Self
start: usize
len: usize
new_items: []const T

std.array_list.Aligned.replaceRangeBounded

function

Source line 1014

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

self: *Self
start: usize
len: usize
new_items: []const T

Errors

OutOfMemory

std.array_list.Aligned.resize

function

Source line 1244

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

self: *Self
gpa: Allocator
new_len: usize

Errors

OutOfMemory

std.array_list.Aligned.Self

alias

Source line 639

Alias of std.array_list.Aligned

std.array_list.Aligned.SentinelSlice

type-function

Source line 664

pub fn SentinelSlice(comptime s: T) type

Parameters

s: T

std.array_list.Aligned.shrinkAndFree

function

Source line 1252

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

self: *Self
gpa: Allocator
new_len: usize

std.array_list.Aligned.shrinkAndFreePrecise

function

Source line 1266

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

self: *Self
gpa: Allocator
new_len: usize

Errors

OutOfMemory

std.array_list.Aligned.shrinkRetainingCapacity

function

Source line 1320

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

Source line 1293

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

self: *Self
gpa: Allocator

Errors

OutOfMemory

std.array_list.Aligned.shrinkToLenSentinel

function

Source line 1300

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

self: *Self
gpa: Allocator

Errors

OutOfMemory

std.array_list.Aligned.Slice

type

Source line 662

std.array_list.Aligned.swapRemove

function

Source line 1096

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

Source line 716

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

self: *Self
gpa: Allocator

std.array_list.Aligned.toOwnedSlice

function

Source line 748

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

self: *Self
gpa: Allocator

Errors

OutOfMemory

std.array_list.Aligned.toOwnedSliceAssert

function

Source line 782

The caller owns the returned memory. Empties this ArrayList. Its capacity is cleared, making deinit() safe but unnecessary to call.

Asserts that 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

Source line 764

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

self: *Self
gpa: Allocator
sentinel: T

Errors

OutOfMemory

std.array_list.Aligned.toOwnedSliceSentinelAssert

function

Source line 792

The caller owns the returned memory. ArrayList becomes empty. Asserts that 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

Source line 710

Undoes one call to lockPointers.

pub fn unlockPointers(self: *Self) void

Parameters

self: *Self

std.array_list.Aligned.unusedCapacitySlice

function

Source line 1521

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

Source line 16

Deprecated.

pub fn AlignedManaged(comptime T: type, comptime alignment: ?mem.Alignment) type

Parameters

T: type
alignment: ?mem.Alignment

Fields

items: Slice

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.

capacity: usize

How many T values this list can hold without allocating additional memory.

allocator: Allocator
pointer_stability: debug.SafetyLock

Used to detect memory safety violations.

std.array_list.AlignedManaged.addManyAsArray

function

Source line 530

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

Source line 541

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

Source line 553

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

Source line 564

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

Source line 199

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

self: *Self
index: usize
count: usize

Errors

OutOfMemory

std.array_list.AlignedManaged.addManyAtAssumeCapacity

function

Source line 240

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

self: *Self
index: usize
count: usize

std.array_list.AlignedManaged.addOne

function

Source line 508

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

Source line 519

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

Source line 585

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

Source line 290

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

Source line 298

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

Source line 386

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

self: *Self
value: T
n: usize

Errors

OutOfMemory

std.array_list.AlignedManaged.appendNTimesAssumeCapacity

function

Source line 397

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

self: *Self
value: T
n: usize

std.array_list.AlignedManaged.appendSlice

function

Source line 333

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

Source line 341

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

Source line 353

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

Source line 364

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

Source line 440

Invalidates all element pointers.

pub fn clearAndFree(self: *Self) void

Parameters

self: *Self

std.array_list.AlignedManaged.clearRetainingCapacity

function

Source line 433

Reduce length to 0. Invalidates all element pointers.

pub fn clearRetainingCapacity(self: *Self) void

Parameters

self: *Self

std.array_list.AlignedManaged.clone

function

Source line 158

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

Source line 66

Release all allocated memory.

pub fn deinit(self: Self) void

Parameters

self: Self

std.array_list.AlignedManaged.ensureTotalCapacity

function

Source line 450

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

Source line 466

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

Source line 494

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

Source line 501

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

Source line 94

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

gpa: Allocator
slice: Slice

std.array_list.AlignedManaged.fromOwnedSliceSentinel

function

Source line 106

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

gpa: Allocator
sentinel: T
slice: [:sentinel]T

std.array_list.AlignedManaged.getLast

function

Source line 600

Deprecated

pub fn getLast(self: Self) T

Parameters

self: Self

std.array_list.AlignedManaged.getLastOrNull

alias

Source line 605

Deprecated in favor of last

Alias of std.array_list.AlignedManaged.last

std.array_list.AlignedManaged.init

function

Source line 47

Deinitialize with deinit or use toOwnedSlice.

pub fn init(gpa: Allocator) Self

Parameters

gpa: Allocator

std.array_list.AlignedManaged.initCapacity

function

Source line 59

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

Source line 170

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

self: *Self
index: usize
item: T

Errors

OutOfMemory

std.array_list.AlignedManaged.insertAssumeCapacity

function

Source line 183

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

self: *Self
index: usize
item: T

std.array_list.AlignedManaged.insertSlice

function

Source line 258

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

self: *Self
index: usize
items: []const T

Errors

OutOfMemory

std.array_list.AlignedManaged.last

function

Source line 610

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

Source line 618

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

Source line 82

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

Source line 117

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

Source line 309

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

Source line 573

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

Source line 374

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

Source line 272

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

self: *Self
start: usize
len: usize
new_items: []const T

Errors

OutOfMemory

std.array_list.AlignedManaged.replaceRangeAssumeCapacity

function

Source line 282

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

self: *Self
start: usize
len: usize
new_items: []const T

std.array_list.AlignedManaged.resize

function

Source line 407

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

Source line 23

Alias of std.array_list.AlignedManaged

std.array_list.AlignedManaged.SentinelSlice

type-function

Source line 42

pub fn SentinelSlice(comptime s: T) type

Parameters

s: T

std.array_list.AlignedManaged.shrinkAndFree

function

Source line 415

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

Source line 424

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

Source line 40

std.array_list.AlignedManaged.swapRemove

function

Source line 321

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

Source line 131

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

Source line 149

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

Source line 87

Undoes one call to lockPointers.

pub fn unlockPointers(self: *Self) void

Parameters

self: *Self

std.array_list.AlignedManaged.unusedCapacitySlice

function

Source line 595

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

Source line 7

Alias of std.mem.Allocator

std.array_list.ArrayList

alias

Source line 8

Alias of std.ArrayList

std.array_list.assert

alias

Source line 3

Alias of std.debug.assert

std.array_list.debug

alias

Source line 2

Alias of std.debug

std.array_list.Item

container

Source line 2209

Fields

integer: i32
sub_items: Managed(Item)

std.array_list.ItemUnmanaged

container

Source line 2214

Fields

integer: i32
sub_items: ArrayList(ItemUnmanaged)

std.array_list.Managed

type-function

Source line 11

Deprecated.

pub fn Managed(comptime T: type) type

Parameters

T: type

Fields

items: Slice

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.

capacity: usize

How many T values this list can hold without allocating additional memory.

allocator: Allocator
pointer_stability: debug.SafetyLock

Used to detect memory safety violations.

std.array_list.math

alias

Source line 6

Alias of std.math

std.array_list.mem

alias

Source line 5

Alias of std.mem

std.array_list.std

alias

Source line 1

Alias of std

std.array_list.testing

alias

Source line 4

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 that 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 that 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);
}