Mini-Capstone: A Dynamic Array in C
Build it, then read your own assembly
- › Design a growable array from scratch, using a struct, a pointer, and heap memory
- › Reason about capacity vs length and why doubling gives amortized O(1) append
- › Implement init, push, get, and free correctly, including the realloc pattern
- › Read your own compiled code and recognize the machine underneath your design
Time to build something real
Weeks 1–3 gave you the machine and C's building blocks. This mini-capstone makes you *combine* them:
you'll design and build a dynamic array (a growable list of ints) from nothing — the data
structure behind Python lists, Go slices, and C++ vector. It exercises structs (day 18), pointers
(day 16), the heap, and array indexing (day 17), and then you'll disassemble your own code and find
everything you've learned staring back at you. This is the shape of every capstone: you architect it,
you build it, you prove you understand it.
The design: capacity vs length
A fixed array can't grow. The trick is to separate two numbers:
- length — how many elements you're actually using.
- capacity — how many the currently-allocated block *can* hold.
When length reaches capacity and you push one more, you grow: allocate a bigger block, copy the old contents over, free the old block, and continue. The struct that tracks this is tiny:
1typedef struct {2 int *data; // pointer to a heap block of ints (day 16)3 size_t len; // elements in use4 size_t cap; // elements the block can hold5} Vec;Why doubling? The amortized argument
When you grow, you don't add one slot — you double the capacity (e.g. 4 → 8 → 16). Here's the reasoning, and it's worth understanding, not memorizing: if you grew by 1 each time, appending N elements would copy 1+2+3+…+N ≈ N²/2 elements total — quadratic, terrible. If you *double*, the copies are N + N/2 + N/4 + … < 2N total across N appends. So each append costs O(1) *on average* (amortized), even though occasional appends do a big copy. Doubling turns a quadratic cost into a linear one. This is the single most important idea about dynamic arrays.
if (len == cap) { cap = cap ? cap*2 : 4; data = realloc(data, cap*sizeof(int)); }
data[len++] = value;. realloc either extends the block in place or allocates a new bigger one,
copies your old bytes over, and frees the old — returning the (possibly new) address, which you must
store back into data. Forgetting to reassign data, or checking the wrong thing for the grow
condition, are the two classic bugs — derive the logic and they won't happen.The contract you'll implement
Four functions, a clear contract each:
void vec_init(Vec *v)— start empty: data = NULL, len = 0, cap = 0.void vec_push(Vec *v, int x)— append x, growing (doubling) if full.int vec_get(Vec *v, size_t i)— return element i (assume i < len for now).void vec_free(Vec *v)— free the block and reset the struct so it can't dangle.
Notice every function takes Vec *v — a pointer — so it can *modify the caller's* struct (day 16).
Passing the struct by value would copy it, and your growth would be lost. Pointers are how the
functions and the owner share one object.
valgrind — it will confirm you free what you malloc/realloc
(no leaks) and never touch freed or out-of-bounds memory. Getting a clean valgrind report on your own
allocator is a genuinely satisfying proof that your pointer and heap reasoning is correct. Memory
correctness is a skill you can *verify*, not just hope for.Build the dynamic array, then disassemble it
Implement the full Vec in vec.c: the struct, and vec_init, vec_push (with doubling via realloc), vec_get, and vec_free, plus a main() that pushes ~20 ints (printing cap each time so you SEE it double: 4, 8, 16, 32), reads a few back with vec_get, and frees. Run it under valgrind for a clean report (no leaks, no errors). THEN compile at -O0, disassemble vec_push, and identify: the struct field accesses ([base + displacement], day 18), the len==cap compare (day 9), the call to realloc (ABI args in rdi/rsi, day 13), and the data[len]=x store ([base+index*scale], day 17). This is the capstone of everything in weeks 1-3.
$ gcc -O0 -g -Wall vec.c -o vec && ./vec$ valgrind --leak-check=full ./vec$ objdump -d -M intel vec # disassemble and annotate vec_push- › Capacity visibly doubles (4, 8, 16, 32...) as you push
- › valgrind reports no leaks and no invalid accesses
- › You reassigned data from realloc's return value (didn't drop it)
- › In vec_push's disassembly you found the field accesses, the len==cap compare, the realloc call, and the indexed store