1 /** 2 Implements a memory block to place elements on. 3 */ 4 5 module alid.blockreusable; 6 7 import alid.errornogc : NogcError; 8 import std.typecons : Flag, Yes; 9 10 // The Error type that ReusableBlock throws 11 private mixin NogcError!"block"; 12 13 /** 14 A reusable memory block for placing objects on. 15 16 The elements are added only at the back either by copying or by moving. They 17 are removed only from the front. The elements are never moved to a different 18 memory location inside the buffer. 19 20 Params: 21 22 T = the type of the elements that will be stored on the block 23 dtors = whether to execute destructors of elements upon removing them 24 */ 25 struct ReusableBlock(T, Flag!"dtors" dtors = Yes.dtors) 26 { 27 private: 28 29 T * ptr_; // The address of the beginning of the block 30 size_t capacity_; // Total elements that the block can hold 31 size_t head_; // The block index where element 0 is currently at 32 size_t tail_; // The block index where the next element will be placed at 33 34 public: 35 36 /** 37 Construct an object that will use the provided memory 38 39 Params: 40 41 buffer = the memory _buffer to use for the elements; the first few 42 bytes of the _buffer may not be used if its `.ptr` property 43 does not match `T.alignof` 44 */ 45 this(ubyte[] buffer) @trusted 46 { 47 const extra = cast(ulong)buffer.ptr % T.alignof; 48 if (extra) { 49 // Align to the next aligned memory location 50 buffer = buffer[T.alignof - extra .. $]; 51 } 52 assert(cast(ulong)buffer.ptr % T.alignof == 0); 53 54 this.ptr_ = cast(T*)(buffer.ptr); 55 this.capacity_ = buffer.length / T.sizeof; 56 this.head_ = 0; 57 this.tail_ = 0; 58 } 59 60 /// Pointer to the beginning of the block 61 inout(T) * ptr() inout 62 { 63 return ptr_; 64 } 65 66 /// Total _capacity of the block 67 size_t capacity() const 68 { 69 return capacity_; 70 } 71 72 /// Number of elements the block currently has room for 73 size_t freeCapacity() const 74 in (tail_ <= capacity_, blockError("Tail is ahead of capacity", this)) 75 { 76 return capacity - tail_; 77 } 78 79 /// Current number of elements in the block 80 size_t length() const 81 in (head_ <= tail_, blockError("Head is ahead of tail", this)) 82 { 83 return tail_ - head_; 84 } 85 86 /// Whether the block has no elements at all 87 bool empty() const 88 { 89 return length == 0; 90 } 91 92 /** 93 Add an _element after the existing elements; lvalues are copied, rvalues 94 are moved. 95 96 Params: 97 98 element = the _element to add 99 */ 100 void opOpAssign(string op, SourceT)(auto ref SourceT element) 101 if (op == "~") 102 in (freeCapacity, blockError("No room to append", this)) 103 { 104 import std.traits : isCopyable; 105 106 // This code is copied from std.array.Appender.put: 107 auto elementUnqual = (() @trusted => & cast() element)(); 108 109 static if (__traits(isRef, element)) 110 { 111 // We have an lvalue 112 import core.lifetime : emplace; 113 import std.format : format; 114 115 static assert(isCopyable!SourceT, 116 format!"%s is not copyable"(SourceT.stringof)); 117 118 emplace(unqualPtr_ + tail_, *elementUnqual); 119 ++tail_; 120 } 121 else 122 { 123 // We have an rvalue 124 this.moveEmplace(element); 125 } 126 } 127 128 /** 129 Calls `~=` to copy the specified _element 130 131 Even rvalues are copied. To move rvalues, either call `moveEmplace` or 132 use `~=` uniformly for both lvalues and rvalues. 133 134 Params: 135 136 element = the _element to copy 137 */ 138 void copyBack(SourceT)(auto ref const(SourceT) element) 139 { 140 // This function copies rvalues because 'auto ref' takes copies of them 141 this ~= element; 142 } 143 144 /** 145 Move the specified _element to the back of existing elements 146 147 Params: 148 149 element = the _element to move 150 */ 151 void moveEmplace(SourceT)(ref SourceT element) 152 in (freeCapacity, blockError("No room to moveEmplaceBack", this)) 153 { 154 import core.lifetime : moveEmplace; 155 156 // This code is copied from std.array.Appender.put: 157 auto elementUnqual = (() @trusted => & cast() element)(); 158 159 moveEmplace(*elementUnqual, *(unqualPtr_ + tail_)); 160 ++tail_; 161 } 162 163 /** 164 Construct a new element after the existing elements 165 166 Params: 167 168 args = the constructor arguments to use 169 */ 170 void emplaceBack(Args...)(auto ref Args args) 171 in (freeCapacity, blockError("No room to emplaceBack", this)) 172 { 173 import core.lifetime : emplace; 174 import std.format : format; 175 176 static assert(__traits(compiles, emplace(ptr_, args)), 177 format!"%s is not emplacable from %s"(T.stringof, Args.stringof)); 178 179 emplace(ptr_ + tail_, args); 180 ++tail_; 181 } 182 183 /** 184 Return a reference to an element 185 186 Params: 187 188 index = the _index of the element to return 189 */ 190 ref inout(T) opIndex(in size_t index) inout 191 in (index < length, blockError("Invalid index", index, length)) 192 { 193 return ptr_[head_ + index]; 194 } 195 196 /** 197 Remove elements from the head of the block. If `n == length`, 198 `freeCapacity` will be equal to `capacity` after this call. Whether the 199 destructors are called on the removed elements is determined by the 200 `dtors` template parameter. 201 202 Params: 203 204 n = number of elements to remove 205 */ 206 void removeFrontN(in size_t n) 207 in (n <= length, blockError("Not enough elements to removeFrontN", n, this)) 208 { 209 import std.traits : hasElaborateDestructor; 210 211 static if (dtors && hasElaborateDestructor!T) 212 { 213 foreach_reverse(i; head_ .. head_ + n) 214 { 215 destroy(unqualPtr_[i]); 216 } 217 } 218 219 if (n == length) 220 { 221 // No element left; start from the beginning 222 head_ = 0; 223 tail_ = 0; 224 } 225 else 226 { 227 head_ += n; 228 } 229 } 230 231 /// The same as calling `this.removeFrontN(this.length)` 232 void clear() 233 { 234 removeFrontN(length); 235 } 236 237 /// Number of elements in the block 238 size_t opDollar() const 239 { 240 return length; 241 } 242 243 /** 244 A slice providing access _to the specified elements 245 246 Params: 247 248 from = the index of the first element of the slice 249 to = the index of the element one beyond the last element of the slice 250 */ 251 inout(T)[] opSlice(in size_t from, in size_t to) inout 252 in (from <= to, blockError("Range begin is greater than end", from, to)) 253 in (to - from <= length, blockError("Range is too long", from, to, length)) 254 { 255 return ptr[head_ + from .. head_ + to]; 256 } 257 258 /// A slice to all elements; the same as `[0..$]` 259 inout(T)[] opSlice() inout 260 { 261 return ptr[head_ .. tail_]; 262 } 263 264 /// String representation of this object mostly for debugging 265 void toString(scope void delegate(in char[]) sink) const 266 { 267 import std.format : formattedWrite; 268 269 sink.formattedWrite!"%s @%s cap:%s elems:[%s..%s]"( 270 T.stringof, ptr_, capacity_, head_, tail_); 271 } 272 273 private auto unqualPtr_() inout 274 { 275 import std.traits : Unqual; 276 277 return cast(Unqual!T*)ptr_; 278 } 279 } 280 281 /// 282 nothrow 283 unittest 284 { 285 // Constructing a block on a piece of memory 286 ubyte[100] buffer; 287 auto b = ReusableBlock!int(buffer); 288 289 // Depending on the alignment of the elements, the capacity may be less than 290 // the requested amount 291 assert(b.capacity <= buffer.length / int.sizeof); 292 293 // Add 2 elements 294 b ~= 0; 295 b ~= 1; 296 297 b.length.shouldBe(2); 298 b[0].shouldBe(0); 299 b[1].shouldBe(1); 300 b.freeCapacity.shouldBe(b.capacity - 2); 301 302 // Remove the first one 303 b.removeFrontN(1); 304 b.length.shouldBe(1); 305 b[0].shouldBe(1); 306 // Note that free capacity does not increase: 307 b.freeCapacity.shouldBe(b.capacity - 2); 308 309 // Remove all elements and reset the block 310 b.clear(); 311 b.length.shouldBe(0); 312 // This time all capacity is free 313 b.freeCapacity.shouldBe(b.capacity); 314 } 315 316 version (unittest) 317 { 318 import alid.test : shouldBe; 319 320 private void assertInitialState(B)(B b) 321 { 322 import std.array : empty; 323 324 b.capacity.shouldBe(b.freeCapacity); 325 b.length.shouldBe(0); 326 assert(b.empty); 327 assert(b[0..$].empty); 328 assert(b[].empty); 329 } 330 331 private auto makeValue(T)(int i) 332 if (is (T == string)) 333 { 334 import std.format : format; 335 336 return format!"value_%s"(i); 337 } 338 339 private auto makeValue(T)(int i) 340 if (!is (T == string)) 341 { 342 return cast(T)i; 343 } 344 } 345 346 unittest 347 { 348 // Initializing with null buffer should not be an error 349 350 auto b = ReusableBlock!int(null); 351 assertInitialState(b); 352 } 353 354 unittest 355 { 356 // Test with some fundamental types 357 358 import std.array : empty; 359 import std.meta : AliasSeq; 360 361 void test(T)() 362 { 363 // Must be large enough to pass range tests below 364 enum length = 40 * int.sizeof; 365 ubyte[length] buffer; 366 auto b = ReusableBlock!T(buffer); 367 const cap = b.capacity; 368 369 assertInitialState(b); 370 371 // Add 1 element 372 const e = makeValue!T(42); 373 b ~= e; 374 b.capacity.shouldBe(cap); 375 b.freeCapacity.shouldBe(b.capacity - 1); 376 b.length.shouldBe(1); 377 assert(!b.empty); 378 b[0].shouldBe(e); 379 b[0..$].shouldBe([ e ]); 380 b[].shouldBe([ e ]); 381 382 // Drop the element 383 b.removeFrontN(1); 384 b.capacity.shouldBe(cap); 385 386 // As all elements are removed, free capacity is increased automatically 387 b.freeCapacity.shouldBe(b.capacity); 388 b.length.shouldBe(0); 389 assert(b.empty); 390 assert(b[0..$].empty); 391 assert(b[].empty); 392 393 // Add another one 394 const f = makeValue!T(43); 395 b ~= f; 396 b.capacity.shouldBe(cap); 397 398 // Note that free capacity is reduced 399 b.freeCapacity.shouldBe(b.capacity - 1); 400 b.length.shouldBe(1); 401 assert(!b.empty); 402 b[0].shouldBe(f); 403 b[0..$].shouldBe([ f ]); 404 b[].shouldBe([ f ]); 405 406 // Clearing should get us back to the beginning 407 b.clear(); 408 assertInitialState(b); 409 410 // Fill test 411 T[] expected; 412 foreach (i; 0 .. b.capacity) 413 { 414 import std.conv : to; 415 416 assert(b.freeCapacity); 417 const elem = makeValue!T(i.to!int); 418 b ~= elem; 419 expected ~= elem; 420 } 421 422 // Maximum capacity should not change 423 b.capacity.shouldBe(cap); 424 b.freeCapacity.shouldBe(0); 425 b.length.shouldBe(b.capacity); 426 assert(!b.empty); 427 b[0..$].shouldBe(expected); 428 b[].shouldBe(expected); 429 430 b.removeFrontN(7); 431 b.length.shouldBe(b.capacity - 7); 432 b[].shouldBe(expected[7..$]); 433 b[0..$].shouldBe(expected[7..$]); 434 b[2..$-1].shouldBe(expected[9..$-1]); 435 436 // Multiple clear calls 437 b.clear(); 438 b.clear(); 439 assertInitialState(b); 440 } 441 442 alias Ts = AliasSeq!(int, const(int), double, immutable(double), ubyte, string); 443 444 foreach (T; Ts) 445 { 446 test!T(); 447 } 448 } 449 450 unittest 451 { 452 import std.meta : AliasSeq; 453 454 struct S 455 { 456 int i = int.max; 457 int j = int.max; 458 459 this(int i, int j) 460 { 461 this.i = i; 462 this.j = j; 463 } 464 465 this(this) {} 466 } 467 468 bool isMoved(ref const(S) s) 469 { 470 return s == S.init; 471 } 472 473 void test(T)() 474 { 475 enum length = 400; 476 auto buffer = new ubyte[length]; 477 auto b = ReusableBlock!T(buffer); 478 479 b ~= T(2, 2); 480 481 const n = T(7, 7); 482 b~= n; 483 assert(!isMoved(n)); 484 485 b.copyBack(n); 486 assert(!isMoved(n)); 487 b.copyBack(T(8, 8)); 488 b.copyBack(n); 489 assert(!isMoved(n)); 490 491 auto m = T(3, 3); 492 b.moveEmplace(m); 493 assert(isMoved(m)); 494 } 495 496 alias Ts = AliasSeq!(S, const(S)); 497 498 foreach (T; Ts) 499 { 500 test!T(); 501 } 502 } 503 504 unittest 505 { 506 // Destructors should be executed when requested 507 508 import std.algorithm : each; 509 import std.format : format; 510 import std.range : iota; 511 import std.typecons : No; 512 513 void test(Flag!"dtors" dtors)(size_t elementCount, size_t expectedDtorCount) 514 { 515 static struct S 516 { 517 size_t * count = null; 518 519 ~this() 520 { 521 if (count) 522 { 523 ++(*count); 524 } 525 } 526 } 527 528 auto b = ReusableBlock!(S, dtors)(new ubyte[100]); 529 530 size_t count = 0; 531 532 iota(elementCount).each!(_ => b ~= S(&count)); 533 b.removeFrontN(elementCount); 534 535 count.shouldBe(expectedDtorCount); 536 } 537 538 test!(Yes.dtors)(10, 10); 539 test!(No.dtors)(10, 0); 540 } 541 542 unittest 543 { 544 // Emplace back from arguments 545 struct S 546 { 547 int i; 548 string s; 549 } 550 551 alias B = ReusableBlock!S; 552 static assert ( __traits(compiles, B.init.emplaceBack(42, "hello"))); 553 static assert (!__traits(compiles, B.init.emplaceBack("hello", 1.5))); 554 }