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.
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.
Returns Ternary.yes if the buffer belongs to the parent allocator and Ternary.no otherwise.
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
each node draws memory from the parent allocator; it must support alignedAllocate
alignment of each block and at the same time length of each node
1 import std.experimental.allocator.building_blocks.ascending_page_allocator : AscendingPageAllocator; 2 import std.experimental.allocator.building_blocks.segregator : Segregator; 3 import std.experimental.allocator.building_blocks.bitmapped_block : BitmappedBlock; 4 import std.typecons : Ternary; 5 6 /* 7 In this example we use 'AlignedBlockList' in conjunction with other allocators 8 in order to create a more complex allocator. 9 10 The 'SuperAllocator' uses a 'Segregator' to distribute allocations to sub-allocators, 11 based on the requested size. 12 13 Each sub-allocator is represented by an 'AlignedBlockList' of 'BitmappedBlocks'. 14 Each 'AlignedBlockList' draws memory from a root allocator which in this case is an 'AscendingPageAllocator' 15 16 Such an allocator not only provides good performance, but also a low degree of memory fragmentation. 17 */ 18 alias SuperAllocator = Segregator!( 19 32, 20 AlignedBlockList!(BitmappedBlock!32, AscendingPageAllocator*, 1 << 12), 21 Segregator!( 22 23 64, 24 AlignedBlockList!(BitmappedBlock!64, AscendingPageAllocator*, 1 << 12), 25 Segregator!( 26 27 128, 28 AlignedBlockList!(BitmappedBlock!128, AscendingPageAllocator*, 1 << 12), 29 AscendingPageAllocator* 30 ))); 31 32 SuperAllocator a; 33 auto pageAlloc = AscendingPageAllocator(128 * 4096); 34 35 // Set the parent allocator for all the sub allocators 36 a.allocatorForSize!256 = &pageAlloc; 37 a.allocatorForSize!128.parent = &pageAlloc; 38 a.allocatorForSize!64.parent = &pageAlloc; 39 a.allocatorForSize!32.parent = &pageAlloc; 40 41 enum testNum = 10; 42 void[][testNum] buf; 43 44 // Allocations of size 32 will go to the first 'AlignedBlockList' 45 foreach (j; 0 .. testNum) 46 { 47 buf[j] = a.allocate(32); 48 assert(buf[j].length == 32); 49 50 // This is owned by the first 'AlignedBlockList' 51 assert(a.allocatorForSize!32.owns(buf[j]) == Ternary.yes); 52 } 53 54 // Free the memory 55 foreach (j; 0 .. testNum) 56 assert(a.deallocate(buf[j])); 57 58 // Allocations of size 64 will go to the second 'AlignedBlockList' 59 foreach (j; 0 .. testNum) 60 { 61 buf[j] = a.allocate(64); 62 assert(buf[j].length == 64); 63 64 // This is owned by the second 'AlignedBlockList' 65 assert(a.allocatorForSize!64.owns(buf[j]) == Ternary.yes); 66 } 67 68 // Free the memory 69 foreach (j; 0 .. testNum) 70 assert(a.deallocate(buf[j])); 71 72 // Allocations of size 128 will go to the third 'AlignedBlockList' 73 foreach (j; 0 .. testNum) 74 { 75 buf[j] = a.allocate(128); 76 assert(buf[j].length == 128); 77 78 // This is owned by the third 'AlignedBlockList' 79 assert(a.allocatorForSize!128.owns(buf[j]) == Ternary.yes); 80 } 81 82 // Free the memory 83 foreach (j; 0 .. testNum) 84 assert(a.deallocate(buf[j])); 85 86 // Allocations which exceed 128, will go to the 'AscendingPageAllocator*' 87 void[] b = a.allocate(256); 88 assert(b.length == 256); 89 a.deallocate(b);
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.
Although allocations are in theory served in linear searching time, deallocate calls take O(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.