Write da_push -- append an element, growing if necessary:
fn da_push(da: i64, val: i64) i64 {
var len: i64 = load64(da + 8);
var cap: i64 = load64(da + 16);
if (len >= cap) {
// Grow: double capacity (minimum 4)
var new_cap: i64 = cap * 2;
if (new_cap < 4) { new_cap = 4; }
var new_ptr: i64 = alloc(new_cap * 8);
var old_ptr: i64 = load64(da);
// Copy old elements
for (0..len) |i| {
store64(new_ptr + i * 8, load64(old_ptr + i * 8));
}
// Free old buffer (if any)
if (old_ptr != 0) { free(old_ptr); }
store64(da, new_ptr);
store64(da + 16, new_cap);
}
store64(load64(da) + len * 8, val);
store64(da + 8, len + 1);
return 0;
}
This is the classic amortized-doubling strategy. Most pushes are O(1) -- just store and increment. Occasionally the array is full and we allocate a new buffer, copy everything, and free the old one. The amortized cost per push is O(1).
Test:
// (include alloc, free, da_new, da_push, da_get, da_len from above)
check(
\\ ... allocator and dynamic array functions ...
\\var arr: i64 = da_new();
\\da_push(arr, 10);
\\da_push(arr, 20);
\\da_push(arr, 30);
\\da_push(arr, 40);
\\da_push(arr, 50);
\\da_get(arr, 0) + da_get(arr, 4)
, 60); // 10 + 50
Five elements pushed. The array started at capacity 0, grew to 4 on the first push, then grew to 8 on the fifth push. da_get(arr, 0) returns 10. da_get(arr, 4) returns 50.