This repository was archived by the owner on Jan 4, 2026. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmanaged_queue.zig
More file actions
237 lines (187 loc) · 7.22 KB
/
managed_queue.zig
File metadata and controls
237 lines (187 loc) · 7.22 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
const std = @import("std");
const testing = std.testing;
const assert = std.debug.assert;
/// The ManagedQueue is a generic queue implementation in Zig that uses a
/// singly linked list. It allows for the management of a queue with operations
/// like enqueueing, dequeueing, checking if the queue is empty, concatenating
/// two queues, and deallocating memory used by the queue. The queue is managed
/// by an allocator, which is used for creating and destroying nodes.
pub fn ManagedQueue(comptime T: type) type {
return struct {
const Self = @This();
const Node = struct {
const Self = @This();
data: T,
next: ?*Node = null,
pub fn new(data: T) Node {
return Node{
.data = data,
.next = null,
};
}
};
head: ?*Node,
tail: ?*Node,
count: usize,
pub fn new() Self {
return Self.empty;
}
pub const empty = Self{
.count = 0,
.head = null,
.tail = null,
};
pub fn deinit(self: *Self, allocator: std.mem.Allocator) void {
// deallocate all items in the queue
while (self.dequeueNode()) |node| {
allocator.destroy(node);
}
// Ensure that the queue is fully deinitialized
assert(self.head == null);
assert(self.tail == null);
assert(self.count == 0);
}
/// Return true if the managed queue `count` is 0
/// Return false if the managed queue > 0 has at least 1 item within.
///
/// Additionally, this validates that the queue is truely empty
pub fn isEmpty(self: *Self) bool {
if (self.count == 0) {
assert(self.head == null);
assert(self.tail == null);
return true;
}
// if one of these fail, that means that the count is borked and we have a
// logic error somewhere in one of the operations so someone has modified
// the count outside of the queue
assert(self.head != null);
assert(self.tail != null);
return false;
}
/// Adds a new element to the end of the queue. A new Node is created with the
/// provided data and added to the end of the queue. The count is incremented
/// after adding the element.
pub fn enqueue(self: *Self, allocator: std.mem.Allocator, data: T) !void {
// create a new node
const node = try allocator.create(Node);
errdefer allocator.destroy(node);
node.* = Node{
.data = data,
.next = null,
};
// append the new node to the end of the queue
{
// always increment the count after this block
defer self.count += 1;
// handle the case the list is empty;
if (self.isEmpty()) {
self.head = node;
self.tail = node;
return;
}
// we know that the tail is not null here;
var temp_tail = self.tail.?;
temp_tail.next = node;
self.tail = node;
}
}
/// Dequeue a single item from the `head` position of the managed queue. If the
/// managed queue is empty `dequeue` returns null. Every dequeued item decrements
/// the managed queue `count`.
pub fn dequeue(self: *Self, allocator: std.mem.Allocator) ?T {
if (self.isEmpty()) return null;
// we know that there is at least one item in the queue
const n = self.head.?;
// capture the data
const data = n.data;
// set the head of the queue to the next item
self.head = n.next;
// if there are no more items in the queue, zero out the queue
if (self.head == null) {
self.tail = null;
}
// decrement the count
self.count -= 1;
// deallocate the node
allocator.destroy(n);
return data;
}
/// internal function used to deliberately dequeue and return the node explicitly
fn dequeueNode(self: *Self) ?*Node {
if (self.isEmpty()) return null;
// we know that there is at least one item in the queue
const n = self.head.?;
// set the head of the queue to the next item
self.head = n.next;
// if there are no more items in the queue, zero out the queue
if (self.head == null) {
self.tail = null;
}
// decrement the count
self.count -= 1;
return n;
}
/// Concatenates another queue (other) to the current queue (self). This operation appends
/// all elements from the other queue to the self queue.
///
/// **Note** This version of concatentate assumes that this and the other queue share the
/// same allocator.
pub fn concatenate(self: *Self, other: *Self) void {
if (other.isEmpty()) return; // No need to do anything if the other queue is empty
if (self.isEmpty()) {
// If `self` is empty, just take `other`'s head and tail
self.head = other.head;
self.tail = other.tail;
} else {
// Link `self.tail` to `other.head`
self.tail.?.next = other.head;
self.tail = other.tail;
}
// Update the count
self.count += other.count;
// Reset the `other` queue
other.head = null;
other.tail = null;
other.count = 0;
}
};
}
test "enqueue/dequeue" {
const allocator = testing.allocator;
var q: ManagedQueue(u8) = .empty;
defer q.deinit(allocator);
try q.enqueue(allocator, 1);
try q.enqueue(allocator, 2);
try q.enqueue(allocator, 3);
try testing.expectEqual(3, q.count);
while (q.dequeue(allocator)) |_| {}
try testing.expectEqual(0, q.count);
}
test "concatenating two queues" {
const allocator = testing.allocator;
var q1: ManagedQueue(u8) = .empty;
defer q1.deinit(allocator);
var q2: ManagedQueue(u8) = .empty;
defer q2.deinit(allocator);
try q1.enqueue(allocator, 1);
try q1.enqueue(allocator, 2);
try q1.enqueue(allocator, 3);
try q1.enqueue(allocator, 4);
try q1.enqueue(allocator, 5);
try q2.enqueue(allocator, 6);
try q2.enqueue(allocator, 7);
try q2.enqueue(allocator, 8);
try q2.enqueue(allocator, 9);
try q2.enqueue(allocator, 10);
try testing.expectEqual(5, q1.count);
try testing.expectEqual(5, q2.count);
q1.concatenate(&q2);
try testing.expectEqual(10, q1.count);
try testing.expectEqual(0, q2.count);
// loop over each item in the queue and verify that everything was added in order
var i: u8 = 1;
while (q1.dequeue(allocator)) |d| : (i += 1) {
try testing.expectEqual(i, d);
}
try testing.expectEqual(10, i - 1);
}