1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
|
//! A list with its capacity in its type: plain data, so it can live in
//! State (no pointers) and migrate there element by element.
const std = @import("std");
/// `buffer` and `len` are public fields, so the host's console and scripts
/// reach elements by path (`boids.buffer[3].pos[0]`, `boids.len`).
///
/// Every method clamps `len` to the capacity: after a reload that shrinks
/// the capacity, a saved `len` may be larger than the new buffer, and the
/// list then holds `capacity` elements rather than indexing out of bounds.
/// The names and errors are std's (`ArrayList`'s bounded methods).
pub fn List(comptime T: type, comptime cap: u32) type {
return struct {
const Self = @This();
pub const capacity = cap;
buffer: [cap]T = default_buffer,
len: u32 = 0,
/// T's own defaults when it has them for every field, zeroes for
/// numbers, the first tag for enums; otherwise undefined. Never
/// `std.mem.zeroes`, which fails on enums with no 0 tag.
const default_buffer: [cap]T = if (defaultOf(T)) |d| @splat(d) else undefined;
pub fn slice(l: *Self) []T {
return l.buffer[0..l.count()];
}
pub fn constSlice(l: *const Self) []const T {
return l.buffer[0..l.count()];
}
/// `len`, clamped to the capacity.
pub fn count(l: *const Self) u32 {
return @min(l.len, cap);
}
pub fn appendBounded(l: *Self, item: T) error{OutOfMemory}!void {
const n = l.count();
if (n == cap) return error.OutOfMemory;
l.buffer[n] = item;
l.len = n + 1;
}
/// Removes the element at `i`, keeping the order of the rest.
pub fn orderedRemove(l: *Self, i: u32) T {
const n = l.count();
const item = l.buffer[i];
std.mem.copyForwards(T, l.buffer[i .. n - 1], l.buffer[i + 1 .. n]);
l.len = n - 1;
return item;
}
/// Removes the element at `i`, moving the last one into its place.
pub fn swapRemove(l: *Self, i: u32) T {
const n = l.count();
const item = l.buffer[i];
l.buffer[i] = l.buffer[n - 1];
l.len = n - 1;
return item;
}
pub fn clear(l: *Self) void {
l.len = 0;
}
};
}
fn defaultOf(comptime T: type) ?T {
return switch (@typeInfo(T)) {
.int, .float, .vector => std.mem.zeroes(T),
.bool => false,
.optional => null,
.array => |a| if (defaultOf(a.child)) |d| @splat(d) else null,
.@"enum" => |e| if (e.mode == .exhaustive) @field(T, e.field_names[0]) else @enumFromInt(0),
.@"struct" => |s| {
for (s.field_attrs) |attrs| if (attrs.default_value_ptr == null) return null;
return .{};
},
else => null,
};
}
test "append, remove, clamp after a capacity shrink" {
const Kind = enum(u8) { a = 1, b = 2 };
const Item = struct { kind: Kind = .b, x: f32 = 1 };
var l: List(Item, 4) = .{};
try std.testing.expectEqual(Kind.b, l.buffer[3].kind);
for (0..4) |i| try l.appendBounded(.{ .x = @floatFromInt(i) });
try std.testing.expectError(error.OutOfMemory, l.appendBounded(.{}));
try std.testing.expectEqual(@as(f32, 1), l.orderedRemove(1).x);
try std.testing.expectEqual(@as(f32, 2), l.constSlice()[1].x);
try std.testing.expectEqual(@as(f32, 0), l.swapRemove(0).x);
try std.testing.expectEqual(@as(f32, 3), l.slice()[0].x);
try std.testing.expectEqual(@as(usize, 2), l.slice().len);
// A saved len from a bigger list.
l.len = 10;
try std.testing.expectEqual(@as(usize, 4), l.constSlice().len);
try std.testing.expectError(error.OutOfMemory, l.appendBounded(.{}));
_ = l.swapRemove(0);
try std.testing.expectEqual(@as(u32, 3), l.len);
}
test "defaults for element types without struct defaults" {
const E = enum(u8) { one = 1, two = 2 };
const a: List(E, 3) = .{};
try std.testing.expectEqual(E.one, a.buffer[2]);
const b: List(f32, 3) = .{};
try std.testing.expectEqual(@as(f32, 0), b.buffer[1]);
const c: List(@Vector(2, f32), 2) = .{};
try std.testing.expectEqual(@as(f32, 0), c.buffer[1][0]);
const NoDefault = struct { x: f32 };
const d: List(NoDefault, 2) = .{};
try std.testing.expectEqual(@as(u32, 0), d.len);
}
|