Appendix A: A Simple Allocator
dynamic-array-push

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.