std.deque.addOrOom
函数
整数加法,溢出时返回 error.OutOfMemory。
fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize
参数
a: usize
b: usize
错误
- OutOfMemory
std.deque.Allocator
别名
别名目标 std.mem.Allocator
std.deque.assert
别名
别名目标 std.debug.assert
std.deque.Deque
类型函数
连续、可增长的双端队列。
从队列任一端压入/弹出元素的时间复杂度均为 O(1)。
pub fn Deque(comptime T: type) type
参数
T: type
字段
buffer: []T环形缓冲区。
head: usize逻辑双端队列中第一项在 buffer 中的存储索引。
len: usize逻辑双端队列中存储的元素数量。
SelfemptyinitCapacityinitBufferdeinitensureTotalCapacityensureTotalCapacityPreciseensureUnusedCapacitypushFrontpushFrontBoundedpushFrontAssumeCapacitypushBackpushBackBoundedpushBackAssumeCapacitypushFrontSlicepushFrontSliceBoundedpushFrontSliceAssumeCapacitypushBackSlicepushBackSliceBoundedpushBackSliceAssumeCapacityfrontfrontPtrbackbackPtratatPtrpopFrontpopBackIteratoriteratorbufferIndex
std.deque.Deque.at
函数
返回双端队列中给定索引处的元素。
队列首个元素的索引为 0。
断言索引未越界。
pub fn at(deque: *const Self, index: usize) T
参数
deque: *const Self
index: usize
std.deque.Deque.atPtr
函数
返回指向双端队列中给定索引处元素的指针。
队列中第一个元素的索引为 0。
断言索引未越界。
pub fn atPtr(deque: *const Self, index: usize) *T
参数
deque: *const Self
index: usize
std.deque.Deque.back
函数
返回双端队列的最后一项;若为空,则返回 null。
pub fn back(deque: *const Self) ?T
参数
deque: *const Self
std.deque.Deque.backPtr
函数
返回双端队列的最后一项;若为空,则返回 null。
pub fn backPtr(deque: *const Self) ?*T
参数
deque: *const Self
std.deque.Deque.bufferIndex
函数
返回逻辑双端队列中给定索引处的元素
在 buffer 中的存储索引。
fn bufferIndex(deque: *const Self, index: usize) usize
参数
deque: *const Self
index: usize
std.deque.Deque.deinit
函数
释放全部已分配内存。
pub fn deinit(deque: *Self, gpa: Allocator) void
参数
std.deque.Deque.empty
常量
不包含元素的 Deque。
Self
std.deque.Deque.ensureTotalCapacity
函数
修改双端队列,使其至少可容纳 new_capacity 个条目。
采用超线性增长,以实现均摊 O(1) 的入队和出队操作。
如果需要额外内存,则使元素指针失效。
pub fn ensureTotalCapacity(deque: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void
参数
错误
- OutOfMemory
std.deque.Deque.ensureTotalCapacityPrecise
函数
若当前容量小于 new_capacity,此函数会
修改双端队列,使其恰好能容纳 new_capacity 个元素。
若需要额外内存,则使元素指针失效。
pub fn ensureTotalCapacityPrecise(deque: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void
参数
错误
- OutOfMemory
std.deque.Deque.ensureUnusedCapacity
函数
修改双端队列,使其至少还能容纳 additional_count 个额外元素。
若需要额外内存,则使元素指针失效。
pub fn ensureUnusedCapacity( deque: *Self, gpa: Allocator, additional_count: usize, ) Allocator.Error!void
参数
错误
- OutOfMemory
std.deque.Deque.front
函数
返回双端队列第一项;为空则返回 null。
pub fn front(deque: *const Self) ?T
参数
deque: *const Self
std.deque.Deque.frontPtr
函数
返回指向双端队列首项的指针;若为空,则返回 null。
pub fn frontPtr(deque: *const Self) ?*T
参数
deque: *const Self
std.deque.Deque.initBuffer
函数
使用外部管理的内存初始化。缓冲区决定容量, 双端队列初始为空。
采用此方式初始化时,所有接受 Allocator 参数的函数 都会导致非法行为。
pub fn initBuffer(buffer: []T) Self
参数
buffer: []T
std.deque.Deque.initCapacity
函数
初始化并分配可容纳 capacity 个元素的容量。
最终容量恰好等于 capacity。
使用 deinit 反初始化。
pub fn initCapacity(gpa: Allocator, capacity: usize) Allocator.Error!Self
参数
gpa: Allocator
capacity: usize
错误
- OutOfMemory
std.deque.Deque.iterator
函数
按从前到后的顺序遍历双端队列中的所有元素。
pub fn iterator(deque: *const Self) Iterator
参数
deque: *const Self
std.deque.Deque.Iterator
容器
字段
deque: *const Self
index: usize
std.deque.Deque.Iterator.next
函数
pub fn next(it: *Iterator) ?T
参数
it: *Iterator
std.deque.Deque.Iterator.nextPtr
函数
pub fn nextPtr(it: *Iterator) ?*T
参数
it: *Iterator
std.deque.Deque.Iterator.peek
函数
pub fn peek(it: Iterator) ?T
参数
it: Iterator
std.deque.Deque.Iterator.peekPtr
函数
pub fn peekPtr(it: Iterator) ?*T
参数
it: Iterator
std.deque.Deque.popBack
函数
移除并返回双端队列最后一项;为空则返回 null。
pub fn popBack(deque: *Self) ?T
参数
deque: *Self
std.deque.Deque.popFront
函数
移除并返回双端队列中的第一项;若为空,则返回 null。
pub fn popFront(deque: *Self) ?T
参数
deque: *Self
std.deque.Deque.pushBack
函数
向双端队列尾部添加一项。
如果需要额外内存,元素指针将失效。
pub fn pushBack(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void
参数
错误
- OutOfMemory
std.deque.Deque.pushBackAssumeCapacity
函数
在双端队列尾部添加一个元素。
绝不会使元素指针失效。
断言双端队列可容纳一个新增元素。
pub fn pushBackAssumeCapacity(deque: *Self, item: T) void
参数
deque: *Self
item: T
std.deque.Deque.pushBackBounded
函数
向双端队列后端添加一个条目。
绝不使元素指针失效。
如果双端队列的未用容量不足以容纳新增条目,则返回
error.OutOfMemory。
pub fn pushBackBounded(deque: *Self, item: T) error{OutOfMemory}!void
参数
deque: *Self
item: T
错误
- OutOfMemory
std.deque.Deque.pushBackSlice
函数
将 items 添加到双端队列后端。
等同于顺序遍历 items,并对每个
条目调用 pushBack。
如果需要额外内存,则使元素指针失效。
pub fn pushBackSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void
参数
错误
- OutOfMemory
std.deque.Deque.pushBackSliceAssumeCapacity
函数
将 items 加入双端队列的后端。
等同于按顺序遍历 items,对每个
条目调用 pushBack。
绝不会使元素指针失效。
断言双端队列能够容纳新增元素。
pub fn pushBackSliceAssumeCapacity(deque: *Self, items: []const T) void
参数
deque: *Self
items: []const T
std.deque.Deque.pushBackSliceBounded
函数
将 items 添加到双端队列尾部。
等价于按顺序遍历 items,对每个条目
调用 pushBack。
绝不会使元素指针失效。
若双端队列的未使用容量不足以容纳新增元素,返回
error.OutOfMemory。
pub fn pushBackSliceBounded(deque: *Self, items: []const T) error{OutOfMemory}!void
参数
deque: *Self
items: []const T
错误
- OutOfMemory
std.deque.Deque.pushFront
函数
向双端队列头部添加一个元素。
如果需要额外内存,则使元素指针失效。
pub fn pushFront(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void
参数
错误
- OutOfMemory
std.deque.Deque.pushFrontAssumeCapacity
函数
在双端队列前端添加一个项目。
永远不会使元素指针失效。
断言双端队列可以容纳一个额外项目。
pub fn pushFrontAssumeCapacity(deque: *Self, item: T) void
参数
deque: *Self
item: T
std.deque.Deque.pushFrontBounded
函数
向双端队列头部添加一个元素。
绝不会使元素指针失效。
若双端队列的未使用容量不足以容纳新元素,
则返回 error.OutOfMemory。
pub fn pushFrontBounded(deque: *Self, item: T) error{OutOfMemory}!void
参数
deque: *Self
item: T
错误
- OutOfMemory
std.deque.Deque.pushFrontSlice
函数
将 items 添加到双端队列前端。
等同于逆序遍历 items,并对每个
条目调用 pushFront。
如果需要额外内存,则使元素指针失效。
pub fn pushFrontSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void
参数
错误
- OutOfMemory
std.deque.Deque.pushFrontSliceAssumeCapacity
函数
将 items 添加到双端队列头部。
等价于逆序遍历 items,对每个条目
调用 pushFront。
绝不会使元素指针失效。
断言双端队列可以容纳新增元素。
pub fn pushFrontSliceAssumeCapacity(deque: *Self, items: []const T) void
参数
deque: *Self
items: []const T
std.deque.Deque.pushFrontSliceBounded
函数
将 items 加入双端队列的前端。
等同于反向迭代 items,对每个
条目调用 pushFront。
绝不会使元素指针失效。
如果双端队列的未使用容量不足以容纳新增元素,则返回
error.OutOfMemory。
pub fn pushFrontSliceBounded(deque: *Self, items: []const T) error{OutOfMemory}!void
参数
deque: *Self
items: []const T
错误
- OutOfMemory
std.deque.Deque.Self
别名
别名目标 std.deque.Deque
std.deque.fuzzAgainstArrayList
函数
fn fuzzAgainstArrayList(_: void, smith: *std.testing.Smith) anyerror!void
参数
std.deque.FuzzAllocator
容器
字段
std.deque.FuzzAllocator.alloc
函数
fn alloc(ctx: *anyopaque, len: usize, a: std.mem.Alignment, _: usize) ?[*]u8
参数
std.deque.FuzzAllocator.allocator
函数
pub fn allocator(f: *FuzzAllocator) std.mem.Allocator
参数
f: *FuzzAllocator
std.deque.FuzzAllocator.allocCount
函数
pub fn allocCount(f: *FuzzAllocator) u2
参数
f: *FuzzAllocator
std.deque.FuzzAllocator.free
函数
fn free(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, _: usize) void
参数
std.deque.FuzzAllocator.init
函数
pub fn init(smith: *std.testing.Smith) FuzzAllocator
参数
std.deque.FuzzAllocator.memSlot
函数
fn memSlot(f: *FuzzAllocator, mem: []u8) u1
参数
f: *FuzzAllocator
mem: []u8
std.deque.FuzzAllocator.remap
函数
fn remap(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) ?[*]u8
参数
std.deque.FuzzAllocator.resize
函数
fn resize(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) bool
参数
std.deque.std
别名
别名目标 std
源码
std/deque.zig
const std = @import("std");
const assert = std.debug.assert;
const Allocator = std.mem.Allocator;
/// 连续、可增长的双端队列。
///
/// 从队列任一端压入/弹出元素的时间复杂度均为 O(1)。
pub fn Deque(comptime T: type) type {
return struct {
const Self = @This();
/// 环形缓冲区。
buffer: []T,
/// 逻辑双端队列中第一项在 buffer 中的存储索引。
head: usize,
/// 逻辑双端队列中存储的元素数量。
len: usize,
/// 不包含元素的 Deque。
pub const empty: Self = .{
.buffer = &.{},
.head = 0,
.len = 0,
};
/// 初始化并分配可容纳 `capacity` 个元素的容量。
/// 最终容量恰好等于 `capacity`。
/// 使用 `deinit` 反初始化。
pub fn initCapacity(gpa: Allocator, capacity: usize) Allocator.Error!Self {
var deque: Self = .empty;
try deque.ensureTotalCapacityPrecise(gpa, capacity);
return deque;
}
/// 使用外部管理的内存初始化。缓冲区决定容量,
/// 双端队列初始为空。
///
/// 采用此方式初始化时,所有接受 Allocator 参数的函数
/// 都会导致非法行为。
pub fn initBuffer(buffer: []T) Self {
return .{
.buffer = buffer,
.head = 0,
.len = 0,
};
}
/// 释放全部已分配内存。
pub fn deinit(deque: *Self, gpa: Allocator) void {
gpa.free(deque.buffer);
deque.* = undefined;
}
/// 修改双端队列,使其至少可容纳 `new_capacity` 个条目。
/// 采用超线性增长,以实现均摊 O(1) 的入队和出队操作。
/// 如果需要额外内存,则使元素指针失效。
pub fn ensureTotalCapacity(deque: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
if (deque.buffer.len >= new_capacity) return;
return deque.ensureTotalCapacityPrecise(gpa, std.ArrayList(T).growCapacity(new_capacity));
}
/// 若当前容量小于 `new_capacity`,此函数会
/// 修改双端队列,使其恰好能容纳 `new_capacity` 个元素。
/// 若需要额外内存,则使元素指针失效。
pub fn ensureTotalCapacityPrecise(deque: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
if (deque.buffer.len >= new_capacity) return;
const old_buffer = deque.buffer;
if (gpa.remap(old_buffer, new_capacity)) |new_buffer| {
// 如果元素绕过缓冲区末尾,则需要执行
// memcpy,防止调整缓冲区大小后出现空隙。
if (deque.head > old_buffer.len - deque.len) {
// 空隙将双端队列中的元素分为头部和尾部。
// 选择较短的一部分进行复制。
const head = new_buffer[deque.head..old_buffer.len];
const tail = new_buffer[0 .. deque.len - head.len];
if (head.len > tail.len and new_buffer.len - old_buffer.len > tail.len) {
@memcpy(new_buffer[old_buffer.len..][0..tail.len], tail);
} else {
// 此时可能发生重叠,例如容量增加 1
// 且 head.len 大于 1。
deque.head = new_buffer.len - head.len;
@memmove(new_buffer[deque.head..][0..head.len], head);
}
}
deque.buffer = new_buffer;
} else {
const new_buffer = try gpa.alloc(T, new_capacity);
if (deque.head < old_buffer.len - deque.len) {
@memcpy(new_buffer[0..deque.len], old_buffer[deque.head..][0..deque.len]);
} else {
const head = old_buffer[deque.head..];
const tail = old_buffer[0 .. deque.len - head.len];
@memcpy(new_buffer[0..head.len], head);
@memcpy(new_buffer[head.len..][0..tail.len], tail);
}
deque.head = 0;
deque.buffer = new_buffer;
gpa.free(old_buffer);
}
}
/// 修改双端队列,使其至少还能容纳 `additional_count` 个额外元素。
/// 若需要额外内存,则使元素指针失效。
pub fn ensureUnusedCapacity(
deque: *Self,
gpa: Allocator,
additional_count: usize,
) Allocator.Error!void {
return deque.ensureTotalCapacity(gpa, try addOrOom(deque.len, additional_count));
}
/// 向双端队列头部添加一个元素。
///
/// 如果需要额外内存,则使元素指针失效。
pub fn pushFront(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void {
try deque.ensureUnusedCapacity(gpa, 1);
deque.pushFrontAssumeCapacity(item);
}
/// 向双端队列头部添加一个元素。
///
/// 绝不会使元素指针失效。
///
/// 若双端队列的未使用容量不足以容纳新元素,
/// 则返回 `error.OutOfMemory`。
pub fn pushFrontBounded(deque: *Self, item: T) error{OutOfMemory}!void {
if (deque.buffer.len - deque.len == 0) return error.OutOfMemory;
return deque.pushFrontAssumeCapacity(item);
}
/// 在双端队列前端添加一个项目。
///
/// 永远不会使元素指针失效。
///
/// 断言双端队列可以容纳一个额外项目。
pub fn pushFrontAssumeCapacity(deque: *Self, item: T) void {
assert(deque.len < deque.buffer.len);
if (deque.head == 0) {
deque.head = deque.buffer.len;
}
deque.head -= 1;
deque.buffer[deque.head] = item;
deque.len += 1;
}
/// 向双端队列尾部添加一项。
///
/// 如果需要额外内存,元素指针将失效。
pub fn pushBack(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void {
try deque.ensureUnusedCapacity(gpa, 1);
deque.pushBackAssumeCapacity(item);
}
/// 向双端队列后端添加一个条目。
///
/// 绝不使元素指针失效。
///
/// 如果双端队列的未用容量不足以容纳新增条目,则返回
/// `error.OutOfMemory`。
pub fn pushBackBounded(deque: *Self, item: T) error{OutOfMemory}!void {
if (deque.buffer.len - deque.len == 0) return error.OutOfMemory;
deque.pushBackAssumeCapacity(item);
}
/// 在双端队列尾部添加一个元素。
///
/// 绝不会使元素指针失效。
///
/// 断言双端队列可容纳一个新增元素。
pub fn pushBackAssumeCapacity(deque: *Self, item: T) void {
assert(deque.len < deque.buffer.len);
const buffer_index = deque.bufferIndex(deque.len);
deque.buffer[buffer_index] = item;
deque.len += 1;
}
/// 将 `items` 添加到双端队列前端。
/// 等同于逆序遍历 `items`,并对每个
/// 条目调用 `pushFront`。
///
/// 如果需要额外内存,则使元素指针失效。
pub fn pushFrontSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void {
try deque.ensureUnusedCapacity(gpa, items.len);
return deque.pushFrontSliceAssumeCapacity(items);
}
/// 将 `items` 加入双端队列的前端。
/// 等同于反向迭代 `items`,对每个
/// 条目调用 `pushFront`。
///
/// 绝不会使元素指针失效。
///
/// 如果双端队列的未使用容量不足以容纳新增元素,则返回
/// `error.OutOfMemory`。
pub fn pushFrontSliceBounded(deque: *Self, items: []const T) error{OutOfMemory}!void {
if (deque.buffer.len - deque.len < items.len) return error.OutOfMemory;
return deque.pushFrontSliceAssumeCapacity(items);
}
/// 将 `items` 添加到双端队列头部。
/// 等价于逆序遍历 `items`,对每个条目
/// 调用 `pushFront`。
///
/// 绝不会使元素指针失效。
///
/// 断言双端队列可以容纳新增元素。
pub fn pushFrontSliceAssumeCapacity(deque: *Self, items: []const T) void {
assert(deque.buffer.len - deque.len >= items.len);
if (deque.head < items.len) {
@memcpy(deque.buffer[0..deque.head], items[items.len - deque.head ..]);
deque.head = deque.buffer.len - items.len + deque.head;
@memcpy(deque.buffer[deque.head..], items.ptr);
} else {
deque.head -= items.len;
@memcpy(deque.buffer[deque.head..][0..items.len], items);
}
deque.len += items.len;
}
/// 将 `items` 添加到双端队列后端。
/// 等同于顺序遍历 `items`,并对每个
/// 条目调用 `pushBack`。
///
/// 如果需要额外内存,则使元素指针失效。
pub fn pushBackSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void {
try deque.ensureUnusedCapacity(gpa, items.len);
return deque.pushBackSliceAssumeCapacity(items);
}
/// 将 `items` 添加到双端队列尾部。
/// 等价于按顺序遍历 `items`,对每个条目
/// 调用 `pushBack`。
///
/// 绝不会使元素指针失效。
///
/// 若双端队列的未使用容量不足以容纳新增元素,返回
/// `error.OutOfMemory`。
pub fn pushBackSliceBounded(deque: *Self, items: []const T) error{OutOfMemory}!void {
if (deque.buffer.len - deque.len < items.len) return error.OutOfMemory;
return deque.pushBackSliceAssumeCapacity(items);
}
/// 将 `items` 加入双端队列的后端。
/// 等同于按顺序遍历 `items`,对每个
/// 条目调用 `pushBack`。
///
/// 绝不会使元素指针失效。
///
/// 断言双端队列能够容纳新增元素。
pub fn pushBackSliceAssumeCapacity(deque: *Self, items: []const T) void {
assert(deque.buffer.len - deque.len >= items.len);
const trailing_buffer = deque.buffer[deque.bufferIndex(deque.len)..];
if (trailing_buffer.len < items.len) {
@memcpy(trailing_buffer, items[0..trailing_buffer.len]);
@memcpy(deque.buffer.ptr, items[trailing_buffer.len..]);
} else {
@memcpy(trailing_buffer[0..items.len], items);
}
deque.len += items.len;
}
/// 返回双端队列第一项;为空则返回 null。
pub fn front(deque: *const Self) ?T {
if (deque.len == 0) return null;
return deque.buffer[deque.head];
}
/// 返回指向双端队列首项的指针;若为空,则返回 null。
pub fn frontPtr(deque: *const Self) ?*T {
if (deque.len == 0) return null;
return &deque.buffer[deque.head];
}
/// 返回双端队列的最后一项;若为空,则返回 null。
pub fn back(deque: *const Self) ?T {
if (deque.len == 0) return null;
return deque.buffer[deque.bufferIndex(deque.len - 1)];
}
/// 返回双端队列的最后一项;若为空,则返回 null。
pub fn backPtr(deque: *const Self) ?*T {
if (deque.len == 0) return null;
return &deque.buffer[deque.bufferIndex(deque.len - 1)];
}
/// 返回双端队列中给定索引处的元素。
///
/// 队列首个元素的索引为 0。
///
/// 断言索引未越界。
pub fn at(deque: *const Self, index: usize) T {
assert(index < deque.len);
return deque.buffer[deque.bufferIndex(index)];
}
/// 返回指向双端队列中给定索引处元素的指针。
///
/// 队列中第一个元素的索引为 0。
///
/// 断言索引未越界。
pub fn atPtr(deque: *const Self, index: usize) *T {
assert(index < deque.len);
return &deque.buffer[deque.bufferIndex(index)];
}
/// 移除并返回双端队列中的第一项;若为空,则返回 null。
pub fn popFront(deque: *Self) ?T {
if (deque.len == 0) return null;
const pop_index = deque.head;
deque.head = deque.bufferIndex(1);
deque.len -= 1;
return deque.buffer[pop_index];
}
/// 移除并返回双端队列最后一项;为空则返回 null。
pub fn popBack(deque: *Self) ?T {
if (deque.len == 0) return null;
deque.len -= 1;
return deque.buffer[deque.bufferIndex(deque.len)];
}
pub const Iterator = struct {
deque: *const Self,
index: usize,
pub fn peek(it: Iterator) ?T {
if (it.index >= it.deque.len) return null;
return it.deque.at(it.index);
}
pub fn next(it: *Iterator) ?T {
const item = it.peek() orelse return null;
it.index += 1;
return item;
}
pub fn peekPtr(it: Iterator) ?*T {
if (it.index >= it.deque.len) return null;
return it.deque.atPtr(it.index);
}
pub fn nextPtr(it: *Iterator) ?*T {
const item_ptr = it.peekPtr() orelse return null;
it.index += 1;
return item_ptr;
}
};
/// 按从前到后的顺序遍历双端队列中的所有元素。
pub fn iterator(deque: *const Self) Iterator {
return .{ .deque = deque, .index = 0 };
}
/// 返回逻辑双端队列中给定索引处的元素
/// 在 `buffer` 中的存储索引。
fn bufferIndex(deque: *const Self, index: usize) usize {
// 此函数采用这种写法,
// 以避免溢出及开销较大的除法。
const head_len = deque.buffer.len - deque.head;
if (index < head_len) {
return deque.head + index;
} else {
return index - head_len;
}
}
};
}
/// 整数加法,溢出时返回 `error.OutOfMemory`。
fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize {
const result, const overflow = @addWithOverflow(a, b);
if (overflow != 0) return error.OutOfMemory;
return result;
}
test "basic" {
const testing = std.testing;
const gpa = testing.allocator;
var q: Deque(u32) = .empty;
defer q.deinit(gpa);
try testing.expectEqual(null, q.popFront());
try testing.expectEqual(null, q.popBack());
try q.pushBack(gpa, 1);
try q.pushBack(gpa, 2);
try q.pushBack(gpa, 3);
try q.pushFront(gpa, 0);
try testing.expectEqual(0, q.popFront());
try testing.expectEqual(1, q.popFront());
try testing.expectEqual(3, q.popBack());
try testing.expectEqual(2, q.popFront());
try testing.expectEqual(null, q.popFront());
try testing.expectEqual(null, q.popBack());
}
test "buffer" {
const testing = std.testing;
var buffer: [4]u32 = undefined;
var q: Deque(u32) = .initBuffer(&buffer);
try testing.expectEqual(null, q.popFront());
try testing.expectEqual(null, q.popBack());
try q.pushBackBounded(1);
try q.pushBackBounded(2);
try q.pushBackBounded(3);
try q.pushFrontBounded(0);
try testing.expectError(error.OutOfMemory, q.pushBackBounded(4));
try testing.expectEqual(0, q.popFront());
try testing.expectEqual(1, q.popFront());
try testing.expectEqual(3, q.popBack());
try testing.expectEqual(2, q.popFront());
try testing.expectEqual(null, q.popFront());
try testing.expectEqual(null, q.popBack());
}
test "slow growth" {
const testing = std.testing;
const gpa = testing.allocator;
var q: Deque(i32) = .empty;
defer q.deinit(gpa);
try q.ensureTotalCapacityPrecise(gpa, 1);
q.pushBackAssumeCapacity(1);
try q.ensureTotalCapacityPrecise(gpa, 2);
q.pushFrontAssumeCapacity(0);
try q.ensureTotalCapacityPrecise(gpa, 3);
q.pushBackAssumeCapacity(2);
try q.ensureTotalCapacityPrecise(gpa, 5);
q.pushBackAssumeCapacity(3);
q.pushFrontAssumeCapacity(-1);
try q.ensureTotalCapacityPrecise(gpa, 6);
q.pushFrontAssumeCapacity(-2);
try testing.expectEqual(-2, q.popFront());
try testing.expectEqual(-1, q.popFront());
try testing.expectEqual(3, q.popBack());
try testing.expectEqual(0, q.popFront());
try testing.expectEqual(2, q.popBack());
try testing.expectEqual(1, q.popBack());
try testing.expectEqual(null, q.popFront());
try testing.expectEqual(null, q.popBack());
}
test "slice" {
const testing = std.testing;
const gpa = testing.allocator;
var q: Deque(i32) = .empty;
defer q.deinit(gpa);
try q.pushBackSlice(gpa, &.{ 3, 4, 5 });
try q.pushBackSlice(gpa, &.{ 6, 7 });
try q.pushFrontSlice(gpa, &.{2});
try q.pushBackSlice(gpa, &.{});
try q.pushFrontSlice(gpa, &.{ 0, 1 });
try q.pushFrontSlice(gpa, &.{});
try testing.expectEqual(0, q.popFront());
try testing.expectEqual(1, q.popFront());
try testing.expectEqual(7, q.popBack());
try testing.expectEqual(6, q.popBack());
try q.pushFrontSlice(gpa, &.{ 0, 1 });
try q.pushBackSlice(gpa, &.{ 6, 7 });
try testing.expectEqual(0, q.popFront());
try testing.expectEqual(1, q.popFront());
try testing.expectEqual(2, q.popFront());
try testing.expectEqual(7, q.popBack());
try testing.expectEqual(6, q.popBack());
try testing.expectEqual(3, q.popFront());
try testing.expectEqual(4, q.popFront());
try testing.expectEqual(5, q.popBack());
try testing.expectEqual(null, q.popFront());
try testing.expectEqual(null, q.popBack());
}
test "iterator" {
const testing = std.testing;
const gpa = testing.allocator;
var q: Deque(i32) = .empty;
defer q.deinit(gpa);
const items: []const i32 = &.{ 0, 1, 2, 3, 4, 5 };
try q.pushFrontSlice(gpa, items);
{
var it = q.iterator();
for (items) |item| {
try testing.expectEqual(item, it.peek());
try testing.expectEqual(item, it.next());
}
try testing.expectEqual(null, it.peek());
try testing.expectEqual(null, it.next());
}
{
var it = q.iterator();
for (items) |item| {
if (it.peekPtr()) |ptr| {
try testing.expectEqual(item, ptr.*);
} else return error.TestExpectedNonNull;
if (it.nextPtr()) |ptr| {
try testing.expectEqual(item, ptr.*);
} else return error.TestExpectedNonNull;
}
try testing.expectEqual(null, it.peekPtr());
try testing.expectEqual(null, it.nextPtr());
}
}
test "fuzz against ArrayList oracle" {
try std.testing.fuzz({}, fuzzAgainstArrayList, .{});
}
const FuzzAllocator = struct {
smith: *std.testing.Smith,
bufs: [2][256 * 4]u8 align(4),
used_bitmap: u2,
used_len: [2]usize,
pub fn init(smith: *std.testing.Smith) FuzzAllocator {
return .{
.smith = smith,
.bufs = undefined,
.used_len = undefined,
.used_bitmap = 0,
};
}
pub fn allocator(f: *FuzzAllocator) std.mem.Allocator {
return .{
.ptr = f,
.vtable = &.{
.alloc = alloc,
.resize = resize,
.remap = remap,
.free = free,
},
};
}
pub fn allocCount(f: *FuzzAllocator) u2 {
return @popCount(f.used_bitmap);
}
fn alloc(ctx: *anyopaque, len: usize, a: std.mem.Alignment, _: usize) ?[*]u8 {
const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
assert(a == .@"4");
assert(len % 4 == 0);
const slot: u1 = @intCast(@ctz(~f.used_bitmap));
const buf: []u8 = &f.bufs[slot];
if (len > buf.len) return null;
f.used_bitmap |= @as(u2, 1) << slot;
f.used_len[slot] = len;
return buf.ptr;
}
fn memSlot(f: *FuzzAllocator, mem: []u8) u1 {
const slot: u1 = if (&mem[0] == &f.bufs[0][0])
0
else if (&mem[0] == &f.bufs[1][0])
1
else
unreachable;
assert((f.used_bitmap >> slot) & 1 == 1);
assert(mem.len == f.used_len[slot]);
return slot;
}
fn resize(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) bool {
const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
assert(a == .@"4");
assert(f.allocCount() == 1);
const slot = f.memSlot(mem);
if (new_len > f.bufs[slot].len or f.smith.value(bool)) return false;
f.used_len[slot] = new_len;
return true;
}
fn remap(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) ?[*]u8 {
const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
assert(a == .@"4");
assert(f.allocCount() == 1);
const slot = f.memSlot(mem);
if (new_len > f.bufs[slot].len or f.smith.value(bool)) return null;
if (f.smith.value(bool)) {
f.used_len[slot] = new_len;
// 原地重新映射
return mem.ptr;
} else {
// 移动式重新映射
const new_slot = ~slot;
f.used_bitmap = ~f.used_bitmap;
f.used_len[new_slot] = new_len;
const new_buf = &f.bufs[new_slot];
@memcpy(new_buf[0..mem.len], mem);
return new_buf.ptr;
}
}
fn free(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, _: usize) void {
const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
assert(a == .@"4");
f.used_bitmap ^= @as(u2, 1) << f.memSlot(mem);
}
};
fn fuzzAgainstArrayList(_: void, smith: *std.testing.Smith) anyerror!void {
const testing = std.testing;
var q_gpa_inst: FuzzAllocator = .init(smith);
var l_gpa_buf: [q_gpa_inst.bufs[0].len]u8 align(4) = undefined;
var l_gpa_inst: std.heap.FixedBufferAllocator = .init(&l_gpa_buf);
const q_gpa = q_gpa_inst.allocator();
const l_gpa = l_gpa_inst.allocator();
var q: Deque(u32) = .empty;
var l: std.ArrayList(u32) = .empty;
const Action = enum(u8) {
grow,
push_back,
push_front,
push_back_slice,
push_front_slice,
pop_back,
pop_front,
};
while (!smith.eosWeightedSimple(15, 1)) {
const baseline = testing.Smith.baselineWeights(Action);
const grow_weight: testing.Smith.Weight = .value(Action, .grow, 3);
switch (smith.valueWeighted(Action, baseline ++ .{grow_weight})) {
.push_back => {
const item = smith.value(u32);
try testing.expectEqual(
l.appendBounded(item),
q.pushBackBounded(item),
);
},
.push_front => {
const item = smith.value(u32);
try testing.expectEqual(
l.insertBounded(0, item),
q.pushFrontBounded(item),
);
},
.push_back_slice => {
var buffer: [std.math.maxInt(u3)]u32 = undefined;
const items = buffer[0..smith.value(u3)];
for (items) |*item| {
item.* = smith.value(u32);
}
try testing.expectEqual(
l.appendSliceBounded(items),
q.pushBackSliceBounded(items),
);
},
.push_front_slice => {
var buffer: [std.math.maxInt(u3)]u32 = undefined;
const items = buffer[0..smith.value(u3)];
for (items) |*item| {
item.* = smith.value(u32);
}
try testing.expectEqual(
l.insertSliceBounded(0, items),
q.pushFrontSliceBounded(items),
);
},
.pop_back => {
try testing.expectEqual(l.pop(), q.popBack());
},
.pop_front => {
try testing.expectEqual(
if (l.items.len > 0) l.orderedRemove(0) else null,
q.popFront(),
);
},
// 以小幅、随机、线性的增量扩容,似乎能更有效地测试 ensureTotalCapacityPrecise(),它是 Deque 实现中最复杂的部分。
//
//
.grow => {
const growth = smith.value(u3);
try l.ensureTotalCapacityPrecise(l_gpa, l.items.len + growth);
try q.ensureTotalCapacityPrecise(q_gpa, q.len + growth);
},
}
try testing.expectEqual(l.last(), q.back());
try testing.expectEqual(
if (l.items.len > 0) l.items[0] else null,
q.front(),
);
try testing.expectEqual(l.items.len, q.len);
try testing.expectEqual(l.capacity, q.buffer.len);
{
var it = q.iterator();
for (l.items) |item| {
try testing.expectEqual(item, it.next());
}
try testing.expectEqual(null, it.next());
}
try testing.expectEqual(@intFromBool(q.buffer.len != 0), q_gpa_inst.allocCount());
}
q.deinit(q_gpa);
try testing.expectEqual(0, q_gpa_inst.allocCount());
}