std.multi_array_list.Allocator
别名
别名目标 std.mem.Allocator
std.multi_array_list.assert
别名
别名目标 std.debug.assert
std.multi_array_list.builtin
常量
std.multi_array_list.doTest
函数
fn doTest(ally: std.mem.Allocator, count: comptime_int) !void
参数
std.multi_array_list.lessThan
函数
fn lessThan(ctx: @This(), a: usize, b: usize) bool
参数
ctx: @This()
a: usize
b: usize
std.multi_array_list.mem
别名
别名目标 std.mem
std.multi_array_list.meta
别名
别名目标 std.meta
std.multi_array_list.MultiArrayList
类型函数
MultiArrayList 存储结构体或带标签联合体类型的列表。
它不存储单一元素列表,而是为结构体的各字段分别存储列表,或分别存储标签列表与裸联合体列表。
若结构体或联合体存在填充,可由此节省内存;若计算只需部分字段或仅需标签,还能改善缓存利用率。
访问字段的主要接口为 slice(),它计算每个字段数组的起始指针。可在切片上调用 .items(.<field_name>),取得字段值的切片。
对于联合体,可调用 .items(.tags) 或 .items(.data)。
pub fn MultiArrayList(comptime T: type) type
参数
T: type
字段
bytes: [*]u8 = undefined此指针始终按 sizes.big_align 边界对齐;类型中不声明该要求,
以免 MultiArrayList(T) 依赖 T 的对齐,因为这
可能导致依赖循环。参见 allocatedBytes,它通过 @alignCast 将该指针转换为
正确类型。
len: usize = 0
capacity: usize = 0
emptyinitCapacityElemFieldSliceSelffield_namesfield_typesfield_attrssizesdeinittoOwnedSlicesliceitemssetgetswapappendappendAssumeCapacityappendBoundedaddOneaddOneAssumeCapacityaddOneBoundedpopinsertinsertAssumeCapacityinsertBoundedswapRemoveorderedRemoveorderedRemoveManyresizeshrinkAndFreeclearAndFreeshrinkRetainingCapacityclearRetainingCapacityensureTotalCapacityinit_capacitygrowCapacityensureUnusedCapacitysetCapacityclonesortInternalsortsortSpansortUnstablesortSpanUnstablecapacityInBytesallocatedBytesFieldTypeEntrydbHelper
std.multi_array_list.MultiArrayList.addOne
函数
将列表扩展 1 个元素,返回新预留的 索引,其数据未初始化。
必要时分配更多内存。
pub fn addOne(self: *Self, gpa: Allocator) Allocator.Error!usize
参数
错误
- OutOfMemory
std.multi_array_list.MultiArrayList.addOneAssumeCapacity
函数
将列表扩展一个元素,返回新预留位置的索引,其数据未初始化。
断言容量足以容纳一个额外项目。
pub fn addOneAssumeCapacity(self: *Self) usize
参数
self: *Self
std.multi_array_list.MultiArrayList.addOneBounded
函数
将列表扩展 1 个元素,返回新保留的 索引,其数据未初始化。
若容量不足以容纳一个新增
条目,则返回 error.OutOfMemory。
pub fn addOneBounded(self: *Self) error{OutOfMemory}!usize
参数
self: *Self
错误
- OutOfMemory
std.multi_array_list.MultiArrayList.allocatedBytes
函数
fn allocatedBytes(self: Self) []align(sizes.big_align.toByteUnits()) u8
参数
self: Self
std.multi_array_list.MultiArrayList.append
函数
将列表扩展 1 个元素。
必要时分配更多内存。
pub fn append(self: *Self, gpa: Allocator, elem: T) Allocator.Error!void
参数
错误
- OutOfMemory
std.multi_array_list.MultiArrayList.appendAssumeCapacity
函数
将列表增加 1 个元素。
断言容量足以容纳一个额外元素。
pub fn appendAssumeCapacity(self: *Self, elem: T) void
参数
self: *Self
elem: T
std.multi_array_list.MultiArrayList.appendBounded
函数
将列表扩展一个元素。
若容量不足以容纳新增元素,
返回 error.OutOfMemory。
pub fn appendBounded(self: *Self, elem: T) error{OutOfMemory}!void
参数
self: *Self
elem: T
错误
- OutOfMemory
std.multi_array_list.MultiArrayList.capacityInBytes
函数
pub fn capacityInBytes(capacity: usize) usize
参数
capacity: usize
std.multi_array_list.MultiArrayList.clearAndFree
函数
pub fn clearAndFree(self: *Self, gpa: Allocator) void
参数
std.multi_array_list.MultiArrayList.clearRetainingCapacity
函数
使所有元素指针失效。
pub fn clearRetainingCapacity(self: *Self) void
参数
self: *Self
std.multi_array_list.MultiArrayList.clone
函数
使用指定分配器, 以新的底层存储创建此列表的副本。
pub fn clone(self: Self, gpa: Allocator) Allocator.Error!Self
参数
错误
- OutOfMemory
std.multi_array_list.MultiArrayList.dbHelper
函数
lib/lldb/ 中的调试器美化格式器使用此函数获取 子字段顺序与条目类型,以支持此类型的美化调试输出。
fn dbHelper(self: *Self, child: *Elem, field: *Field, entry: *Entry) void
参数
std.multi_array_list.MultiArrayList.deinit
函数
释放全部已分配内存。
pub fn deinit(self: *Self, gpa: Allocator) void
参数
std.multi_array_list.MultiArrayList.Elem
类型
std.multi_array_list.MultiArrayList.Elem.Bare
类型
std.multi_array_list.MultiArrayList.Elem.fromT
函数
pub fn fromT(outer: T) @This()
参数
outer: T
std.multi_array_list.MultiArrayList.Elem.Tag
常量
std.multi_array_list.MultiArrayList.Elem.toT
函数
pub fn toT(tag: Tag, bare: Bare) T
参数
std.multi_array_list.MultiArrayList.empty
常量
Self
std.multi_array_list.MultiArrayList.ensureTotalCapacity
函数
修改数组,使其至少可容纳 new_capacity 个条目。
采用超线性增长,以实现均摊 O(1) 的追加操作。
如果需要额外内存,则使元素指针失效。
pub fn ensureTotalCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void
参数
错误
- OutOfMemory
std.multi_array_list.MultiArrayList.ensureUnusedCapacity
函数
调整数组,使其至少可再容纳 additional_count 个元素。
如果需要额外内存,指针将失效。
pub fn ensureUnusedCapacity(self: *Self, gpa: Allocator, additional_count: usize) Allocator.Error!void
参数
错误
- OutOfMemory
std.multi_array_list.MultiArrayList.Entry
常量
std.multi_array_list.MultiArrayList.Field
类型
std.multi_array_list.MultiArrayList.field_attrs
常量
std.multi_array_list.MultiArrayList.field_names
常量
std.multi_array_list.MultiArrayList.field_types
常量
std.multi_array_list.MultiArrayList.FieldType
类型函数
fn FieldType(comptime field: Field) type
参数
field: Field
std.multi_array_list.MultiArrayList.get
函数
获取一个数组元素的所有数据。
pub fn get(self: Self, index: usize) T
参数
self: Self
index: usize
std.multi_array_list.MultiArrayList.growCapacity
函数
给定所需内存容量的下限,返回按超线性 增长得到的更大值。
pub fn growCapacity(minimum: usize) usize
参数
minimum: usize
std.multi_array_list.MultiArrayList.init_capacity
常量
comptime_int
std.multi_array_list.MultiArrayList.initCapacity
函数
初始化并分配恰好可容纳 num 个元素的容量。
使用 deinit 或 toOwnedSlice 反初始化。
pub fn initCapacity(gpa: Allocator, num: usize) Allocator.Error!Self
参数
gpa: Allocator
num: usize
错误
- OutOfMemory
std.multi_array_list.MultiArrayList.insert
函数
向列表插入一个元素。将指定索引及其后 的所有元素向后移动一位, 并将指定索引设置为所给元素。
按需分配更多内存。
pub fn insert(self: *Self, gpa: Allocator, index: usize, elem: T) !void
参数
std.multi_array_list.MultiArrayList.insertAssumeCapacity
函数
向列表插入一个元素。将指定索引及其后 的所有元素向后移动一位, 并将指定索引设置为所给元素。
断言容量足以容纳一个新增元素。
pub fn insertAssumeCapacity(self: *Self, index: usize, elem: T) void
参数
std.multi_array_list.MultiArrayList.insertBounded
函数
向列表插入一个元素。将指定索引及其后 的所有元素向后移动一位, 并将指定索引设置为所给元素。
若容量不足以容纳一个新增元素,
返回 error.OutOfMemory。
pub fn insertBounded(self: *Self, index: usize, elem: T) error{OutOfMemory}!void
参数
错误
- OutOfMemory
std.multi_array_list.MultiArrayList.items
函数
获取指定字段的值切片。 如果需要多个字段,考虑改为 调用 slice()。
pub fn items(self: Self, comptime field: Field) []FieldType(field)
参数
std.multi_array_list.MultiArrayList.orderedRemove
函数
从列表中移除指定项目,并移动其后的项目以保持顺序。
pub fn orderedRemove(self: *Self, index: usize) void
参数
self: *Self
index: usize
std.multi_array_list.MultiArrayList.orderedRemoveMany
函数
移除 sorted_indexes 索引的元素。这些待移除索引
对应删除前的数组列表。
断言:
- 每个待移除索引都在范围内。
- 待移除索引按升序排列。
允许 sorted_indexes 中存在重复项。
此操作的时间复杂度为 O(N)。
使首个被删除索引之后的元素指针失效。
pub fn orderedRemoveMany(self: *Self, sorted_indexes: []const usize) void
参数
self: *Self
sorted_indexes: []const usize
std.multi_array_list.MultiArrayList.pop
函数
从列表移除并返回最后一个元素;若列表为空则返回 null。
使指向被移除元素字段的指针失效。
pub fn pop(self: *Self) ?T
参数
self: *Self
std.multi_array_list.MultiArrayList.resize
函数
将列表长度调整为 new_len。
不会初始化新增项目。
pub fn resize(self: *Self, gpa: Allocator, new_len: usize) Allocator.Error!void
参数
错误
- OutOfMemory
std.multi_array_list.MultiArrayList.Self
别名
std.multi_array_list.MultiArrayList.set
函数
用新数据覆盖一个数组元素。
pub fn set(self: *Self, index: usize, elem: T) void
参数
std.multi_array_list.MultiArrayList.setCapacity
函数
修改数组,使其恰好可容纳 new_capacity 个条目。
如果需要额外内存,则使指针失效。
new_capacity 必须大于或等于 len。
pub fn setCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void
参数
错误
- OutOfMemory
std.multi_array_list.MultiArrayList.shrinkAndFree
函数
尝试将已分配容量缩减为 new_len。
若 new_len 大于零,则可能无法缩减容量,
但数据保持完整,长度会更新为 new_len。
pub fn shrinkAndFree(self: *Self, gpa: Allocator, new_len: usize) void
参数
std.multi_array_list.MultiArrayList.shrinkRetainingCapacity
函数
将长度缩减为 new_len。
指向元素 items[new_len..] 的指针会失效。
容量保持不变。
pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void
参数
self: *Self
new_len: usize
std.multi_array_list.MultiArrayList.sizes
常量
sizes.bytes 是各 T 字段 @sizeOf 的数组,按对齐要求降序排列。
sizes.fields 数组将 sizes.bytes 的数组索引映射为字段索引。
sizes.big_align 为分配的整体对齐要求,等于各字段对齐要求的最大值。
std.multi_array_list.MultiArrayList.sizes.lessThan
函数
fn lessThan(context: void, lhs: Data, rhs: Data) bool
参数
context: void
lhs: Data
rhs: Data
std.multi_array_list.MultiArrayList.slice
函数
计算指向数组每个字段起始位置的指针。
若需访问多个字段,调用此函数可能比
多次调用 items() 更高效。
pub fn slice(self: Self) Slice
参数
self: Self
std.multi_array_list.MultiArrayList.Slice
容器
MultiArrayList.Slice 包含列表各字段起始指针的缓存。 为减小列表的内存大小,通常不存储这些指针。 若要访问多个字段,应先调用 slice() 计算指针,再从该切片取得各字段数组。
字段
ptrs: [field_names.len][*]u8此数组以字段索引为下标; 可对 Field 枚举调用 @intFromEnum() 获取该索引。
len: usize
capacity: usize
std.multi_array_list.MultiArrayList.Slice.dbHelper
函数
lib/lldb/ 中的调试器美化格式器使用此函数获取 子字段顺序与条目类型,以支持此类型的美化调试输出。
fn dbHelper(self: *Slice, child: *Elem, field: *Field, entry: *Entry) void
参数
std.multi_array_list.MultiArrayList.Slice.deinit
函数
pub fn deinit(self: *Slice, gpa: Allocator) void
参数
std.multi_array_list.MultiArrayList.Slice.empty
常量
Slice
std.multi_array_list.MultiArrayList.Slice.get
函数
pub fn get(self: Slice, index: usize) T
参数
self: Slice
index: usize
std.multi_array_list.MultiArrayList.Slice.items
函数
pub fn items(self: Slice, comptime field: Field) []FieldType(field)
参数
std.multi_array_list.MultiArrayList.Slice.set
函数
pub fn set(self: *Slice, index: usize, elem: T) void
参数
std.multi_array_list.MultiArrayList.Slice.subslice
函数
返回表示 s 中一段元素范围的 Slice,类似 arr[off..len]。
对返回的 Slice 调用 deinit 或 toMultiArrayList 属于非法操作。
断言 off + len <= s.len。
pub fn subslice(s: Slice, off: usize, len: usize) Slice
参数
std.multi_array_list.MultiArrayList.Slice.swap
函数
pub fn swap(self: Slice, a: usize, b: usize) void
参数
std.multi_array_list.MultiArrayList.Slice.toMultiArrayList
函数
pub fn toMultiArrayList(self: Slice) Self
参数
self: Slice
std.multi_array_list.MultiArrayList.sort
函数
此函数保证稳定排序,即排序时保留相等元素的相对顺序。
稳定排序的更多说明:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
如果不需要此保证,sortUnstable 可能更快。
ctx 具有以下方法:
fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool
pub fn sort(self: Self, ctx: anytype) void
参数
self: Self
std.multi_array_list.MultiArrayList.sortInternal
函数
ctx 具有以下方法:
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
参数
std.multi_array_list.MultiArrayList.sortInternal.lessThan
函数
pub fn lessThan(sc: @This(), a_index: usize, b_index: usize) bool
参数
sc: @This()
a_index: usize
b_index: usize
std.multi_array_list.MultiArrayList.sortInternal.swap
函数
pub fn swap(sc: @This(), a_index: usize, b_index: usize) void
参数
sc: @This()
a_index: usize
b_index: usize
std.multi_array_list.MultiArrayList.sortSpan
函数
仅对索引 a 和 b 之间、不含 b 的元素子区间排序。
保证稳定排序,即排序时保留相等元素的相对顺序。
稳定排序的更多说明:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
若不需要此保证,sortSpanUnstable 可能更快。
ctx 具有以下方法:
fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool
pub fn sortSpan(self: Self, a: usize, b: usize, ctx: anytype) void
参数
std.multi_array_list.MultiArrayList.sortSpanUnstable
函数
仅排序索引 a 与 b 之间的元素子区间,不包含 b。
此函数不保证稳定排序,即相等元素的相对顺序可能在排序期间改变。
由于保证较弱,此函数可能比稳定的 sortSpan 方法更快。
稳定排序的详细说明:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
ctx 具有以下方法:
fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool
pub fn sortSpanUnstable(self: Self, a: usize, b: usize, ctx: anytype) void
参数
std.multi_array_list.MultiArrayList.sortUnstable
函数
此函数不保证稳定排序,即相等元素的相对顺序可能在排序期间改变。
由于保证较弱,此函数可能比稳定的 sort 方法更快。
稳定排序的详细说明:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
ctx 具有以下方法:
fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool
pub fn sortUnstable(self: Self, ctx: anytype) void
参数
self: Self
std.multi_array_list.MultiArrayList.swap
函数
pub fn swap(self: Self, a: usize, b: usize) void
参数
std.multi_array_list.MultiArrayList.swapRemove
函数
从列表中移除指定项,将列表最后一项 交换到其位置。速度快,但不 保持列表顺序。
pub fn swapRemove(self: *Self, index: usize) void
参数
self: *Self
index: usize
std.multi_array_list.MultiArrayList.toOwnedSlice
函数
调用方拥有返回的内存。清空此 MultiArrayList。
pub fn toOwnedSlice(self: *Self) Slice
参数
self: *Self
std.multi_array_list.std
别名
别名目标 std
std.multi_array_list.testing
别名
别名目标 std.testing
std.multi_array_list.Type
类型函数
fn Type(count: comptime_int) type
参数
count: comptime_int
源码
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;
/// MultiArrayList 存储结构体或带标签联合体类型的列表。
/// 它不存储单一元素列表,而是为结构体的各字段分别存储列表,或分别存储标签列表与裸联合体列表。
/// 若结构体或联合体存在填充,可由此节省内存;若计算只需部分字段或仅需标签,还能改善缓存利用率。
/// 访问字段的主要接口为 `slice()`,它计算每个字段数组的起始指针。可在切片上调用 `.items(.<field_name>)`,取得字段值的切片。
/// 对于联合体,可调用 `.items(.tags)` 或 `.items(.data)`。
///
///
///
///
///
///
pub fn MultiArrayList(comptime T: type) type {
return struct {
/// 此指针始终按 `sizes.big_align` 边界对齐;类型中不声明该要求,
/// 以免 `MultiArrayList(T)` 依赖 `T` 的对齐,因为这
/// 可能导致依赖循环。参见 `allocatedBytes`,它通过 `@alignCast` 将该指针转换为
/// 正确类型。
bytes: [*]u8 = undefined,
len: usize = 0,
capacity: usize = 0,
pub const empty: Self = .{
.bytes = undefined,
.len = 0,
.capacity = 0,
};
/// 初始化并分配恰好可容纳 `num` 个元素的容量。
/// 使用 `deinit` 或 `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);
/// MultiArrayList.Slice 包含列表各字段起始指针的缓存。
/// 为减小列表的内存大小,通常不存储这些指针。
/// 若要访问多个字段,应先调用 slice() 计算指针,再从该切片取得各字段数组。
///
pub const Slice = struct {
/// 此数组以字段索引为下标;
/// 可对 Field 枚举调用 @intFromEnum() 获取该索引。
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;
}
/// 返回表示 `s` 中一段元素范围的 `Slice`,类似 `arr[off..len]`。
/// 对返回的 `Slice` 调用 `deinit` 或 `toMultiArrayList` 属于非法操作。
/// 断言 `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,
};
}
/// lib/lldb/ 中的调试器美化格式器使用此函数获取
/// 子字段顺序与条目类型,以支持此类型的美化调试输出。
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` 是各 T 字段 @sizeOf 的数组,按对齐要求降序排列。
/// `sizes.fields` 数组将 `sizes.bytes` 的数组索引映射为字段索引。
/// `sizes.big_align` 为分配的整体对齐要求,等于各字段对齐要求的最大值。
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),
};
};
/// 释放全部已分配内存。
pub fn deinit(self: *Self, gpa: Allocator) void {
gpa.free(self.allocatedBytes());
self.* = undefined;
}
/// 调用方拥有返回的内存。清空此 MultiArrayList。
pub fn toOwnedSlice(self: *Self) Slice {
const result = self.slice();
self.* = .{};
return result;
}
/// 计算指向数组每个字段起始位置的指针。
/// 若需访问多个字段,调用此函数可能比
/// 多次调用 `items()` 更高效。
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;
}
/// 获取指定字段的值切片。
/// 如果需要多个字段,考虑改为
/// 调用 slice()。
pub fn items(self: Self, comptime field: Field) []FieldType(field) {
return self.slice().items(field);
}
/// 用新数据覆盖一个数组元素。
pub fn set(self: *Self, index: usize, elem: T) void {
var slices = self.slice();
slices.set(index, elem);
}
/// 获取一个数组元素的所有数据。
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);
}
/// 将列表扩展 1 个元素。
///
/// 必要时分配更多内存。
pub fn append(self: *Self, gpa: Allocator, elem: T) Allocator.Error!void {
try self.ensureUnusedCapacity(gpa, 1);
self.appendAssumeCapacity(elem);
}
/// 将列表增加 1 个元素。
///
/// 断言容量足以容纳一个额外元素。
pub fn appendAssumeCapacity(self: *Self, elem: T) void {
assert(self.len < self.capacity);
self.len += 1;
self.set(self.len - 1, elem);
}
/// 将列表扩展一个元素。
///
/// 若容量不足以容纳新增元素,
/// 返回 `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);
}
/// 将列表扩展 1 个元素,返回新预留的
/// 索引,其数据未初始化。
///
/// 必要时分配更多内存。
pub fn addOne(self: *Self, gpa: Allocator) Allocator.Error!usize {
try self.ensureUnusedCapacity(gpa, 1);
return self.addOneAssumeCapacity();
}
/// 将列表扩展一个元素,返回新预留位置的索引,其数据未初始化。
///
/// 断言容量足以容纳一个额外项目。
///
pub fn addOneAssumeCapacity(self: *Self) usize {
assert(self.len < self.capacity);
const index = self.len;
self.len += 1;
return index;
}
/// 将列表扩展 1 个元素,返回新保留的
/// 索引,其数据未初始化。
///
/// 若容量不足以容纳一个新增
/// 条目,则返回 `error.OutOfMemory`。
pub fn addOneBounded(self: *Self) error{OutOfMemory}!usize {
if (self.capacity - self.len < 1) return error.OutOfMemory;
return addOneAssumeCapacity(self);
}
/// 从列表移除并返回最后一个元素;若列表为空则返回 `null`。
/// 使指向被移除元素字段的指针失效。
pub fn pop(self: *Self) ?T {
if (self.len == 0) return null;
const val = self.get(self.len - 1);
self.len -= 1;
return val;
}
/// 向列表插入一个元素。将指定索引及其后
/// 的所有元素向后移动一位,
/// 并将指定索引设置为所给元素。
///
/// 按需分配更多内存。
pub fn insert(self: *Self, gpa: Allocator, index: usize, elem: T) !void {
try self.ensureUnusedCapacity(gpa, 1);
self.insertAssumeCapacity(index, elem);
}
/// 向列表插入一个元素。将指定索引及其后
/// 的所有元素向后移动一位,
/// 并将指定索引设置为所给元素。
///
/// 断言容量足以容纳一个新增元素。
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);
}
}
/// 向列表插入一个元素。将指定索引及其后
/// 的所有元素向后移动一位,
/// 并将指定索引设置为所给元素。
///
/// 若容量不足以容纳一个新增元素,
/// 返回 `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);
}
/// 从列表中移除指定项,将列表最后一项
/// 交换到其位置。速度快,但不
/// 保持列表顺序。
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;
}
/// 从列表中移除指定项目,并移动其后的项目以保持顺序。
///
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;
}
/// 移除 `sorted_indexes` 索引的元素。这些待移除索引
/// 对应删除前的数组列表。
///
/// 断言:
/// * 每个待移除索引都在范围内。
/// * 待移除索引按升序排列。
///
/// 允许 `sorted_indexes` 中存在重复项。
///
/// 此操作的时间复杂度为 O(N)。
///
/// 使首个被删除索引之后的元素指针失效。
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; // 允许 `sorted_indexes` 中存在重复项
const start = removed + 1;
const len = end - start; // 安全检查:`sorted_indexes` 已排序
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]); // 安全检查:初始 `sorted_indexes` 均在范围内
}
shift += 1;
}
const start = sorted_indexes[sorted_indexes.len - 1] + 1;
const end = self.len;
const len = end - start; // 安全检查:最终 `sorted_indexes` 均在范围内
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;
}
/// 将列表长度调整为 `new_len`。
/// 不会初始化新增项目。
pub fn resize(self: *Self, gpa: Allocator, new_len: usize) Allocator.Error!void {
try self.ensureTotalCapacity(gpa, new_len);
self.len = new_len;
}
/// 尝试将已分配容量缩减为 `new_len`。
/// 若 `new_len` 大于零,则可能无法缩减容量,
/// 但数据保持完整,长度会更新为 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..];
// 此处使用 memset,以便在启用安全检查和 valgrind 的
// 构建中生成更高效的代码。否则,
// 每个元素都会重复执行 valgrind 客户端请求。
@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.* = .{};
}
/// 将长度缩减为 `new_len`。
/// 指向元素 `items[new_len..]` 的指针会失效。
/// 容量保持不变。
pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
self.len = new_len;
}
/// 使所有元素指针失效。
pub fn clearRetainingCapacity(self: *Self) void {
self.len = 0;
}
/// 修改数组,使其至少可容纳 `new_capacity` 个条目。
/// 采用超线性增长,以实现均摊 O(1) 的追加操作。
/// 如果需要额外内存,则使元素指针失效。
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);
};
/// 给定所需内存容量的下限,返回按超线性
/// 增长得到的更大值。
pub fn growCapacity(minimum: usize) usize {
return minimum +| (minimum / 2 + init_capacity);
}
/// 调整数组,使其至少可**再**容纳 `additional_count` 个元素。
/// 如果需要额外内存,指针将失效。
pub fn ensureUnusedCapacity(self: *Self, gpa: Allocator, additional_count: usize) Allocator.Error!void {
return self.ensureTotalCapacity(gpa, self.len + additional_count);
}
/// 修改数组,使其恰好可容纳 `new_capacity` 个条目。
/// 如果需要额外内存,则使指针失效。
/// `new_capacity` 必须大于或等于 `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;
}
/// 使用指定分配器,
/// 以新的底层存储创建此列表的副本。
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` 具有以下方法:
/// `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),
}
}
/// 此函数保证稳定排序,即排序时保留相等元素的相对顺序。
/// 稳定排序的更多说明:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
/// 如果不需要此保证,`sortUnstable` 可能更快。
/// `ctx` 具有以下方法:
/// `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);
}
/// 仅对索引 `a` 和 `b` 之间、不含 `b` 的元素子区间排序。
/// 保证稳定排序,即排序时保留相等元素的相对顺序。
/// 稳定排序的更多说明:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
/// 若不需要此保证,`sortSpanUnstable` 可能更快。
/// `ctx` 具有以下方法:
/// `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);
}
/// 此函数不保证稳定排序,即相等元素的相对顺序可能在排序期间改变。
/// 由于保证较弱,此函数可能比稳定的 `sort` 方法更快。
/// 稳定排序的详细说明:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
/// `ctx` 具有以下方法:
/// `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);
}
/// 仅排序索引 `a` 与 `b` 之间的元素子区间,不包含 `b`。
/// 此函数不保证稳定排序,即相等元素的相对顺序可能在排序期间改变。
/// 由于保证较弱,此函数可能比稳定的 `sortSpan` 方法更快。
/// 稳定排序的详细说明:https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
/// `ctx` 具有以下方法:
/// `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);
};
/// lib/lldb/ 中的调试器美化格式器使用此函数获取
/// 子字段顺序与条目类型,以支持此类型的美化调试输出。
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]);
// 再添加 6 个项目以强制扩容。
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);
}
// 已观察到 LLVM 11 在 aarch64 上,当 capacityInBytes
// 函数使用 @reduce 代码路径时,此测试失败。
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);
// 再添加 6 个项目以强制扩容。
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));
}