View source code
Display the source code in std/experimental/allocator/building_blocks/aligned_block_list.d from which this page was generated on github.
Report a bug
If you spot a problem with this page, click here to create a Bugzilla issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

Struct std.experimental.allocator.building_blocks.aligned_block_list.AlignedBlockList

AlignedBlockList represents a wrapper around a chain of allocators, allowing for fast deallocations and preserving a low degree of fragmentation. The allocator holds internally a doubly linked list of Allocator objects, which will serve allocations in a most-recently-used fashion. Most recent allocators used for allocate calls, will be moved to the front of the list.

struct AlignedBlockList(Allocator, ParentAllocator, ulong theAlignment = 1 << 21) ;

Although allocations are in theory served in linear searching time, deallocate calls take Ο(1) time, by using aligned allocations. ParentAllocator must implement alignedAllocate and it must be able to allocate theAlignment bytes at the same alignment. Each aligned allocation done by ParentAllocator will contain metadata for an Allocator, followed by its payload.

Methods

NameDescription
allocate (n) Returns a chunk of memory of size n It finds the first node in the AlignedBlockNode list which has available memory, and moves it to the front of the list.
deallocate (b) Deallocates the buffer b given as parameter. Deallocations take place in constant time, regardless of the number of nodes in the list. b.ptr is rounded down to the nearest multiple of the alignment to quickly find the corresponding AlignedBlockNode.
owns (b) Returns Ternary.yes if the buffer belongs to the parent allocator and Ternary.no otherwise.

Parameters

NameDescription
Allocator the allocator which is used to manage each node; it must have a constructor which receives ubyte[] and it must not have any parent allocators, except for the NullAllocator
ParentAllocator each node draws memory from the parent allocator; it must support alignedAllocate
theAlignment alignment of each block and at the same time length of each node

Example

import std.experimental.allocator.building_blocks.ascending_page_allocator : AscendingPageAllocator;
import std.experimental.allocator.building_blocks.segregator : Segregator;
import std.experimental.allocator.building_blocks.bitmapped_block : BitmappedBlock;
import std.typecons : Ternary;

/*
In this example we use 'AlignedBlockList' in conjunction with other allocators
in order to create a more complex allocator.

The 'SuperAllocator' uses a 'Segregator' to distribute allocations to sub-allocators,
based on the requested size.

Each sub-allocator is represented by an 'AlignedBlockList' of 'BitmappedBlocks'.
Each 'AlignedBlockList' draws memory from a root allocator which in this case is an 'AscendingPageAllocator'

Such an allocator not only provides good performance, but also a low degree of memory fragmentation.
*/
alias SuperAllocator = Segregator!(
    32,
    AlignedBlockList!(BitmappedBlock!32, AscendingPageAllocator*, 1 << 12),
    Segregator!(

    64,
    AlignedBlockList!(BitmappedBlock!64, AscendingPageAllocator*, 1 << 12),
    Segregator!(

    128,
    AlignedBlockList!(BitmappedBlock!128, AscendingPageAllocator*, 1 << 12),
    AscendingPageAllocator*
)));

SuperAllocator a;
auto pageAlloc = AscendingPageAllocator(128 * 4096);

// Set the parent allocator for all the sub allocators
a.allocatorForSize!256 = &pageAlloc;
a.allocatorForSize!128.parent = &pageAlloc;
a.allocatorForSize!64.parent = &pageAlloc;
a.allocatorForSize!32.parent = &pageAlloc;

enum testNum = 10;
void[][testNum] buf;

// Allocations of size 32 will go to the first 'AlignedBlockList'
foreach (j; 0 .. testNum)
{
    buf[j] = a.allocate(32);
    writeln(buf[j].length); // 32

    // This is owned by the first 'AlignedBlockList'
    writeln(a.allocatorForSize!32.owns(buf[j])); // Ternary.yes
}

// Free the memory
foreach (j; 0 .. testNum)
    assert(a.deallocate(buf[j]));

// Allocations of size 64 will go to the second 'AlignedBlockList'
foreach (j; 0 .. testNum)
{
    buf[j] = a.allocate(64);
    writeln(buf[j].length); // 64

    // This is owned by the second 'AlignedBlockList'
    writeln(a.allocatorForSize!64.owns(buf[j])); // Ternary.yes
}

// Free the memory
foreach (j; 0 .. testNum)
    assert(a.deallocate(buf[j]));

// Allocations of size 128 will go to the third 'AlignedBlockList'
foreach (j; 0 .. testNum)
{
    buf[j] = a.allocate(128);
    writeln(buf[j].length); // 128

    // This is owned by the third 'AlignedBlockList'
    writeln(a.allocatorForSize!128.owns(buf[j])); // Ternary.yes
}

// Free the memory
foreach (j; 0 .. testNum)
    assert(a.deallocate(buf[j]));

// Allocations which exceed 128, will go to the 'AscendingPageAllocator*'
void[] b = a.allocate(256);
writeln(b.length); // 256
a.deallocate(b);

Authors

License