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