Bucket_Array

A growable collection whose elements never move: Bucket_Array(Type, items_per_bucket).

Storage is a list of fixed-size buckets of items_per_bucket slots, allocated one at a time from the allocator in the allocator field (context.allocator when it is unset at the first add). Adding never moves existing elements, so a pointer to an element stays valid until that element is removed or the array is reset; this is what it is for. Removing leaves a hole that a later add fills, lowest free slot first, so there is no gap-free order. count is the number of live elements.

Elements are addressed by the Bucket_Locator that bucket_array_add returns. The for loop visits live elements bucket by bucket, slot by slot, which is insertion order only until something has been removed. With always_iterate_by_pointer set, it is a pointer to the element even without for *.

Looping. for value: array visits the live elements. A second name, as in for value, index: array, is the index: how many elements were visited before this one (0, 1, 2, ...), free slots skipped. It is not a Bucket_Locator and not a slot number, so do not hand it to array[n] or bucket_array_find once anything has been removed; keep the locator that bucket_array_add returned for that. To delete the element you are on, write remove value; (the name of the loop variable, it when you gave none) inside the loop. The loop carries on with the next element, and it needs no locator.

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);

array[n] is the element in the slot numbered n (*array[n] is its address), counted as bucket * items_per_bucket + slot; it fails an assert on a free slot, so after removals it is not the n-th live element.

A Bucket_Array that is never reset leaks its buckets: call bucket_array_reset to free them.

array: Bucket_Array(string, 4);
locator, pointer := bucket_array_add(*array, "first");
bucket_array_add(*array, "second");

assert(bucket_array_find(*array, locator) == "first");
assert(pointer.* == "first" && array.count == 2);

bucket_array_remove(*array, locator);
for name: array assert(name == "second");
bucket_array_reset(*array);