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