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