Dynamic Memory Management

Section 4.12 Dynamic Memory Management

The life time of a local variable is bound to the execution of its surrounding block. Consider the following example:

int *numbers(int n) {
    int a[n];
    for (int i = 0; i < n; i++)
        a[i] = i;
    return a;
}

Run

Apparently, it attempts to return an array with the first \(n\) non-negative integers. However, the life time of a is restricted to the execution of the body of the numbers function, since it is the innermost block that surrounds the declaration. When the execution returns from numbers to the caller, the container of a is thus deallocated. The corresponding pointer to the first element of the array dangles: It points to no existing container. Therefore, the program is incorrect. There are two ways to solve this problem:

We pass the address of a previously allocated result array to numbers. The function is then no longer concerned with allocating a container for the resulting array. Most of the time, this solution is to be preferred since it is more flexible. The array could (but does not need to) be declared as a local variable in the calling function.
The numbers function can itself allocate a container for the array. Since a local variable is not fit for this task, a container on the heap is the only option. These are allocate with the malloc function.

If we want containers that live longer than the execution of their surrounding block, we need to allocate them with the malloc function:

void* malloc(size_t  n)

Run

The parameter n determines the size of the allocated container in bytes (its type size_t is provided by the compiler and defined to be a sufficiently large unsigned integer type). It is very common to use the sizeof operator to define the container's size in terms of the type of its intended content. For example, the following statement allocates an array of n elements of the type T:

T *a = malloc(n * sizeof(a[0])); // sizeof(a[0]) == sizeof(T)

Run

Remark 4.12.1.

sizeof(x) is an operator, not a function. Its operand x can either be a type or an expression. If it is an expression, the compiler computes the expression's type and determines its size. sizeof is not evaluated during the program's execution and does therefore not provide the size of a container, but of a type.

Such a container lives until the pointer returned by malloc is given to the free function for deallocation:

void free(void* b)

Run

In contrast to the containers of local variables, malloced containers are not deallocated when execution leaves the block that surrounds their allocation.

Example 4.12.2. Eratosthenes.

Consider a main function that obtains the size of the table for the Sieve of Eratosthenes from a command line parameter:

int main(int argc, char** argv) {
    if (argc < 2) {
        printf("syntax: %s <n>\n", argv[0]);
        return 1;
    }
    unsigned n = atoi(argv[1]);
    char *table = malloc(n * sizeof(table[0]));
    eratosthenes(table, n);
    print_table(table, n);
    free(table)
    return 0;
}

Run

Subsection 4.12.1 realloc

A common use of arrays is to implement lists. This is particularly sensible if we need fast access to arbitrary elements: The address of the i-th element of an array can be computed using pointer arithmetic.

The size of an array is determined at its creation (at the declaration for a local variable, or as an argument to the malloc call) and cannot be changed retroactively. If the number of elements that are added to an array-based list exceeds the array's size, a new, larger array needs to be allocated, the previous contents copied, and the old array needs to be deallocated. The realloc function performs all these steps:

int* read_numbers_from_file(FILE *f) {
    int *numbers = NULL;
    unsigned capacity = 0;
    unsigned n = 0;
    int x;
    while (fscanf(f, "%d", &x) == 1) {
        if (n == capacity) {
            capacity = capacity == 0 ? 1 : 2 * capacity;
            numbers = realloc(numbers, sizeof(numbers[0])*capacity);
        }
        numbers[n++] = x;
    }
}

Run

When implementing such an array list, it is sensible to double the array's size with every realloc call: When \(n\) elements are inserted, the space for at most \(n - 1\) elements is wasted while at most 2n copies need to be performed.

An Introduction to Imperative Programming