(array: *Bucket_Array)
Frees every bucket through the array's allocator and empties the array, ready for reuse.
array: Bucket_Array(int, 4);
bucket_array_add(*array, 1);
bucket_array_reset(*array);
assert(array.count == 0);#import "Bucket_Array";
A collection with stable element addresses, grown a fixed-size bucket at a time.
nodes: Bucket_Array(int, 64);
locator, node := bucket_array_add(*nodes, 1);
for 2..1000 bucket_array_add(*nodes, it);
assert(node.* == 1); // the address did not change while the array grew
assert(bucket_array_find(*nodes, locator) == 1);
bucket_array_reset(*nodes);Procedures#
(array: *Bucket_Array, item: array.type) -> (Bucket_Locator, pointer: *array.type)
Stores item in the first free slot and returns its Bucket_Locator and a pointer to the stored copy.
array: Bucket_Array(int, 2);
a, pa := bucket_array_add(*array, 10);
b, pb := bucket_array_add(*array, 20);
c, pc := bucket_array_add(*array, 30); // starts a second bucket
assert(array.count == 3 && c.bucket_index == 1);
pa.* += 1; // pointers stay valid as the array grows
assert(bucket_array_find(*array, a) == 11);
bucket_array_reset(*array);(array: *Bucket_Array, locator: Bucket_Locator) -> array.type
The element at locator, by value. Fails an assert when the locator is out of range or names a free slot.
array: Bucket_Array(string, 4);
locator := bucket_array_add(*array, "hi");
assert(bucket_array_find(*array, locator) == "hi");
bucket_array_reset(*array);(array: *Bucket_Array, locator: Bucket_Locator) -> *array.type
A pointer to the element at locator, to change it in place. Fails an assert when the locator is out of range or names a free slot.
array: Bucket_Array(int, 4);
locator := bucket_array_add(*array, 1);
bucket_array_find_pointer(*array, locator).* = 5;
assert(bucket_array_find(*array, locator) == 5);
bucket_array_reset(*array);(array: *Bucket_Array, locator: Bucket_Locator)
Removes the element at locator, freeing its slot for a later add. Fails an assert when the locator names a free or invalid slot.
array: Bucket_Array(int, 2);
for 1..4 bucket_array_add(*array, it);
for value: array {
if value % 2 == 0 remove value;
}
assert(array.count == 2);
bucket_array_reset(*array);(array: *Bucket_Array, $initialize := true) -> (*array.type, Bucket_Locator)
Claims a free slot and returns a pointer to it and its locator; the lower-level half of bucket_array_add.
array: Bucket_Array(int, 4);
slot, locator := find_and_occupy_empty_slot(*array);
assert(slot.* == 0 && array.count == 1);
slot.* = 9;
assert(bucket_array_find(*array, locator) == 9);
bucket_array_reset(*array);(array: *$T/Bucket_Array, body: Code, flags: For_Flags)
Lets a Bucket_Array be used in a for loop over its live elements, in bucket and slot order; it_index numbers the elements visited, 0, 1, 2, ... with free slots skipped.
array: Bucket_Array(string, 2);
for string.["a", "b", "c"] bucket_array_add(*array, it);
for name, index: array {
if name == "b" remove name;
}
assert(array.count == 2);
for name, index: array assert(name == ifx index == 0 then "a" else "c");
bucket_array_reset(*array);Types#
:: struct
A growable collection whose elements never move: Bucket_Array(Type, items_per_bucket).
- count: s64
- allocator: Allocator
- all_buckets: [..] *My_Bucket
- unfull_buckets: [..] *My_Bucket
array: Bucket_Array(int, 4);
for 10..14 bucket_array_add(*array, it);
for value, index: array {
assert(value == 10 + index); // counts the elements visited, removed ones too
if value == 11 || value == 13 remove value;
}
assert(array.count == 3);
for value, index: array assert(value == 10 + 2 * index); // 10, 12, 14: numbered afresh
bucket_array_reset(*array);:: struct
One bucket of a Bucket_Array: an occupancy flag and storage for each of items_per_bucket slots. Reachable through all_buckets; it is not meant to be created directly.
- occupied: [items_per_bucket] bool
- data: [items_per_bucket] type
- lowest_maybe_not_occupied: s32
- bucket_index: u32
- count: := 0
:: struct
Where an element lives: the number of its bucket and its slot in that bucket.
- bucket_index: u32
- slot_index: s32