1 // Written in the D programming language.
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.
9 $(SCRIPT inhibitQuickIndex = 1;)
11 $(TR $(TH Category) $(TH Functions))
15 $(LREF makeMultidimensionalArray)
17 $(TR $(TD Dispose) $(TD
19 $(LREF disposeMultidimensionalArray)
21 $(TR $(TD Modify) $(TD
25 $(TR $(TD Global) $(TD
26 $(LREF processAllocator)
29 $(TR $(TD Class interface) $(TD
30 $(LREF allocatorObject)
31 $(LREF CAllocatorImpl)
38 // Allocate an int, initialize it with 42
39 int* p = theAllocator.make!int(42);
41 // Destroy and deallocate it
42 theAllocator.dispose(p);
44 // Allocate using the global process allocator
45 p = processAllocator.make!int(100);
47 // Destroy and deallocate
48 processAllocator.dispose(p);
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);
60 $(H2 Layered Structure)
62 D's allocators have a layered structure in both implementation and documentation:
65 $(LI A high-level, dynamically-typed layer (described further down in this
66 module). It consists of an interface called $(LREF IAllocator), which concrete
67 allocators need to implement. The interface primitives themselves are oblivious
68 to the type of the objects being allocated; they only deal in `void[]`, by
69 necessity of the interface being dynamic (as opposed to type-parameterized).
70 Each thread has a current allocator it uses by default, which is a thread-local
71 variable $(LREF theAllocator) of type $(LREF IAllocator). The process has a
72 global allocator called $(LREF processAllocator), also of type $(LREF
73 IAllocator). When a new thread is created, $(LREF processAllocator) is copied
74 into $(LREF theAllocator). An application can change the objects to which these
75 references point. By default, at application startup, $(LREF processAllocator)
76 refers to an object that uses D's garbage collected heap. This layer also
77 include high-level functions such as $(LREF make) and $(LREF dispose) that
78 comfortably allocate/create and respectively destroy/deallocate objects. This
79 layer is all needed for most casual uses of allocation primitives.)
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.)
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).)
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.)
110 $(H2 Idiomatic Use of `std.experimental.allocator`)
112 As of this time, `std.experimental.allocator` is not integrated with D's
113 built-in operators that allocate memory, such as `new`, array literals, or
114 array concatenation operators. That means `std.experimental.allocator` is
115 opt-in$(MDASH)applications need to make explicit use of it.
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:
127 // Use the current allocator
128 int[] a1 = theAllocator.makeArray!int(n);
129 scope(exit) theAllocator.dispose(a1);
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:
144 import std.experimental.allocator.building_blocks.free_list
146 theAllocator = allocatorObject(FreeList!8());
151 $(H3 Saving the `IAllocator` Reference For Later Use)
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.
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:
168 private IAllocator allocator;
169 this(size_t buckets, IAllocator allocator = theAllocator) {
170 this.allocator = allocator;
174 IAllocator allocator() { return allocator; }
175 void allocator(IAllocator a) { assert(empty); allocator = a; }
179 Following initialization, the `HashTable` object would consistently use its
180 `allocator` object for acquiring memory. Furthermore, setting
181 `HashTable.allocator` to point to a different allocator should be legal but
182 only if the object is empty; otherwise, the object wouldn't be able to
183 deallocate its existing state.
185 $(H3 Using Allocators without `IAllocator`)
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:
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);
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
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.
214 Copyright: Andrei Alexandrescu 2013-.
216 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
218 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
220 Source: $(PHOBOSSRC std/experimental/allocator)
224 module std.experimental.allocator;
226 public import std.experimental.allocator.common,
227 std.experimental.allocator.typed;
229 // Fix https://issues.dlang.org/show_bug.cgi?id=17806
230 // this should always be the first unittest in this module in order to ensure
231 // that we use the `processAllocator` setter before the getter
234 import std.experimental.allocator.mallocator : Mallocator;
235 import std.experimental.allocator.gc_allocator : GCAllocator;
236 auto newAlloc = sharedAllocatorObject(Mallocator.instance);
237 processAllocator = newAlloc;
238 assert(processAllocator is newAlloc);
239 processAllocator = sharedAllocatorObject(GCAllocator.instance);
242 // Example in the synopsis above
245 import std.algorithm.comparison : min, max;
246 import std.experimental.allocator.building_blocks.allocator_list
248 import std.experimental.allocator.building_blocks.bitmapped_block
250 import std.experimental.allocator.building_blocks.bucketizer : Bucketizer;
251 import std.experimental.allocator.building_blocks.free_list : FreeList;
252 import std.experimental.allocator.building_blocks.segregator : Segregator;
253 import std.experimental.allocator.gc_allocator : GCAllocator;
255 alias FList = FreeList!(GCAllocator, 0, unbounded);
256 alias A = Segregator!(
257 8, FreeList!(GCAllocator, 0, 8),
258 128, Bucketizer!(FList, 1, 128, 16),
259 256, Bucketizer!(FList, 129, 256, 32),
260 512, Bucketizer!(FList, 257, 512, 64),
261 1024, Bucketizer!(FList, 513, 1024, 128),
262 2048, Bucketizer!(FList, 1025, 2048, 256),
263 3584, Bucketizer!(FList, 2049, 3584, 512),
264 4072 * 1024, AllocatorList!(
265 (n) => BitmappedBlock!(4096)(
266 cast(ubyte[])(GCAllocator.instance.allocate(
267 max(n, 4072 * 1024))))),
271 auto b = tuMalloc.allocate(500);
272 assert(b.length == 500);
273 auto c = tuMalloc.allocate(113);
274 assert(c.length == 113);
275 assert(tuMalloc.expand(c, 14));
276 tuMalloc.deallocate(b);
277 tuMalloc.deallocate(c);
280 import std.range.primitives;
285 Dynamic allocator interface. Code that defines allocators ultimately implements
286 this interface. This should be used wherever a uniform type is required for
287 encapsulating various allocator implementations.
289 Composition of allocators is not recommended at this level due to
290 inflexibility of dynamic interfaces and inefficiencies caused by cascaded
291 multiple calls. Instead, compose allocators using the static interface defined
292 in $(MREF std,experimental,allocator,building_blocks),
293 then adapt the composed
294 allocator to `IAllocator` (possibly by using $(LREF CAllocatorImpl) below).
296 Methods returning `Ternary` return `Ternary.yes` upon success,
297 `Ternary.no` upon failure, and `Ternary.unknown` if the primitive is not
298 implemented by the allocator instance.
304 Returns the alignment offered.
306 @property uint alignment();
309 Returns the good allocation size that guarantees zero internal
312 size_t goodAllocSize(size_t s);
315 Allocates `n` bytes of memory.
317 void[] allocate(size_t, TypeInfo ti = null);
320 Allocates `n` bytes of memory with specified alignment `a`. Implementations
321 that do not support this primitive should always return `null`.
323 void[] alignedAllocate(size_t n, uint a);
326 Allocates and returns all memory available to this allocator.
327 Implementations that do not support this primitive should always return
330 void[] allocateAll();
333 Expands a memory block in place and returns `true` if successful.
334 Implementations that don't support this primitive should always return
337 bool expand(ref void[], size_t);
339 /// Reallocates a memory block.
340 bool reallocate(ref void[], size_t);
342 /// Reallocates a memory block with specified alignment.
343 bool alignedReallocate(ref void[] b, size_t size, uint alignment);
346 Returns `Ternary.yes` if the allocator owns `b`, `Ternary.no` if
347 the allocator doesn't own `b`, and `Ternary.unknown` if ownership
348 cannot be determined. Implementations that don't support this primitive
349 should always return `Ternary.unknown`.
351 Ternary owns(void[] b);
354 Resolves an internal pointer to the full block allocated. Implementations
355 that don't support this primitive should always return `Ternary.unknown`.
357 Ternary resolveInternalPointer(const void* p, ref void[] result);
360 Deallocates a memory block. Implementations that don't support this
361 primitive should always return `false`. A simple way to check that an
362 allocator supports deallocation is to call `deallocate(null)`.
364 bool deallocate(void[] b);
367 Deallocates all memory. Implementations that don't support this primitive
368 should always return `false`.
370 bool deallocateAll();
373 Returns `Ternary.yes` if no memory is currently allocated from this
374 allocator, `Ternary.no` if some allocations are currently active, or
375 `Ternary.unknown` if not supported.
380 Increases the reference count of the concrete class that implements this
383 For stateless allocators, this does nothing.
389 Decreases the reference count of the concrete class that implements this
391 When the reference count is `0`, the object self-destructs.
393 Returns: `true` if the reference count is greater than `0` and `false` when
394 it hits `0`. For stateless allocators, it always returns `true`.
401 A reference counted struct that wraps the dynamic allocator interface.
402 This should be used wherever a uniform type is required for encapsulating
403 various allocator implementations.
405 Code that defines allocators ultimately implements the $(LREF IAllocator)
406 interface, possibly by using $(LREF CAllocatorImpl) below, and then build a
407 `RCIAllocator` out of this.
409 Composition of allocators is not recommended at this level due to
410 inflexibility of dynamic interfaces and inefficiencies caused by cascaded
411 multiple calls. Instead, compose allocators using the static interface defined
412 in $(A std_experimental_allocator_building_blocks.html,
413 `std.experimental.allocator.building_blocks`), then adapt the composed
414 allocator to `RCIAllocator` (possibly by using $(LREF allocatorObject) below).
418 private IAllocator _alloc;
421 private @nogc pure @safe
422 this(this _)(IAllocator alloc)
442 bool isLast = !_alloc.decRef();
443 if (isLast) _alloc = null;
448 auto ref opAssign()(typeof(this) rhs)
450 if (_alloc is rhs._alloc)
454 // incRef was allready called by rhs posblit, so we're just moving
455 // calling dtor is the equivalent of decRef
464 bool isNull(this _)()
466 return _alloc is null;
469 @property uint alignment()
472 return _alloc.alignment();
475 size_t goodAllocSize(size_t s)
478 return _alloc.goodAllocSize(s);
481 void[] allocate(size_t n, TypeInfo ti = null)
484 return _alloc.allocate(n, ti);
487 void[] alignedAllocate(size_t n, uint a)
490 return _alloc.alignedAllocate(n, a);
496 return _alloc.allocateAll();
499 bool expand(ref void[] b, size_t size)
502 return _alloc.expand(b, size);
505 bool reallocate(ref void[] b, size_t size)
508 return _alloc.reallocate(b, size);
511 bool alignedReallocate(ref void[] b, size_t size, uint alignment)
514 return _alloc.alignedReallocate(b, size, alignment);
517 Ternary owns(void[] b)
520 return _alloc.owns(b);
523 Ternary resolveInternalPointer(const void* p, ref void[] result)
526 return _alloc.resolveInternalPointer(p, result);
529 bool deallocate(void[] b)
532 return _alloc.deallocate(b);
538 return _alloc.deallocateAll();
544 return _alloc.empty();
550 import std.experimental.allocator.building_blocks.region : Region;
551 import std.conv : emplace;
553 auto reg = Region!()(new ubyte[1024]);
554 auto state = reg.allocate(stateSize!(CAllocatorImpl!(Region!(), Yes.indirect)));
555 auto regObj = emplace!(CAllocatorImpl!(Region!(), Yes.indirect))(state, ®);
557 auto rcalloc = RCIAllocator(regObj);
558 auto b = rcalloc.allocate(10);
559 assert(b.length == 10);
561 // The reference counting is zero based
562 assert((cast(CAllocatorImpl!(Region!(), Yes.indirect))(rcalloc._alloc)).rc == 1);
565 assert((cast(CAllocatorImpl!(Region!(), Yes.indirect))(rcalloc._alloc)).rc == 2);
567 assert((cast(CAllocatorImpl!(Region!(), Yes.indirect))(rcalloc._alloc)).rc == 1);
573 import std.experimental.allocator.mallocator;
574 import std.experimental.allocator.building_blocks.stats_collector;
576 alias SCAlloc = StatsCollector!(Mallocator, Options.bytesUsed);
577 SCAlloc statsCollectorAlloc;
579 ulong bytesUsed = statsCollectorAlloc.bytesUsed;
580 assert(bytesUsed == 0);
583 auto _allocator = allocatorObject(&statsCollectorAlloc);
584 bytesUsed = statsCollectorAlloc.bytesUsed;
585 assert(bytesUsed == stateSize!(CAllocatorImpl!(SCAlloc, Yes.indirect)));
588 bytesUsed = statsCollectorAlloc.bytesUsed;
589 assert(bytesUsed == 0, "RCIAllocator leaks memory; leaked "
590 ~ to!string(bytesUsed) ~ " bytes");
596 import std.experimental.allocator.mallocator;
597 import std.experimental.allocator.building_blocks.stats_collector;
599 alias SCAlloc = StatsCollector!(Mallocator, Options.bytesUsed);
600 SCAlloc statsCollectorAlloc;
602 ulong bytesUsed = statsCollectorAlloc.bytesUsed;
603 assert(bytesUsed == 0);
606 auto _allocator = allocatorObject(statsCollectorAlloc);
608 // Ensure that the allocator was passed through in CAllocatorImpl
609 // This allocator was used to allocate the chunk that holds the
610 // CAllocatorImpl object; which is it's own wrapper
611 bytesUsed = (cast(CAllocatorImpl!(SCAlloc))(_allocator._alloc)).impl.bytesUsed;
612 assert(bytesUsed == stateSize!(CAllocatorImpl!(SCAlloc)),
613 "RCIAllocator leaks memory; leaked " ~ to!string(bytesUsed) ~ " bytes");
614 _allocator.allocate(1);
615 bytesUsed = (cast(CAllocatorImpl!(SCAlloc))(_allocator._alloc)).impl.bytesUsed;
616 assert(bytesUsed == stateSize!(CAllocatorImpl!(SCAlloc)) + 1,
617 "RCIAllocator leaks memory; leaked " ~ to!string(bytesUsed) ~ " bytes");
620 bytesUsed = statsCollectorAlloc.bytesUsed;
621 assert(bytesUsed == stateSize!(CAllocatorImpl!(SCAlloc)),
622 "RCIAllocator leaks memory; leaked "
623 ~ to!string(bytesUsed) ~ " bytes");
627 Dynamic shared allocator interface. Code that defines allocators shareable
628 across threads ultimately implements this interface. This should be used
629 wherever a uniform type is required for encapsulating various allocator
632 Composition of allocators is not recommended at this level due to
633 inflexibility of dynamic interfaces and inefficiencies caused by cascaded
634 multiple calls. Instead, compose allocators using the static interface defined
635 in $(MREF std,experimental,allocator,building_blocks),
636 then adapt the composed
637 allocator to `ISharedAllocator` (possibly by using $(LREF CSharedAllocatorImpl) below).
639 Methods returning `Ternary` return `Ternary.yes` upon success,
640 `Ternary.no` upon failure, and `Ternary.unknown` if the primitive is not
641 implemented by the allocator instance.
643 interface ISharedAllocator
647 Returns the alignment offered.
649 @property uint alignment() shared;
652 Returns the good allocation size that guarantees zero internal
655 size_t goodAllocSize(size_t s) shared;
658 Allocates `n` bytes of memory.
660 void[] allocate(size_t, TypeInfo ti = null) shared;
663 Allocates `n` bytes of memory with specified alignment `a`. Implementations
664 that do not support this primitive should always return `null`.
666 void[] alignedAllocate(size_t n, uint a) shared;
669 Allocates and returns all memory available to this allocator.
670 Implementations that do not support this primitive should always return
673 void[] allocateAll() shared;
676 Expands a memory block in place and returns `true` if successful.
677 Implementations that don't support this primitive should always return
680 bool expand(ref void[], size_t) shared;
682 /// Reallocates a memory block.
683 bool reallocate(ref void[], size_t) shared;
685 /// Reallocates a memory block with specified alignment.
686 bool alignedReallocate(ref void[] b, size_t size, uint alignment) shared;
689 Returns `Ternary.yes` if the allocator owns `b`, `Ternary.no` if
690 the allocator doesn't own `b`, and `Ternary.unknown` if ownership
691 cannot be determined. Implementations that don't support this primitive
692 should always return `Ternary.unknown`.
694 Ternary owns(void[] b) shared;
697 Resolves an internal pointer to the full block allocated. Implementations
698 that don't support this primitive should always return `Ternary.unknown`.
700 Ternary resolveInternalPointer(const void* p, ref void[] result) shared;
703 Deallocates a memory block. Implementations that don't support this
704 primitive should always return `false`. A simple way to check that an
705 allocator supports deallocation is to call `deallocate(null)`.
707 bool deallocate(void[] b) shared;
710 Deallocates all memory. Implementations that don't support this primitive
711 should always return `false`.
713 bool deallocateAll() shared;
716 Returns `Ternary.yes` if no memory is currently allocated from this
717 allocator, `Ternary.no` if some allocations are currently active, or
718 `Ternary.unknown` if not supported.
720 Ternary empty() shared;
723 Increases the reference count of the concrete class that implements this
726 For stateless allocators, this does nothing.
729 void incRef() shared;
732 Decreases the reference count of the concrete class that implements this
734 When the reference count is `0`, the object self-destructs.
736 For stateless allocators, this does nothing.
738 Returns: `true` if the reference count is greater than `0` and `false` when
739 it hits `0`. For stateless allocators, it always returns `true`.
742 bool decRef() shared;
746 A reference counted struct that wraps the dynamic shared allocator interface.
747 This should be used wherever a uniform type is required for encapsulating
748 various allocator implementations.
750 Code that defines allocators shareable across threads ultimately implements the
751 $(LREF ISharedAllocator) interface, possibly by using
752 $(LREF CSharedAllocatorImpl) below, and then build a `RCISharedAllocator` out
755 Composition of allocators is not recommended at this level due to
756 inflexibility of dynamic interfaces and inefficiencies caused by cascaded
757 multiple calls. Instead, compose allocators using the static interface defined
758 in $(A std_experimental_allocator_building_blocks.html,
759 `std.experimental.allocator.building_blocks`), then adapt the composed allocator
760 to `RCISharedAllocator` (possibly by using $(LREF sharedAllocatorObject) below).
762 shared struct RCISharedAllocator
764 private ISharedAllocator _alloc;
767 private @nogc pure @safe
768 this(shared ISharedAllocator alloc)
788 bool isLast = !_alloc.decRef();
789 if (isLast) _alloc = null;
794 auto ref opAssign()(RCISharedAllocator rhs)
796 if (_alloc is rhs._alloc)
800 // incRef was allready called by rhs posblit, so we're just moving
812 bool isNull(this _)()
814 return _alloc is null;
817 @property uint alignment()
820 return _alloc.alignment();
823 size_t goodAllocSize(size_t s)
826 return _alloc.goodAllocSize(s);
829 void[] allocate(size_t n, TypeInfo ti = null)
832 return _alloc.allocate(n, ti);
835 void[] alignedAllocate(size_t n, uint a)
838 return _alloc.alignedAllocate(n, a);
844 return _alloc.allocateAll();
847 bool expand(ref void[] b, size_t size)
850 return _alloc.expand(b, size);
853 bool reallocate(ref void[] b, size_t size)
856 return _alloc.reallocate(b, size);
859 bool alignedReallocate(ref void[] b, size_t size, uint alignment)
862 return _alloc.alignedReallocate(b, size, alignment);
865 Ternary owns(void[] b)
868 return _alloc.owns(b);
871 Ternary resolveInternalPointer(const void* p, ref void[] result)
874 return _alloc.resolveInternalPointer(p, result);
877 bool deallocate(void[] b)
880 return _alloc.deallocate(b);
886 return _alloc.deallocateAll();
892 return _alloc.empty();
896 private RCISharedAllocator _processAllocator;
897 private RCIAllocator _threadAllocator;
900 private ref RCIAllocator setupThreadAllocator()
903 Forwards the `_threadAllocator` calls to the `processAllocator`
905 static class ThreadAllocator : IAllocator
908 private RCISharedAllocator _allocator;
911 this(ref RCISharedAllocator procAlloc)
913 _allocator = procAlloc;
916 override @property uint alignment()
918 return _allocator.alignment();
921 override size_t goodAllocSize(size_t s)
923 return _allocator.goodAllocSize(s);
926 override void[] allocate(size_t n, TypeInfo ti = null)
928 return _allocator.allocate(n, ti);
931 override void[] alignedAllocate(size_t n, uint a)
933 return _allocator.alignedAllocate(n, a);
936 override void[] allocateAll()
938 return _allocator.allocateAll();
941 override bool expand(ref void[] b, size_t size)
943 return _allocator.expand(b, size);
946 override bool reallocate(ref void[] b, size_t size)
948 return _allocator.reallocate(b, size);
951 override bool alignedReallocate(ref void[] b, size_t size, uint alignment)
953 return _allocator.alignedReallocate(b, size, alignment);
956 override Ternary owns(void[] b)
958 return _allocator.owns(b);
961 override Ternary resolveInternalPointer(const void* p, ref void[] result)
963 return _allocator.resolveInternalPointer(p, result);
966 override bool deallocate(void[] b)
968 return _allocator.deallocate(b);
971 override bool deallocateAll()
973 return _allocator.deallocateAll();
976 override Ternary empty()
978 return _allocator.empty();
982 override void incRef()
984 _allocator._alloc.incRef();
988 override bool decRef()
990 return _allocator._alloc.decRef();
994 assert(_threadAllocator.isNull);
995 import core.lifetime : emplace;
996 static ulong[stateSize!(ThreadAllocator).divideRoundUp(ulong.sizeof)] _threadAllocatorState;
998 _threadAllocator = RCIAllocator(emplace!(ThreadAllocator)(_threadAllocatorState[], processAllocator()));
1000 return _threadAllocator;
1003 // Fix threadAllocator bug: the threadAllocator should hold an internal reference
1004 // to the processAllocator that it's using
1007 import std.experimental.allocator.mallocator : Mallocator;
1009 auto a = sharedAllocatorObject(Mallocator.instance);
1010 auto buf = theAllocator.allocate(42);
1011 processAllocator = a;
1012 theAllocator.deallocate(buf);
1016 Gets/sets the allocator for the current thread. This is the default allocator
1017 that should be used for allocating thread-local memory. For allocating memory
1018 to be shared across threads, use `processAllocator` (below). By default,
1019 `theAllocator` ultimately fetches memory from `processAllocator`, which
1020 in turn uses the garbage collected heap.
1023 @property ref RCIAllocator theAllocator()
1025 alias p = _threadAllocator;
1026 return !p.isNull() ? p : setupThreadAllocator();
1030 nothrow @system @nogc
1031 @property void theAllocator(RCIAllocator a)
1034 _threadAllocator = a;
1040 // Install a new allocator that is faster for 128-byte allocations.
1041 import std.experimental.allocator.building_blocks.free_list : FreeList;
1042 import std.experimental.allocator.gc_allocator : GCAllocator;
1043 auto oldAllocator = theAllocator;
1044 scope(exit) theAllocator = oldAllocator;
1045 theAllocator = allocatorObject(FreeList!(GCAllocator, 128)());
1046 // Use the now changed allocator to allocate an array
1047 const ubyte[] arr = theAllocator.makeArray!ubyte(128);
1053 Gets/sets the allocator for the current process. This allocator must be used
1054 for allocating memory shared across threads. Objects created using this
1055 allocator can be cast to `shared`.
1057 @nogc nothrow @trusted
1058 @property ref RCISharedAllocator processAllocator()
1060 import std.experimental.allocator.gc_allocator : GCAllocator;
1061 import std.concurrency : initOnce;
1063 static RCISharedAllocator* forceAttributes()
1065 return &initOnce!_processAllocator(
1066 sharedAllocatorObject(GCAllocator.instance));
1069 return *(cast(RCISharedAllocator* function() @nogc nothrow)(&forceAttributes))();
1073 @nogc nothrow @system
1074 @property void processAllocator(ref RCISharedAllocator a)
1077 processAllocator() = a;
1082 import core.exception : AssertError;
1083 import std.exception : assertThrown;
1084 import std.experimental.allocator.building_blocks.free_list : SharedFreeList;
1085 import std.experimental.allocator.mallocator : Mallocator;
1087 assert(!processAllocator.isNull);
1088 assert(!theAllocator.isNull);
1090 testAllocatorObject(processAllocator);
1091 testAllocatorObject(theAllocator);
1093 shared SharedFreeList!(Mallocator, chooseAtRuntime, chooseAtRuntime) sharedFL;
1094 RCISharedAllocator sharedFLObj = sharedAllocatorObject(sharedFL);
1095 alias SharedAllocT = CSharedAllocatorImpl!(
1096 shared SharedFreeList!(
1097 Mallocator, chooseAtRuntime, chooseAtRuntime));
1099 assert((cast(SharedAllocT)(sharedFLObj._alloc)).rc == 1);
1100 assert(!sharedFLObj.isNull);
1101 testAllocatorObject(sharedFLObj);
1103 // Test processAllocator setter
1104 RCISharedAllocator oldProcessAllocator = processAllocator;
1105 processAllocator = sharedFLObj;
1106 assert((cast(SharedAllocT)(sharedFLObj._alloc)).rc == 2);
1107 assert(processAllocator._alloc is sharedFLObj._alloc);
1109 testAllocatorObject(processAllocator);
1110 testAllocatorObject(theAllocator);
1111 assertThrown!AssertError(processAllocator = RCISharedAllocator(null));
1113 // Restore initial processAllocator state
1114 processAllocator = oldProcessAllocator;
1115 assert((cast(SharedAllocT)(sharedFLObj._alloc)).rc == 1);
1116 assert(processAllocator is oldProcessAllocator);
1118 RCISharedAllocator indirectShFLObj = sharedAllocatorObject(&sharedFL);
1119 testAllocatorObject(indirectShFLObj);
1120 alias IndirectSharedAllocT = CSharedAllocatorImpl!(
1121 shared SharedFreeList!(
1122 Mallocator, chooseAtRuntime, chooseAtRuntime)
1125 assert((cast(IndirectSharedAllocT)(indirectShFLObj._alloc)).rc == 1);
1127 RCIAllocator indirectMallocator = allocatorObject(&Mallocator.instance);
1128 testAllocatorObject(indirectMallocator);
1132 Dynamically allocates (using `alloc`) and then creates in the memory
1133 allocated an object of type `T`, using `args` (if any) for its
1134 initialization. Initialization occurs in the memory allocated and is otherwise
1135 semantically the same as `T(args)`.
1136 (Note that using `alloc.make!(T[])` creates a pointer to an (empty) array
1137 of `T`s, not an array. To use an allocator to allocate and initialize an
1138 array, use `alloc.makeArray!T` described below.)
1141 T = Type of the object being created.
1142 alloc = The allocator used for getting the needed memory. It may be an object
1143 implementing the static interface for allocators, or an `IAllocator`
1145 args = Optional arguments used for initializing the created object. If not
1146 present, the object is default constructed.
1148 Returns: If `T` is a class type, returns a reference to the created `T`
1149 object. Otherwise, returns a `T*` pointing to the created object. In all
1150 cases, returns `null` if allocation failed.
1152 Throws: If `T`'s constructor throws, deallocates the allocated memory and
1153 propagates the exception.
1155 auto make(T, Allocator, A...)(auto ref Allocator alloc, auto ref A args)
1157 import std.algorithm.comparison : max;
1158 static if (!is(T == class) && !is(T == interface) && A.length == 0
1159 && __traits(compiles, {T t;}) && __traits(isZeroInit, T)
1160 && is(typeof(alloc.allocateZeroed(size_t.max))))
1162 auto m = alloc.allocateZeroed(max(T.sizeof, 1));
1163 return (() @trusted => cast(T*) m.ptr)();
1167 import core.internal.lifetime : emplaceRef;
1168 import core.lifetime : emplace;
1170 auto m = alloc.allocate(max(stateSize!T, 1));
1171 if (!m.ptr) return null;
1173 // make can only be @safe if emplace or emplaceRef is `pure`
1176 static if (is(T == class)) return emplace!T(m, args);
1179 // Assume cast is safe as allocation succeeded for `stateSize!T`
1180 auto p = () @trusted { return cast(T*) m.ptr; }();
1181 emplaceRef!T(*p, args);
1188 static if (is(typeof(() pure { return construct(); })))
1190 // Assume deallocation is safe because:
1191 // 1) in case of failure, `m` is the only reference to this memory
1192 // 2) `m` is known to originate from `alloc`
1193 () @trusted { alloc.deallocate(m); }();
1197 alloc.deallocate(m);
1208 // Dynamically allocate one integer
1209 const int* p1 = theAllocator.make!int;
1210 // It's implicitly initialized with its .init value
1212 // Dynamically allocate one double, initialize to 42.5
1213 const double* p2 = theAllocator.make!double(42.5);
1214 assert(*p2 == 42.5);
1216 // Dynamically allocate a struct
1221 // Use the generated constructor taking field values in order
1222 const Point* p = theAllocator.make!Point(1, 2);
1223 assert(p.x == 1 && p.y == 2 && p.z == 0);
1225 // Dynamically allocate a class object
1226 static class Customer
1230 this(uint id) { this.id = id; }
1233 Customer cust = theAllocator.make!Customer;
1234 assert(cust.id == uint.max); // default initialized
1235 cust = theAllocator.make!Customer(42);
1236 assert(cust.id == 42);
1238 // explicit passing of outer pointer
1244 auto getX() { return x; }
1247 auto outer = theAllocator.make!Outer();
1248 auto inner = theAllocator.make!(Outer.Inner)(outer);
1249 assert(outer.x == inner.getX);
1252 // https://issues.dlang.org/show_bug.cgi?id=15639
1253 // https://issues.dlang.org/show_bug.cgi?id=15772
1256 abstract class Foo {}
1258 static assert(!is(typeof(theAllocator.make!Foo)));
1259 static assert( is(typeof(theAllocator.make!Bar)));
1264 void test(Allocator)(auto ref Allocator alloc)
1266 const int* a = alloc.make!int(10);
1276 A* b = alloc.make!A(42);
1278 assert(b.y is null);
1279 import std.math.traits : isNaN;
1282 b = alloc.make!A(43, "44", 45);
1284 assert(b.y == "44");
1292 this(int _x, string _y = null, double _z = double.init)
1300 B c = alloc.make!B(42);
1302 assert(c.y is null);
1305 c = alloc.make!B(43, "44", 45);
1307 assert(c.y == "44");
1310 const parray = alloc.make!(int[]);
1311 assert((*parray).empty);
1314 import std.experimental.allocator.gc_allocator : GCAllocator;
1315 test(GCAllocator.instance);
1319 // Attribute propagation
1320 nothrow @safe @nogc unittest
1322 import std.experimental.allocator.mallocator : Mallocator;
1323 alias alloc = Mallocator.instance;
1325 void test(T, Args...)(auto ref Args args)
1327 auto k = alloc.make!T(args);
1328 () @trusted { alloc.dispose(k); }();
1337 // should be pure with the GCAllocator
1338 /*pure nothrow*/ @safe unittest
1340 import std.experimental.allocator.gc_allocator : GCAllocator;
1342 alias alloc = GCAllocator.instance;
1344 void test(T, Args...)(auto ref Args args)
1346 auto k = alloc.make!T(args);
1347 (a) @trusted { a.dispose(k); }(alloc);
1356 // Verify that making an object by calling an impure constructor is not @safe
1357 nothrow @safe @nogc unittest
1359 import std.experimental.allocator.mallocator : Mallocator;
1360 static struct Pure { this(int) pure nothrow @nogc @safe {} }
1362 cast(void) Mallocator.instance.make!Pure(0);
1365 static struct Impure { this(int) nothrow @nogc @safe {
1368 static assert(!__traits(compiles, cast(void) Mallocator.instance.make!Impure(0)));
1371 // test failure with a pure, failing struct
1374 import std.exception : assertThrown, enforce;
1376 // this struct can't be initialized
1377 struct InvalidStruct
1384 import std.experimental.allocator.mallocator : Mallocator;
1385 assertThrown(make!InvalidStruct(Mallocator.instance, 42));
1388 // test failure with an impure, failing struct
1391 import std.exception : assertThrown, enforce;
1393 struct InvalidImpureStruct
1401 import std.experimental.allocator.mallocator : Mallocator;
1402 assertThrown(make!InvalidImpureStruct(Mallocator.instance, 42));
1405 // Don't allow zero-ctor-args `make` for structs with `@disable this();`
1408 struct NoDefaultCtor
1413 import std.experimental.allocator.mallocator : Mallocator;
1414 static assert(!__traits(compiles, make!NoDefaultCtor(Mallocator.instance)),
1415 "Don't allow zero-ctor-args `make` for structs with `@disable this();`");
1418 // https://issues.dlang.org/show_bug.cgi?id=18937
1423 ubyte[16 * 1024] data;
1426 static struct SomeAllocator
1428 ubyte[] allocate(size_t) { return []; }
1429 void deallocate(void[]) {}
1432 auto x = SomeAllocator().make!S();
1435 private void fillWithMemcpy(T)(scope void[] array, auto ref T filler) nothrow
1438 import core.stdc.string : memset;
1439 import std.traits : CopyConstness;
1440 if (!array.length) return;
1441 memset(array.ptr, *cast(CopyConstness!(T*, ubyte*)) &filler, array.length);
1444 private void fillWithMemcpy(T)(scope void[] array, auto ref T filler) nothrow
1447 import core.stdc.string : memcpy;
1448 import std.algorithm.comparison : min;
1449 if (!array.length) return;
1450 memcpy(array.ptr, &filler, T.sizeof);
1451 // Fill the array from the initialized portion of itself exponentially.
1452 for (size_t offset = T.sizeof; offset < array.length; )
1454 size_t extent = min(offset, array.length - offset);
1455 memcpy(array.ptr + offset, array.ptr, extent);
1462 // Test T.sizeof == 1 path of fillWithMemcpy.
1464 fillWithMemcpy(a, ubyte(42));
1465 assert(a.length == 0);
1466 a = [ 1, 2, 3, 4, 5 ];
1467 fillWithMemcpy(a, ubyte(42));
1468 assert(a == [ 42, 42, 42, 42, 42]);
1474 fillWithMemcpy(a, 42);
1475 assert(a.length == 0);
1476 a = [ 1, 2, 3, 4, 5 ];
1477 fillWithMemcpy(a, 42);
1478 assert(a == [ 42, 42, 42, 42, 42]);
1481 //Make shared object
1484 import core.atomic : atomicLoad;
1485 auto psi = theAllocator.make!(shared(int))(10);
1486 assert(10 == (*psi).atomicLoad());
1489 private T[] uninitializedFillDefault(T)(T[] array) nothrow
1491 static if (__traits(isZeroInit, T))
1493 import core.stdc.string : memset;
1495 memset(array.ptr, 0, T.sizeof * array.length);
1498 else static if (is(immutable T == immutable char) || is(immutable T == immutable wchar))
1500 import core.stdc.string : memset;
1502 memset(array.ptr, 0xff, T.sizeof * array.length);
1508 fillWithMemcpy(array, t);
1516 static struct S { int x = 42; @disable this(this); }
1518 int[5] expected = [42, 42, 42, 42, 42];
1520 uninitializedFillDefault(arr);
1521 assert((cast(int*) arr.ptr)[0 .. arr.length] == expected);
1526 int[] a = [1, 2, 4];
1527 uninitializedFillDefault(a);
1528 assert(a == [0, 0, 0]);
1530 char[] b = [1, 2, 4];
1531 uninitializedFillDefault(b);
1532 assert(b == [0xff, 0xff, 0xff]);
1534 wchar[] c = [1, 2, 4];
1535 uninitializedFillDefault(c);
1536 assert(c == [0xffff, 0xffff, 0xffff]);
1541 static struct P { float x = 0; float y = 0; }
1543 static assert(__traits(isZeroInit, P));
1544 P[] a = [P(10, 11), P(20, 21), P(40, 41)];
1545 uninitializedFillDefault(a);
1546 assert(a == [P.init, P.init, P.init]);
1550 Create an array of `T` with `length` elements using `alloc`. The array is either default-initialized, filled with copies of `init`, or initialized with values fetched from `range`.
1553 T = element type of the array being created
1554 alloc = the allocator used for getting memory
1555 length = length of the newly created array
1556 init = element used for filling the array
1557 range = range used for initializing the array elements
1560 The newly-created array, or `null` if either `length` was `0` or
1564 The first two overloads throw only if `alloc`'s primitives do. The
1565 overloads that involve copy initialization deallocate memory and propagate the
1566 exception if the copy operation throws.
1568 T[] makeArray(T, Allocator)(auto ref Allocator alloc, size_t length)
1570 if (!length) return null;
1571 static if (T.sizeof <= 1)
1573 const nAlloc = length * T.sizeof;
1577 import core.checkedint : mulu;
1579 const nAlloc = mulu(length, T.sizeof, overflow);
1580 if (overflow) return null;
1583 static if (__traits(isZeroInit, T) && hasMember!(Allocator, "allocateZeroed"))
1585 auto m = alloc.allocateZeroed(nAlloc);
1586 return (() @trusted => cast(T[]) m)();
1590 auto m = alloc.allocate(nAlloc);
1591 if (!m.ptr) return null;
1593 return () @trusted { return cast(T[]) uninitializedFillDefault(cast(U[]) m); }();
1599 void test1(A)(auto ref A alloc)
1601 int[] a = alloc.makeArray!int(0);
1602 assert(a.length == 0 && a.ptr is null);
1603 a = alloc.makeArray!int(5);
1604 assert(a.length == 5);
1605 static immutable cheatsheet = [0, 0, 0, 0, 0];
1606 assert(a == cheatsheet);
1609 void test2(A)(auto ref A alloc)
1611 static struct S { int x = 42; @disable this(this); }
1612 S[] arr = alloc.makeArray!S(5);
1613 assert(arr.length == 5);
1614 int[] arrInt = () @trusted { return (cast(int*) arr.ptr)[0 .. 5]; }();
1615 static immutable res = [42, 42, 42, 42, 42];
1616 assert(arrInt == res);
1619 import std.experimental.allocator.gc_allocator : GCAllocator;
1620 import std.experimental.allocator.mallocator : Mallocator;
1621 (alloc) /*pure nothrow*/ @safe { test1(alloc); test2(alloc);} (GCAllocator.instance);
1622 (alloc) nothrow @safe @nogc { test1(alloc); test2(alloc);} (Mallocator.instance);
1623 test2(theAllocator);
1628 import std.algorithm.comparison : equal;
1629 auto a = theAllocator.makeArray!(shared int)(5);
1630 static assert(is(typeof(a) == shared(int)[]));
1631 assert(a.length == 5);
1632 assert(a.equal([0, 0, 0, 0, 0]));
1634 auto b = theAllocator.makeArray!(const int)(5);
1635 static assert(is(typeof(b) == const(int)[]));
1636 assert(b.length == 5);
1637 assert(b.equal([0, 0, 0, 0, 0]));
1639 auto c = theAllocator.makeArray!(immutable int)(5);
1640 static assert(is(typeof(c) == immutable(int)[]));
1641 assert(c.length == 5);
1642 assert(c.equal([0, 0, 0, 0, 0]));
1645 // https://issues.dlang.org/show_bug.cgi?id=19085 - makeArray with void
1648 auto b = theAllocator.makeArray!void(5);
1649 scope(exit) theAllocator.dispose(b);
1650 auto c = cast(ubyte[]) b;
1651 assert(c.length == 5);
1652 assert(c == [0, 0, 0, 0, 0]); // default initialization
1655 private enum hasPurePostblit(T) = !hasElaborateCopyConstructor!T ||
1656 is(typeof(() pure { T.init.__xpostblit(); }));
1658 private enum hasPureDtor(T) = !hasElaborateDestructor!T ||
1659 is(typeof(() pure { T.init.__xdtor(); }));
1661 // `true` when postblit and destructor of T cannot escape references to itself
1662 private enum canSafelyDeallocPostRewind(T) = hasPurePostblit!T && hasPureDtor!T;
1665 T[] makeArray(T, Allocator)(auto ref Allocator alloc, size_t length, T init)
1667 if (!length) return null;
1668 auto m = alloc.allocate(T.sizeof * length);
1669 if (!m.ptr) return null;
1670 auto result = () @trusted { return cast(T[]) m; } ();
1671 import std.traits : hasElaborateCopyConstructor;
1672 static if (hasElaborateCopyConstructor!T)
1676 static if (canSafelyDeallocPostRewind!T)
1677 () @trusted { alloc.deallocate(m); } ();
1679 alloc.deallocate(m);
1683 static if (hasElaborateDestructor!T)
1693 import core.lifetime : emplace;
1694 for (; i < length; ++i)
1696 emplace!T(&result[i], init);
1702 () @trusted { fillWithMemcpy(cast(U[]) result, *(cast(U*) &init)); }();
1710 import std.algorithm.comparison : equal;
1711 static void test(T)()
1713 T[] a = theAllocator.makeArray!T(2);
1714 assert(a.equal([0, 0]));
1715 a = theAllocator.makeArray!T(3, 42);
1716 assert(a.equal([42, 42, 42]));
1717 import std.range : only;
1718 a = theAllocator.makeArray!T(only(42, 43, 44));
1719 assert(a.equal([42, 43, 44]));
1722 test!(shared int)();
1724 test!(immutable int)();
1729 void test(T)(in T initialValue)
1731 auto t = theAllocator.makeArray!T(100, initialValue);
1732 //auto t = theAllocator.makeArray(100, initialValue); // works well with the old code
1741 void test(A)(auto ref A alloc)
1743 long[] a = alloc.makeArray!long(0, 42);
1744 assert(a.length == 0 && a.ptr is null);
1745 a = alloc.makeArray!long(5, 42);
1746 assert(a.length == 5);
1747 assert(a == [ 42, 42, 42, 42, 42 ]);
1749 import std.experimental.allocator.gc_allocator : GCAllocator;
1750 (alloc) /*pure nothrow*/ @safe { test(alloc); } (GCAllocator.instance);
1754 // test failure with a pure, failing struct
1757 import std.exception : assertThrown, enforce;
1771 import std.experimental.allocator.mallocator : Mallocator;
1772 assertThrown(makeArray!NoCopy(Mallocator.instance, 10, NoCopy(42)));
1775 // test failure with an impure, failing struct
1778 import std.exception : assertThrown, enforce;
1798 import std.experimental.allocator.mallocator : Mallocator;
1799 assertThrown(makeArray!Singleton(Mallocator.instance, 10, Singleton(42)));
1803 Unqual!(ElementEncodingType!R)[] makeArray(Allocator, R)(auto ref Allocator alloc, R range)
1804 if (isInputRange!R && !isInfinite!R)
1806 alias T = Unqual!(ElementEncodingType!R);
1807 return makeArray!(T, Allocator, R)(alloc, range);
1811 T[] makeArray(T, Allocator, R)(auto ref Allocator alloc, R range)
1812 if (isInputRange!R && !isInfinite!R)
1814 static if (isForwardRange!R || hasLength!R)
1816 static if (hasLength!R || isNarrowString!R)
1817 immutable length = range.length;
1819 immutable length = range.save.walkLength;
1821 if (!length) return null;
1822 auto m = alloc.allocate(T.sizeof * length);
1823 if (!m.ptr) return null;
1824 auto result = () @trusted { return cast(T[]) m; } ();
1831 auto p = () @trusted { return cast(Unqual!T*) &result[j]; }();
1835 static if (canSafelyDeallocPostRewind!T)
1836 () @trusted { alloc.deallocate(m); } ();
1838 alloc.deallocate(m);
1841 import core.internal.lifetime : emplaceRef;
1842 static if (isNarrowString!R || isRandomAccessRange!R)
1844 foreach (j; 0 .. range.length)
1846 emplaceRef!T(result[i++], range[j]);
1851 for (; !range.empty; range.popFront, ++i)
1853 emplaceRef!T(result[i], range.front);
1862 size_t estimated = 8;
1863 auto m = alloc.allocate(T.sizeof * estimated);
1864 if (!m.ptr) return null;
1865 auto result = () @trusted { return cast(T[]) m; } ();
1867 size_t initialized = 0;
1870 foreach (i; 0 .. initialized + 1)
1875 static if (canSafelyDeallocPostRewind!T)
1876 () @trusted { alloc.deallocate(m); } ();
1878 alloc.deallocate(m);
1880 scope (failure) bailout;
1882 for (; !range.empty; range.popFront, ++initialized)
1884 if (initialized == estimated)
1886 // Need to reallocate
1887 static if (hasPurePostblit!T)
1888 auto success = () @trusted { return alloc.reallocate(m, T.sizeof * (estimated *= 2)); } ();
1890 auto success = alloc.reallocate(m, T.sizeof * (estimated *= 2));
1896 result = () @trusted { return cast(T[]) m; } ();
1898 import core.internal.lifetime : emplaceRef;
1899 emplaceRef(result[initialized], range.front);
1902 if (initialized < estimated)
1904 // Try to shrink memory, no harm if not possible
1905 static if (hasPurePostblit!T)
1906 auto success = () @trusted { return alloc.reallocate(m, T.sizeof * initialized); } ();
1908 auto success = alloc.reallocate(m, T.sizeof * initialized);
1910 result = () @trusted { return cast(T[]) m; } ();
1913 return result[0 .. initialized];
1919 void test(A)(auto ref A alloc)
1921 long[] a = alloc.makeArray!long((int[]).init);
1922 assert(a.length == 0 && a.ptr is null);
1923 a = alloc.makeArray!long([5, 42]);
1924 assert(a.length == 2);
1925 assert(a == [ 5, 42]);
1927 // we can also infer the type
1928 auto b = alloc.makeArray([4.0, 2.0]);
1929 static assert(is(typeof(b) == double[]));
1930 assert(b == [4.0, 2.0]);
1932 import std.experimental.allocator.gc_allocator : GCAllocator;
1933 (alloc) pure nothrow @safe { test(alloc); } (GCAllocator.instance);
1937 // infer types for strings
1940 void test(A)(auto ref A alloc)
1942 auto c = alloc.makeArray("fooπ😜");
1943 static assert(is(typeof(c) == char[]));
1944 assert(c == "fooπ😜");
1946 auto d = alloc.makeArray("fooπ😜"d);
1947 static assert(is(typeof(d) == dchar[]));
1948 assert(d == "fooπ😜");
1950 auto w = alloc.makeArray("fooπ😜"w);
1951 static assert(is(typeof(w) == wchar[]));
1952 assert(w == "fooπ😜");
1955 import std.experimental.allocator.gc_allocator : GCAllocator;
1956 (alloc) pure nothrow @safe { test(alloc); } (GCAllocator.instance);
1960 /*pure*/ nothrow @safe unittest
1962 import std.algorithm.comparison : equal;
1963 import std.experimental.allocator.gc_allocator : GCAllocator;
1964 import std.internal.test.dummyrange;
1965 import std.range : iota;
1966 foreach (DummyType; AllDummyRanges)
1968 (alloc) pure nothrow @safe
1971 auto arr = alloc.makeArray(d);
1972 assert(arr.length == 10);
1973 assert(arr.equal(iota(1, 11)));
1974 } (GCAllocator.instance);
1978 // test failure with a pure, failing struct
1981 import std.exception : assertThrown, enforce;
1997 enforce(b < 3, "there can only be three elements");
2000 import std.experimental.allocator.mallocator : Mallocator;
2001 auto arr = [NoCopy(1), NoCopy(2), NoCopy(3)];
2002 assertThrown(makeArray!NoCopy(Mallocator.instance, arr));
2022 makeArray!NoCopy(Mallocator.instance, NoCopyRange()); // rvalue elements are forwarded/moved
2025 // test failure with an impure, failing struct
2028 import std.exception : assertThrown, enforce;
2031 static maxElements = 2;
2044 enforce(i++ < maxElements, "there can only be four elements");
2048 import std.experimental.allocator.mallocator : Mallocator;
2049 auto arr = [NoCopy(1), NoCopy(2)];
2050 assertThrown(makeArray!NoCopy(Mallocator.instance, arr));
2053 maxElements = 0; // disallow any postblit
2074 auto arr2 = makeArray!NoCopy(Mallocator.instance, NoCopyRange());
2075 assert(i == j && i == 101); // all 101 rvalue elements forwarded/moved
2078 version (StdUnittest)
2080 private struct ForcedInputRange(T)
2083 pure nothrow @safe @nogc:
2084 bool empty() { return !array || (*array).empty; }
2085 ref T front() { return (*array)[0]; }
2086 void popFront() { *array = (*array)[1 .. $]; }
2092 import std.array : array;
2093 import std.range : iota;
2094 int[] arr = iota(10).array;
2096 void test(A)(auto ref A alloc)
2098 ForcedInputRange!int r;
2099 long[] a = alloc.makeArray!long(r);
2100 assert(a.length == 0 && a.ptr is null);
2102 r.array = () @trusted { return &arr2; } ();
2103 a = alloc.makeArray!long(r);
2104 assert(a.length == 10);
2105 assert(a == iota(10).array);
2107 import std.experimental.allocator.gc_allocator : GCAllocator;
2108 (alloc) pure nothrow @safe { test(alloc); } (GCAllocator.instance);
2113 Grows `array` by appending `delta` more elements. The needed memory is
2114 allocated using `alloc`. The extra elements added are either default-
2115 initialized, filled with copies of `init`, or initialized with values
2116 fetched from `range`.
2119 T = element type of the array being created
2120 alloc = the allocator used for getting memory
2121 array = a reference to the array being grown
2122 delta = number of elements to add (upon success the new length of `array` is
2123 $(D array.length + delta))
2124 init = element used for filling the array
2125 range = range used for initializing the array elements
2128 `true` upon success, `false` if memory could not be allocated. In the
2129 latter case `array` is left unaffected.
2132 The first two overloads throw only if `alloc`'s primitives do. The
2133 overloads that involve copy initialization deallocate memory and propagate the
2134 exception if the copy operation throws.
2136 bool expandArray(T, Allocator)(auto ref Allocator alloc, ref T[] array,
2139 if (!delta) return true;
2140 if (array is null) return false;
2141 immutable oldLength = array.length;
2143 if (!alloc.reallocate(buf, buf.length + T.sizeof * delta)) return false;
2144 array = cast(T[]) buf;
2145 array[oldLength .. $].uninitializedFillDefault;
2151 void test(A)(auto ref A alloc)
2153 auto arr = alloc.makeArray!int([1, 2, 3]);
2154 assert(alloc.expandArray(arr, 3));
2155 assert(arr == [1, 2, 3, 0, 0, 0]);
2157 import std.experimental.allocator.gc_allocator : GCAllocator;
2158 test(GCAllocator.instance);
2163 bool expandArray(T, Allocator)(auto ref Allocator alloc, ref T[] array,
2164 size_t delta, auto ref T init)
2166 if (!delta) return true;
2167 if (array is null) return false;
2169 if (!alloc.reallocate(buf, buf.length + T.sizeof * delta)) return false;
2170 immutable oldLength = array.length;
2171 array = cast(T[]) buf;
2172 scope(failure) array[oldLength .. $].uninitializedFillDefault;
2173 import std.algorithm.mutation : uninitializedFill;
2174 array[oldLength .. $].uninitializedFill(init);
2180 void test(A)(auto ref A alloc)
2182 auto arr = alloc.makeArray!int([1, 2, 3]);
2183 assert(alloc.expandArray(arr, 3, 1));
2184 assert(arr == [1, 2, 3, 1, 1, 1]);
2186 import std.experimental.allocator.gc_allocator : GCAllocator;
2187 test(GCAllocator.instance);
2192 bool expandArray(T, Allocator, R)(auto ref Allocator alloc, ref T[] array,
2196 if (array is null) return false;
2197 static if (isForwardRange!R)
2199 immutable delta = walkLength(range.save);
2200 if (!delta) return true;
2201 immutable oldLength = array.length;
2203 // Reallocate support memory
2205 if (!alloc.reallocate(buf, buf.length + T.sizeof * delta))
2209 array = cast(T[]) buf;
2210 // At this point we're committed to the new length.
2212 auto toFill = array[oldLength .. $];
2215 // Fill the remainder with default-constructed data
2216 toFill.uninitializedFillDefault;
2219 for (; !range.empty; range.popFront, toFill = toFill[1 .. $])
2221 assert(toFill.length > 0);
2222 import core.lifetime : emplace;
2223 emplace!T(&toFill[0], range.front);
2225 assert(toFill.length == 0);
2231 // The last element didn't make it, fill with default
2232 array[$ - 1 .. $].uninitializedFillDefault;
2235 for (; !range.empty; range.popFront)
2237 if (!alloc.reallocate(buf, buf.length + T.sizeof))
2239 array = cast(T[]) buf;
2242 import core.lifetime : emplace;
2243 emplace!T(buf[$ - T.sizeof .. $], range.front);
2246 array = cast(T[]) buf;
2254 auto arr = theAllocator.makeArray!int([1, 2, 3]);
2255 assert(theAllocator.expandArray(arr, 2));
2256 assert(arr == [1, 2, 3, 0, 0]);
2257 import std.range : only;
2258 assert(theAllocator.expandArray(arr, only(4, 5)));
2259 assert(arr == [1, 2, 3, 0, 0, 4, 5]);
2264 auto arr = theAllocator.makeArray!int([1, 2, 3]);
2265 ForcedInputRange!int r;
2266 int[] b = [ 1, 2, 3, 4 ];
2269 assert(theAllocator.expandArray(arr, r));
2270 assert(arr == [1, 2, 3, 1, 2, 3, 4]);
2273 // Regression test for https://issues.dlang.org/show_bug.cgi?id=20929
2276 static void test(Char, Allocator)(auto ref Allocator alloc)
2278 auto arr = alloc.makeArray!Char(1, Char('f'));
2280 import std.utf : byUTF;
2281 auto forwardRange = "oo".byUTF!Char();
2282 static assert(isForwardRange!(typeof(forwardRange)));
2283 // Test the forward-range code-path.
2284 assert(alloc.expandArray(arr, forwardRange));
2286 assert(arr == "foo");
2288 immutable(Char)[] temp = "bar";
2289 auto inputRange = ForcedInputRange!(immutable(Char))(&temp);
2290 // Test the input-range code-path.
2291 assert(alloc.expandArray(arr, inputRange));
2293 assert(arr == "foobar");
2296 import std.experimental.allocator.gc_allocator : GCAllocator;
2297 test!char(GCAllocator.instance);
2298 test!wchar(GCAllocator.instance);
2299 test!char(theAllocator);
2300 test!wchar(theAllocator);
2304 Shrinks an array by `delta` elements.
2306 If $(D array.length < delta), does nothing and returns `false`. Otherwise,
2307 destroys the last $(D array.length - delta) elements in the array and then
2308 reallocates the array's buffer. If reallocation fails, fills the array with
2309 default-initialized data.
2312 T = element type of the array being created
2313 alloc = the allocator used for getting memory
2314 array = a reference to the array being shrunk
2315 delta = number of elements to remove (upon success the new length of `array` is $(D array.length - delta))
2318 `true` upon success, `false` if memory could not be reallocated. In the latter
2319 case, the slice $(D array[$ - delta .. $]) is left with default-initialized
2323 The first two overloads throw only if `alloc`'s primitives do. The
2324 overloads that involve copy initialization deallocate memory and propagate the
2325 exception if the copy operation throws.
2327 bool shrinkArray(T, Allocator)(auto ref Allocator alloc,
2328 ref T[] array, size_t delta)
2330 if (delta > array.length) return false;
2332 // Destroy elements. If a destructor throws, fill the already destroyed
2333 // stuff with the default initializer.
2338 array[$ - delta .. $][0 .. destroyed].uninitializedFillDefault;
2340 foreach (ref e; array[$ - delta .. $])
2347 if (delta == array.length)
2349 alloc.deallocate(array);
2355 if (!alloc.reallocate(buf, buf.length - T.sizeof * delta))
2357 // urgh, at least fill back with default
2358 array[$ - delta .. $].uninitializedFillDefault;
2361 array = cast(T[]) buf;
2368 int[] a = theAllocator.makeArray!int(100, 42);
2369 assert(a.length == 100);
2370 assert(theAllocator.shrinkArray(a, 98));
2371 assert(a.length == 2);
2372 assert(a == [42, 42]);
2377 void test(A)(auto ref A alloc)
2379 long[] a = alloc.makeArray!long((int[]).init);
2380 assert(a.length == 0 && a.ptr is null);
2381 a = alloc.makeArray!long(100, 42);
2382 assert(alloc.shrinkArray(a, 98));
2383 assert(a.length == 2);
2384 assert(a == [ 42, 42]);
2386 import std.experimental.allocator.gc_allocator : GCAllocator;
2387 test(GCAllocator.instance);
2393 Destroys and then deallocates (using `alloc`) the object pointed to by a
2394 pointer, the class object referred to by a `class` or `interface`
2395 reference, or an entire array. It is assumed the respective entities had been
2396 allocated with the same allocator.
2399 void dispose(A, T)(auto ref A alloc, auto ref T* p)
2401 static if (hasElaborateDestructor!T)
2405 alloc.deallocate((cast(void*) p)[0 .. T.sizeof]);
2406 static if (__traits(isRef, p))
2411 void dispose(A, T)(auto ref A alloc, auto ref T p)
2412 if (is(T == class) || is(T == interface))
2415 static if (is(T == interface))
2419 import core.sys.windows.unknwn : IUnknown;
2420 static assert(!is(T: IUnknown), "COM interfaces can't be destroyed in "
2421 ~ __PRETTY_FUNCTION__);
2423 auto ob = cast(Object) p;
2427 auto support = (cast(void*) ob)[0 .. typeid(ob).initializer.length];
2429 alloc.deallocate(support);
2430 static if (__traits(isRef, p))
2435 void dispose(A, T)(auto ref A alloc, auto ref T[] array)
2437 static if (hasElaborateDestructor!(typeof(array[0])))
2439 foreach (ref e; array)
2444 alloc.deallocate(array);
2445 static if (__traits(isRef, array))
2459 override void method() { x = 21; }
2465 auto a = theAllocator.make!A;
2468 theAllocator.dispose(a);
2471 B b = theAllocator.make!B;
2474 theAllocator.dispose(b);
2477 I i = theAllocator.make!B;
2480 theAllocator.dispose(i);
2483 int[] arr = theAllocator.makeArray!int(43);
2484 theAllocator.dispose(arr);
2487 // https://issues.dlang.org/show_bug.cgi?id=16512
2490 import std.experimental.allocator.mallocator : Mallocator;
2492 int* i = Mallocator.instance.make!int(0);
2493 Mallocator.instance.dispose(i);
2496 Object o = Mallocator.instance.make!Object();
2497 Mallocator.instance.dispose(o);
2500 uint* u = Mallocator.instance.make!uint(0);
2501 Mallocator.instance.dispose((){return u;}());
2504 uint[] ua = Mallocator.instance.makeArray!uint([0,1,2]);
2505 Mallocator.instance.dispose(ua);
2509 // https://issues.dlang.org/show_bug.cgi?id=15721
2512 import std.experimental.allocator.mallocator : Mallocator;
2519 bar = Mallocator.instance.make!Bar;
2520 foo = cast(Foo) bar;
2521 Mallocator.instance.dispose(foo);
2525 Allocates a multidimensional array of elements of type T.
2528 N = number of dimensions
2529 T = element type of an element of the multidimensional arrat
2530 alloc = the allocator used for getting memory
2531 lengths = static array containing the size of each dimension
2534 An N-dimensional array with individual elements of type T.
2536 auto makeMultidimensionalArray(T, Allocator, size_t N)(auto ref Allocator alloc, size_t[N] lengths...)
2540 return makeArray!T(alloc, lengths[0]);
2544 alias E = typeof(makeMultidimensionalArray!(T, Allocator, N - 1)(alloc, lengths[1 .. $]));
2545 auto ret = makeArray!E(alloc, lengths[0]);
2546 foreach (ref e; ret)
2547 e = makeMultidimensionalArray!(T, Allocator, N - 1)(alloc, lengths[1 .. $]);
2555 import std.experimental.allocator.mallocator : Mallocator;
2557 auto mArray = Mallocator.instance.makeMultidimensionalArray!int(2, 3, 6);
2559 // deallocate when exiting scope
2562 Mallocator.instance.disposeMultidimensionalArray(mArray);
2565 assert(mArray.length == 2);
2566 foreach (lvl2Array; mArray)
2568 assert(lvl2Array.length == 3);
2569 foreach (lvl3Array; lvl2Array)
2570 assert(lvl3Array.length == 6);
2575 Destroys and then deallocates a multidimensional array, assuming it was
2576 created with makeMultidimensionalArray and the same allocator was used.
2579 T = element type of an element of the multidimensional array
2580 alloc = the allocator used for getting memory
2581 array = the multidimensional array that is to be deallocated
2583 void disposeMultidimensionalArray(T, Allocator)(auto ref Allocator alloc, auto ref T[] array)
2585 static if (isArray!T)
2587 foreach (ref e; array)
2588 disposeMultidimensionalArray(alloc, e);
2591 dispose(alloc, array);
2592 static if (__traits(isRef, array))
2599 struct TestAllocator
2601 import std.experimental.allocator.common : platformAlignment;
2602 import std.experimental.allocator.mallocator : Mallocator;
2604 alias allocator = Mallocator.instance;
2606 private static struct ByteRange
2612 private ByteRange[] _allocations;
2614 enum uint alignment = platformAlignment;
2616 void[] allocate(size_t numBytes)
2618 auto ret = allocator.allocate(numBytes);
2619 _allocations ~= ByteRange(ret.ptr, ret.length);
2623 bool deallocate(void[] bytes)
2625 import std.algorithm.mutation : remove;
2626 import std.algorithm.searching : canFind;
2628 bool pred(ByteRange other)
2629 { return other.ptr == bytes.ptr && other.length == bytes.length; }
2631 assert(_allocations.canFind!pred);
2633 _allocations = _allocations.remove!pred;
2634 return allocator.deallocate(bytes);
2639 assert(!_allocations.length);
2643 TestAllocator allocator;
2645 auto mArray = allocator.makeMultidimensionalArray!int(2, 3, 5, 6, 7, 2);
2647 allocator.disposeMultidimensionalArray(mArray);
2652 Returns a dynamically-typed `CAllocator` built around a given statically-
2653 typed allocator `a` of type `A`. Passing a pointer to the allocator
2654 creates a dynamic allocator around the allocator pointed to by the pointer,
2655 without attempting to copy or move it. Passing the allocator by value or
2656 reference behaves as follows.
2659 $(LI If `A` has no state, the resulting object is allocated in static
2661 $(LI If `A` has state, the result will $(REF move, std,algorithm,mutation)
2662 the supplied allocator $(D A a) within. The result itself is allocated in its
2663 own statically-typed allocator.)
2667 RCIAllocator allocatorObject(A)(auto ref A a)
2670 import core.lifetime : emplace;
2671 static if (stateSize!A == 0)
2673 enum s = stateSize!(CAllocatorImpl!A).divideRoundUp(ulong.sizeof);
2674 __gshared ulong[s] state;
2675 __gshared RCIAllocator result;
2678 // Don't care about a few races
2679 result = RCIAllocator(emplace!(CAllocatorImpl!A)(state[]));
2681 assert(!result.isNull);
2686 auto state = a.allocate(stateSize!(CAllocatorImpl!A));
2687 import std.algorithm.mutation : move;
2688 import std.traits : hasMember;
2689 static if (hasMember!(A, "deallocate"))
2691 scope(failure) a.deallocate(state);
2693 auto tmp = cast(CAllocatorImpl!A) emplace!(CAllocatorImpl!A)(state);
2695 return RCIAllocator(tmp);
2700 RCIAllocator allocatorObject(A)(A* pa)
2703 import core.lifetime : emplace;
2704 auto state = pa.allocate(stateSize!(CAllocatorImpl!(A, Yes.indirect)));
2705 import std.traits : hasMember;
2706 static if (hasMember!(A, "deallocate"))
2708 scope(failure) pa.deallocate(state);
2710 return RCIAllocator(emplace!(CAllocatorImpl!(A, Yes.indirect))
2717 import std.experimental.allocator.mallocator : Mallocator;
2719 RCIAllocator a = allocatorObject(Mallocator.instance);
2720 auto b = a.allocate(100);
2721 assert(b.length == 100);
2722 assert(a.deallocate(b));
2724 // The in-situ region must be used by pointer
2725 import std.experimental.allocator.building_blocks.region : InSituRegion;
2726 auto r = InSituRegion!1024();
2727 a = allocatorObject(&r);
2728 b = a.allocate(200);
2729 assert(b.length == 200);
2730 // In-situ regions can deallocate the last allocation
2731 assert(a.deallocate(b));
2737 import std.experimental.allocator.mallocator;
2738 import std.experimental.allocator.building_blocks.stats_collector;
2740 alias SCAlloc = StatsCollector!(Mallocator, Options.bytesUsed);
2741 SCAlloc statsCollectorAlloc;
2742 assert(statsCollectorAlloc.bytesUsed == 0);
2744 auto _allocator = allocatorObject(statsCollectorAlloc);
2745 // Ensure that the allocator was passed through in CAllocatorImpl
2746 // This allocator was used to allocate the chunk that holds the
2747 // CAllocatorImpl object; which is it's own wrapper
2748 assert((cast(CAllocatorImpl!(SCAlloc))(_allocator._alloc)).impl.bytesUsed
2749 == stateSize!(CAllocatorImpl!(SCAlloc)));
2750 _allocator.allocate(1);
2751 assert((cast(CAllocatorImpl!(SCAlloc))(_allocator._alloc)).impl.bytesUsed
2752 == stateSize!(CAllocatorImpl!(SCAlloc)) + 1);
2757 Returns a dynamically-typed `CSharedAllocator` built around a given statically-
2758 typed allocator `a` of type `A`. Passing a pointer to the allocator
2759 creates a dynamic allocator around the allocator pointed to by the pointer,
2760 without attempting to copy or move it. Passing the allocator by value or
2761 reference behaves as follows.
2764 $(LI If `A` has no state, the resulting object is allocated in static
2766 $(LI If `A` has state and is copyable, the result will
2767 $(REF move, std,algorithm,mutation) the supplied allocator $(D A a) within.
2768 The result itself is allocated in its own statically-typed allocator.)
2769 $(LI If `A` has state and is not copyable, the result will move the
2770 passed-in argument into the result. The result itself is allocated in its own
2771 statically-typed allocator.)
2776 //nothrow @nogc @safe
2778 RCISharedAllocator sharedAllocatorObject(A)(auto ref A a)
2781 import core.lifetime : emplace;
2782 static if (stateSize!A == 0)
2784 enum s = stateSize!(CSharedAllocatorImpl!A).divideRoundUp(ulong.sizeof);
2785 static shared ulong[s] state;
2786 static RCISharedAllocator result;
2789 // Don't care about a few races
2790 result = RCISharedAllocator(
2791 (cast(shared CSharedAllocatorImpl!A)(
2792 emplace!(CSharedAllocatorImpl!A)(
2793 (() @trusted => cast(ulong[]) state[])()))));
2795 assert(!result.isNull);
2798 else static if (is(typeof({ shared A b = a; shared A c = b; }))) // copyable
2800 auto state = a.allocate(stateSize!(CSharedAllocatorImpl!A));
2801 import std.algorithm.mutation : move;
2802 import std.traits : hasMember;
2803 static if (hasMember!(A, "deallocate"))
2805 scope(failure) a.deallocate(state);
2807 auto tmp = emplace!(shared CSharedAllocatorImpl!A)(state);
2809 return RCISharedAllocator(tmp);
2811 else // the allocator object is not copyable
2813 assert(0, "Not yet implemented");
2818 RCISharedAllocator sharedAllocatorObject(A)(A* pa)
2821 import core.lifetime : emplace;
2822 auto state = pa.allocate(stateSize!(CSharedAllocatorImpl!(A, Yes.indirect)));
2823 import std.traits : hasMember;
2824 static if (hasMember!(A, "deallocate"))
2826 scope(failure) pa.deallocate(state);
2828 return RCISharedAllocator(emplace!(shared CSharedAllocatorImpl!(A, Yes.indirect))(state, pa));
2834 Implementation of `IAllocator` using `Allocator`. This adapts a
2835 statically-built allocator type to `IAllocator` that is directly usable by
2838 Usually `CAllocatorImpl` is used indirectly by calling $(LREF theAllocator).
2840 class CAllocatorImpl(Allocator, Flag!"indirect" indirect = No.indirect)
2843 import std.traits : hasMember;
2845 static if (stateSize!Allocator) private size_t rc = 1;
2848 The implementation is available as a public member.
2850 static if (indirect)
2853 private Allocator* pimpl;
2856 ref Allocator impl()
2869 static if (stateSize!Allocator) Allocator impl;
2870 else alias impl = Allocator.instance;
2874 /// Returns `impl.alignment`.
2875 override @property uint alignment()
2877 return impl.alignment;
2881 Returns `impl.goodAllocSize(s)`.
2883 override size_t goodAllocSize(size_t s)
2885 return impl.goodAllocSize(s);
2889 Returns `impl.allocate(s)`.
2891 override void[] allocate(size_t s, TypeInfo ti = null)
2893 return impl.allocate(s);
2897 If `impl.alignedAllocate` exists, calls it and returns the result.
2898 Otherwise, always returns `null`.
2900 override void[] alignedAllocate(size_t s, uint a)
2902 static if (hasMember!(Allocator, "alignedAllocate"))
2903 return impl.alignedAllocate(s, a);
2909 If `Allocator` implements `owns`, forwards to it. Otherwise, returns
2912 override Ternary owns(void[] b)
2914 static if (hasMember!(Allocator, "owns")) return impl.owns(b);
2915 else return Ternary.unknown;
2918 /// Returns $(D impl.expand(b, s)) if defined, `false` otherwise.
2919 override bool expand(ref void[] b, size_t s)
2921 static if (hasMember!(Allocator, "expand"))
2922 return impl.expand(b, s);
2927 /// Returns $(D impl.reallocate(b, s)).
2928 override bool reallocate(ref void[] b, size_t s)
2930 return impl.reallocate(b, s);
2933 /// Forwards to `impl.alignedReallocate` if defined, `false` otherwise.
2934 bool alignedReallocate(ref void[] b, size_t s, uint a)
2936 static if (!hasMember!(Allocator, "alignedAllocate"))
2942 return impl.alignedReallocate(b, s, a);
2946 // Undocumented for now
2947 Ternary resolveInternalPointer(const void* p, ref void[] result)
2949 static if (hasMember!(Allocator, "resolveInternalPointer"))
2951 return impl.resolveInternalPointer(p, result);
2955 return Ternary.unknown;
2960 If `impl.deallocate` is not defined, returns `false`. Otherwise it forwards
2963 override bool deallocate(void[] b)
2965 static if (hasMember!(Allocator, "deallocate"))
2967 return impl.deallocate(b);
2976 Calls `impl.deallocateAll()` and returns the result if defined,
2977 otherwise returns `false`.
2979 override bool deallocateAll()
2981 static if (hasMember!(Allocator, "deallocateAll"))
2983 return impl.deallocateAll();
2992 Forwards to `impl.empty()` if defined, otherwise returns `Ternary.unknown`.
2994 override Ternary empty()
2996 static if (hasMember!(Allocator, "empty"))
2998 return Ternary(impl.empty);
3002 return Ternary.unknown;
3007 Returns `impl.allocateAll()` if present, `null` otherwise.
3009 override void[] allocateAll()
3011 static if (hasMember!(Allocator, "allocateAll"))
3013 return impl.allocateAll();
3021 @nogc nothrow pure @safe
3022 override void incRef()
3024 static if (stateSize!Allocator) ++rc;
3027 @nogc nothrow pure @trusted
3028 override bool decRef()
3030 static if (stateSize!Allocator)
3032 import core.stdc.string : memcpy;
3036 static if (indirect)
3038 Allocator* tmp = pimpl;
3043 memcpy(&tmp, &this.impl, Allocator.sizeof);
3045 void[] support = (cast(void*) this)[0 .. stateSize!(typeof(this))];
3046 tmp.deallocate(support);
3062 Implementation of `ISharedAllocator` using `Allocator`. This adapts a
3063 statically-built, shareable across threads, allocator type to `ISharedAllocator`
3064 that is directly usable by non-templated code.
3066 Usually `CSharedAllocatorImpl` is used indirectly by calling
3067 $(LREF processAllocator).
3069 class CSharedAllocatorImpl(Allocator, Flag!"indirect" indirect = No.indirect)
3072 import std.traits : hasMember;
3073 import core.atomic : atomicOp, atomicLoad;
3075 static if (stateSize!Allocator) shared size_t rc = 1;
3078 The implementation is available as a public member.
3080 static if (indirect)
3083 private shared Allocator* pimpl;
3086 ref Allocator impl() shared
3092 this(Allocator* pa) shared
3099 static if (stateSize!Allocator) shared Allocator impl;
3100 else alias impl = Allocator.instance;
3104 /// Returns `impl.alignment`.
3105 override @property uint alignment() shared
3107 return impl.alignment;
3111 Returns `impl.goodAllocSize(s)`.
3113 override size_t goodAllocSize(size_t s) shared
3115 return impl.goodAllocSize(s);
3119 Returns `impl.allocate(s)`.
3121 override void[] allocate(size_t s, TypeInfo ti = null) shared
3123 return impl.allocate(s);
3127 If `impl.alignedAllocate` exists, calls it and returns the result.
3128 Otherwise, always returns `null`.
3130 override void[] alignedAllocate(size_t s, uint a) shared
3132 static if (hasMember!(Allocator, "alignedAllocate"))
3133 return impl.alignedAllocate(s, a);
3139 If `Allocator` implements `owns`, forwards to it. Otherwise, returns
3142 override Ternary owns(void[] b) shared
3144 static if (hasMember!(Allocator, "owns")) return impl.owns(b);
3145 else return Ternary.unknown;
3148 /// Returns $(D impl.expand(b, s)) if defined, `false` otherwise.
3149 override bool expand(ref void[] b, size_t s) shared
3151 static if (hasMember!(Allocator, "expand"))
3152 return impl.expand(b, s);
3157 /// Returns $(D impl.reallocate(b, s)).
3158 override bool reallocate(ref void[] b, size_t s) shared
3160 return impl.reallocate(b, s);
3163 /// Forwards to `impl.alignedReallocate` if defined, `false` otherwise.
3164 bool alignedReallocate(ref void[] b, size_t s, uint a) shared
3166 static if (!hasMember!(Allocator, "alignedAllocate"))
3172 return impl.alignedReallocate(b, s, a);
3176 // Undocumented for now
3177 Ternary resolveInternalPointer(const void* p, ref void[] result) shared
3179 static if (hasMember!(Allocator, "resolveInternalPointer"))
3181 return impl.resolveInternalPointer(p, result);
3185 return Ternary.unknown;
3190 If `impl.deallocate` is not defined, returns `false`. Otherwise it forwards
3193 override bool deallocate(void[] b) shared
3195 static if (hasMember!(Allocator, "deallocate"))
3197 return impl.deallocate(b);
3206 Calls `impl.deallocateAll()` and returns the result if defined,
3207 otherwise returns `false`.
3209 override bool deallocateAll() shared
3211 static if (hasMember!(Allocator, "deallocateAll"))
3213 return impl.deallocateAll();
3222 Forwards to `impl.empty()` if defined, otherwise returns `Ternary.unknown`.
3224 override Ternary empty() shared
3226 static if (hasMember!(Allocator, "empty"))
3228 return Ternary(impl.empty);
3232 return Ternary.unknown;
3237 Returns `impl.allocateAll()` if present, `null` otherwise.
3239 override void[] allocateAll() shared
3241 static if (hasMember!(Allocator, "allocateAll"))
3243 return impl.allocateAll();
3251 @nogc nothrow pure @safe
3252 override void incRef() shared
3254 static if (stateSize!Allocator) atomicOp!"+="(rc, 1);
3257 @nogc nothrow pure @trusted
3258 override bool decRef() shared
3260 static if (stateSize!Allocator)
3262 import core.stdc.string : memcpy;
3264 // rc starts as 1 to avoid comparing with size_t(0) - 1
3265 if (atomicOp!"-="(rc, 1) == 0)
3267 static if (indirect)
3269 Allocator* tmp = pimpl;
3274 memcpy(cast(void*) &tmp, cast(void*) &this.impl, Allocator.sizeof);
3276 memcpy(cast(void*) &this.impl, cast(void*) &empty, Allocator.sizeof);
3278 void[] support = (cast(void*) this)[0 .. stateSize!(typeof(this))];
3279 (cast(bool delegate(void[]) @nogc nothrow pure)(&tmp.deallocate))(support);
3292 // Example in intro above
3295 // Allocate an int, initialize it with 42
3296 int* p = theAllocator.make!int(42);
3299 // Destroy and deallocate it
3300 theAllocator.dispose(p);
3302 // Allocate using the global process allocator
3303 p = processAllocator.make!int(100);
3306 // Destroy and deallocate
3307 processAllocator.dispose(p);
3309 // Create an array of 50 doubles initialized to -1.0
3310 double[] arr = theAllocator.makeArray!double(50, -1.0);
3312 // Check internal pointer
3314 assert(theAllocator.resolveInternalPointer(null, result) == Ternary.no);
3315 Ternary r = theAllocator.resolveInternalPointer(arr.ptr, result);
3316 assert(result.ptr is arr.ptr && result.length >= arr.length);
3318 // Append two zeros to it
3319 theAllocator.expandArray(arr, 2, 0.0);
3320 // On second thought, take that back
3321 theAllocator.shrinkArray(arr, 2);
3322 // Destroy and deallocate
3323 theAllocator.dispose(arr);
3328 Stores an allocator object in thread-local storage (i.e. non-`shared` D
3329 global). `ThreadLocal!A` is a subtype of `A` so it appears to implement
3330 `A`'s allocator primitives.
3332 `A` must hold state, otherwise `ThreadLocal!A` refuses instantiation. This
3333 means e.g. `ThreadLocal!Mallocator` does not work because `Mallocator`'s
3334 state is not stored as members of `Mallocator`, but instead is hidden in the
3335 C library implementation.
3338 struct ThreadLocal(A)
3340 static assert(stateSize!A,
3342 ~ " does not have state so it cannot be used with ThreadLocal");
3345 The allocator instance.
3350 `ThreadLocal!A` is a subtype of `A` so it appears to implement `A`'s
3351 allocator primitives.
3353 alias instance this;
3356 `ThreadLocal` disables all constructors. The intended usage is
3357 `ThreadLocal!A.instance`.
3361 @disable this(this);
3368 import std.experimental.allocator.building_blocks.free_list : FreeList;
3369 import std.experimental.allocator.gc_allocator : GCAllocator;
3370 import std.experimental.allocator.mallocator : Mallocator;
3372 static assert(!is(ThreadLocal!Mallocator));
3373 static assert(!is(ThreadLocal!GCAllocator));
3374 alias Allocator = ThreadLocal!(FreeList!(GCAllocator, 0, 8));
3375 auto b = Allocator.instance.allocate(5);
3376 static assert(__traits(hasMember, Allocator, "allocate"));
3382 A binary search tree that uses no allocation of its own. Instead, it relies on
3383 user code to allocate nodes externally. Then `EmbeddedTree`'s primitives wire
3384 the nodes appropriately.
3386 Warning: currently `EmbeddedTree` is not using rebalancing, so it may
3387 degenerate. A red-black tree implementation storing the color with one of the
3388 pointers is planned for the future.
3390 private struct EmbeddedTree(T, alias less)
3400 private Node* insert(Node* n, ref Node* backref)
3403 n.left = n.right = null;
3407 Node* find(Node* data)
3409 for (auto n = root; n; )
3415 else if (less(n, data))
3427 Node* insert(Node* data)
3432 data.left = data.right = null;
3442 // Found insertion point
3443 return insert(data, n.left);
3447 else if (less(n, data))
3451 // Found insertion point
3452 return insert(data, n.right);
3461 if (!n) return null;
3465 Node* remove(Node* data)
3468 Node* parent = null;
3471 if (!n) return null;
3477 else if (less(n, data))
3491 private void remove(Node* n, Node* parent)
3494 assert(!parent || parent.left == n || parent.right == n);
3495 Node** referrer = parent
3496 ? (parent.left == n ? &parent.left : &parent.right)
3500 *referrer = n.right;
3508 // Find the leftmost child in the right subtree
3509 auto leftmost = n.right;
3510 Node** leftmostReferrer = &n.right;
3511 while (leftmost.left)
3513 leftmostReferrer = &leftmost.left;
3514 leftmost = leftmost.left;
3516 // Unlink leftmost from there
3517 *leftmostReferrer = leftmost.right;
3518 // Link leftmost in lieu of n
3519 leftmost.left = n.left;
3520 leftmost.right = n.right;
3521 *referrer = leftmost;
3525 Ternary empty() const
3527 return Ternary(!root);
3532 import std.stdio : writeln;
3533 writeln(typeid(this), " @ ", cast(void*) &this);
3537 void dump(Node* r, uint indent)
3539 import std.stdio : write, writeln;
3540 import std.range : repeat;
3541 import std.array : array;
3543 write(repeat(' ', indent).array);
3549 writeln(r.payload, " @ ", cast(void*) r);
3550 dump(r.left, indent + 3);
3551 dump(r.right, indent + 3);
3556 static bool isBST(Node* r, Node* lb, Node* ub)
3558 if (!r) return true;
3559 if (lb && !less(lb, r)) return false;
3560 if (ub && !less(r, ub)) return false;
3561 return isBST(r.left, lb, r) &&
3562 isBST(r.right, r, ub);
3564 if (isBST(root, null, null)) return;
3573 import std.experimental.allocator.gc_allocator : GCAllocator;
3575 alias a = GCAllocator.instance;
3576 alias Tree = EmbeddedTree!(int, (a, b) => a.payload < b.payload);
3578 assert(t.empty == Ternary.yes);
3579 int[] vals = [ 6, 3, 9, 1, 0, 2, 8, 11 ];
3582 auto n = new Tree.Node(v, null, null);
3583 assert(t.insert(n));
3587 assert(t.empty != Ternary.yes);
3590 Tree.Node n = { v };
3591 assert(t.remove(&n));
3594 assert(t.empty == Ternary.yes);
3599 `InternalPointersTree` adds a primitive on top of another allocator: calling
3600 `resolveInternalPointer(p)` returns the block within which the internal
3601 pointer `p` lies. Pointers right after the end of allocated blocks are also
3602 considered internal.
3604 The implementation stores three additional words with each allocation (one for
3605 the block size and two for search management).
3608 private struct InternalPointersTree(Allocator)
3610 import std.experimental.allocator.building_blocks.affix_allocator : AffixAllocator;
3612 alias Tree = EmbeddedTree!(size_t,
3613 (a, b) => cast(void*) a + a.payload < cast(void*) b);
3614 alias Parent = AffixAllocator!(Allocator, Tree.Node);
3617 private Tree blockMap;
3619 alias alignment = Parent.alignment;
3622 The implementation is available as a public member.
3624 static if (stateSize!Parent) Parent parent;
3625 else alias parent = Parent.instance;
3628 void[] allocate(size_t bytes)
3630 auto r = parent.allocate(bytes);
3631 if (!r.ptr) return r;
3632 Tree.Node* n = &parent.prefix(r);
3634 blockMap.insert(n) || assert(0);
3639 bool deallocate(void[] b)
3641 if (!b.ptr) return true;
3642 Tree.Node* n = &parent.prefix(b);
3643 blockMap.remove(n) || assert(false);
3644 parent.deallocate(b);
3649 static if (hasMember!(Allocator, "reallocate"))
3650 bool reallocate(ref void[] b, size_t s)
3652 auto n = &parent.prefix(b);
3653 assert(n.payload == b.length);
3654 blockMap.remove(n) || assert(0);
3655 if (!parent.reallocate(b, s))
3657 // Failed, must reinsert the same node in the tree
3658 assert(n.payload == b.length);
3659 blockMap.insert(n) || assert(0);
3662 // Insert the new node
3663 n = &parent.prefix(b);
3665 blockMap.insert(n) || assert(0);
3670 Ternary owns(void[] b)
3673 return resolveInternalPointer(b.ptr, result);
3679 return Ternary(blockMap.empty);
3682 /** Returns the block inside which `p` resides, or `null` if the
3683 pointer does not belong.
3685 pure nothrow @safe @nogc
3686 Ternary resolveInternalPointer(const void* p, ref void[] result)
3688 // Must define a custom find
3691 for (auto n = blockMap.root; n; )
3697 else if ((() @trusted => p > (cast(void*) (n + 1)) + n.payload)())
3710 if (!n) return Ternary.no;
3711 result = (() @trusted => (cast(void*) (n + 1))[0 .. n.payload])();
3719 import std.experimental.allocator.mallocator : Mallocator;
3720 import std.random : randomCover;
3722 InternalPointersTree!(Mallocator) a;
3723 int[] vals = [ 6, 3, 9, 1, 2, 8, 11 ];
3727 allox ~= a.allocate(v);
3729 a.blockMap.assertSane;
3733 () pure nothrow @safe {
3735 Ternary r = (() @nogc => a.resolveInternalPointer(&b[0], p))();
3736 assert(&p[0] == &b[0] && p.length >= b.length);
3737 r = a.resolveInternalPointer((() @trusted => &b[0] + b.length)(), p);
3739 /* This line randomly fails on MacOS 12.x x64
3740 * https://issues.dlang.org/show_bug.cgi?id=22660
3741 * Commenting it out until someone can fix it.
3743 //assert(&p[0] == &b[0] && p.length >= b.length);
3745 r = a.resolveInternalPointer((() @trusted => &b[0] + b.length / 2)(), p);
3746 assert(&p[0] == &b[0] && p.length >= b.length);
3747 auto bogus = new void[b.length];
3748 assert(a.resolveInternalPointer(&bogus[0], p) == Ternary.no);
3752 foreach (b; allox.randomCover)
3754 () nothrow @nogc { a.deallocate(b); }();
3757 assert(a.empty == Ternary.yes);
3760 //version (std_allocator_benchmark)
3764 import std.experimental.allocator.building_blocks.null_allocator : NullAllocator;
3765 import std.experimental.allocator.building_blocks.allocator_list : AllocatorList;
3766 import std.experimental.allocator.building_blocks.bitmapped_block : BitmappedBlock;
3767 import std.experimental.allocator.building_blocks.segregator : Segregator;
3768 import std.experimental.allocator.building_blocks.bucketizer : Bucketizer;
3769 import std.experimental.allocator.building_blocks.free_list : FreeList;
3770 import std.experimental.allocator.gc_allocator : GCAllocator;
3771 import std.experimental.allocator.mallocator : Mallocator;
3773 static void testSpeed(A)()
3775 static if (stateSize!A) A a;
3776 else alias a = A.instance;
3781 foreach (i; 0 .. 100_000)
3783 auto j = uniform(0, bufs.length);
3784 switch (uniform(0, 2))
3787 () nothrow @nogc { a.deallocate(bufs[j]); }();
3788 bufs[j] = a.allocate(uniform(0, 4096));
3791 () nothrow @nogc { a.deallocate(bufs[j]); }();
3800 import std.algorithm.comparison : max;
3802 alias FList = FreeList!(GCAllocator, 0, unbounded);
3803 alias A = Segregator!(
3804 8, FreeList!(GCAllocator, 0, 8),
3805 128, Bucketizer!(FList, 1, 128, 16),
3806 256, Bucketizer!(FList, 129, 256, 32),
3807 512, Bucketizer!(FList, 257, 512, 64),
3808 1024, Bucketizer!(FList, 513, 1024, 128),
3809 2048, Bucketizer!(FList, 1025, 2048, 256),
3810 3584, Bucketizer!(FList, 2049, 3584, 512),
3811 4072 * 1024, AllocatorList!(
3812 (size_t n) => BitmappedBlock!(4096)(cast(ubyte[]) GCAllocator.instance.allocate(
3813 max(n, 4072 * 1024)))),
3818 import std.conv : to;
3819 import std.datetime.stopwatch;
3820 import std.algorithm.iteration : map;
3822 if (false) writeln(benchmark!(
3823 testSpeed!NullAllocator,
3824 testSpeed!Mallocator,
3825 testSpeed!GCAllocator,
3826 testSpeed!(ThreadLocal!A),
3828 )(20)[].map!(t => t.to!Duration));
3834 import std.experimental.allocator.building_blocks.free_list : FreeList;
3835 import std.experimental.allocator.building_blocks.region : InSituRegion;
3836 import std.experimental.allocator.building_blocks.fallback_allocator : FallbackAllocator;
3837 import std.experimental.allocator.gc_allocator : GCAllocator;
3838 import std.experimental.allocator.mallocator : Mallocator;
3840 auto a = allocatorObject(Mallocator.instance);
3841 auto b = a.allocate(100);
3842 assert(b.length == 100);
3844 FreeList!(GCAllocator, 0, 8) fl;
3845 auto sa = allocatorObject(fl);
3846 b = a.allocate(101);
3847 assert(b.length == 101);
3849 FallbackAllocator!(InSituRegion!(10240, 64), GCAllocator) fb;
3850 // Doesn't work yet...
3851 //a = allocatorObject(fb);
3852 //b = a.allocate(102);
3853 //assert(b.length == 102);
3860 import std.experimental.allocator.building_blocks.allocator_list : AllocatorList;
3861 import std.experimental.allocator.building_blocks.bitmapped_block : BitmappedBlock;
3862 import std.experimental.allocator.building_blocks.segregator : Segregator;
3863 import std.experimental.allocator.building_blocks.bucketizer : Bucketizer;
3864 import std.experimental.allocator.building_blocks.free_list : FreeList;
3865 import std.experimental.allocator.gc_allocator : GCAllocator;
3867 /// Define an allocator bound to the built-in GC.
3868 auto alloc = allocatorObject(GCAllocator.instance);
3869 auto b = alloc.allocate(42);
3870 assert(b.length == 42);
3871 assert(alloc.deallocate(b));
3873 import std.algorithm.comparison : max;
3874 // Define an elaborate allocator and bind it to the class API.
3875 alias FList = FreeList!(GCAllocator, 0, unbounded);
3876 alias A = ThreadLocal!(
3878 8, FreeList!(GCAllocator, 0, 8),
3879 128, Bucketizer!(FList, 1, 128, 16),
3880 256, Bucketizer!(FList, 129, 256, 32),
3881 512, Bucketizer!(FList, 257, 512, 64),
3882 1024, Bucketizer!(FList, 513, 1024, 128),
3883 2048, Bucketizer!(FList, 1025, 2048, 256),
3884 3584, Bucketizer!(FList, 2049, 3584, 512),
3885 4072 * 1024, AllocatorList!(
3886 (n) => BitmappedBlock!(4096)(cast(ubyte[]) GCAllocator.instance.allocate(
3887 max(n, 4072 * 1024)))),
3892 auto alloc2 = allocatorObject(A.instance);
3893 b = alloc2.allocate(101);
3894 assert(alloc2.deallocate(b));