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.

Example

#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;
}

std.BucketArray

BucketArray :: fn (TElem: type) type

Create a new BucketArray type based on TElem element type.

BucketArray :: struct {
    len: s64;
}

File: bucket_array.bl

std.BucketArrayIterator

BucketArrayIterator :: fn (TArr: type) type

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

BucketArrayIterator :: struct {
    value: TElem;
}

File: bucket_array.bl

std.bucket_array_init

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

std.bucket_array_terminate

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

std.bucket_array_push

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.

Overloads:

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

File: bucket_array.bl

std.bucket_array_erase

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

std.bucket_array_begin

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

std.bucket_array_iter_next

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

std.bucket_array_clear

bucket_array_clear :: fn (arr: *?TArr) 

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

File: bucket_array.bl

std.bucket_array_typeof_elem

bucket_array_typeof_elem :: fn (TArr: type) type

Returns type of the value stored in TArr type.

File: bucket_array.bl