C / CAPSTONE PROJECTS
Project: a dynamic array library with tests
Build a growable array in C with doubling reserve and failure-safe realloc, plus an assert harness that tests the growth and empty-pop paths.
What you will learn
- Split a vector into data, len and cap, and keep len <= cap in every operation
- Grow capacity by doubling so n pushes cost about 2n copies instead of n^2/2
- Route realloc through one reserve function that reports failure without losing data
- Store indices, not pointers, because any push can move the buffer
Understanding Project: a dynamic array library with tests
A dynamic array is a fixed-size buffer plus two numbers: len, how many elements you have actually stored, and cap, how many the buffer can hold before it must be replaced. Every function in the library is either pure bookkeeping (indexing, len, pop) or a size change (push, insert, reserve), and only the second kind can fail. Keeping len and cap separate is what makes push cheap: the common case is one store and one increment, and the expensive case is rare.
Capacity must grow by multiplication, not addition. If each push reallocs for exactly one more slot, the n-th push carries n-1 elements over and the whole sequence costs on the order of n^2 element moves; doubling makes those moves sum to less than 2n, so a push is constant time on average. realloc adds two details the library has to respect: realloc(NULL, n) behaves like malloc(n), which is why an all-zero struct is already a valid empty vector, and a failed realloc returns NULL while leaving the original block allocated. Writing the result straight into v->data therefore turns a temporary out-of-memory condition into a leak plus a NULL dereference, so the result goes into a local first.
Because a grow can move the buffer to a different address, a pointer into the array is only valid until the next push. Keep indices in long-lived data, use raw element pointers only immediately, and say so in the header, because realloc frequently extends in place and the broken version keeps working until the day it does not. Tests are what make that discipline checkable: pin down cap and len around the exact push that crosses the boundary, pop from an empty vector, reuse a vector after freeing it, and run the suite under a sanitizer so a use-after-free is a failure instead of a lucky pass.
<stdio.h>
<stdlib.h>
typedef struct {
int *data;
size_t len; /* elements in use */
size_t cap; /* elements the buffer can hold */
} IntVec;
/* The only function that calls realloc. Returns 1 on success, 0 on
failure, and on failure leaves the vector exactly as it was. */
static int vec_reserve(IntVec *v, size_t want)
{
size_t cap;
int *grown;
if (want <= v->cap)
return 1;
cap = v->cap ? v->cap * 2 : 4; /* seed: 0 * 2 is still 0 */
if (cap < want)
cap = want;
grown = realloc(v->data, cap * sizeof *v->data);
if (grown == NULL)
return 0; /* v->data is still valid */
v->data = grown;
v->cap = cap;
return 1;
}
static int vec_push(IntVec *v, int x)
{
if (!vec_reserve(v, v->len + 1))
return 0;
v->data[v->len++] = x;
return 1;
}
static int vec_pop(IntVec *v, int *out)
{
if (v->len == 0)
return 0;
*out = v->data[--v->len];
return 1;
}
static void vec_free(IntVec *v)
{
free(v->data);
v->data = NULL;
v->len = v->cap = 0;
}
/* ---- test harness ---- */
static int tests, failures;
CHECK(cond)
static void run(const char *name, void (*fn)(void))
{
int before = failures;
tests++;
fn();
printf("%s: %s\n", name, failures == before ? "ok" : "FAILED");
}
static void test_push_grows_capacity(void)
{
IntVec v = {0}; /* zeroed struct is a valid empty vector */
int i;
for (i = 0; i < 4; i++)
CHECK(vec_push(&v, i) == 1);
CHECK(v.len == 4);
CHECK(v.cap == 4);
CHECK(vec_push(&v, 4) == 1); /* the push that must realloc */
CHECK(v.len == 5);
CHECK(v.cap == 8);
CHECK(v.data[0] == 0 && v.data[4] == 4);
vec_free(&v);
}
static void test_pop_is_lifo(void)
{
IntVec v = {0};
int out = -1;
CHECK(vec_pop(&v, &out) == 0); /* empty pop reports failure ... */
CHECK(out == -1); /* ... and leaves out alone */
vec_push(&v, 10);
vec_push(&v, 20);
CHECK(vec_pop(&v, &out) == 1 && out == 20);
CHECK(vec_pop(&v, &out) == 1 && out == 10);
CHECK(v.len == 0);
CHECK(v.cap == 4); /* pop does not hand memory back */
vec_free(&v);
}
static void test_reuse_after_free(void)
{
IntVec v = {0};
int i;
for (i = 0; i < 1000; i++)
CHECK(vec_push(&v, i) == 1);
CHECK(v.cap == 1024); /* 4 -> 8 -> ... -> 1024 */
vec_free(&v);
CHECK(v.data == NULL && v.len == 0 && v.cap == 0);
CHECK(vec_push(&v, 7) == 1); /* a freed vector is a fresh vector */
CHECK(v.data[0] == 7 && v.cap == 4);
vec_free(&v);
}
int main(void)
{
run("push_grows_capacity", test_push_grows_capacity);
run("pop_is_lifo", test_pop_is_lifo);
run("reuse_after_free", test_reuse_after_free);
printf("%d tests, %d failures\n", tests, failures);
return failures != 0;
}
Everything difficult about a dynamic array happens at the moment the buffer is replaced, so that moment belongs in one reserve function the tests can pin down.
Worked examples
Why doubling and not plus one
Counts the elements each growth strategy has to carry over for the same 1000 pushes.
<stdio.h>
<stdlib.h>
typedef struct { int *data; size_t len, cap; } Vec;
static size_t copies; /* elements a grow has to carry over */
static int *grow(int *p, size_t n)
{
int *q = realloc(p, n * sizeof *q);
if (q == NULL) { free(p); fputs("out of memory\n", stderr); exit(1); }
return q;
}
static void push_doubling(Vec *v, int x)
{
if (v->len == v->cap) {
size_t cap = v->cap ? v->cap * 2 : 1;
v->data = grow(v->data, cap);
copies += v->len;
v->cap = cap;
}
v->data[v->len++] = x;
}
static void push_plus_one(Vec *v, int x)
{
v->data = grow(v->data, v->len + 1);
copies += v->len;
v->cap = v->len + 1;
v->data[v->len++] = x;
}
int main(void)
{
Vec a = {0}, b = {0};
int i;
for (i = 0; i < 1000; i++) push_doubling(&a, i);
printf("doubling: cap=%zu copies=%zu\n", a.cap, copies);
copies = 0;
for (i = 0; i < 1000; i++) push_plus_one(&b, i);
printf("grow-by-1: cap=%zu copies=%zu\n", b.cap, copies);
free(a.data);
free(b.data);
return 0;
}
Example explained
Line 1copies += v->len records how many elements existed when the buffer was replaced, which is the work realloc must do in the worst case.
Line 2Doubling reallocs 11 times for 1000 pushes and moves 1023 elements in total, roughly one move per push.
Line 3push_plus_one reallocs on every push, so the moves add up to 999*1000/2 = 499500 and the cost is quadratic in the number of pushes.
Line 4grow frees the old pointer before exiting because a NULL from realloc means the original block is still yours to release.
One implementation for any element type
Stores structs by byte size so the same array code works for every type without macros or templates.
<stdio.h>
<stdlib.h>
<string.h>
typedef struct {
unsigned char *data; /* bytes, so the offset math is legal C */
size_t elem_size;
size_t len, cap;
} Array;
static void arr_init(Array *a, size_t elem_size)
{
a->data = NULL;
a->elem_size = elem_size;
a->len = a->cap = 0;
}
static void *arr_at(const Array *a, size_t i)
{
return a->data + i * a->elem_size;
}
static int arr_push(Array *a, const void *elem)
{
if (a->len == a->cap) {
size_t cap = a->cap ? a->cap * 2 : 4;
unsigned char *grown = realloc(a->data, cap * a->elem_size);
if (grown == NULL)
return 0;
a->data = grown;
a->cap = cap;
}
memcpy(a->data + a->len * a->elem_size, elem, a->elem_size);
a->len++;
return 1;
}
typedef struct { int id; double score; } Row;
int main(void)
{
Array a;
Row r;
size_t i;
arr_init(&a, sizeof r);
r.id = 1; r.score = 2.5; arr_push(&a, &r);
r.id = 2; r.score = 3.5; arr_push(&a, &r);
r.id = 3; r.score = 4.0; arr_push(&a, &r);
for (i = 0; i < a.len; i++) {
const Row *p = arr_at(&a, i);
printf("id=%d score=%.1f\n", p->id, p->score);
}
printf("len=%zu cap=%zu\n", a.len, a.cap);
free(a.data);
return 0;
}
Example explained
Line 1data is unsigned char * rather than void * because arithmetic on void pointers is a compiler extension, not standard C.
Line 2arr_at multiplies by elem_size at run time, which is the price a generic container pays compared with a typed int * array.
Line 3memcpy copies elem_size bytes out of the caller's object, so the array owns the data and r can be overwritten for the next push.
Line 4cap jumps to 4 on the first push and stays there, so three pushes cost exactly one allocation.
Important notes
cap * sizeof *v->data can wrap around on a 32-bit size_t and quietly allocate a buffer that is too small; reject the request when want > SIZE_MAX / sizeof *v->data.
pop keeps the capacity on purpose. Shrinking on every pop makes a push/pop loop realloc forever, so expose shrinking as a separate call the caller chooses to make.
Common mistakes
Writing cap = cap * 2 with no seed value: an empty vector has cap 0, twice 0 is still 0, and the first push writes past the end of a zero-size allocation.
Doing v->data = realloc(v->data, n) directly: when realloc returns NULL the struct loses the only pointer to a block that is still allocated, so you leak the elements and every later v->data[i] dereferences NULL.
Testing with three pushes when the initial capacity is four: the realloc branch never executes, the suite passes, and the array corrupts memory the first time a caller stores a fifth element.
Try it yourself
Change, predict, then run
Add vec_insert(IntVec *v, size_t i, int x) that returns 0 when i > v->len, calls vec_reserve first, then uses memmove to shift the tail one slot right. Write a test that inserts at index 0 of a vector already at full capacity and checks len, cap and every shifted element.
Open the C workspaceCheck your understanding
A caller does int *first = &v->data[0]; then pushes 100 more elements and reads *first. On your machine it prints the right value every time. What is the correct assessment?
- It is safe because realloc copies the old bytes, so only v->data needs updating after a grow
- It is safe because the buffer only ever grows, so the addresses of existing elements never change
- It is broken: realloc may place the new buffer elsewhere and free the old one, so first can point into freed memory and the matching address is allocator luck
- It is broken only because first should be volatile so the compiler reloads it after each push
Show answer
realloc is allowed to allocate a new block, copy the bytes there and release the old one, which leaves any saved element pointer dangling; that it often extends in place is an implementation detail you cannot rely on. Option 0 is tempting because the contents really are copied, but they are copied to a different address and only v->data is updated to it. Store the index instead and recompute &v->data[i] after the push.