diff options
Diffstat (limited to 'lib/std/multi_array_list.zig')
| -rw-r--r-- | lib/std/multi_array_list.zig | 160 |
1 files changed, 137 insertions, 23 deletions
diff --git a/lib/std/multi_array_list.zig b/lib/std/multi_array_list.zig index 35df5e8523..c96af48cb2 100644 --- a/lib/std/multi_array_list.zig +++ b/lib/std/multi_array_list.zig @@ -10,6 +10,15 @@ const mem = std.mem; const Allocator = mem.Allocator; const testing = std.testing; +/// A MultiArrayList stores a list of a struct type. +/// Instead of storing a single list of items, MultiArrayList +/// stores separate lists for each field of the struct. +/// This allows for memory savings if the struct has padding, +/// and also improves cache usage if only some fields 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. pub fn MultiArrayList(comptime S: type) type { return struct { bytes: [*]align(@alignOf(S)) u8 = undefined, @@ -20,6 +29,10 @@ pub fn MultiArrayList(comptime S: type) type { pub const Field = meta.FieldEnum(S); + /// 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 @enumToInt() on the Field enum @@ -29,11 +42,12 @@ pub fn MultiArrayList(comptime S: type) type { pub fn items(self: Slice, comptime field: Field) []FieldType(field) { const F = FieldType(field); - if (self.len == 0) { + if (self.capacity == 0) { return &[_]F{}; } const byte_ptr = self.ptrs[@enumToInt(field)]; - const casted_ptr = @ptrCast([*]F, @alignCast(@alignOf(F), byte_ptr)); + const casted_ptr: [*]F = if (@sizeOf([*]F) == 0) undefined + else @ptrCast([*]F, @alignCast(@alignOf(F), byte_ptr)); return casted_ptr[0..self.len]; } @@ -74,12 +88,12 @@ pub fn MultiArrayList(comptime S: type) type { data[i] = .{ .size = @sizeOf(field_info.field_type), .size_index = i, - .alignment = field_info.alignment, + .alignment = if (@sizeOf(field_info.field_type) == 0) 1 else field_info.alignment, }; } const Sort = struct { fn lessThan(trash: *i32, lhs: Data, rhs: Data) bool { - return lhs.alignment >= rhs.alignment; + return lhs.alignment > rhs.alignment; } }; var trash: i32 = undefined; // workaround for stage1 compiler bug @@ -109,6 +123,9 @@ pub fn MultiArrayList(comptime S: type) type { 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, @@ -123,6 +140,9 @@ pub fn MultiArrayList(comptime S: type) type { 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); } @@ -159,6 +179,72 @@ pub fn MultiArrayList(comptime S: type) type { self.set(self.len - 1, elem); } + /// Extend the list by 1 element, asserting `self.capacity` + /// is sufficient to hold an additional item. Returns the + /// newly reserved index with uninitialized data. + pub fn addOneAssumeCapacity(self: *Self) usize { + assert(self.len < self.capacity); + const index = self.len; + self.len += 1; + return index; + } + + /// Inserts an item into an ordered list. Shifts all elements + /// after and including the specified index back by one and + /// sets the given index to the specified element. May reallocate + /// and invalidate iterators. + pub fn insert(self: *Self, gpa: *Allocator, index: usize, elem: S) void { + try self.ensureCapacity(gpa, self.len + 1); + self.insertAssumeCapacity(index, elem); + } + + /// Inserts an item into an ordered list which has room for it. + /// Shifts all elements after and including the specified index + /// back by one and sets the given index to the specified element. + /// Will not reallocate the array, does not invalidate iterators. + pub fn insertAssumeCapacity(self: *Self, index: usize, elem: S) void { + assert(self.len < self.capacity); + assert(index <= self.len); + self.len += 1; + const slices = self.slice(); + inline for (fields) |field_info, field_index| { + const field_slice = slices.items(@intToEnum(Field, field_index)); + var i: usize = self.len-1; + while (i > index) : (i -= 1) { + field_slice[i] = field_slice[i-1]; + } + field_slice[index] = @field(elem, field_info.name); + } + } + + /// 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 (fields) |field_info, i| { + const field_slice = slices.items(@intToEnum(Field, 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 (fields) |field_info, field_index| { + const field_slice = slices.items(@intToEnum(Field, 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; + } + /// 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) !void { @@ -186,13 +272,15 @@ pub fn MultiArrayList(comptime S: type) type { ) catch { const self_slice = self.slice(); inline for (fields) |field_info, i| { - const field = @intToEnum(Field, i); - const dest_slice = self_slice.items(field)[new_len..]; - const byte_count = dest_slice.len * @sizeOf(field_info.field_type); - // 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(@ptrCast([*]u8, dest_slice.ptr), undefined, byte_count); + if (@sizeOf(field_info.field_type) != 0) { + const field = @intToEnum(Field, i); + const dest_slice = self_slice.items(field)[new_len..]; + const byte_count = dest_slice.len * @sizeOf(field_info.field_type); + // 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(@ptrCast([*]u8, dest_slice.ptr), undefined, byte_count); + } } self.len = new_len; return; @@ -206,12 +294,14 @@ pub fn MultiArrayList(comptime S: type) type { const self_slice = self.slice(); const other_slice = other.slice(); inline for (fields) |field_info, i| { - const field = @intToEnum(Field, i); - // TODO we should be able to use std.mem.copy here but it causes a - // test failure on aarch64 with -OReleaseFast - const src_slice = mem.sliceAsBytes(self_slice.items(field)); - const dst_slice = mem.sliceAsBytes(other_slice.items(field)); - @memcpy(dst_slice.ptr, src_slice.ptr, src_slice.len); + if (@sizeOf(field_info.field_type) != 0) { + const field = @intToEnum(Field, i); + // TODO we should be able to use std.mem.copy here but it causes a + // test failure on aarch64 with -OReleaseFast + const src_slice = mem.sliceAsBytes(self_slice.items(field)); + const dst_slice = mem.sliceAsBytes(other_slice.items(field)); + @memcpy(dst_slice.ptr, src_slice.ptr, src_slice.len); + } } gpa.free(self.allocatedBytes()); self.* = other; @@ -273,17 +363,41 @@ pub fn MultiArrayList(comptime S: type) type { const self_slice = self.slice(); const other_slice = other.slice(); inline for (fields) |field_info, i| { - const field = @intToEnum(Field, i); - // TODO we should be able to use std.mem.copy here but it causes a - // test failure on aarch64 with -OReleaseFast - const src_slice = mem.sliceAsBytes(self_slice.items(field)); - const dst_slice = mem.sliceAsBytes(other_slice.items(field)); - @memcpy(dst_slice.ptr, src_slice.ptr, src_slice.len); + if (@sizeOf(field_info.field_type) != 0) { + const field = @intToEnum(Field, i); + // TODO we should be able to use std.mem.copy here but it causes a + // test failure on aarch64 with -OReleaseFast + const src_slice = mem.sliceAsBytes(self_slice.items(field)); + const dst_slice = mem.sliceAsBytes(other_slice.items(field)); + @memcpy(dst_slice.ptr, src_slice.ptr, src_slice.len); + } } 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) !Self { + var result = Self{}; + errdefer result.deinit(gpa); + try result.ensureCapacity(gpa, self.len); + result.len = self.len; + const self_slice = self.slice(); + const result_slice = result.slice(); + inline for (fields) |field_info, i| { + if (@sizeOf(field_info.field_type) != 0) { + const field = @intToEnum(Field, i); + // TODO we should be able to use std.mem.copy here but it causes a + // test failure on aarch64 with -OReleaseFast + const src_slice = mem.sliceAsBytes(self_slice.items(field)); + const dst_slice = mem.sliceAsBytes(result_slice.items(field)); + @memcpy(dst_slice.ptr, src_slice.ptr, src_slice.len); + } + } + return result; + } + fn capacityInBytes(capacity: usize) usize { const sizes_vector: std.meta.Vector(sizes.bytes.len, usize) = sizes.bytes; const capacity_vector = @splat(sizes.bytes.len, capacity); |