1 /** 2 License: public domain 3 Authors: Simon Bürger 4 */ 5 6 module jive.queue; 7 8 import core.exception : RangeError; 9 import core.stdc.string : memmove, memcpy, memset; 10 import std.algorithm; 11 import std.conv : emplace; 12 import std.range; 13 import std.traits; 14 import jive.internal; 15 16 17 /** 18 * Array structure that allows addition/deletion at both ends. 19 * 20 * Intended to be used as a FIFO-queue or as a stack by combining 21 * `pushFront`/`pushBack` and `popFront`/`popBack` appropriately. Implemented 22 * as a circular buffer inside a continuous block of memory that is 23 * automatically expanded as necessary, similar to jive.Array. 24 */ 25 struct Queue(V) 26 { 27 private V* _ptr = null; // unused elements are undefined 28 private size_t _capacity = 0; // size of buf 29 private size_t _length = 0; // used size 30 private size_t _left = 0; // offset into buffer 31 32 /** constructor that gets content from arbitrary range */ 33 this(Stuff)(Stuff stuff) 34 if(isInputRange!Stuff && is(ElementType!Stuff:V)) 35 { 36 static if(hasLength!Stuff) 37 reserve(_length + stuff.length); 38 39 foreach(ref x; stuff) 40 pushBack(x); 41 } 42 43 /** post-blit that does a full copy */ 44 this(this) 45 { 46 auto newPtr = jiveMalloc!V(_length); 47 48 static if(hasElaborateCopyConstructor!V) 49 { 50 for(size_t i = 0; i < _length; ++i) 51 emplace(newPtr + i, this[i]); 52 } 53 else 54 { 55 if(_left + _length <= _capacity) 56 { 57 memcpy(newPtr, _ptr + _left, V.sizeof * _length); 58 } 59 else 60 { 61 memcpy(newPtr, _ptr + _left, V.sizeof * (_capacity - _left)); 62 memcpy(newPtr + _capacity - _left, _ptr, V.sizeof * (_length - _capacity + _left)); 63 } 64 } 65 _ptr = newPtr; 66 _capacity = _length; 67 _left = 0; 68 } 69 70 /** destructor */ 71 ~this() 72 { 73 static if (hasElaborateDestructor!V) 74 foreach (ref x; this[]) 75 destroy(x); 76 77 jiveFree(_ptr); 78 _ptr = null; // probably not necessary, just a precaution 79 } 80 81 /** check for emptiness */ 82 bool empty() const pure nothrow @property @safe 83 { 84 return _length == 0; 85 } 86 87 /** number of elements */ 88 size_t length() const pure nothrow @property @safe 89 { 90 return _length; 91 } 92 93 /** ditto */ 94 size_t opDollar() const pure nothrow @property @safe 95 { 96 return _length; 97 } 98 99 /** number of elements this structure can hold without further allocations */ 100 size_t capacity() const pure nothrow @property @safe 101 { 102 return _capacity; 103 } 104 105 /** make sure this structure can contain given number of elements without further allocs */ 106 void reserve(size_t newCap, bool overEstimate = false) nothrow @trusted 107 { 108 if(newCap <= _capacity) 109 return; 110 111 if(overEstimate) 112 newCap = max(newCap, 2*_capacity); 113 114 auto newPtr = jiveMalloc!V(newCap); 115 if(_left + _length <= _capacity) 116 { 117 memcpy(newPtr, _ptr + _left, V.sizeof * _length); 118 } 119 else 120 { 121 memcpy(newPtr, _ptr + _left, V.sizeof * (_capacity - _left)); 122 memcpy(newPtr + _capacity - _left, _ptr, V.sizeof * (_length - _capacity + _left)); 123 } 124 125 static if(hasIndirections!V) 126 memset(newPtr + _length, 0, V.sizeof * (newCap - _length)); // prevent false pointers 127 128 jiveFree(_ptr); 129 _ptr = newPtr; 130 _capacity = newCap; 131 _left = 0; 132 } 133 134 /** default range */ 135 auto opSlice() nothrow pure @trusted 136 { 137 if(_left + _length <= _capacity) 138 return chain( 139 _ptr[_left .. _left + _length], 140 _ptr[0 .. 0] 141 ); 142 else 143 return chain( 144 _ptr[_left .. _capacity], 145 _ptr[0 .. _left + _length - _capacity] 146 ); 147 } 148 149 /** ditto */ 150 auto opSlice() const nothrow pure @trusted 151 { 152 if(_left + _length <= _capacity) 153 return chain( 154 _ptr[_left .. _left + _length], 155 _ptr[0 .. 0] 156 ); 157 else 158 return chain( 159 _ptr[_left .. _capacity], 160 _ptr[0 .. _left + _length - _capacity] 161 ); 162 } 163 164 /** ditto */ 165 auto opSlice() immutable nothrow pure @trusted 166 { 167 if(_left + _length <= _capacity) 168 return chain( 169 _ptr[_left .. _left + _length], 170 _ptr[0 .. 0] 171 ); 172 else 173 return chain( 174 _ptr[_left .. _capacity], 175 _ptr[0 .. _left + _length - _capacity] 176 ); 177 } 178 179 /** indexing */ 180 ref inout(V) opIndex(string file = __FILE__, int line = __LINE__)(size_t i) inout pure nothrow @trusted 181 { 182 if(boundsChecks && i >= _length) 183 assert(false, boundsCheckMsg!(file, line)); 184 return _ptr[(_left + i) % _capacity]; 185 } 186 187 /** first element, same as this[0] */ 188 ref inout(V) front(string file = __FILE__, int line = __LINE__)() inout pure nothrow @property 189 { 190 if(boundsChecks && empty) 191 assert(false, boundsCheckMsg!(file, line)); 192 return _ptr[_left]; 193 } 194 195 /** last element, same as this[$-1] */ 196 ref inout(V) back(string file = __FILE__, int line = __LINE__)() inout pure nothrow @property 197 { 198 if(boundsChecks && empty) 199 assert(false, boundsCheckMsg!(file, line)); 200 return _ptr[(_left + _length - 1) % _capacity]; 201 } 202 203 /** add an element to the front of the queue */ 204 void pushFront(V val) @trusted 205 { 206 reserve(_length + 1, true); 207 ++_length; 208 if(_left == 0) 209 _left = _capacity-1; 210 else 211 --_left; 212 moveEmplace(val, front); 213 } 214 215 /** add multiple elements to the front of the queue */ 216 void pushFront(Stuff)(Stuff stuff) 217 if(isInputRange!Stuff && is(ElementType!Stuff:V)) 218 { 219 static if(hasLength!Stuff) 220 reserve(_length + stuff.length, true); 221 222 foreach(ref x; stuff) 223 pushFront(x); 224 } 225 226 /** add an element to the back of the queue */ 227 void pushBack(V val) @trusted 228 { 229 reserve(_length + 1, true); 230 ++_length; 231 moveEmplace(val, back); 232 } 233 234 /** add multiple elements to the back of the queue */ 235 void pushBack(Stuff)(Stuff stuff) 236 if(!is(Stuff:V) && isInputRange!Stuff && is(ElementType!Stuff:V)) 237 { 238 static if(hasLength!Stuff) 239 reserve(_length + stuff.length, true); 240 241 foreach(ref x; stuff) 242 pushBack(x); 243 } 244 245 /** removes first element of the queue and returns it */ 246 V popFront(string file = __FILE__, int line = __LINE__)() @trusted 247 { 248 if(boundsChecks && empty) 249 assert(false, boundsCheckMsg!(file, line)); 250 251 V r = void; 252 memcpy(&r, &front(), V.sizeof); 253 static if(hasIndirections!V) 254 memset(&front(), 0, V.sizeof); 255 _left = (_left + 1) % _capacity; 256 --_length; 257 return r; 258 } 259 260 /** removes last element of the queue and returns it */ 261 V popBack(string file = __FILE__, int line = __LINE__)() @trusted 262 { 263 if(boundsChecks && empty) 264 assert(false, boundsCheckMsg!(file, line)); 265 266 V r = void; 267 memcpy(&r, &back(), V.sizeof); 268 static if(hasIndirections!V) 269 memset(&back(), 0, V.sizeof); 270 --_length; 271 return r; 272 } 273 274 /** remove all content but keep allocated memory */ 275 void clear() @trusted 276 { 277 // TODO: remove @trusted in case V's destructor is @system 278 static if(hasElaborateDestructor!V) 279 for(size_t i = 0; i < _length; ++i) 280 destroy(this[i]); 281 static if(hasIndirections!V) 282 memset(_ptr, 0, V.sizeof * _capacity); 283 _length = 0; 284 } 285 } 286 287 /// 288 /*@nogc*/ nothrow pure @safe unittest 289 { 290 Queue!int a; 291 a.pushBack([1,2,3]); 292 a.pushFront([4,5,6]); 293 294 assert(equal(a[], [6,5,4,1,2,3])); 295 296 assert(a.popFront == 6); 297 assert(a.popBack == 3); 298 299 assert(a.length == 4); 300 } 301 302 // check actual 'circular' buffer 303 @nogc nothrow pure @safe unittest 304 { 305 Queue!int q; 306 q.reserve(3); 307 assert(q.capacity == 3); 308 assert(q.empty); 309 310 // forward 311 q.pushBack(1); 312 q.pushBack(2); 313 q.pushBack(3); 314 assert(q.popFront == 1); q.pushBack(4); 315 assert(q.popFront == 2); q.pushBack(5); 316 assert(q.popFront == 3); q.pushBack(6); 317 assert(q.popFront == 4); q.pushBack(7); 318 assert(q[0] == 5); 319 assert(q[1] == 6); 320 assert(q[2] == 7); 321 322 q.clear(); 323 assert(q.empty); 324 assert(q.capacity == 3); 325 326 // backward 327 q.pushFront(1); 328 q.pushFront(2); 329 q.pushFront(3); 330 assert(q.popBack == 1); q.pushFront(4); 331 assert(q.popBack == 2); q.pushFront(5); 332 assert(q.popBack == 3); q.pushFront(6); 333 assert(q.popBack == 4); q.pushFront(7); 334 assert(q[$-1] == 5); 335 assert(q[$-2] == 6); 336 assert(q[$-3] == 7); 337 } 338 339 // check correct invocation of postblit/destructor 340 unittest 341 { 342 int counter = 0; 343 344 struct S 345 { 346 bool active; 347 this(bool active) { this.active = active; if(active) ++counter; } 348 this(this) { if(active) ++counter; } 349 ~this() { if(active) --counter; } 350 } 351 352 { 353 Queue!S a; 354 assert(counter == 0); 355 a.pushBack(S(true)); 356 assert(counter == 1); 357 a.pushFront(a[0]); 358 assert(counter == 2); 359 a.reserve(5); 360 a.pushBack(a[]); 361 362 Queue!S b = a; 363 assert(equal(a[], b[])); 364 assert(counter == 8); 365 } 366 assert(counter == 0); 367 } 368 369 // check move-semantics 370 unittest 371 { 372 struct S3 373 { 374 int x; 375 alias x this; 376 this(this) { assert(x == 0); } 377 } 378 379 Queue!S3 a; 380 a.pushBack(S3(1)); 381 a.pushBack(S3(2)); 382 a.pushFront(S3(3)); 383 a.reserve(5); 384 a.popBack(); 385 a.popFront(); 386 a[0] = S3(4); 387 a.clear(); 388 } 389 390 // type with no @safe/pure/etc-attributes 391 unittest 392 { 393 struct S 394 { 395 int* x; 396 this(this){ } 397 ~this(){ } 398 } 399 400 static assert(hasIndirections!S); 401 static assert(hasElaborateDestructor!S); 402 403 S s; 404 Queue!S a; 405 a.pushBack(s); 406 a.pushBack([s,s]); 407 a.pushFront(s); 408 a.pushFront([s,s]); 409 a.popBack(); 410 a.popFront(); 411 Queue!S b = a; 412 a.clear(); 413 assert(equal(b[], [s,s,s,s])); 414 }