std.deque.addOrOom
function
Integer addition returning error.OutOfMemory on overflow.
fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize
Parameters
a: usize
b: usize
Errors
- OutOfMemory
std.deque.Allocator
alias
Alias of std.mem.Allocator
std.deque.assert
alias
Alias of std.debug.assert
std.deque.Deque
type-function
A contiguous, growable, double-ended queue.
Pushing/popping items from either end of the queue is O(1).
pub fn Deque(comptime T: type) type
Parameters
T: type
Fields
buffer: []TA ring buffer.
head: usizeThe index in buffer where the first item in the logical deque is stored.
len: usizeThe number of items stored in the logical deque.
SelfemptyinitCapacityinitBufferdeinitensureTotalCapacityensureTotalCapacityPreciseensureUnusedCapacitypushFrontpushFrontBoundedpushFrontAssumeCapacitypushBackpushBackBoundedpushBackAssumeCapacitypushFrontSlicepushFrontSliceBoundedpushFrontSliceAssumeCapacitypushBackSlicepushBackSliceBoundedpushBackSliceAssumeCapacityfrontfrontPtrbackbackPtratatPtrpopFrontpopBackIteratoriteratorbufferIndex
std.deque.Deque.at
function
Return the item at the given index in the deque.
The first item in the queue is at index 0.
Asserts that the index is in-bounds.
pub fn at(deque: *const Self, index: usize) T
Parameters
deque: *const Self
index: usize
std.deque.Deque.atPtr
function
Return pointer to the item at the given index in the deque.
The first item in the queue is at index 0.
Asserts that the index is in-bounds.
pub fn atPtr(deque: *const Self, index: usize) *T
Parameters
deque: *const Self
index: usize
std.deque.Deque.back
function
Return the last item in the deque or null if empty.
pub fn back(deque: *const Self) ?T
Parameters
deque: *const Self
std.deque.Deque.backPtr
function
Return the last item in the deque or null if empty.
pub fn backPtr(deque: *const Self) ?*T
Parameters
deque: *const Self
std.deque.Deque.bufferIndex
function
Returns the index in buffer where the element at the given
index in the logical deque is stored.
fn bufferIndex(deque: *const Self, index: usize) usize
Parameters
deque: *const Self
index: usize
std.deque.Deque.deinit
function
Release all allocated memory.
pub fn deinit(deque: *Self, gpa: Allocator) void
Parameters
std.deque.Deque.empty
constant
A Deque containing no elements.
Self
std.deque.Deque.ensureTotalCapacity
function
Modify the deque so that it can hold at least new_capacity items.
Implements super-linear growth to achieve amortized O(1) push/pop operations.
Invalidates element pointers if additional memory is needed.
pub fn ensureTotalCapacity(deque: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.deque.Deque.ensureTotalCapacityPrecise
function
If the current capacity is less than new_capacity, this function will
modify the deque so that it can hold exactly new_capacity items.
Invalidates element pointers if additional memory is needed.
pub fn ensureTotalCapacityPrecise(deque: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.deque.Deque.ensureUnusedCapacity
function
Modify the deque so that it can hold at least additional_count more items.
Invalidates element pointers if additional memory is needed.
pub fn ensureUnusedCapacity( deque: *Self, gpa: Allocator, additional_count: usize, ) Allocator.Error!void
Parameters
Errors
- OutOfMemory
std.deque.Deque.front
function
Return the first item in the deque or null if empty.
pub fn front(deque: *const Self) ?T
Parameters
deque: *const Self
std.deque.Deque.frontPtr
function
Return pointer to the first item in the deque or null if empty.
pub fn frontPtr(deque: *const Self) ?*T
Parameters
deque: *const Self
std.deque.Deque.initBuffer
function
Initialize with externally-managed memory. The buffer determines the capacity and the deque is initially empty.
When initialized this way, all functions that accept an Allocator argument cause illegal behavior.
pub fn initBuffer(buffer: []T) Self
Parameters
buffer: []T
std.deque.Deque.initCapacity
function
Initialize with capacity to hold capacity elements.
The resulting capacity will equal capacity exactly.
Deinitialize with deinit.
pub fn initCapacity(gpa: Allocator, capacity: usize) Allocator.Error!Self
Parameters
gpa: Allocator
capacity: usize
Errors
- OutOfMemory
std.deque.Deque.iterator
function
Iterates over all items in the deque in order from front to back.
pub fn iterator(deque: *const Self) Iterator
Parameters
deque: *const Self
std.deque.Deque.Iterator
container
Fields
deque: *const Self
index: usize
std.deque.Deque.Iterator.next
function
pub fn next(it: *Iterator) ?T
Parameters
it: *Iterator
std.deque.Deque.Iterator.nextPtr
function
pub fn nextPtr(it: *Iterator) ?*T
Parameters
it: *Iterator
std.deque.Deque.Iterator.peek
function
pub fn peek(it: Iterator) ?T
Parameters
it: Iterator
std.deque.Deque.Iterator.peekPtr
function
pub fn peekPtr(it: Iterator) ?*T
Parameters
it: Iterator
std.deque.Deque.popBack
function
Remove and return the last item in the deque or null if empty.
pub fn popBack(deque: *Self) ?T
Parameters
deque: *Self
std.deque.Deque.popFront
function
Remove and return the first item in the deque or null if empty.
pub fn popFront(deque: *Self) ?T
Parameters
deque: *Self
std.deque.Deque.pushBack
function
Add one item to the back of the deque.
Invalidates element pointers if additional memory is needed.
pub fn pushBack(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void
Parameters
Errors
- OutOfMemory
std.deque.Deque.pushBackAssumeCapacity
function
Add one item to the back of the deque.
Never invalidates element pointers.
Asserts that the deque can hold one additional item.
pub fn pushBackAssumeCapacity(deque: *Self, item: T) void
Parameters
deque: *Self
item: T
std.deque.Deque.pushBackBounded
function
Add one item to the back of the deque.
Never invalidates element pointers.
If the deque lacks unused capacity for the additional item, returns
error.OutOfMemory.
pub fn pushBackBounded(deque: *Self, item: T) error{OutOfMemory}!void
Parameters
deque: *Self
item: T
Errors
- OutOfMemory
std.deque.Deque.pushBackSlice
function
Add items to the back of the deque.
This is equivalent to iterating items in order and calling
pushBack on every single entry.
Invalidates element pointers if additional memory is needed.
pub fn pushBackSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void
Parameters
Errors
- OutOfMemory
std.deque.Deque.pushBackSliceAssumeCapacity
function
Add items to the back of the deque.
This is equivalent to iterating items in order and calling
pushBack on every single entry.
Never invalidates element pointers.
Asserts that the deque can hold the additional items.
pub fn pushBackSliceAssumeCapacity(deque: *Self, items: []const T) void
Parameters
deque: *Self
items: []const T
std.deque.Deque.pushBackSliceBounded
function
Add items to the back of the deque.
This is equivalent to iterating items in order and calling
pushBack on every single entry.
Never invalidates element pointers.
If the deque lacks unused capacity for the additional items, returns
error.OutOfMemory.
pub fn pushBackSliceBounded(deque: *Self, items: []const T) error{OutOfMemory}!void
Parameters
deque: *Self
items: []const T
Errors
- OutOfMemory
std.deque.Deque.pushFront
function
Add one item to the front of the deque.
Invalidates element pointers if additional memory is needed.
pub fn pushFront(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void
Parameters
Errors
- OutOfMemory
std.deque.Deque.pushFrontAssumeCapacity
function
Add one item to the front of the deque.
Never invalidates element pointers.
Asserts that the deque can hold one additional item.
pub fn pushFrontAssumeCapacity(deque: *Self, item: T) void
Parameters
deque: *Self
item: T
std.deque.Deque.pushFrontBounded
function
Add one item to the front of the deque.
Never invalidates element pointers.
If the deque lacks unused capacity for the additional item, returns
error.OutOfMemory.
pub fn pushFrontBounded(deque: *Self, item: T) error{OutOfMemory}!void
Parameters
deque: *Self
item: T
Errors
- OutOfMemory
std.deque.Deque.pushFrontSlice
function
Add items to the front of the deque.
This is equivalent to iterating items in reverse and calling
pushFront on every single entry.
Invalidates element pointers if additional memory is needed.
pub fn pushFrontSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void
Parameters
Errors
- OutOfMemory
std.deque.Deque.pushFrontSliceAssumeCapacity
function
Add items to the front of the deque.
This is equivalent to iterating items in reverse and calling
pushFront on every single entry.
Never invalidates element pointers.
Asserts that the deque can hold the additional items.
pub fn pushFrontSliceAssumeCapacity(deque: *Self, items: []const T) void
Parameters
deque: *Self
items: []const T
std.deque.Deque.pushFrontSliceBounded
function
Add items to the front of the deque.
This is equivalent to iterating items in reverse and calling
pushFront on every single entry.
Never invalidates element pointers.
If the deque lacks unused capacity for the additional items, returns
error.OutOfMemory.
pub fn pushFrontSliceBounded(deque: *Self, items: []const T) error{OutOfMemory}!void
Parameters
deque: *Self
items: []const T
Errors
- OutOfMemory
std.deque.Deque.Self
alias
Alias of std.deque.Deque
std.deque.fuzzAgainstArrayList
function
fn fuzzAgainstArrayList(_: void, smith: *std.testing.Smith) anyerror!void
Parameters
std.deque.FuzzAllocator
container
Fields
std.deque.FuzzAllocator.alloc
function
fn alloc(ctx: *anyopaque, len: usize, a: std.mem.Alignment, _: usize) ?[*]u8
Parameters
std.deque.FuzzAllocator.allocator
function
pub fn allocator(f: *FuzzAllocator) std.mem.Allocator
Parameters
f: *FuzzAllocator
std.deque.FuzzAllocator.allocCount
function
pub fn allocCount(f: *FuzzAllocator) u2
Parameters
f: *FuzzAllocator
std.deque.FuzzAllocator.free
function
fn free(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, _: usize) void
Parameters
std.deque.FuzzAllocator.init
function
pub fn init(smith: *std.testing.Smith) FuzzAllocator
Parameters
std.deque.FuzzAllocator.memSlot
function
fn memSlot(f: *FuzzAllocator, mem: []u8) u1
Parameters
f: *FuzzAllocator
mem: []u8
std.deque.FuzzAllocator.remap
function
fn remap(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) ?[*]u8
Parameters
std.deque.FuzzAllocator.resize
function
fn resize(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) bool
Parameters
std.deque.std
alias
Alias of std
Source code
std/deque.zig
const std = @import("std");
const assert = std.debug.assert;
const Allocator = std.mem.Allocator;
/// A contiguous, growable, double-ended queue.
///
/// Pushing/popping items from either end of the queue is O(1).
pub fn Deque(comptime T: type) type {
return struct {
const Self = @This();
/// A ring buffer.
buffer: []T,
/// The index in buffer where the first item in the logical deque is stored.
head: usize,
/// The number of items stored in the logical deque.
len: usize,
/// A Deque containing no elements.
pub const empty: Self = .{
.buffer = &.{},
.head = 0,
.len = 0,
};
/// Initialize with capacity to hold `capacity` elements.
/// The resulting capacity will equal `capacity` exactly.
/// Deinitialize with `deinit`.
pub fn initCapacity(gpa: Allocator, capacity: usize) Allocator.Error!Self {
var deque: Self = .empty;
try deque.ensureTotalCapacityPrecise(gpa, capacity);
return deque;
}
/// Initialize with externally-managed memory. The buffer determines the
/// capacity and the deque is initially empty.
///
/// When initialized this way, all functions that accept an Allocator
/// argument cause illegal behavior.
pub fn initBuffer(buffer: []T) Self {
return .{
.buffer = buffer,
.head = 0,
.len = 0,
};
}
/// Release all allocated memory.
pub fn deinit(deque: *Self, gpa: Allocator) void {
gpa.free(deque.buffer);
deque.* = undefined;
}
/// Modify the deque so that it can hold at least `new_capacity` items.
/// Implements super-linear growth to achieve amortized O(1) push/pop operations.
/// Invalidates element pointers if additional memory is needed.
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));
}
/// If the current capacity is less than `new_capacity`, this function will
/// modify the deque so that it can hold exactly `new_capacity` items.
/// Invalidates element pointers if additional memory is needed.
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| {
// If the items wrap around the end of the buffer we need to do
// a memcpy to prevent a gap after resizing the buffer.
if (deque.head > old_buffer.len - deque.len) {
// The gap splits the items in the deque into head and tail parts.
// Choose the shorter part to copy.
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 {
// In this case overlap is possible if e.g. the capacity increase is 1
// and head.len is greater than 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);
}
}
/// Modify the deque so that it can hold at least `additional_count` **more** items.
/// Invalidates element pointers if additional memory is needed.
pub fn ensureUnusedCapacity(
deque: *Self,
gpa: Allocator,
additional_count: usize,
) Allocator.Error!void {
return deque.ensureTotalCapacity(gpa, try addOrOom(deque.len, additional_count));
}
/// Add one item to the front of the deque.
///
/// Invalidates element pointers if additional memory is needed.
pub fn pushFront(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void {
try deque.ensureUnusedCapacity(gpa, 1);
deque.pushFrontAssumeCapacity(item);
}
/// Add one item to the front of the deque.
///
/// Never invalidates element pointers.
///
/// If the deque lacks unused capacity for the additional item, returns
/// `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);
}
/// Add one item to the front of the deque.
///
/// Never invalidates element pointers.
///
/// Asserts that the deque can hold one additional 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;
}
/// Add one item to the back of the deque.
///
/// Invalidates element pointers if additional memory is needed.
pub fn pushBack(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void {
try deque.ensureUnusedCapacity(gpa, 1);
deque.pushBackAssumeCapacity(item);
}
/// Add one item to the back of the deque.
///
/// Never invalidates element pointers.
///
/// If the deque lacks unused capacity for the additional item, returns
/// `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);
}
/// Add one item to the back of the deque.
///
/// Never invalidates element pointers.
///
/// Asserts that the deque can hold one additional 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;
}
/// Add `items` to the front of the deque.
/// This is equivalent to iterating `items` in reverse and calling
/// `pushFront` on every single entry.
///
/// Invalidates element pointers if additional memory is needed.
pub fn pushFrontSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void {
try deque.ensureUnusedCapacity(gpa, items.len);
return deque.pushFrontSliceAssumeCapacity(items);
}
/// Add `items` to the front of the deque.
/// This is equivalent to iterating `items` in reverse and calling
/// `pushFront` on every single entry.
///
/// Never invalidates element pointers.
///
/// If the deque lacks unused capacity for the additional items, returns
/// `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);
}
/// Add `items` to the front of the deque.
/// This is equivalent to iterating `items` in reverse and calling
/// `pushFront` on every single entry.
///
/// Never invalidates element pointers.
///
/// Asserts that the deque can hold the additional items.
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;
}
/// Add `items` to the back of the deque.
/// This is equivalent to iterating `items` in order and calling
/// `pushBack` on every single entry.
///
/// Invalidates element pointers if additional memory is needed.
pub fn pushBackSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void {
try deque.ensureUnusedCapacity(gpa, items.len);
return deque.pushBackSliceAssumeCapacity(items);
}
/// Add `items` to the back of the deque.
/// This is equivalent to iterating `items` in order and calling
/// `pushBack` on every single entry.
///
/// Never invalidates element pointers.
///
/// If the deque lacks unused capacity for the additional items, returns
/// `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);
}
/// Add `items` to the back of the deque.
/// This is equivalent to iterating `items` in order and calling
/// `pushBack` on every single entry.
///
/// Never invalidates element pointers.
///
/// Asserts that the deque can hold the additional items.
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;
}
/// Return the first item in the deque or null if empty.
pub fn front(deque: *const Self) ?T {
if (deque.len == 0) return null;
return deque.buffer[deque.head];
}
/// Return pointer to the first item in the deque or null if empty.
pub fn frontPtr(deque: *const Self) ?*T {
if (deque.len == 0) return null;
return &deque.buffer[deque.head];
}
/// Return the last item in the deque or null if empty.
pub fn back(deque: *const Self) ?T {
if (deque.len == 0) return null;
return deque.buffer[deque.bufferIndex(deque.len - 1)];
}
/// Return the last item in the deque or null if empty.
pub fn backPtr(deque: *const Self) ?*T {
if (deque.len == 0) return null;
return &deque.buffer[deque.bufferIndex(deque.len - 1)];
}
/// Return the item at the given index in the deque.
///
/// The first item in the queue is at index 0.
///
/// Asserts that the index is in-bounds.
pub fn at(deque: *const Self, index: usize) T {
assert(index < deque.len);
return deque.buffer[deque.bufferIndex(index)];
}
/// Return pointer to the item at the given index in the deque.
///
/// The first item in the queue is at index 0.
///
/// Asserts that the index is in-bounds.
pub fn atPtr(deque: *const Self, index: usize) *T {
assert(index < deque.len);
return &deque.buffer[deque.bufferIndex(index)];
}
/// Remove and return the first item in the deque or null if empty.
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];
}
/// Remove and return the last item in the deque or null if empty.
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;
}
};
/// Iterates over all items in the deque in order from front to back.
pub fn iterator(deque: *const Self) Iterator {
return .{ .deque = deque, .index = 0 };
}
/// Returns the index in `buffer` where the element at the given
/// index in the logical deque is stored.
fn bufferIndex(deque: *const Self, index: usize) usize {
// This function is written in this way to avoid overflow and
// expensive division.
const head_len = deque.buffer.len - deque.head;
if (index < head_len) {
return deque.head + index;
} else {
return index - head_len;
}
}
};
}
/// Integer addition returning `error.OutOfMemory` on overflow.
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;
// remap in place
return mem.ptr;
} else {
// moving remap
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(),
);
},
// Growing by small, random, linear amounts seems to better test
// ensureTotalCapacityPrecise(), which is the most complex part
// of the Deque implementation.
.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());
}