CodeCrafters | C Chapter 11: 11. Dynamic memory

Chapter 11 of 24

11. Dynamic memory

Requesting storage while a program runs

A local variable is useful when its storage is needed only in a known part of a function. Sometimes a program does not know how much storage it needs until it runs. Dynamic memory lets the program request that storage and manage how long it remains in use.

Request enough bytes with an allocation function such as malloc.
Check that the request succeeded before using the returned pointer.
When finished, release the allocation exactly once with free and do not use that pointer to access the released object.

Dynamic allocation creates an ownership responsibility: code must know who releases the memory and on which paths. The examples below build that responsibility into reusable data structures.

Use dynamic allocation when the size or lifetime of an object must be chosen
at runtime. The allocation functions are declared in <stdlib.h>.

#include <stdint.h>
#include <stdlib.h>

int main(void)
{
    size_t count = 10;
    if (count > SIZE_MAX / sizeof(int)) {
        return 1;
    }

    int *items = malloc(count * sizeof *items);
    if (items == NULL) {
        return 1;
    }

    for (size_t i = 0; i < count; ++i) {
        items[i] = (int)i;
    }

    free(items);
    return 0;
}

Key rules:

Check allocation results before use.
Allocate enough space and check that size calculations cannot overflow.
Initialize allocated memory before reading it. malloc leaves contents
indeterminate; calloc allocates zeroed bytes.
Release each allocation exactly once with free.
Do not use a pointer after free, free the same allocation twice, or access
outside the allocated region.
realloc can move an allocation. Store its result in a temporary pointer so
the original allocation is not lost if it fails.

Memory bugs include leaks, use-after-free, double-free, buffer overflows, and
invalid frees. Ownership should be clear: decide which function is responsible
for releasing each allocation.

Allocation as an ownership contract

malloc requests a number of bytes and returns either a suitably aligned
pointer to the allocated space or NULL. It does not initialize the bytes.
Use sizeof *pointer rather than repeating the pointed-to type in a
calculation; the expression stays correct if the pointer type changes:

#include <stdint.h>
#include <stdlib.h>

int main(void)
{
    size_t count = 10;
    if (count > SIZE_MAX / sizeof(int)) {
        return 1;
    }

    int *items = malloc(count * sizeof *items);
    if (items == NULL) {
        return 1;
    }

    free(items);
    return 0;
}

Before multiplying count by the element size, ensure the product fits in
size_t. Otherwise the allocation can be smaller than intended. Handle a
zero element count explicitly if the program needs consistent behavior,
because zero-size allocation behavior is special and not useful as ordinary
element storage.

free(NULL) is allowed and does nothing, but freeing a non-null pointer is
valid only when it is the original pointer returned by an allocation
function and has not already been freed. After release, clear or stop using
all aliases to that allocation; setting one pointer to NULL does not fix
other aliases.

For realloc, preserve the old pointer if the resize fails:

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>

bool resize_ints(int **items, size_t new_count)
{
    if (items == NULL) {
        return false;
    }
    if (new_count == 0) {
        free(*items);
        *items = NULL;
        return true;
    }
    if (new_count > SIZE_MAX / sizeof **items) {
        return false;
    }

    int *larger = realloc(*items, new_count * sizeof **items);
    if (larger == NULL) {
        return false;  // *items still refers to the original allocation. 
    }

    *items = larger;
    return true;
}

The new size calculation must also be checked for overflow. If resizing to
zero is needed, prefer an explicit policy (such as freeing and setting the
pointer to NULL) rather than relying on edge-case behavior.

Before writing an allocation, state its owner and cleanup path. In a simple
program, one function may allocate and free. In a reusable library, document
whether the caller or library releases returned storage. Every early-return
error path must still release resources it owns.

Checkpoint: Explain why assigning realloc directly to the only copy of
the old pointer can lose the allocation when resizing fails.

A reusable dynamic-array abstraction

A dynamic array (often called a vector) stores a pointer, a number of used
elements (length), and the number of allocated slots (capacity). Its
central invariant is:

0 <= length <= capacity

The pointer is either NULL when capacity is zero, or points to storage for
at least capacity elements. Only elements with indices below length are
initialized and part of the collection. Capacity may exceed length so that
adding an element does not require allocation every time.

A push operation follows this sequence:

If length < capacity, write the new element at data[length] and
increment length.
Otherwise choose a larger capacity, checking that the new capacity and
byte count cannot overflow.
Resize using a temporary pointer.
If allocation fails, leave the original vector unchanged and report
failure.
On success, install the new pointer and capacity, then append the element.

Growing geometrically (for example, doubling capacity) gives good average
performance over many appends. A single append can still be expensive because
it may move the allocation, so callers must not keep pointers to vector
elements across an operation that might resize it.

Document whether a vector owns its storage, whether callers may access its
elements directly, and whether a failed push changes the vector. A clean API
might provide init, push, get, clear, and destroy operations.
destroy releases owned storage and resets the object to a valid empty
state; it should be safe to call only according to the API's documented
initialization rules.

#include <stdbool.h>
#include <stddef.h>

typedef struct {
    int *data;
    size_t length;
    size_t capacity;
} IntVector;

 // Required empty-state invariant: data == NULL, length == capacity == 0. 
void vector_init(IntVector *vector)
{
    vector->data = NULL;
    vector->length = 0;
    vector->capacity = 0;
}

In the complete implementation later in this chapter, push grows capacity
while preserving the invariant, and destroy releases the owned buffer.

Allocation failure and cleanup paths

An allocation failure is not exceptional in the language; the program must
decide how to respond. A command-line utility may report an error and exit.
A library should normally return a failure status and leave its inputs in a
documented state. Never continue as if allocation succeeded.

When a function acquires more than one resource, cleanup must handle partial
success. If the second allocation fails after the first succeeded, release
the first before returning. A single cleanup section can make this visible:

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

int main(void)
{
int result = 1;
char *buffer = malloc(128);
FILE *file = NULL;

if (buffer == NULL) {
    goto cleanup;
}

file = fopen("data.txt", "r");
if (file == NULL) {
    goto cleanup;
}

 // Work with file and buffer. 
result = 0;

cleanup:
if (file != NULL) {
    fclose(file);
}
free(buffer);
return result;
}

This style is useful when it remains short and each resource has a clear
cleanup action. Check close errors where losing buffered data matters. Do not
jump into scopes in ways that skip required initialization.

Worked example: a small integer vector

This example puts the vector invariant and allocation rules together. The
vector must first be initialized (or set to {0}), and only functions that
preserve its invariant should modify its fields:

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct {
    int *data;
    size_t length;
    size_t capacity;
} IntVector;

void int_vector_init(IntVector *vector)
{
    if (vector != NULL) {
        vector->data = NULL;
        vector->length = 0;
        vector->capacity = 0;
    }
}

bool int_vector_push(IntVector *vector, int value)
{
    if (vector == NULL) {
        return false;
    }

    if (vector->length == vector->capacity) {
        size_t new_capacity = 4;
        if (vector->capacity != 0) {
            if (vector->capacity > SIZE_MAX / 2) {
                return false;
            }
            new_capacity = vector->capacity * 2;
        }

        if (new_capacity > SIZE_MAX / sizeof *vector->data) {
            return false;
        }

        int *new_data =
            realloc(vector->data, new_capacity * sizeof *vector->data);
        if (new_data == NULL) {
            return false;
        }

        vector->data = new_data;
        vector->capacity = new_capacity;
    }

    vector->data[vector->length] = value;
    ++vector->length;
    return true;
}

void int_vector_destroy(IntVector *vector)
{
    if (vector != NULL) {
        free(vector->data);
        vector->data = NULL;
        vector->length = 0;
        vector->capacity = 0;
    }
}

The realloc result is held in new_data so that failure leaves the old
vector intact. The multiplication is checked before computing the byte
count. push changes the vector only after the new allocation succeeds.
destroy releases the one allocation owned by the vector and restores the
empty invariant. In a larger library, put the type and function declarations
in a header and keep the implementation in a source file.

The caller still must check int_vector_push's return value and must not keep
an element pointer across a push that could grow and move the allocation.
This example assumes the vector was initialized; it cannot safely repair
arbitrary uninitialized fields.