rockorager.dev
An asynchronous IO runtime
1// This code is mostly a copy of the intrusive queue code from libxev. I've modified it to be a
2// doubly linked list that also ensures a certain state is set on each node when put into the list
3//
4// MIT License
5//
6// Copyright (c) 2023 Mitchell Hashimoto
7//
8// Permission is hereby granted, free of charge, to any person obtaining a copy of this software and
9// associated documentation files (the "Software"), to deal in the Software without restriction,
10// including without limitation the rights to use, copy, modify, merge, publish, distribute,
11// sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is
12// furnished to do so, subject to the following conditions:
13//
14// The above copyright notice and this permission notice shall be included in all copies or
15// substantial portions of the Software.
16//
17// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT
18// NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
20// DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22
23const std = @import("std");
24const assert = std.debug.assert;
25
26/// An intrusive queue implementation. The type T must have a field
27/// "next" of type `?*T` and a field "state" which is an enum with a value matching the passed in
28/// value
29pub fn Intrusive(comptime T: type, comptime state: @Type(.enum_literal)) type {
30 return struct {
31 const Self = @This();
32
33 const set_state = state;
34
35 /// Head is the front of the queue and tail is the back of the queue.
36 head: ?*T = null,
37 tail: ?*T = null,
38
39 /// Enqueue a new element to the back of the queue.
40 pub fn push(self: *Self, v: *T) void {
41 assert(v.next == null);
42 v.state = set_state;
43
44 if (self.tail) |tail| {
45 // If we have elements in the queue, then we add a new tail.
46 tail.next = v;
47 v.prev = tail;
48 self.tail = v;
49 } else {
50 // No elements in the queue we setup the initial state.
51 self.head = v;
52 self.tail = v;
53 }
54 }
55
56 /// Dequeue the next element from the queue.
57 pub fn pop(self: *Self) ?*T {
58 // The next element is in "head".
59 const next = self.head orelse return null;
60
61 // If the head and tail are equal this is the last element
62 // so we also set tail to null so we can now be empty.
63 if (self.head == self.tail) self.tail = null;
64
65 // Head is whatever is next (if we're the last element,
66 // this will be null);
67 self.head = next.next;
68 if (self.head) |head| head.prev = null;
69
70 // We set the "next" field to null so that this element
71 // can be inserted again.
72 next.next = null;
73 next.prev = null;
74 return next;
75 }
76
77 /// Returns true if the queue is empty.
78 pub fn empty(self: Self) bool {
79 return self.head == null;
80 }
81
82 /// Removes the item from the queue. Asserts that Queue contains the item
83 pub fn remove(self: *Self, item: *T) void {
84 assert(self.hasItem(item));
85 if (item.prev) |prev| prev.next = item.next else self.head = item.next;
86
87 if (item.next) |next| next.prev = item.prev else self.tail = item.prev;
88
89 item.prev = null;
90 item.next = null;
91 }
92
93 pub fn hasItem(self: Self, item: *T) bool {
94 var maybe_node = self.head;
95 while (maybe_node) |node| {
96 if (node == item) return true;
97 maybe_node = node.next;
98 } else return false;
99 }
100
101 pub fn len(self: Self) usize {
102 var count: usize = 0;
103 var maybe_node = self.head;
104 while (maybe_node) |node| {
105 count += 1;
106 maybe_node = node.next;
107 }
108 return count;
109 }
110 };
111}