1 /**
2  * Optimized copying appender, no chaining
3  *
4  * License:
5  *   This Source Code Form is subject to the terms of
6  *   the Mozilla Public License, v. 2.0. If a copy of
7  *   the MPL was not distributed with this file, You
8  *   can obtain one at http://mozilla.org/MPL/2.0/.
9  *
10  * Authors:
11  *   Vladimir Panteleev <vladimir@thecybershadow.net>
12  */
13 
14 module ae.utils.appender;
15 
16 import std.experimental.allocator : makeArray, stateSize;
17 import std.experimental.allocator.common : stateSize;
18 import std.experimental.allocator.gc_allocator : GCAllocator;
19 import std.traits;
20 
21 struct FastAppender(I, Allocator = GCAllocator)
22 {
23 	static assert(T.sizeof == 1, "TODO");
24 
25 private:
26 	enum PAGE_SIZE = 4096;
27 	enum MIN_SIZE  = PAGE_SIZE / 2 + 1; // smallest size that can expand
28 
29 	alias Unqual!I T;
30 
31 	T* cursor, start, end;
32 	bool unique; // Holding a unique reference to the buffer?
33 
34 	void reserve(size_t len)
35 	{
36 		immutable size = cursor-start;
37 		immutable newSize = size + len;
38 		immutable capacity = end-start;
39 
40 		if (start)
41 		{
42 			size_t extended = 0;
43 			static if (is(Allocator == GCAllocator))
44 			{
45 				// std.allocator does not have opportunistic extend
46 				import core.memory;
47 				extended = GC.extend(start, newSize, newSize * 2);
48 			}
49 			else
50 			{
51 				static if (is(hasMember!(Allocator, "expand")))
52 				{
53 					auto buf = start[0..capacity];
54 					if (allocator.expand(buf, newSize))
55 					{
56 						assert(buf.ptr == start);
57 						extended = buf.length;
58 					}
59 				}
60 			}
61 			if (extended)
62 			{
63 				end = start + extended;
64 				return;
65 			}
66 		}
67 
68 		auto newCapacity = newSize < MIN_SIZE ? MIN_SIZE : newSize * 2;
69 
70 		version(none)
71 		{
72 			auto bi = GC.qalloc(newCapacity * T.sizeof, (typeid(T[]).next.flags & 1) ? 0 : GC.BlkAttr.NO_SCAN);
73 			auto newStart = cast(T*)bi.base;
74 			newCapacity = bi.size;
75 		}
76 		else
77 		{
78 			auto buf = allocator.makeArray!T(newCapacity);
79 			assert(buf.length == newCapacity);
80 			auto newStart = buf.ptr;
81 		}
82 
83 		newStart[0..size] = start[0..size];
84 		if (unique)
85 			allocator.deallocate(start[0..capacity]);
86 		start = newStart;
87 		cursor = start + size;
88 		end = start + newCapacity;
89 		unique = true;
90 	}
91 
92 public:
93 	static if (stateSize!Allocator)
94 		Allocator allocator;
95 	else
96 		alias allocator = Allocator.instance;
97 
98 	static if (stateSize!Allocator == 0)
99 	{
100 		/// Preallocate
101 		this(size_t capacity)
102 		{
103 			reserve(capacity);
104 		}
105 	}
106 
107 	/// Start with a given buffer
108 	this(I[] arr)
109 	{
110 		start = cursor = cast(T*)arr.ptr;
111 		end = start + arr.length;
112 	}
113 
114 	@disable this(this);
115 
116 	~this()
117 	{
118 		if (cursor && unique)
119 			allocator.deallocate(start[0..end-start]);
120 	}
121 
122 	/// Put elements.
123 	/// Accepts any number of items (and will allocate at most once per call).
124 	/// Items can be of the element type (I), or arrays.
125 	void putEx(U...)(U items)
126 		if (CanPutAll!U)
127 	{
128 		// TODO: check for static if length is 1
129 		auto cursorEnd = cursor;
130 		foreach (item; items)
131 			static if (is(typeof(cursor[0] = item)))
132 				cursorEnd++;
133 			else
134 			// TODO: is this too lax? it allows passing static arrays by value
135 			static if (is(typeof(cursor[0..1] = item[0..1])))
136 				cursorEnd += item.length;
137 			else
138 				static assert(0, "Can't put " ~ typeof(item).stringof);
139 
140 		if (cursorEnd > end)
141 		{
142 			auto len = cursorEnd - cursor;
143 			reserve(len);
144 			cursorEnd = cursor + len;
145 		}
146 		auto cursor = this.cursor;
147 		this.cursor = cursorEnd;
148 
149 		static if (items.length == 1)
150 		{
151 			alias items[0] item;
152 			static if (is(typeof(cursor[0] = item)))
153 				cursor[0] = item;
154 			else
155 				cursor[0..item.length] = item[];
156 		}
157 		else
158 		{
159 			foreach (item; items)
160 				static if (is(typeof(cursor[0] = item)))
161 					*cursor++ = item;
162 				else
163 				static if (is(typeof(cursor[0..1] = item[0..1])))
164 				{
165 					cursor[0..item.length] = item[];
166 					cursor += item.length;
167 				}
168 		}
169 	}
170 
171 	alias put = putEx;
172 
173 	/// Unsafe. Use together with preallocate().
174 	void uncheckedPut(U...)(U items) @system
175 		if (CanPutAll!U)
176 	{
177 		auto cursor = this.cursor;
178 
179 		foreach (item; items)
180 			static if (is(typeof(cursor[0] = item)))
181 				*cursor++ = item;
182 			else
183 			static if (is(typeof(cursor[0..1] = item[0..1])))
184 			{
185 				cursor[0..item.length] = item;
186 				cursor += item.length;
187 			}
188 
189 		this.cursor = cursor;
190 	}
191 
192 	/// Ensure we can append at least `len` more bytes before allocating.
193 	void preallocate(size_t len)
194 	{
195 		if (end - cursor < len)
196 			reserve(len);
197 	}
198 
199 	/// Allocate a number of bytes, without initializing them,
200 	/// and return the slice to be filled in.
201 	/// The slice reference is temporary, and valid until the next allocation.
202 	T[] allocate(size_t len) @system
203 	{
204 		auto cursorEnd = cursor + len;
205 		if (cursorEnd > end)
206 		{
207 			reserve(len);
208 			cursorEnd = cursor + len;
209 		}
210 		auto result = cursor[0..len];
211 		cursor = cursorEnd;
212 		return result;
213 	}
214 
215 	template CanPutAll(U...)
216 	{
217 		static if (U.length==0)
218 			enum bool CanPutAll = true;
219 		else
220 		{
221 			enum bool CanPutAll =
222 				(
223 					is(typeof(cursor[0   ] = U[0].init      )) ||
224 				 	is(typeof(cursor[0..1] = U[0].init[0..1]))
225 				) && CanPutAll!(U[1..$]);
226 		}
227 	}
228 
229 	void opOpAssign(string op, U)(U item)
230 		if (op=="~" && is(typeof(put!U)))
231 	{
232 		put(item);
233 	}
234 
235 	/// Get a reference to the buffer.
236 	/// Ownership of the buffer is passed to the caller
237 	/// (Appender will not deallocate it after this call).
238 	I[] get()
239 	{
240 		unique = false;
241 		return peek();
242 	}
243 
244 	/// As with `get`, but ownership is preserved.
245 	/// The return value is valid until the next allocation,
246 	/// or until Appender is destroyed.
247 	I[] peek()
248 	{
249 		return cast(I[])start[0..cursor-start];
250 	}
251 
252 	@property size_t capacity()
253 	{
254 		return end-start;
255 	}
256 
257 	@property void capacity(size_t value)
258 	{
259 		immutable current = end - start;
260 		assert(value >= current, "Cannot shrink capacity");
261 		reserve(value - length);
262 	}
263 
264 	@property size_t length()
265 	{
266 		return cursor-start;
267 	}
268 
269 	static if (is(I == T)) // mutable types only
270 	{
271 		/// Set the length (up to the current capacity).
272 		@property void length(size_t value)
273 		{
274 			if (start + value > end)
275 				preallocate(start + value - end);
276 			cursor = start + value;
277 			assert(cursor <= end);
278 		}
279 
280 		/// Effectively empties the data, but preserves the storage for reuse.
281 		/// Same as setting length to 0.
282 		void clear()
283 		{
284 			cursor = start;
285 		}
286 	}
287 }
288 
289 unittest
290 {
291 	import std.meta : AliasSeq;
292 	import std.experimental.allocator.mallocator;
293 
294 	foreach (Allocator; AliasSeq!(GCAllocator, Mallocator))
295 	{
296 		FastAppender!(char, Allocator) a;
297 		assert(a.get == "");
298 		a.put('a', "bcd", 'e');
299 		assert(a.get == "abcde");
300 		a.clear();
301 		assert(a.get == "");
302 		a.allocate(3)[] = 'x';
303 		assert(a.get == "xxx");
304 	}
305 }
306 
307 /// UFCS shim for classic output ranges, which only take a single-argument put.
308 void putEx(R, U...)(auto ref R r, U items)
309 {
310 	foreach (item; items)
311 	{
312 		static if (is(typeof(r.put(item))))
313 			r.put(item);
314 		else
315 		static if (is(typeof(r.put(item[]))))
316 			r.put(item[]);
317 		else
318 		static if (is(typeof({ foreach (c; item) r.put(c); })))
319 			foreach (c; item)
320 				r.put(c);
321 		else
322 		static if (is(typeof(r.put((&item)[0..1]))))
323 			r.put((&item)[0..1]);
324 		else
325 			static assert(false, "Can't figure out how to put " ~ typeof(item).stringof ~ " into a " ~ R.stringof);
326 	}
327 }