master
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 /// Return the first item in the deque or null if empty.
178 pub fn front(deque: *const Self) ?T {
179 if (deque.len == 0) return null;
180 return deque.buffer[deque.head];
181 }
182
183 /// Return the last item in the deque or null if empty.
184 pub fn back(deque: *const Self) ?T {
185 if (deque.len == 0) return null;
186 return deque.buffer[deque.bufferIndex(deque.len - 1)];
187 }
188
189 /// Return the item at the given index in the deque.
190 ///
191 /// The first item in the queue is at index 0.
192 ///
193 /// Asserts that the index is in-bounds.
194 pub fn at(deque: *const Self, index: usize) T {
195 assert(index < deque.len);
196 return deque.buffer[deque.bufferIndex(index)];
197 }
198
199 /// Remove and return the first item in the deque or null if empty.
200 pub fn popFront(deque: *Self) ?T {
201 if (deque.len == 0) return null;
202 const pop_index = deque.head;
203 deque.head = deque.bufferIndex(1);
204 deque.len -= 1;
205 return deque.buffer[pop_index];
206 }
207
208 /// Remove and return the last item in the deque or null if empty.
209 pub fn popBack(deque: *Self) ?T {
210 if (deque.len == 0) return null;
211 deque.len -= 1;
212 return deque.buffer[deque.bufferIndex(deque.len)];
213 }
214
215 pub const Iterator = struct {
216 deque: *const Self,
217 index: usize,
218
219 pub fn next(it: *Iterator) ?T {
220 if (it.index < it.deque.len) {
221 defer it.index += 1;
222 return it.deque.at(it.index);
223 } else {
224 return null;
225 }
226 }
227 };
228
229 /// Iterates over all items in the deque in order from front to back.
230 pub fn iterator(deque: *const Self) Iterator {
231 return .{ .deque = deque, .index = 0 };
232 }
233
234 /// Returns the index in `buffer` where the element at the given
235 /// index in the logical deque is stored.
236 fn bufferIndex(deque: *const Self, index: usize) usize {
237 // This function is written in this way to avoid overflow and
238 // expensive division.
239 const head_len = deque.buffer.len - deque.head;
240 if (index < head_len) {
241 return deque.head + index;
242 } else {
243 return index - head_len;
244 }
245 }
246 };
247}
248
249/// Integer addition returning `error.OutOfMemory` on overflow.
250fn addOrOom(a: usize, b: usize) error{OutOfMemory}!usize {
251 const result, const overflow = @addWithOverflow(a, b);
252 if (overflow != 0) return error.OutOfMemory;
253 return result;
254}
255
256test "basic" {
257 const testing = std.testing;
258 const gpa = testing.allocator;
259
260 var q: Deque(u32) = .empty;
261 defer q.deinit(gpa);
262
263 try testing.expectEqual(null, q.popFront());
264 try testing.expectEqual(null, q.popBack());
265
266 try q.pushBack(gpa, 1);
267 try q.pushBack(gpa, 2);
268 try q.pushBack(gpa, 3);
269 try q.pushFront(gpa, 0);
270
271 try testing.expectEqual(0, q.popFront());
272 try testing.expectEqual(1, q.popFront());
273 try testing.expectEqual(3, q.popBack());
274 try testing.expectEqual(2, q.popFront());
275 try testing.expectEqual(null, q.popFront());
276 try testing.expectEqual(null, q.popBack());
277}
278
279test "buffer" {
280 const testing = std.testing;
281
282 var buffer: [4]u32 = undefined;
283 var q: Deque(u32) = .initBuffer(&buffer);
284
285 try testing.expectEqual(null, q.popFront());
286 try testing.expectEqual(null, q.popBack());
287
288 try q.pushBackBounded(1);
289 try q.pushBackBounded(2);
290 try q.pushBackBounded(3);
291 try q.pushFrontBounded(0);
292 try testing.expectError(error.OutOfMemory, q.pushBackBounded(4));
293
294 try testing.expectEqual(0, q.popFront());
295 try testing.expectEqual(1, q.popFront());
296 try testing.expectEqual(3, q.popBack());
297 try testing.expectEqual(2, q.popFront());
298 try testing.expectEqual(null, q.popFront());
299 try testing.expectEqual(null, q.popBack());
300}
301
302test "slow growth" {
303 const testing = std.testing;
304 const gpa = testing.allocator;
305
306 var q: Deque(i32) = .empty;
307 defer q.deinit(gpa);
308
309 try q.ensureTotalCapacityPrecise(gpa, 1);
310 q.pushBackAssumeCapacity(1);
311 try q.ensureTotalCapacityPrecise(gpa, 2);
312 q.pushFrontAssumeCapacity(0);
313 try q.ensureTotalCapacityPrecise(gpa, 3);
314 q.pushBackAssumeCapacity(2);
315 try q.ensureTotalCapacityPrecise(gpa, 5);
316 q.pushBackAssumeCapacity(3);
317 q.pushFrontAssumeCapacity(-1);
318 try q.ensureTotalCapacityPrecise(gpa, 6);
319 q.pushFrontAssumeCapacity(-2);
320
321 try testing.expectEqual(-2, q.popFront());
322 try testing.expectEqual(-1, q.popFront());
323 try testing.expectEqual(3, q.popBack());
324 try testing.expectEqual(0, q.popFront());
325 try testing.expectEqual(2, q.popBack());
326 try testing.expectEqual(1, q.popBack());
327 try testing.expectEqual(null, q.popFront());
328 try testing.expectEqual(null, q.popBack());
329}
330
331test "fuzz against ArrayList oracle" {
332 try std.testing.fuzz({}, fuzzAgainstArrayList, .{});
333}
334
335test "dumb fuzz against ArrayList oracle" {
336 const testing = std.testing;
337 const gpa = testing.allocator;
338
339 const input = try gpa.alloc(u8, 1024);
340 defer gpa.free(input);
341
342 var prng = std.Random.DefaultPrng.init(testing.random_seed);
343 prng.random().bytes(input);
344
345 try fuzzAgainstArrayList({}, input);
346}
347
348fn fuzzAgainstArrayList(_: void, input: []const u8) anyerror!void {
349 const testing = std.testing;
350 const gpa = testing.allocator;
351
352 var q: Deque(u32) = .empty;
353 defer q.deinit(gpa);
354 var l: std.ArrayList(u32) = .empty;
355 defer l.deinit(gpa);
356
357 if (input.len < 2) return;
358
359 var prng = std.Random.DefaultPrng.init(input[0]);
360 const random = prng.random();
361
362 const Action = enum {
363 push_back,
364 push_front,
365 pop_back,
366 pop_front,
367 grow,
368 /// Sentinel to avoid hardcoding the cast below
369 max,
370 };
371 for (input[1..]) |byte| {
372 switch (@as(Action, @enumFromInt(byte % (@intFromEnum(Action.max))))) {
373 .push_back => {
374 const item = random.int(u8);
375 try testing.expectEqual(
376 l.appendBounded(item),
377 q.pushBackBounded(item),
378 );
379 },
380 .push_front => {
381 const item = random.int(u8);
382 try testing.expectEqual(
383 l.insertBounded(0, item),
384 q.pushFrontBounded(item),
385 );
386 },
387 .pop_back => {
388 try testing.expectEqual(l.pop(), q.popBack());
389 },
390 .pop_front => {
391 try testing.expectEqual(
392 if (l.items.len > 0) l.orderedRemove(0) else null,
393 q.popFront(),
394 );
395 },
396 // Growing by small, random, linear amounts seems to better test
397 // ensureTotalCapacityPrecise(), which is the most complex part
398 // of the Deque implementation.
399 .grow => {
400 const growth = random.int(u3);
401 try l.ensureTotalCapacityPrecise(gpa, l.items.len + growth);
402 try q.ensureTotalCapacityPrecise(gpa, q.len + growth);
403 },
404 .max => unreachable,
405 }
406 try testing.expectEqual(l.getLastOrNull(), q.back());
407 try testing.expectEqual(
408 if (l.items.len > 0) l.items[0] else null,
409 q.front(),
410 );
411 try testing.expectEqual(l.items.len, q.len);
412 try testing.expectEqual(l.capacity, q.buffer.len);
413 {
414 var it = q.iterator();
415 for (l.items) |item| {
416 try testing.expectEqual(item, it.next());
417 }
418 try testing.expectEqual(null, it.next());
419 }
420 }
421}