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;
}
Note: Organizing data into buckets leads to less allocations, faster free and better memory locality.
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: null)
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)
Note: New memory is allocated only in case there is no free slot left in the preallocated buckets.
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