CircularBlocks

Represents an expanding circular buffer implemented as blocks of elements of T.

The elements are added to the end, removed from the front, and are never moved around on the buffers.

If user blocks are provided, those blocks are used for the elements until there is no more room on them, in which case new blocks are allocated from the GC heap.

struct CircularBlocks (

) {

this(size_t heapBlockCapacity);

this(ubyte[] buffer);

this(ubyte[][] buffers);

this(ubyte[N][M] buffers);

~this();

void toString(void delegate(in char[]) sink);

size_t capacity();

size_t length();

void opOpAssign(T element);

void moveEmplace(T element);

void emplaceBack(Args args);

inout(T) opIndex(size_t index);

size_t opDollar();

auto opSlice(size_t from, size_t to);

auto opSlice();

void removeFrontN(size_t n);

auto heapBlockOccupancy();

size_t compact();

}

Constructors

this this(size_t heapBlockCapacity): Construct an object without any user-provided blocks. All blocks will be allocated dynamically.
this this(ubyte[] buffer): Construct an object that will use the provided buffer
this this(ubyte[][] buffers)
this(ubyte[N][M] buffers): Construct an object that will use the provided buffers

Destructor

~this ~this(): Clears all blocks in reverse order

Postblit

this(this) this(this): Undocumented in source.

Members

Functions

capacity size_t capacity(): Total element capacity
compact size_t compact(): Release all unoccupied heap blocks from the blocks array
emplaceBack void emplaceBack(Args args): Construct a new _element at the end
heapBlockOccupancy auto heapBlockOccupancy(): Total number of heap blocks and the number of those that are occupied by at least one element
length size_t length(): Number of elements currently available
moveEmplace void moveEmplace(T element): Move an _element to the end
opDollar size_t opDollar(): Number of elements in the block
opIndex inout(T) opIndex(size_t index): Return a reference to an element
opOpAssign void opOpAssign(T element): Append an _element
opSlice auto opSlice(size_t from, size_t to): A range providing access _to the specified elements.
opSlice auto opSlice(): A range to all elements; the same as [0..$]
removeFrontN void removeFrontN(size_t n): Remove elements from the head of the block
toString void toString(void delegate(in char[]) sink): String representation of this object useful mostly for debugging

Variables

heapAllocations size_t heapAllocations;: Undocumented in source.

Parameters

T: the type of the elements to store

Examples

// This example starts with user-provided buffers. (It is possible to
// provide a single buffer but that case would need to allocate at least one
// heap buffer later e.g. in a sliding window use case.)

enum size = 42;
enum count = 2;
ubyte[size][count] buffers;

// Create a circular buffer of ints using those buffers
auto c = CircularBlocks!int(buffers);

// We can't be certain about total capacity because initial parts of the
// buffers may not be used due to alignment requirements. At least make sure
// the tests will be valid
const initialCapacity = c.capacity;
assert(initialCapacity > 0, "Invalid unittest");

// Populate with some elements
iota(initialCapacity).each!(i => c ~= i.to!int);

// All capacity should be utilized at this point
c.length.shouldBe(c.capacity);

// As all elements are on provided buffers so far, there should be no heap
// allocation yet
c.heapBlockOccupancy.total.shouldBe(0);
c.heapBlockOccupancy.occupied.shouldBe(0);

// Adding one more element should allocate one heap block
c ~= 42;
c.heapBlockOccupancy.total.shouldBe(1);
c.heapBlockOccupancy.occupied.shouldBe(1);
assert(c.capacity > initialCapacity);

// Remove all elements
c.removeFrontN(c.length);
c.length.shouldBe(0);
c.heapBlockOccupancy.total.shouldBe(1);
c.heapBlockOccupancy.occupied.shouldBe(0);

// Release the unoccupied heap blocks
c.compact();
c.heapBlockOccupancy.total.shouldBe(0);
c.heapBlockOccupancy.occupied.shouldBe(0);

// Because we started with user buffers, the capacity should never be less
// than initial capacity
c.capacity.shouldBe(initialCapacity);

// This example uses a single user-provided buffer. It is inevitable that
// there will be at least one heap block allocation if more elements added
// than the capacity of the user-provided buffer.

ubyte[100] buffer;
auto c = CircularBlocks!string(buffer[]);

iota(c.capacity).each!(_ => c ~= "hi");
c.length.shouldBe(c.capacity);

// There should be no heap block allocation
c.heapBlockOccupancy.total.shouldBe(0);
c.heapBlockOccupancy.occupied.shouldBe(0);

// This example does not start with any user-provided buffer
const heapBlockCapacity = 100;
auto c = CircularBlocks!double(heapBlockCapacity);

// Due to lazy allocation, no heap block should be allocated yet
c.capacity.shouldBe(0);

// Adding elements should cause heap block allocations
c ~= 1;
assert(c.capacity != 0);
c.heapBlockOccupancy.total.shouldBe(1);
c.heapBlockOccupancy.occupied.shouldBe(1);

// When user-provided buffers are sufficiently large for a sliding window of
// elements, no heap block should be allocated

ubyte[64][2] buffers;
auto c = CircularBlocks!int(buffers);
assert(c.capacity != 0);

// Start with some elements filling half the capacity
iota(c.capacity / 2).each!(i => c ~= i.to!int);

// Use the rest of the capacity as the width of a sliding window
const windowWidth = c.capacity - c.length;

// Add and remove equal number of elements for many number of times
foreach (i; 0 .. 117)
{
    iota(windowWidth).each!(i => c ~= i.to!int);
    // Prove that buffer is completely full after the additions
    c.length.shouldBe(c.capacity);
    c.removeFrontN(windowWidth);
}

// No heap block should have been allocated
c.heapBlockOccupancy.total.shouldBe(0);