libphobos/src/std/experimental/allocator/typed.d

   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 std.experimental.allocator.typed;
  13
  14 import std.experimental.allocator;
  15 import std.experimental.allocator.common;
  16 import std.range : isInputRange, isForwardRange, walkLength, save, empty,
  17     front, popFront;
  18 import std.traits : isPointer, hasElaborateDestructor;
  19 import std.typecons : Flag, Yes, No;
  20
  21 /**
  22 Allocation-related flags dictated by type characteristics. `TypedAllocator`
  23 deduces these flags from the type being allocated and uses the appropriate
  24 allocator accordingly.
  25 */
  26 enum 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
  63 can be assembled. To let the system make a choice about a particular kind of
  64 allocation, use `Default` for the respective parameters.
  65
  66 There is a hierarchy of allocation kinds. When an allocator is implemented for
  67 a given combination of flags, it is used. Otherwise, the next down the list is
  68 chosen.
  69
  70 $(BOOKTABLE ,
  71
  72 $(TR $(TH `AllocFlag` combination) $(TH Description))
  73
  74 $(T2 AllocFlag.threadLocal |$(NBSP)AllocFlag.hasNoIndirections
  75 |$(NBSP)AllocFlag.fixedSize,
  76 This is the most specific allocation policy: the memory being allocated is
  77 thread local, has no indirections at all, and will not be reallocated. Examples
  78 of types fitting this description: `int`, `double`, $(D Tuple!(int, long)), but
  79 not $(D Tuple!(int, string)), which contains an indirection.)
  80
  81 $(T2 AllocFlag.threadLocal |$(NBSP)AllocFlag.hasNoIndirections,
  82 As above, but may be reallocated later. Examples of types fitting this
  83 description 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,
  87 As above, but may embed indirections. Examples of types fitting this
  88 description are $(D int*[]), $(D Object[]), $(D Tuple!(int, string)[]).)
  89
  90 $(T2 AllocFlag.immutableShared |$(NBSP)AllocFlag.hasNoIndirections
  91 |$(NBSP)AllocFlag.fixedSize,
  92 The type being allocated is `immutable` and has no pointers. The thread that
  93 allocated it must also deallocate it. Example: `immutable(int)`.)
  94
  95 $(T2 AllocFlag.immutableShared |$(NBSP)AllocFlag.hasNoIndirections,
  96 As above, but the type may be appended to in the future. Example: `string`.)
  97
  98 $(T2 AllocFlag.immutableShared,
  99 As above, but the type may embed references. Example: `immutable(Object)[]`.)
 100
 101 $(T2 AllocFlag.hasNoIndirections |$(NBSP)AllocFlag.fixedSize,
 102 The type being allocated may be shared across threads, embeds no indirections,
 103 and has fixed size.)
 104
 105 $(T2 AllocFlag.hasNoIndirections,
 106 The type being allocated may be shared across threads, may embed indirections,
 107 and has variable size.)
 108
 109 $(T2 AllocFlag.fixedSize,
 110 The type being allocated may be shared across threads, may embed indirections,
 111 and has fixed size.)
 112
 113 $(T2 0, The most conservative/general allocation: memory may be shared,
 114 deallocated in a different thread, may or may not be resized, and may embed
 115 references.)
 116 )
 117
 118 Params:
 119 PrimaryAllocator = The default allocator.
 120 Policies = Zero or more pairs consisting of an `AllocFlag` and an allocator
 121 type.
 122 */
 123 struct 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 }