Bucket Array

Bucket Array is generic, dynamically allocated array storing elements of the same type into heap preallocated memory blocks called "buckets". Compared to regular dynamic arrays, the elements allocated in buckets are stable (the address of each element does not change when array grows).

Internally each bucket contains 64 slots to hold inserted elements, when new element is pushed into the array, the first free slot is used; in case there are no free slots in the bucket, the new one is allocated.

Elements can be also erased from the bucket array, the corresponding slot is just marked as free slot and reused later. No reordering is done when element is erased.

Clearing of the bucket array keeps all already allocated buckets for the later use.

Since not all elements inside the bucket array are not allocated in continuous memory block, special API is provided for iteration over the array.


#import "std/bucket_array"

Entity :: struct {
    id: s32;
    name: string_view;
    health: s32;

main :: fn () s32 {
    using std;
    arr: BucketArray(Entity);
    // Release all allocated memory
    defer bucket_array_terminate(&arr);

    loop i := 0; i < 10; i += 1 {
        // Get the adress of the newly pushed entity element.
        entity_ptr := bucket_array_push(&arr);
        // Initialize with some dummy values.
        entity_ptr.id = i;
        entity_ptr.name = "Martin";
        entity_ptr.health = i * 2;

    // Iterate over all entities
    loop it := bucket_array_begin(&arr); it; it = bucket_array_iter_next(&arr, it) {
        print("%\n", it.value);

    return 0;


Organizing data into buckets leads to less allocations, faster free and better memory locality.


BucketArray :: fn (TElem: type) type

Create a new BucketArray type based on TElem element type.

BucketArray :: struct {
    len: s64;

File: bucket_array.bl


BucketArrayIterator :: fn (TArr: type) type

Create a new BucketArrayIterator type based of TArr bucket array type.

BucketArrayIterator :: struct {
    value: TElem;

File: bucket_array.bl


bucket_array_init :: fn (arr: *?TArr, expected_size: s32, allocator : *Allocator: ) 

Initialize the arr bucket array. It's not necessary to call this method in case the arr is already zero-initialized. The expected_size can be used to preallocate memory for expected_size elements in advance. Memory preallocation is performed using allocator.

File: bucket_array.bl


bucket_array_terminate :: fn (arr: *?TArr) 

Release all memory resources used by the arr and set the arr instance to the default state.

File: bucket_array.bl


bucket_array_push :: fn { impl_push_empty; impl_push; }

Push a new element value at the end of arr or into any available free slot in preallocated buckets. Returns pointer to the pushed element. In case the value is not explicitly specified returned element pointer points to un-initialized memory.


fn (arr: *?TArr, value: bucket_array_typeof_elem(TArr)) *bucket_array_typeof_elem(TArr)
fn (arr: *?TArr) *bucket_array_typeof_elem(TArr)


New memory is allocated only in case there is no free slot left in the preallocated buckets.

File: bucket_array.bl


bucket_array_erase :: fn (arr: *?TArr, value: *) 

Erase previously pushed value from the arr, and asserts in case the value was already erased. Memory for erased value stays allocated and can be used later for new values.

File: bucket_array.bl


bucket_array_begin :: fn (arr: *?TArr) *

Returns bucket array iterator pointing to the first element in the bucket array or null if the array is empty.

File: bucket_array.bl


bucket_array_iter_next :: fn (arr: *?TArr, iter: *) *

Returns bucket array iterator pointing to the next element in the arr or null if there is no next element in the array (we reached the end).

File: bucket_array.bl


bucket_array_clear :: fn (arr: *?TArr) 

Clears the bucket array but keeps the allocated memory for later use.

File: bucket_array.bl


bucket_array_typeof_elem :: fn (TArr: type) type

Returns type of the value stored in TArr type.

File: bucket_array.bl