1const std = @import("std");
2const assert = std.debug.assert;
3const Allocator = std.mem.Allocator;
4
5/// A contiguous, growable, double-ended queue.
6///
7/// Pushing/popping items from either end of the queue is O(1).
8pub fn Deque(comptime T: type) type {
9 return struct {
10 const Self = @This();
11
12 /// A ring buffer.
13 buffer: []T,
14 /// The index in buffer where the first item in the logical deque is stored.
15 head: usize,
16 /// The number of items stored in the logical deque.
17 len: usize,
18
19 /// A Deque containing no elements.
20 pub const empty: Self = .{
21 .buffer = &.{},
22 .head = 0,
23 .len = 0,
24 };
25
26 /// Initialize with capacity to hold `capacity` elements.
27 /// The resulting capacity will equal `capacity` exactly.
28 /// Deinitialize with `deinit`.
29 pub fn initCapacity(gpa: Allocator, capacity: usize) Allocator.Error!Self {
30 var deque: Self = .empty;
31 try deque.ensureTotalCapacityPrecise(gpa, capacity);
32 return deque;
33 }
34
35 /// Initialize with externally-managed memory. The buffer determines the
36 /// capacity and the deque is initially empty.
37 ///
38 /// When initialized this way, all functions that accept an Allocator
39 /// argument cause illegal behavior.
40 pub fn initBuffer(buffer: []T) Self {
41 return .{
42 .buffer = buffer,
43 .head = 0,
44 .len = 0,
45 };
46 }
47
48 /// Release all allocated memory.
49 pub fn deinit(deque: *Self, gpa: Allocator) void {
50 gpa.free(deque.buffer);
51 deque.* = undefined;
52 }
53
54 /// Modify the deque so that it can hold at least `new_capacity` items.
55 /// Implements super-linear growth to achieve amortized O(1) push/pop operations.
56 /// Invalidates element pointers if additional memory is needed.
57 pub fn ensureTotalCapacity(deque: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
58 if (deque.buffer.len >= new_capacity) return;
59 return deque.ensureTotalCapacityPrecise(gpa, std.ArrayList(T).growCapacity(new_capacity));
60 }
61
62 /// If the current capacity is less than `new_capacity`, this function will
63 /// modify the deque so that it can hold exactly `new_capacity` items.
64 /// Invalidates element pointers if additional memory is needed.
65 pub fn ensureTotalCapacityPrecise(deque: *Self, gpa: Allocator, new_capacity: usize) Allocator.Error!void {
66 if (deque.buffer.len >= new_capacity) return;
67 const old_buffer = deque.buffer;
68 if (gpa.remap(old_buffer, new_capacity)) |new_buffer| {
69 // If the items wrap around the end of the buffer we need to do
70 // a memcpy to prevent a gap after resizing the buffer.
71 if (deque.head > old_buffer.len - deque.len) {
72 // The gap splits the items in the deque into head and tail parts.
73 // Choose the shorter part to copy.
74 const head = new_buffer[deque.head..old_buffer.len];
75 const tail = new_buffer[0 .. deque.len - head.len];
76 if (head.len > tail.len and new_buffer.len - old_buffer.len > tail.len) {
77 @memcpy(new_buffer[old_buffer.len..][0..tail.len], tail);
78 } else {
79 // In this case overlap is possible if e.g. the capacity increase is 1
80 // and head.len is greater than 1.
81 deque.head = new_buffer.len - head.len;
82 @memmove(new_buffer[deque.head..][0..head.len], head);
83 }
84 }
85 deque.buffer = new_buffer;
86 } else {
87 const new_buffer = try gpa.alloc(T, new_capacity);
88 if (deque.head < old_buffer.len - deque.len) {
89 @memcpy(new_buffer[0..deque.len], old_buffer[deque.head..][0..deque.len]);
90 } else {
91 const head = old_buffer[deque.head..];
92 const tail = old_buffer[0 .. deque.len - head.len];
93 @memcpy(new_buffer[0..head.len], head);
94 @memcpy(new_buffer[head.len..][0..tail.len], tail);
95 }
96 deque.head = 0;
97 deque.buffer = new_buffer;
98 gpa.free(old_buffer);
99 }
100 }
101
102 /// Modify the deque so that it can hold at least `additional_count` **more** items.
103 /// Invalidates element pointers if additional memory is needed.
104 pub fn ensureUnusedCapacity(
105 deque: *Self,
106 gpa: Allocator,
107 additional_count: usize,
108 ) Allocator.Error!void {
109 return deque.ensureTotalCapacity(gpa, try addOrOom(deque.len, additional_count));
110 }
111
112 /// Add one item to the front of the deque.
113 ///
114 /// Invalidates element pointers if additional memory is needed.
115 pub fn pushFront(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void {
116 try deque.ensureUnusedCapacity(gpa, 1);
117 deque.pushFrontAssumeCapacity(item);
118 }
119
120 /// Add one item to the front of the deque.
121 ///
122 /// Never invalidates element pointers.
123 ///
124 /// If the deque lacks unused capacity for the additional item, returns
125 /// `error.OutOfMemory`.
126 pub fn pushFrontBounded(deque: *Self, item: T) error{OutOfMemory}!void {
127 if (deque.buffer.len - deque.len == 0) return error.OutOfMemory;
128 return deque.pushFrontAssumeCapacity(item);
129 }
130
131 /// Add one item to the front of the deque.
132 ///
133 /// Never invalidates element pointers.
134 ///
135 /// Asserts that the deque can hold one additional item.
136 pub fn pushFrontAssumeCapacity(deque: *Self, item: T) void {
137 assert(deque.len < deque.buffer.len);
138 if (deque.head == 0) {
139 deque.head = deque.buffer.len;
140 }
141 deque.head -= 1;
142 deque.buffer[deque.head] = item;
143 deque.len += 1;
144 }
145
146 /// Add one item to the back of the deque.
147 ///
148 /// Invalidates element pointers if additional memory is needed.
149 pub fn pushBack(deque: *Self, gpa: Allocator, item: T) error{OutOfMemory}!void {
150 try deque.ensureUnusedCapacity(gpa, 1);
151 deque.pushBackAssumeCapacity(item);
152 }
153
154 /// Add one item to the back of the deque.
155 ///
156 /// Never invalidates element pointers.
157 ///
158 /// If the deque lacks unused capacity for the additional item, returns
159 /// `error.OutOfMemory`.
160 pub fn pushBackBounded(deque: *Self, item: T) error{OutOfMemory}!void {
161 if (deque.buffer.len - deque.len == 0) return error.OutOfMemory;
162 deque.pushBackAssumeCapacity(item);
163 }
164
165 /// Add one item to the back of the deque.
166 ///
167 /// Never invalidates element pointers.
168 ///
169 /// Asserts that the deque can hold one additional item.
170 pub fn pushBackAssumeCapacity(deque: *Self, item: T) void {
171 assert(deque.len < deque.buffer.len);
172 const buffer_index = deque.bufferIndex(deque.len);
173 deque.buffer[buffer_index] = item;
174 deque.len += 1;
175 }
176
177 /// Add `items` to the front of the deque.
178 /// This is equivalent to iterating `items` in reverse and calling
179 /// `pushFront` on every single entry.
180 ///
181 /// Invalidates element pointers if additional memory is needed.
182 pub fn pushFrontSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void {
183 try deque.ensureUnusedCapacity(gpa, items.len);
184 return deque.pushFrontSliceAssumeCapacity(items);
185 }
186
187 /// Add `items` to the front of the deque.
188 /// This is equivalent to iterating `items` in reverse and calling
189 /// `pushFront` on every single entry.
190 ///
191 /// Never invalidates element pointers.
192 ///
193 /// If the deque lacks unused capacity for the additional items, returns
194 /// `error.OutOfMemory`.
195 pub fn pushFrontSliceBounded(deque: *Self, items: []const T) error{OutOfMemory}!void {
196 if (deque.buffer.len - deque.len < items.len) return error.OutOfMemory;
197 return deque.pushFrontSliceAssumeCapacity(items);
198 }
199
200 /// Add `items` to the front of the deque.
201 /// This is equivalent to iterating `items` in reverse and calling
202 /// `pushFront` on every single entry.
203 ///
204 /// Never invalidates element pointers.
205 ///
206 /// Asserts that the deque can hold the additional items.
207 pub fn pushFrontSliceAssumeCapacity(deque: *Self, items: []const T) void {
208 assert(deque.buffer.len - deque.len >= items.len);
209 if (deque.head < items.len) {
210 @memcpy(deque.buffer[0..deque.head], items[items.len - deque.head ..]);
211 deque.head = deque.buffer.len - items.len + deque.head;
212 @memcpy(deque.buffer[deque.head..], items.ptr);
213 } else {
214 deque.head -= items.len;
215 @memcpy(deque.buffer[deque.head..][0..items.len], items);
216 }
217 deque.len += items.len;
218 }
219
220 /// Add `items` to the back of the deque.
221 /// This is equivalent to iterating `items` in order and calling
222 /// `pushBack` on every single entry.
223 ///
224 /// Invalidates element pointers if additional memory is needed.
225 pub fn pushBackSlice(deque: *Self, gpa: Allocator, items: []const T) error{OutOfMemory}!void {
226 try deque.ensureUnusedCapacity(gpa, items.len);
227 return deque.pushBackSliceAssumeCapacity(items);
228 }
229
230 /// Add `items` to the back of the deque.
231 /// This is equivalent to iterating `items` in order and calling
232 /// `pushBack` on every single entry.
233 ///
234 /// Never invalidates element pointers.
235 ///
236 /// If the deque lacks unused capacity for the additional items, returns
237 /// `error.OutOfMemory`.
238 pub fn pushBackSliceBounded(deque: *Self, items: []const T) error{OutOfMemory}!void {
239 if (deque.buffer.len - deque.len < items.len) return error.OutOfMemory;
240 return deque.pushBackSliceAssumeCapacity(items);
241 }
242
243 /// Add `items` to the back of the deque.
244 /// This is equivalent to iterating `items` in order and calling
245 /// `pushBack` on every single entry.
246 ///
247 /// Never invalidates element pointers.
248 ///
249 /// Asserts that the deque can hold the additional items.
250 pub fn pushBackSliceAssumeCapacity(deque: *Self, items: []const T) void {
251 assert(deque.buffer.len - deque.len >= items.len);
252 const trailing_buffer = deque.buffer[deque.bufferIndex(deque.len)..];
253 if (trailing_buffer.len < items.len) {
254 @memcpy(trailing_buffer, items[0..trailing_buffer.len]);
255 @memcpy(deque.buffer.ptr, items[trailing_buffer.len..]);
256 } else {
257 @memcpy(trailing_buffer[0..items.len], items);
258 }
259 deque.len += items.len;
260 }
261
262 /// Return the first item in the deque or null if empty.
263 pub fn front(deque: *const Self) ?T {
264 if (deque.len == 0) return null;
265 return deque.buffer[deque.head];
266 }
267
268 /// Return pointer to the first item in the deque or null if empty.
269 pub fn frontPtr(deque: *const Self) ?*T {
270 if (deque.len == 0) return null;
271 return &deque.buffer[deque.head];
272 }
273
274 /// Return the last item in the deque or null if empty.
275 pub fn back(deque: *const Self) ?T {
276 if (deque.len == 0) return null;
277 return deque.buffer[deque.bufferIndex(deque.len - 1)];
278 }
279
280 /// Return the last item in the deque or null if empty.
281 pub fn backPtr(deque: *const Self) ?*T {
282 if (deque.len == 0) return null;
283 return &deque.buffer[deque.bufferIndex(deque.len - 1)];
284 }
285
286 /// Return the item at the given index in the deque.
287 ///
288 /// The first item in the queue is at index 0.
289 ///
290 /// Asserts that the index is in-bounds.
291 pub fn at(deque: *const Self, index: usize) T {
292 assert(index < deque.len);
293 return deque.buffer[deque.bufferIndex(index)];
294 }
295
296 /// Return pointer to the item at the given index in the deque.
297 ///
298 /// The first item in the queue is at index 0.
299 ///
300 /// Asserts that the index is in-bounds.
301 pub fn atPtr(deque: *const Self, index: usize) *T {
302 assert(index < deque.len);
303 return &deque.buffer[deque.bufferIndex(index)];
304 }
305
306 /// Remove and return the first item in the deque or null if empty.
307 pub fn popFront(deque: *Self) ?T {
308 if (deque.len == 0) return null;
309 const pop_index = deque.head;
310 deque.head = deque.bufferIndex(1);
311 deque.len -= 1;
312 return deque.buffer[pop_index];
313 }
314
315 /// Remove and return the last item in the deque or null if empty.
316 pub fn popBack(deque: *Self) ?T {
317 if (deque.len == 0) return null;
318 deque.len -= 1;
319 return deque.buffer[deque.bufferIndex(deque.len)];
320 }
321
322 pub const Iterator = struct {
323 deque: *const Self,
324 index: usize,
325
326 pub fn peek(it: Iterator) ?T {
327 if (it.index >= it.deque.len) return null;
328 return it.deque.at(it.index);
329 }
330 pub fn next(it: *Iterator) ?T {
331 const item = it.peek() orelse return null;
332 it.index += 1;
333 return item;
334 }
335
336 pub fn peekPtr(it: Iterator) ?*T {
337 if (it.index >= it.deque.len) return null;
338 return it.deque.atPtr(it.index);
339 }
340 pub fn nextPtr(it: *Iterator) ?*T {
341 const item_ptr = it.peekPtr() orelse return null;
342 it.index += 1;
343 return item_ptr;
344 }
345 };
346
347 /// Iterates over all items in the deque in order from front to back.
348 pub fn iterator(deque: *const Self) Iterator {
349 return .{ .deque = deque, .index = 0 };
350 }
351
352 /// Returns the index in `buffer` where the element at the given
353 /// index in the logical deque is stored.
354 fn bufferIndex(deque: *const Self, index: usize) usize {
355 // This function is written in this way to avoid overflow and
356 // expensive division.
357 const head_len = deque.buffer.len - deque.head;
358 if (index < head_len) {
359 return deque.head + index;
360 } else {
361 return index - head_len;
362 }
363 }
364 };
365}
366
367/// Integer addition returning `error.OutOfMemory` on overflow.
368fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize {
369 const result, const overflow = @addWithOverflow(a, b);
370 if (overflow != 0) return error.OutOfMemory;
371 return result;
372}
373
374test "basic" {
375 const testing = std.testing;
376 const gpa = testing.allocator;
377
378 var q: Deque(u32) = .empty;
379 defer q.deinit(gpa);
380
381 try testing.expectEqual(null, q.popFront());
382 try testing.expectEqual(null, q.popBack());
383
384 try q.pushBack(gpa, 1);
385 try q.pushBack(gpa, 2);
386 try q.pushBack(gpa, 3);
387 try q.pushFront(gpa, 0);
388
389 try testing.expectEqual(0, q.popFront());
390 try testing.expectEqual(1, q.popFront());
391 try testing.expectEqual(3, q.popBack());
392 try testing.expectEqual(2, q.popFront());
393 try testing.expectEqual(null, q.popFront());
394 try testing.expectEqual(null, q.popBack());
395}
396
397test "buffer" {
398 const testing = std.testing;
399
400 var buffer: [4]u32 = undefined;
401 var q: Deque(u32) = .initBuffer(&buffer);
402
403 try testing.expectEqual(null, q.popFront());
404 try testing.expectEqual(null, q.popBack());
405
406 try q.pushBackBounded(1);
407 try q.pushBackBounded(2);
408 try q.pushBackBounded(3);
409 try q.pushFrontBounded(0);
410 try testing.expectError(error.OutOfMemory, q.pushBackBounded(4));
411
412 try testing.expectEqual(0, q.popFront());
413 try testing.expectEqual(1, q.popFront());
414 try testing.expectEqual(3, q.popBack());
415 try testing.expectEqual(2, q.popFront());
416 try testing.expectEqual(null, q.popFront());
417 try testing.expectEqual(null, q.popBack());
418}
419
420test "slow growth" {
421 const testing = std.testing;
422 const gpa = testing.allocator;
423
424 var q: Deque(i32) = .empty;
425 defer q.deinit(gpa);
426
427 try q.ensureTotalCapacityPrecise(gpa, 1);
428 q.pushBackAssumeCapacity(1);
429 try q.ensureTotalCapacityPrecise(gpa, 2);
430 q.pushFrontAssumeCapacity(0);
431 try q.ensureTotalCapacityPrecise(gpa, 3);
432 q.pushBackAssumeCapacity(2);
433 try q.ensureTotalCapacityPrecise(gpa, 5);
434 q.pushBackAssumeCapacity(3);
435 q.pushFrontAssumeCapacity(-1);
436 try q.ensureTotalCapacityPrecise(gpa, 6);
437 q.pushFrontAssumeCapacity(-2);
438
439 try testing.expectEqual(-2, q.popFront());
440 try testing.expectEqual(-1, q.popFront());
441 try testing.expectEqual(3, q.popBack());
442 try testing.expectEqual(0, q.popFront());
443 try testing.expectEqual(2, q.popBack());
444 try testing.expectEqual(1, q.popBack());
445 try testing.expectEqual(null, q.popFront());
446 try testing.expectEqual(null, q.popBack());
447}
448
449test "slice" {
450 const testing = std.testing;
451 const gpa = testing.allocator;
452
453 var q: Deque(i32) = .empty;
454 defer q.deinit(gpa);
455
456 try q.pushBackSlice(gpa, &.{ 3, 4, 5 });
457 try q.pushBackSlice(gpa, &.{ 6, 7 });
458 try q.pushFrontSlice(gpa, &.{2});
459 try q.pushBackSlice(gpa, &.{});
460 try q.pushFrontSlice(gpa, &.{ 0, 1 });
461 try q.pushFrontSlice(gpa, &.{});
462
463 try testing.expectEqual(0, q.popFront());
464 try testing.expectEqual(1, q.popFront());
465 try testing.expectEqual(7, q.popBack());
466 try testing.expectEqual(6, q.popBack());
467
468 try q.pushFrontSlice(gpa, &.{ 0, 1 });
469 try q.pushBackSlice(gpa, &.{ 6, 7 });
470
471 try testing.expectEqual(0, q.popFront());
472 try testing.expectEqual(1, q.popFront());
473 try testing.expectEqual(2, q.popFront());
474 try testing.expectEqual(7, q.popBack());
475 try testing.expectEqual(6, q.popBack());
476 try testing.expectEqual(3, q.popFront());
477 try testing.expectEqual(4, q.popFront());
478 try testing.expectEqual(5, q.popBack());
479 try testing.expectEqual(null, q.popFront());
480 try testing.expectEqual(null, q.popBack());
481}
482
483test "iterator" {
484 const testing = std.testing;
485 const gpa = testing.allocator;
486
487 var q: Deque(i32) = .empty;
488 defer q.deinit(gpa);
489
490 const items: []const i32 = &.{ 0, 1, 2, 3, 4, 5 };
491 try q.pushFrontSlice(gpa, items);
492
493 {
494 var it = q.iterator();
495 for (items) |item| {
496 try testing.expectEqual(item, it.peek());
497 try testing.expectEqual(item, it.next());
498 }
499 try testing.expectEqual(null, it.peek());
500 try testing.expectEqual(null, it.next());
501 }
502 {
503 var it = q.iterator();
504 for (items) |item| {
505 if (it.peekPtr()) |ptr| {
506 try testing.expectEqual(item, ptr.*);
507 } else return error.TestExpectedNonNull;
508 if (it.nextPtr()) |ptr| {
509 try testing.expectEqual(item, ptr.*);
510 } else return error.TestExpectedNonNull;
511 }
512 try testing.expectEqual(null, it.peekPtr());
513 try testing.expectEqual(null, it.nextPtr());
514 }
515}
516
517test "fuzz against ArrayList oracle" {
518 try std.testing.fuzz({}, fuzzAgainstArrayList, .{});
519}
520
521const FuzzAllocator = struct {
522 smith: *std.testing.Smith,
523 bufs: [2][256 * 4]u8 align(4),
524 used_bitmap: u2,
525 used_len: [2]usize,
526
527 pub fn init(smith: *std.testing.Smith) FuzzAllocator {
528 return .{
529 .smith = smith,
530 .bufs = undefined,
531 .used_len = undefined,
532 .used_bitmap = 0,
533 };
534 }
535
536 pub fn allocator(f: *FuzzAllocator) std.mem.Allocator {
537 return .{
538 .ptr = f,
539 .vtable = &.{
540 .alloc = alloc,
541 .resize = resize,
542 .remap = remap,
543 .free = free,
544 },
545 };
546 }
547
548 pub fn allocCount(f: *FuzzAllocator) u2 {
549 return @popCount(f.used_bitmap);
550 }
551
552 fn alloc(ctx: *anyopaque, len: usize, a: std.mem.Alignment, _: usize) ?[*]u8 {
553 const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
554 assert(a == .@"4");
555 assert(len % 4 == 0);
556
557 const slot: u1 = @intCast(@ctz(~f.used_bitmap));
558 const buf: []u8 = &f.bufs[slot];
559 if (len > buf.len) return null;
560 f.used_bitmap |= @as(u2, 1) << slot;
561 f.used_len[slot] = len;
562 return buf.ptr;
563 }
564
565 fn memSlot(f: *FuzzAllocator, mem: []u8) u1 {
566 const slot: u1 = if (&mem[0] == &f.bufs[0][0])
567 0
568 else if (&mem[0] == &f.bufs[1][0])
569 1
570 else
571 unreachable;
572 assert((f.used_bitmap >> slot) & 1 == 1);
573 assert(mem.len == f.used_len[slot]);
574 return slot;
575 }
576
577 fn resize(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) bool {
578 const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
579 assert(a == .@"4");
580 assert(f.allocCount() == 1);
581
582 const slot = f.memSlot(mem);
583 if (new_len > f.bufs[slot].len or f.smith.value(bool)) return false;
584 f.used_len[slot] = new_len;
585 return true;
586 }
587
588 fn remap(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, new_len: usize, _: usize) ?[*]u8 {
589 const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
590 assert(a == .@"4");
591 assert(f.allocCount() == 1);
592
593 const slot = f.memSlot(mem);
594 if (new_len > f.bufs[slot].len or f.smith.value(bool)) return null;
595
596 if (f.smith.value(bool)) {
597 f.used_len[slot] = new_len;
598 // remap in place
599 return mem.ptr;
600 } else {
601 // moving remap
602 const new_slot = ~slot;
603 f.used_bitmap = ~f.used_bitmap;
604 f.used_len[new_slot] = new_len;
605
606 const new_buf = &f.bufs[new_slot];
607 @memcpy(new_buf[0..mem.len], mem);
608 return new_buf.ptr;
609 }
610 }
611
612 fn free(ctx: *anyopaque, mem: []u8, a: std.mem.Alignment, _: usize) void {
613 const f: *FuzzAllocator = @ptrCast(@alignCast(ctx));
614 assert(a == .@"4");
615 f.used_bitmap ^= @as(u2, 1) << f.memSlot(mem);
616 }
617};
618
619fn fuzzAgainstArrayList(_: void, smith: *std.testing.Smith) anyerror!void {
620 const testing = std.testing;
621
622 var q_gpa_inst: FuzzAllocator = .init(smith);
623 var l_gpa_buf: [q_gpa_inst.bufs[0].len]u8 align(4) = undefined;
624 var l_gpa_inst: std.heap.FixedBufferAllocator = .init(&l_gpa_buf);
625 const q_gpa = q_gpa_inst.allocator();
626 const l_gpa = l_gpa_inst.allocator();
627
628 var q: Deque(u32) = .empty;
629 var l: std.ArrayList(u32) = .empty;
630
631 const Action = enum(u8) {
632 grow,
633 push_back,
634 push_front,
635 push_back_slice,
636 push_front_slice,
637 pop_back,
638 pop_front,
639 };
640
641 while (!smith.eosWeightedSimple(15, 1)) {
642 const baseline = testing.Smith.baselineWeights(Action);
643 const grow_weight: testing.Smith.Weight = .value(Action, .grow, 3);
644 switch (smith.valueWeighted(Action, baseline ++ .{grow_weight})) {
645 .push_back => {
646 const item = smith.value(u32);
647 try testing.expectEqual(
648 l.appendBounded(item),
649 q.pushBackBounded(item),
650 );
651 },
652 .push_front => {
653 const item = smith.value(u32);
654 try testing.expectEqual(
655 l.insertBounded(0, item),
656 q.pushFrontBounded(item),
657 );
658 },
659 .push_back_slice => {
660 var buffer: [std.math.maxInt(u3)]u32 = undefined;
661 const items = buffer[0..smith.value(u3)];
662 for (items) |*item| {
663 item.* = smith.value(u32);
664 }
665 try testing.expectEqual(
666 l.appendSliceBounded(items),
667 q.pushBackSliceBounded(items),
668 );
669 },
670 .push_front_slice => {
671 var buffer: [std.math.maxInt(u3)]u32 = undefined;
672 const items = buffer[0..smith.value(u3)];
673 for (items) |*item| {
674 item.* = smith.value(u32);
675 }
676 try testing.expectEqual(
677 l.insertSliceBounded(0, items),
678 q.pushFrontSliceBounded(items),
679 );
680 },
681 .pop_back => {
682 try testing.expectEqual(l.pop(), q.popBack());
683 },
684 .pop_front => {
685 try testing.expectEqual(
686 if (l.items.len > 0) l.orderedRemove(0) else null,
687 q.popFront(),
688 );
689 },
690 // Growing by small, random, linear amounts seems to better test
691 // ensureTotalCapacityPrecise(), which is the most complex part
692 // of the Deque implementation.
693 .grow => {
694 const growth = smith.value(u3);
695 try l.ensureTotalCapacityPrecise(l_gpa, l.items.len + growth);
696 try q.ensureTotalCapacityPrecise(q_gpa, q.len + growth);
697 },
698 }
699 try testing.expectEqual(l.last(), q.back());
700 try testing.expectEqual(
701 if (l.items.len > 0) l.items[0] else null,
702 q.front(),
703 );
704 try testing.expectEqual(l.items.len, q.len);
705 try testing.expectEqual(l.capacity, q.buffer.len);
706 {
707 var it = q.iterator();
708 for (l.items) |item| {
709 try testing.expectEqual(item, it.next());
710 }
711 try testing.expectEqual(null, it.next());
712 }
713 try testing.expectEqual(@intFromBool(q.buffer.len != 0), q_gpa_inst.allocCount());
714 }
715 q.deinit(q_gpa);
716 try testing.expectEqual(0, q_gpa_inst.allocCount());
717}