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 }