1//! An ArrayList that grows backwards. Counts nested prefix length fields
2//! in O(n) instead of O(n^depth) at the cost of extra buffering.
3//!
4//! Laid out in memory like:
5//! capacity |--------------------------|
6//! data |-------------|
7
8const std = @import("std");
9const Allocator = std.mem.Allocator;
10const assert = std.debug.assert;
11const testing = std.testing;
12
13data: []u8,
14capacity: usize,
15allocator: Allocator,
16
17const ArrayListReverse = @This();
18const Error = Allocator.Error;
19
20pub fn init(allocator: Allocator) ArrayListReverse {
21 return .{ .data = &.{}, .capacity = 0, .allocator = allocator };
22}
23
24pub fn deinit(self: *ArrayListReverse) void {
25 self.allocator.free(self.allocatedSlice());
26}
27
28pub fn ensureCapacity(self: *ArrayListReverse, new_capacity: usize) Error!void {
29 if (self.capacity >= new_capacity) return;
30
31 const old_memory = self.allocatedSlice();
32 // Just make a new allocation to not worry about aliasing.
33 const new_memory = try self.allocator.alloc(u8, new_capacity);
34 @memcpy(new_memory[new_capacity - self.data.len ..], self.data);
35 self.allocator.free(old_memory);
36 self.data.ptr = new_memory.ptr + new_capacity - self.data.len;
37 self.capacity = new_memory.len;
38}
39
40pub fn prependSlice(self: *ArrayListReverse, data: []const u8) Error!void {
41 try self.ensureCapacity(self.data.len + data.len);
42 const old_len = self.data.len;
43 const new_len = old_len + data.len;
44 assert(new_len <= self.capacity);
45 self.data.len = new_len;
46
47 const end = self.data.ptr;
48 const begin = end - data.len;
49 const slice = begin[0..data.len];
50 @memcpy(slice, data);
51 self.data.ptr = begin;
52}
53
54fn prependSliceSize(self: *ArrayListReverse, data: []const u8) Error!usize {
55 try self.prependSlice(data);
56 return data.len;
57}
58
59fn allocatedSlice(self: *ArrayListReverse) []u8 {
60 return (self.data.ptr + self.data.len - self.capacity)[0..self.capacity];
61}
62
63/// Invalidates all element pointers.
64pub fn clearAndFree(self: *ArrayListReverse) void {
65 self.allocator.free(self.allocatedSlice());
66 self.data.len = 0;
67 self.capacity = 0;
68}
69
70/// The caller owns the returned memory.
71/// Capacity is cleared, making deinit() safe but unnecessary to call.
72pub fn toOwnedSlice(self: *ArrayListReverse) Error![]u8 {
73 const new_memory = try self.allocator.alloc(u8, self.data.len);
74 @memcpy(new_memory, self.data);
75 @memset(self.data, undefined);
76 self.clearAndFree();
77 return new_memory;
78}
79
80test ArrayListReverse {
81 var b = ArrayListReverse.init(testing.allocator);
82 defer b.deinit();
83 const data: []const u8 = &.{ 4, 5, 6 };
84 try b.prependSlice(data);
85 try testing.expectEqual(data.len, b.data.len);
86 try testing.expectEqualSlices(u8, data, b.data);
87
88 const data2: []const u8 = &.{ 1, 2, 3 };
89 try b.prependSlice(data2);
90 try testing.expectEqual(data.len + data2.len, b.data.len);
91 try testing.expectEqualSlices(u8, data2 ++ data, b.data);
92}