1const std = @import("std");
2const builtin = @import("builtin");
3const assert = std.debug.assert;
4const meta = std.meta;
5const mem = std.mem;
6const Allocator = mem.Allocator;
7const testing = std.testing;
8
9/// A MultiArrayList stores a list of a struct or tagged union type.
10/// Instead of storing a single list of items, MultiArrayList
11/// stores separate lists for each field of the struct or
12/// lists of tags and bare unions.
13/// This allows for memory savings if the struct or union has padding,
14/// and also improves cache usage if only some fields or just tags
15/// are needed for a computation. The primary API for accessing fields is
16/// the `slice()` function, which computes the start pointers
17/// for the array of each field. From the slice you can call
18/// `.items(.<field_name>)` to obtain a slice of field values.
19/// For unions you can call `.items(.tags)` or `.items(.data)`.
20pub fn MultiArrayList(comptime T: type) type {
21 return struct {
22 /// This pointer is always aligned to the boundary `sizes.big_align`; this is not specified
23 /// in the type to avoid `MultiArrayList(T)` depending on the alignment of `T` because this
24 /// can lead to dependency loops. See `allocatedBytes` which `@alignCast`s this pointer to
25 /// the correct type.
26 bytes: [*]u8 = undefined,
27 len: usize = 0,
28 capacity: usize = 0,
29
30 pub const empty: Self = .{
31 .bytes = undefined,
32 .len = 0,
33 .capacity = 0,
34 };
35
36 /// Initialize with capacity to hold exactly `num` elements.
37 /// Deinitialize with `deinit` or `toOwnedSlice`.
38 pub fn initCapacity(gpa: Allocator, num: usize) Allocator.Error!Self {
39 var self: Self = .empty;
40 try self.setCapacity(gpa, num);
41 return self;
42 }
43
44 const Elem = switch (@typeInfo(T)) {
45 .@"struct" => T,
46 .@"union" => |u| struct {
47 pub const Bare = std.meta.BareUnion(T);
48 pub const Tag =
49 u.tag_type orelse @compileError("MultiArrayList does not support untagged unions");
50 tags: Tag,
51 data: Bare,
52
53 pub fn fromT(outer: T) @This() {
54 const tag = meta.activeTag(outer);
55 return .{
56 .tags = tag,
57 .data = switch (tag) {
58 inline else => |t| @unionInit(Bare, @tagName(t), @field(outer, @tagName(t))),
59 },
60 };
61 }
62 pub fn toT(tag: Tag, bare: Bare) T {
63 return switch (tag) {
64 inline else => |t| @unionInit(T, @tagName(t), @field(bare, @tagName(t))),
65 };
66 }
67 },
68 else => @compileError("MultiArrayList only supports structs and tagged unions"),
69 };
70
71 pub const Field = meta.FieldEnum(Elem);
72
73 /// A MultiArrayList.Slice contains cached start pointers for each field in the list.
74 /// These pointers are not normally stored to reduce the size of the list in memory.
75 /// If you are accessing multiple fields, call slice() first to compute the pointers,
76 /// and then get the field arrays from the slice.
77 pub const Slice = struct {
78 /// This array is indexed by the field index which can be obtained
79 /// by using @intFromEnum() on the Field enum
80 ptrs: [field_names.len][*]u8,
81 len: usize,
82 capacity: usize,
83
84 pub const empty: Slice = .{
85 .ptrs = undefined,
86 .len = 0,
87 .capacity = 0,
88 };
89
90 pub fn items(self: Slice, comptime field: Field) []FieldType(field) {
91 const F = FieldType(field);
92 if (self.capacity == 0) {
93 return &[_]F{};
94 }
95 const byte_ptr = self.ptrs[@backingInt(field)];
96 const casted_ptr: [*]F = if (@sizeOf(F) == 0)
97 undefined
98 else
99 @ptrCast(@alignCast(byte_ptr));
100 return casted_ptr[0..self.len];
101 }
102
103 pub fn set(self: *Slice, index: usize, elem: T) void {
104 const e = switch (@typeInfo(T)) {
105 .@"struct" => elem,
106 .@"union" => Elem.fromT(elem),
107 else => unreachable,
108 };
109 inline for (field_names, 0..) |field_name, i| {
110 self.items(@as(Field, @fromBackingInt(@intCast(i))))[index] = @field(e, field_name);
111 }
112 }
113
114 pub fn get(self: Slice, index: usize) T {
115 var result: Elem = undefined;
116 inline for (field_names, 0..) |field_name, i| {
117 @field(result, field_name) = self.items(@as(Field, @fromBackingInt(@intCast(i))))[index];
118 }
119 return switch (@typeInfo(T)) {
120 .@"struct" => result,
121 .@"union" => Elem.toT(result.tags, result.data),
122 else => unreachable,
123 };
124 }
125
126 pub fn swap(self: Slice, a: usize, b: usize) void {
127 inline for (@typeInfo(Field).@"enum".field_names) |field_name| {
128 const its = self.items(@field(Field, field_name));
129 std.mem.swap(@FieldType(T, field_name), &its[a], &its[b]);
130 }
131 }
132
133 pub fn toMultiArrayList(self: Slice) Self {
134 if (self.ptrs.len == 0 or self.capacity == 0) {
135 return .{};
136 }
137 return .{
138 .bytes = self.ptrs[sizes.fields[0]],
139 .len = self.len,
140 .capacity = self.capacity,
141 };
142 }
143
144 pub fn deinit(self: *Slice, gpa: Allocator) void {
145 var other = self.toMultiArrayList();
146 other.deinit(gpa);
147 self.* = undefined;
148 }
149
150 /// Returns a `Slice` representing a range of elements in `s`, analagous to `arr[off..len]`.
151 /// It is illegal to call `deinit` or `toMultiArrayList` on the returned `Slice`.
152 /// Asserts that `off + len <= s.len`.
153 pub fn subslice(s: Slice, off: usize, len: usize) Slice {
154 assert(off + len <= s.len);
155 var ptrs: [field_names.len][*]u8 = undefined;
156 inline for (s.ptrs, &ptrs, field_types) |in, *out, field_type| {
157 out.* = in + (off * @sizeOf(field_type));
158 }
159 return .{
160 .ptrs = ptrs,
161 .len = len,
162 .capacity = len,
163 };
164 }
165
166 /// This function is used in the debugger pretty formatters in lib/lldb/ to fetch the
167 /// child field order and entry type to facilitate fancy debug printing for this type.
168 fn dbHelper(self: *Slice, child: *Elem, field: *Field, entry: *Entry) void {
169 _ = self;
170 _ = child;
171 _ = field;
172 _ = entry;
173 }
174 };
175
176 const Self = @This();
177
178 const field_names = @typeInfo(Elem).@"struct".field_names;
179 const field_types = @typeInfo(Elem).@"struct".field_types;
180 const field_attrs = @typeInfo(Elem).@"struct".field_attrs;
181 /// `sizes.bytes` is an array of @sizeOf each T field. Sorted by alignment, descending.
182 /// `sizes.fields` is an array mapping from `sizes.bytes` array index to field index.
183 /// `sizes.big_align` is the overall alignment of the allocation, which equals the maximum field alignment.
184 const sizes = blk: {
185 const Data = struct {
186 size: usize,
187 size_index: usize,
188 alignment: usize,
189 };
190 var data: [field_names.len]Data = undefined;
191 var big_align: usize = 1;
192 for (field_types, field_attrs, 0..) |f_type, f_attrs, i| {
193 data[i] = .{
194 .size = @sizeOf(f_type),
195 .size_index = i,
196 .alignment = f_attrs.@"align" orelse @alignOf(f_type),
197 };
198 big_align = @max(big_align, data[i].alignment);
199 }
200 const Sort = struct {
201 fn lessThan(context: void, lhs: Data, rhs: Data) bool {
202 _ = context;
203 return lhs.alignment > rhs.alignment;
204 }
205 };
206 @setEvalBranchQuota(3 * field_names.len * std.math.log2(field_names.len));
207 mem.sort(Data, &data, {}, Sort.lessThan);
208 var sizes_bytes: [field_names.len]usize = undefined;
209 var field_indexes: [field_names.len]usize = undefined;
210 for (data, 0..) |elem, i| {
211 sizes_bytes[i] = elem.size;
212 field_indexes[i] = elem.size_index;
213 }
214 break :blk .{
215 .bytes = sizes_bytes,
216 .fields = field_indexes,
217 .big_align = mem.Alignment.fromByteUnits(big_align),
218 };
219 };
220
221 /// Release all allocated memory.
222 pub fn deinit(self: *Self, gpa: Allocator) void {
223 gpa.free(self.allocatedBytes());
224 self.* = undefined;
225 }
226
227 /// The caller owns the returned memory. Empties this MultiArrayList.
228 pub fn toOwnedSlice(self: *Self) Slice {
229 const result = self.slice();
230 self.* = .{};
231 return result;
232 }
233
234 /// Compute pointers to the start of each field of the array.
235 /// If you need to access multiple fields, calling this may
236 /// be more efficient than calling `items()` multiple times.
237 pub fn slice(self: Self) Slice {
238 var result: Slice = .{
239 .ptrs = undefined,
240 .len = self.len,
241 .capacity = self.capacity,
242 };
243 var ptr: [*]u8 = self.bytes;
244 for (sizes.bytes, sizes.fields) |field_size, i| {
245 result.ptrs[i] = ptr;
246 ptr += field_size * self.capacity;
247 }
248 return result;
249 }
250
251 /// Get the slice of values for a specified field.
252 /// If you need multiple fields, consider calling slice()
253 /// instead.
254 pub fn items(self: Self, comptime field: Field) []FieldType(field) {
255 return self.slice().items(field);
256 }
257
258 /// Overwrite one array element with new data.
259 pub fn set(self: *Self, index: usize, elem: T) void {
260 var slices = self.slice();
261 slices.set(index, elem);
262 }
263
264 /// Obtain all the data for one array element.
265 pub fn get(self: Self, index: usize) T {
266 return self.slice().get(index);
267 }
268
269 pub fn swap(self: Self, a: usize, b: usize) void {
270 return self.slice().swap(a, b);
271 }
272
273 /// Extend the list by 1 element.
274 ///
275 /// Allocates more memory as necessary.
276 pub fn append(self: *Self, gpa: Allocator, elem: T) Allocator.Error!void {
277 try self.ensureUnusedCapacity(gpa, 1);
278 self.appendAssumeCapacity(elem);
279 }
280
281 /// Extend the list by 1 element.
282 ///
283 /// Asserts that capacity is sufficient to hold an additional item.
284 pub fn appendAssumeCapacity(self: *Self, elem: T) void {
285 assert(self.len < self.capacity);
286 self.len += 1;
287 self.set(self.len - 1, elem);
288 }
289
290 /// Extend the list by 1 element.
291 ///
292 /// If capacity is not sufficient to hold an additional
293 /// item, returns `error.OutOfMemory`.
294 pub fn appendBounded(self: *Self, elem: T) error{OutOfMemory}!void {
295 if (self.capacity - self.len < 1) return error.OutOfMemory;
296 return appendAssumeCapacity(self, elem);
297 }
298
299 /// Extend the list by 1 element, returning the newly reserved
300 /// index with uninitialized data.
301 ///
302 /// Allocates more memory as necessary.
303 pub fn addOne(self: *Self, gpa: Allocator) Allocator.Error!usize {
304 try self.ensureUnusedCapacity(gpa, 1);
305 return self.addOneAssumeCapacity();
306 }
307
308 /// Extend the list by 1 element, returning the newly reserved
309 /// index with uninitialized data.
310 ///
311 /// Asserts that capacity is sufficient to hold an additional item.
312 pub fn addOneAssumeCapacity(self: *Self) usize {
313 assert(self.len < self.capacity);
314 const index = self.len;
315 self.len += 1;
316 return index;
317 }
318
319 /// Extend the list by 1 element, returning the newly reserved
320 /// index with uninitialized data.
321 ///
322 /// If capacity is not sufficient to hold an additional
323 /// item, returns `error.OutOfMemory`.
324 pub fn addOneBounded(self: *Self) error{OutOfMemory}!usize {
325 if (self.capacity - self.len < 1) return error.OutOfMemory;
326 return addOneAssumeCapacity(self);
327 }
328
329 /// Remove and return the last element from the list, or return `null` if list is empty.
330 /// Invalidates pointers to fields of the removed element.
331 pub fn pop(self: *Self) ?T {
332 if (self.len == 0) return null;
333 const val = self.get(self.len - 1);
334 self.len -= 1;
335 return val;
336 }
337
338 /// Inserts an item into the list. Shifts all elements
339 /// after and including the specified index back by one and
340 /// sets the given index to the specified element.
341 ///
342 /// Allocates more memory as necessary.
343 pub fn insert(self: *Self, gpa: Allocator, index: usize, elem: T) !void {
344 try self.ensureUnusedCapacity(gpa, 1);
345 self.insertAssumeCapacity(index, elem);
346 }
347
348 /// Inserts an item into the list. Shifts all elements
349 /// after and including the specified index back by one and
350 /// sets the given index to the specified element.
351 ///
352 /// Asserts that capacity is sufficient to hold an additional item.
353 pub fn insertAssumeCapacity(self: *Self, index: usize, elem: T) void {
354 assert(self.len < self.capacity);
355 assert(index <= self.len);
356 self.len += 1;
357 const entry = switch (@typeInfo(T)) {
358 .@"struct" => elem,
359 .@"union" => Elem.fromT(elem),
360 else => unreachable,
361 };
362 const slices = self.slice();
363 inline for (field_names, 0..) |field_name, field_index| {
364 const field_slice = slices.items(@as(Field, @fromBackingInt(@intCast(field_index))));
365 var i: usize = self.len - 1;
366 while (i > index) : (i -= 1) {
367 field_slice[i] = field_slice[i - 1];
368 }
369 field_slice[index] = @field(entry, field_name);
370 }
371 }
372
373 /// Inserts an item into the list. Shifts all elements
374 /// after and including the specified index back by one and
375 /// sets the given index to the specified element.
376 ///
377 /// If capacity is not sufficient to hold an additional
378 /// item, returns `error.OutOfMemory`.
379 pub fn insertBounded(self: *Self, index: usize, elem: T) error{OutOfMemory}!void {
380 if (self.capacity - self.len < 1) return error.OutOfMemory;
381 return insertAssumeCapacity(self, index, elem);
382 }
383
384 /// Remove the specified item from the list, swapping the last
385 /// item in the list into its position. Fast, but does not
386 /// retain list ordering.
387 pub fn swapRemove(self: *Self, index: usize) void {
388 const slices = self.slice();
389 inline for (field_names, 0..) |_, i| {
390 const field_slice = slices.items(@as(Field, @fromBackingInt(@intCast(i))));
391 field_slice[index] = field_slice[self.len - 1];
392 field_slice[self.len - 1] = undefined;
393 }
394 self.len -= 1;
395 }
396
397 /// Remove the specified item from the list, shifting items
398 /// after it to preserve order.
399 pub fn orderedRemove(self: *Self, index: usize) void {
400 const slices = self.slice();
401 inline for (field_names, 0..) |_, field_index| {
402 const field_slice = slices.items(@as(Field, @fromBackingInt(@intCast(field_index))));
403 var i = index;
404 while (i < self.len - 1) : (i += 1) {
405 field_slice[i] = field_slice[i + 1];
406 }
407 field_slice[i] = undefined;
408 }
409 self.len -= 1;
410 }
411
412 /// Remove the elements indexed by `sorted_indexes`. The indexes to be
413 /// removed correspond to the array list before deletion.
414 ///
415 /// Asserts:
416 /// * Each index to be removed is in bounds.
417 /// * The indexes to be removed are sorted ascending.
418 ///
419 /// Duplicates in `sorted_indexes` are allowed.
420 ///
421 /// This operation is O(N).
422 ///
423 /// Invalidates element pointers beyond the first deleted index.
424 pub fn orderedRemoveMany(self: *Self, sorted_indexes: []const usize) void {
425 if (sorted_indexes.len == 0) return;
426 const slices = self.slice();
427 var shift: usize = 1;
428 for (sorted_indexes[0 .. sorted_indexes.len - 1], sorted_indexes[1..]) |removed, end| {
429 if (removed == end) continue; // allows duplicates in `sorted_indexes`
430 const start = removed + 1;
431 const len = end - start; // safety checks `sorted_indexes` are sorted
432 inline for (field_names, 0..) |_, field_index| {
433 const field_slice = slices.items(@fromBackingInt(@intCast(field_index)));
434 @memmove(field_slice[start - shift ..][0..len], field_slice[start..][0..len]); // safety checks initial `sorted_indexes` are in range
435 }
436 shift += 1;
437 }
438 const start = sorted_indexes[sorted_indexes.len - 1] + 1;
439 const end = self.len;
440 const len = end - start; // safety checks final `sorted_indexes` are in range
441 inline for (field_names, 0..) |_, field_index| {
442 const field_slice = slices.items(@fromBackingInt(@intCast(field_index)));
443 @memmove(field_slice[start - shift ..][0..len], field_slice[start..][0..len]);
444 }
445 self.len = end - shift;
446 }
447
448 /// Adjust the list's length to `new_len`.
449 /// Does not initialize added items, if any.
450 pub fn resize(self: *Self, gpa: Allocator, new_len: usize) Allocator.Error!void {
451 try self.ensureTotalCapacity(gpa, new_len);
452 self.len = new_len;
453 }
454
455 /// Attempt to reduce allocated capacity to `new_len`.
456 /// If `new_len` is greater than zero, this may fail to reduce the capacity,
457 /// but the data remains intact and the length is updated to new_len.
458 pub fn shrinkAndFree(self: *Self, gpa: Allocator, new_len: usize) void {
459 if (new_len == 0) return clearAndFree(self, gpa);
460
461 assert(new_len <= self.capacity);
462 assert(new_len <= self.len);
463
464 const other_bytes = gpa.alignedAlloc(u8, sizes.big_align, capacityInBytes(new_len)) catch {
465 const self_slice = self.slice();
466 inline for (field_types, 0..) |field_type, i| {
467 if (@sizeOf(field_type) != 0) {
468 const field = @as(Field, @fromBackingInt(@intCast(i)));
469 const dest_slice = self_slice.items(field)[new_len..];
470 // We use memset here for more efficient codegen in safety-checked,
471 // valgrind-enabled builds. Otherwise the valgrind client request
472 // will be repeated for every element.
473 @memset(dest_slice, undefined);
474 }
475 }
476 self.len = new_len;
477 return;
478 };
479 var other = Self{
480 .bytes = other_bytes.ptr,
481 .capacity = new_len,
482 .len = new_len,
483 };
484 self.len = new_len;
485 const self_slice = self.slice();
486 const other_slice = other.slice();
487 inline for (field_types, 0..) |field_type, i| {
488 if (@sizeOf(field_type) != 0) {
489 const field = @as(Field, @fromBackingInt(@intCast(i)));
490 @memcpy(other_slice.items(field), self_slice.items(field));
491 }
492 }
493 gpa.free(self.allocatedBytes());
494 self.* = other;
495 }
496
497 pub fn clearAndFree(self: *Self, gpa: Allocator) void {
498 gpa.free(self.allocatedBytes());
499 self.* = .{};
500 }
501
502 /// Reduce length to `new_len`.
503 /// Invalidates pointers to elements `items[new_len..]`.
504 /// Keeps capacity the same.
505 pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
506 self.len = new_len;
507 }
508
509 /// Invalidates all element pointers.
510 pub fn clearRetainingCapacity(self: *Self) void {
511 self.len = 0;
512 }
513
514 /// Modify the array so that it can hold at least `new_capacity` items.
515 /// Implements super-linear growth to achieve amortized O(1) append operations.
516 /// Invalidates element pointers if additional memory is needed.
517 pub fn ensureTotalCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
518 if (self.capacity >= new_capacity) return;
519 return self.setCapacity(gpa, growCapacity(new_capacity));
520 }
521
522 const init_capacity: comptime_int = init: {
523 var max: comptime_int = 1;
524 for (field_types) |field_type| max = @max(max, @sizeOf(field_type));
525 break :init @max(1, std.atomic.cache_line / max);
526 };
527
528 /// Given a lower bound of required memory capacity, returns a larger value
529 /// with super-linear growth.
530 pub fn growCapacity(minimum: usize) usize {
531 return minimum +| (minimum / 2 + init_capacity);
532 }
533
534 /// Modify the array so that it can hold at least `additional_count` **more** items.
535 /// Invalidates pointers if additional memory is needed.
536 pub fn ensureUnusedCapacity(self: *Self, gpa: Allocator, additional_count: usize) Allocator.Error!void {
537 return self.ensureTotalCapacity(gpa, self.len + additional_count);
538 }
539
540 /// Modify the array so that it can hold exactly `new_capacity` items.
541 /// Invalidates pointers if additional memory is needed.
542 /// `new_capacity` must be greater or equal to `len`.
543 pub fn setCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
544 assert(new_capacity >= self.len);
545 const new_bytes = try gpa.alignedAlloc(u8, sizes.big_align, capacityInBytes(new_capacity));
546 if (self.len == 0) {
547 gpa.free(self.allocatedBytes());
548 self.bytes = new_bytes.ptr;
549 self.capacity = new_capacity;
550 return;
551 }
552 var other = Self{
553 .bytes = new_bytes.ptr,
554 .capacity = new_capacity,
555 .len = self.len,
556 };
557 const self_slice = self.slice();
558 const other_slice = other.slice();
559 inline for (field_types, 0..) |field_type, i| {
560 if (@sizeOf(field_type) != 0) {
561 const field = @as(Field, @fromBackingInt(@intCast(i)));
562 @memcpy(other_slice.items(field), self_slice.items(field));
563 }
564 }
565 gpa.free(self.allocatedBytes());
566 self.* = other;
567 }
568
569 /// Create a copy of this list with a new backing store,
570 /// using the specified allocator.
571 pub fn clone(self: Self, gpa: Allocator) Allocator.Error!Self {
572 var result = Self{};
573 errdefer result.deinit(gpa);
574 try result.ensureTotalCapacity(gpa, self.len);
575 result.len = self.len;
576 const self_slice = self.slice();
577 const result_slice = result.slice();
578 inline for (field_types, 0..) |field_type, i| {
579 if (@sizeOf(field_type) != 0) {
580 const field = @as(Field, @fromBackingInt(@intCast(i)));
581 @memcpy(result_slice.items(field), self_slice.items(field));
582 }
583 }
584 return result;
585 }
586
587 /// `ctx` has the following method:
588 /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
589 fn sortInternal(self: Self, a: usize, b: usize, ctx: anytype, comptime mode: std.sort.Mode) void {
590 const sort_context: struct {
591 sub_ctx: @TypeOf(ctx),
592 slice: Slice,
593
594 pub fn swap(sc: @This(), a_index: usize, b_index: usize) void {
595 inline for (field_types, 0..) |field_type, i| {
596 if (@sizeOf(field_type) != 0) {
597 const field: Field = @fromBackingInt(@intCast(i));
598 const ptr = sc.slice.items(field);
599 mem.swap(field_type, &ptr[a_index], &ptr[b_index]);
600 }
601 }
602 }
603
604 pub fn lessThan(sc: @This(), a_index: usize, b_index: usize) bool {
605 return sc.sub_ctx.lessThan(a_index, b_index);
606 }
607 } = .{
608 .sub_ctx = ctx,
609 .slice = self.slice(),
610 };
611
612 switch (mode) {
613 .stable => mem.sortContext(a, b, sort_context),
614 .unstable => mem.sortUnstableContext(a, b, sort_context),
615 }
616 }
617
618 /// This function guarantees a stable sort, i.e the relative order of equal elements is preserved during sorting.
619 /// Read more about stable sorting here: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
620 /// If this guarantee does not matter, `sortUnstable` might be a faster alternative.
621 /// `ctx` has the following method:
622 /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
623 pub fn sort(self: Self, ctx: anytype) void {
624 self.sortInternal(0, self.len, ctx, .stable);
625 }
626
627 /// Sorts only the subsection of items between indices `a` and `b` (excluding `b`)
628 /// This function guarantees a stable sort, i.e the relative order of equal elements is preserved during sorting.
629 /// Read more about stable sorting here: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
630 /// If this guarantee does not matter, `sortSpanUnstable` might be a faster alternative.
631 /// `ctx` has the following method:
632 /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
633 pub fn sortSpan(self: Self, a: usize, b: usize, ctx: anytype) void {
634 self.sortInternal(a, b, ctx, .stable);
635 }
636
637 /// This function does NOT guarantee a stable sort, i.e the relative order of equal elements may change during sorting.
638 /// Due to the weaker guarantees of this function, this may be faster than the stable `sort` method.
639 /// Read more about stable sorting here: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
640 /// `ctx` has the following method:
641 /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
642 pub fn sortUnstable(self: Self, ctx: anytype) void {
643 self.sortInternal(0, self.len, ctx, .unstable);
644 }
645
646 /// Sorts only the subsection of items between indices `a` and `b` (excluding `b`)
647 /// This function does NOT guarantee a stable sort, i.e the relative order of equal elements may change during sorting.
648 /// Due to the weaker guarantees of this function, this may be faster than the stable `sortSpan` method.
649 /// Read more about stable sorting here: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
650 /// `ctx` has the following method:
651 /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
652 pub fn sortSpanUnstable(self: Self, a: usize, b: usize, ctx: anytype) void {
653 self.sortInternal(a, b, ctx, .unstable);
654 }
655
656 pub fn capacityInBytes(capacity: usize) usize {
657 comptime var elem_bytes: usize = 0;
658 inline for (sizes.bytes) |size| elem_bytes += size;
659 return elem_bytes * capacity;
660 }
661
662 fn allocatedBytes(self: Self) []align(sizes.big_align.toByteUnits()) u8 {
663 return @alignCast(self.bytes[0..capacityInBytes(self.capacity)]);
664 }
665
666 fn FieldType(comptime field: Field) type {
667 return @FieldType(Elem, @tagName(field));
668 }
669
670 const Entry = entry: {
671 var entry_field_names: [field_names.len][]const u8 = undefined;
672 var entry_field_types: [field_names.len]type = undefined;
673 var entry_field_attrs: [field_names.len]std.builtin.Type.Struct.FieldAttributes = undefined;
674 for (sizes.fields, &entry_field_names, &entry_field_types, &entry_field_attrs) |i, *name, *Type, *attrs| {
675 name.* = field_names[i] ++ "_ptr";
676 Type.* = *field_types[i];
677 attrs.* = .{
678 .@"comptime" = field_attrs[i].@"comptime",
679 .@"align" = field_attrs[i].@"align",
680 };
681 }
682 break :entry @Struct(.@"extern", null, &entry_field_names, &entry_field_types, &entry_field_attrs);
683 };
684 /// This function is used in the debugger pretty formatters in lib/lldb/ to fetch the
685 /// child field order and entry type to facilitate fancy debug printing for this type.
686 fn dbHelper(self: *Self, child: *Elem, field: *Field, entry: *Entry) void {
687 _ = self;
688 _ = child;
689 _ = field;
690 _ = entry;
691 }
692
693 comptime {
694 if (builtin.zig_backend == .stage2_llvm and !builtin.strip_debug_info) {
695 _ = &dbHelper;
696 _ = &Slice.dbHelper;
697 }
698 }
699 };
700}
701
702test "basic usage" {
703 const ally = testing.allocator;
704
705 const Foo = struct {
706 a: u32,
707 b: []const u8,
708 c: u8,
709 };
710
711 var list: MultiArrayList(Foo) = .empty;
712 defer list.deinit(ally);
713
714 try testing.expectEqual(@as(usize, 0), list.items(.a).len);
715
716 try list.ensureTotalCapacity(ally, 2);
717
718 list.appendAssumeCapacity(.{
719 .a = 1,
720 .b = "foobar",
721 .c = 'a',
722 });
723
724 try list.appendBounded(.{
725 .a = 2,
726 .b = "zigzag",
727 .c = 'b',
728 });
729
730 try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 1, 2 });
731 try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'a', 'b' });
732
733 try testing.expectEqual(@as(usize, 2), list.items(.b).len);
734 try testing.expectEqualStrings("foobar", list.items(.b)[0]);
735 try testing.expectEqualStrings("zigzag", list.items(.b)[1]);
736
737 try list.append(ally, .{
738 .a = 3,
739 .b = "fizzbuzz",
740 .c = 'c',
741 });
742
743 try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 1, 2, 3 });
744 try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'a', 'b', 'c' });
745
746 try testing.expectEqual(@as(usize, 3), list.items(.b).len);
747 try testing.expectEqualStrings("foobar", list.items(.b)[0]);
748 try testing.expectEqualStrings("zigzag", list.items(.b)[1]);
749 try testing.expectEqualStrings("fizzbuzz", list.items(.b)[2]);
750
751 // Add 6 more things to force a capacity increase.
752 var i: usize = 0;
753 while (i < 6) : (i += 1) {
754 try list.append(ally, .{
755 .a = @as(u32, @intCast(4 + i)),
756 .b = "whatever",
757 .c = @as(u8, @intCast('d' + i)),
758 });
759 }
760
761 try testing.expectEqualSlices(
762 u32,
763 &[_]u32{ 1, 2, 3, 4, 5, 6, 7, 8, 9 },
764 list.items(.a),
765 );
766 try testing.expectEqualSlices(
767 u8,
768 &[_]u8{ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i' },
769 list.items(.c),
770 );
771
772 list.shrinkAndFree(ally, 3);
773
774 try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 1, 2, 3 });
775 try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'a', 'b', 'c' });
776
777 list.swap(0, 2);
778 try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 3, 2, 1 });
779 try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'c', 'b', 'a' });
780 list.swap(2, 1);
781 try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 3, 1, 2 });
782 try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'c', 'a', 'b' });
783 list.swap(2, 0);
784 try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 2, 1, 3 });
785 try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'b', 'a', 'c' });
786 list.swap(0, 1);
787 try testing.expectEqualSlices(u32, list.items(.a), &[_]u32{ 1, 2, 3 });
788 try testing.expectEqualSlices(u8, list.items(.c), &[_]u8{ 'a', 'b', 'c' });
789
790 try testing.expectEqual(@as(usize, 3), list.items(.b).len);
791 try testing.expectEqualStrings("foobar", list.items(.b)[0]);
792 try testing.expectEqualStrings("zigzag", list.items(.b)[1]);
793 try testing.expectEqualStrings("fizzbuzz", list.items(.b)[2]);
794
795 try testing.expectError(error.OutOfMemory, list.addOneBounded());
796
797 list.set(try list.addOne(ally), .{
798 .a = 4,
799 .b = "xnopyt",
800 .c = 'd',
801 });
802 try testing.expectEqualStrings("xnopyt", list.pop().?.b);
803 try testing.expectEqual(@as(?u8, 'c'), if (list.pop()) |elem| elem.c else null);
804 try testing.expectEqual(@as(u32, 2), list.pop().?.a);
805 try testing.expectEqual(@as(u8, 'a'), list.pop().?.c);
806 try testing.expectEqual(@as(?Foo, null), list.pop());
807
808 list.clearRetainingCapacity();
809 try testing.expectEqual(0, list.len);
810 try testing.expect(list.capacity > 0);
811
812 list.clearAndFree(ally);
813 try testing.expectEqual(0, list.len);
814 try testing.expectEqual(0, list.capacity);
815}
816
817// This was observed to fail on aarch64 with LLVM 11, when the capacityInBytes
818// function used the @reduce code path.
819test "regression test for @reduce bug" {
820 const ally = testing.allocator;
821 var list: MultiArrayList(struct {
822 tag: std.zig.Token.Tag,
823 start: u32,
824 }) = .empty;
825 defer list.deinit(ally);
826
827 try list.ensureTotalCapacity(ally, 20);
828
829 try list.append(ally, .{ .tag = .keyword_const, .start = 0 });
830 try list.append(ally, .{ .tag = .identifier, .start = 6 });
831 try list.append(ally, .{ .tag = .equal, .start = 10 });
832 try list.append(ally, .{ .tag = .builtin, .start = 12 });
833 try list.append(ally, .{ .tag = .l_paren, .start = 19 });
834 try list.append(ally, .{ .tag = .string_literal, .start = 20 });
835 try list.append(ally, .{ .tag = .r_paren, .start = 25 });
836 try list.append(ally, .{ .tag = .semicolon, .start = 26 });
837 try list.append(ally, .{ .tag = .keyword_pub, .start = 29 });
838 try list.append(ally, .{ .tag = .keyword_fn, .start = 33 });
839 try list.append(ally, .{ .tag = .identifier, .start = 36 });
840 try list.append(ally, .{ .tag = .l_paren, .start = 40 });
841 try list.append(ally, .{ .tag = .r_paren, .start = 41 });
842 try list.append(ally, .{ .tag = .identifier, .start = 43 });
843 try list.append(ally, .{ .tag = .bang, .start = 51 });
844 try list.append(ally, .{ .tag = .identifier, .start = 52 });
845 try list.append(ally, .{ .tag = .l_brace, .start = 57 });
846 try list.append(ally, .{ .tag = .identifier, .start = 63 });
847 try list.append(ally, .{ .tag = .period, .start = 66 });
848 try list.append(ally, .{ .tag = .identifier, .start = 67 });
849 try list.append(ally, .{ .tag = .period, .start = 70 });
850 try list.append(ally, .{ .tag = .identifier, .start = 71 });
851 try list.append(ally, .{ .tag = .l_paren, .start = 75 });
852 try list.append(ally, .{ .tag = .string_literal, .start = 76 });
853 try list.append(ally, .{ .tag = .comma, .start = 113 });
854 try list.append(ally, .{ .tag = .period, .start = 115 });
855 try list.append(ally, .{ .tag = .l_brace, .start = 116 });
856 try list.append(ally, .{ .tag = .r_brace, .start = 117 });
857 try list.append(ally, .{ .tag = .r_paren, .start = 118 });
858 try list.append(ally, .{ .tag = .semicolon, .start = 119 });
859 try list.append(ally, .{ .tag = .r_brace, .start = 121 });
860 try list.append(ally, .{ .tag = .eof, .start = 123 });
861
862 const tags = list.items(.tag);
863 try testing.expectEqual(tags[1], .identifier);
864 try testing.expectEqual(tags[2], .equal);
865 try testing.expectEqual(tags[3], .builtin);
866 try testing.expectEqual(tags[4], .l_paren);
867 try testing.expectEqual(tags[5], .string_literal);
868 try testing.expectEqual(tags[6], .r_paren);
869 try testing.expectEqual(tags[7], .semicolon);
870 try testing.expectEqual(tags[8], .keyword_pub);
871 try testing.expectEqual(tags[9], .keyword_fn);
872 try testing.expectEqual(tags[10], .identifier);
873 try testing.expectEqual(tags[11], .l_paren);
874 try testing.expectEqual(tags[12], .r_paren);
875 try testing.expectEqual(tags[13], .identifier);
876 try testing.expectEqual(tags[14], .bang);
877 try testing.expectEqual(tags[15], .identifier);
878 try testing.expectEqual(tags[16], .l_brace);
879 try testing.expectEqual(tags[17], .identifier);
880 try testing.expectEqual(tags[18], .period);
881 try testing.expectEqual(tags[19], .identifier);
882 try testing.expectEqual(tags[20], .period);
883 try testing.expectEqual(tags[21], .identifier);
884 try testing.expectEqual(tags[22], .l_paren);
885 try testing.expectEqual(tags[23], .string_literal);
886 try testing.expectEqual(tags[24], .comma);
887 try testing.expectEqual(tags[25], .period);
888 try testing.expectEqual(tags[26], .l_brace);
889 try testing.expectEqual(tags[27], .r_brace);
890 try testing.expectEqual(tags[28], .r_paren);
891 try testing.expectEqual(tags[29], .semicolon);
892 try testing.expectEqual(tags[30], .r_brace);
893 try testing.expectEqual(tags[31], .eof);
894}
895
896test "ensure capacity on empty list" {
897 const ally = testing.allocator;
898
899 const Foo = struct {
900 a: u32,
901 b: u8,
902 };
903
904 var list: MultiArrayList(Foo) = .empty;
905 defer list.deinit(ally);
906
907 try list.ensureTotalCapacity(ally, 2);
908 list.appendAssumeCapacity(.{ .a = 1, .b = 2 });
909 list.appendAssumeCapacity(.{ .a = 3, .b = 4 });
910
911 try testing.expectEqualSlices(u32, &[_]u32{ 1, 3 }, list.items(.a));
912 try testing.expectEqualSlices(u8, &[_]u8{ 2, 4 }, list.items(.b));
913
914 list.len = 0;
915 list.appendAssumeCapacity(.{ .a = 5, .b = 6 });
916 list.appendAssumeCapacity(.{ .a = 7, .b = 8 });
917
918 try testing.expectEqualSlices(u32, &[_]u32{ 5, 7 }, list.items(.a));
919 try testing.expectEqualSlices(u8, &[_]u8{ 6, 8 }, list.items(.b));
920
921 list.len = 0;
922 try list.ensureTotalCapacity(ally, 16);
923
924 list.appendAssumeCapacity(.{ .a = 9, .b = 10 });
925 list.appendAssumeCapacity(.{ .a = 11, .b = 12 });
926
927 try testing.expectEqualSlices(u32, &[_]u32{ 9, 11 }, list.items(.a));
928 try testing.expectEqualSlices(u8, &[_]u8{ 10, 12 }, list.items(.b));
929}
930
931test "insert elements" {
932 const ally = testing.allocator;
933
934 const Foo = struct {
935 a: u8,
936 b: u32,
937 };
938
939 var list = try MultiArrayList(Foo).initCapacity(ally, 2);
940 defer list.deinit(ally);
941
942 try list.insertBounded(0, .{ .a = 1, .b = 2 });
943 list.insertAssumeCapacity(1, .{ .a = 2, .b = 3 });
944 try list.insert(ally, 0, .{ .a = 3, .b = 4 });
945
946 try testing.expectEqualSlices(u8, &[_]u8{ 3, 1, 2 }, list.items(.a));
947 try testing.expectEqualSlices(u32, &[_]u32{ 4, 2, 3 }, list.items(.b));
948}
949
950test "initCapacity" {
951 const gpa = testing.allocator;
952
953 var list = try MultiArrayList(struct { a: u8, b: u32 }).initCapacity(gpa, 404);
954 defer list.deinit(gpa);
955
956 try testing.expectEqual(0, list.len);
957 try testing.expectEqual(404, list.capacity);
958}
959
960test "union" {
961 const ally = testing.allocator;
962
963 const Foo = union(enum) {
964 a: u32,
965 b: []const u8,
966 };
967
968 var list: MultiArrayList(Foo) = .empty;
969 defer list.deinit(ally);
970
971 try testing.expectEqual(@as(usize, 0), list.items(.tags).len);
972
973 try list.ensureTotalCapacity(ally, 3);
974
975 list.appendAssumeCapacity(.{ .a = 1 });
976 list.appendAssumeCapacity(.{ .b = "zigzag" });
977
978 try testing.expectEqualSlices(meta.Tag(Foo), list.items(.tags), &.{ .a, .b });
979 try testing.expectEqual(@as(usize, 2), list.items(.tags).len);
980
981 list.appendAssumeCapacity(.{ .b = "foobar" });
982 try testing.expectEqualStrings("zigzag", list.items(.data)[1].b);
983 try testing.expectEqualStrings("foobar", list.items(.data)[2].b);
984
985 // Add 6 more things to force a capacity increase.
986 for (0..6) |i| {
987 try list.append(ally, .{ .a = @as(u32, @intCast(4 + i)) });
988 }
989
990 try testing.expectEqualSlices(
991 meta.Tag(Foo),
992 &.{ .a, .b, .b, .a, .a, .a, .a, .a, .a },
993 list.items(.tags),
994 );
995 try testing.expectEqual(Foo{ .a = 1 }, list.get(0));
996 try testing.expectEqual(Foo{ .b = "zigzag" }, list.get(1));
997 try testing.expectEqual(Foo{ .b = "foobar" }, list.get(2));
998 try testing.expectEqual(Foo{ .a = 4 }, list.get(3));
999 try testing.expectEqual(Foo{ .a = 5 }, list.get(4));
1000 try testing.expectEqual(Foo{ .a = 6 }, list.get(5));
1001 try testing.expectEqual(Foo{ .a = 7 }, list.get(6));
1002 try testing.expectEqual(Foo{ .a = 8 }, list.get(7));
1003 try testing.expectEqual(Foo{ .a = 9 }, list.get(8));
1004
1005 list.shrinkAndFree(ally, 3);
1006
1007 try testing.expectEqual(@as(usize, 3), list.items(.tags).len);
1008 try testing.expectEqualSlices(meta.Tag(Foo), list.items(.tags), &.{ .a, .b, .b });
1009
1010 try testing.expectEqual(Foo{ .a = 1 }, list.get(0));
1011 try testing.expectEqual(Foo{ .b = "zigzag" }, list.get(1));
1012 try testing.expectEqual(Foo{ .b = "foobar" }, list.get(2));
1013}
1014
1015test "sorting a span" {
1016 var list: MultiArrayList(struct { score: u32, chr: u8 }) = .empty;
1017 defer list.deinit(testing.allocator);
1018
1019 try list.ensureTotalCapacity(testing.allocator, 42);
1020 for (
1021 // zig fmt: off
1022 [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' },
1023 [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 },
1024 // zig fmt: on
1025 ) |chr, score| {
1026 list.appendAssumeCapacity(.{ .chr = chr, .score = score });
1027 }
1028
1029 const sliced = list.slice();
1030 list.sortSpan(6, 21, struct {
1031 chars: []const u8,
1032
1033 fn lessThan(ctx: @This(), a: usize, b: usize) bool {
1034 return ctx.chars[a] < ctx.chars[b];
1035 }
1036 }{ .chars = sliced.items(.chr) });
1037
1038 var i: u32 = undefined;
1039 var j: u32 = 6;
1040 var c: u8 = 'a';
1041
1042 while (j < 21) {
1043 i = j;
1044 j += 5;
1045 var n: u32 = 3;
1046 for (sliced.items(.chr)[i..j], sliced.items(.score)[i..j]) |chr, score| {
1047 try testing.expectEqual(score, n);
1048 try testing.expectEqual(chr, c);
1049 n += 1;
1050 }
1051 c += 1;
1052 }
1053}
1054
1055test "0 sized struct field" {
1056 const ally = testing.allocator;
1057
1058 const Foo = struct {
1059 a: u0,
1060 b: f32,
1061 };
1062
1063 var list: MultiArrayList(Foo) = .empty;
1064 defer list.deinit(ally);
1065
1066 try testing.expectEqualSlices(u0, &[_]u0{}, list.items(.a));
1067 try testing.expectEqualSlices(f32, &[_]f32{}, list.items(.b));
1068
1069 try list.append(ally, .{ .a = 0, .b = 42.0 });
1070 try testing.expectEqualSlices(u0, &[_]u0{0}, list.items(.a));
1071 try testing.expectEqualSlices(f32, &[_]f32{42.0}, list.items(.b));
1072
1073 try list.insert(ally, 0, .{ .a = 0, .b = -1.0 });
1074 try testing.expectEqualSlices(u0, &[_]u0{ 0, 0 }, list.items(.a));
1075 try testing.expectEqualSlices(f32, &[_]f32{ -1.0, 42.0 }, list.items(.b));
1076
1077 list.swapRemove(list.len - 1);
1078 try testing.expectEqualSlices(u0, &[_]u0{0}, list.items(.a));
1079 try testing.expectEqualSlices(f32, &[_]f32{-1.0}, list.items(.b));
1080}
1081
1082test "0 sized struct" {
1083 const ally = testing.allocator;
1084
1085 const Foo = struct {
1086 a: u0,
1087 };
1088
1089 var list: MultiArrayList(Foo) = .empty;
1090 defer list.deinit(ally);
1091
1092 try testing.expectEqualSlices(u0, &[_]u0{}, list.items(.a));
1093
1094 try list.append(ally, .{ .a = 0 });
1095 try testing.expectEqualSlices(u0, &[_]u0{0}, list.items(.a));
1096
1097 try list.insert(ally, 0, .{ .a = 0 });
1098 try testing.expectEqualSlices(u0, &[_]u0{ 0, 0 }, list.items(.a));
1099
1100 list.swapRemove(list.len - 1);
1101 try testing.expectEqualSlices(u0, &[_]u0{0}, list.items(.a));
1102}
1103
1104test "struct with many fields" {
1105 const ManyFields = struct {
1106 fn Type(count: comptime_int) type {
1107 @setEvalBranchQuota(50000);
1108 var field_names: [count][]const u8 = undefined;
1109 for (&field_names, 0..) |*n, i| n.* = std.fmt.comptimePrint("a{d}", .{i});
1110 return @Struct(.@"extern", null, &field_names, &@splat(u32), &@splat(.{}));
1111 }
1112
1113 fn doTest(ally: std.mem.Allocator, count: comptime_int) !void {
1114 var list: MultiArrayList(Type(count)) = .empty;
1115 defer list.deinit(ally);
1116
1117 try list.resize(ally, 1);
1118 list.items(.a0)[0] = 42;
1119 }
1120 };
1121
1122 try ManyFields.doTest(testing.allocator, 25);
1123 try ManyFields.doTest(testing.allocator, 50);
1124 try ManyFields.doTest(testing.allocator, 100);
1125 try ManyFields.doTest(testing.allocator, 200);
1126}
1127
1128test "orderedRemoveMany" {
1129 const gpa = testing.allocator;
1130
1131 var list: MultiArrayList(struct { x: usize }) = .empty;
1132 defer list.deinit(gpa);
1133
1134 for (0..10) |n| {
1135 try list.append(gpa, .{ .x = n });
1136 }
1137
1138 list.orderedRemoveMany(&.{ 1, 5, 5, 7, 9 });
1139 try testing.expectEqualSlices(usize, &.{ 0, 2, 3, 4, 6, 8 }, list.items(.x));
1140
1141 list.orderedRemoveMany(&.{0});
1142 try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, list.items(.x));
1143
1144 list.orderedRemoveMany(&.{});
1145 try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, list.items(.x));
1146
1147 list.orderedRemoveMany(&.{ 1, 2, 3, 4 });
1148 try testing.expectEqualSlices(usize, &.{2}, list.items(.x));
1149
1150 list.orderedRemoveMany(&.{0});
1151 try testing.expectEqualSlices(usize, &.{}, list.items(.x));
1152}