1 /** 2 RAII arrays 3 */ 4 module automem.unique_array; 5 6 import automem.traits: isAllocator; 7 import automem.test_utils: TestUtils; 8 import stdx.allocator: theAllocator; 9 10 version(unittest) { 11 import unit_threaded; 12 import test_allocator: TestAllocator; 13 } 14 15 mixin TestUtils; 16 17 /** 18 A unique array similar to C++'s std::unique_ptr<T> when T is an array 19 */ 20 struct UniqueArray(Type, Allocator = typeof(theAllocator)) if(isAllocator!Allocator) { 21 22 import std.traits: hasMember, isScalarType; 23 import std.range: isInputRange; 24 25 enum isSingleton = hasMember!(Allocator, "instance"); 26 enum isTheAllocator = is(Allocator == typeof(theAllocator)); 27 enum isGlobal = isSingleton || isTheAllocator; 28 29 static if(isGlobal) { 30 31 /** 32 The allocator is global, so no need to pass it in to the 33 constructor 34 */ 35 36 this(size_t size) { 37 makeObjects(size); 38 } 39 40 this(size_t size, Type init) { 41 makeObjects(size, init); 42 } 43 44 this(R)(R range) if(isInputRange!R) { 45 makeObjects(range); 46 } 47 48 49 } else { 50 51 /** 52 Non-singleton allocator, must be passed in 53 */ 54 55 this(Allocator allocator) { 56 _allocator = allocator; 57 } 58 59 this(Allocator allocator, size_t size) { 60 _allocator = allocator; 61 makeObjects(size); 62 } 63 64 this(Allocator allocator, size_t size, Type init) { 65 _allocator = allocator; 66 makeObjects(size, init); 67 } 68 69 this(R)(Allocator allocator, R range) if(isInputRange!R) { 70 _allocator = allocator; 71 makeObjects(range); 72 } 73 } 74 75 76 this(T)(UniqueArray!(T, Allocator) other) if(is(T: Type[])) { 77 moveFrom(other); 78 } 79 80 @disable this(this); 81 82 ~this() { 83 deleteObjects; 84 } 85 86 /** 87 Releases ownership and transfers it to the returned 88 Unique object. 89 */ 90 UniqueArray unique() { 91 import std.algorithm: move; 92 UniqueArray u; 93 move(this, u); 94 assert(_objects.length == 0 && _objects.ptr is null); 95 return u; 96 } 97 alias move = unique; 98 99 /** 100 "Truthiness" cast 101 */ 102 bool opCast(T)() const if(is(T == bool)) { 103 return _objects.ptr !is null; 104 } 105 106 void opAssign(T)(UniqueArray!(T, Allocator) other) if(is(T: Type[])) { 107 deleteObject; 108 moveFrom(other); 109 } 110 111 ref inout(Type) opIndex(long i) inout nothrow { 112 return _objects[i]; 113 } 114 115 const(Type)[] opSlice(long i, long j) const nothrow { 116 return _objects[i .. j]; 117 } 118 119 const(Type)[] opSlice() const nothrow { 120 return _objects[0 .. length]; 121 } 122 123 long opDollar() const nothrow { 124 return length; 125 } 126 127 @property long length() const nothrow { 128 return _length; 129 } 130 131 @property void length(long size) { 132 133 import stdx.allocator: expandArray, shrinkArray; 134 135 if(_objects is null) { 136 makeObjects(size); 137 } else if(size == length) { 138 return; 139 } else if(size <= _capacity && size > length) { 140 foreach(ref obj; _objects[_length .. size]) 141 obj = obj.init; 142 _length = size; 143 } else if(size < length) { 144 _length = size; 145 } else { 146 if(size > length) { 147 _allocator.expandArray(_objects, size - length); 148 setLength; 149 } else 150 assert(0); 151 } 152 } 153 154 /** 155 Dereference. const since this otherwise could be used to try 156 and append to the array, which would not be nice 157 */ 158 const(Type[]) opUnary(string s)() const if(s == "*") { 159 return this[]; 160 } 161 162 /** 163 Append to the array 164 */ 165 UniqueArray opBinary(string s)(UniqueArray other) if(s == "~") { 166 this ~= other.unique; 167 return this.unique; 168 } 169 170 /// Append to the array 171 void opOpAssign(string op)(Type other) if(op == "~") { 172 length(length + 1); 173 _objects[$ - 1] = other; 174 } 175 176 /// Append to the array 177 void opOpAssign(string op)(Type[] other) if(op == "~") { 178 const originalLength = length; 179 length(originalLength + other.length); 180 _objects[originalLength .. length] = other[]; 181 } 182 183 /// Append to the array 184 void opOpAssign(string op)(UniqueArray other) if(op == "~") { 185 this ~= other._objects; 186 } 187 188 /// Assign from a slice. 189 void opAssign(Type[] other) { 190 length = other.length; 191 _objects[0 .. length] = other[0 .. length]; 192 } 193 194 /** 195 Reserves memory to prevent too many allocations 196 */ 197 void reserve(in long size) { 198 import stdx.allocator: expandArray; 199 200 if(_objects is null) { 201 const oldLength = length; 202 makeObjects(size); // length = capacity here 203 _length = oldLength; 204 return; 205 } 206 207 if(size < _capacity) { 208 if(size < _length) _length = size; 209 return; 210 } 211 212 _capacity = size; 213 _allocator.expandArray(_objects, _capacity); 214 } 215 216 /** 217 Returns a pointer to the underlying data. @system 218 */ 219 inout(Type)* ptr() inout { 220 return _objects.ptr; 221 } 222 223 static if(isGlobal) { 224 UniqueArray dup() const { 225 return UniqueArray(_objects); 226 } 227 } else static if(isScalarType!Allocator && is(typeof(() { auto a = Allocator.init; auto b = a; }))) { 228 UniqueArray dup() const { 229 return UniqueArray(_allocator, _objects); 230 } 231 } else { 232 UniqueArray dup() { 233 return UniqueArray(_allocator, _objects); 234 } 235 } 236 237 private: 238 239 Type[] _objects; 240 long _length; 241 long _capacity; 242 243 static if(isSingleton) 244 alias _allocator = Allocator.instance; 245 else static if(isTheAllocator) 246 alias _allocator = theAllocator; 247 else 248 Allocator _allocator; 249 250 void makeObjects(size_t size) { 251 import stdx.allocator: makeArray; 252 _objects = _allocator.makeArray!Type(size); 253 setLength; 254 } 255 256 void makeObjects(size_t size, Type init) { 257 import stdx.allocator: makeArray; 258 _objects = _allocator.makeArray!Type(size, init); 259 setLength; 260 261 } 262 263 void makeObjects(R)(R range) if(isInputRange!R) { 264 import stdx.allocator: makeArray; 265 _objects = _allocator.makeArray!Type(range); 266 setLength; 267 } 268 269 void setLength() { 270 _capacity = _length = _objects.length; 271 } 272 273 void deleteObjects() { 274 import stdx.allocator: dispose; 275 import std.traits: isPointer; 276 277 static if(isPointer!Allocator) 278 assert((_objects.length == 0 && _objects.ptr is null) || _allocator !is null); 279 280 if(_objects.ptr !is null) _allocator.dispose(_objects); 281 _length = 0; 282 } 283 284 void moveFrom(T)(ref UniqueArray!(T, Allocator) other) if(is(T: Type[])) { 285 import std.algorithm: swap; 286 _object = other._object; 287 other._object = null; 288 289 swap(_length, other._length); 290 swap(_capacity, other._capacity); 291 292 static if(!isGlobal) { 293 import std.algorithm: move; 294 _allocator = other._allocator.move; 295 } 296 } 297 } 298 299 300 @("default TestAllocator") 301 @system unittest { 302 defaultTest!TestAllocator; 303 } 304 305 306 @("default Mallocator") 307 @system unittest { 308 import stdx.allocator.mallocator: Mallocator; 309 defaultTest!Mallocator; 310 } 311 312 version(unittest) { 313 314 void defaultTest(T)() { 315 import std.algorithm: move; 316 317 mixin AllocatorAlias!T; 318 319 auto ptr = makeUniqueArray!(Struct, Allocator)(allocator, 3); 320 ptr.length.shouldEqual(3); 321 322 ptr[2].twice.shouldEqual(0); 323 ptr[2] = Struct(5); 324 ptr[2].twice.shouldEqual(10); 325 326 ptr[1..$].shouldEqual([Struct(), Struct(5)]); 327 328 typeof(ptr) ptr2 = ptr.move; 329 330 ptr.length.shouldEqual(0); 331 (cast(bool)ptr).shouldBeFalse; 332 ptr2.length.shouldEqual(3); 333 (cast(bool)ptr2).shouldBeTrue; 334 335 // not copyable 336 static assert(!__traits(compiles, ptr2 = ptr1)); 337 338 auto ptr3 = ptr2.unique; 339 ptr3.length.shouldEqual(3); 340 ptr3[].shouldEqual([Struct(), Struct(), Struct(5)]); 341 (*ptr3).shouldEqual([Struct(), Struct(), Struct(5)]); 342 343 ptr3 ~= Struct(10); 344 ptr3[].shouldEqual([Struct(), Struct(), Struct(5), Struct(10)]); 345 346 ptr3 ~= [Struct(11), Struct(12)]; 347 ptr3[].shouldEqual([Struct(), Struct(), Struct(5), Struct(10), Struct(11), Struct(12)]); 348 349 ptr3.length = 3; 350 ptr3[].shouldEqual([Struct(), Struct(), Struct(5)]); 351 352 ptr3.length = 4; 353 ptr3[].shouldEqual([Struct(), Struct(), Struct(5), Struct()]); 354 355 ptr3.length = 1; 356 357 ptr3 ~= makeUniqueArray!(Struct, Allocator)(allocator, 1); 358 359 ptr3[].shouldEqual([Struct(), Struct()]); 360 361 auto ptr4 = makeUniqueArray!(Struct, Allocator)(allocator, 1); 362 363 ptr3 ~= ptr4.unique; 364 ptr3[].shouldEqual([Struct(), Struct(), Struct()]); 365 366 ptr3 = [Struct(7), Struct(9)]; 367 ptr3[].shouldEqual([Struct(7), Struct(9)]); 368 } 369 } 370 371 /// 372 @("@nogc") 373 @system @nogc unittest { 374 375 import stdx.allocator.mallocator: Mallocator; 376 377 auto arr = UniqueArray!(NoGcStruct, Mallocator)(2); 378 assert(arr.length == 2); 379 380 arr[0] = NoGcStruct(1); 381 arr[1] = NoGcStruct(3); 382 383 { 384 NoGcStruct[2] expected = [NoGcStruct(1), NoGcStruct(3)]; 385 assert(arr[] == expected[]); 386 } 387 388 auto arr2 = UniqueArray!(NoGcStruct, Mallocator)(1); 389 arr ~= arr2.unique; 390 391 { 392 NoGcStruct[3] expected = [NoGcStruct(1), NoGcStruct(3), NoGcStruct()]; 393 assert(arr[] == expected[]); 394 } 395 } 396 397 @("@nogc @safe") 398 @safe @nogc unittest { 399 auto allocator = SafeAllocator(); 400 auto arr = UniqueArray!(NoGcStruct, SafeAllocator)(SafeAllocator(), 6); 401 assert(arr.length == 6); 402 } 403 404 405 @("init TestAllocator") 406 @system unittest { 407 auto allocator = TestAllocator(); 408 auto arr = UniqueArray!(Struct, TestAllocator*)(&allocator, 2, Struct(7)); 409 arr[].shouldEqual([Struct(7), Struct(7)]); 410 } 411 412 @("init Mallocator") 413 @system unittest { 414 import stdx.allocator.mallocator: Mallocator; 415 alias allocator = Mallocator.instance; 416 auto arr = UniqueArray!(Struct, Mallocator)(2, Struct(7)); 417 arr[].shouldEqual([Struct(7), Struct(7)]); 418 } 419 420 421 @("range TestAllocator") 422 @system unittest { 423 auto allocator = TestAllocator(); 424 auto arr = UniqueArray!(Struct, TestAllocator*)(&allocator, [Struct(1), Struct(2)]); 425 arr[].shouldEqual([Struct(1), Struct(2)]); 426 } 427 428 @("range Mallocator") 429 @system unittest { 430 import stdx.allocator.mallocator: Mallocator; 431 auto arr = UniqueArray!(Struct, Mallocator)([Struct(1), Struct(2)]); 432 arr[].shouldEqual([Struct(1), Struct(2)]); 433 } 434 435 436 @("theAllocator") 437 @system unittest { 438 with(theTestAllocator) { 439 auto arr = UniqueArray!Struct(2); 440 arr[].shouldEqual([Struct(), Struct()]); 441 } 442 } 443 444 @("issue 1 array") 445 @system unittest { 446 import stdx.allocator.mallocator; 447 UniqueArray!(int, Mallocator) a; 448 a ~= [0, 1]; 449 } 450 451 @("issue 1 value") 452 @system unittest { 453 import stdx.allocator.mallocator; 454 UniqueArray!(int, Mallocator) a; 455 a ~= 7; 456 } 457 458 @("issue 1 UniqueArray") 459 @system unittest { 460 import stdx.allocator.mallocator; 461 UniqueArray!(int, Mallocator) a; 462 a ~= UniqueArray!(int, Mallocator)([1, 2, 3]); 463 } 464 465 @("dereference") 466 unittest { 467 import stdx.allocator.mallocator; 468 UniqueArray!(int, Mallocator) a; 469 a ~= [0, 1]; 470 (*a).shouldEqual([0, 1]); 471 } 472 473 @("reserve from nothing") 474 @system unittest { 475 auto allocator = TestAllocator(); 476 auto a = UniqueArray!(int, TestAllocator*)(&allocator); 477 a.reserve(10); //allocates here 478 a ~= [1, 2, 3]; // should not allocate 479 a ~= [4, 5, 6, 7, 8, 9]; //should not allocate 480 a[].shouldEqual([1, 2, 3, 4, 5, 6, 7, 8, 9]); 481 allocator.numAllocations.shouldEqual(1); 482 } 483 484 @("reserve from existing expand") 485 @system unittest { 486 auto allocator = TestAllocator(); 487 auto a = UniqueArray!(int, TestAllocator*)(&allocator, [1, 2]); //allocates here 488 a.reserve(10); //allocates here 489 a ~= [3, 4]; // should not allocate 490 a ~= [5, 6, 7, 8, 9]; //should not allocate 491 a[].shouldEqual([1, 2, 3, 4, 5, 6, 7, 8, 9]); 492 allocator.numAllocations.shouldEqual(2); 493 } 494 495 @("reserve from existing reduce") 496 @system unittest { 497 auto allocator = TestAllocator(); 498 auto a = UniqueArray!(int, TestAllocator*)(&allocator, [1, 2, 3, 4, 5]); //allocates here 499 a.reserve(2); // should not allocate, changes length to 2 500 a ~= [5, 6]; // should not allocate 501 a[].shouldEqual([1, 2, 5, 6]); 502 allocator.numAllocations.shouldEqual(1); 503 } 504 505 @("Append 2 arrays") 506 @system unittest { 507 auto allocator = TestAllocator(); 508 auto a = UniqueArray!(int, TestAllocator*)(&allocator, [1, 2, 3]) ~ 509 UniqueArray!(int, TestAllocator*)(&allocator, [4, 5]); 510 a[].shouldEqual([1, 2, 3, 4, 5]); 511 } 512 513 @("ptr") 514 @system unittest { 515 auto allocator = TestAllocator(); 516 auto a = UniqueArray!(int, TestAllocator*)(&allocator, [1, 2, 3, 4, 5]); 517 auto ptr = a.ptr; 518 ++ptr; 519 (*ptr).shouldEqual(2); 520 } 521 522 @("dup TestAllocator") 523 @system unittest { 524 auto allocator = TestAllocator(); 525 auto a = UniqueArray!(int, TestAllocator*)(&allocator, [1, 2, 3, 4, 5]); 526 auto b = a.dup; 527 allocator.numAllocations.shouldEqual(2); 528 b[].shouldEqual([1, 2, 3, 4, 5]); 529 } 530 531 @("dup Mallocator") 532 @system unittest { 533 import stdx.allocator.mallocator: Mallocator; 534 auto a = UniqueArray!(int, Mallocator)([1, 2, 3, 4, 5]); 535 auto b = a.dup; 536 b[].shouldEqual([1, 2, 3, 4, 5]); 537 } 538 539 @("dup TestAllocator indirections") 540 @system unittest { 541 auto allocator = TestAllocator(); 542 struct String { string s; } 543 auto a = UniqueArray!(String, TestAllocator*)(&allocator, [String("foo"), String("bar")]); 544 auto b = a.dup; 545 a[0] = String("quux"); 546 a[1] = String("toto"); 547 allocator.numAllocations.shouldEqual(2); 548 a[].shouldEqual([String("quux"), String("toto")]); 549 b[].shouldEqual([String("foo"), String("bar")]); 550 } 551 552 @("Set length to the same length") 553 unittest { 554 auto allocator = TestAllocator(); 555 auto a = UniqueArray!(Struct, TestAllocator*)(&allocator, [Struct(2), Struct(3)]); 556 a.length = 2; 557 } 558 559 version(unittest) { 560 561 mixin template AllocatorAlias(T) { 562 import std.traits: hasMember; 563 564 enum isGlobal = hasMember!(T, "instance"); 565 566 static if(isGlobal) { 567 alias allocator = T.instance; 568 alias Allocator = T; 569 } else { 570 auto allocator = T(); 571 alias Allocator = T*; 572 } 573 } 574 575 576 auto makeUniqueArray(T, A1, A2, Args...)(ref A2 allocator, Args args) { 577 578 import std.traits: isPointer, hasMember; 579 580 enum isGlobal = hasMember!(A1, "instance"); 581 582 static if(isGlobal) 583 return UniqueArray!(T, A1)(args); 584 else static if(isPointer!A1) 585 return UniqueArray!(T, A1)(&allocator, args); 586 else 587 return UniqueArray!(T, A1)(allocator, args); 588 } 589 590 }