1 // Written in the D programming language. 2 /** 3 4 High-level interface for allocators. Implements bundled allocation/creation 5 and destruction/deallocation of data including `struct`s and `class`es, 6 and also array primitives related to allocation. This module is the entry point 7 for both making use of allocators and for their documentation. 8 9 $(SCRIPT inhibitQuickIndex = 1;) 10 $(BOOKTABLE, 11 $(TR $(TH Category) $(TH Functions)) 12 $(TR $(TD Make) $(TD 13 $(LREF make) 14 $(LREF makeArray) 15 $(LREF makeMultidimensionalArray) 16 )) 17 $(TR $(TD Dispose) $(TD 18 $(LREF dispose) 19 $(LREF disposeMultidimensionalArray) 20 )) 21 $(TR $(TD Modify) $(TD 22 $(LREF expandArray) 23 $(LREF shrinkArray) 24 )) 25 $(TR $(TD Global) $(TD 26 $(LREF processAllocator) 27 $(LREF theAllocator) 28 )) 29 $(TR $(TD Class interface) $(TD 30 $(LREF allocatorObject) 31 $(LREF CAllocatorImpl) 32 $(LREF IAllocator) 33 )) 34 ) 35 36 Synopsis: 37 --- 38 // Allocate an int, initialize it with 42 39 int* p = theAllocator.make!int(42); 40 assert(*p == 42); 41 // Destroy and deallocate it 42 theAllocator.dispose(p); 43 44 // Allocate using the global process allocator 45 p = processAllocator.make!int(100); 46 assert(*p == 100); 47 // Destroy and deallocate 48 processAllocator.dispose(p); 49 50 // Create an array of 50 doubles initialized to -1.0 51 double[] arr = theAllocator.makeArray!double(50, -1.0); 52 // Append two zeros to it 53 theAllocator.expandArray(arr, 2, 0.0); 54 // On second thought, take that back 55 theAllocator.shrinkArray(arr, 2); 56 // Destroy and deallocate 57 theAllocator.dispose(arr); 58 --- 59 60 $(H2 Layered Structure) 61 62 D's allocators have a layered structure in both implementation and documentation: 63 64 $(OL 65 $(LI A high-level, dynamically-typed layer (described further down in this 66 module). It consists of an interface called $(LREF IAllocator), which concrete 67 allocators need to implement. The interface primitives themselves are oblivious 68 to the type of the objects being allocated; they only deal in `void[]`, by 69 necessity of the interface being dynamic (as opposed to type-parameterized). 70 Each thread has a current allocator it uses by default, which is a thread-local 71 variable $(LREF theAllocator) of type $(LREF IAllocator). The process has a 72 global allocator called $(LREF processAllocator), also of type $(LREF 73 IAllocator). When a new thread is created, $(LREF processAllocator) is copied 74 into $(LREF theAllocator). An application can change the objects to which these 75 references point. By default, at application startup, $(LREF processAllocator) 76 refers to an object that uses D's garbage collected heap. This layer also 77 include high-level functions such as $(LREF make) and $(LREF dispose) that 78 comfortably allocate/create and respectively destroy/deallocate objects. This 79 layer is all needed for most casual uses of allocation primitives.) 80 81 $(LI A mid-level, statically-typed layer for assembling several allocators into 82 one. It uses properties of the type of the objects being created to route 83 allocation requests to possibly specialized allocators. This layer is relatively 84 thin and implemented and documented in the $(MREF 85 std,experimental,allocator,typed) module. It allows an interested user to e.g. 86 use different allocators for arrays versus fixed-sized objects, to the end of 87 better overall performance.) 88 89 $(LI A low-level collection of highly generic $(I heap building blocks)$(MDASH) 90 Lego-like pieces that can be used to assemble application-specific allocators. 91 The real allocation smarts are occurring at this level. This layer is of 92 interest to advanced applications that want to configure their own allocators. 93 A good illustration of typical uses of these building blocks is module $(MREF 94 std,experimental,allocator,showcase) which defines a collection of frequently- 95 used preassembled allocator objects. The implementation and documentation entry 96 point is $(MREF std,experimental,allocator,building_blocks). By design, the 97 primitives of the static interface have the same signatures as the $(LREF 98 IAllocator) primitives but are for the most part optional and driven by static 99 introspection. The parameterized class $(LREF CAllocatorImpl) offers an 100 immediate and useful means to package a static low-level allocator into an 101 implementation of $(LREF IAllocator).) 102 103 $(LI Core allocator objects that interface with D's garbage collected heap 104 ($(MREF std,experimental,allocator,gc_allocator)), the C `malloc` family 105 ($(MREF std,experimental,allocator,mallocator)), and the OS ($(MREF 106 std,experimental,allocator,mmap_allocator)). Most custom allocators would 107 ultimately obtain memory from one of these core allocators.) 108 ) 109 110 $(H2 Idiomatic Use of `std.experimental.allocator`) 111 112 As of this time, `std.experimental.allocator` is not integrated with D's 113 built-in operators that allocate memory, such as `new`, array literals, or 114 array concatenation operators. That means `std.experimental.allocator` is 115 opt-in$(MDASH)applications need to make explicit use of it. 116 117 For casual creation and disposal of dynamically-allocated objects, use $(LREF 118 make), $(LREF dispose), and the array-specific functions $(LREF makeArray), 119 $(LREF expandArray), and $(LREF shrinkArray). These use by default D's garbage 120 collected heap, but open the application to better configuration options. These 121 primitives work either with `theAllocator` but also with any allocator obtained 122 by combining heap building blocks. For example: 123 124 ---- 125 void fun(size_t n) 126 { 127 // Use the current allocator 128 int[] a1 = theAllocator.makeArray!int(n); 129 scope(exit) theAllocator.dispose(a1); 130 ... 131 } 132 ---- 133 134 To experiment with alternative allocators, set $(LREF theAllocator) for the 135 current thread. For example, consider an application that allocates many 8-byte 136 objects. These are not well supported by the default allocator, so a 137 $(MREF_ALTTEXT free list allocator, 138 std,experimental,allocator,building_blocks,free_list) would be recommended. 139 To install one in `main`, the application would use: 140 141 ---- 142 void main() 143 { 144 import std.experimental.allocator.building_blocks.free_list 145 : FreeList; 146 theAllocator = allocatorObject(FreeList!8()); 147 ... 148 } 149 ---- 150 151 $(H3 Saving the `IAllocator` Reference For Later Use) 152 153 As with any global resource, setting `theAllocator` and `processAllocator` 154 should not be done often and casually. In particular, allocating memory with 155 one allocator and deallocating with another causes undefined behavior. 156 Typically, these variables are set during application initialization phase and 157 last through the application. 158 159 To avoid this, long-lived objects that need to perform allocations, 160 reallocations, and deallocations relatively often may want to store a reference 161 to the allocator object they use throughout their lifetime. Then, instead of 162 using `theAllocator` for internal allocation-related tasks, they'd use the 163 internally held reference. For example, consider a user-defined hash table: 164 165 ---- 166 struct HashTable 167 { 168 private IAllocator allocator; 169 this(size_t buckets, IAllocator allocator = theAllocator) { 170 this.allocator = allocator; 171 ... 172 } 173 // Getter and setter 174 IAllocator allocator() { return allocator; } 175 void allocator(IAllocator a) { assert(empty); allocator = a; } 176 } 177 ---- 178 179 Following initialization, the `HashTable` object would consistently use its 180 `allocator` object for acquiring memory. Furthermore, setting 181 `HashTable.allocator` to point to a different allocator should be legal but 182 only if the object is empty; otherwise, the object wouldn't be able to 183 deallocate its existing state. 184 185 $(H3 Using Allocators without `IAllocator`) 186 187 Allocators assembled from the heap building blocks don't need to go through 188 `IAllocator` to be usable. They have the same primitives as `IAllocator` and 189 they work with $(LREF make), $(LREF makeArray), $(LREF dispose) etc. So it 190 suffice to create allocator objects wherever fit and use them appropriately: 191 192 ---- 193 void fun(size_t n) 194 { 195 // Use a stack-installed allocator for up to 64KB 196 StackFront!65536 myAllocator; 197 int[] a2 = myAllocator.makeArray!int(n); 198 scope(exit) myAllocator.dispose(a2); 199 ... 200 } 201 ---- 202 203 In this case, `myAllocator` does not obey the `IAllocator` interface, but 204 implements its primitives so it can work with `makeArray` by means of duck 205 typing. 206 207 One important thing to note about this setup is that statically-typed assembled 208 allocators are almost always faster than allocators that go through 209 `IAllocator`. An important rule of thumb is: "assemble allocator first, adapt 210 to `IAllocator` after". A good allocator implements intricate logic by means of 211 template assembly, and gets wrapped with `IAllocator` (usually by means of 212 $(LREF allocatorObject)) only once, at client level. 213 214 Copyright: Andrei Alexandrescu 2013-. 215 216 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0). 217 218 Authors: $(HTTP erdani.com, Andrei Alexandrescu) 219 220 Source: $(PHOBOSSRC std/experimental/allocator) 221 222 */ 223 224 module std.experimental.allocator; 225 226 public import std.experimental.allocator.common, 227 std.experimental.allocator.typed; 228 229 // Fix https://issues.dlang.org/show_bug.cgi?id=17806 230 // this should always be the first unittest in this module in order to ensure 231 // that we use the `processAllocator` setter before the getter 232 @system unittest 233 { 234 import std.experimental.allocator.mallocator : Mallocator; 235 import std.experimental.allocator.gc_allocator : GCAllocator; 236 auto newAlloc = sharedAllocatorObject(Mallocator.instance); 237 processAllocator = newAlloc; 238 assert(processAllocator is newAlloc); 239 processAllocator = sharedAllocatorObject(GCAllocator.instance); 240 } 241 242 // Example in the synopsis above 243 @system unittest 244 { 245 import std.algorithm.comparison : min, max; 246 import std.experimental.allocator.building_blocks.allocator_list 247 : AllocatorList; 248 import std.experimental.allocator.building_blocks.bitmapped_block 249 : BitmappedBlock; 250 import std.experimental.allocator.building_blocks.bucketizer : Bucketizer; 251 import std.experimental.allocator.building_blocks.free_list : FreeList; 252 import std.experimental.allocator.building_blocks.segregator : Segregator; 253 import std.experimental.allocator.gc_allocator : GCAllocator; 254 255 alias FList = FreeList!(GCAllocator, 0, unbounded); 256 alias A = Segregator!( 257 8, FreeList!(GCAllocator, 0, 8), 258 128, Bucketizer!(FList, 1, 128, 16), 259 256, Bucketizer!(FList, 129, 256, 32), 260 512, Bucketizer!(FList, 257, 512, 64), 261 1024, Bucketizer!(FList, 513, 1024, 128), 262 2048, Bucketizer!(FList, 1025, 2048, 256), 263 3584, Bucketizer!(FList, 2049, 3584, 512), 264 4072 * 1024, AllocatorList!( 265 (n) => BitmappedBlock!(4096)( 266 cast(ubyte[])(GCAllocator.instance.allocate( 267 max(n, 4072 * 1024))))), 268 GCAllocator 269 ); 270 A tuMalloc; 271 auto b = tuMalloc.allocate(500); 272 assert(b.length == 500); 273 auto c = tuMalloc.allocate(113); 274 assert(c.length == 113); 275 assert(tuMalloc.expand(c, 14)); 276 tuMalloc.deallocate(b); 277 tuMalloc.deallocate(c); 278 } 279 280 import std.range.primitives; 281 import std.traits; 282 import std.typecons; 283 284 /** 285 Dynamic allocator interface. Code that defines allocators ultimately implements 286 this interface. This should be used wherever a uniform type is required for 287 encapsulating various allocator implementations. 288 289 Composition of allocators is not recommended at this level due to 290 inflexibility of dynamic interfaces and inefficiencies caused by cascaded 291 multiple calls. Instead, compose allocators using the static interface defined 292 in $(MREF std,experimental,allocator,building_blocks), 293 then adapt the composed 294 allocator to `IAllocator` (possibly by using $(LREF CAllocatorImpl) below). 295 296 Methods returning `Ternary` return `Ternary.yes` upon success, 297 `Ternary.no` upon failure, and `Ternary.unknown` if the primitive is not 298 implemented by the allocator instance. 299 */ 300 interface IAllocator 301 { 302 nothrow: 303 /** 304 Returns the alignment offered. 305 */ 306 @property uint alignment(); 307 308 /** 309 Returns the good allocation size that guarantees zero internal 310 fragmentation. 311 */ 312 size_t goodAllocSize(size_t s); 313 314 /** 315 Allocates `n` bytes of memory. 316 */ 317 void[] allocate(size_t, TypeInfo ti = null); 318 319 /** 320 Allocates `n` bytes of memory with specified alignment `a`. Implementations 321 that do not support this primitive should always return `null`. 322 */ 323 void[] alignedAllocate(size_t n, uint a); 324 325 /** 326 Allocates and returns all memory available to this allocator. 327 Implementations that do not support this primitive should always return 328 `null`. 329 */ 330 void[] allocateAll(); 331 332 /** 333 Expands a memory block in place and returns `true` if successful. 334 Implementations that don't support this primitive should always return 335 `false`. 336 */ 337 bool expand(ref void[], size_t); 338 339 /// Reallocates a memory block. 340 bool reallocate(ref void[], size_t); 341 342 /// Reallocates a memory block with specified alignment. 343 bool alignedReallocate(ref void[] b, size_t size, uint alignment); 344 345 /** 346 Returns `Ternary.yes` if the allocator owns `b`, `Ternary.no` if 347 the allocator doesn't own `b`, and `Ternary.unknown` if ownership 348 cannot be determined. Implementations that don't support this primitive 349 should always return `Ternary.unknown`. 350 */ 351 Ternary owns(void[] b); 352 353 /** 354 Resolves an internal pointer to the full block allocated. Implementations 355 that don't support this primitive should always return `Ternary.unknown`. 356 */ 357 Ternary resolveInternalPointer(const void* p, ref void[] result); 358 359 /** 360 Deallocates a memory block. Implementations that don't support this 361 primitive should always return `false`. A simple way to check that an 362 allocator supports deallocation is to call `deallocate(null)`. 363 */ 364 bool deallocate(void[] b); 365 366 /** 367 Deallocates all memory. Implementations that don't support this primitive 368 should always return `false`. 369 */ 370 bool deallocateAll(); 371 372 /** 373 Returns `Ternary.yes` if no memory is currently allocated from this 374 allocator, `Ternary.no` if some allocations are currently active, or 375 `Ternary.unknown` if not supported. 376 */ 377 Ternary empty(); 378 379 /** 380 Increases the reference count of the concrete class that implements this 381 interface. 382 383 For stateless allocators, this does nothing. 384 */ 385 @safe @nogc pure 386 void incRef(); 387 388 /** 389 Decreases the reference count of the concrete class that implements this 390 interface. 391 When the reference count is `0`, the object self-destructs. 392 393 Returns: `true` if the reference count is greater than `0` and `false` when 394 it hits `0`. For stateless allocators, it always returns `true`. 395 */ 396 @safe @nogc pure 397 bool decRef(); 398 } 399 400 /** 401 A reference counted struct that wraps the dynamic allocator interface. 402 This should be used wherever a uniform type is required for encapsulating 403 various allocator implementations. 404 405 Code that defines allocators ultimately implements the $(LREF IAllocator) 406 interface, possibly by using $(LREF CAllocatorImpl) below, and then build a 407 `RCIAllocator` out of this. 408 409 Composition of allocators is not recommended at this level due to 410 inflexibility of dynamic interfaces and inefficiencies caused by cascaded 411 multiple calls. Instead, compose allocators using the static interface defined 412 in $(A std_experimental_allocator_building_blocks.html, 413 `std.experimental.allocator.building_blocks`), then adapt the composed 414 allocator to `RCIAllocator` (possibly by using $(LREF allocatorObject) below). 415 */ 416 struct RCIAllocator 417 { 418 private IAllocator _alloc; 419 420 nothrow: 421 private @nogc pure @safe 422 this(this _)(IAllocator alloc) 423 { 424 assert(alloc); 425 _alloc = alloc; 426 } 427 428 @nogc pure @safe 429 this(this) 430 { 431 if (_alloc !is null) 432 { 433 _alloc.incRef(); 434 } 435 } 436 437 @nogc pure @safe 438 ~this() 439 { 440 if (_alloc !is null) 441 { 442 bool isLast = !_alloc.decRef(); 443 if (isLast) _alloc = null; 444 } 445 } 446 447 @nogc pure @safe 448 auto ref opAssign()(typeof(this) rhs) 449 { 450 if (_alloc is rhs._alloc) 451 { 452 return this; 453 } 454 // incRef was allready called by rhs posblit, so we're just moving 455 // calling dtor is the equivalent of decRef 456 __dtor(); 457 _alloc = rhs._alloc; 458 // move 459 rhs._alloc = null; 460 return this; 461 } 462 463 @nogc pure @safe 464 bool isNull(this _)() 465 { 466 return _alloc is null; 467 } 468 469 @property uint alignment() 470 { 471 assert(_alloc); 472 return _alloc.alignment(); 473 } 474 475 size_t goodAllocSize(size_t s) 476 { 477 assert(_alloc); 478 return _alloc.goodAllocSize(s); 479 } 480 481 void[] allocate(size_t n, TypeInfo ti = null) 482 { 483 assert(_alloc); 484 return _alloc.allocate(n, ti); 485 } 486 487 void[] alignedAllocate(size_t n, uint a) 488 { 489 assert(_alloc); 490 return _alloc.alignedAllocate(n, a); 491 } 492 493 void[] allocateAll() 494 { 495 assert(_alloc); 496 return _alloc.allocateAll(); 497 } 498 499 bool expand(ref void[] b, size_t size) 500 { 501 assert(_alloc); 502 return _alloc.expand(b, size); 503 } 504 505 bool reallocate(ref void[] b, size_t size) 506 { 507 assert(_alloc); 508 return _alloc.reallocate(b, size); 509 } 510 511 bool alignedReallocate(ref void[] b, size_t size, uint alignment) 512 { 513 assert(_alloc); 514 return _alloc.alignedReallocate(b, size, alignment); 515 } 516 517 Ternary owns(void[] b) 518 { 519 assert(_alloc); 520 return _alloc.owns(b); 521 } 522 523 Ternary resolveInternalPointer(const void* p, ref void[] result) 524 { 525 assert(_alloc); 526 return _alloc.resolveInternalPointer(p, result); 527 } 528 529 bool deallocate(void[] b) 530 { 531 assert(_alloc); 532 return _alloc.deallocate(b); 533 } 534 535 bool deallocateAll() 536 { 537 assert(_alloc); 538 return _alloc.deallocateAll(); 539 } 540 541 Ternary empty() 542 { 543 assert(_alloc); 544 return _alloc.empty(); 545 } 546 } 547 548 @system unittest 549 { 550 import std.experimental.allocator.building_blocks.region : Region; 551 import std.conv : emplace; 552 553 auto reg = Region!()(new ubyte[1024]); 554 auto state = reg.allocate(stateSize!(CAllocatorImpl!(Region!(), Yes.indirect))); 555 auto regObj = emplace!(CAllocatorImpl!(Region!(), Yes.indirect))(state, ®); 556 557 auto rcalloc = RCIAllocator(regObj); 558 auto b = rcalloc.allocate(10); 559 assert(b.length == 10); 560 561 // The reference counting is zero based 562 assert((cast(CAllocatorImpl!(Region!(), Yes.indirect))(rcalloc._alloc)).rc == 1); 563 { 564 auto rca2 = rcalloc; 565 assert((cast(CAllocatorImpl!(Region!(), Yes.indirect))(rcalloc._alloc)).rc == 2); 566 } 567 assert((cast(CAllocatorImpl!(Region!(), Yes.indirect))(rcalloc._alloc)).rc == 1); 568 } 569 570 @system unittest 571 { 572 import std.conv; 573 import std.experimental.allocator.mallocator; 574 import std.experimental.allocator.building_blocks.stats_collector; 575 576 alias SCAlloc = StatsCollector!(Mallocator, Options.bytesUsed); 577 SCAlloc statsCollectorAlloc; 578 579 ulong bytesUsed = statsCollectorAlloc.bytesUsed; 580 assert(bytesUsed == 0); 581 582 { 583 auto _allocator = allocatorObject(&statsCollectorAlloc); 584 bytesUsed = statsCollectorAlloc.bytesUsed; 585 assert(bytesUsed == stateSize!(CAllocatorImpl!(SCAlloc, Yes.indirect))); 586 } 587 588 bytesUsed = statsCollectorAlloc.bytesUsed; 589 assert(bytesUsed == 0, "RCIAllocator leaks memory; leaked " 590 ~ to!string(bytesUsed) ~ " bytes"); 591 } 592 593 @system unittest 594 { 595 import std.conv; 596 import std.experimental.allocator.mallocator; 597 import std.experimental.allocator.building_blocks.stats_collector; 598 599 alias SCAlloc = StatsCollector!(Mallocator, Options.bytesUsed); 600 SCAlloc statsCollectorAlloc; 601 602 ulong bytesUsed = statsCollectorAlloc.bytesUsed; 603 assert(bytesUsed == 0); 604 605 { 606 auto _allocator = allocatorObject(statsCollectorAlloc); 607 608 // Ensure that the allocator was passed through in CAllocatorImpl 609 // This allocator was used to allocate the chunk that holds the 610 // CAllocatorImpl object; which is it's own wrapper 611 bytesUsed = (cast(CAllocatorImpl!(SCAlloc))(_allocator._alloc)).impl.bytesUsed; 612 assert(bytesUsed == stateSize!(CAllocatorImpl!(SCAlloc)), 613 "RCIAllocator leaks memory; leaked " ~ to!string(bytesUsed) ~ " bytes"); 614 _allocator.allocate(1); 615 bytesUsed = (cast(CAllocatorImpl!(SCAlloc))(_allocator._alloc)).impl.bytesUsed; 616 assert(bytesUsed == stateSize!(CAllocatorImpl!(SCAlloc)) + 1, 617 "RCIAllocator leaks memory; leaked " ~ to!string(bytesUsed) ~ " bytes"); 618 } 619 620 bytesUsed = statsCollectorAlloc.bytesUsed; 621 assert(bytesUsed == stateSize!(CAllocatorImpl!(SCAlloc)), 622 "RCIAllocator leaks memory; leaked " 623 ~ to!string(bytesUsed) ~ " bytes"); 624 } 625 626 /** 627 Dynamic shared allocator interface. Code that defines allocators shareable 628 across threads ultimately implements this interface. This should be used 629 wherever a uniform type is required for encapsulating various allocator 630 implementations. 631 632 Composition of allocators is not recommended at this level due to 633 inflexibility of dynamic interfaces and inefficiencies caused by cascaded 634 multiple calls. Instead, compose allocators using the static interface defined 635 in $(MREF std,experimental,allocator,building_blocks), 636 then adapt the composed 637 allocator to `ISharedAllocator` (possibly by using $(LREF CSharedAllocatorImpl) below). 638 639 Methods returning `Ternary` return `Ternary.yes` upon success, 640 `Ternary.no` upon failure, and `Ternary.unknown` if the primitive is not 641 implemented by the allocator instance. 642 */ 643 interface ISharedAllocator 644 { 645 nothrow: 646 /** 647 Returns the alignment offered. 648 */ 649 @property uint alignment() shared; 650 651 /** 652 Returns the good allocation size that guarantees zero internal 653 fragmentation. 654 */ 655 size_t goodAllocSize(size_t s) shared; 656 657 /** 658 Allocates `n` bytes of memory. 659 */ 660 void[] allocate(size_t, TypeInfo ti = null) shared; 661 662 /** 663 Allocates `n` bytes of memory with specified alignment `a`. Implementations 664 that do not support this primitive should always return `null`. 665 */ 666 void[] alignedAllocate(size_t n, uint a) shared; 667 668 /** 669 Allocates and returns all memory available to this allocator. 670 Implementations that do not support this primitive should always return 671 `null`. 672 */ 673 void[] allocateAll() shared; 674 675 /** 676 Expands a memory block in place and returns `true` if successful. 677 Implementations that don't support this primitive should always return 678 `false`. 679 */ 680 bool expand(ref void[], size_t) shared; 681 682 /// Reallocates a memory block. 683 bool reallocate(ref void[], size_t) shared; 684 685 /// Reallocates a memory block with specified alignment. 686 bool alignedReallocate(ref void[] b, size_t size, uint alignment) shared; 687 688 /** 689 Returns `Ternary.yes` if the allocator owns `b`, `Ternary.no` if 690 the allocator doesn't own `b`, and `Ternary.unknown` if ownership 691 cannot be determined. Implementations that don't support this primitive 692 should always return `Ternary.unknown`. 693 */ 694 Ternary owns(void[] b) shared; 695 696 /** 697 Resolves an internal pointer to the full block allocated. Implementations 698 that don't support this primitive should always return `Ternary.unknown`. 699 */ 700 Ternary resolveInternalPointer(const void* p, ref void[] result) shared; 701 702 /** 703 Deallocates a memory block. Implementations that don't support this 704 primitive should always return `false`. A simple way to check that an 705 allocator supports deallocation is to call `deallocate(null)`. 706 */ 707 bool deallocate(void[] b) shared; 708 709 /** 710 Deallocates all memory. Implementations that don't support this primitive 711 should always return `false`. 712 */ 713 bool deallocateAll() shared; 714 715 /** 716 Returns `Ternary.yes` if no memory is currently allocated from this 717 allocator, `Ternary.no` if some allocations are currently active, or 718 `Ternary.unknown` if not supported. 719 */ 720 Ternary empty() shared; 721 722 /** 723 Increases the reference count of the concrete class that implements this 724 interface. 725 726 For stateless allocators, this does nothing. 727 */ 728 @safe @nogc pure 729 void incRef() shared; 730 731 /** 732 Decreases the reference count of the concrete class that implements this 733 interface. 734 When the reference count is `0`, the object self-destructs. 735 736 For stateless allocators, this does nothing. 737 738 Returns: `true` if the reference count is greater than `0` and `false` when 739 it hits `0`. For stateless allocators, it always returns `true`. 740 */ 741 @safe @nogc pure 742 bool decRef() shared; 743 } 744 745 /** 746 A reference counted struct that wraps the dynamic shared allocator interface. 747 This should be used wherever a uniform type is required for encapsulating 748 various allocator implementations. 749 750 Code that defines allocators shareable across threads ultimately implements the 751 $(LREF ISharedAllocator) interface, possibly by using 752 $(LREF CSharedAllocatorImpl) below, and then build a `RCISharedAllocator` out 753 of this. 754 755 Composition of allocators is not recommended at this level due to 756 inflexibility of dynamic interfaces and inefficiencies caused by cascaded 757 multiple calls. Instead, compose allocators using the static interface defined 758 in $(A std_experimental_allocator_building_blocks.html, 759 `std.experimental.allocator.building_blocks`), then adapt the composed allocator 760 to `RCISharedAllocator` (possibly by using $(LREF sharedAllocatorObject) below). 761 */ 762 shared struct RCISharedAllocator 763 { 764 private ISharedAllocator _alloc; 765 766 nothrow: 767 private @nogc pure @safe 768 this(shared ISharedAllocator alloc) 769 { 770 assert(alloc); 771 _alloc = alloc; 772 } 773 774 @nogc pure @safe 775 this(this) 776 { 777 if (_alloc !is null) 778 { 779 _alloc.incRef(); 780 } 781 } 782 783 @nogc pure @safe 784 ~this() 785 { 786 if (_alloc !is null) 787 { 788 bool isLast = !_alloc.decRef(); 789 if (isLast) _alloc = null; 790 } 791 } 792 793 @nogc pure @safe 794 auto ref opAssign()(RCISharedAllocator rhs) 795 { 796 if (_alloc is rhs._alloc) 797 { 798 return this; 799 } 800 // incRef was allready called by rhs posblit, so we're just moving 801 if (_alloc !is null) 802 { 803 _alloc.decRef(); 804 } 805 _alloc = rhs._alloc; 806 // move 807 rhs._alloc = null; 808 return this; 809 } 810 811 @nogc pure @safe 812 bool isNull(this _)() 813 { 814 return _alloc is null; 815 } 816 817 @property uint alignment() 818 { 819 assert(_alloc); 820 return _alloc.alignment(); 821 } 822 823 size_t goodAllocSize(size_t s) 824 { 825 assert(_alloc); 826 return _alloc.goodAllocSize(s); 827 } 828 829 void[] allocate(size_t n, TypeInfo ti = null) 830 { 831 assert(_alloc); 832 return _alloc.allocate(n, ti); 833 } 834 835 void[] alignedAllocate(size_t n, uint a) 836 { 837 assert(_alloc); 838 return _alloc.alignedAllocate(n, a); 839 } 840 841 void[] allocateAll() 842 { 843 assert(_alloc); 844 return _alloc.allocateAll(); 845 } 846 847 bool expand(ref void[] b, size_t size) 848 { 849 assert(_alloc); 850 return _alloc.expand(b, size); 851 } 852 853 bool reallocate(ref void[] b, size_t size) 854 { 855 assert(_alloc); 856 return _alloc.reallocate(b, size); 857 } 858 859 bool alignedReallocate(ref void[] b, size_t size, uint alignment) 860 { 861 assert(_alloc); 862 return _alloc.alignedReallocate(b, size, alignment); 863 } 864 865 Ternary owns(void[] b) 866 { 867 assert(_alloc); 868 return _alloc.owns(b); 869 } 870 871 Ternary resolveInternalPointer(const void* p, ref void[] result) 872 { 873 assert(_alloc); 874 return _alloc.resolveInternalPointer(p, result); 875 } 876 877 bool deallocate(void[] b) 878 { 879 assert(_alloc); 880 return _alloc.deallocate(b); 881 } 882 883 bool deallocateAll() 884 { 885 assert(_alloc); 886 return _alloc.deallocateAll(); 887 } 888 889 Ternary empty() 890 { 891 assert(_alloc); 892 return _alloc.empty(); 893 } 894 } 895 896 private RCISharedAllocator _processAllocator; 897 private RCIAllocator _threadAllocator; 898 899 @nogc nothrow @safe 900 private ref RCIAllocator setupThreadAllocator() 901 { 902 /* 903 Forwards the `_threadAllocator` calls to the `processAllocator` 904 */ 905 static class ThreadAllocator : IAllocator 906 { 907 nothrow: 908 private RCISharedAllocator _allocator; 909 910 @nogc @safe 911 this(ref RCISharedAllocator procAlloc) 912 { 913 _allocator = procAlloc; 914 } 915 916 override @property uint alignment() 917 { 918 return _allocator.alignment(); 919 } 920 921 override size_t goodAllocSize(size_t s) 922 { 923 return _allocator.goodAllocSize(s); 924 } 925 926 override void[] allocate(size_t n, TypeInfo ti = null) 927 { 928 return _allocator.allocate(n, ti); 929 } 930 931 override void[] alignedAllocate(size_t n, uint a) 932 { 933 return _allocator.alignedAllocate(n, a); 934 } 935 936 override void[] allocateAll() 937 { 938 return _allocator.allocateAll(); 939 } 940 941 override bool expand(ref void[] b, size_t size) 942 { 943 return _allocator.expand(b, size); 944 } 945 946 override bool reallocate(ref void[] b, size_t size) 947 { 948 return _allocator.reallocate(b, size); 949 } 950 951 override bool alignedReallocate(ref void[] b, size_t size, uint alignment) 952 { 953 return _allocator.alignedReallocate(b, size, alignment); 954 } 955 956 override Ternary owns(void[] b) 957 { 958 return _allocator.owns(b); 959 } 960 961 override Ternary resolveInternalPointer(const void* p, ref void[] result) 962 { 963 return _allocator.resolveInternalPointer(p, result); 964 } 965 966 override bool deallocate(void[] b) 967 { 968 return _allocator.deallocate(b); 969 } 970 971 override bool deallocateAll() 972 { 973 return _allocator.deallocateAll(); 974 } 975 976 override Ternary empty() 977 { 978 return _allocator.empty(); 979 } 980 981 @nogc pure @safe 982 override void incRef() 983 { 984 _allocator._alloc.incRef(); 985 } 986 987 @nogc pure @safe 988 override bool decRef() 989 { 990 return _allocator._alloc.decRef(); 991 } 992 } 993 994 assert(_threadAllocator.isNull); 995 import std.conv : emplace; 996 static ulong[stateSize!(ThreadAllocator).divideRoundUp(ulong.sizeof)] _threadAllocatorState; 997 () @trusted { 998 _threadAllocator = RCIAllocator(emplace!(ThreadAllocator)(_threadAllocatorState[], processAllocator())); 999 }(); 1000 return _threadAllocator; 1001 } 1002 1003 // Fix threadAllocator bug: the threadAllocator should hold an internal reference 1004 // to the processAllocator that it's using 1005 @system unittest 1006 { 1007 import std.experimental.allocator.mallocator : Mallocator; 1008 1009 auto a = sharedAllocatorObject(Mallocator.instance); 1010 auto buf = theAllocator.allocate(42); 1011 processAllocator = a; 1012 theAllocator.deallocate(buf); 1013 } 1014 1015 /** 1016 Gets/sets the allocator for the current thread. This is the default allocator 1017 that should be used for allocating thread-local memory. For allocating memory 1018 to be shared across threads, use `processAllocator` (below). By default, 1019 `theAllocator` ultimately fetches memory from `processAllocator`, which 1020 in turn uses the garbage collected heap. 1021 */ 1022 @nogc nothrow @safe 1023 @property ref RCIAllocator theAllocator() 1024 { 1025 alias p = _threadAllocator; 1026 return !p.isNull() ? p : setupThreadAllocator(); 1027 } 1028 1029 /// Ditto 1030 nothrow @system @nogc 1031 @property void theAllocator(RCIAllocator a) 1032 { 1033 assert(!a.isNull); 1034 _threadAllocator = a; 1035 } 1036 1037 /// 1038 @system unittest 1039 { 1040 // Install a new allocator that is faster for 128-byte allocations. 1041 import std.experimental.allocator.building_blocks.free_list : FreeList; 1042 import std.experimental.allocator.gc_allocator : GCAllocator; 1043 auto oldAllocator = theAllocator; 1044 scope(exit) theAllocator = oldAllocator; 1045 theAllocator = allocatorObject(FreeList!(GCAllocator, 128)()); 1046 // Use the now changed allocator to allocate an array 1047 const ubyte[] arr = theAllocator.makeArray!ubyte(128); 1048 assert(arr.ptr); 1049 //... 1050 } 1051 1052 /** 1053 Gets/sets the allocator for the current process. This allocator must be used 1054 for allocating memory shared across threads. Objects created using this 1055 allocator can be cast to `shared`. 1056 */ 1057 @nogc nothrow @trusted 1058 @property ref RCISharedAllocator processAllocator() 1059 { 1060 import std.experimental.allocator.gc_allocator : GCAllocator; 1061 import std.concurrency : initOnce; 1062 1063 static RCISharedAllocator* forceAttributes() 1064 { 1065 return &initOnce!_processAllocator( 1066 sharedAllocatorObject(GCAllocator.instance)); 1067 } 1068 1069 return *(cast(RCISharedAllocator* function() @nogc nothrow)(&forceAttributes))(); 1070 } 1071 1072 /// Ditto 1073 @nogc nothrow @system 1074 @property void processAllocator(ref RCISharedAllocator a) 1075 { 1076 assert(!a.isNull); 1077 processAllocator() = a; 1078 } 1079 1080 @system unittest 1081 { 1082 import core.exception : AssertError; 1083 import std.exception : assertThrown; 1084 import std.experimental.allocator.building_blocks.free_list : SharedFreeList; 1085 import std.experimental.allocator.mallocator : Mallocator; 1086 1087 assert(!processAllocator.isNull); 1088 assert(!theAllocator.isNull); 1089 1090 testAllocatorObject(processAllocator); 1091 testAllocatorObject(theAllocator); 1092 1093 shared SharedFreeList!(Mallocator, chooseAtRuntime, chooseAtRuntime) sharedFL; 1094 RCISharedAllocator sharedFLObj = sharedAllocatorObject(sharedFL); 1095 alias SharedAllocT = CSharedAllocatorImpl!( 1096 shared SharedFreeList!( 1097 Mallocator, chooseAtRuntime, chooseAtRuntime)); 1098 1099 assert((cast(SharedAllocT)(sharedFLObj._alloc)).rc == 1); 1100 assert(!sharedFLObj.isNull); 1101 testAllocatorObject(sharedFLObj); 1102 1103 // Test processAllocator setter 1104 RCISharedAllocator oldProcessAllocator = processAllocator; 1105 processAllocator = sharedFLObj; 1106 assert((cast(SharedAllocT)(sharedFLObj._alloc)).rc == 2); 1107 assert(processAllocator._alloc is sharedFLObj._alloc); 1108 1109 testAllocatorObject(processAllocator); 1110 testAllocatorObject(theAllocator); 1111 assertThrown!AssertError(processAllocator = RCISharedAllocator(null)); 1112 1113 // Restore initial processAllocator state 1114 processAllocator = oldProcessAllocator; 1115 assert((cast(SharedAllocT)(sharedFLObj._alloc)).rc == 1); 1116 assert(processAllocator is oldProcessAllocator); 1117 1118 RCISharedAllocator indirectShFLObj = sharedAllocatorObject(&sharedFL); 1119 testAllocatorObject(indirectShFLObj); 1120 alias IndirectSharedAllocT = CSharedAllocatorImpl!( 1121 shared SharedFreeList!( 1122 Mallocator, chooseAtRuntime, chooseAtRuntime) 1123 , Yes.indirect); 1124 1125 assert((cast(IndirectSharedAllocT)(indirectShFLObj._alloc)).rc == 1); 1126 1127 RCIAllocator indirectMallocator = allocatorObject(&Mallocator.instance); 1128 testAllocatorObject(indirectMallocator); 1129 } 1130 1131 /** 1132 Dynamically allocates (using `alloc`) and then creates in the memory 1133 allocated an object of type `T`, using `args` (if any) for its 1134 initialization. Initialization occurs in the memory allocated and is otherwise 1135 semantically the same as `T(args)`. 1136 (Note that using `alloc.make!(T[])` creates a pointer to an (empty) array 1137 of `T`s, not an array. To use an allocator to allocate and initialize an 1138 array, use `alloc.makeArray!T` described below.) 1139 1140 Params: 1141 T = Type of the object being created. 1142 alloc = The allocator used for getting the needed memory. It may be an object 1143 implementing the static interface for allocators, or an `IAllocator` 1144 reference. 1145 args = Optional arguments used for initializing the created object. If not 1146 present, the object is default constructed. 1147 1148 Returns: If `T` is a class type, returns a reference to the created `T` 1149 object. Otherwise, returns a `T*` pointing to the created object. In all 1150 cases, returns `null` if allocation failed. 1151 1152 Throws: If `T`'s constructor throws, deallocates the allocated memory and 1153 propagates the exception. 1154 */ 1155 auto make(T, Allocator, A...)(auto ref Allocator alloc, auto ref A args) 1156 { 1157 import std.algorithm.comparison : max; 1158 static if (!is(T == class) && !is(T == interface) && A.length == 0 1159 && __traits(compiles, {T t;}) && __traits(isZeroInit, T) 1160 && is(typeof(alloc.allocateZeroed(size_t.max)))) 1161 { 1162 auto m = alloc.allocateZeroed(max(T.sizeof, 1)); 1163 return (() @trusted => cast(T*) m.ptr)(); 1164 } 1165 else 1166 { 1167 import std.conv : emplace, emplaceRef; 1168 auto m = alloc.allocate(max(stateSize!T, 1)); 1169 if (!m.ptr) return null; 1170 1171 // make can only be @safe if emplace or emplaceRef is `pure` 1172 auto construct() 1173 { 1174 static if (is(T == class)) return emplace!T(m, args); 1175 else 1176 { 1177 // Assume cast is safe as allocation succeeded for `stateSize!T` 1178 auto p = () @trusted { return cast(T*) m.ptr; }(); 1179 emplaceRef!T(*p, args); 1180 return p; 1181 } 1182 } 1183 1184 scope(failure) 1185 { 1186 static if (is(typeof(() pure { return construct(); }))) 1187 { 1188 // Assume deallocation is safe because: 1189 // 1) in case of failure, `m` is the only reference to this memory 1190 // 2) `m` is known to originate from `alloc` 1191 () @trusted { alloc.deallocate(m); }(); 1192 } 1193 else 1194 { 1195 alloc.deallocate(m); 1196 } 1197 } 1198 1199 return construct(); 1200 } 1201 } 1202 1203 /// 1204 @system unittest 1205 { 1206 // Dynamically allocate one integer 1207 const int* p1 = theAllocator.make!int; 1208 // It's implicitly initialized with its .init value 1209 assert(*p1 == 0); 1210 // Dynamically allocate one double, initialize to 42.5 1211 const double* p2 = theAllocator.make!double(42.5); 1212 assert(*p2 == 42.5); 1213 1214 // Dynamically allocate a struct 1215 static struct Point 1216 { 1217 int x, y, z; 1218 } 1219 // Use the generated constructor taking field values in order 1220 const Point* p = theAllocator.make!Point(1, 2); 1221 assert(p.x == 1 && p.y == 2 && p.z == 0); 1222 1223 // Dynamically allocate a class object 1224 static class Customer 1225 { 1226 uint id = uint.max; 1227 this() {} 1228 this(uint id) { this.id = id; } 1229 // ... 1230 } 1231 Customer cust = theAllocator.make!Customer; 1232 assert(cust.id == uint.max); // default initialized 1233 cust = theAllocator.make!Customer(42); 1234 assert(cust.id == 42); 1235 1236 // explicit passing of outer pointer 1237 static class Outer 1238 { 1239 int x = 3; 1240 class Inner 1241 { 1242 auto getX() { return x; } 1243 } 1244 } 1245 auto outer = theAllocator.make!Outer(); 1246 auto inner = theAllocator.make!(Outer.Inner)(outer); 1247 assert(outer.x == inner.getX); 1248 } 1249 1250 // https://issues.dlang.org/show_bug.cgi?id=15639 1251 // https://issues.dlang.org/show_bug.cgi?id=15772 1252 @system unittest 1253 { 1254 abstract class Foo {} 1255 class Bar: Foo {} 1256 static assert(!is(typeof(theAllocator.make!Foo))); 1257 static assert( is(typeof(theAllocator.make!Bar))); 1258 } 1259 1260 @system unittest 1261 { 1262 void test(Allocator)(auto ref Allocator alloc) 1263 { 1264 const int* a = alloc.make!int(10); 1265 assert(*a == 10); 1266 1267 struct A 1268 { 1269 int x; 1270 string y; 1271 double z; 1272 } 1273 1274 A* b = alloc.make!A(42); 1275 assert(b.x == 42); 1276 assert(b.y is null); 1277 import std.math : isNaN; 1278 assert(b.z.isNaN); 1279 1280 b = alloc.make!A(43, "44", 45); 1281 assert(b.x == 43); 1282 assert(b.y == "44"); 1283 assert(b.z == 45); 1284 1285 static class B 1286 { 1287 int x; 1288 string y; 1289 double z; 1290 this(int _x, string _y = null, double _z = double.init) 1291 { 1292 x = _x; 1293 y = _y; 1294 z = _z; 1295 } 1296 } 1297 1298 B c = alloc.make!B(42); 1299 assert(c.x == 42); 1300 assert(c.y is null); 1301 assert(c.z.isNaN); 1302 1303 c = alloc.make!B(43, "44", 45); 1304 assert(c.x == 43); 1305 assert(c.y == "44"); 1306 assert(c.z == 45); 1307 1308 const parray = alloc.make!(int[]); 1309 assert((*parray).empty); 1310 } 1311 1312 import std.experimental.allocator.gc_allocator : GCAllocator; 1313 test(GCAllocator.instance); 1314 test(theAllocator); 1315 } 1316 1317 // Attribute propagation 1318 nothrow @safe @nogc unittest 1319 { 1320 import std.experimental.allocator.mallocator : Mallocator; 1321 alias alloc = Mallocator.instance; 1322 1323 void test(T, Args...)(auto ref Args args) 1324 { 1325 auto k = alloc.make!T(args); 1326 () @trusted { alloc.dispose(k); }(); 1327 } 1328 1329 test!int; 1330 test!(int*); 1331 test!int(0); 1332 test!(int*)(null); 1333 } 1334 1335 // should be pure with the GCAllocator 1336 /*pure nothrow*/ @safe unittest 1337 { 1338 import std.experimental.allocator.gc_allocator : GCAllocator; 1339 1340 alias alloc = GCAllocator.instance; 1341 1342 void test(T, Args...)(auto ref Args args) 1343 { 1344 auto k = alloc.make!T(args); 1345 (a) @trusted { a.dispose(k); }(alloc); 1346 } 1347 1348 test!int(); 1349 test!(int*); 1350 test!int(0); 1351 test!(int*)(null); 1352 } 1353 1354 // Verify that making an object by calling an impure constructor is not @safe 1355 nothrow @safe @nogc unittest 1356 { 1357 import std.experimental.allocator.mallocator : Mallocator; 1358 static struct Pure { this(int) pure nothrow @nogc @safe {} } 1359 1360 cast(void) Mallocator.instance.make!Pure(0); 1361 1362 static int g = 0; 1363 static struct Impure { this(int) nothrow @nogc @safe { 1364 g++; 1365 } } 1366 static assert(!__traits(compiles, cast(void) Mallocator.instance.make!Impure(0))); 1367 } 1368 1369 // test failure with a pure, failing struct 1370 @safe unittest 1371 { 1372 import std.exception : assertThrown, enforce; 1373 1374 // this struct can't be initialized 1375 struct InvalidStruct 1376 { 1377 this(int b) 1378 { 1379 enforce(1 == 2); 1380 } 1381 } 1382 import std.experimental.allocator.mallocator : Mallocator; 1383 assertThrown(make!InvalidStruct(Mallocator.instance, 42)); 1384 } 1385 1386 // test failure with an impure, failing struct 1387 @system unittest 1388 { 1389 import std.exception : assertThrown, enforce; 1390 static int g; 1391 struct InvalidImpureStruct 1392 { 1393 this(int b) 1394 { 1395 g++; 1396 enforce(1 == 2); 1397 } 1398 } 1399 import std.experimental.allocator.mallocator : Mallocator; 1400 assertThrown(make!InvalidImpureStruct(Mallocator.instance, 42)); 1401 } 1402 1403 // Don't allow zero-ctor-args `make` for structs with `@disable this();` 1404 @system unittest 1405 { 1406 struct NoDefaultCtor 1407 { 1408 int i; 1409 @disable this(); 1410 } 1411 import std.experimental.allocator.mallocator : Mallocator; 1412 static assert(!__traits(compiles, make!NoDefaultCtor(Mallocator.instance)), 1413 "Don't allow zero-ctor-args `make` for structs with `@disable this();`"); 1414 } 1415 1416 // https://issues.dlang.org/show_bug.cgi?id=18937 1417 @safe unittest 1418 { 1419 static struct S 1420 { 1421 ubyte[16 * 1024] data; 1422 } 1423 1424 static struct SomeAllocator 1425 { 1426 ubyte[] allocate(size_t) { return []; } 1427 void deallocate(void[]) {} 1428 } 1429 1430 auto x = SomeAllocator().make!S(); 1431 } 1432 1433 private void fillWithMemcpy(T)(scope void[] array, auto ref T filler) nothrow 1434 if (T.sizeof == 1) 1435 { 1436 import core.stdc..string : memset; 1437 import std.traits : CopyConstness; 1438 if (!array.length) return; 1439 memset(array.ptr, *cast(CopyConstness!(T*, ubyte*)) &filler, array.length); 1440 } 1441 1442 private void fillWithMemcpy(T)(scope void[] array, auto ref T filler) nothrow 1443 if (T.sizeof != 1) 1444 { 1445 import core.stdc..string : memcpy; 1446 import std.algorithm.comparison : min; 1447 if (!array.length) return; 1448 memcpy(array.ptr, &filler, T.sizeof); 1449 // Fill the array from the initialized portion of itself exponentially. 1450 for (size_t offset = T.sizeof; offset < array.length; ) 1451 { 1452 size_t extent = min(offset, array.length - offset); 1453 memcpy(array.ptr + offset, array.ptr, extent); 1454 offset += extent; 1455 } 1456 } 1457 1458 @system unittest 1459 { 1460 // Test T.sizeof == 1 path of fillWithMemcpy. 1461 ubyte[] a; 1462 fillWithMemcpy(a, ubyte(42)); 1463 assert(a.length == 0); 1464 a = [ 1, 2, 3, 4, 5 ]; 1465 fillWithMemcpy(a, ubyte(42)); 1466 assert(a == [ 42, 42, 42, 42, 42]); 1467 } 1468 1469 @system unittest 1470 { 1471 int[] a; 1472 fillWithMemcpy(a, 42); 1473 assert(a.length == 0); 1474 a = [ 1, 2, 3, 4, 5 ]; 1475 fillWithMemcpy(a, 42); 1476 assert(a == [ 42, 42, 42, 42, 42]); 1477 } 1478 1479 //Make shared object 1480 @system unittest 1481 { 1482 import core.atomic : atomicLoad; 1483 auto psi = theAllocator.make!(shared(int))(10); 1484 assert(10 == (*psi).atomicLoad()); 1485 } 1486 1487 private T[] uninitializedFillDefault(T)(T[] array) nothrow 1488 { 1489 static if (__traits(isZeroInit, T)) 1490 { 1491 import core.stdc..string : memset; 1492 if (array !is null) 1493 memset(array.ptr, 0, T.sizeof * array.length); 1494 return array; 1495 } 1496 else static if (is(immutable T == immutable char) || is(immutable T == immutable wchar)) 1497 { 1498 import core.stdc..string : memset; 1499 if (array !is null) 1500 memset(array.ptr, 0xff, T.sizeof * array.length); 1501 return array; 1502 } 1503 else 1504 { 1505 T t = T.init; 1506 fillWithMemcpy(array, t); 1507 return array; 1508 } 1509 } 1510 1511 pure nothrow @nogc 1512 @system unittest 1513 { 1514 static struct S { int x = 42; @disable this(this); } 1515 1516 int[5] expected = [42, 42, 42, 42, 42]; 1517 S[5] arr = void; 1518 uninitializedFillDefault(arr); 1519 assert((cast(int*) arr.ptr)[0 .. arr.length] == expected); 1520 } 1521 1522 @system unittest 1523 { 1524 int[] a = [1, 2, 4]; 1525 uninitializedFillDefault(a); 1526 assert(a == [0, 0, 0]); 1527 1528 char[] b = [1, 2, 4]; 1529 uninitializedFillDefault(b); 1530 assert(b == [0xff, 0xff, 0xff]); 1531 1532 wchar[] c = [1, 2, 4]; 1533 uninitializedFillDefault(c); 1534 assert(c == [0xffff, 0xffff, 0xffff]); 1535 } 1536 1537 @system unittest 1538 { 1539 static struct P { float x = 0; float y = 0; } 1540 1541 static assert(__traits(isZeroInit, P)); 1542 P[] a = [P(10, 11), P(20, 21), P(40, 41)]; 1543 uninitializedFillDefault(a); 1544 assert(a == [P.init, P.init, P.init]); 1545 } 1546 1547 /** 1548 Create an array of `T` with `length` elements using `alloc`. The array is either default-initialized, filled with copies of `init`, or initialized with values fetched from `range`. 1549 1550 Params: 1551 T = element type of the array being created 1552 alloc = the allocator used for getting memory 1553 length = length of the newly created array 1554 init = element used for filling the array 1555 range = range used for initializing the array elements 1556 1557 Returns: 1558 The newly-created array, or `null` if either `length` was `0` or 1559 allocation failed. 1560 1561 Throws: 1562 The first two overloads throw only if `alloc`'s primitives do. The 1563 overloads that involve copy initialization deallocate memory and propagate the 1564 exception if the copy operation throws. 1565 */ 1566 T[] makeArray(T, Allocator)(auto ref Allocator alloc, size_t length) 1567 { 1568 if (!length) return null; 1569 static if (T.sizeof <= 1) 1570 { 1571 const nAlloc = length * T.sizeof; 1572 } 1573 else 1574 { 1575 import core.checkedint : mulu; 1576 bool overflow; 1577 const nAlloc = mulu(length, T.sizeof, overflow); 1578 if (overflow) return null; 1579 } 1580 1581 static if (__traits(isZeroInit, T) && hasMember!(Allocator, "allocateZeroed")) 1582 { 1583 auto m = alloc.allocateZeroed(nAlloc); 1584 return (() @trusted => cast(T[]) m)(); 1585 } 1586 else 1587 { 1588 auto m = alloc.allocate(nAlloc); 1589 if (!m.ptr) return null; 1590 alias U = Unqual!T; 1591 return () @trusted { return cast(T[]) uninitializedFillDefault(cast(U[]) m); }(); 1592 } 1593 } 1594 1595 @system unittest 1596 { 1597 void test1(A)(auto ref A alloc) 1598 { 1599 int[] a = alloc.makeArray!int(0); 1600 assert(a.length == 0 && a.ptr is null); 1601 a = alloc.makeArray!int(5); 1602 assert(a.length == 5); 1603 static immutable cheatsheet = [0, 0, 0, 0, 0]; 1604 assert(a == cheatsheet); 1605 } 1606 1607 void test2(A)(auto ref A alloc) 1608 { 1609 static struct S { int x = 42; @disable this(this); } 1610 S[] arr = alloc.makeArray!S(5); 1611 assert(arr.length == 5); 1612 int[] arrInt = () @trusted { return (cast(int*) arr.ptr)[0 .. 5]; }(); 1613 static immutable res = [42, 42, 42, 42, 42]; 1614 assert(arrInt == res); 1615 } 1616 1617 import std.experimental.allocator.gc_allocator : GCAllocator; 1618 import std.experimental.allocator.mallocator : Mallocator; 1619 (alloc) /*pure nothrow*/ @safe { test1(alloc); test2(alloc);} (GCAllocator.instance); 1620 (alloc) nothrow @safe @nogc { test1(alloc); test2(alloc);} (Mallocator.instance); 1621 test2(theAllocator); 1622 } 1623 1624 @system unittest 1625 { 1626 import std.algorithm.comparison : equal; 1627 auto a = theAllocator.makeArray!(shared int)(5); 1628 static assert(is(typeof(a) == shared(int)[])); 1629 assert(a.length == 5); 1630 assert(a.equal([0, 0, 0, 0, 0])); 1631 1632 auto b = theAllocator.makeArray!(const int)(5); 1633 static assert(is(typeof(b) == const(int)[])); 1634 assert(b.length == 5); 1635 assert(b.equal([0, 0, 0, 0, 0])); 1636 1637 auto c = theAllocator.makeArray!(immutable int)(5); 1638 static assert(is(typeof(c) == immutable(int)[])); 1639 assert(c.length == 5); 1640 assert(c.equal([0, 0, 0, 0, 0])); 1641 } 1642 1643 // https://issues.dlang.org/show_bug.cgi?id=19085 - makeArray with void 1644 @system unittest 1645 { 1646 auto b = theAllocator.makeArray!void(5); 1647 scope(exit) theAllocator.dispose(b); 1648 auto c = cast(ubyte[]) b; 1649 assert(c.length == 5); 1650 assert(c == [0, 0, 0, 0, 0]); // default initialization 1651 } 1652 1653 private enum hasPurePostblit(T) = !hasElaborateCopyConstructor!T || 1654 is(typeof(() pure { T.init.__xpostblit(); })); 1655 1656 private enum hasPureDtor(T) = !hasElaborateDestructor!T || 1657 is(typeof(() pure { T.init.__xdtor(); })); 1658 1659 // `true` when postblit and destructor of T cannot escape references to itself 1660 private enum canSafelyDeallocPostRewind(T) = hasPurePostblit!T && hasPureDtor!T; 1661 1662 /// Ditto 1663 T[] makeArray(T, Allocator)(auto ref Allocator alloc, size_t length, T init) 1664 { 1665 if (!length) return null; 1666 auto m = alloc.allocate(T.sizeof * length); 1667 if (!m.ptr) return null; 1668 auto result = () @trusted { return cast(T[]) m; } (); 1669 import std.traits : hasElaborateCopyConstructor; 1670 static if (hasElaborateCopyConstructor!T) 1671 { 1672 scope(failure) 1673 { 1674 static if (canSafelyDeallocPostRewind!T) 1675 () @trusted { alloc.deallocate(m); } (); 1676 else 1677 alloc.deallocate(m); 1678 } 1679 1680 size_t i = 0; 1681 static if (hasElaborateDestructor!T) 1682 { 1683 scope (failure) 1684 { 1685 foreach (j; 0 .. i) 1686 { 1687 destroy(result[j]); 1688 } 1689 } 1690 } 1691 import std.conv : emplace; 1692 for (; i < length; ++i) 1693 { 1694 emplace!T(&result[i], init); 1695 } 1696 } 1697 else 1698 { 1699 alias U = Unqual!T; 1700 () @trusted { fillWithMemcpy(cast(U[]) result, *(cast(U*) &init)); }(); 1701 } 1702 return result; 1703 } 1704 1705 /// 1706 @system unittest 1707 { 1708 import std.algorithm.comparison : equal; 1709 static void test(T)() 1710 { 1711 T[] a = theAllocator.makeArray!T(2); 1712 assert(a.equal([0, 0])); 1713 a = theAllocator.makeArray!T(3, 42); 1714 assert(a.equal([42, 42, 42])); 1715 import std.range : only; 1716 a = theAllocator.makeArray!T(only(42, 43, 44)); 1717 assert(a.equal([42, 43, 44])); 1718 } 1719 test!int(); 1720 test!(shared int)(); 1721 test!(const int)(); 1722 test!(immutable int)(); 1723 } 1724 1725 @system unittest 1726 { 1727 void test(T)(in T initialValue) 1728 { 1729 auto t = theAllocator.makeArray!T(100, initialValue); 1730 //auto t = theAllocator.makeArray(100, initialValue); // works well with the old code 1731 } 1732 1733 const int init = 3; 1734 test(init); 1735 } 1736 1737 @system unittest 1738 { 1739 void test(A)(auto ref A alloc) 1740 { 1741 long[] a = alloc.makeArray!long(0, 42); 1742 assert(a.length == 0 && a.ptr is null); 1743 a = alloc.makeArray!long(5, 42); 1744 assert(a.length == 5); 1745 assert(a == [ 42, 42, 42, 42, 42 ]); 1746 } 1747 import std.experimental.allocator.gc_allocator : GCAllocator; 1748 (alloc) /*pure nothrow*/ @safe { test(alloc); } (GCAllocator.instance); 1749 test(theAllocator); 1750 } 1751 1752 // test failure with a pure, failing struct 1753 @safe unittest 1754 { 1755 import std.exception : assertThrown, enforce; 1756 1757 struct NoCopy 1758 { 1759 @disable this(); 1760 1761 this(int b){} 1762 1763 // can't be copied 1764 this(this) 1765 { 1766 enforce(1 == 2); 1767 } 1768 } 1769 import std.experimental.allocator.mallocator : Mallocator; 1770 assertThrown(makeArray!NoCopy(Mallocator.instance, 10, NoCopy(42))); 1771 } 1772 1773 // test failure with an impure, failing struct 1774 @system unittest 1775 { 1776 import std.exception : assertThrown, enforce; 1777 1778 static int i = 0; 1779 struct Singleton 1780 { 1781 @disable this(); 1782 1783 this(int b){} 1784 1785 // can't be copied 1786 this(this) 1787 { 1788 enforce(i++ == 0); 1789 } 1790 1791 ~this() 1792 { 1793 i--; 1794 } 1795 } 1796 import std.experimental.allocator.mallocator : Mallocator; 1797 assertThrown(makeArray!Singleton(Mallocator.instance, 10, Singleton(42))); 1798 } 1799 1800 /// Ditto 1801 Unqual!(ElementEncodingType!R)[] makeArray(Allocator, R)(auto ref Allocator alloc, R range) 1802 if (isInputRange!R && !isInfinite!R) 1803 { 1804 alias T = Unqual!(ElementEncodingType!R); 1805 return makeArray!(T, Allocator, R)(alloc, range); 1806 } 1807 1808 /// Ditto 1809 T[] makeArray(T, Allocator, R)(auto ref Allocator alloc, R range) 1810 if (isInputRange!R && !isInfinite!R) 1811 { 1812 static if (isForwardRange!R || hasLength!R) 1813 { 1814 static if (hasLength!R || isNarrowString!R) 1815 immutable length = range.length; 1816 else 1817 immutable length = range.save.walkLength; 1818 1819 if (!length) return null; 1820 auto m = alloc.allocate(T.sizeof * length); 1821 if (!m.ptr) return null; 1822 auto result = () @trusted { return cast(T[]) m; } (); 1823 1824 size_t i = 0; 1825 scope (failure) 1826 { 1827 foreach (j; 0 .. i) 1828 { 1829 auto p = () @trusted { return cast(Unqual!T*) &result[j]; }(); 1830 destroy(p); 1831 } 1832 1833 static if (canSafelyDeallocPostRewind!T) 1834 () @trusted { alloc.deallocate(m); } (); 1835 else 1836 alloc.deallocate(m); 1837 } 1838 1839 import std.conv : emplaceRef; 1840 static if (isNarrowString!R || isRandomAccessRange!R) 1841 { 1842 foreach (j; 0 .. range.length) 1843 { 1844 emplaceRef!T(result[i++], range[j]); 1845 } 1846 } 1847 else 1848 { 1849 for (; !range.empty; range.popFront, ++i) 1850 { 1851 emplaceRef!T(result[i], range.front); 1852 } 1853 } 1854 1855 return result; 1856 } 1857 else 1858 { 1859 // Estimated size 1860 size_t estimated = 8; 1861 auto m = alloc.allocate(T.sizeof * estimated); 1862 if (!m.ptr) return null; 1863 auto result = () @trusted { return cast(T[]) m; } (); 1864 1865 size_t initialized = 0; 1866 void bailout() 1867 { 1868 foreach (i; 0 .. initialized + 1) 1869 { 1870 destroy(result[i]); 1871 } 1872 1873 static if (canSafelyDeallocPostRewind!T) 1874 () @trusted { alloc.deallocate(m); } (); 1875 else 1876 alloc.deallocate(m); 1877 } 1878 scope (failure) bailout; 1879 1880 for (; !range.empty; range.popFront, ++initialized) 1881 { 1882 if (initialized == estimated) 1883 { 1884 // Need to reallocate 1885 static if (hasPurePostblit!T) 1886 auto success = () @trusted { return alloc.reallocate(m, T.sizeof * (estimated *= 2)); } (); 1887 else 1888 auto success = alloc.reallocate(m, T.sizeof * (estimated *= 2)); 1889 if (!success) 1890 { 1891 bailout; 1892 return null; 1893 } 1894 result = () @trusted { return cast(T[]) m; } (); 1895 } 1896 import std.conv : emplaceRef; 1897 emplaceRef(result[initialized], range.front); 1898 } 1899 1900 if (initialized < estimated) 1901 { 1902 // Try to shrink memory, no harm if not possible 1903 static if (hasPurePostblit!T) 1904 auto success = () @trusted { return alloc.reallocate(m, T.sizeof * initialized); } (); 1905 else 1906 auto success = alloc.reallocate(m, T.sizeof * initialized); 1907 if (success) 1908 result = () @trusted { return cast(T[]) m; } (); 1909 } 1910 1911 return result[0 .. initialized]; 1912 } 1913 } 1914 1915 @system unittest 1916 { 1917 void test(A)(auto ref A alloc) 1918 { 1919 long[] a = alloc.makeArray!long((int[]).init); 1920 assert(a.length == 0 && a.ptr is null); 1921 a = alloc.makeArray!long([5, 42]); 1922 assert(a.length == 2); 1923 assert(a == [ 5, 42]); 1924 1925 // we can also infer the type 1926 auto b = alloc.makeArray([4.0, 2.0]); 1927 static assert(is(typeof(b) == double[])); 1928 assert(b == [4.0, 2.0]); 1929 } 1930 import std.experimental.allocator.gc_allocator : GCAllocator; 1931 (alloc) pure nothrow @safe { test(alloc); } (GCAllocator.instance); 1932 test(theAllocator); 1933 } 1934 1935 // infer types for strings 1936 @system unittest 1937 { 1938 void test(A)(auto ref A alloc) 1939 { 1940 auto c = alloc.makeArray("fooπ😜"); 1941 static assert(is(typeof(c) == char[])); 1942 assert(c == "fooπ😜"); 1943 1944 auto d = alloc.makeArray("fooπ😜"d); 1945 static assert(is(typeof(d) == dchar[])); 1946 assert(d == "fooπ😜"); 1947 1948 auto w = alloc.makeArray("fooπ😜"w); 1949 static assert(is(typeof(w) == wchar[])); 1950 assert(w == "fooπ😜"); 1951 } 1952 1953 import std.experimental.allocator.gc_allocator : GCAllocator; 1954 (alloc) pure nothrow @safe { test(alloc); } (GCAllocator.instance); 1955 test(theAllocator); 1956 } 1957 1958 /*pure*/ nothrow @safe unittest 1959 { 1960 import std.algorithm.comparison : equal; 1961 import std.experimental.allocator.gc_allocator : GCAllocator; 1962 import std.internal.test.dummyrange; 1963 import std.range : iota; 1964 foreach (DummyType; AllDummyRanges) 1965 { 1966 (alloc) pure nothrow @safe 1967 { 1968 DummyType d; 1969 auto arr = alloc.makeArray(d); 1970 assert(arr.length == 10); 1971 assert(arr.equal(iota(1, 11))); 1972 } (GCAllocator.instance); 1973 } 1974 } 1975 1976 // test failure with a pure, failing struct 1977 @safe unittest 1978 { 1979 import std.exception : assertThrown, enforce; 1980 1981 struct NoCopy 1982 { 1983 int b; 1984 1985 @disable this(); 1986 1987 this(int b) 1988 { 1989 this.b = b; 1990 } 1991 1992 // can't be copied 1993 this(this) 1994 { 1995 enforce(b < 3, "there can only be three elements"); 1996 } 1997 } 1998 import std.experimental.allocator.mallocator : Mallocator; 1999 auto arr = [NoCopy(1), NoCopy(2), NoCopy(3)]; 2000 assertThrown(makeArray!NoCopy(Mallocator.instance, arr)); 2001 2002 struct NoCopyRange 2003 { 2004 static j = 0; 2005 bool empty() 2006 { 2007 return j > 5; 2008 } 2009 2010 auto front() 2011 { 2012 return NoCopy(j); 2013 } 2014 2015 void popFront() 2016 { 2017 j++; 2018 } 2019 } 2020 assertThrown(makeArray!NoCopy(Mallocator.instance, NoCopyRange())); 2021 } 2022 2023 // test failure with an impure, failing struct 2024 @system unittest 2025 { 2026 import std.exception : assertThrown, enforce; 2027 2028 static i = 0; 2029 static maxElements = 2; 2030 struct NoCopy 2031 { 2032 int val; 2033 @disable this(); 2034 2035 this(int b){ 2036 this.val = i++; 2037 } 2038 2039 // can't be copied 2040 this(this) 2041 { 2042 enforce(i++ < maxElements, "there can only be four elements"); 2043 } 2044 } 2045 2046 import std.experimental.allocator.mallocator : Mallocator; 2047 auto arr = [NoCopy(1), NoCopy(2)]; 2048 assertThrown(makeArray!NoCopy(Mallocator.instance, arr)); 2049 2050 // allow more copies and thus force reallocation 2051 i = 0; 2052 maxElements = 30; 2053 static j = 0; 2054 2055 struct NoCopyRange 2056 { 2057 bool empty() 2058 { 2059 return j > 100; 2060 } 2061 2062 auto front() 2063 { 2064 return NoCopy(1); 2065 } 2066 2067 void popFront() 2068 { 2069 j++; 2070 } 2071 } 2072 assertThrown(makeArray!NoCopy(Mallocator.instance, NoCopyRange())); 2073 2074 maxElements = 300; 2075 auto arr2 = makeArray!NoCopy(Mallocator.instance, NoCopyRange()); 2076 2077 import std.algorithm.comparison : equal; 2078 import std.algorithm.iteration : map; 2079 import std.range : iota; 2080 assert(arr2.map!`a.val`.equal(iota(32, 204, 2))); 2081 } 2082 2083 version (StdUnittest) 2084 { 2085 private struct ForcedInputRange(T) 2086 { 2087 T[]* array; 2088 pure nothrow @safe @nogc: 2089 bool empty() { return !array || (*array).empty; } 2090 ref T front() { return (*array)[0]; } 2091 void popFront() { *array = (*array)[1 .. $]; } 2092 } 2093 } 2094 2095 @system unittest 2096 { 2097 import std.array : array; 2098 import std.range : iota; 2099 int[] arr = iota(10).array; 2100 2101 void test(A)(auto ref A alloc) 2102 { 2103 ForcedInputRange!int r; 2104 long[] a = alloc.makeArray!long(r); 2105 assert(a.length == 0 && a.ptr is null); 2106 auto arr2 = arr; 2107 r.array = () @trusted { return &arr2; } (); 2108 a = alloc.makeArray!long(r); 2109 assert(a.length == 10); 2110 assert(a == iota(10).array); 2111 } 2112 import std.experimental.allocator.gc_allocator : GCAllocator; 2113 (alloc) pure nothrow @safe { test(alloc); } (GCAllocator.instance); 2114 test(theAllocator); 2115 } 2116 2117 /** 2118 Grows `array` by appending `delta` more elements. The needed memory is 2119 allocated using `alloc`. The extra elements added are either default- 2120 initialized, filled with copies of `init`, or initialized with values 2121 fetched from `range`. 2122 2123 Params: 2124 T = element type of the array being created 2125 alloc = the allocator used for getting memory 2126 array = a reference to the array being grown 2127 delta = number of elements to add (upon success the new length of `array` is 2128 $(D array.length + delta)) 2129 init = element used for filling the array 2130 range = range used for initializing the array elements 2131 2132 Returns: 2133 `true` upon success, `false` if memory could not be allocated. In the 2134 latter case `array` is left unaffected. 2135 2136 Throws: 2137 The first two overloads throw only if `alloc`'s primitives do. The 2138 overloads that involve copy initialization deallocate memory and propagate the 2139 exception if the copy operation throws. 2140 */ 2141 bool expandArray(T, Allocator)(auto ref Allocator alloc, ref T[] array, 2142 size_t delta) 2143 { 2144 if (!delta) return true; 2145 if (array is null) return false; 2146 immutable oldLength = array.length; 2147 void[] buf = array; 2148 if (!alloc.reallocate(buf, buf.length + T.sizeof * delta)) return false; 2149 array = cast(T[]) buf; 2150 array[oldLength .. $].uninitializedFillDefault; 2151 return true; 2152 } 2153 2154 @system unittest 2155 { 2156 void test(A)(auto ref A alloc) 2157 { 2158 auto arr = alloc.makeArray!int([1, 2, 3]); 2159 assert(alloc.expandArray(arr, 3)); 2160 assert(arr == [1, 2, 3, 0, 0, 0]); 2161 } 2162 import std.experimental.allocator.gc_allocator : GCAllocator; 2163 test(GCAllocator.instance); 2164 test(theAllocator); 2165 } 2166 2167 /// Ditto 2168 bool expandArray(T, Allocator)(auto ref Allocator alloc, ref T[] array, 2169 size_t delta, auto ref T init) 2170 { 2171 if (!delta) return true; 2172 if (array is null) return false; 2173 void[] buf = array; 2174 if (!alloc.reallocate(buf, buf.length + T.sizeof * delta)) return false; 2175 immutable oldLength = array.length; 2176 array = cast(T[]) buf; 2177 scope(failure) array[oldLength .. $].uninitializedFillDefault; 2178 import std.algorithm.mutation : uninitializedFill; 2179 array[oldLength .. $].uninitializedFill(init); 2180 return true; 2181 } 2182 2183 @system unittest 2184 { 2185 void test(A)(auto ref A alloc) 2186 { 2187 auto arr = alloc.makeArray!int([1, 2, 3]); 2188 assert(alloc.expandArray(arr, 3, 1)); 2189 assert(arr == [1, 2, 3, 1, 1, 1]); 2190 } 2191 import std.experimental.allocator.gc_allocator : GCAllocator; 2192 test(GCAllocator.instance); 2193 test(theAllocator); 2194 } 2195 2196 /// Ditto 2197 bool expandArray(T, Allocator, R)(auto ref Allocator alloc, ref T[] array, 2198 R range) 2199 if (isInputRange!R) 2200 { 2201 if (array is null) return false; 2202 static if (isForwardRange!R) 2203 { 2204 immutable delta = walkLength(range.save); 2205 if (!delta) return true; 2206 immutable oldLength = array.length; 2207 2208 // Reallocate support memory 2209 void[] buf = array; 2210 if (!alloc.reallocate(buf, buf.length + T.sizeof * delta)) 2211 { 2212 return false; 2213 } 2214 array = cast(T[]) buf; 2215 // At this point we're committed to the new length. 2216 2217 auto toFill = array[oldLength .. $]; 2218 scope (failure) 2219 { 2220 // Fill the remainder with default-constructed data 2221 toFill.uninitializedFillDefault; 2222 } 2223 2224 for (; !range.empty; range.popFront, toFill = toFill[1 .. $]) 2225 { 2226 assert(toFill.length > 0); 2227 import std.conv : emplace; 2228 emplace!T(&toFill[0], range.front); 2229 } 2230 assert(toFill.length == 0); 2231 } 2232 else 2233 { 2234 scope(failure) 2235 { 2236 // The last element didn't make it, fill with default 2237 array[$ - 1 .. $].uninitializedFillDefault; 2238 } 2239 void[] buf = array; 2240 for (; !range.empty; range.popFront) 2241 { 2242 if (!alloc.reallocate(buf, buf.length + T.sizeof)) 2243 { 2244 array = cast(T[]) buf; 2245 return false; 2246 } 2247 import std.conv : emplace; 2248 emplace!T(buf[$ - T.sizeof .. $], range.front); 2249 } 2250 2251 array = cast(T[]) buf; 2252 } 2253 return true; 2254 } 2255 2256 /// 2257 @system unittest 2258 { 2259 auto arr = theAllocator.makeArray!int([1, 2, 3]); 2260 assert(theAllocator.expandArray(arr, 2)); 2261 assert(arr == [1, 2, 3, 0, 0]); 2262 import std.range : only; 2263 assert(theAllocator.expandArray(arr, only(4, 5))); 2264 assert(arr == [1, 2, 3, 0, 0, 4, 5]); 2265 } 2266 2267 @system unittest 2268 { 2269 auto arr = theAllocator.makeArray!int([1, 2, 3]); 2270 ForcedInputRange!int r; 2271 int[] b = [ 1, 2, 3, 4 ]; 2272 auto temp = b; 2273 r.array = &temp; 2274 assert(theAllocator.expandArray(arr, r)); 2275 assert(arr == [1, 2, 3, 1, 2, 3, 4]); 2276 } 2277 2278 // Regression test for https://issues.dlang.org/show_bug.cgi?id=20929 2279 @system unittest 2280 { 2281 static void test(Char, Allocator)(auto ref Allocator alloc) 2282 { 2283 auto arr = alloc.makeArray!Char(1, Char('f')); 2284 2285 import std.utf : byUTF; 2286 auto forwardRange = "oo".byUTF!Char(); 2287 static assert(isForwardRange!(typeof(forwardRange))); 2288 // Test the forward-range code-path. 2289 assert(alloc.expandArray(arr, forwardRange)); 2290 2291 assert(arr == "foo"); 2292 2293 immutable(Char)[] temp = "bar"; 2294 auto inputRange = ForcedInputRange!(immutable(Char))(&temp); 2295 // Test the input-range code-path. 2296 assert(alloc.expandArray(arr, inputRange)); 2297 2298 assert(arr == "foobar"); 2299 } 2300 2301 import std.experimental.allocator.gc_allocator : GCAllocator; 2302 test!char(GCAllocator.instance); 2303 test!wchar(GCAllocator.instance); 2304 test!char(theAllocator); 2305 test!wchar(theAllocator); 2306 } 2307 2308 /** 2309 Shrinks an array by `delta` elements. 2310 2311 If $(D array.length < delta), does nothing and returns `false`. Otherwise, 2312 destroys the last $(D array.length - delta) elements in the array and then 2313 reallocates the array's buffer. If reallocation fails, fills the array with 2314 default-initialized data. 2315 2316 Params: 2317 T = element type of the array being created 2318 alloc = the allocator used for getting memory 2319 array = a reference to the array being shrunk 2320 delta = number of elements to remove (upon success the new length of `array` is $(D array.length - delta)) 2321 2322 Returns: 2323 `true` upon success, `false` if memory could not be reallocated. In the latter 2324 case, the slice $(D array[$ - delta .. $]) is left with default-initialized 2325 elements. 2326 2327 Throws: 2328 The first two overloads throw only if `alloc`'s primitives do. The 2329 overloads that involve copy initialization deallocate memory and propagate the 2330 exception if the copy operation throws. 2331 */ 2332 bool shrinkArray(T, Allocator)(auto ref Allocator alloc, 2333 ref T[] array, size_t delta) 2334 { 2335 if (delta > array.length) return false; 2336 2337 // Destroy elements. If a destructor throws, fill the already destroyed 2338 // stuff with the default initializer. 2339 { 2340 size_t destroyed; 2341 scope(failure) 2342 { 2343 array[$ - delta .. $][0 .. destroyed].uninitializedFillDefault; 2344 } 2345 foreach (ref e; array[$ - delta .. $]) 2346 { 2347 e.destroy; 2348 ++destroyed; 2349 } 2350 } 2351 2352 if (delta == array.length) 2353 { 2354 alloc.deallocate(array); 2355 array = null; 2356 return true; 2357 } 2358 2359 void[] buf = array; 2360 if (!alloc.reallocate(buf, buf.length - T.sizeof * delta)) 2361 { 2362 // urgh, at least fill back with default 2363 array[$ - delta .. $].uninitializedFillDefault; 2364 return false; 2365 } 2366 array = cast(T[]) buf; 2367 return true; 2368 } 2369 2370 /// 2371 @system unittest 2372 { 2373 int[] a = theAllocator.makeArray!int(100, 42); 2374 assert(a.length == 100); 2375 assert(theAllocator.shrinkArray(a, 98)); 2376 assert(a.length == 2); 2377 assert(a == [42, 42]); 2378 } 2379 2380 @system unittest 2381 { 2382 void test(A)(auto ref A alloc) 2383 { 2384 long[] a = alloc.makeArray!long((int[]).init); 2385 assert(a.length == 0 && a.ptr is null); 2386 a = alloc.makeArray!long(100, 42); 2387 assert(alloc.shrinkArray(a, 98)); 2388 assert(a.length == 2); 2389 assert(a == [ 42, 42]); 2390 } 2391 import std.experimental.allocator.gc_allocator : GCAllocator; 2392 test(GCAllocator.instance); 2393 test(theAllocator); 2394 } 2395 2396 /** 2397 2398 Destroys and then deallocates (using `alloc`) the object pointed to by a 2399 pointer, the class object referred to by a `class` or `interface` 2400 reference, or an entire array. It is assumed the respective entities had been 2401 allocated with the same allocator. 2402 2403 */ 2404 void dispose(A, T)(auto ref A alloc, auto ref T* p) 2405 { 2406 static if (hasElaborateDestructor!T) 2407 { 2408 destroy(*p); 2409 } 2410 alloc.deallocate((cast(void*) p)[0 .. T.sizeof]); 2411 static if (__traits(isRef, p)) 2412 p = null; 2413 } 2414 2415 /// Ditto 2416 void dispose(A, T)(auto ref A alloc, auto ref T p) 2417 if (is(T == class) || is(T == interface)) 2418 { 2419 if (!p) return; 2420 static if (is(T == interface)) 2421 { 2422 version (Windows) 2423 { 2424 import core.sys.windows.unknwn : IUnknown; 2425 static assert(!is(T: IUnknown), "COM interfaces can't be destroyed in " 2426 ~ __PRETTY_FUNCTION__); 2427 } 2428 auto ob = cast(Object) p; 2429 } 2430 else 2431 alias ob = p; 2432 auto support = (cast(void*) ob)[0 .. typeid(ob).initializer.length]; 2433 destroy(p); 2434 alloc.deallocate(support); 2435 static if (__traits(isRef, p)) 2436 p = null; 2437 } 2438 2439 /// Ditto 2440 void dispose(A, T)(auto ref A alloc, auto ref T[] array) 2441 { 2442 static if (hasElaborateDestructor!(typeof(array[0]))) 2443 { 2444 foreach (ref e; array) 2445 { 2446 destroy(e); 2447 } 2448 } 2449 alloc.deallocate(array); 2450 static if (__traits(isRef, array)) 2451 array = null; 2452 } 2453 2454 @system unittest 2455 { 2456 static int x; 2457 static interface I 2458 { 2459 void method(); 2460 } 2461 static class A : I 2462 { 2463 int y; 2464 override void method() { x = 21; } 2465 ~this() { x = 42; } 2466 } 2467 static class B : A 2468 { 2469 } 2470 auto a = theAllocator.make!A; 2471 a.method(); 2472 assert(x == 21); 2473 theAllocator.dispose(a); 2474 assert(x == 42); 2475 2476 B b = theAllocator.make!B; 2477 b.method(); 2478 assert(x == 21); 2479 theAllocator.dispose(b); 2480 assert(x == 42); 2481 2482 I i = theAllocator.make!B; 2483 i.method(); 2484 assert(x == 21); 2485 theAllocator.dispose(i); 2486 assert(x == 42); 2487 2488 int[] arr = theAllocator.makeArray!int(43); 2489 theAllocator.dispose(arr); 2490 } 2491 2492 // https://issues.dlang.org/show_bug.cgi?id=16512 2493 @system unittest 2494 { 2495 import std.experimental.allocator.mallocator : Mallocator; 2496 2497 int* i = Mallocator.instance.make!int(0); 2498 Mallocator.instance.dispose(i); 2499 assert(i is null); 2500 2501 Object o = Mallocator.instance.make!Object(); 2502 Mallocator.instance.dispose(o); 2503 assert(o is null); 2504 2505 uint* u = Mallocator.instance.make!uint(0); 2506 Mallocator.instance.dispose((){return u;}()); 2507 assert(u !is null); 2508 2509 uint[] ua = Mallocator.instance.makeArray!uint([0,1,2]); 2510 Mallocator.instance.dispose(ua); 2511 assert(ua is null); 2512 } 2513 2514 // https://issues.dlang.org/show_bug.cgi?id=15721 2515 @system unittest 2516 { 2517 import std.experimental.allocator.mallocator : Mallocator; 2518 2519 interface Foo {} 2520 class Bar: Foo {} 2521 2522 Bar bar; 2523 Foo foo; 2524 bar = Mallocator.instance.make!Bar; 2525 foo = cast(Foo) bar; 2526 Mallocator.instance.dispose(foo); 2527 } 2528 2529 /** 2530 Allocates a multidimensional array of elements of type T. 2531 2532 Params: 2533 N = number of dimensions 2534 T = element type of an element of the multidimensional arrat 2535 alloc = the allocator used for getting memory 2536 lengths = static array containing the size of each dimension 2537 2538 Returns: 2539 An N-dimensional array with individual elements of type T. 2540 */ 2541 auto makeMultidimensionalArray(T, Allocator, size_t N)(auto ref Allocator alloc, size_t[N] lengths...) 2542 { 2543 static if (N == 1) 2544 { 2545 return makeArray!T(alloc, lengths[0]); 2546 } 2547 else 2548 { 2549 alias E = typeof(makeMultidimensionalArray!(T, Allocator, N - 1)(alloc, lengths[1 .. $])); 2550 auto ret = makeArray!E(alloc, lengths[0]); 2551 foreach (ref e; ret) 2552 e = makeMultidimensionalArray!(T, Allocator, N - 1)(alloc, lengths[1 .. $]); 2553 return ret; 2554 } 2555 } 2556 2557 /// 2558 @system unittest 2559 { 2560 import std.experimental.allocator.mallocator : Mallocator; 2561 2562 auto mArray = Mallocator.instance.makeMultidimensionalArray!int(2, 3, 6); 2563 2564 // deallocate when exiting scope 2565 scope(exit) 2566 { 2567 Mallocator.instance.disposeMultidimensionalArray(mArray); 2568 } 2569 2570 assert(mArray.length == 2); 2571 foreach (lvl2Array; mArray) 2572 { 2573 assert(lvl2Array.length == 3); 2574 foreach (lvl3Array; lvl2Array) 2575 assert(lvl3Array.length == 6); 2576 } 2577 } 2578 2579 /** 2580 Destroys and then deallocates a multidimensional array, assuming it was 2581 created with makeMultidimensionalArray and the same allocator was used. 2582 2583 Params: 2584 T = element type of an element of the multidimensional array 2585 alloc = the allocator used for getting memory 2586 array = the multidimensional array that is to be deallocated 2587 */ 2588 void disposeMultidimensionalArray(T, Allocator)(auto ref Allocator alloc, auto ref T[] array) 2589 { 2590 static if (isArray!T) 2591 { 2592 foreach (ref e; array) 2593 disposeMultidimensionalArray(alloc, e); 2594 } 2595 2596 dispose(alloc, array); 2597 static if (__traits(isRef, array)) 2598 array = null; 2599 } 2600 2601 /// 2602 @system unittest 2603 { 2604 struct TestAllocator 2605 { 2606 import std.experimental.allocator.common : platformAlignment; 2607 import std.experimental.allocator.mallocator : Mallocator; 2608 2609 alias allocator = Mallocator.instance; 2610 2611 private static struct ByteRange 2612 { 2613 void* ptr; 2614 size_t length; 2615 } 2616 2617 private ByteRange[] _allocations; 2618 2619 enum uint alignment = platformAlignment; 2620 2621 void[] allocate(size_t numBytes) 2622 { 2623 auto ret = allocator.allocate(numBytes); 2624 _allocations ~= ByteRange(ret.ptr, ret.length); 2625 return ret; 2626 } 2627 2628 bool deallocate(void[] bytes) 2629 { 2630 import std.algorithm.mutation : remove; 2631 import std.algorithm.searching : canFind; 2632 2633 bool pred(ByteRange other) 2634 { return other.ptr == bytes.ptr && other.length == bytes.length; } 2635 2636 assert(_allocations.canFind!pred); 2637 2638 _allocations = _allocations.remove!pred; 2639 return allocator.deallocate(bytes); 2640 } 2641 2642 ~this() 2643 { 2644 assert(!_allocations.length); 2645 } 2646 } 2647 2648 TestAllocator allocator; 2649 2650 auto mArray = allocator.makeMultidimensionalArray!int(2, 3, 5, 6, 7, 2); 2651 2652 allocator.disposeMultidimensionalArray(mArray); 2653 } 2654 2655 /** 2656 2657 Returns a dynamically-typed `CAllocator` built around a given statically- 2658 typed allocator `a` of type `A`. Passing a pointer to the allocator 2659 creates a dynamic allocator around the allocator pointed to by the pointer, 2660 without attempting to copy or move it. Passing the allocator by value or 2661 reference behaves as follows. 2662 2663 $(UL 2664 $(LI If `A` has no state, the resulting object is allocated in static 2665 shared storage.) 2666 $(LI If `A` has state, the result will $(REF move, std,algorithm,mutation) 2667 the supplied allocator $(D A a) within. The result itself is allocated in its 2668 own statically-typed allocator.) 2669 ) 2670 2671 */ 2672 RCIAllocator allocatorObject(A)(auto ref A a) 2673 if (!isPointer!A) 2674 { 2675 import std.conv : emplace; 2676 static if (stateSize!A == 0) 2677 { 2678 enum s = stateSize!(CAllocatorImpl!A).divideRoundUp(ulong.sizeof); 2679 __gshared ulong[s] state; 2680 __gshared RCIAllocator result; 2681 if (result.isNull) 2682 { 2683 // Don't care about a few races 2684 result = RCIAllocator(emplace!(CAllocatorImpl!A)(state[])); 2685 } 2686 assert(!result.isNull); 2687 return result; 2688 } 2689 else 2690 { 2691 auto state = a.allocate(stateSize!(CAllocatorImpl!A)); 2692 import std.algorithm.mutation : move; 2693 import std.traits : hasMember; 2694 static if (hasMember!(A, "deallocate")) 2695 { 2696 scope(failure) a.deallocate(state); 2697 } 2698 auto tmp = cast(CAllocatorImpl!A) emplace!(CAllocatorImpl!A)(state); 2699 move(a, tmp.impl); 2700 return RCIAllocator(tmp); 2701 } 2702 } 2703 2704 /// Ditto 2705 RCIAllocator allocatorObject(A)(A* pa) 2706 { 2707 assert(pa); 2708 import std.conv : emplace; 2709 auto state = pa.allocate(stateSize!(CAllocatorImpl!(A, Yes.indirect))); 2710 import std.traits : hasMember; 2711 static if (hasMember!(A, "deallocate")) 2712 { 2713 scope(failure) pa.deallocate(state); 2714 } 2715 return RCIAllocator(emplace!(CAllocatorImpl!(A, Yes.indirect)) 2716 (state, pa)); 2717 } 2718 2719 /// 2720 @system unittest 2721 { 2722 import std.experimental.allocator.mallocator : Mallocator; 2723 2724 RCIAllocator a = allocatorObject(Mallocator.instance); 2725 auto b = a.allocate(100); 2726 assert(b.length == 100); 2727 assert(a.deallocate(b)); 2728 2729 // The in-situ region must be used by pointer 2730 import std.experimental.allocator.building_blocks.region : InSituRegion; 2731 auto r = InSituRegion!1024(); 2732 a = allocatorObject(&r); 2733 b = a.allocate(200); 2734 assert(b.length == 200); 2735 // In-situ regions can deallocate the last allocation 2736 assert(a.deallocate(b)); 2737 } 2738 2739 @system unittest 2740 { 2741 import std.conv; 2742 import std.experimental.allocator.mallocator; 2743 import std.experimental.allocator.building_blocks.stats_collector; 2744 2745 alias SCAlloc = StatsCollector!(Mallocator, Options.bytesUsed); 2746 SCAlloc statsCollectorAlloc; 2747 assert(statsCollectorAlloc.bytesUsed == 0); 2748 2749 auto _allocator = allocatorObject(statsCollectorAlloc); 2750 // Ensure that the allocator was passed through in CAllocatorImpl 2751 // This allocator was used to allocate the chunk that holds the 2752 // CAllocatorImpl object; which is it's own wrapper 2753 assert((cast(CAllocatorImpl!(SCAlloc))(_allocator._alloc)).impl.bytesUsed 2754 == stateSize!(CAllocatorImpl!(SCAlloc))); 2755 _allocator.allocate(1); 2756 assert((cast(CAllocatorImpl!(SCAlloc))(_allocator._alloc)).impl.bytesUsed 2757 == stateSize!(CAllocatorImpl!(SCAlloc)) + 1); 2758 } 2759 2760 /** 2761 2762 Returns a dynamically-typed `CSharedAllocator` built around a given statically- 2763 typed allocator `a` of type `A`. Passing a pointer to the allocator 2764 creates a dynamic allocator around the allocator pointed to by the pointer, 2765 without attempting to copy or move it. Passing the allocator by value or 2766 reference behaves as follows. 2767 2768 $(UL 2769 $(LI If `A` has no state, the resulting object is allocated in static 2770 shared storage.) 2771 $(LI If `A` has state and is copyable, the result will 2772 $(REF move, std,algorithm,mutation) the supplied allocator $(D A a) within. 2773 The result itself is allocated in its own statically-typed allocator.) 2774 $(LI If `A` has state and is not copyable, the result will move the 2775 passed-in argument into the result. The result itself is allocated in its own 2776 statically-typed allocator.) 2777 ) 2778 2779 */ 2780 //nothrow @safe 2781 //nothrow @nogc @safe 2782 nothrow 2783 RCISharedAllocator sharedAllocatorObject(A)(auto ref A a) 2784 if (!isPointer!A) 2785 { 2786 import std.conv : emplace; 2787 static if (stateSize!A == 0) 2788 { 2789 enum s = stateSize!(CSharedAllocatorImpl!A).divideRoundUp(ulong.sizeof); 2790 static shared ulong[s] state; 2791 static RCISharedAllocator result; 2792 if (result.isNull) 2793 { 2794 // Don't care about a few races 2795 result = RCISharedAllocator( 2796 (cast(shared CSharedAllocatorImpl!A)( 2797 emplace!(CSharedAllocatorImpl!A)( 2798 (() @trusted => cast(ulong[]) state[])())))); 2799 } 2800 assert(!result.isNull); 2801 return result; 2802 } 2803 else static if (is(typeof({ shared A b = a; shared A c = b; }))) // copyable 2804 { 2805 auto state = a.allocate(stateSize!(CSharedAllocatorImpl!A)); 2806 import std.algorithm.mutation : move; 2807 import std.traits : hasMember; 2808 static if (hasMember!(A, "deallocate")) 2809 { 2810 scope(failure) a.deallocate(state); 2811 } 2812 auto tmp = emplace!(shared CSharedAllocatorImpl!A)(state); 2813 move(a, tmp.impl); 2814 return RCISharedAllocator(tmp); 2815 } 2816 else // the allocator object is not copyable 2817 { 2818 assert(0, "Not yet implemented"); 2819 } 2820 } 2821 2822 /// Ditto 2823 RCISharedAllocator sharedAllocatorObject(A)(A* pa) 2824 { 2825 assert(pa); 2826 import std.conv : emplace; 2827 auto state = pa.allocate(stateSize!(CSharedAllocatorImpl!(A, Yes.indirect))); 2828 import std.traits : hasMember; 2829 static if (hasMember!(A, "deallocate")) 2830 { 2831 scope(failure) pa.deallocate(state); 2832 } 2833 return RCISharedAllocator(emplace!(shared CSharedAllocatorImpl!(A, Yes.indirect))(state, pa)); 2834 } 2835 2836 2837 /** 2838 2839 Implementation of `IAllocator` using `Allocator`. This adapts a 2840 statically-built allocator type to `IAllocator` that is directly usable by 2841 non-templated code. 2842 2843 Usually `CAllocatorImpl` is used indirectly by calling $(LREF theAllocator). 2844 */ 2845 class CAllocatorImpl(Allocator, Flag!"indirect" indirect = No.indirect) 2846 : IAllocator 2847 { 2848 import std.traits : hasMember; 2849 2850 static if (stateSize!Allocator) private size_t rc = 1; 2851 2852 /** 2853 The implementation is available as a public member. 2854 */ 2855 static if (indirect) 2856 { 2857 nothrow: 2858 private Allocator* pimpl; 2859 2860 @nogc pure @safe 2861 ref Allocator impl() 2862 { 2863 return *pimpl; 2864 } 2865 2866 @nogc pure @safe 2867 this(Allocator* pa) 2868 { 2869 pimpl = pa; 2870 } 2871 } 2872 else 2873 { 2874 static if (stateSize!Allocator) Allocator impl; 2875 else alias impl = Allocator.instance; 2876 } 2877 2878 nothrow: 2879 /// Returns `impl.alignment`. 2880 override @property uint alignment() 2881 { 2882 return impl.alignment; 2883 } 2884 2885 /** 2886 Returns `impl.goodAllocSize(s)`. 2887 */ 2888 override size_t goodAllocSize(size_t s) 2889 { 2890 return impl.goodAllocSize(s); 2891 } 2892 2893 /** 2894 Returns `impl.allocate(s)`. 2895 */ 2896 override void[] allocate(size_t s, TypeInfo ti = null) 2897 { 2898 return impl.allocate(s); 2899 } 2900 2901 /** 2902 If `impl.alignedAllocate` exists, calls it and returns the result. 2903 Otherwise, always returns `null`. 2904 */ 2905 override void[] alignedAllocate(size_t s, uint a) 2906 { 2907 static if (hasMember!(Allocator, "alignedAllocate")) 2908 return impl.alignedAllocate(s, a); 2909 else 2910 return null; 2911 } 2912 2913 /** 2914 If `Allocator` implements `owns`, forwards to it. Otherwise, returns 2915 `Ternary.unknown`. 2916 */ 2917 override Ternary owns(void[] b) 2918 { 2919 static if (hasMember!(Allocator, "owns")) return impl.owns(b); 2920 else return Ternary.unknown; 2921 } 2922 2923 /// Returns $(D impl.expand(b, s)) if defined, `false` otherwise. 2924 override bool expand(ref void[] b, size_t s) 2925 { 2926 static if (hasMember!(Allocator, "expand")) 2927 return impl.expand(b, s); 2928 else 2929 return s == 0; 2930 } 2931 2932 /// Returns $(D impl.reallocate(b, s)). 2933 override bool reallocate(ref void[] b, size_t s) 2934 { 2935 return impl.reallocate(b, s); 2936 } 2937 2938 /// Forwards to `impl.alignedReallocate` if defined, `false` otherwise. 2939 bool alignedReallocate(ref void[] b, size_t s, uint a) 2940 { 2941 static if (!hasMember!(Allocator, "alignedAllocate")) 2942 { 2943 return false; 2944 } 2945 else 2946 { 2947 return impl.alignedReallocate(b, s, a); 2948 } 2949 } 2950 2951 // Undocumented for now 2952 Ternary resolveInternalPointer(const void* p, ref void[] result) 2953 { 2954 static if (hasMember!(Allocator, "resolveInternalPointer")) 2955 { 2956 return impl.resolveInternalPointer(p, result); 2957 } 2958 else 2959 { 2960 return Ternary.unknown; 2961 } 2962 } 2963 2964 /** 2965 If `impl.deallocate` is not defined, returns `false`. Otherwise it forwards 2966 the call. 2967 */ 2968 override bool deallocate(void[] b) 2969 { 2970 static if (hasMember!(Allocator, "deallocate")) 2971 { 2972 return impl.deallocate(b); 2973 } 2974 else 2975 { 2976 return false; 2977 } 2978 } 2979 2980 /** 2981 Calls `impl.deallocateAll()` and returns the result if defined, 2982 otherwise returns `false`. 2983 */ 2984 override bool deallocateAll() 2985 { 2986 static if (hasMember!(Allocator, "deallocateAll")) 2987 { 2988 return impl.deallocateAll(); 2989 } 2990 else 2991 { 2992 return false; 2993 } 2994 } 2995 2996 /** 2997 Forwards to `impl.empty()` if defined, otherwise returns `Ternary.unknown`. 2998 */ 2999 override Ternary empty() 3000 { 3001 static if (hasMember!(Allocator, "empty")) 3002 { 3003 return Ternary(impl.empty); 3004 } 3005 else 3006 { 3007 return Ternary.unknown; 3008 } 3009 } 3010 3011 /** 3012 Returns `impl.allocateAll()` if present, `null` otherwise. 3013 */ 3014 override void[] allocateAll() 3015 { 3016 static if (hasMember!(Allocator, "allocateAll")) 3017 { 3018 return impl.allocateAll(); 3019 } 3020 else 3021 { 3022 return null; 3023 } 3024 } 3025 3026 @nogc nothrow pure @safe 3027 override void incRef() 3028 { 3029 static if (stateSize!Allocator) ++rc; 3030 } 3031 3032 @nogc nothrow pure @trusted 3033 override bool decRef() 3034 { 3035 static if (stateSize!Allocator) 3036 { 3037 import core.stdc..string : memcpy; 3038 3039 if (rc == 1) 3040 { 3041 static if (indirect) 3042 { 3043 Allocator* tmp = pimpl; 3044 } 3045 else 3046 { 3047 Allocator tmp; 3048 memcpy(&tmp, &this.impl, Allocator.sizeof); 3049 } 3050 void[] support = (cast(void*) this)[0 .. stateSize!(typeof(this))]; 3051 tmp.deallocate(support); 3052 return false; 3053 } 3054 3055 --rc; 3056 return true; 3057 } 3058 else 3059 { 3060 return true; 3061 } 3062 } 3063 } 3064 3065 /** 3066 3067 Implementation of `ISharedAllocator` using `Allocator`. This adapts a 3068 statically-built, shareable across threads, allocator type to `ISharedAllocator` 3069 that is directly usable by non-templated code. 3070 3071 Usually `CSharedAllocatorImpl` is used indirectly by calling 3072 $(LREF processAllocator). 3073 */ 3074 class CSharedAllocatorImpl(Allocator, Flag!"indirect" indirect = No.indirect) 3075 : ISharedAllocator 3076 { 3077 import std.traits : hasMember; 3078 import core.atomic : atomicOp, atomicLoad; 3079 3080 static if (stateSize!Allocator) shared size_t rc = 1; 3081 3082 /** 3083 The implementation is available as a public member. 3084 */ 3085 static if (indirect) 3086 { 3087 nothrow: 3088 private shared Allocator* pimpl; 3089 3090 @nogc pure @safe 3091 ref Allocator impl() shared 3092 { 3093 return *pimpl; 3094 } 3095 3096 @nogc pure @safe 3097 this(Allocator* pa) shared 3098 { 3099 pimpl = pa; 3100 } 3101 } 3102 else 3103 { 3104 static if (stateSize!Allocator) shared Allocator impl; 3105 else alias impl = Allocator.instance; 3106 } 3107 3108 nothrow: 3109 /// Returns `impl.alignment`. 3110 override @property uint alignment() shared 3111 { 3112 return impl.alignment; 3113 } 3114 3115 /** 3116 Returns `impl.goodAllocSize(s)`. 3117 */ 3118 override size_t goodAllocSize(size_t s) shared 3119 { 3120 return impl.goodAllocSize(s); 3121 } 3122 3123 /** 3124 Returns `impl.allocate(s)`. 3125 */ 3126 override void[] allocate(size_t s, TypeInfo ti = null) shared 3127 { 3128 return impl.allocate(s); 3129 } 3130 3131 /** 3132 If `impl.alignedAllocate` exists, calls it and returns the result. 3133 Otherwise, always returns `null`. 3134 */ 3135 override void[] alignedAllocate(size_t s, uint a) shared 3136 { 3137 static if (hasMember!(Allocator, "alignedAllocate")) 3138 return impl.alignedAllocate(s, a); 3139 else 3140 return null; 3141 } 3142 3143 /** 3144 If `Allocator` implements `owns`, forwards to it. Otherwise, returns 3145 `Ternary.unknown`. 3146 */ 3147 override Ternary owns(void[] b) shared 3148 { 3149 static if (hasMember!(Allocator, "owns")) return impl.owns(b); 3150 else return Ternary.unknown; 3151 } 3152 3153 /// Returns $(D impl.expand(b, s)) if defined, `false` otherwise. 3154 override bool expand(ref void[] b, size_t s) shared 3155 { 3156 static if (hasMember!(Allocator, "expand")) 3157 return impl.expand(b, s); 3158 else 3159 return s == 0; 3160 } 3161 3162 /// Returns $(D impl.reallocate(b, s)). 3163 override bool reallocate(ref void[] b, size_t s) shared 3164 { 3165 return impl.reallocate(b, s); 3166 } 3167 3168 /// Forwards to `impl.alignedReallocate` if defined, `false` otherwise. 3169 bool alignedReallocate(ref void[] b, size_t s, uint a) shared 3170 { 3171 static if (!hasMember!(Allocator, "alignedAllocate")) 3172 { 3173 return false; 3174 } 3175 else 3176 { 3177 return impl.alignedReallocate(b, s, a); 3178 } 3179 } 3180 3181 // Undocumented for now 3182 Ternary resolveInternalPointer(const void* p, ref void[] result) shared 3183 { 3184 static if (hasMember!(Allocator, "resolveInternalPointer")) 3185 { 3186 return impl.resolveInternalPointer(p, result); 3187 } 3188 else 3189 { 3190 return Ternary.unknown; 3191 } 3192 } 3193 3194 /** 3195 If `impl.deallocate` is not defined, returns `false`. Otherwise it forwards 3196 the call. 3197 */ 3198 override bool deallocate(void[] b) shared 3199 { 3200 static if (hasMember!(Allocator, "deallocate")) 3201 { 3202 return impl.deallocate(b); 3203 } 3204 else 3205 { 3206 return false; 3207 } 3208 } 3209 3210 /** 3211 Calls `impl.deallocateAll()` and returns the result if defined, 3212 otherwise returns `false`. 3213 */ 3214 override bool deallocateAll() shared 3215 { 3216 static if (hasMember!(Allocator, "deallocateAll")) 3217 { 3218 return impl.deallocateAll(); 3219 } 3220 else 3221 { 3222 return false; 3223 } 3224 } 3225 3226 /** 3227 Forwards to `impl.empty()` if defined, otherwise returns `Ternary.unknown`. 3228 */ 3229 override Ternary empty() shared 3230 { 3231 static if (hasMember!(Allocator, "empty")) 3232 { 3233 return Ternary(impl.empty); 3234 } 3235 else 3236 { 3237 return Ternary.unknown; 3238 } 3239 } 3240 3241 /** 3242 Returns `impl.allocateAll()` if present, `null` otherwise. 3243 */ 3244 override void[] allocateAll() shared 3245 { 3246 static if (hasMember!(Allocator, "allocateAll")) 3247 { 3248 return impl.allocateAll(); 3249 } 3250 else 3251 { 3252 return null; 3253 } 3254 } 3255 3256 @nogc nothrow pure @safe 3257 override void incRef() shared 3258 { 3259 static if (stateSize!Allocator) atomicOp!"+="(rc, 1); 3260 } 3261 3262 @nogc nothrow pure @trusted 3263 override bool decRef() shared 3264 { 3265 static if (stateSize!Allocator) 3266 { 3267 import core.stdc..string : memcpy; 3268 3269 // rc starts as 1 to avoid comparing with size_t(0) - 1 3270 if (atomicOp!"-="(rc, 1) == 0) 3271 { 3272 static if (indirect) 3273 { 3274 Allocator* tmp = pimpl; 3275 } 3276 else 3277 { 3278 Allocator tmp; 3279 memcpy(cast(void*) &tmp, cast(void*) &this.impl, Allocator.sizeof); 3280 Allocator empty; 3281 memcpy(cast(void*) &this.impl, cast(void*) &empty, Allocator.sizeof); 3282 } 3283 void[] support = (cast(void*) this)[0 .. stateSize!(typeof(this))]; 3284 (cast(bool delegate(void[]) @nogc nothrow pure)(&tmp.deallocate))(support); 3285 return false; 3286 } 3287 return true; 3288 } 3289 else 3290 { 3291 return true; 3292 } 3293 } 3294 } 3295 3296 3297 // Example in intro above 3298 @system unittest 3299 { 3300 // Allocate an int, initialize it with 42 3301 int* p = theAllocator.make!int(42); 3302 assert(*p == 42); 3303 3304 // Destroy and deallocate it 3305 theAllocator.dispose(p); 3306 3307 // Allocate using the global process allocator 3308 p = processAllocator.make!int(100); 3309 assert(*p == 100); 3310 3311 // Destroy and deallocate 3312 processAllocator.dispose(p); 3313 3314 // Create an array of 50 doubles initialized to -1.0 3315 double[] arr = theAllocator.makeArray!double(50, -1.0); 3316 3317 // Check internal pointer 3318 void[] result; 3319 assert(theAllocator.resolveInternalPointer(null, result) == Ternary.no); 3320 Ternary r = theAllocator.resolveInternalPointer(arr.ptr, result); 3321 assert(result.ptr is arr.ptr && result.length >= arr.length); 3322 3323 // Append two zeros to it 3324 theAllocator.expandArray(arr, 2, 0.0); 3325 // On second thought, take that back 3326 theAllocator.shrinkArray(arr, 2); 3327 // Destroy and deallocate 3328 theAllocator.dispose(arr); 3329 } 3330 3331 __EOF__ 3332 3333 /** 3334 3335 Stores an allocator object in thread-local storage (i.e. non-`shared` D 3336 global). `ThreadLocal!A` is a subtype of `A` so it appears to implement 3337 `A`'s allocator primitives. 3338 3339 `A` must hold state, otherwise `ThreadLocal!A` refuses instantiation. This 3340 means e.g. `ThreadLocal!Mallocator` does not work because `Mallocator`'s 3341 state is not stored as members of `Mallocator`, but instead is hidden in the 3342 C library implementation. 3343 3344 */ 3345 struct ThreadLocal(A) 3346 { 3347 static assert(stateSize!A, 3348 typeof(A).stringof 3349 ~ " does not have state so it cannot be used with ThreadLocal"); 3350 3351 /** 3352 The allocator instance. 3353 */ 3354 static A instance; 3355 3356 /** 3357 `ThreadLocal!A` is a subtype of `A` so it appears to implement `A`'s 3358 allocator primitives. 3359 */ 3360 alias instance this; 3361 3362 /** 3363 `ThreadLocal` disables all constructors. The intended usage is 3364 `ThreadLocal!A.instance`. 3365 */ 3366 @disable this(); 3367 /// Ditto 3368 @disable this(this); 3369 } 3370 3371 /// 3372 unittest 3373 { 3374 import std.experimental.allocator.building_blocks.free_list : FreeList; 3375 import std.experimental.allocator.gc_allocator : GCAllocator; 3376 import std.experimental.allocator.mallocator : Mallocator; 3377 3378 static assert(!is(ThreadLocal!Mallocator)); 3379 static assert(!is(ThreadLocal!GCAllocator)); 3380 alias ThreadLocal!(FreeList!(GCAllocator, 0, 8)) Allocator; 3381 auto b = Allocator.instance.allocate(5); 3382 static assert(hasMember!(Allocator, "allocate")); 3383 } 3384 3385 /* 3386 (Not public.) 3387 3388 A binary search tree that uses no allocation of its own. Instead, it relies on 3389 user code to allocate nodes externally. Then `EmbeddedTree`'s primitives wire 3390 the nodes appropriately. 3391 3392 Warning: currently `EmbeddedTree` is not using rebalancing, so it may 3393 degenerate. A red-black tree implementation storing the color with one of the 3394 pointers is planned for the future. 3395 */ 3396 private struct EmbeddedTree(T, alias less) 3397 { 3398 static struct Node 3399 { 3400 T payload; 3401 Node* left, right; 3402 } 3403 3404 private Node* root; 3405 3406 private Node* insert(Node* n, ref Node* backref) 3407 { 3408 backref = n; 3409 n.left = n.right = null; 3410 return n; 3411 } 3412 3413 Node* find(Node* data) 3414 { 3415 for (auto n = root; n; ) 3416 { 3417 if (less(data, n)) 3418 { 3419 n = n.left; 3420 } 3421 else if (less(n, data)) 3422 { 3423 n = n.right; 3424 } 3425 else 3426 { 3427 return n; 3428 } 3429 } 3430 return null; 3431 } 3432 3433 Node* insert(Node* data) 3434 { 3435 if (!root) 3436 { 3437 root = data; 3438 data.left = data.right = null; 3439 return root; 3440 } 3441 auto n = root; 3442 for (;;) 3443 { 3444 if (less(data, n)) 3445 { 3446 if (!n.left) 3447 { 3448 // Found insertion point 3449 return insert(data, n.left); 3450 } 3451 n = n.left; 3452 } 3453 else if (less(n, data)) 3454 { 3455 if (!n.right) 3456 { 3457 // Found insertion point 3458 return insert(data, n.right); 3459 } 3460 n = n.right; 3461 } 3462 else 3463 { 3464 // Found 3465 return n; 3466 } 3467 if (!n) return null; 3468 } 3469 } 3470 3471 Node* remove(Node* data) 3472 { 3473 auto n = root; 3474 Node* parent = null; 3475 for (;;) 3476 { 3477 if (!n) return null; 3478 if (less(data, n)) 3479 { 3480 parent = n; 3481 n = n.left; 3482 } 3483 else if (less(n, data)) 3484 { 3485 parent = n; 3486 n = n.right; 3487 } 3488 else 3489 { 3490 // Found 3491 remove(n, parent); 3492 return n; 3493 } 3494 } 3495 } 3496 3497 private void remove(Node* n, Node* parent) 3498 { 3499 assert(n); 3500 assert(!parent || parent.left == n || parent.right == n); 3501 Node** referrer = parent 3502 ? (parent.left == n ? &parent.left : &parent.right) 3503 : &root; 3504 if (!n.left) 3505 { 3506 *referrer = n.right; 3507 } 3508 else if (!n.right) 3509 { 3510 *referrer = n.left; 3511 } 3512 else 3513 { 3514 // Find the leftmost child in the right subtree 3515 auto leftmost = n.right; 3516 Node** leftmostReferrer = &n.right; 3517 while (leftmost.left) 3518 { 3519 leftmostReferrer = &leftmost.left; 3520 leftmost = leftmost.left; 3521 } 3522 // Unlink leftmost from there 3523 *leftmostReferrer = leftmost.right; 3524 // Link leftmost in lieu of n 3525 leftmost.left = n.left; 3526 leftmost.right = n.right; 3527 *referrer = leftmost; 3528 } 3529 } 3530 3531 Ternary empty() const 3532 { 3533 return Ternary(!root); 3534 } 3535 3536 void dump() 3537 { 3538 import std.stdio; 3539 writeln(typeid(this), " @ ", cast(void*) &this); 3540 dump(root, 3); 3541 } 3542 3543 void dump(Node* r, uint indent) 3544 { 3545 import std.stdio; 3546 import std.range : repeat; 3547 import std.array : array; 3548 3549 write(repeat(' ', indent).array); 3550 if (!r) 3551 { 3552 writeln("(null)"); 3553 return; 3554 } 3555 writeln(r.payload, " @ ", cast(void*) r); 3556 dump(r.left, indent + 3); 3557 dump(r.right, indent + 3); 3558 } 3559 3560 void assertSane() 3561 { 3562 static bool isBST(Node* r, Node* lb, Node* ub) 3563 { 3564 if (!r) return true; 3565 if (lb && !less(lb, r)) return false; 3566 if (ub && !less(r, ub)) return false; 3567 return isBST(r.left, lb, r) && 3568 isBST(r.right, r, ub); 3569 } 3570 if (isBST(root, null, null)) return; 3571 dump; 3572 assert(0); 3573 } 3574 } 3575 3576 unittest 3577 { 3578 import std.experimental.allocator.gc_allocator : GCAllocator; 3579 3580 alias a = GCAllocator.instance; 3581 alias Tree = EmbeddedTree!(int, (a, b) => a.payload < b.payload); 3582 Tree t; 3583 assert(t.empty == Ternary.yes); 3584 int[] vals = [ 6, 3, 9, 1, 0, 2, 8, 11 ]; 3585 foreach (v; vals) 3586 { 3587 auto n = new Tree.Node(v, null, null); 3588 assert(t.insert(n)); 3589 assert(n); 3590 t.assertSane; 3591 } 3592 assert(t.empty != Ternary.yes); 3593 foreach (v; vals) 3594 { 3595 Tree.Node n = { v }; 3596 assert(t.remove(&n)); 3597 t.assertSane; 3598 } 3599 assert(t.empty == Ternary.yes); 3600 } 3601 3602 /* 3603 3604 `InternalPointersTree` adds a primitive on top of another allocator: calling 3605 `resolveInternalPointer(p)` returns the block within which the internal 3606 pointer `p` lies. Pointers right after the end of allocated blocks are also 3607 considered internal. 3608 3609 The implementation stores three additional words with each allocation (one for 3610 the block size and two for search management). 3611 3612 */ 3613 private struct InternalPointersTree(Allocator) 3614 { 3615 import std.experimental.allocator.building_blocks.affix_allocator : AffixAllocator; 3616 3617 alias Tree = EmbeddedTree!(size_t, 3618 (a, b) => cast(void*) a + a.payload < cast(void*) b); 3619 alias Parent = AffixAllocator!(Allocator, Tree.Node); 3620 3621 // Own state 3622 private Tree blockMap; 3623 3624 alias alignment = Parent.alignment; 3625 3626 /** 3627 The implementation is available as a public member. 3628 */ 3629 static if (stateSize!Parent) Parent parent; 3630 else alias parent = Parent.instance; 3631 3632 /// Allocator API. 3633 void[] allocate(size_t bytes) 3634 { 3635 auto r = parent.allocate(bytes); 3636 if (!r.ptr) return r; 3637 Tree.Node* n = &parent.prefix(r); 3638 n.payload = bytes; 3639 blockMap.insert(n) || assert(0); 3640 return r; 3641 } 3642 3643 /// Ditto 3644 bool deallocate(void[] b) 3645 { 3646 if (!b.ptr) return true; 3647 Tree.Node* n = &parent.prefix(b); 3648 blockMap.remove(n) || assert(false); 3649 parent.deallocate(b); 3650 return true; 3651 } 3652 3653 /// Ditto 3654 static if (hasMember!(Allocator, "reallocate")) 3655 bool reallocate(ref void[] b, size_t s) 3656 { 3657 auto n = &parent.prefix(b); 3658 assert(n.payload == b.length); 3659 blockMap.remove(n) || assert(0); 3660 if (!parent.reallocate(b, s)) 3661 { 3662 // Failed, must reinsert the same node in the tree 3663 assert(n.payload == b.length); 3664 blockMap.insert(n) || assert(0); 3665 return false; 3666 } 3667 // Insert the new node 3668 n = &parent.prefix(b); 3669 n.payload = s; 3670 blockMap.insert(n) || assert(0); 3671 return true; 3672 } 3673 3674 /// Ditto 3675 Ternary owns(void[] b) 3676 { 3677 void[] result; 3678 return resolveInternalPointer(b.ptr, result); 3679 } 3680 3681 /// Ditto 3682 Ternary empty() 3683 { 3684 return Ternary(blockMap.empty); 3685 } 3686 3687 /** Returns the block inside which `p` resides, or `null` if the 3688 pointer does not belong. 3689 */ 3690 pure nothrow @safe @nogc 3691 Ternary resolveInternalPointer(const void* p, ref void[] result) 3692 { 3693 // Must define a custom find 3694 Tree.Node* find() 3695 { 3696 for (auto n = blockMap.root; n; ) 3697 { 3698 if (p < n) 3699 { 3700 n = n.left; 3701 } 3702 else if ((() @trusted => p > (cast(void*) (n + 1)) + n.payload)()) 3703 { 3704 n = n.right; 3705 } 3706 else 3707 { 3708 return n; 3709 } 3710 } 3711 return null; 3712 } 3713 3714 auto n = find(); 3715 if (!n) return Ternary.no; 3716 result = (() @trusted => (cast(void*) (n + 1))[0 .. n.payload])(); 3717 return Ternary.yes; 3718 } 3719 } 3720 3721 unittest 3722 { 3723 import std.experimental.allocator.mallocator : Mallocator; 3724 import std.random : randomCover; 3725 3726 InternalPointersTree!(Mallocator) a; 3727 int[] vals = [ 6, 3, 9, 1, 2, 8, 11 ]; 3728 void[][] allox; 3729 foreach (v; vals) 3730 { 3731 allox ~= a.allocate(v); 3732 } 3733 a.blockMap.assertSane; 3734 3735 foreach (b; allox) 3736 { 3737 () pure nothrow @safe { 3738 void[] p; 3739 Ternary r = (() @nogc => a.resolveInternalPointer(&b[0], p))(); 3740 assert(&p[0] == &b[0] && p.length >= b.length); 3741 r = a.resolveInternalPointer((() @trusted => &b[0] + b.length)(), p); 3742 assert(&p[0] == &b[0] && p.length >= b.length); 3743 r = a.resolveInternalPointer((() @trusted => &b[0] + b.length / 2)(), p); 3744 assert(&p[0] == &b[0] && p.length >= b.length); 3745 auto bogus = new void[b.length]; 3746 assert(a.resolveInternalPointer(&bogus[0], p) == Ternary.no); 3747 }(); 3748 } 3749 3750 foreach (b; allox.randomCover) 3751 { 3752 () nothrow @nogc { a.deallocate(b); }(); 3753 } 3754 3755 assert(a.empty == Ternary.yes); 3756 } 3757 3758 //version (std_allocator_benchmark) 3759 unittest 3760 { 3761 import std.experimental.allocator.building_blocks.null_allocator : NullAllocator; 3762 import std.experimental.allocator.building_blocks.allocator_list : AllocatorList; 3763 import std.experimental.allocator.building_blocks.bitmapped_block : BitmappedBlock; 3764 import std.experimental.allocator.building_blocks.segregator : Segregator; 3765 import std.experimental.allocator.building_blocks.bucketizer : Bucketizer; 3766 import std.experimental.allocator.building_blocks.free_list : FreeList; 3767 import std.experimental.allocator.gc_allocator : GCAllocator; 3768 import std.experimental.allocator.mallocator : Mallocator; 3769 3770 static void testSpeed(A)() 3771 { 3772 static if (stateSize!A) A a; 3773 else alias a = A.instance; 3774 3775 void[][128] bufs; 3776 3777 import std.random; 3778 foreach (i; 0 .. 100_000) 3779 { 3780 auto j = uniform(0, bufs.length); 3781 switch (uniform(0, 2)) 3782 { 3783 case 0: 3784 () nothrow @nogc { a.deallocate(bufs[j]); }(); 3785 bufs[j] = a.allocate(uniform(0, 4096)); 3786 break; 3787 case 1: 3788 () nothrow @nogc { a.deallocate(bufs[j]); }(); 3789 bufs[j] = null; 3790 break; 3791 default: 3792 assert(0); 3793 } 3794 } 3795 } 3796 3797 import std.algorithm.comparison : max; 3798 3799 alias FList = FreeList!(GCAllocator, 0, unbounded); 3800 alias A = Segregator!( 3801 8, FreeList!(GCAllocator, 0, 8), 3802 128, Bucketizer!(FList, 1, 128, 16), 3803 256, Bucketizer!(FList, 129, 256, 32), 3804 512, Bucketizer!(FList, 257, 512, 64), 3805 1024, Bucketizer!(FList, 513, 1024, 128), 3806 2048, Bucketizer!(FList, 1025, 2048, 256), 3807 3584, Bucketizer!(FList, 2049, 3584, 512), 3808 4072 * 1024, AllocatorList!( 3809 (size_t n) => BitmappedBlock!(4096)(cast(ubyte[]) GCAllocator.instance.allocate( 3810 max(n, 4072 * 1024)))), 3811 GCAllocator 3812 ); 3813 3814 import std.stdio; 3815 import std.conv : to; 3816 import std.datetime.stopwatch; 3817 import std.algorithm.iteration : map; 3818 3819 if (false) writeln(benchmark!( 3820 testSpeed!NullAllocator, 3821 testSpeed!Mallocator, 3822 testSpeed!GCAllocator, 3823 testSpeed!(ThreadLocal!A), 3824 testSpeed!(A), 3825 )(20)[].map!(t => t.to!Duration)); 3826 } 3827 3828 unittest 3829 { 3830 import std.experimental.allocator.building_blocks.free_list : FreeList; 3831 import std.experimental.allocator.building_blocks.region : InSituRegion; 3832 import std.experimental.allocator.building_blocks.fallback_allocator : FallbackAllocator; 3833 import std.experimental.allocator.gc_allocator : GCAllocator; 3834 import std.experimental.allocator.mallocator : Mallocator; 3835 3836 auto a = allocatorObject(Mallocator.instance); 3837 auto b = a.allocate(100); 3838 assert(b.length == 100); 3839 3840 FreeList!(GCAllocator, 0, 8) fl; 3841 auto sa = allocatorObject(fl); 3842 b = a.allocate(101); 3843 assert(b.length == 101); 3844 3845 FallbackAllocator!(InSituRegion!(10240, 64), GCAllocator) fb; 3846 // Doesn't work yet... 3847 //a = allocatorObject(fb); 3848 //b = a.allocate(102); 3849 //assert(b.length == 102); 3850 } 3851 3852 /// 3853 unittest 3854 { 3855 import std.experimental.allocator.building_blocks.allocator_list : AllocatorList; 3856 import std.experimental.allocator.building_blocks.bitmapped_block : BitmappedBlock; 3857 import std.experimental.allocator.building_blocks.segregator : Segregator; 3858 import std.experimental.allocator.building_blocks.bucketizer : Bucketizer; 3859 import std.experimental.allocator.building_blocks.free_list : FreeList; 3860 import std.experimental.allocator.gc_allocator : GCAllocator; 3861 3862 /// Define an allocator bound to the built-in GC. 3863 IAllocator alloc = allocatorObject(GCAllocator.instance); 3864 auto b = alloc.allocate(42); 3865 assert(b.length == 42); 3866 assert(alloc.deallocate(b)); 3867 3868 import std.algorithm.comparison : max; 3869 // Define an elaborate allocator and bind it to the class API. 3870 alias FList = FreeList!(GCAllocator, 0, unbounded); 3871 alias A = ThreadLocal!( 3872 Segregator!( 3873 8, FreeList!(GCAllocator, 0, 8), 3874 128, Bucketizer!(FList, 1, 128, 16), 3875 256, Bucketizer!(FList, 129, 256, 32), 3876 512, Bucketizer!(FList, 257, 512, 64), 3877 1024, Bucketizer!(FList, 513, 1024, 128), 3878 2048, Bucketizer!(FList, 1025, 2048, 256), 3879 3584, Bucketizer!(FList, 2049, 3584, 512), 3880 4072 * 1024, AllocatorList!( 3881 (n) => BitmappedBlock!(4096)(cast(ubyte[]) GCAllocator.instance.allocate( 3882 max(n, 4072 * 1024)))), 3883 GCAllocator 3884 ) 3885 ); 3886 3887 auto alloc2 = allocatorObject(A.instance); 3888 b = alloc2.allocate(101); 3889 assert(alloc2.deallocate(b)); 3890 }