Class 15 — Thursday, October 15

A function that hands back an array of its own: malloc, free, and memory that belongs to no function.

First, the presentation of A6. Then the Opening Journal: its prompt is in the announcements on Brightspace.

1 An array that outlives its function

Every array so far was declared in main, or in the function that used it. This function makes one of its own and hands it back. Nobody compiles until it is announced. Predict first, in the Journal: does it compile, and what does it print?

#include <stdio.h>
#define SIZE 3

// returns an array holding 0, 1, 2
int * make_range() {
    int a[SIZE];
    int i = 0;
    for (int * p = a; p < a + SIZE; p++) {
        *p = i;
        i++;
    }
    return a;
}

int main() {
    int * r = make_range();
    printf("%d %d %d\n", r[0], r[1], r[2]);
}

a is make_range’s own variable, and a function’s variables are gone when it returns. r holds the address of memory that belongs to nobody any more, and reading it is undefined behavior.

malloc hands out memory that belongs to no function: it stays until free gives it back. It takes a size in bytes and returns the address of the first one, or NULL when there is no memory left.

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

// returns a new array of n elements holding 0, 1, ..., n - 1
int * make_range(int n) {
    int * a = malloc(sizeof(int) * n);
    assert(a != NULL);
    int i = 0;
    for (int * p = a; p < a + n; p++) {
        *p = i;
        i++;
    }
    return a;
}

int main() {
    int n = 3;
    int * r = make_range(n);
    for (int i = 0; i < n; i++) {
        printf("%d ", r[i]);
    }
    printf("\n");
    free(r);
}
The 3-step malloc protocol
  1. malloc takes the size of the array you need in bytes, so sizeof(int) * n, not just n. And n can be any number main has while it runs, where int a[SIZE] needed a constant.

  2. The assert checks the address against NULL before it is used.

  3. And free(r) gives the memory back, once, from wherever the last copy of the address is.

2 Memory you ask for, in pairs

Pairs protocol
  1. The navigator (not typing) says the examples first: each assert line. Then they say the steps the function takes.
  2. The driver types the above, and decides how each step becomes C.
  3. If either of you is stuck, drop the roles for a minute and talk it over.
  4. Swap at every function.

Still no [ or ] inside any function: walk with a pointer. Every function gets the design recipe’s one-line comment and two asserts of your own beside the one given, and every array that was asked for is freed.

Before anything else, entr in a second terminal, so that every save recompiles and runs your file: the command is on the command line page. malloc and free need #include <stdlib.h>; strlen and strcmp need #include <string.h>.

2.1 range

Write int * range(int start, int end), which hands back a new array holding start, start + 1, and so on up to end - 1. Work out first how many elements that is:

int main() {
    int * r = range(3, 8);
    assert(r[4] == 7);
    free(r);
}

Then two asserts of your own, one of them awkward: a range that starts below zero, say, or one too long for anyone to declare its array in main.

Done when the asserts pass. Then read start and end with scanf instead of writing them, and check again with numbers of your own. Then try 8 and 3: what stops the program, and where? Put // in front of the assert, and try 8 and 3 again.

2.2 copy

Write char * copy(char * s), which hands back a new string holding the same characters as s. The reading’s strlen counts them; the '\0' needs a byte of its own.

int main() {
    char word[] = "hello";
    char * c = copy(word);
    assert(c != word);
    free(c);
}

The assert says the copy lives somewhere else. Then two of your own, one of them awkward: that the copy holds the same characters, that changing it leaves word alone, or the empty string.

Done when the asserts pass.

2.3 read_numbers

From here on, for pairs who are done with 2.1 and 2.2.

Write int * read_numbers(int n), which reads the next n numbers from the input with scanf into a new array and hands it back. scanf("%d", p) takes no & when p is already an address. main reads n first, then prints the numbers backwards:

int main() {
    int n;
    scanf("%d", &n);
    int * a = read_numbers(n);
    for (int i = n - 1; i >= 0; i--) {
        printf("%d\n", a[i]);
    }
    free(a);
}

Make a file numbers.txt holding 4 on its first line and 8 15 16 23 on its second, then run ./readnums < numbers.txt. Done when it prints 23, 16, 15, 8, each on its own line. No #define SIZE could have written this program: how many numbers there are is not known until it runs.

2.4 repeat

Write char * repeat(char * s, int k), which hands back a new string holding s written k times:

int main() {
    char * r = repeat("ab", 3);
    assert(strcmp(r, "ababab") == 0);
    free(r);
}

strcmp, from the reading, returns 0 when two strings hold the same characters. Then two asserts of your own, one of them awkward: k of 0, or an empty s.

Done when the asserts pass.

3 Keep going

For pairs who are done with section 2: one harder function, then the book’s own questions.

3.1 merge

Write int * merge(int * a, int na, int * b, int nb). a holds na values and b holds nb, each in increasing order, and merge hands back a new array of all na + nb values, in increasing order. Its recipe comment says who frees that array:

// returns a new sorted array of the values of a and b; the caller frees it

Three pointers do the work: one walks a, one walks b, and one writes the new array. While both a and b have values left, copy the smaller and move its pointer on; then copy whatever is left.

#define NA 3
#define NB 4

int main() {
    int a[NA] = {1, 4, 9};
    int b[NB] = {2, 3, 10, 12};
    int * m = merge(a, NA, b, NB);
    assert(m[3] == 4);
    free(m);
}

Then two asserts of your own, one of them awkward: a with no values at all, or every value of a smaller than every value of b.

Done when the asserts pass.

3.2 The book’s own questions

Dive Into Systems has checkpoint questions for its sections, and they check each answer as you give it: 2.4, dynamic memory allocation, and 2.6, strings. Tuesday’s Quiz 6 is on 2.4 and 2.6.2, so they are worth doing before then, here or at home.

4 Before you leave