"Fossies" - the Fresh Open Source Software Archive

Member "dmd2/src/phobos/std/experimental/allocator/package.d" (20 Nov 2020, 109310 Bytes) of package /linux/misc/dmd.2.094.2.linux.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) D source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    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, &reg);
  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 }