A dynamic array

An array from lesson 22 has a size fixed at compile time. A dynamic array keeps a heap block, a count of used elements and a count of allocated places, and it grows the block when the two meet. The idea is three fields and two functions, and the rest of the data structures in this part build on it.

The struct and push

The capacity is the number of elements the block can hold; the size is the number in use. When they are equal, push doubles the capacity with realloc and stores the new pointer only after the call succeeded. Doubling makes the average cost of a push constant.

#include <stdio.h> #include <stdlib.h> struct IntArray { int *data; size_t size; size_t capacity; }; static int init(struct IntArray *array, size_t capacity) { array->data = malloc(capacity * sizeof *array->data); if (array->data == NULL) { return 0; } array->size = 0; array->capacity = capacity; return 1; } static int push(struct IntArray *array, int value) { if (array->size == array->capacity) { size_t capacity = array->capacity * 2; int *data = realloc(array->data, capacity * sizeof *data); if (data == NULL) { return 0; } array->data = data; array->capacity = capacity; } array->data[array->size++] = value; return 1; } static void destroy(struct IntArray *array) { free(array->data); array->data = NULL; array->size = 0; array->capacity = 0; } int main(void) { struct IntArray array; if (!init(&array, 2)) { return 1; } for (int i = 0; i < 6; i++) { if (!push(&array, i * 10)) { destroy(&array); return 1; } printf("%zu/%zu ", array.size, array.capacity); } printf("\n"); for (size_t i = 0; i < array.size; i++) { printf("%d ", array.data[i]); } printf("\n"); destroy(&array); return 0; }

gcc -Wall -Wextra array.c -o array
./array

1/2 2/2 3/4 4/4 5/8 6/8
0 10 20 30 40 50

The capacity goes 2, 4, 8 while the size grows one at a time. If realloc returns NULL, the old block is still valid and is freed by destroy, which is why the new pointer goes into a temporary first.

Reserve and capacity

When the final count is known in advance, reserving the capacity once avoids the repeated reallocations. A reserve function does nothing when the request fits and otherwise grows the block to the requested size. After the call the capacity is at least the request, never less.

#include <stdio.h> #include <stdlib.h> struct IntArray { int *data; size_t size; size_t capacity; }; static int reserve(struct IntArray *array, size_t capacity) { if (capacity <= array->capacity) { return 1; } int *data = realloc(array->data, capacity * sizeof *data); if (data == NULL) { return 0; } array->data = data; array->capacity = capacity; return 1; } int main(void) { struct IntArray array = {NULL, 0, 2}; array.data = malloc(array.capacity * sizeof *array.data); if (array.data == NULL) { return 1; } printf("start: %zu\n", array.capacity); if (!reserve(&array, 10)) { free(array.data); return 1; } printf("after reserve 10: %zu\n", array.capacity); reserve(&array, 5); printf("after reserve 5: %zu\n", array.capacity); free(array.data); return 0; }

gcc -Wall -Wextra reserve.c -o reserve
./reserve

start: 2
after reserve 10: 10
after reserve 5: 10

The second reserve asked for less than the current capacity and changed nothing, which is the contract that lets a caller reserve an upper bound without shrinking the array. A real implementation might also grow geometrically here, but the exact capacity is easier to reason about.

A checked accessor

Direct indexing is fine inside the module, but a caller can pass an index past the size. An accessor returns a status and writes the value through a pointer, the out-parameter pattern from lesson 27. The check is one comparison and turns a memory error into a boolean.

#include <stdio.h> #include <stdlib.h> struct IntArray { int *data; size_t size; }; static int get(const struct IntArray *array, size_t index, int *out) { if (index >= array->size) { return 0; } *out = array->data[index]; return 1; } int main(void) { int storage[4] = {3, 1, 4, 1}; struct IntArray array = {storage, 4}; int value = 0; if (get(&array, 2, &value)) { printf("index 2: %d\n", value); } if (!get(&array, 9, &value)) { printf("index 9: out of range\n"); } return 0; }

gcc -Wall -Wextra get.c -o get
./get

index 2: 4
index 9: out of range

The array in this example borrows a stack buffer instead of owning a heap block, which a struct with a pointer and a size allows. The accessor does not care where the data lives, which is why the same function works for both kinds of storage.

A pointer lost to realloc

A pointer into the block becomes invalid as soon as realloc moves it. The program below saves the address of the first element, grows the array past the first capacity, and then reads through the old address. AddressSanitizer reports the read as a heap-use-after-free:

#include <stdio.h> #include <stdlib.h> struct IntArray { int *data; size_t size; size_t capacity; }; static int push(struct IntArray *array, int value) { if (array->size == array->capacity) { size_t capacity = array->capacity * 2; int *data = realloc(array->data, capacity * sizeof *data); if (data == NULL) { return 0; } array->data = data; array->capacity = capacity; } array->data[array->size++] = value; return 1; } int main(void) { struct IntArray array = {NULL, 0, 1}; array.data = malloc(array.capacity * sizeof *array.data); if (array.data == NULL) { return 1; } *array.data = 99; int *first = &array.data[0]; for (int i = 0; i < 8; i++) { if (!push(&array, i)) { free(array.data); return 1; } } printf("%d\n", *first); free(array.data); return 0; }

gcc -fsanitize=address -g -Wall -Wextra after.c -o after
./after 2>&1 | head -n 5

=================================================================
==769==ERROR: AddressSanitizer: heap-use-after-free on address 0x798345cc0010 at pc 0x578573121688 bp 0x7ffc8ce02ea0 sp 0x7ffc8ce02e90
READ of size 4 at 0x798345cc0010 thread T0
#0 0x578573121687 in main /tmp/c5/L50/after.c:43
#1 0x7d63467b8153 in libc_start_main_stage2 src/env/__libc_start_main.c:95

The report continues with the address and size of the freed block, and the process id and addresses change per run. The rule is that an index, not a pointer, survives a growth: after every push that may reallocate, address the element through array.data again.

Exercises

  1. Add a pop function that removes the last element and returns it through a status and an out-parameter.
  2. Add shrink, which reduces the capacity to the size when less than a quarter of the block is used.
  3. Write a loop that pushes a million values into the array and print the final capacity. How many reallocations happened?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What is the difference between size and capacity?

    Answer

    Size counts used elements; capacity counts allocated slots

    size is the number of stored values, while capacity is how many the current block can hold.

  2. Why does push double the capacity instead of adding one?

    Answer

    The average cost of a push stays constant

    Doubling makes the expensive copies rare, so the total work over many pushes grows linearly.

  3. Why does push store realloc in a temporary pointer?

    Answer

    The old block must survive a failed realloc

    On failure realloc returns NULL and leaves the old block valid, so overwriting the only pointer would leak it.

  4. Why is an index safer than a saved pointer after a growth?

    Answer

    realloc may move the block to a new address

    A move invalidates every pointer into the old block, while the index is resolved again through the new data.

  5. What does this program print for size and capacity? #include <stdio.h> #include <stdlib.h> int main(void){ int *d=malloc(2*sizeof *d); size_t s=0,c=2; for(int i=0;i<6;i++){ if(s==c){c*=2;d=realloc(d,c*sizeof *d);} d[s++]=i*10; printf("%zu/%zu ",s,c);} printf("\n"); free(d); return 0; }

    Answer

    1/2 2/2 3/4 4/4 5/8 6/8

    The capacity doubles when the array is full, so the pairs go 2, 4 and 8 while the size grows one at a time.

  6. What values does this program print after six pushes? #include <stdio.h> #include <stdlib.h> int main(void){ int *d=malloc(2*sizeof *d); size_t s=0,c=2; for(int i=0;i<6;i++){ if(s==c){c*=2;d=realloc(d,c*sizeof *d);} d[s++]=i*10;} for(size_t i=0;i<s;i++) printf("%d ",d[i]); printf("\n"); free(d); return 0; }

    Answer

    0 10 20 30 40 50

    The loop pushes i * 10 for i from 0 to 5, and the values print in insertion order.

  7. What does this program print for its three capacity lines? #include <stdio.h> #include <stdlib.h> int main(void){ int *d=malloc(2*sizeof *d); size_t c=2; printf("start: %zu\n",c); d=realloc(d,10*sizeof *d); c=10; printf("after reserve 10: %zu\n",c); if(5>c){d=realloc(d,5*sizeof *d);c=5;} printf("after reserve 5: %zu\n",c); free(d); return 0; }

    Answer

    start: 2 / after reserve 10: 10 / after reserve 5: 10

    The first reserve grows the block to ten, and the request for five is smaller than the current capacity, so nothing changes.

  8. What does the checked accessor print for index 2 and index 9?

    Answer

    index 2: 4 and index 9: out of range

    The third element is 4, and the size check rejects index 9 before the array is read.

  9. What does AddressSanitizer report for the saved pointer after growth?

    Answer

    A heap-use-after-free read

    The old block was released by realloc, so the later read through the saved address touches freed memory.

  10. What happens if realloc is assigned directly to array->data and fails?

    Answer

    The old block is leaked with no pointer left

    The failed call returns NULL, and overwriting the only pointer to the old block loses it without a free.

The code on this page was run with gcc (Alpine 15.2.0) 15.2.0 with the AddressSanitizer runtime on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev

Banner image