1
2 // Copyright Ferdinand Majerech 2011-2014.
3 // Distributed under the Boost Software License, Version 1.0.
4 // (See accompanying file LICENSE_1_0.txt or copy at
5 // http://www.boost.org/LICENSE_1_0.txt)
6
7 module dyaml.queue;
8
9
10 import std.traits : hasMember, hasIndirections;
11
12 package:
13
14 /// Simple queue implemented as a singly linked list with a tail pointer.
15 ///
16 /// Needed in some D:YAML code that needs a queue-like structure without too much
17 /// reallocation that goes with an array.
18 ///
19 /// Allocations are non-GC and are damped by a free-list based on the nodes
20 /// that are removed. Note that elements lifetime must be managed
21 /// outside.
22 struct Queue(T)
23 if (!hasMember!(T, "__xdtor"))
24 {
25
26 private:
27
28 // Linked list node containing one element and pointer to the next node.
29 struct Node
30 {
31 T payload_;
32 Node* next_;
33 }
34
35 // Start of the linked list - first element added in time (end of the queue).
36 Node* first_;
37 // Last element of the linked list - last element added in time (start of the queue).
38 Node* last_;
39 // free-list
40 Node* stock;
41
42 // Length of the queue.
43 size_t length_;
44
45 // allocate a new node or recycle one from the stock.
46 Node* makeNewNode(T thePayload, Node* theNext = null) @trusted nothrow @nogc
47 {
48 import std.experimental.allocator : make;
49 import std.experimental.allocator.mallocator : Mallocator;
50
51 Node* result;
52 if (stock !is null)
53 {
54 result = stock;
55 stock = result.next_;
56 result.payload_ = thePayload;
57 result.next_ = theNext;
58 }
59 else
60 {
61 result = Mallocator.instance.make!(Node)(thePayload, theNext);
62 // GC can dispose T managed member if it thinks they are no used...
63 static if (hasIndirections!T)
64 {
65 import core.memory : GC;
66 GC.addRange(result, Node.sizeof);
67 }
68 }
69 return result;
70 }
71
72 // free the stock of available free nodes.
73 void freeStock() @trusted @nogc nothrow
74 {
75 import std.experimental.allocator.mallocator : Mallocator;
76
77 while (stock !is null)
78 {
79 Node* toFree = stock;
80 stock = stock.next_;
81 static if (hasIndirections!T)
82 {
83 import core.memory : GC;
84 GC.removeRange(toFree);
85 }
86 Mallocator.instance.deallocate((cast(ubyte*) toFree)[0 .. Node.sizeof]);
87 }
88 }
89
90 public:
91
92 @disable void opAssign(ref Queue);
93 @disable bool opEquals(ref Queue);
94 @disable int opCmp(ref Queue);
95
96 this(this) @safe nothrow @nogc
97 {
98 auto node = first_;
99 first_ = null;
100 last_ = null;
101 while (node !is null)
102 {
103 Node* newLast = makeNewNode(node.payload_);
104 if (last_ !is null)
105 last_.next_ = newLast;
106 if (first_ is null)
107 first_ = newLast;
108 last_ = newLast;
109 node = node.next_;
110 }
111 }
112
113 ~this() @safe nothrow @nogc
114 {
115 freeStock();
116 stock = first_;
117 freeStock();
118 }
119
120 /// Returns a forward range iterating over this queue.
121 auto range() @safe pure nothrow @nogc
122 {
123 static struct Result
124 {
125 private Node* cursor;
126
127 void popFront() @safe pure nothrow @nogc
128 {
129 cursor = cursor.next_;
130 }
131 ref T front() @safe pure nothrow @nogc
132 in(cursor !is null)
133 {
134 return cursor.payload_;
135 }
136 bool empty() @safe pure nothrow @nogc const
137 {
138 return cursor is null;
139 }
140 }
141 return Result(first_);
142 }
143
144 /// Push a new item to the queue.
145 void push(T item) @nogc @safe nothrow
146 {
147 Node* newLast = makeNewNode(item);
148 if (last_ !is null)
149 last_.next_ = newLast;
150 if (first_ is null)
151 first_ = newLast;
152 last_ = newLast;
153 ++length_;
154 }
155
156 /// Insert a new item putting it to specified index in the linked list.
157 void insert(T item, const size_t idx) @safe nothrow
158 in
159 {
160 assert(idx <= length_);
161 }
162 do
163 {
164 if (idx == 0)
165 {
166 first_ = makeNewNode(item, first_);
167 ++length_;
168 }
169 // Adding before last added element, so we can just push.
170 else if (idx == length_)
171 {
172 push(item);
173 }
174 else
175 {
176 // Get the element before one we're inserting.
177 Node* current = first_;
178 foreach (i; 1 .. idx)
179 current = current.next_;
180
181 assert(current);
182 // Insert a new node after current, and put current.next_ behind it.
183 current.next_ = makeNewNode(item, current.next_);
184 ++length_;
185 }
186 }
187
188 /// Returns: The next element in the queue and remove it.
189 T pop() @safe nothrow
190 in
191 {
192 assert(!empty, "Trying to pop an element from an empty queue");
193 }
194 do
195 {
196 T result = peek();
197
198 Node* oldStock = stock;
199 Node* old = first_;
200 first_ = first_.next_;
201
202 // start the stock from the popped element
203 stock = old;
204 old.next_ = null;
205 // add the existing "old" stock to the new first stock element
206 if (oldStock !is null)
207 stock.next_ = oldStock;
208
209 if (--length_ == 0)
210 {
211 assert(first_ is null);
212 last_ = null;
213 }
214
215 return result;
216 }
217
218 /// Returns: The next element in the queue.
219 ref inout(T) peek() @safe pure nothrow inout @nogc
220 in
221 {
222 assert(!empty, "Trying to peek at an element in an empty queue");
223 }
224 do
225 {
226 return first_.payload_;
227 }
228
229 /// Returns: true of the queue empty, false otherwise.
230 bool empty() @safe pure nothrow const @nogc
231 {
232 return first_ is null;
233 }
234
235 /// Returns: The number of elements in the queue.
236 size_t length() @safe pure nothrow const @nogc
237 {
238 return length_;
239 }
240 }
241
242 @safe nothrow unittest
243 {
244 auto queue = Queue!int();
245 assert(queue.empty);
246 foreach (i; 0 .. 65)
247 {
248 queue.push(5);
249 assert(queue.pop() == 5);
250 assert(queue.empty);
251 assert(queue.length_ == 0);
252 }
253
254 int[] array = [1, -1, 2, -2, 3, -3, 4, -4, 5, -5];
255 foreach (i; array)
256 {
257 queue.push(i);
258 }
259
260 array = 42 ~ array[0 .. 3] ~ 42 ~ array[3 .. $] ~ 42;
261 queue.insert(42, 3);
262 queue.insert(42, 0);
263 queue.insert(42, queue.length);
264
265 int[] array2;
266 while (!queue.empty)
267 {
268 array2 ~= queue.pop();
269 }
270
271 assert(array == array2);
272 }