calloc, realloc and growing buffers

Why this matters

malloc alone forces you to know the size before you allocate. Much of the time you do not: you are reading input of unknown length, collecting results one at a time, or loading a file. The standard answer, used inside every dynamic array, string builder and vector in every language runtime, is a buffer that grows by reallocation. Python lists, C++ std::vector, Go slices and Rust Vec all work this way underneath. This lesson shows the two remaining allocation functions and the growth pattern built on them.

calloc: zeroed memory, overflow-checked

void *calloc(size_t count, size_t size);

calloc allocates room for count elements of size bytes each and sets every byte to zero. Two advantages over malloc(count * size):

1. The memory starts zeroed, so integers are 0, pointers are null (on every platform you will meet), and strings are empty.
2. It checks the multiplication for overflow. count * size is computed in size_t, which wraps around silently; a huge count can wrap to a small number, and malloc would then happily return a block far smaller than you think.

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

int main(void)
{
    int *a = calloc(5, sizeof *a);
    if (a == NULL) return 1;
    printf("%d %d %d %d %d\n", a[0], a[1], a[2], a[3], a[4]);

    size_t huge = SIZE_MAX / 2;
    int *b = calloc(huge, sizeof *b);
    printf("calloc of %zu ints: %s\n", huge, b ? "succeeded" : "NULL");
    printf("%zu\n", huge * sizeof(int));
    free(a);
    return 0;
}

0 0 0 0 0
calloc of 9223372036854775807 ints: NULL
18446744073709551612

The last line shows the danger: huge * 4 wrapped around to a number that is wrong (it is SIZE_MAX - 3; with other values it can wrap to something small). calloc refused the request instead. When sizes come from input, this matters for security.

realloc: change a block's size

void *realloc(void *ptr, size_t new_size);

realloc resizes the block at ptr to new_size bytes and returns a pointer to the resized block. What happens underneath:

• If there is free space right after the block, the allocator just extends it in place and returns the same address.
• Otherwise it allocates a new block, copies the old contents (up to the smaller of the two sizes), frees the old block, and returns the new address.
• If it cannot get the memory, it returns NULL and leaves the old block untouched.

  in place:   [hdr| a b c d |  free space  ]   ->  [hdr| a b c d ? ? ? ? ]   same address

  moved:      [hdr| a b c d ][hdr| in use ]        old block freed
                                                   [hdr| a b c d ? ? ? ? ]   new address

Special cases: realloc(NULL, n) behaves like malloc(n), which is handy for buffers that start empty. New bytes are uninitialized.

Because the old block survives a failure, the correct pattern always uses a temporary:

int *tmp = realloc(data, new_cap * sizeof *data);
if (tmp == NULL) {
    /* data is still valid: report the error, free(data), or carry on with the old size */
} else {
    data = tmp;
}

And because the block may move, never keep pointers into a buffer across a realloc. Keep indexes instead.

Capacity and length

A growable buffer tracks two numbers:

• length (or count): how many elements are in use;
• capacity: how many fit in the current allocation.

  data -> [ 3 | 1 | 4 | 1 | . | . | . | . ]
            <---- length 4 ---->
            <------------ capacity 8 ------------>

Appending is cheap while length < capacity. When they are equal, grow. The crucial design choice is by how much:

• Grow by one each time: every append copies the whole array. Appending n elements costs about n²/2 copies. A million elements means half a trillion copies.
• Grow by a factor (double, or 1.5x): copies happen rarely. Appending n elements copies 1 + 2 + 4 + ... + n, less than 2n elements in total. The cost per append, averaged over all appends, is constant. This is called amortized O(1).

The growth pattern in full

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

int main(void)
{
    size_t count = 0, capacity = 4;
    int *data = malloc(capacity * sizeof *data);
    if (data == NULL)
        return 1;

    int x;
    while (scanf("%d", &x) == 1) {
        if (count == capacity) {
            size_t new_cap = capacity * 2;
            int *bigger = realloc(data, new_cap * sizeof *data);
            if (bigger == NULL) {
                free(data);
                printf("out of memory\n");
                return 1;
            }
            data = bigger;
            capacity = new_cap;
            printf("grew to %zu\n", capacity);
        }
        data[count++] = x;
    }

    long sum = 0;
    for (size_t i = 0; i < count; i++)
        sum += data[i];
    printf("%zu numbers, sum %ld\n", count, sum);
    free(data);
    return 0;
}

$ seq 1 20 | ./prog
grew to 8
grew to 16
grew to 32
20 numbers, sum 210

Twenty appends, three reallocations. With a million numbers there would be only about eighteen.

data[count++] = x; uses the post-increment you met in the operators module: store at index count, then add one to count.

Strings of unknown length

The same idea reads a line of any length. Grow when there is no room for one more character plus the terminator:

char *buf = NULL;
size_t len = 0, cap = 0;
int c;
while ((c = getchar()) != EOF && c != '\n') {
    if (len + 2 > cap) {                       /* char + '\0' */
        size_t new_cap = cap ? cap * 2 : 16;
        char *tmp = realloc(buf, new_cap);     /* realloc(NULL, n) == malloc(n) */
        if (tmp == NULL) { free(buf); return NULL; }
        buf = tmp;
        cap = new_cap;
    }
    buf[len++] = (char)c;
}

POSIX systems provide getline, which does exactly this for you; you will use it in the files module. Writing it once yourself is how you understand what it does.

Common mistakes

• p = realloc(p, n): leaks the block when realloc fails. Use a temporary.
• Forgetting the multiplication: realloc(data, new_cap) gives new_cap bytes, not new_cap ints. valgrind reports Invalid write of size 4 ... 0 bytes after a block of size 32 alloc'd.
• Keeping a pointer into the old block after realloc, then writing through it: a write into freed memory, Invalid write ... inside a block of size 16 free'd.
• Growing by a constant (capacity + 10): correct but quadratic. Fine for 100 elements, painfully slow for 10 million.
• Unsigned countdown loops: for (size_t i = count - 1; i >= 0; i--) never ends, because a size_t is always >= 0; when count is 0 the start value wraps to SIZE_MAX. gcc warns comparison of unsigned expression in '>= 0' is always true [-Wtype-limits] with -Wextra.

Recap

• calloc(count, size) zeroes the memory and catches count * size overflow.
• realloc(p, n) resizes, possibly moving and copying the block; on failure it returns NULL and the old block is still yours. Always assign through a temporary.
• Pointers into a block are invalid after it moves; keep indexes.
• Growable buffers track length and capacity and grow geometrically (doubling) for amortized constant-time appends.

Going further: read the getline(3) manual page (man 3 getline with manpages-dev installed, or man7.org) and compare its interface with the loop above. Then try growing by capacity + 1 instead of doubling in the example and time seq 1 200000 | ./prog against the doubling version with time.