1 /**
2 This module defines `TypedAllocator`, a statically-typed allocator that
3 aggregates multiple untyped allocators and uses them depending on the static
4 properties of the types allocated. For example, distinct allocators may be used
5 for thread-local vs. thread-shared data, or for fixed-size data (`struct`,
6 `class` objects) vs. resizable data (arrays).
7 
8 Macros:
9 T2=$(TR <td style="text-align:left">$(D $1)</td> $(TD $(ARGS $+)))
10 */
11 
12 module stdx.allocator.typed;
13 
14 import stdx.allocator;
15 import stdx.allocator.common;
16 import std.range.primitives : isInputRange, isForwardRange, save, empty,
17     front, popFront;
18 import std.typecons : Flag, Yes, No;
19 
20 /**
21 Allocation-related flags dictated by type characteristics. `TypedAllocator`
22 deduces these flags from the type being allocated and uses the appropriate
23 allocator accordingly.
24 */
25 enum AllocFlag : uint
26 {
27     init = 0,
28     /**
29     Fixed-size allocation (unlikely to get reallocated later). Examples: `int`,
30     `double`, any `struct` or `class` type. By default it is assumed that the
31     allocation is variable-size, i.e. susceptible to later reallocation
32     (for example all array types). This flag is advisory, i.e. in-place resizing
33     may be attempted for `fixedSize` allocations and may succeed. The flag is
34     just a hint to the compiler it may use allocation strategies that work well
35     with objects of fixed size.
36     */
37     fixedSize = 1,
38     /**
39     The type being allocated embeds no pointers. Examples: `int`, `int[]`, $(D
40     Tuple!(int, float)). The implicit conservative assumption is that the type
41     has members with indirections so it needs to be scanned if garbage
42     collected. Example of types with pointers: `int*[]`, $(D Tuple!(int,
43     string)).
44     */
45     hasNoIndirections = 4,
46     /**
47     By default it is conservatively assumed that allocated memory may be `cast`
48     to `shared`, passed across threads, and deallocated in a different thread
49     than the one that allocated it. If that's not the case, there are two
50     options. First, `immutableShared` means the memory is allocated for
51     `immutable` data and will be deallocated in the same thread it was
52     allocated in. Second, `threadLocal` means the memory is not to be shared
53     across threads at all. The two flags cannot be simultaneously present.
54     */
55     immutableShared = 8,
56     /// ditto
57     threadLocal = 16,
58 }
59 
60 /**
61 `TypedAllocator` acts like a chassis on which several specialized allocators
62 can be assembled. To let the system make a choice about a particular kind of
63 allocation, use `Default` for the respective parameters.
64 
65 There is a hierarchy of allocation kinds. When an allocator is implemented for
66 a given combination of flags, it is used. Otherwise, the next down the list is
67 chosen.
68 
69 $(BOOKTABLE ,
70 
71 $(TR $(TH `AllocFlag` combination) $(TH Description))
72 
73 $(T2 AllocFlag.threadLocal |$(NBSP)AllocFlag.hasNoIndirections
74 |$(NBSP)AllocFlag.fixedSize,
75 This is the most specific allocation policy: the memory being allocated is
76 thread local, has no indirections at all, and will not be reallocated. Examples
77 of types fitting this description: `int`, `double`, $(D Tuple!(int, long)), but
78 not $(D Tuple!(int, string)), which contains an indirection.)
79 
80 $(T2 AllocFlag.threadLocal |$(NBSP)AllocFlag.hasNoIndirections,
81 As above, but may be reallocated later. Examples of types fitting this
82 description are $(D int[]), $(D double[]), $(D Tuple!(int, long)[]), but not
83 $(D Tuple!(int, string)[]), which contains an indirection.)
84 
85 $(T2 AllocFlag.threadLocal,
86 As above, but may embed indirections. Examples of types fitting this
87 description are $(D int*[]), $(D Object[]), $(D Tuple!(int, string)[]).)
88 
89 $(T2 AllocFlag.immutableShared |$(NBSP)AllocFlag.hasNoIndirections
90 |$(NBSP)AllocFlag.fixedSize,
91 The type being allocated is `immutable` and has no pointers. The thread that
92 allocated it must also deallocate it. Example: `immutable(int)`.)
93 
94 $(T2 AllocFlag.immutableShared |$(NBSP)AllocFlag.hasNoIndirections,
95 As above, but the type may be appended to in the future. Example: `string`.)
96 
97 $(T2 AllocFlag.immutableShared,
98 As above, but the type may embed references. Example: `immutable(Object)[]`.)
99 
100 $(T2 AllocFlag.hasNoIndirections |$(NBSP)AllocFlag.fixedSize,
101 The type being allocated may be shared across threads, embeds no indirections,
102 and has fixed size.)
103 
104 $(T2 AllocFlag.hasNoIndirections,
105 The type being allocated may be shared across threads, may embed indirections,
106 and has variable size.)
107 
108 $(T2 AllocFlag.fixedSize,
109 The type being allocated may be shared across threads, may embed indirections,
110 and has fixed size.)
111 
112 $(T2 0, The most conservative/general allocation: memory may be shared,
113 deallocated in a different thread, may or may not be resized, and may embed
114 references.)
115 )
116 
117 Params:
118 PrimaryAllocator = The default allocator.
119 Policies = Zero or more pairs consisting of an `AllocFlag` and an allocator
120 type.
121 */
122 struct TypedAllocator(PrimaryAllocator, Policies...)
123 {
124     import std.algorithm.sorting : isSorted;
125     import std.meta : AliasSeq;
126     import std.typecons : Tuple;
127 
128     static assert(Policies.length == 0 || isSorted([Stride2!Policies]));
129 
130     private template Stride2(T...)
131     {
132         static if (T.length >= 2)
133         {
134             alias Stride2 = AliasSeq!(T[0], Stride2!(T[2 .. $]));
135         }
136         else
137         {
138             alias Stride2 = AliasSeq!(T[0 .. $]);
139         }
140     }
141 
142     // state
143     static if (stateSize!PrimaryAllocator) private PrimaryAllocator primary;
144     else alias primary = PrimaryAllocator.instance;
145     static if (Policies.length > 0)
146         private Tuple!(Stride2!(Policies[1 .. $])) extras;
147 
148     private static bool match(uint have, uint want)
149     {
150         enum uint maskAway =
151             ~(AllocFlag.immutableShared | AllocFlag.threadLocal);
152         // Do we offer thread local?
153         if (have & AllocFlag.threadLocal)
154         {
155             if (want & AllocFlag.threadLocal)
156                 return match(have & maskAway, want & maskAway);
157             return false;
158         }
159         if (have & AllocFlag.immutableShared)
160         {
161             // Okay to ask for either thread local or immutable shared
162             if (want & (AllocFlag.threadLocal
163                     | AllocFlag.immutableShared))
164                 return match(have & maskAway, want & maskAway);
165             return false;
166         }
167         // From here on we have full-blown thread sharing.
168         if (have & AllocFlag.hasNoIndirections)
169         {
170             if (want & AllocFlag.hasNoIndirections)
171                 return match(have & ~AllocFlag.hasNoIndirections,
172                     want & ~AllocFlag.hasNoIndirections);
173             return false;
174         }
175         // Fixed size or variable size both match.
176         return true;
177     }
178 
179     /**
180     Given `flags` as a combination of `AllocFlag` values, or a type `T`, returns
181     the allocator that's a closest fit in capabilities.
182     */
183     auto ref allocatorFor(uint flags)()
184     {
185         static if (Policies.length == 0 || !match(Policies[0], flags))
186         {
187             return primary;
188         }
189         else static if (Policies.length && match(Policies[$ - 2], flags))
190         {
191             return extras[$ - 1];
192         }
193         else
194         {
195             foreach (i, choice; Stride2!Policies)
196             {
197                 static if (!match(choice, flags))
198                 {
199                     return extras[i - 1];
200                 }
201             }
202             assert(0);
203         }
204     }
205 
206     /// ditto
207     auto ref allocatorFor(T)()
208     {
209         static if (is(T == void[]))
210         {
211             return primary;
212         }
213         else
214         {
215             return allocatorFor!(type2flags!T)();
216         }
217     }
218 
219     /**
220     Given a type `T`, returns its allocation-related flags as a combination of
221     `AllocFlag` values.
222     */
223     static uint type2flags(T)()
224     {
225         uint result;
226         static if (is(T == immutable))
227             result |= AllocFlag.immutableShared;
228         else static if (is(T == shared))
229             result |= AllocFlag.forSharing;
230         static if (!is(T == U[], U))
231             result |= AllocFlag.fixedSize;
232         import std.traits : hasIndirections;
233         static if (!hasIndirections!T)
234             result |= AllocFlag.hasNoIndirections;
235         return result;
236     }
237 
238     /**
239     Dynamically allocates (using the appropriate allocator chosen with
240     `allocatorFor!T`) and then creates in the memory allocated an object of
241     type `T`, using `args` (if any) for its initialization. Initialization
242     occurs in the memory allocated and is otherwise semantically the same as
243     `T(args)`. (Note that using `make!(T[])` creates a pointer to an
244     (empty) array of `T`s, not an array. To allocate and initialize an
245     array, use `makeArray!T` described below.)
246 
247     Params:
248     T = Type of the object being created.
249     args = Optional arguments used for initializing the created object. If not
250     present, the object is default constructed.
251 
252     Returns: If `T` is a class type, returns a reference to the created `T`
253     object. Otherwise, returns a `T*` pointing to the created object. In all
254     cases, returns `null` if allocation failed.
255 
256     Throws: If `T`'s constructor throws, deallocates the allocated memory and
257     propagates the exception.
258     */
259     auto make(T, A...)(auto ref A args)
260     {
261         return .make!T(allocatorFor!T, args);
262     }
263 
264     /**
265     Create an array of `T` with `length` elements. The array is either
266     default-initialized, filled with copies of `init`, or initialized with
267     values fetched from `range`.
268 
269     Params:
270     T = element type of the array being created
271     length = length of the newly created array
272     init = element used for filling the array
273     range = range used for initializing the array elements
274 
275     Returns:
276     The newly-created array, or `null` if either `length` was `0` or
277     allocation failed.
278 
279     Throws:
280     The first two overloads throw only if the used allocator's primitives do.
281     The overloads that involve copy initialization deallocate memory and propagate the exception if the copy operation throws.
282     */
283     T[] makeArray(T)(size_t length)
284     {
285         return .makeArray!T(allocatorFor!(T[]), length);
286     }
287 
288     /// Ditto
289     T[] makeArray(T)(size_t length, auto ref T init)
290     {
291         return .makeArray!T(allocatorFor!(T[]), init, length);
292     }
293 
294     /// Ditto
295     T[] makeArray(T, R)(R range)
296     if (isInputRange!R)
297     {
298         return .makeArray!T(allocatorFor!(T[]), range);
299     }
300 
301     /**
302     Grows `array` by appending `delta` more elements. The needed memory is
303     allocated using the same allocator that was used for the array type. The
304     extra elements added are either default-initialized, filled with copies of
305     `init`, or initialized with values fetched from `range`.
306 
307     Params:
308     T = element type of the array being created
309     array = a reference to the array being grown
310     delta = number of elements to add (upon success the new length of `array`
311     is $(D array.length + delta))
312     init = element used for filling the array
313     range = range used for initializing the array elements
314 
315     Returns:
316     `true` upon success, `false` if memory could not be allocated. In the
317     latter case `array` is left unaffected.
318 
319     Throws:
320     The first two overloads throw only if the used allocator's primitives do.
321     The overloads that involve copy initialization deallocate memory and
322     propagate the exception if the copy operation throws.
323     */
324     bool expandArray(T)(ref T[] array, size_t delta)
325     {
326         return .expandArray(allocatorFor!(T[]), array, delta);
327     }
328     /// Ditto
329     bool expandArray(T)(T[] array, size_t delta, auto ref T init)
330     {
331         return .expandArray(allocatorFor!(T[]), array, delta, init);
332     }
333     /// Ditto
334     bool expandArray(T, R)(ref T[] array, R range)
335     if (isInputRange!R)
336     {
337         return .expandArray(allocatorFor!(T[]), array, range);
338     }
339 
340     /**
341     Shrinks an array by `delta` elements using `allocatorFor!(T[])`.
342 
343     If $(D arr.length < delta), does nothing and returns `false`. Otherwise,
344     destroys the last $(D arr.length - delta) elements in the array and then
345     reallocates the array's buffer. If reallocation fails, fills the array with
346     default-initialized data.
347 
348     Params:
349     T = element type of the array being created
350     arr = a reference to the array being shrunk
351     delta = number of elements to remove (upon success the new length of
352     `arr` is $(D arr.length - delta))
353 
354     Returns:
355     `true` upon success, `false` if memory could not be reallocated. In the
356     latter case $(D arr[$ - delta .. $]) is left with default-initialized
357     elements.
358 
359     Throws:
360     The first two overloads throw only if the used allocator's primitives do.
361     The overloads that involve copy initialization deallocate memory and
362     propagate the exception if the copy operation throws.
363     */
364     bool shrinkArray(T)(ref T[] arr, size_t delta)
365     {
366         return .shrinkArray(allocatorFor!(T[]), arr, delta);
367     }
368 
369     /**
370     Destroys and then deallocates (using `allocatorFor!T`) the object pointed
371     to by a pointer, the class object referred to by a `class` or `interface`
372     reference, or an entire array. It is assumed the respective entities had
373     been allocated with the same allocator.
374     */
375     void dispose(T)(T* p)
376     {
377         return .dispose(allocatorFor!T, p);
378     }
379     /// Ditto
380     void dispose(T)(T p)
381     if (is(T == class) || is(T == interface))
382     {
383         return .dispose(allocatorFor!T, p);
384     }
385     /// Ditto
386     void dispose(T)(T[] array)
387     {
388         return .dispose(allocatorFor!(T[]), array);
389     }
390 }
391 
392 ///
393 @system unittest
394 {
395     import stdx.allocator.gc_allocator : GCAllocator;
396     import stdx.allocator.mallocator : Mallocator;
397     import stdx.allocator.mmap_allocator : MmapAllocator;
398     alias MyAllocator = TypedAllocator!(GCAllocator,
399         AllocFlag.fixedSize | AllocFlag.threadLocal, Mallocator,
400         AllocFlag.fixedSize | AllocFlag.threadLocal
401                 | AllocFlag.hasNoIndirections,
402             MmapAllocator,
403     );
404     MyAllocator a;
405     auto b = a.allocatorFor!0();
406     static assert(is(typeof(b) == GCAllocator));
407     enum f1 = AllocFlag.fixedSize | AllocFlag.threadLocal;
408     auto c = a.allocatorFor!f1();
409     static assert(is(typeof(c) == Mallocator));
410     enum f2 = AllocFlag.fixedSize | AllocFlag.threadLocal;
411     static assert(is(typeof(a.allocatorFor!f2()) == Mallocator));
412     // Partial match
413     enum f3 = AllocFlag.threadLocal;
414     static assert(is(typeof(a.allocatorFor!f3()) == Mallocator));
415 
416     int* p = a.make!int;
417     scope(exit) a.dispose(p);
418     int[] arr = a.makeArray!int(42);
419     scope(exit) a.dispose(arr);
420     assert(a.expandArray(arr, 3));
421     assert(a.shrinkArray(arr, 4));
422 }