Merge pull request #8975 from SpexGuy/hash-map-updates

Breaking hash map changes for 0.8.0

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