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     // Cursor pointing to the current node in iteration.
40     Node* cursor_;
41     // free-list
42     Node* stock;
43 
44     // Length of the queue.
45     size_t length_;
46 
47     // allocate a new node or recycle one from the stock.
48     Node* makeNewNode(T thePayload, Node* theNext = null) @trusted nothrow @nogc
49     {
50         import std.experimental.allocator : make;
51         import std.experimental.allocator.mallocator : Mallocator;
52 
53         Node* result;
54         if (stock !is null)
55         {
56             result = stock;
57             stock = result.next_;
58             result.payload_ = thePayload;
59             result.next_ = theNext;
60         }
61         else
62         {
63             result = Mallocator.instance.make!(Node)(thePayload, theNext);
64             // GC can dispose T managed member if it thinks they are no used...
65             static if (hasIndirections!T)
66             {
67                 import core.memory : GC;
68                 GC.addRange(result, Node.sizeof);
69             }
70         }
71         return result;
72     }
73 
74     // free the stock of available free nodes.
75     void freeStock() @trusted @nogc nothrow
76     {
77         import std.experimental.allocator.mallocator : Mallocator;
78 
79         while (stock !is null)
80         {
81             Node* toFree = stock;
82             stock = stock.next_;
83             static if (hasIndirections!T)
84             {
85                 import core.memory : GC;
86                 GC.removeRange(toFree);
87             }
88             Mallocator.instance.deallocate((cast(ubyte*) toFree)[0 .. Node.sizeof]);
89         }
90     }
91 
92 public:
93 
94     @disable void opAssign(ref Queue);
95     @disable bool opEquals(ref Queue);
96     @disable int opCmp(ref Queue);
97 
98     @disable this(this);
99 
100     ~this() @safe nothrow @nogc
101     {
102         freeStock();
103         stock = first_;
104         freeStock();
105     }
106 
107     /// Start iterating over the queue.
108     void startIteration() @safe pure nothrow @nogc
109     {
110         cursor_ = first_;
111     }
112 
113     /// Returns: The next element in the queue.
114     ref const(T) next() @safe pure nothrow @nogc
115     in
116     {
117         assert(!empty);
118         assert(cursor_ !is null);
119     }
120     do
121     {
122         const previous = cursor_;
123         cursor_ = cursor_.next_;
124         return previous.payload_;
125     }
126 
127     /// Returns: true if itrating is not possible anymore, false otherwise.
128     bool iterationOver() @safe pure nothrow const @nogc
129     {
130         return cursor_ is null;
131     }
132 
133     /// Push a new item to the queue.
134     void push(T item) @nogc @safe nothrow
135     {
136         Node* newLast = makeNewNode(item);
137         if (last_ !is null)
138             last_.next_ = newLast;
139         if (first_ is null)
140             first_      = newLast;
141         last_ = newLast;
142         ++length_;
143     }
144 
145     /// Insert a new item putting it to specified index in the linked list.
146     void insert(T item, const size_t idx) @safe nothrow
147     in
148     {
149         assert(idx <= length_);
150     }
151     do
152     {
153         if (idx == 0)
154         {
155             first_ = makeNewNode(item, first_);
156             ++length_;
157         }
158         // Adding before last added element, so we can just push.
159         else if (idx == length_)
160         {
161             push(item);
162         }
163         else
164         {
165             // Get the element before one we're inserting.
166             Node* current = first_;
167             foreach (i; 1 .. idx)
168                 current = current.next_;
169 
170             assert(current);
171             // Insert a new node after current, and put current.next_ behind it.
172             current.next_ = makeNewNode(item, current.next_);
173             ++length_;
174         }
175     }
176 
177     /// Returns: The next element in the queue and remove it.
178     T pop() @safe nothrow
179     in
180     {
181         assert(!empty, "Trying to pop an element from an empty queue");
182     }
183     do
184     {
185         T result = peek();
186 
187         Node* oldStock = stock;
188         Node* old = first_;
189         first_ = first_.next_;
190 
191         // start the stock from the popped element
192         stock = old;
193         old.next_ = null;
194         // add the existing "old" stock to the new first stock element
195         if (oldStock !is null)
196             stock.next_ = oldStock;
197 
198         if (--length_ == 0)
199         {
200             assert(first_ is null);
201             last_ = null;
202         }
203 
204         return result;
205     }
206 
207     /// Returns: The next element in the queue.
208     ref inout(T) peek() @safe pure nothrow inout @nogc
209     in
210     {
211         assert(!empty, "Trying to peek at an element in an empty queue");
212     }
213     do
214     {
215         return first_.payload_;
216     }
217 
218     /// Returns: true of the queue empty, false otherwise.
219     bool empty() @safe pure nothrow const @nogc
220     {
221         return first_ is null;
222     }
223 
224     /// Returns: The number of elements in the queue.
225     size_t length() @safe pure nothrow const @nogc
226     {
227         return length_;
228     }
229 }
230 
231 @safe nothrow unittest
232 {
233     auto queue = Queue!int();
234     assert(queue.empty);
235     foreach (i; 0 .. 65)
236     {
237         queue.push(5);
238         assert(queue.pop() == 5);
239         assert(queue.empty);
240         assert(queue.length_ == 0);
241     }
242 
243     int[] array = [1, -1, 2, -2, 3, -3, 4, -4, 5, -5];
244     foreach (i; array)
245     {
246         queue.push(i);
247     }
248 
249     array = 42 ~ array[0 .. 3] ~ 42 ~ array[3 .. $] ~ 42;
250     queue.insert(42, 3);
251     queue.insert(42, 0);
252     queue.insert(42, queue.length);
253 
254     int[] array2;
255     while (!queue.empty)
256     {
257         array2 ~= queue.pop();
258     }
259 
260     assert(array == array2);
261 }