反向增长的 ArrayList。以额外缓冲为代价,将嵌套 长度前缀字段的计数复杂度从 O(n^depth) 降至 O(n)。
内存布局如下: capacity |--------------------------| data |-------------|
字段
std.crypto.codecs.asn1.der.ArrayListReverse.allocatedSlice
函数
fn allocatedSlice(self: *ArrayListReverse) []u8
参数
self: *ArrayListReverse
std.crypto.codecs.asn1.der.ArrayListReverse.Allocator
别名
别名目标 std.mem.Allocator
std.crypto.codecs.asn1.der.ArrayListReverse.ArrayListReverse
别名
std.crypto.codecs.asn1.der.ArrayListReverse.assert
别名
别名目标 std.debug.assert
std.crypto.codecs.asn1.der.ArrayListReverse.clearAndFree
函数
使所有元素指针失效。
pub fn clearAndFree(self: *ArrayListReverse) void
参数
self: *ArrayListReverse
std.crypto.codecs.asn1.der.ArrayListReverse.deinit
函数
pub fn deinit(self: *ArrayListReverse) void
参数
self: *ArrayListReverse
std.crypto.codecs.asn1.der.ArrayListReverse.ensureCapacity
函数
pub fn ensureCapacity(self: *ArrayListReverse, new_capacity: usize) Error!void
参数
self: *ArrayListReverse
new_capacity: usize
错误
- OutOfMemory Error
std.crypto.codecs.asn1.der.ArrayListReverse.Error
别名
std.crypto.codecs.asn1.der.ArrayListReverse.init
函数
pub fn init(allocator: Allocator) ArrayListReverse
参数
allocator: Allocator
std.crypto.codecs.asn1.der.ArrayListReverse.prependSlice
函数
pub fn prependSlice(self: *ArrayListReverse, data: []const u8) Error!void
参数
self: *ArrayListReverse
data: []const u8
错误
- OutOfMemory Error
std.crypto.codecs.asn1.der.ArrayListReverse.prependSliceSize
函数
fn prependSliceSize(self: *ArrayListReverse, data: []const u8) Error!usize
参数
self: *ArrayListReverse
data: []const u8
错误
- OutOfMemory Error
std.crypto.codecs.asn1.der.ArrayListReverse.std
别名
别名目标 std
std.crypto.codecs.asn1.der.ArrayListReverse.testing
别名
别名目标 std.testing
std.crypto.codecs.asn1.der.ArrayListReverse.toOwnedSlice
函数
调用方拥有返回的内存。 容量会被清零,因此调用 deinit() 安全但无必要。
pub fn toOwnedSlice(self: *ArrayListReverse) Error![]u8
参数
self: *ArrayListReverse
错误
- OutOfMemory Error
源码
std/crypto/codecs/asn1/der/ArrayListReverse.zig
//! 反向增长的 ArrayList。以额外缓冲为代价,将嵌套
//! 长度前缀字段的计数复杂度从 O(n^depth) 降至 O(n)。
//!
//! 内存布局如下:
//! capacity |--------------------------|
//! data |-------------|
const std = @import("std");
const Allocator = std.mem.Allocator;
const assert = std.debug.assert;
const testing = std.testing;
data: []u8,
capacity: usize,
allocator: Allocator,
const ArrayListReverse = @This();
const Error = Allocator.Error;
pub fn init(allocator: Allocator) ArrayListReverse {
return .{ .data = &.{}, .capacity = 0, .allocator = allocator };
}
pub fn deinit(self: *ArrayListReverse) void {
self.allocator.free(self.allocatedSlice());
}
pub fn ensureCapacity(self: *ArrayListReverse, new_capacity: usize) Error!void {
if (self.capacity >= new_capacity) return;
const old_memory = self.allocatedSlice();
// 直接进行新的分配,以免考虑别名问题。
const new_memory = try self.allocator.alloc(u8, new_capacity);
@memcpy(new_memory[new_capacity - self.data.len ..], self.data);
self.allocator.free(old_memory);
self.data.ptr = new_memory.ptr + new_capacity - self.data.len;
self.capacity = new_memory.len;
}
pub fn prependSlice(self: *ArrayListReverse, data: []const u8) Error!void {
try self.ensureCapacity(self.data.len + data.len);
const old_len = self.data.len;
const new_len = old_len + data.len;
assert(new_len <= self.capacity);
self.data.len = new_len;
const end = self.data.ptr;
const begin = end - data.len;
const slice = begin[0..data.len];
@memcpy(slice, data);
self.data.ptr = begin;
}
fn prependSliceSize(self: *ArrayListReverse, data: []const u8) Error!usize {
try self.prependSlice(data);
return data.len;
}
fn allocatedSlice(self: *ArrayListReverse) []u8 {
return (self.data.ptr + self.data.len - self.capacity)[0..self.capacity];
}
/// 使所有元素指针失效。
pub fn clearAndFree(self: *ArrayListReverse) void {
self.allocator.free(self.allocatedSlice());
self.data.len = 0;
self.capacity = 0;
}
/// 调用方拥有返回的内存。
/// 容量会被清零,因此调用 deinit() 安全但无必要。
pub fn toOwnedSlice(self: *ArrayListReverse) Error![]u8 {
const new_memory = try self.allocator.alloc(u8, self.data.len);
@memcpy(new_memory, self.data);
@memset(self.data, undefined);
self.clearAndFree();
return new_memory;
}
test ArrayListReverse {
var b = ArrayListReverse.init(testing.allocator);
defer b.deinit();
const data: []const u8 = &.{ 4, 5, 6 };
try b.prependSlice(data);
try testing.expectEqual(data.len, b.data.len);
try testing.expectEqualSlices(u8, data, b.data);
const data2: []const u8 = &.{ 1, 2, 3 };
try b.prependSlice(data2);
try testing.expectEqual(data.len + data2.len, b.data.len);
try testing.expectEqualSlices(u8, data2 ++ data, b.data);
}