Dynamic Memory Allocation

1Why the heap exists

Automatic and static storage cover most needs. Three situations they cannot:

• The size is not known until run time. You cannot declare an array before you know how many lines the file has.
• The object must outlive the function that creates it. A function that builds a list and returns it cannot put it on the stack — week 13's dangling pointer.
• The object is too large for the stack. Week 17's 8 MB limit; a 100 MB buffer has nowhere else to go.

The default should still be automatic storage. Reach for the heap when one of the three reasons above applies, not by habit.

2The four functions

#include <stdlib.h>

void *malloc(size_t size);
void *calloc(size_t count, size_t size);
void *realloc(void *ptr, size_t new_size);
void  free(void *ptr);

malloc

int *values = malloc(n * sizeof *values);
if (values == NULL) {
    return false;                 /* allocation failed */
}

Returns a pointer to size uninitialized bytes, or NULL. Three details in that one line:

sizeof *values, not sizeof(int). Writing the size in terms of the pointer means changing the type later cannot desynchronize them. It is the standard idiom and worth adopting immediately.

No cast. void * converts implicitly to any object pointer in C. Casting is unnecessary and, before C99, could hide a missing #include <stdlib.h>. (In C++ the cast is required — which is why you will see it in code written to compile as both.)

The contents are garbage. Not zero. Reading before writing is undefined behavior, exactly like an uninitialized local.

calloc

int *values = calloc(n, sizeof *values);   /* zero-filled */

Takes the count and element size separately, and zeroes the memory. The separate arguments are not cosmetic: calloc detects overflow in count * size and returns NULL, whereas malloc(count * size) would silently wrap and allocate far too little — a classic vulnerability. Prefer calloc whenever the count comes from outside your program.

realloc

int *bigger = realloc(values, new_count * sizeof *values);
if (bigger == NULL) {
    free(values);                 /* the original is still valid */
    return false;
}
values = bigger;

Grows or shrinks a block, preserving the contents up to the smaller of the two sizes. It may return a different address, having copied the data — so any other pointer into the old block is now dangling.

free

free(values);
values = NULL;        /* not required, but a good habit */

Returns the block to the allocator. free(NULL) is explicitly safe and does nothing, which removes the need for a guard. Setting the pointer to NULL afterwards turns a later use-after-free into an immediate null-pointer crash rather than silent corruption — week 20's subject.

3Checking every allocation

malloc can fail. On a desktop with overcommit it rarely does, which is exactly why unchecked allocations survive into production and then fail on a constrained machine, or under a memory limit, or when a corrupted size request asks for four gigabytes.

/* wrong */
int *p = malloc(n * sizeof *p);
p[0] = 1;                         /* if p is NULL, this crashes */

/* right */
int *p = malloc(n * sizeof *p);
if (p == NULL) {
    fprintf(stderr, "out of memory\n");
    return EXIT_FAILURE;
}

One subtlety: malloc(0) may return NULL or a unique pointer that you must still free. Both are conforming. Code that treats NULL as failure will misreport a zero-size request, so guard the zero case explicitly if it can occur.

4Ownership

C has no garbage collector and no destructors. For every allocated block there must be exactly one free, and deciding who calls it is a design decision that belongs in the interface.

Make it explicit in one of three ways:

/* 1. The caller owns the result and must free it. */
char *duplicate_string(const char *s);      /* caller frees */

/* 2. The caller supplies the storage; nobody allocates. */
bool copy_into(char *dst, size_t dst_size, const char *src);

/* 3. Paired create and destroy — the clearest for anything with state. */
Buffer *buffer_create(size_t capacity);
void    buffer_destroy(Buffer *b);

The third convention is the one to adopt for anything non-trivial. Naming them as a pair makes the obligation visible at the call site, and it scales to types that own several allocations internally — buffer_destroy frees everything, and the caller does not need to know what "everything" is. Week 33 turns this into an opaque handle where the caller cannot know.

Write the ownership rule down. A one-line comment above the prototype — /* returns a new string; caller frees */ — prevents both the leak and the double free, and it costs nothing.

5Two ways to allocate a matrix

/* A: one contiguous block, indexed manually */
int *m = malloc(rows * cols * sizeof *m);
m[r * cols + c] = 7;
free(m);

/* B: an array of row pointers */
int **m = malloc(rows * sizeof *m);
for (size_t r = 0; r < rows; r++) {
    m[r] = malloc(cols * sizeof *m[r]);
}
m[r][c] = 7;
for (size_t r = 0; r < rows; r++) free(m[r]);
free(m);

Prefer A unless you genuinely need ragged rows. One allocation, one free, contiguous memory. The slightly uglier indexing is a small price, and it can be hidden behind an accessor function or a macro.

6Worked example: the growable array

This is the data structure the rest of the course keeps returning to. Week 28 turns it into a module with a header; week 29 builds it as a library; week 30 makes it generic; week 45 packages it.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int    *data;
    size_t  count;      /* elements in use   */
    size_t  capacity;   /* elements allocated */
} IntArray;

/* Paired with array_destroy. After this returns true the caller owns
   the array and must call array_destroy exactly once. */
static bool array_init(IntArray *a, size_t initial_capacity)
{
    if (initial_capacity == 0) {
        initial_capacity = 4;
    }
    a->data = malloc(initial_capacity * sizeof *a->data);
    if (a->data == NULL) {
        a->count = a->capacity = 0;
        return false;
    }
    a->count = 0;
    a->capacity = initial_capacity;
    return true;
}

static void array_destroy(IntArray *a)
{
    free(a->data);              /* free(NULL) is safe */
    a->data = NULL;
    a->count = a->capacity = 0;
}

/* Doubling gives amortized O(1) append: n appends cost O(n) copies total. */
static bool array_grow(IntArray *a)
{
    size_t new_capacity = a->capacity * 2;

    int *bigger = realloc(a->data, new_capacity * sizeof *a->data);
    if (bigger == NULL) {
        return false;           /* a->data is still valid and still ours */
    }
    a->data = bigger;
    a->capacity = new_capacity;
    return true;
}

static bool array_push(IntArray *a, int value)
{
    if (a->count == a->capacity && !array_grow(a)) {
        return false;
    }
    a->data[a->count++] = value;
    return true;
}

static bool array_get(const IntArray *a, size_t index, int *out)
{
    if (index >= a->count) {
        return false;
    }
    *out = a->data[index];
    return true;
}

static void array_print(const IntArray *a, const char *label)
{
    printf("  %-10s count=%-3zu capacity=%-3zu [", label, a->count, a->capacity);
    for (size_t i = 0; i < a->count; i++) {
        printf("%d%s", a->data[i], i + 1 < a->count ? " " : "");
    }
    puts("]");
}

/* Caller frees the result. Named so the obligation is hard to miss. */
static char *duplicate_string(const char *s)
{
    size_t bytes = strlen(s) + 1;          /* room for the terminator */
    char *copy = malloc(bytes);
    if (copy == NULL) {
        return NULL;
    }
    memcpy(copy, s, bytes);
    return copy;
}

int main(void)
{
    puts("== growable array ==");
    IntArray a;
    if (!array_init(&a, 2)) {
        fprintf(stderr, "out of memory\n");
        return EXIT_FAILURE;
    }

    array_print(&a, "empty");
    for (int i = 1; i <= 9; i++) {
        if (!array_push(&a, i * i)) {
            fprintf(stderr, "out of memory\n");
            array_destroy(&a);
            return EXIT_FAILURE;
        }
        if (a.count == a.capacity) {
            array_print(&a, "full");
        }
    }
    array_print(&a, "final");
    puts("  capacity doubled 2 -> 4 -> 8 -> 16: five reallocations for nine pushes");

    int value;
    printf("  element 3  : %s", array_get(&a, 3, &value) ? "" : "refused\n");
    if (array_get(&a, 3, &value)) printf("%d\n", value);
    printf("  element 99 : %s\n",
           array_get(&a, 99, &value) ? "returned a value" : "refused");

    array_destroy(&a);
    puts("  destroyed; calling array_destroy again would also be safe");
    array_destroy(&a);

    puts("\n== calloc zeroes, malloc does not ==");
    int *raw = malloc(4 * sizeof *raw);
    int *zeroed = calloc(4, sizeof *zeroed);
    if (raw != NULL && zeroed != NULL) {
        printf("  malloc: %d %d %d %d   (garbage — do not rely on it)\n",
               raw[0], raw[1], raw[2], raw[3]);
        printf("  calloc: %d %d %d %d   (guaranteed zero)\n",
               zeroed[0], zeroed[1], zeroed[2], zeroed[3]);
    }
    free(raw);
    free(zeroed);

    puts("\n== a flat matrix: one allocation, one free ==");
    const size_t rows = 3, cols = 4;
    int *m = malloc(rows * cols * sizeof *m);
    if (m == NULL) {
        return EXIT_FAILURE;
    }
    for (size_t r = 0; r < rows; r++) {
        for (size_t c = 0; c < cols; c++) {
            m[r * cols + c] = (int)(r * cols + c);
        }
    }
    for (size_t r = 0; r < rows; r++) {
        printf("  ");
        for (size_t c = 0; c < cols; c++) {
            printf("%3d", m[r * cols + c]);
        }
        putchar('\n');
    }
    free(m);

    puts("\n== ownership, stated in the name ==");
    char *copy = duplicate_string("the caller frees this");
    if (copy != NULL) {
        printf("  \"%s\"\n", copy);
        free(copy);
    }

    return EXIT_SUCCESS;
}

gcc -std=c17 -Wall -Wextra -g -fsanitize=address -o dynarray dynarray.c
./dynarray

Why doubling

Growing by one element per push would copy the whole array every time: n pushes cost n²/2 copies. Doubling copies only when the array is full, and the total work across n pushes is n + n/2 + n/4 + … < 2n. Each push is therefore O(1) amortized, even though individual pushes occasionally cost O(n). Week 33 puts a name to this reasoning.

The output shows five reallocations for nine pushes. Change the growth to capacity + 1 and count again.

Confirm there are no leaks

AddressSanitizer includes a leak detector, and the program above is clean:

./dynarray
(no LeakSanitizer output = nothing leaked)

Now remove one free — the free(copy) at the end — and run it again:

==1234==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 22 byte(s) in 1 object(s) allocated from:
    #0 0x... in malloc
    #1 0x... in duplicate_string dynarray.c:103
    #2 0x... in main dynarray.c:176

SUMMARY: AddressSanitizer: 22 byte(s) leaked in 1 allocation(s).

Exact size, exact allocation site, exact call path. Valgrind gives the same information without recompiling:

valgrind --leak-check=full ./dynarray

The realloc mistake, demonstrated

Change array_grow to the tempting one-liner:

a->data = realloc(a->data, new_capacity * sizeof *a->data);
if (a->data == NULL) return false;

It works, until realloc fails. Then a->data is NULL, the old block is still allocated, and the only pointer to it has been destroyed. Simulating this is awkward on a desktop, which is the point: the bug is invisible in testing and fires exactly when memory is scarce.

7Common mistakes

9Where this leads

You can now allocate and release memory correctly — in code that works. Week 20 is about code that does not: leaks, use-after-free, double free, and overruns, each seeded deliberately into the array you just built and then hunted down with a different tool. Those tools are what make heap programming in C tractable rather than terrifying.