The OpenD Programming Language

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