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