diff options
Diffstat (limited to 'lib/std/array_list.zig')
| -rw-r--r-- | lib/std/array_list.zig | 225 |
1 files changed, 165 insertions, 60 deletions
diff --git a/lib/std/array_list.zig b/lib/std/array_list.zig index ab47510cb7..f30a86d8f7 100644 --- a/lib/std/array_list.zig +++ b/lib/std/array_list.zig @@ -1,5 +1,5 @@ // SPDX-License-Identifier: MIT -// Copyright (c) 2015-2020 Zig Contributors +// Copyright (c) 2015-2021 Zig Contributors // This file is part of [zig](https://ziglang.org/), which is MIT licensed. // The MIT license requires this copyright notice to be included in all copies // and substantial portions of the software. @@ -12,10 +12,20 @@ const Allocator = mem.Allocator; /// A contiguous, growable list of items in memory. /// This is a wrapper around an array of T values. Initialize with `init`. +/// +/// This struct internally stores a `std.mem.Allocator` for memory management. +/// To manually specify an allocator with each method call see `ArrayListUnmanaged`. pub fn ArrayList(comptime T: type) type { return ArrayListAligned(T, null); } +/// A contiguous, growable list of arbitrarily aligned items in memory. +/// This is a wrapper around an array of T values aligned to `alignment`-byte +/// addresses. If the specified alignment is `null`, then `@alignOf(T)` is used. +/// Initialize with `init`. +/// +/// This struct internally stores a `std.mem.Allocator` for memory management. +/// To manually specify an allocator with each method call see `ArrayListAlignedUnmanaged`. pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { if (alignment) |a| { if (a == @alignOf(T)) { @@ -24,9 +34,18 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { } return struct { const Self = @This(); - - /// Content of the ArrayList + /// Contents of the list. Pointers to elements in this slice are + /// **invalid after resizing operations** on the ArrayList, unless the + /// operation explicitly either: (1) states otherwise or (2) lists the + /// invalidated pointers. + /// + /// The allocator used determines how element pointers are + /// invalidated, so the behavior may vary between lists. To avoid + /// illegal behavior, take into account the above paragraph plus the + /// explicit statements given in each method. items: Slice, + /// How many T values this list can hold without allocating + /// additional memory. capacity: usize, allocator: *Allocator, @@ -42,7 +61,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { }; } - /// Initialize with capacity to hold at least num elements. + /// Initialize with capacity to hold at least `num` elements. /// Deinitialize with `deinit` or use `toOwnedSlice`. pub fn initCapacity(allocator: *Allocator, num: usize) !Self { var self = Self.init(allocator); @@ -79,11 +98,23 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { }; } + /// Initializes an ArrayListUnmanaged with the `items` and `capacity` fields + /// of this ArrayList. This ArrayList retains ownership of underlying memory. + /// Deprecated: use `moveToUnmanaged` which has different semantics. pub fn toUnmanaged(self: Self) ArrayListAlignedUnmanaged(T, alignment) { return .{ .items = self.items, .capacity = self.capacity }; } - /// The caller owns the returned memory. ArrayList becomes empty. + /// Initializes an ArrayListUnmanaged with the `items` and `capacity` fields + /// of this ArrayList. Empties this ArrayList. + pub fn moveToUnmanaged(self: *Self) ArrayListAlignedUnmanaged(T, alignment) { + const allocator = self.allocator; + const result = .{ .items = self.items, .capacity = self.capacity }; + self.* = init(allocator); + return result; + } + + /// The caller owns the returned memory. Empties this ArrayList. pub fn toOwnedSlice(self: *Self) Slice { const allocator = self.allocator; const result = allocator.shrink(self.allocatedSlice(), self.items.len); @@ -91,6 +122,13 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { return result; } + /// The caller owns the returned memory. Empties this ArrayList. + pub fn toOwnedSliceSentinel(self: *Self, comptime sentinel: T) ![:sentinel]T { + try self.append(sentinel); + const result = self.toOwnedSlice(); + return result[0 .. result.len - 1 :sentinel]; + } + /// Insert `item` at index `n` by moving `list[n .. list.len]` to make room. /// This operation is O(N). pub fn insert(self: *Self, n: usize, item: T) !void { @@ -111,9 +149,10 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { mem.copy(T, self.items[i .. i + items.len], items); } - /// Replace range of elements `list[start..start+len]` with `new_items` - /// grows list if `len < new_items.len`. may allocate - /// shrinks list if `len > new_items.len` + /// Replace range of elements `list[start..start+len]` with `new_items`. + /// Grows list if `len < new_items.len`. + /// Shrinks list if `len > new_items.len`. + /// Invalidates pointers if this ArrayList is resized. pub fn replaceRange(self: *Self, start: usize, len: usize, new_items: SliceConst) !void { const after_range = start + len; const range = self.items[start..after_range]; @@ -144,15 +183,18 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { new_item_ptr.* = item; } - /// Extend the list by 1 element, but asserting `self.capacity` - /// is sufficient to hold an additional item. + /// Extend the list by 1 element, but assert `self.capacity` + /// is sufficient to hold an additional item. **Does not** + /// invalidate pointers. pub fn appendAssumeCapacity(self: *Self, item: T) void { const new_item_ptr = self.addOneAssumeCapacity(); new_item_ptr.* = item; } - /// Remove the element at index `i` from the list and return its value. + /// Remove the element at index `i`, shift elements after index + /// `i` forward, and return the removed element. /// Asserts the array has at least one item. + /// Invalidates pointers to end of list. /// This operation is O(N). pub fn orderedRemove(self: *Self, i: usize) T { const newlen = self.items.len - 1; @@ -184,7 +226,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { } /// Append the slice of items to the list, asserting the capacity is already - /// enough to store the new items. + /// enough to store the new items. **Does not** invalidate pointers. pub fn appendSliceAssumeCapacity(self: *Self, items: SliceConst) void { const oldlen = self.items.len; const newlen = self.items.len + items.len; @@ -200,9 +242,6 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { return .{ .context = self }; } - /// Deprecated: use `writer` - pub const outStream = writer; - /// Same as `append` except it returns the number of bytes written, which is always the same /// as `m.len`. The purpose of this function existing is to match `std.io.Writer` API. fn appendWrite(self: *Self, m: []const u8) !usize { @@ -220,7 +259,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { } /// Append a value to the list `n` times. - /// Asserts the capacity is enough. + /// Asserts the capacity is enough. **Does not** invalidate pointers. pub fn appendNTimesAssumeCapacity(self: *Self, value: T, n: usize) void { const new_len = self.items.len + n; assert(new_len <= self.capacity); @@ -236,8 +275,8 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { } /// Reduce allocated capacity to `new_len`. - /// Invalidates element pointers. - pub fn shrink(self: *Self, new_len: usize) void { + /// May invalidate element pointers. + pub fn shrinkAndFree(self: *Self, new_len: usize) void { assert(new_len <= self.items.len); self.items = self.allocator.realloc(self.allocatedSlice(), new_len) catch |e| switch (e) { @@ -250,13 +289,14 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { } /// Reduce length to `new_len`. - /// Invalidates element pointers. - /// Keeps capacity the same. + /// Invalidates pointers for the elements `items[new_len..]`. pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void { assert(new_len <= self.items.len); self.items.len = new_len; } + /// Modify the array so that it can hold at least `new_capacity` items. + /// Invalidates pointers if additional memory is needed. pub fn ensureCapacity(self: *Self, new_capacity: usize) !void { var better_capacity = self.capacity; if (better_capacity >= new_capacity) return; @@ -273,14 +313,13 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { } /// Increases the array's length to match the full capacity that is already allocated. - /// The new elements have `undefined` values. This operation does not invalidate any - /// element pointers. + /// The new elements have `undefined` values. **Does not** invalidate pointers. pub fn expandToCapacity(self: *Self) void { self.items.len = self.capacity; } /// Increase length by 1, returning pointer to the new item. - /// The returned pointer becomes invalid when the list is resized. + /// The returned pointer becomes invalid when the list resized. pub fn addOne(self: *Self) !*T { const newlen = self.items.len + 1; try self.ensureCapacity(newlen); @@ -290,6 +329,7 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { /// Increase length by 1, returning pointer to the new item. /// Asserts that there is already space for the new item without allocating more. /// The returned pointer becomes invalid when the list is resized. + /// **Does not** invalidate element pointers. pub fn addOneAssumeCapacity(self: *Self) *T { assert(self.items.len < self.capacity); @@ -299,6 +339,8 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { /// Resize the array, adding `n` new elements, which have `undefined` values. /// The return value is an array pointing to the newly allocated elements. + /// The returned pointer becomes invalid when the list is resized. + /// Resizes list if `self.capacity` is not large enough. pub fn addManyAsArray(self: *Self, comptime n: usize) !*[n]T { const prev_len = self.items.len; try self.resize(self.items.len + n); @@ -308,6 +350,8 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { /// Resize the array, adding `n` new elements, which have `undefined` values. /// The return value is an array pointing to the newly allocated elements. /// Asserts that there is already space for the new item without allocating more. + /// **Does not** invalidate element pointers. + /// The returned pointer becomes invalid when the list is resized. pub fn addManyAsArrayAssumeCapacity(self: *Self, comptime n: usize) *[n]T { assert(self.items.len + n <= self.capacity); const prev_len = self.items.len; @@ -317,33 +361,51 @@ pub fn ArrayListAligned(comptime T: type, comptime alignment: ?u29) type { /// Remove and return the last element from the list. /// Asserts the list has at least one item. + /// Invalidates pointers to the removed element. pub fn pop(self: *Self) T { const val = self.items[self.items.len - 1]; self.items.len -= 1; return val; } - /// Remove and return the last element from the list. - /// If the list is empty, returns `null`. + /// Remove and return the last element from the list, or + /// return `null` if list is empty. + /// Invalidates pointers to the removed element, if any. pub fn popOrNull(self: *Self) ?T { if (self.items.len == 0) return null; return self.pop(); } - // For a nicer API, `items.len` is the length, not the capacity. - // This requires "unsafe" slicing. - fn allocatedSlice(self: Self) Slice { + /// Returns a slice of all the items plus the extra capacity, whose memory + /// contents are `undefined`. + pub fn allocatedSlice(self: Self) Slice { + // For a nicer API, `items.len` is the length, not the capacity. + // This requires "unsafe" slicing. return self.items.ptr[0..self.capacity]; } + + /// Returns a slice of only the extra capacity after items. + /// This can be useful for writing directly into an ArrayList. + /// Note that such an operation must be followed up with a direct + /// modification of `self.items.len`. + pub fn unusedCapacitySlice(self: Self) Slice { + return self.allocatedSlice()[self.items.len..]; + } }; } -/// Bring-your-own allocator with every function call. -/// Initialize directly and deinitialize with `deinit` or use `toOwnedSlice`. +/// An ArrayList, but the allocator is passed as a parameter to the relevant functions +/// rather than stored in the struct itself. The same allocator **must** be used throughout +/// the entire lifetime of an ArrayListUnmanaged. Initialize directly or with +/// `initCapacity`, and deinitialize with `deinit` or use `toOwnedSlice`. pub fn ArrayListUnmanaged(comptime T: type) type { return ArrayListAlignedUnmanaged(T, null); } +/// An ArrayListAligned, but the allocator is passed as a parameter to the relevant +/// functions rather than stored in the struct itself. The same allocator **must** +/// be used throughout the entire lifetime of an ArrayListAlignedUnmanaged. +/// Initialize directly or with `initCapacity`, and deinitialize with `deinit` or use `toOwnedSlice`. pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) type { if (alignment) |a| { if (a == @alignOf(T)) { @@ -352,9 +414,18 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ } return struct { const Self = @This(); - - /// Content of the ArrayList. + /// Contents of the list. Pointers to elements in this slice are + /// **invalid after resizing operations** on the ArrayList, unless the + /// operation explicitly either: (1) states otherwise or (2) lists the + /// invalidated pointers. + /// + /// The allocator used determines how element pointers are + /// invalidated, so the behavior may vary between lists. To avoid + /// illegal behavior, take into account the above paragraph plus the + /// explicit statements given in each method. items: Slice = &[_]T{}, + /// How many T values this list can hold without allocating + /// additional memory. capacity: usize = 0, pub const Slice = if (alignment) |a| ([]align(a) T) else []T; @@ -378,6 +449,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ self.* = undefined; } + /// Convert this list into an analogous memory-managed one. + /// The returned list has ownership of the underlying memory. pub fn toManaged(self: *Self, allocator: *Allocator) ArrayListAligned(T, alignment) { return .{ .items = self.items, .capacity = self.capacity, .allocator = allocator }; } @@ -389,8 +462,16 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ return result; } + /// The caller owns the returned memory. ArrayList becomes empty. + pub fn toOwnedSliceSentinel(self: *Self, allocator: *Allocator, comptime sentinel: T) ![:sentinel]T { + try self.append(allocator, sentinel); + const result = self.toOwnedSlice(allocator); + return result[0 .. result.len - 1 :sentinel]; + } + /// Insert `item` at index `n`. Moves `list[n .. list.len]` - /// to make room. + /// to higher indices to make room. + /// This operation is O(N). pub fn insert(self: *Self, allocator: *Allocator, n: usize, item: T) !void { try self.ensureCapacity(allocator, self.items.len + 1); self.items.len += 1; @@ -399,8 +480,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ self.items[n] = item; } - /// Insert slice `items` at index `i`. Moves - /// `list[i .. list.len]` to make room. + /// Insert slice `items` at index `i`. Moves `list[i .. list.len]` to + /// higher indicices make room. /// This operation is O(N). pub fn insertSlice(self: *Self, allocator: *Allocator, i: usize, items: SliceConst) !void { try self.ensureCapacity(allocator, self.items.len + items.len); @@ -411,8 +492,9 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ } /// Replace range of elements `list[start..start+len]` with `new_items` - /// grows list if `len < new_items.len`. may allocate - /// shrinks list if `len > new_items.len` + /// Grows list if `len < new_items.len`. + /// Shrinks list if `len > new_items.len` + /// Invalidates pointers if this ArrayList is resized. pub fn replaceRange(self: *Self, allocator: *Allocator, start: usize, len: usize, new_items: SliceConst) !void { var managed = self.toManaged(allocator); try managed.replaceRange(start, len, new_items); @@ -433,7 +515,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ } /// Remove the element at index `i` from the list and return its value. - /// Asserts the array has at least one item. + /// Asserts the array has at least one item. Invalidates pointers to + /// last element. /// This operation is O(N). pub fn orderedRemove(self: *Self, i: usize) T { const newlen = self.items.len - 1; @@ -448,6 +531,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ /// Removes the element at the specified index and returns it. /// The empty slot is filled from the end of the list. + /// Invalidates pointers to last element. /// This operation is O(1). pub fn swapRemove(self: *Self, i: usize) T { if (self.items.len - 1 == i) return self.pop(); @@ -474,14 +558,6 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ mem.copy(T, self.items[oldlen..], items); } - /// Same as `append` except it returns the number of bytes written, which is always the same - /// as `m.len`. The purpose of this function existing is to match `std.io.OutStream` API. - /// This function may be called only when `T` is `u8`. - fn appendWrite(self: *Self, allocator: *Allocator, m: []const u8) !usize { - try self.appendSlice(allocator, m); - return m.len; - } - /// Append a value to the list `n` times. /// Allocates more memory as necessary. pub fn appendNTimes(self: *Self, allocator: *Allocator, value: T, n: usize) !void { @@ -491,6 +567,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ } /// Append a value to the list `n` times. + /// **Does not** invalidate pointers. /// Asserts the capacity is enough. pub fn appendNTimesAssumeCapacity(self: *Self, value: T, n: usize) void { const new_len = self.items.len + n; @@ -500,15 +577,14 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ } /// Adjust the list's length to `new_len`. - /// Does not initialize added items if any. + /// Does not initialize added items, if any. pub fn resize(self: *Self, allocator: *Allocator, new_len: usize) !void { try self.ensureCapacity(allocator, new_len); self.items.len = new_len; } /// Reduce allocated capacity to `new_len`. - /// Invalidates element pointers. - pub fn shrink(self: *Self, allocator: *Allocator, new_len: usize) void { + pub fn shrinkAndFree(self: *Self, allocator: *Allocator, new_len: usize) void { assert(new_len <= self.items.len); self.items = allocator.realloc(self.allocatedSlice(), new_len) catch |e| switch (e) { @@ -521,13 +597,15 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ } /// Reduce length to `new_len`. - /// Invalidates element pointers. + /// Invalidates pointers to elements `items[new_len..]`. /// Keeps capacity the same. pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void { assert(new_len <= self.items.len); self.items.len = new_len; } + /// Modify the array so that it can hold at least `new_capacity` items. + /// Invalidates pointers if additional memory is needed. pub fn ensureCapacity(self: *Self, allocator: *Allocator, new_capacity: usize) !void { var better_capacity = self.capacity; if (better_capacity >= new_capacity) return; @@ -544,13 +622,13 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ /// Increases the array's length to match the full capacity that is already allocated. /// The new elements have `undefined` values. - /// This operation does not invalidate any element pointers. + /// **Does not** invalidate pointers. pub fn expandToCapacity(self: *Self) void { self.items.len = self.capacity; } /// Increase length by 1, returning pointer to the new item. - /// The returned pointer becomes invalid when the list is resized. + /// The returned pointer becomes invalid when the list resized. pub fn addOne(self: *Self, allocator: *Allocator) !*T { const newlen = self.items.len + 1; try self.ensureCapacity(allocator, newlen); @@ -559,8 +637,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ /// Increase length by 1, returning pointer to the new item. /// Asserts that there is already space for the new item without allocating more. - /// The returned pointer becomes invalid when the list is resized. - /// This operation does not invalidate any element pointers. + /// **Does not** invalidate pointers. + /// The returned pointer becomes invalid when the list resized. pub fn addOneAssumeCapacity(self: *Self) *T { assert(self.items.len < self.capacity); @@ -570,6 +648,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ /// Resize the array, adding `n` new elements, which have `undefined` values. /// The return value is an array pointing to the newly allocated elements. + /// The returned pointer becomes invalid when the list is resized. pub fn addManyAsArray(self: *Self, allocator: *Allocator, comptime n: usize) !*[n]T { const prev_len = self.items.len; try self.resize(allocator, self.items.len + n); @@ -579,6 +658,8 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ /// Resize the array, adding `n` new elements, which have `undefined` values. /// The return value is an array pointing to the newly allocated elements. /// Asserts that there is already space for the new item without allocating more. + /// **Does not** invalidate pointers. + /// The returned pointer becomes invalid when the list is resized. pub fn addManyAsArrayAssumeCapacity(self: *Self, comptime n: usize) *[n]T { assert(self.items.len + n <= self.capacity); const prev_len = self.items.len; @@ -588,7 +669,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ /// Remove and return the last element from the list. /// Asserts the list has at least one item. - /// This operation does not invalidate any element pointers. + /// Invalidates pointers to last element. pub fn pop(self: *Self) T { const val = self.items[self.items.len - 1]; self.items.len -= 1; @@ -597,7 +678,7 @@ pub fn ArrayListAlignedUnmanaged(comptime T: type, comptime alignment: ?u29) typ /// Remove and return the last element from the list. /// If the list is empty, returns `null`. - /// This operation does not invalidate any element pointers. + /// Invalidates pointers to last element. pub fn popOrNull(self: *Self) ?T { if (self.items.len == 0) return null; return self.pop(); @@ -1047,13 +1128,13 @@ test "std.ArrayList/ArrayListUnmanaged: ArrayList(T) of struct T" { } } -test "std.ArrayList(u8) implements outStream" { +test "std.ArrayList(u8) implements writer" { var buffer = ArrayList(u8).init(std.testing.allocator); defer buffer.deinit(); const x: i32 = 42; const y: i32 = 1234; - try buffer.outStream().print("x: {}\ny: {}\n", .{ x, y }); + try buffer.writer().print("x: {}\ny: {}\n", .{ x, y }); testing.expectEqualSlices(u8, "x: 42\ny: 1234\n", buffer.items); } @@ -1071,7 +1152,7 @@ test "std.ArrayList/ArrayListUnmanaged.shrink still sets length on error.OutOfMe try list.append(2); try list.append(3); - list.shrink(1); + list.shrinkAndFree(1); testing.expect(list.items.len == 1); } { @@ -1081,7 +1162,7 @@ test "std.ArrayList/ArrayListUnmanaged.shrink still sets length on error.OutOfMe try list.append(a, 2); try list.append(a, 3); - list.shrink(a, 1); + list.shrinkAndFree(a, 1); testing.expect(list.items.len == 1); } } @@ -1121,3 +1202,27 @@ test "std.ArrayList/ArrayListUnmanaged.addManyAsArray" { testing.expectEqualSlices(u8, list.items, "aoeuasdf"); } } + +test "std.ArrayList/ArrayListUnmanaged.toOwnedSliceSentinel" { + const a = testing.allocator; + { + var list = ArrayList(u8).init(a); + defer list.deinit(); + + try list.appendSlice("foobar"); + + const result = try list.toOwnedSliceSentinel(0); + defer a.free(result); + testing.expectEqualStrings(result, mem.spanZ(result.ptr)); + } + { + var list = ArrayListUnmanaged(u8){}; + defer list.deinit(a); + + try list.appendSlice(a, "foobar"); + + const result = try list.toOwnedSliceSentinel(a, 0); + defer a.free(result); + testing.expectEqualStrings(result, mem.spanZ(result.ptr)); + } +} |