Skip to content

std.multi_array_list

Standard libraryZig 0.17.1Official documentation
Sourcestd/multi_array_list.zig

Source line 1

std.multi_array_list.Allocator

alias

Source line 6

Alias of std.mem.Allocator

std.multi_array_list.assert

alias

Source line 3

Alias of std.debug.assert

std.multi_array_list.builtin

constant

Source line 2

std.multi_array_list.doTest

function

Source line 1113

fn doTest(ally: std.mem.Allocator, count: comptime_int) !void

Parameters

ally: std.mem.Allocator
count: comptime_int

std.multi_array_list.lessThan

function

Source line 1033

fn lessThan(ctx: @This(), a: usize, b: usize) bool

Parameters

ctx: @This()
a: usize
b: usize

std.multi_array_list.mem

alias

Source line 5

Alias of std.mem

std.multi_array_list.meta

alias

Source line 4

Alias of std.meta

std.multi_array_list.MultiArrayList

type-function

Source line 20

A MultiArrayList stores a list of a struct or tagged union type. Instead of storing a single list of items, MultiArrayList stores separate lists for each field of the struct or lists of tags and bare unions. This allows for memory savings if the struct or union has padding, and also improves cache usage if only some fields or just tags are needed for a computation. The primary API for accessing fields is the slice() function, which computes the start pointers for the array of each field. From the slice you can call .items(.<field_name>) to obtain a slice of field values. For unions you can call .items(.tags) or .items(.data).

pub fn MultiArrayList(comptime T: type) type

Parameters

T: type

Fields

bytes: [*]u8 = undefined

This pointer is always aligned to the boundary sizes.big_align; this is not specified in the type to avoid MultiArrayList(T) depending on the alignment of T because this can lead to dependency loops. See allocatedBytes which @alignCasts this pointer to the correct type.

len: usize = 0
capacity: usize = 0

std.multi_array_list.MultiArrayList.addOne

function

Source line 303

Extend the list by 1 element, returning the newly reserved index with uninitialized data.

Allocates more memory as necessary.

pub fn addOne(self: *Self, gpa: Allocator) Allocator.Error!usize

Parameters

self: *Self
gpa: Allocator

Errors

OutOfMemory

std.multi_array_list.MultiArrayList.addOneAssumeCapacity

function

Source line 312

Extend the list by 1 element, returning the newly reserved index with uninitialized data.

Asserts that capacity is sufficient to hold an additional item.

pub fn addOneAssumeCapacity(self: *Self) usize

Parameters

self: *Self

std.multi_array_list.MultiArrayList.addOneBounded

function

Source line 324

Extend the list by 1 element, returning the newly reserved index with uninitialized data.

If capacity is not sufficient to hold an additional item, returns error.OutOfMemory.

pub fn addOneBounded(self: *Self) error{OutOfMemory}!usize

Parameters

self: *Self

Errors

OutOfMemory

std.multi_array_list.MultiArrayList.allocatedBytes

function

Source line 662

fn allocatedBytes(self: Self) []align(sizes.big_align.toByteUnits()) u8

Parameters

self: Self

std.multi_array_list.MultiArrayList.append

function

Source line 276

Extend the list by 1 element.

Allocates more memory as necessary.

pub fn append(self: *Self, gpa: Allocator, elem: T) Allocator.Error!void

Parameters

self: *Self
gpa: Allocator
elem: T

Errors

OutOfMemory

std.multi_array_list.MultiArrayList.appendAssumeCapacity

function

Source line 284

Extend the list by 1 element.

Asserts that capacity is sufficient to hold an additional item.

pub fn appendAssumeCapacity(self: *Self, elem: T) void

Parameters

self: *Self
elem: T

std.multi_array_list.MultiArrayList.appendBounded

function

Source line 294

Extend the list by 1 element.

If capacity is not sufficient to hold an additional item, returns error.OutOfMemory.

pub fn appendBounded(self: *Self, elem: T) error{OutOfMemory}!void

Parameters

self: *Self
elem: T

Errors

OutOfMemory

std.multi_array_list.MultiArrayList.capacityInBytes

function

Source line 656

pub fn capacityInBytes(capacity: usize) usize

Parameters

capacity: usize

std.multi_array_list.MultiArrayList.clearAndFree

function

Source line 497

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

Parameters

self: *Self
gpa: Allocator

std.multi_array_list.MultiArrayList.clearRetainingCapacity

function

Source line 510

Invalidates all element pointers.

pub fn clearRetainingCapacity(self: *Self) void

Parameters

self: *Self

std.multi_array_list.MultiArrayList.clone

function

Source line 571

Create a copy of this list with a new backing store, using the specified allocator.

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

Parameters

self: Self
gpa: Allocator

Errors

OutOfMemory

std.multi_array_list.MultiArrayList.dbHelper

function

Source line 686

This function is used in the debugger pretty formatters in lib/lldb/ to fetch the child field order and entry type to facilitate fancy debug printing for this type.

fn dbHelper(self: *Self, child: *Elem, field: *Field, entry: *Entry) void

Parameters

self: *Self
child: *Elem
field: *Field
entry: *Entry

std.multi_array_list.MultiArrayList.deinit

function

Source line 222

Release all allocated memory.

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

Parameters

self: *Self
gpa: Allocator

std.multi_array_list.MultiArrayList.Elem

type

Source line 44

std.multi_array_list.MultiArrayList.Elem.Bare

type

Source line 47

std.multi_array_list.MultiArrayList.Elem.fromT

function

Source line 53

pub fn fromT(outer: T) @This()

Parameters

outer: T

std.multi_array_list.MultiArrayList.Elem.Tag

constant

Source line 48

std.multi_array_list.MultiArrayList.Elem.toT

function

Source line 62

pub fn toT(tag: Tag, bare: Bare) T

Parameters

tag: Tag
bare: Bare

std.multi_array_list.MultiArrayList.empty

constant

Source line 30

Self

std.multi_array_list.MultiArrayList.ensureTotalCapacity

function

Source line 517

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.multi_array_list.MultiArrayList.ensureUnusedCapacity

function

Source line 536

Modify the array so that it can hold at least additional_count more items. Invalidates 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.multi_array_list.MultiArrayList.Entry

constant

Source line 670

std.multi_array_list.MultiArrayList.Field

type

Source line 71

std.multi_array_list.MultiArrayList.field_attrs

constant

Source line 180

std.multi_array_list.MultiArrayList.field_names

constant

Source line 178

std.multi_array_list.MultiArrayList.field_types

constant

Source line 179

std.multi_array_list.MultiArrayList.FieldType

type-function

Source line 666

fn FieldType(comptime field: Field) type

Parameters

field: Field

std.multi_array_list.MultiArrayList.get

function

Source line 265

Obtain all the data for one array element.

pub fn get(self: Self, index: usize) T

Parameters

self: Self
index: usize

std.multi_array_list.MultiArrayList.growCapacity

function

Source line 530

Given a lower bound of required memory capacity, returns a larger value with super-linear growth.

pub fn growCapacity(minimum: usize) usize

Parameters

minimum: usize

std.multi_array_list.MultiArrayList.init_capacity

constant

Source line 522

comptime_int

std.multi_array_list.MultiArrayList.initCapacity

function

Source line 38

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.multi_array_list.MultiArrayList.insert

function

Source line 343

Inserts an item into the list. Shifts all elements after and including the specified index back by one and sets the given index to the specified element.

Allocates more memory as necessary.

pub fn insert(self: *Self, gpa: Allocator, index: usize, elem: T) !void

Parameters

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

std.multi_array_list.MultiArrayList.insertAssumeCapacity

function

Source line 353

Inserts an item into the list. Shifts all elements after and including the specified index back by one and sets the given index to the specified element.

Asserts that capacity is sufficient to hold an additional item.

pub fn insertAssumeCapacity(self: *Self, index: usize, elem: T) void

Parameters

self: *Self
index: usize
elem: T

std.multi_array_list.MultiArrayList.insertBounded

function

Source line 379

Inserts an item into the list. Shifts all elements after and including the specified index back by one and sets the given index to the specified element.

If capacity is not sufficient to hold an additional item, returns error.OutOfMemory.

pub fn insertBounded(self: *Self, index: usize, elem: T) error{OutOfMemory}!void

Parameters

self: *Self
index: usize
elem: T

Errors

OutOfMemory

std.multi_array_list.MultiArrayList.items

function

Source line 254

Get the slice of values for a specified field. If you need multiple fields, consider calling slice() instead.

pub fn items(self: Self, comptime field: Field) []FieldType(field)

Parameters

self: Self
field: Field

std.multi_array_list.MultiArrayList.orderedRemove

function

Source line 399

Remove the specified item from the list, shifting items after it to preserve order.

pub fn orderedRemove(self: *Self, index: usize) void

Parameters

self: *Self
index: usize

std.multi_array_list.MultiArrayList.orderedRemoveMany

function

Source line 424

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.multi_array_list.MultiArrayList.pop

function

Source line 331

Remove and return the last element from the list, or return null if list is empty. Invalidates pointers to fields of the removed element.

pub fn pop(self: *Self) ?T

Parameters

self: *Self

std.multi_array_list.MultiArrayList.resize

function

Source line 450

Adjust the list's length to new_len. Does not initialize added items, if any.

pub fn resize(self: *Self, gpa: Allocator, new_len: usize) Allocator.Error!void

Parameters

self: *Self
gpa: Allocator
new_len: usize

Errors

OutOfMemory

std.multi_array_list.MultiArrayList.Self

alias

Source line 176

Alias of std.multi_array_list.MultiArrayList

std.multi_array_list.MultiArrayList.set

function

Source line 259

Overwrite one array element with new data.

pub fn set(self: *Self, index: usize, elem: T) void

Parameters

self: *Self
index: usize
elem: T

std.multi_array_list.MultiArrayList.setCapacity

function

Source line 543

Modify the array so that it can hold exactly new_capacity items. Invalidates pointers if additional memory is needed. new_capacity must be greater or equal to len.

pub fn setCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void

Parameters

self: *Self
gpa: Allocator
new_capacity: usize

Errors

OutOfMemory

std.multi_array_list.MultiArrayList.shrinkAndFree

function

Source line 458

Attempt to reduce allocated capacity to new_len. If new_len is greater than zero, this may fail to reduce the capacity, but the data remains intact and the length is updated to new_len.

pub fn shrinkAndFree(self: *Self, gpa: Allocator, new_len: usize) void

Parameters

self: *Self
gpa: Allocator
new_len: usize

std.multi_array_list.MultiArrayList.shrinkRetainingCapacity

function

Source line 505

Reduce length to new_len. Invalidates pointers to elements items[new_len..]. Keeps capacity the same.

pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void

Parameters

self: *Self
new_len: usize

std.multi_array_list.MultiArrayList.sizes

constant

Source line 184

sizes.bytes is an array of @sizeOf each T field. Sorted by alignment, descending. sizes.fields is an array mapping from sizes.bytes array index to field index. sizes.big_align is the overall alignment of the allocation, which equals the maximum field alignment.

std.multi_array_list.MultiArrayList.sizes.lessThan

function

Source line 201

fn lessThan(context: void, lhs: Data, rhs: Data) bool

Parameters

context: void
lhs: Data
rhs: Data

std.multi_array_list.MultiArrayList.slice

function

Source line 237

Compute pointers to the start of each field of the array. If you need to access multiple fields, calling this may be more efficient than calling items() multiple times.

pub fn slice(self: Self) Slice

Parameters

self: Self

std.multi_array_list.MultiArrayList.Slice

container

Source line 77

A MultiArrayList.Slice contains cached start pointers for each field in the list. These pointers are not normally stored to reduce the size of the list in memory. If you are accessing multiple fields, call slice() first to compute the pointers, and then get the field arrays from the slice.

Fields

ptrs: [field_names.len][*]u8

This array is indexed by the field index which can be obtained by using @intFromEnum() on the Field enum

len: usize
capacity: usize

std.multi_array_list.MultiArrayList.Slice.dbHelper

function

Source line 168

This function is used in the debugger pretty formatters in lib/lldb/ to fetch the child field order and entry type to facilitate fancy debug printing for this type.

fn dbHelper(self: *Slice, child: *Elem, field: *Field, entry: *Entry) void

Parameters

self: *Slice
child: *Elem
field: *Field
entry: *Entry

std.multi_array_list.MultiArrayList.Slice.deinit

function

Source line 144

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

Parameters

self: *Slice
gpa: Allocator

std.multi_array_list.MultiArrayList.Slice.empty

constant

Source line 84

Slice

std.multi_array_list.MultiArrayList.Slice.get

function

Source line 114

pub fn get(self: Slice, index: usize) T

Parameters

self: Slice
index: usize

std.multi_array_list.MultiArrayList.Slice.items

function

Source line 90

pub fn items(self: Slice, comptime field: Field) []FieldType(field)

Parameters

self: Slice
field: Field

std.multi_array_list.MultiArrayList.Slice.set

function

Source line 103

pub fn set(self: *Slice, index: usize, elem: T) void

Parameters

self: *Slice
index: usize
elem: T

std.multi_array_list.MultiArrayList.Slice.subslice

function

Source line 153

Returns a Slice representing a range of elements in s, analagous to arr[off..len]. It is illegal to call deinit or toMultiArrayList on the returned Slice. Asserts that off + len <= s.len.

pub fn subslice(s: Slice, off: usize, len: usize) Slice

Parameters

s: Slice
off: usize
len: usize

std.multi_array_list.MultiArrayList.Slice.swap

function

Source line 126

pub fn swap(self: Slice, a: usize, b: usize) void

Parameters

self: Slice
a: usize
b: usize

std.multi_array_list.MultiArrayList.Slice.toMultiArrayList

function

Source line 133

pub fn toMultiArrayList(self: Slice) Self

Parameters

self: Slice

std.multi_array_list.MultiArrayList.sort

function

Source line 623

This function guarantees a stable sort, i.e the relative order of equal elements is preserved during sorting. Read more about stable sorting here: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability If this guarantee does not matter, sortUnstable might be a faster alternative. ctx has the following method: fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool

pub fn sort(self: Self, ctx: anytype) void

Parameters

self: Self

std.multi_array_list.MultiArrayList.sortInternal

function

Source line 589

ctx has the following method: fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool

fn sortInternal(self: Self, a: usize, b: usize, ctx: anytype, comptime mode: std.sort.Mode) void

Parameters

self: Self
a: usize
b: usize
mode: std.sort.Mode

std.multi_array_list.MultiArrayList.sortInternal.lessThan

function

Source line 604

pub fn lessThan(sc: @This(), a_index: usize, b_index: usize) bool

Parameters

sc: @This()
a_index: usize
b_index: usize

std.multi_array_list.MultiArrayList.sortInternal.swap

function

Source line 594

pub fn swap(sc: @This(), a_index: usize, b_index: usize) void

Parameters

sc: @This()
a_index: usize
b_index: usize

std.multi_array_list.MultiArrayList.sortSpan

function

Source line 633

Sorts only the subsection of items between indices a and b (excluding b) This function guarantees a stable sort, i.e the relative order of equal elements is preserved during sorting. Read more about stable sorting here: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability If this guarantee does not matter, sortSpanUnstable might be a faster alternative. ctx has the following method: fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool

pub fn sortSpan(self: Self, a: usize, b: usize, ctx: anytype) void

Parameters

self: Self
a: usize
b: usize

std.multi_array_list.MultiArrayList.sortSpanUnstable

function

Source line 652

Sorts only the subsection of items between indices a and b (excluding b) This function does NOT guarantee a stable sort, i.e the relative order of equal elements may change during sorting. Due to the weaker guarantees of this function, this may be faster than the stable sortSpan method. Read more about stable sorting here: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability ctx has the following method: fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool

pub fn sortSpanUnstable(self: Self, a: usize, b: usize, ctx: anytype) void

Parameters

self: Self
a: usize
b: usize

std.multi_array_list.MultiArrayList.sortUnstable

function

Source line 642

This function does NOT guarantee a stable sort, i.e the relative order of equal elements may change during sorting. Due to the weaker guarantees of this function, this may be faster than the stable sort method. Read more about stable sorting here: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability ctx has the following method: fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool

pub fn sortUnstable(self: Self, ctx: anytype) void

Parameters

self: Self

std.multi_array_list.MultiArrayList.swap

function

Source line 269

pub fn swap(self: Self, a: usize, b: usize) void

Parameters

self: Self
a: usize
b: usize

std.multi_array_list.MultiArrayList.swapRemove

function

Source line 387

Remove the specified item from the list, swapping the last item in the list into its position. Fast, but does not retain list ordering.

pub fn swapRemove(self: *Self, index: usize) void

Parameters

self: *Self
index: usize

std.multi_array_list.MultiArrayList.toOwnedSlice

function

Source line 228

The caller owns the returned memory. Empties this MultiArrayList.

pub fn toOwnedSlice(self: *Self) Slice

Parameters

self: *Self

std.multi_array_list.std

alias

Source line 1

Alias of std

std.multi_array_list.testing

alias

Source line 7

Alias of std.testing

std.multi_array_list.Type

type-function

Source line 1106

fn Type(count: comptime_int) type

Parameters

count: comptime_int
Source code

std/multi_array_list.zig

const std = @import("std");
const builtin = @import("builtin");
const assert = std.debug.assert;
const meta = std.meta;
const mem = std.mem;
const Allocator = mem.Allocator;
const testing = std.testing;

/// A MultiArrayList stores a list of a struct or tagged union type.
/// Instead of storing a single list of items, MultiArrayList
/// stores separate lists for each field of the struct or
/// lists of tags and bare unions.
/// This allows for memory savings if the struct or union has padding,
/// and also improves cache usage if only some fields or just tags
/// are needed for a computation.  The primary API for accessing fields is
/// the `slice()` function, which computes the start pointers
/// for the array of each field.  From the slice you can call
/// `.items(.<field_name>)` to obtain a slice of field values.
/// For unions you can call `.items(.tags)` or `.items(.data)`.
pub fn MultiArrayList(comptime T: type) type {
    return struct {
        /// This pointer is always aligned to the boundary `sizes.big_align`; this is not specified
        /// in the type to avoid `MultiArrayList(T)` depending on the alignment of `T` because this
        /// can lead to dependency loops. See `allocatedBytes` which `@alignCast`s this pointer to
        /// the correct type.
        bytes: [*]u8 = undefined,
        len: usize = 0,
        capacity: usize = 0,

        pub const empty: Self = .{
            .bytes = undefined,
            .len = 0,
            .capacity = 0,
        };

        /// 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.setCapacity(gpa, num);
            return self;
        }

        const Elem = switch (@typeInfo(T)) {
            .@"struct" => T,
            .@"union" => |u| struct {
                pub const Bare = std.meta.BareUnion(T);
                pub const Tag =
                    u.tag_type orelse @compileError("MultiArrayList does not support untagged unions");
                tags: Tag,
                data: Bare,

                pub fn fromT(outer: T) @This() {
                    const tag = meta.activeTag(outer);
                    return .{
                        .tags = tag,
                        .data = switch (tag) {
                            inline else => |t| @unionInit(Bare, @tagName(t), @field(outer, @tagName(t))),
                        },
                    };
                }
                pub fn toT(tag: Tag, bare: Bare) T {
                    return switch (tag) {
                        inline else => |t| @unionInit(T, @tagName(t), @field(bare, @tagName(t))),
                    };
                }
            },
            else => @compileError("MultiArrayList only supports structs and tagged unions"),
        };

        pub const Field = meta.FieldEnum(Elem);

        /// A MultiArrayList.Slice contains cached start pointers for each field in the list.
        /// These pointers are not normally stored to reduce the size of the list in memory.
        /// If you are accessing multiple fields, call slice() first to compute the pointers,
        /// and then get the field arrays from the slice.
        pub const Slice = struct {
            /// This array is indexed by the field index which can be obtained
            /// by using @intFromEnum() on the Field enum
            ptrs: [field_names.len][*]u8,
            len: usize,
            capacity: usize,

            pub const empty: Slice = .{
                .ptrs = undefined,
                .len = 0,
                .capacity = 0,
            };

            pub fn items(self: Slice, comptime field: Field) []FieldType(field) {
                const F = FieldType(field);
                if (self.capacity == 0) {
                    return &[_]F{};
                }
                const byte_ptr = self.ptrs[@backingInt(field)];
                const casted_ptr: [*]F = if (@sizeOf(F) == 0)
                    undefined
                else
                    @ptrCast(@alignCast(byte_ptr));
                return casted_ptr[0..self.len];
            }

            pub fn set(self: *Slice, index: usize, elem: T) void {
                const e = switch (@typeInfo(T)) {
                    .@"struct" => elem,
                    .@"union" => Elem.fromT(elem),
                    else => unreachable,
                };
                inline for (field_names, 0..) |field_name, i| {
                    self.items(@as(Field, @fromBackingInt(@intCast(i))))[index] = @field(e, field_name);
                }
            }

            pub fn get(self: Slice, index: usize) T {
                var result: Elem = undefined;
                inline for (field_names, 0..) |field_name, i| {
                    @field(result, field_name) = self.items(@as(Field, @fromBackingInt(@intCast(i))))[index];
                }
                return switch (@typeInfo(T)) {
                    .@"struct" => result,
                    .@"union" => Elem.toT(result.tags, result.data),
                    else => unreachable,
                };
            }

            pub fn swap(self: Slice, a: usize, b: usize) void {
                inline for (@typeInfo(Field).@"enum".field_names) |field_name| {
                    const its = self.items(@field(Field, field_name));
                    std.mem.swap(@FieldType(T, field_name), &its[a], &its[b]);
                }
            }

            pub fn toMultiArrayList(self: Slice) Self {
                if (self.ptrs.len == 0 or self.capacity == 0) {
                    return .{};
                }
                return .{
                    .bytes = self.ptrs[sizes.fields[0]],
                    .len = self.len,
                    .capacity = self.capacity,
                };
            }

            pub fn deinit(self: *Slice, gpa: Allocator) void {
                var other = self.toMultiArrayList();
                other.deinit(gpa);
                self.* = undefined;
            }

            /// Returns a `Slice` representing a range of elements in `s`, analagous to `arr[off..len]`.
            /// It is illegal to call `deinit` or `toMultiArrayList` on the returned `Slice`.
            /// Asserts that `off + len <= s.len`.
            pub fn subslice(s: Slice, off: usize, len: usize) Slice {
                assert(off + len <= s.len);
                var ptrs: [field_names.len][*]u8 = undefined;
                inline for (s.ptrs, &ptrs, field_types) |in, *out, field_type| {
                    out.* = in + (off * @sizeOf(field_type));
                }
                return .{
                    .ptrs = ptrs,
                    .len = len,
                    .capacity = len,
                };
            }

            /// This function is used in the debugger pretty formatters in lib/lldb/ to fetch the
            /// child field order and entry type to facilitate fancy debug printing for this type.
            fn dbHelper(self: *Slice, child: *Elem, field: *Field, entry: *Entry) void {
                _ = self;
                _ = child;
                _ = field;
                _ = entry;
            }
        };

        const Self = @This();

        const field_names = @typeInfo(Elem).@"struct".field_names;
        const field_types = @typeInfo(Elem).@"struct".field_types;
        const field_attrs = @typeInfo(Elem).@"struct".field_attrs;
        /// `sizes.bytes` is an array of @sizeOf each T field. Sorted by alignment, descending.
        /// `sizes.fields` is an array mapping from `sizes.bytes` array index to field index.
        /// `sizes.big_align` is the overall alignment of the allocation, which equals the maximum field alignment.
        const sizes = blk: {
            const Data = struct {
                size: usize,
                size_index: usize,
                alignment: usize,
            };
            var data: [field_names.len]Data = undefined;
            var big_align: usize = 1;
            for (field_types, field_attrs, 0..) |f_type, f_attrs, i| {
                data[i] = .{
                    .size = @sizeOf(f_type),
                    .size_index = i,
                    .alignment = f_attrs.@"align" orelse @alignOf(f_type),
                };
                big_align = @max(big_align, data[i].alignment);
            }
            const Sort = struct {
                fn lessThan(context: void, lhs: Data, rhs: Data) bool {
                    _ = context;
                    return lhs.alignment > rhs.alignment;
                }
            };
            @setEvalBranchQuota(3 * field_names.len * std.math.log2(field_names.len));
            mem.sort(Data, &data, {}, Sort.lessThan);
            var sizes_bytes: [field_names.len]usize = undefined;
            var field_indexes: [field_names.len]usize = undefined;
            for (data, 0..) |elem, i| {
                sizes_bytes[i] = elem.size;
                field_indexes[i] = elem.size_index;
            }
            break :blk .{
                .bytes = sizes_bytes,
                .fields = field_indexes,
                .big_align = mem.Alignment.fromByteUnits(big_align),
            };
        };

        /// Release all allocated memory.
        pub fn deinit(self: *Self, gpa: Allocator) void {
            gpa.free(self.allocatedBytes());
            self.* = undefined;
        }

        /// The caller owns the returned memory. Empties this MultiArrayList.
        pub fn toOwnedSlice(self: *Self) Slice {
            const result = self.slice();
            self.* = .{};
            return result;
        }

        /// Compute pointers to the start of each field of the array.
        /// If you need to access multiple fields, calling this may
        /// be more efficient than calling `items()` multiple times.
        pub fn slice(self: Self) Slice {
            var result: Slice = .{
                .ptrs = undefined,
                .len = self.len,
                .capacity = self.capacity,
            };
            var ptr: [*]u8 = self.bytes;
            for (sizes.bytes, sizes.fields) |field_size, i| {
                result.ptrs[i] = ptr;
                ptr += field_size * self.capacity;
            }
            return result;
        }

        /// Get the slice of values for a specified field.
        /// If you need multiple fields, consider calling slice()
        /// instead.
        pub fn items(self: Self, comptime field: Field) []FieldType(field) {
            return self.slice().items(field);
        }

        /// Overwrite one array element with new data.
        pub fn set(self: *Self, index: usize, elem: T) void {
            var slices = self.slice();
            slices.set(index, elem);
        }

        /// Obtain all the data for one array element.
        pub fn get(self: Self, index: usize) T {
            return self.slice().get(index);
        }

        pub fn swap(self: Self, a: usize, b: usize) void {
            return self.slice().swap(a, b);
        }

        /// Extend the list by 1 element.
        ///
        /// Allocates more memory as necessary.
        pub fn append(self: *Self, gpa: Allocator, elem: T) Allocator.Error!void {
            try self.ensureUnusedCapacity(gpa, 1);
            self.appendAssumeCapacity(elem);
        }

        /// Extend the list by 1 element.
        ///
        /// Asserts that capacity is sufficient to hold an additional item.
        pub fn appendAssumeCapacity(self: *Self, elem: T) void {
            assert(self.len < self.capacity);
            self.len += 1;
            self.set(self.len - 1, elem);
        }

        /// Extend the list by 1 element.
        ///
        /// If capacity is not sufficient to hold an additional
        /// item, returns `error.OutOfMemory`.
        pub fn appendBounded(self: *Self, elem: T) error{OutOfMemory}!void {
            if (self.capacity - self.len < 1) return error.OutOfMemory;
            return appendAssumeCapacity(self, elem);
        }

        /// Extend the list by 1 element, returning the newly reserved
        /// index with uninitialized data.
        ///
        /// Allocates more memory as necessary.
        pub fn addOne(self: *Self, gpa: Allocator) Allocator.Error!usize {
            try self.ensureUnusedCapacity(gpa, 1);
            return self.addOneAssumeCapacity();
        }

        /// Extend the list by 1 element, returning the newly reserved
        /// index with uninitialized data.
        ///
        /// Asserts that capacity is sufficient to hold an additional item.
        pub fn addOneAssumeCapacity(self: *Self) usize {
            assert(self.len < self.capacity);
            const index = self.len;
            self.len += 1;
            return index;
        }

        /// Extend the list by 1 element, returning the newly reserved
        /// index with uninitialized data.
        ///
        /// If capacity is not sufficient to hold an additional
        /// item, returns `error.OutOfMemory`.
        pub fn addOneBounded(self: *Self) error{OutOfMemory}!usize {
            if (self.capacity - self.len < 1) return error.OutOfMemory;
            return addOneAssumeCapacity(self);
        }

        /// Remove and return the last element from the list, or return `null` if list is empty.
        /// Invalidates pointers to fields of the removed element.
        pub fn pop(self: *Self) ?T {
            if (self.len == 0) return null;
            const val = self.get(self.len - 1);
            self.len -= 1;
            return val;
        }

        /// Inserts an item into the list. Shifts all elements
        /// after and including the specified index back by one and
        /// sets the given index to the specified element.
        ///
        /// Allocates more memory as necessary.
        pub fn insert(self: *Self, gpa: Allocator, index: usize, elem: T) !void {
            try self.ensureUnusedCapacity(gpa, 1);
            self.insertAssumeCapacity(index, elem);
        }

        /// Inserts an item into the list. Shifts all elements
        /// after and including the specified index back by one and
        /// sets the given index to the specified element.
        ///
        /// Asserts that capacity is sufficient to hold an additional item.
        pub fn insertAssumeCapacity(self: *Self, index: usize, elem: T) void {
            assert(self.len < self.capacity);
            assert(index <= self.len);
            self.len += 1;
            const entry = switch (@typeInfo(T)) {
                .@"struct" => elem,
                .@"union" => Elem.fromT(elem),
                else => unreachable,
            };
            const slices = self.slice();
            inline for (field_names, 0..) |field_name, field_index| {
                const field_slice = slices.items(@as(Field, @fromBackingInt(@intCast(field_index))));
                var i: usize = self.len - 1;
                while (i > index) : (i -= 1) {
                    field_slice[i] = field_slice[i - 1];
                }
                field_slice[index] = @field(entry, field_name);
            }
        }

        /// Inserts an item into the list. Shifts all elements
        /// after and including the specified index back by one and
        /// sets the given index to the specified element.
        ///
        /// If capacity is not sufficient to hold an additional
        /// item, returns `error.OutOfMemory`.
        pub fn insertBounded(self: *Self, index: usize, elem: T) error{OutOfMemory}!void {
            if (self.capacity - self.len < 1) return error.OutOfMemory;
            return insertAssumeCapacity(self, index, elem);
        }

        /// Remove the specified item from the list, swapping the last
        /// item in the list into its position. Fast, but does not
        /// retain list ordering.
        pub fn swapRemove(self: *Self, index: usize) void {
            const slices = self.slice();
            inline for (field_names, 0..) |_, i| {
                const field_slice = slices.items(@as(Field, @fromBackingInt(@intCast(i))));
                field_slice[index] = field_slice[self.len - 1];
                field_slice[self.len - 1] = undefined;
            }
            self.len -= 1;
        }

        /// Remove the specified item from the list, shifting items
        /// after it to preserve order.
        pub fn orderedRemove(self: *Self, index: usize) void {
            const slices = self.slice();
            inline for (field_names, 0..) |_, field_index| {
                const field_slice = slices.items(@as(Field, @fromBackingInt(@intCast(field_index))));
                var i = index;
                while (i < self.len - 1) : (i += 1) {
                    field_slice[i] = field_slice[i + 1];
                }
                field_slice[i] = undefined;
            }
            self.len -= 1;
        }

        /// 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 {
            if (sorted_indexes.len == 0) return;
            const slices = self.slice();
            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
                inline for (field_names, 0..) |_, field_index| {
                    const field_slice = slices.items(@fromBackingInt(@intCast(field_index)));
                    @memmove(field_slice[start - shift ..][0..len], field_slice[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.len;
            const len = end - start; // safety checks final `sorted_indexes` are in range
            inline for (field_names, 0..) |_, field_index| {
                const field_slice = slices.items(@fromBackingInt(@intCast(field_index)));
                @memmove(field_slice[start - shift ..][0..len], field_slice[start..][0..len]);
            }
            self.len = end - shift;
        }

        /// Adjust the list's length to `new_len`.
        /// Does not initialize added items, if any.
        pub fn resize(self: *Self, gpa: Allocator, new_len: usize) Allocator.Error!void {
            try self.ensureTotalCapacity(gpa, new_len);
            self.len = new_len;
        }

        /// Attempt to reduce allocated capacity to `new_len`.
        /// If `new_len` is greater than zero, this may fail to reduce the capacity,
        /// but the data remains intact and the length is updated to new_len.
        pub fn shrinkAndFree(self: *Self, gpa: Allocator, new_len: usize) void {
            if (new_len == 0) return clearAndFree(self, gpa);

            assert(new_len <= self.capacity);
            assert(new_len <= self.len);

            const other_bytes = gpa.alignedAlloc(u8, sizes.big_align, capacityInBytes(new_len)) catch {
                const self_slice = self.slice();
                inline for (field_types, 0..) |field_type, i| {
                    if (@sizeOf(field_type) != 0) {
                        const field = @as(Field, @fromBackingInt(@intCast(i)));
                        const dest_slice = self_slice.items(field)[new_len..];
                        // We use memset here for more efficient codegen in safety-checked,
                        // valgrind-enabled builds. Otherwise the valgrind client request
                        // will be repeated for every element.
                        @memset(dest_slice, undefined);
                    }
                }
                self.len = new_len;
                return;
            };
            var other = Self{
                .bytes = other_bytes.ptr,
                .capacity = new_len,
                .len = new_len,
            };
            self.len = new_len;
            const self_slice = self.slice();
            const other_slice = other.slice();
            inline for (field_types, 0..) |field_type, i| {
                if (@sizeOf(field_type) != 0) {
                    const field = @as(Field, @fromBackingInt(@intCast(i)));
                    @memcpy(other_slice.items(field), self_slice.items(field));
                }
            }
            gpa.free(self.allocatedBytes());
            self.* = other;
        }

        pub fn clearAndFree(self: *Self, gpa: Allocator) void {
            gpa.free(self.allocatedBytes());
            self.* = .{};
        }

        /// Reduce length to `new_len`.
        /// Invalidates pointers to elements `items[new_len..]`.
        /// Keeps capacity the same.
        pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
            self.len = new_len;
        }

        /// Invalidates all element pointers.
        pub fn clearRetainingCapacity(self: *Self) void {
            self.len = 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.setCapacity(gpa, growCapacity(new_capacity));
        }

        const init_capacity: comptime_int = init: {
            var max: comptime_int = 1;
            for (field_types) |field_type| max = @max(max, @sizeOf(field_type));
            break :init @max(1, std.atomic.cache_line / max);
        };

        /// Given a lower bound of required memory capacity, returns a larger value
        /// with super-linear growth.
        pub fn growCapacity(minimum: usize) usize {
            return minimum +| (minimum / 2 + init_capacity);
        }

        /// Modify the array so that it can hold at least `additional_count` **more** items.
        /// Invalidates pointers if additional memory is needed.
        pub fn ensureUnusedCapacity(self: *Self, gpa: Allocator, additional_count: usize) Allocator.Error!void {
            return self.ensureTotalCapacity(gpa, self.len + additional_count);
        }

        /// Modify the array so that it can hold exactly `new_capacity` items.
        /// Invalidates pointers if additional memory is needed.
        /// `new_capacity` must be greater or equal to `len`.
        pub fn setCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
            assert(new_capacity >= self.len);
            const new_bytes = try gpa.alignedAlloc(u8, sizes.big_align, capacityInBytes(new_capacity));
            if (self.len == 0) {
                gpa.free(self.allocatedBytes());
                self.bytes = new_bytes.ptr;
                self.capacity = new_capacity;
                return;
            }
            var other = Self{
                .bytes = new_bytes.ptr,
                .capacity = new_capacity,
                .len = self.len,
            };
            const self_slice = self.slice();
            const other_slice = other.slice();
            inline for (field_types, 0..) |field_type, i| {
                if (@sizeOf(field_type) != 0) {
                    const field = @as(Field, @fromBackingInt(@intCast(i)));
                    @memcpy(other_slice.items(field), self_slice.items(field));
                }
            }
            gpa.free(self.allocatedBytes());
            self.* = other;
        }

        /// Create a copy of this list with a new backing store,
        /// using the specified allocator.
        pub fn clone(self: Self, gpa: Allocator) Allocator.Error!Self {
            var result = Self{};
            errdefer result.deinit(gpa);
            try result.ensureTotalCapacity(gpa, self.len);
            result.len = self.len;
            const self_slice = self.slice();
            const result_slice = result.slice();
            inline for (field_types, 0..) |field_type, i| {
                if (@sizeOf(field_type) != 0) {
                    const field = @as(Field, @fromBackingInt(@intCast(i)));
                    @memcpy(result_slice.items(field), self_slice.items(field));
                }
            }
            return result;
        }

        /// `ctx` has the following method:
        /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
        fn sortInternal(self: Self, a: usize, b: usize, ctx: anytype, comptime mode: std.sort.Mode) void {
            const sort_context: struct {
                sub_ctx: @TypeOf(ctx),
                slice: Slice,

                pub fn swap(sc: @This(), a_index: usize, b_index: usize) void {
                    inline for (field_types, 0..) |field_type, i| {
                        if (@sizeOf(field_type) != 0) {
                            const field: Field = @fromBackingInt(@intCast(i));
                            const ptr = sc.slice.items(field);
                            mem.swap(field_type, &ptr[a_index], &ptr[b_index]);
                        }
                    }
                }

                pub fn lessThan(sc: @This(), a_index: usize, b_index: usize) bool {
                    return sc.sub_ctx.lessThan(a_index, b_index);
                }
            } = .{
                .sub_ctx = ctx,
                .slice = self.slice(),
            };

            switch (mode) {
                .stable => mem.sortContext(a, b, sort_context),
                .unstable => mem.sortUnstableContext(a, b, sort_context),
            }
        }

        /// This function guarantees a stable sort, i.e the relative order of equal elements is preserved during sorting.
        /// Read more about stable sorting here: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
        /// If this guarantee does not matter, `sortUnstable` might be a faster alternative.
        /// `ctx` has the following method:
        /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
        pub fn sort(self: Self, ctx: anytype) void {
            self.sortInternal(0, self.len, ctx, .stable);
        }

        /// Sorts only the subsection of items between indices `a` and `b` (excluding `b`)
        /// This function guarantees a stable sort, i.e the relative order of equal elements is preserved during sorting.
        /// Read more about stable sorting here: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
        /// If this guarantee does not matter, `sortSpanUnstable` might be a faster alternative.
        /// `ctx` has the following method:
        /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
        pub fn sortSpan(self: Self, a: usize, b: usize, ctx: anytype) void {
            self.sortInternal(a, b, ctx, .stable);
        }

        /// This function does NOT guarantee a stable sort, i.e the relative order of equal elements may change during sorting.
        /// Due to the weaker guarantees of this function, this may be faster than the stable `sort` method.
        /// Read more about stable sorting here: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
        /// `ctx` has the following method:
        /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
        pub fn sortUnstable(self: Self, ctx: anytype) void {
            self.sortInternal(0, self.len, ctx, .unstable);
        }

        /// Sorts only the subsection of items between indices `a` and `b` (excluding `b`)
        /// This function does NOT guarantee a stable sort, i.e the relative order of equal elements may change during sorting.
        /// Due to the weaker guarantees of this function, this may be faster than the stable `sortSpan` method.
        /// Read more about stable sorting here: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
        /// `ctx` has the following method:
        /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
        pub fn sortSpanUnstable(self: Self, a: usize, b: usize, ctx: anytype) void {
            self.sortInternal(a, b, ctx, .unstable);
        }

        pub fn capacityInBytes(capacity: usize) usize {
            comptime var elem_bytes: usize = 0;
            inline for (sizes.bytes) |size| elem_bytes += size;
            return elem_bytes * capacity;
        }

        fn allocatedBytes(self: Self) []align(sizes.big_align.toByteUnits()) u8 {
            return @alignCast(self.bytes[0..capacityInBytes(self.capacity)]);
        }

        fn FieldType(comptime field: Field) type {
            return @FieldType(Elem, @tagName(field));
        }

        const Entry = entry: {
            var entry_field_names: [field_names.len][]const u8 = undefined;
            var entry_field_types: [field_names.len]type = undefined;
            var entry_field_attrs: [field_names.len]std.builtin.Type.Struct.FieldAttributes = undefined;
            for (sizes.fields, &entry_field_names, &entry_field_types, &entry_field_attrs) |i, *name, *Type, *attrs| {
                name.* = field_names[i] ++ "_ptr";
                Type.* = *field_types[i];
                attrs.* = .{
                    .@"comptime" = field_attrs[i].@"comptime",
                    .@"align" = field_attrs[i].@"align",
                };
            }
            break :entry @Struct(.@"extern", null, &entry_field_names, &entry_field_types, &entry_field_attrs);
        };
        /// This function is used in the debugger pretty formatters in lib/lldb/ to fetch the
        /// child field order and entry type to facilitate fancy debug printing for this type.
        fn dbHelper(self: *Self, child: *Elem, field: *Field, entry: *Entry) void {
            _ = self;
            _ = child;
            _ = field;
            _ = entry;
        }

        comptime {
            if (builtin.zig_backend == .stage2_llvm and !builtin.strip_debug_info) {
                _ = &dbHelper;
                _ = &Slice.dbHelper;
            }
        }
    };
}

test "basic usage" {
    const ally = testing.allocator;

    const Foo = struct {
        a: u32,
        b: []const u8,
        c: u8,
    };

    var list: MultiArrayList(Foo) = .empty;
    defer list.deinit(ally);

    try testing.expectEqual(@as(usize, 0), list.items(.a).len);

    try list.ensureTotalCapacity(ally, 2);

    list.appendAssumeCapacity(.{
        .a = 1,
        .b = "foobar",
        .c = 'a',
    });

    try list.appendBounded(.{
        .a = 2,
        .b = "zigzag",
        .c = 'b',
    });

    try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 1, 2 });
    try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'a', 'b' });

    try testing.expectEqual(@as(usize, 2), list.items(.b).len);
    try testing.expectEqualStrings("foobar", list.items(.b)[0]);
    try testing.expectEqualStrings("zigzag", list.items(.b)[1]);

    try list.append(ally, .{
        .a = 3,
        .b = "fizzbuzz",
        .c = 'c',
    });

    try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 1, 2, 3 });
    try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'a', 'b', 'c' });

    try testing.expectEqual(@as(usize, 3), list.items(.b).len);
    try testing.expectEqualStrings("foobar", list.items(.b)[0]);
    try testing.expectEqualStrings("zigzag", list.items(.b)[1]);
    try testing.expectEqualStrings("fizzbuzz", list.items(.b)[2]);

    // Add 6 more things to force a capacity increase.
    var i: usize = 0;
    while (i < 6) : (i += 1) {
        try list.append(ally, .{
            .a = @as(u32, @intCast(4 + i)),
            .b = "whatever",
            .c = @as(u8, @intCast('d' + i)),
        });
    }

    try testing.expectEqualSlices(
        u32,
        &[_]u32{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
        list.items(.a),
    );
    try testing.expectEqualSlices(
        u8,
        &[_]u8{ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i' },
        list.items(.c),
    );

    list.shrinkAndFree(ally, 3);

    try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 1, 2, 3 });
    try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'a', 'b', 'c' });

    list.swap(0, 2);
    try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 3, 2, 1 });
    try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'c', 'b', 'a' });
    list.swap(2, 1);
    try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 3, 1, 2 });
    try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'c', 'a', 'b' });
    list.swap(2, 0);
    try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 2, 1, 3 });
    try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'b', 'a', 'c' });
    list.swap(0, 1);
    try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 1, 2, 3 });
    try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'a', 'b', 'c' });

    try testing.expectEqual(@as(usize, 3), list.items(.b).len);
    try testing.expectEqualStrings("foobar", list.items(.b)[0]);
    try testing.expectEqualStrings("zigzag", list.items(.b)[1]);
    try testing.expectEqualStrings("fizzbuzz", list.items(.b)[2]);

    try testing.expectError(error.OutOfMemory, list.addOneBounded());

    list.set(try list.addOne(ally), .{
        .a = 4,
        .b = "xnopyt",
        .c = 'd',
    });
    try testing.expectEqualStrings("xnopyt", list.pop().?.b);
    try testing.expectEqual(@as(?u8, 'c'), if (list.pop()) |elem| elem.c else null);
    try testing.expectEqual(@as(u32, 2), list.pop().?.a);
    try testing.expectEqual(@as(u8, 'a'), list.pop().?.c);
    try testing.expectEqual(@as(?Foo, null), list.pop());

    list.clearRetainingCapacity();
    try testing.expectEqual(0, list.len);
    try testing.expect(list.capacity > 0);

    list.clearAndFree(ally);
    try testing.expectEqual(0, list.len);
    try testing.expectEqual(0, list.capacity);
}

// This was observed to fail on aarch64 with LLVM 11, when the capacityInBytes
// function used the @reduce code path.
test "regression test for @reduce bug" {
    const ally = testing.allocator;
    var list: MultiArrayList(struct {
        tag: std.zig.Token.Tag,
        start: u32,
    }) = .empty;
    defer list.deinit(ally);

    try list.ensureTotalCapacity(ally, 20);

    try list.append(ally, .{ .tag = .keyword_const, .start = 0 });
    try list.append(ally, .{ .tag = .identifier, .start = 6 });
    try list.append(ally, .{ .tag = .equal, .start = 10 });
    try list.append(ally, .{ .tag = .builtin, .start = 12 });
    try list.append(ally, .{ .tag = .l_paren, .start = 19 });
    try list.append(ally, .{ .tag = .string_literal, .start = 20 });
    try list.append(ally, .{ .tag = .r_paren, .start = 25 });
    try list.append(ally, .{ .tag = .semicolon, .start = 26 });
    try list.append(ally, .{ .tag = .keyword_pub, .start = 29 });
    try list.append(ally, .{ .tag = .keyword_fn, .start = 33 });
    try list.append(ally, .{ .tag = .identifier, .start = 36 });
    try list.append(ally, .{ .tag = .l_paren, .start = 40 });
    try list.append(ally, .{ .tag = .r_paren, .start = 41 });
    try list.append(ally, .{ .tag = .identifier, .start = 43 });
    try list.append(ally, .{ .tag = .bang, .start = 51 });
    try list.append(ally, .{ .tag = .identifier, .start = 52 });
    try list.append(ally, .{ .tag = .l_brace, .start = 57 });
    try list.append(ally, .{ .tag = .identifier, .start = 63 });
    try list.append(ally, .{ .tag = .period, .start = 66 });
    try list.append(ally, .{ .tag = .identifier, .start = 67 });
    try list.append(ally, .{ .tag = .period, .start = 70 });
    try list.append(ally, .{ .tag = .identifier, .start = 71 });
    try list.append(ally, .{ .tag = .l_paren, .start = 75 });
    try list.append(ally, .{ .tag = .string_literal, .start = 76 });
    try list.append(ally, .{ .tag = .comma, .start = 113 });
    try list.append(ally, .{ .tag = .period, .start = 115 });
    try list.append(ally, .{ .tag = .l_brace, .start = 116 });
    try list.append(ally, .{ .tag = .r_brace, .start = 117 });
    try list.append(ally, .{ .tag = .r_paren, .start = 118 });
    try list.append(ally, .{ .tag = .semicolon, .start = 119 });
    try list.append(ally, .{ .tag = .r_brace, .start = 121 });
    try list.append(ally, .{ .tag = .eof, .start = 123 });

    const tags = list.items(.tag);
    try testing.expectEqual(tags[1], .identifier);
    try testing.expectEqual(tags[2], .equal);
    try testing.expectEqual(tags[3], .builtin);
    try testing.expectEqual(tags[4], .l_paren);
    try testing.expectEqual(tags[5], .string_literal);
    try testing.expectEqual(tags[6], .r_paren);
    try testing.expectEqual(tags[7], .semicolon);
    try testing.expectEqual(tags[8], .keyword_pub);
    try testing.expectEqual(tags[9], .keyword_fn);
    try testing.expectEqual(tags[10], .identifier);
    try testing.expectEqual(tags[11], .l_paren);
    try testing.expectEqual(tags[12], .r_paren);
    try testing.expectEqual(tags[13], .identifier);
    try testing.expectEqual(tags[14], .bang);
    try testing.expectEqual(tags[15], .identifier);
    try testing.expectEqual(tags[16], .l_brace);
    try testing.expectEqual(tags[17], .identifier);
    try testing.expectEqual(tags[18], .period);
    try testing.expectEqual(tags[19], .identifier);
    try testing.expectEqual(tags[20], .period);
    try testing.expectEqual(tags[21], .identifier);
    try testing.expectEqual(tags[22], .l_paren);
    try testing.expectEqual(tags[23], .string_literal);
    try testing.expectEqual(tags[24], .comma);
    try testing.expectEqual(tags[25], .period);
    try testing.expectEqual(tags[26], .l_brace);
    try testing.expectEqual(tags[27], .r_brace);
    try testing.expectEqual(tags[28], .r_paren);
    try testing.expectEqual(tags[29], .semicolon);
    try testing.expectEqual(tags[30], .r_brace);
    try testing.expectEqual(tags[31], .eof);
}

test "ensure capacity on empty list" {
    const ally = testing.allocator;

    const Foo = struct {
        a: u32,
        b: u8,
    };

    var list: MultiArrayList(Foo) = .empty;
    defer list.deinit(ally);

    try list.ensureTotalCapacity(ally, 2);
    list.appendAssumeCapacity(.{ .a = 1, .b = 2 });
    list.appendAssumeCapacity(.{ .a = 3, .b = 4 });

    try testing.expectEqualSlices(u32, &[_]u32{ 1, 3 }, list.items(.a));
    try testing.expectEqualSlices(u8, &[_]u8{ 2, 4 }, list.items(.b));

    list.len = 0;
    list.appendAssumeCapacity(.{ .a = 5, .b = 6 });
    list.appendAssumeCapacity(.{ .a = 7, .b = 8 });

    try testing.expectEqualSlices(u32, &[_]u32{ 5, 7 }, list.items(.a));
    try testing.expectEqualSlices(u8, &[_]u8{ 6, 8 }, list.items(.b));

    list.len = 0;
    try list.ensureTotalCapacity(ally, 16);

    list.appendAssumeCapacity(.{ .a = 9, .b = 10 });
    list.appendAssumeCapacity(.{ .a = 11, .b = 12 });

    try testing.expectEqualSlices(u32, &[_]u32{ 9, 11 }, list.items(.a));
    try testing.expectEqualSlices(u8, &[_]u8{ 10, 12 }, list.items(.b));
}

test "insert elements" {
    const ally = testing.allocator;

    const Foo = struct {
        a: u8,
        b: u32,
    };

    var list = try MultiArrayList(Foo).initCapacity(ally, 2);
    defer list.deinit(ally);

    try list.insertBounded(0, .{ .a = 1, .b = 2 });
    list.insertAssumeCapacity(1, .{ .a = 2, .b = 3 });
    try list.insert(ally, 0, .{ .a = 3, .b = 4 });

    try testing.expectEqualSlices(u8, &[_]u8{ 3, 1, 2 }, list.items(.a));
    try testing.expectEqualSlices(u32, &[_]u32{ 4, 2, 3 }, list.items(.b));
}

test "initCapacity" {
    const gpa = testing.allocator;

    var list = try MultiArrayList(struct { a: u8, b: u32 }).initCapacity(gpa, 404);
    defer list.deinit(gpa);

    try testing.expectEqual(0, list.len);
    try testing.expectEqual(404, list.capacity);
}

test "union" {
    const ally = testing.allocator;

    const Foo = union(enum) {
        a: u32,
        b: []const u8,
    };

    var list: MultiArrayList(Foo) = .empty;
    defer list.deinit(ally);

    try testing.expectEqual(@as(usize, 0), list.items(.tags).len);

    try list.ensureTotalCapacity(ally, 3);

    list.appendAssumeCapacity(.{ .a = 1 });
    list.appendAssumeCapacity(.{ .b = "zigzag" });

    try testing.expectEqualSlices(meta.Tag(Foo), list.items(.tags), &.{ .a, .b });
    try testing.expectEqual(@as(usize, 2), list.items(.tags).len);

    list.appendAssumeCapacity(.{ .b = "foobar" });
    try testing.expectEqualStrings("zigzag", list.items(.data)[1].b);
    try testing.expectEqualStrings("foobar", list.items(.data)[2].b);

    // Add 6 more things to force a capacity increase.
    for (0..6) |i| {
        try list.append(ally, .{ .a = @as(u32, @intCast(4 + i)) });
    }

    try testing.expectEqualSlices(
        meta.Tag(Foo),
        &.{ .a, .b, .b, .a, .a, .a, .a, .a, .a },
        list.items(.tags),
    );
    try testing.expectEqual(Foo{ .a = 1 }, list.get(0));
    try testing.expectEqual(Foo{ .b = "zigzag" }, list.get(1));
    try testing.expectEqual(Foo{ .b = "foobar" }, list.get(2));
    try testing.expectEqual(Foo{ .a = 4 }, list.get(3));
    try testing.expectEqual(Foo{ .a = 5 }, list.get(4));
    try testing.expectEqual(Foo{ .a = 6 }, list.get(5));
    try testing.expectEqual(Foo{ .a = 7 }, list.get(6));
    try testing.expectEqual(Foo{ .a = 8 }, list.get(7));
    try testing.expectEqual(Foo{ .a = 9 }, list.get(8));

    list.shrinkAndFree(ally, 3);

    try testing.expectEqual(@as(usize, 3), list.items(.tags).len);
    try testing.expectEqualSlices(meta.Tag(Foo), list.items(.tags), &.{ .a, .b, .b });

    try testing.expectEqual(Foo{ .a = 1 }, list.get(0));
    try testing.expectEqual(Foo{ .b = "zigzag" }, list.get(1));
    try testing.expectEqual(Foo{ .b = "foobar" }, list.get(2));
}

test "sorting a span" {
    var list: MultiArrayList(struct { score: u32, chr: u8 }) = .empty;
    defer list.deinit(testing.allocator);

    try list.ensureTotalCapacity(testing.allocator, 42);
    for (
        // zig fmt: off
        [42]u8{ 'b', 'a', 'c', 'a', 'b', 'c', 'b', 'c', 'b', 'a', 'b', 'a', 'b', 'c', 'b', 'a', 'a', 'c', 'c', 'a', 'c', 'b', 'a', 'c', 'a', 'b', 'b', 'c', 'c', 'b', 'a', 'b', 'a', 'b', 'c', 'b', 'a', 'a', 'c', 'c', 'a', 'c' },
        [42]u32{ 1,   1,   1,   2,   2,   2,   3,   3,   4,   3,   5,   4,   6,   4,   7,   5,   6,   5,   6,   7,   7,   8,   8,   8,   9,   9,  10,   9,  10,  11,  10,  12,  11,  13,  11,  14,  12,  13,  12,  13,  14,  14 },
        // zig fmt: on
    ) |chr, score| {
        list.appendAssumeCapacity(.{ .chr = chr, .score = score });
    }

    const sliced = list.slice();
    list.sortSpan(6, 21, struct {
        chars: []const u8,

        fn lessThan(ctx: @This(), a: usize, b: usize) bool {
            return ctx.chars[a] < ctx.chars[b];
        }
    }{ .chars = sliced.items(.chr) });

    var i: u32 = undefined;
    var j: u32 = 6;
    var c: u8 = 'a';

    while (j < 21) {
        i = j;
        j += 5;
        var n: u32 = 3;
        for (sliced.items(.chr)[i..j], sliced.items(.score)[i..j]) |chr, score| {
            try testing.expectEqual(score, n);
            try testing.expectEqual(chr, c);
            n += 1;
        }
        c += 1;
    }
}

test "0 sized struct field" {
    const ally = testing.allocator;

    const Foo = struct {
        a: u0,
        b: f32,
    };

    var list: MultiArrayList(Foo) = .empty;
    defer list.deinit(ally);

    try testing.expectEqualSlices(u0, &[_]u0{}, list.items(.a));
    try testing.expectEqualSlices(f32, &[_]f32{}, list.items(.b));

    try list.append(ally, .{ .a = 0, .b = 42.0 });
    try testing.expectEqualSlices(u0, &[_]u0{0}, list.items(.a));
    try testing.expectEqualSlices(f32, &[_]f32{42.0}, list.items(.b));

    try list.insert(ally, 0, .{ .a = 0, .b = -1.0 });
    try testing.expectEqualSlices(u0, &[_]u0{ 0, 0 }, list.items(.a));
    try testing.expectEqualSlices(f32, &[_]f32{ -1.0, 42.0 }, list.items(.b));

    list.swapRemove(list.len - 1);
    try testing.expectEqualSlices(u0, &[_]u0{0}, list.items(.a));
    try testing.expectEqualSlices(f32, &[_]f32{-1.0}, list.items(.b));
}

test "0 sized struct" {
    const ally = testing.allocator;

    const Foo = struct {
        a: u0,
    };

    var list: MultiArrayList(Foo) = .empty;
    defer list.deinit(ally);

    try testing.expectEqualSlices(u0, &[_]u0{}, list.items(.a));

    try list.append(ally, .{ .a = 0 });
    try testing.expectEqualSlices(u0, &[_]u0{0}, list.items(.a));

    try list.insert(ally, 0, .{ .a = 0 });
    try testing.expectEqualSlices(u0, &[_]u0{ 0, 0 }, list.items(.a));

    list.swapRemove(list.len - 1);
    try testing.expectEqualSlices(u0, &[_]u0{0}, list.items(.a));
}

test "struct with many fields" {
    const ManyFields = struct {
        fn Type(count: comptime_int) type {
            @setEvalBranchQuota(50000);
            var field_names: [count][]const u8 = undefined;
            for (&field_names, 0..) |*n, i| n.* = std.fmt.comptimePrint("a{d}", .{i});
            return @Struct(.@"extern", null, &field_names, &@splat(u32), &@splat(.{}));
        }

        fn doTest(ally: std.mem.Allocator, count: comptime_int) !void {
            var list: MultiArrayList(Type(count)) = .empty;
            defer list.deinit(ally);

            try list.resize(ally, 1);
            list.items(.a0)[0] = 42;
        }
    };

    try ManyFields.doTest(testing.allocator, 25);
    try ManyFields.doTest(testing.allocator, 50);
    try ManyFields.doTest(testing.allocator, 100);
    try ManyFields.doTest(testing.allocator, 200);
}

test "orderedRemoveMany" {
    const gpa = testing.allocator;

    var list: MultiArrayList(struct { x: usize }) = .empty;
    defer list.deinit(gpa);

    for (0..10) |n| {
        try list.append(gpa, .{ .x = n });
    }

    list.orderedRemoveMany(&.{ 1, 5, 5, 7, 9 });
    try testing.expectEqualSlices(usize, &.{ 0, 2, 3, 4, 6, 8 }, list.items(.x));

    list.orderedRemoveMany(&.{0});
    try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, list.items(.x));

    list.orderedRemoveMany(&.{});
    try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, list.items(.x));

    list.orderedRemoveMany(&.{ 1, 2, 3, 4 });
    try testing.expectEqualSlices(usize, &.{2}, list.items(.x));

    list.orderedRemoveMany(&.{0});
    try testing.expectEqualSlices(usize, &.{}, list.items(.x));
}