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 }