stdx.allocator.building_blocks.free_list

  • FreeList

    Declaration

    struct FreeList(ParentAllocator, size_t minSize, size_t maxSize = minSize, Flag!"adaptive" adaptive = No.adaptive);

    , stackable on top of another allocator. Allocation requests between and bytes are rounded up to and served from a singly-linked list of buffers deallocated in the past. All other allocations are directed to . Due to the simplicity of free list management, allocations from the free list are fast.

    Discussion

    One instantiation is of particular interest: puts every deallocation in the freelist, and subsequently serves any allocation from the freelist (if not empty). There is no checking of size matching, which would be incorrect for a freestanding allocator but is both correct and fast when an owning allocator on top of the free list allocator (such as ) is already in charge of handling size checking.

    The following methods are defined if defines them, and forward to it: , , .

    • min

      Declaration

      const @property size_t min();

      Returns the smallest allocation size eligible for allocation from the freelist. (If , this is simply an alias for .)

    • min

      Declaration

      @property void min(size_t low);

      If has been instantiated with , then the property is writable. Setting it must precede any allocation.

      Parameters

      size_t low

      new value for

      Precondition: , or and has not yet been initialized. Also, no allocation has been yet done with this allocator.

      Postcondition:

    • max

      Declaration

      const @property size_t max();

      Returns the largest allocation size eligible for allocation from the freelist. (If , this is simply an alias for .) All allocation requests for sizes greater than or equal to and less than or equal to are rounded to and forwarded to the parent allocator. When the block fitting the same constraint gets deallocated, it is put in the freelist with the allocated size assumed to be .

    • max

      Declaration

      @property void max(size_t high);

      If has been instantiated with , then the property is writable. Setting it must precede any allocation.

      Parameters

      size_t high

      new value for

      Precondition: , or and has not yet been initialized. Also . Also, no allocation has been yet done with this allocator.

      Postcondition:

    • parent

      Declaration

      ParentAllocator parent;

      The parent allocator. Depending on whether holds state or not, this is a member variable or an alias for ParentAllocator.instance.

    • alignment

      Declaration

      alias alignment = ParentAllocator.alignment;

      Alignment offered.

    • goodAllocSize

      Declaration

      size_t goodAllocSize(size_t bytes);

      If , returns . Otherwise, returns for sizes in the interval , and otherwise.

      Precondition: If set at runtime, and/or must be initialized appropriately.

      Postcondition:

    • allocate

      Declaration

      void[] allocate(size_t n);

      Allocates memory either off of the free list or from the parent allocator. If is within or if the free list is unchecked (), then the free list is consulted first. If not empty (hit), the block at the front of the free list is removed from the list and returned. Otherwise (miss), a new block of bytes is allocated, truncated to bytes, and returned.

      Parameters

      size_t n

      number of bytes to allocate

      Return Value

      The allocated block, or .

      Precondition: If set at runtime, and/or must be initialized appropriately.

      Postcondition:

    • deallocate

      Declaration

      bool deallocate(void[] block);

      If is within or if the free list is unchecked (), then inserts the block at the front of the free list. For all others, forwards to if is defined.

      Parameters

      void[] block

      Block to deallocate.

      Precondition: If set at runtime, and/or must be initialized appropriately. The block must have been allocated with this freelist, and no dynamic changing of or is allowed to occur between allocation and deallocation.

    • deallocateAll

      Declaration

      bool deallocateAll();

      Defined only if defines . If so, forwards to it and resets the freelist.

    • minimize

      Declaration

      void minimize();

      Nonstandard function that minimizes the memory usage of the freelist by freeing each element in turn. Defined only if defines .

  • ContiguousFreeList

    Declaration

    struct ContiguousFreeList(ParentAllocator, size_t minSize, size_t maxSize = minSize);

    Free list built on top of exactly one contiguous block of memory. The block is assumed to have been allocated with , and is released in 's destructor (unless is ).

    Discussion

    has most advantages of but fewer disadvantages. It has better cache locality because items are closer to one another. It imposes less fragmentation on its parent allocator.

    The disadvantages of over are its pay upfront model (as opposed to 's pay-as-you-go approach), and a hard limit on the number of nodes in the list. Thus, a large number of long- lived objects may occupy the entire block, making it unavailable for serving allocations from the free list. However, an absolute cap on the free list size may be beneficial.

    The options and are not available for .

    Examples

    1. import stdx.allocator.building_blocks.allocator_list : AllocatorList; import stdx.allocator.gc_allocator : GCAllocator; import stdx.allocator.common : unbounded; alias ScalableFreeList = AllocatorList!((n) => ContiguousFreeList!(GCAllocator, 0, unbounded)(4096) );

    • parent

      Declaration

      SParent parent;

      The parent allocator. Depending on whether holds state or not, this is a member variable or an alias for ParentAllocator.instance.

    • alignment

      Declaration

      enum uint alignment;

      Alignment offered.

    • this

      Declaration

      this(ubyte[] buffer);
      this(ParentAllocator parent, ubyte[] buffer);
      this(size_t bytes);
      this(ParentAllocator parent, size_t bytes);
      this(size_t bytes, size_t max);
      this(ParentAllocator parent, size_t bytes, size_t max);
      this(size_t bytes, size_t min, size_t max);
      this(ParentAllocator parent, size_t bytes, size_t min, size_t max);

      Constructors setting up the memory structured as a free list.

      Parameters

      ubyte[] buffer

      Buffer to structure as a free list. If is not , the buffer is assumed to be allocated by and will be freed in the destructor.

      ParentAllocator parent

      Parent allocator. For construction from stateless allocators, use their instance static member.

      size_t bytes

      Bytes (not items) to be allocated for the free list. Memory will be allocated during construction and deallocated in the destructor.

      size_t max

      Maximum size eligible for freelisting. Construction with this parameter is defined only if or .

      size_t min

      Minimum size eligible for freelisting. Construction with this parameter is defined only if . If this condition is met and no parameter is present, is initialized with .

    • goodAllocSize

      Declaration

      size_t goodAllocSize(size_t n);

      If is eligible for freelisting, returns . Otherwise, returns .

      Precondition: If set at runtime, and/or must be initialized appropriately.

      Postcondition:

    • allocate

      Declaration

      void[] allocate(size_t n);

      Allocate bytes of memory. If is eligible for freelist and the freelist is not empty, pops the memory off the free list. In all other cases, uses the parent allocator.

    • owns

      Declaration

      Ternary owns(void[] b);

      Defined if ParentAllocator defines it. Checks whether the block belongs to this allocator.

    • deallocate

      Declaration

      bool deallocate(void[] b);

      Deallocates . If it's of eligible size, it's put on the free list. Otherwise, it's returned to .

      Precondition: has been allocated with this allocator, or is .

    • deallocateAll

      Declaration

      bool deallocateAll();

      Deallocates everything from the parent.

    • empty

      Declaration

      Ternary empty();

      Returns Ternary.yes if no memory is currently allocated with this allocator, Ternary.no otherwise. This method never returns Ternary.unknown.

  • SharedFreeList

    Declaration

    struct SharedFreeList(ParentAllocator, size_t minSize, size_t maxSize = minSize, size_t approxMaxNodes = unbounded);

    FreeList shared across threads. Allocation and deallocation are lock-free. The parameters have the same semantics as for .

    Discussion

    is defined to forward to (it must be also ).

    Examples

    1. import stdx.allocator.common : chooseAtRuntime; import stdx.allocator.mallocator : Mallocator; shared SharedFreeList!(Mallocator, chooseAtRuntime, chooseAtRuntime) a; a.setBounds(64, 128); assert(a.max == 128); assert(a.min == 64);

    Examples

    1. import stdx.allocator.common : chooseAtRuntime; import stdx.allocator.mallocator : Mallocator; shared SharedFreeList!(Mallocator, 50, 50, chooseAtRuntime) a; // Set the maxSize first so setting the minSize doesn't throw a.approxMaxLength = 128; assert(a.approxMaxLength == 128); a.approxMaxLength = 1024; assert(a.approxMaxLength == 1024); a.approxMaxLength = 1; assert(a.approxMaxLength == 1);

    • min

      Declaration

      @property size_t min();
      @property void min(size_t newMinSize);
      @property size_t max();
      @property void max(size_t newMaxSize);
      void setBounds(size_t newMin, size_t newMax);

      Properties for getting (and possibly setting) the bounds. Setting bounds is allowed only once , and before any allocation takes place. Otherwise, the primitives have the same semantics as those of .

    • approxMaxLength

      Declaration

      shared const @property size_t approxMaxLength();
      shared @property void approxMaxLength(size_t x);

      Properties for getting (and possibly setting) the approximate maximum length of a shared freelist.

    • parent

      Declaration

      shared ParentAllocator parent;

      The parent allocator. Depending on whether holds state or not, this is a member variable or an alias for ParentAllocator.instance.

    • alignment

      Declaration

      enum uint alignment;
      shared size_t goodAllocSize(size_t bytes);
      shared const Ternary owns(void[] b);
      shared bool reallocate(ref void[] b, size_t s);
      shared void[] allocate(size_t bytes);
      shared bool deallocate(void[] b);
      shared bool deallocateAll();

      Standard primitives.

    • minimize

      Declaration

      shared void minimize();

      Nonstandard function that minimizes the memory usage of the freelist by freeing each element in turn. Defined only if defines .