Arrays that grow

Lesson 22 of 30 · Part 4 · Memory · about 15 minutes

When you ask malloc for memory, you have to say how much. Often you just don't know at the start: how many orders will come in today, how many lines a file has. This lesson builds an array that grows: when it's full, it moves to a bigger block. The tool for that is realloc:

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5    int *scores = malloc(2 * sizeof(int));6    if (scores == NULL) {7        return 1;8    }9    scores[0] = 78;10    scores[1] = 85;11    int *bigger = realloc(scores, 4 * sizeof(int));12    if (bigger == NULL) {13        free(scores);14        return 1;15    }16    scores = bigger;17    scores[2] = 90;18    scores[3] = 66;19    printf("%d %d %d %d\n", scores[0], scores[1], scores[2], scores[3]);20    free(scores);21    return 0;22}

78 85 90 66

realloc(old_pointer, new_bytes) gives you memory of the new size, moves the old contents over as they are, and returns the new block's address. The 78 and 85 are still there, with two more cells after them to use.

What realloc does

Press Step past line 11: a "16 bytes · line 11" block appears on the heap with 78 and 85 in it and two cells still empty, and the old "8 bytes" block turns gray, "freed". That's all realloc does: get a new block, copy the old contents in, give the old block back.

On this page, realloc always moves like this. In real C, if the space right after the old block happens to be free, it may grow the block in place and keep the address. You can't know which it will do, so:

• Use only the address realloc returns, never the old pointer.
• realloc already gave the old block back, so don't free it; in the end, free only the new one.

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5    int *old = malloc(2 * sizeof(int));6    old[0] = 78;7    old[1] = 85;8    int *scores = realloc(old, 4 * sizeof(int));9    printf("%d\n", old[0]);10    free(scores);11    return 0;12}

heap-use-after-free

Line 9 still uses old, but the block it points at was given back by realloc. Our engine stops here, just like "using it after free" in the last lesson. In real C, if the block happened to grow in place, this line looks fine, and then it breaks on another computer or with a few more values: the hardest kind of bug to find. Press "see how it went wrong" and look at old's red dashed arrow.

Put it in another pointer first

The program at the top didn't write scores = realloc(scores, ...); it put the result in bigger first. Here's why: when realloc can't get the memory, it returns NULL, and the old block is still there, not given back. If you write

1scores = realloc(scores, 4 * sizeof(int));

and it fails, scores becomes NULL and the old block can never be found again: the data is gone, and the block has leaked too. So always write it like this:

1int *bigger = realloc(scores, 4 * sizeof(int));2if (bigger == NULL) {3    // scores still works; free(scores) if you're giving up4}5scores = bigger;

Tip: realloc(NULL, n) does the same as malloc(n). That's why some people start the pointer at NULL and use realloc even the first time.

Length and capacity

Calling realloc for every single value is too much work. An array that grows keeps track of two numbers:

Before adding a value, take a look: if count equals capacity, it's full, so double the capacity; otherwise just add it. Here we add one day's steps at a time, for 6 days:

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5    int capacity = 2;6    int count = 0;7    int *steps = malloc(capacity * sizeof(int));8    if (steps == NULL) {9        return 1;10    }11    for (int day = 1; day <= 6; day++) {12        if (count == capacity) {13            int *bigger = realloc(steps, capacity * 2 * sizeof(int));14            if (bigger == NULL) {15                free(steps);16                return 1;17            }18            steps = bigger;19            capacity *= 2;20            printf("Full, capacity is now %d\n", capacity);21        }22        steps[count] = day * 1000;23        count++;24    }25    printf("Length %d, capacity %d\n", count, capacity);26    free(steps);27    return 0;28}

Full, capacity is now 4
Full, capacity is now 8
Length 6, capacity 8

Press Step and keep an eye on the heap: first an "8 bytes" block, swapped for "16 bytes" when the 3rd value goes in, then "32 bytes" at the 5th, with each old block turning gray. In the end the length is 6 and the capacity 8, with two empty cells waiting for the next values. When the program ends, only the last block is alive, and free gives it back.

Why double?

Could you grow by one cell each time? You could, but it's slow. Every time realloc moves, all the values so far get copied. Let's count, for 1000 values, how many moves there are and how many values get copied in all:

1#include <stdio.h>2 3int main(void) {4    int moves_one = 0;5    int copied_one = 0;6    int moves_double = 0;7    int copied_double = 0;8    int cap_one = 1;9    int cap_double = 1;10    for (int count = 1; count <= 1000; count++) {11        if (count > cap_one) {12            copied_one += cap_one;13            cap_one += 1;14            moves_one++;15        }16        if (count > cap_double) {17            copied_double += cap_double;18            cap_double *= 2;19            moves_double++;20        }21    }22    printf("Add 1 each time: %d moves, %d copied\n", moves_one, copied_one);23    printf("Double each time: %d moves, %d copied\n", moves_double, copied_double);24    return 0;25}

Add 1 each time: 999 moves, 499500 copied
Double each time: 10 moves, 1023 copied

This program doesn't actually ask for any memory; it just works out how many moves each way takes. The difference is huge: adding 1 means 999 moves and nearly half a million values copied; doubling means just 10 moves and 1023 values copied. The more values, the bigger the gap. The cost is that up to almost half the cells can sit empty, which is usually well worth it.

1#include <stdio.h>2 3int main(void) {4    int capacity = 1;5    int moves = 0;6    for (int count = 1; count <= 10; count++) {7        if (count > capacity) {8            capacity *= 2;9            moves++;10        }11    }12    printf("%d %d\n", moves, capacity);13    return 0;14}

As a function

Writing out the if and realloc for every value is long, so put it in a function, push. It has to change the length and capacity in main, so those two are passed by address (lesson 16); the block may move, so it returns the (maybe new) address:

1#include <stdio.h>2#include <stdlib.h>3 4int *push(int *items, int *count, int *capacity, int value) {5    if (*count == *capacity) {6        int *bigger = realloc(items, *capacity * 2 * sizeof(int));7        if (bigger == NULL) {8            return items;9        }10        items = bigger;11        *capacity *= 2;12    }13    items[*count] = value;14    *count += 1;15    return items;16}17 18int main(void) {19    int prices[5] = {12, 8, 25, 4, 30};20    int count = 0;21    int capacity = 1;22    int *list = malloc(capacity * sizeof(int));23    if (list == NULL) {24        return 1;25    }26    for (int i = 0; i < 5; i++) {27        list = push(list, &count, &capacity, prices[i]);28    }29    for (int i = 0; i < count; i++) {30        printf("%d ", list[i]);31    }32    printf("\nLength %d, capacity %d\n", count, capacity);33    free(list);34    return 0;35}

12 8 25 4 30 
Length 5, capacity 8

Press Step and go into push: in its box, the arrows from count and capacity point back at the variables in main's box, and items points at the block on the heap. If the memory can't be had, push adds nothing and hands back the old address as it was, so main's list is never lost.

Don't write *count += 1 as *count++: ++ comes before *, so that would move the pointer itself, not add to the number it points at.

Practice

Write the code, then press Check. A hint costs nothing; the answer is there when you need it.

88 76 91 70 95 

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5    int *scores = malloc(3 * sizeof(int));6    if (scores == NULL) {7        return 1;8    }9    scores[0] = 88;10    scores[1] = 76;11    scores[2] = 91;12 13    for (int i = 0; i < 5; i++) {14        printf("%d ", scores[i]);15    }16    printf("\n");17    free(scores);18    return 0;19}

8 6 4 10 2 
Length 5, capacity 8

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5    int numbers[8] = {3, 8, 6, 1, 4, 10, 7, 2};6    int count = 0;7    int capacity = 2;8    int *evens = malloc(capacity * sizeof(int));9    if (evens == NULL) {10        return 1;11    }12 13    for (int i = 0; i < count; i++) {14        printf("%d ", evens[i]);15    }16    printf("\nLength %d, capacity %d\n", count, capacity);17    free(evens);18    return 0;19}

5 9 2 7 

1#include <stdio.h>2#include <stdlib.h>3 4int main(void) {5    int values[4] = {5, 9, 2, 7};6    int count = 0;7    int capacity = 2;8    int *list = malloc(capacity * sizeof(int));9    if (list == NULL) {10        return 1;11    }12    for (int i = 0; i < 4; i++) {13        if (count > capacity) {14            int *bigger = realloc(list, capacity * 2 * sizeof(int));15            if (bigger == NULL) {16                free(list);17                return 1;18            }19            list = bigger;20            capacity *= 2;21        }22        list[count] = values[i];23        count++;24    }25    for (int i = 0; i < count; i++) {26        printf("%d ", list[i]);27    }28    printf("\n");29    free(list);30    return 0;31}

What you learned

• realloc(p, new_bytes) gives you a block of the new size with the old contents moved over and returns its address; from then on, use only the new address.
• Put the result in another pointer and check for NULL: on failure the old block is still there, and p = realloc(p, ...) would lose it.
• An array that grows tracks its length (how many are in it) and capacity (how many fit); when length equals capacity, it's full.
• When full, double the capacity: far fewer moves than growing by one.
• As a function, pass the length and capacity by address and return the block's address; free it once at the end.