Week 5

We start with the lines int* x; and int* y;, in which we declare two variables of type int*, or pointers to int values. So far these variables don’t point to anything, however.

We then give x somewhere to point with the line x = malloc(sizeof(int));, which allocates enough memory to fit an int and stores the address of this chunk of memory in x. In other words, x is now pointing to that address.

Next we store a value at the address of x with *x = 42;, which dereferences x (goes to the address x) and sets the value in that chunk of memory we just allocated to be the number 42.

Then we try to do the same for y with *y = 13;, but we haven’t allocated any memory for y to point at, so this makes Binky’s head explode. y contains some garbage value, which the program tries to interpret as an address somewhere in memory, but that location in memory doesn’t belong to the program so we can’t assign to it.

We then do y = x;, which sets the address stored in y to the address stored in x.

Now y points to memory we can use, so now we can dereference y and store the value 13 there. Note that because y and x store the same address, if we check what the value at x is now, we’ll also see 13!

It declares a variable x and printfs a message asking for a number, but what about line 7?

scanf "scans" the user’s input in from the keyboard, using a format string just like printf: %i means we expect an integer. Then we pass in &x, because we want the input to be saved at that location (the address of the int variable x). If scanf didn’t have access to the address of x, only a copy of x would be changed by scanf.

Hm, seems to work until we don’t cooperate and give it something that isn’t an int. Clearly we need to implement some kind of error checking to make sure the user really did type in a number.

This time we don’t say &buffer, because buffer is already an address.

But we realize this is a bad example. We create a char* buffer and expect scanf to take some string and put it in memory at whatever address buffer points to. But buffer is some garbage value, so scanf will put the input at an address that could be anywhere in memory. And if the memory doesn’t belong to us, then we’ll probably cause a segmentation fault and crash our program.

Note that when you see a video on YouTube or streaming elsewhere "buffering", that means that there’s an array of memory - typically more than 16 bytes, maybe 1 MB or 10 MB - that the video is being read into, and the video player has reached the end of the array before the streaming service has been able to fill up the array with more bytes of the video (often because of a slow network connection). A buffer is simply this sort of array of memory, into which we read content from somewhere.

Again, we don’t need to use &buffer, because arrays are represented by pointers to the actual memory where the contents of the array are stored, so buffer is itself an address.

Let’s run it:

jharvard@ide50:~/workspace/src5m $ ./scanf-1
String please: helloworld
Thanks for the helloworld!
jharvard@ide50:~/workspace/src5m $ ./scanf-1
String please: [very long string of many more than 16 characters]
Segmentation fault

This example is better, since we’re declaring an array of characters, which sets aside memory, and works perfectly, until we type in 16, 17, or more characters. Then that string will partly end up in buffer, but overwrite whatever is beyond the boundary of that array, since we only asked for 16 bytes.

We can support longer sentences by implementing a larger buffer, but that’s a waste of space if we don’t actually fill them. And even then, it’s still possible for a user to enter an even longer string.

Rather than assigning a buffer of a specific size, we’re starting with an empty buffer, and we’ll grow it to fit the user’s input. This lets us fit long input without having to allocate a lot of memory right away or set a specific length that the string must be.

We’ll malloc new memory each time we make the buffer larger and free the old memory.

Note that we’re keeping track of how long our buffer has gotten and how many chars we’ve actually stored in the buffer using unsigned int variables. Because an unsigned int doesn’t need to keep track of sign, it has one additional bit to use on the value (and thus twice as many possible values). Since sizes can’t be negative, we don’t need to use half our possible values on negative numbers.

...
    // character read or EOF
    int c;

    // iteratively get chars from standard input
    while ((c = fgetc(stdin)) != '\n' && c != EOF)
    {
...

c is a char, although we’re storing it as an int for reasons we won’t go into now.

You might’ve used fgetc on Problem Set 4, and certainly on Problem Set 5 it’ll be of use. It gets one character at a time from a file - in this case stdin, the "file" consisting of what the user is typing at their keyboard.

...
        // grow buffer if necessary
        if (n + 1 > capacity)
        {
            // determine new capacity: start at 32 then double
            if (capacity == 0)
            {
                capacity = 32;
            }
            else if (capacity <= (UINT_MAX / 2))
            {
                capacity *= 2;
            }
            else
            {
                free(buffer);
                return NULL;
            }

            // extend buffer's capacity
            string temp = realloc(buffer, capacity * sizeof(char));
            if (temp == NULL)
            {
                free(buffer);
                return NULL;
            }
            buffer = temp;
        }

        // append current character to buffer
        buffer[n++] = c;
    }
...

Note the line string temp = realloc(buffer, capacity * sizeof(char)); - the function realloc works like malloc, but allows you to make an existing chunk of memory larger or smaller.

This lets us grow the buffer as the user types more characters. Each time we run out of space, we double the size of our buffer to store what the user types.

This is a subjective design decision, though - it means we’re probably wasting a bit more space (e.g., if the string the user types in is one character longer than a power of 2, almost half the buffer will be empty) in order to be a little bit faster. These sorts of tradeoffs are the choices we often have to make when writing software.

Note that the other functions in the CS50 Library, like GetInt(), call GetString() to deal with actually getting the characters the user typed, and then parse those characters into the type they’re expecting:

 1...
 2/**
 3 * Reads a line of text from standard input and returns it as an
 4 * int in the range of [-2^31 + 1, 2^31 - 2], if possible; if text
 5 * does not represent such an int, user is prompted to retry.  Leading
 6 * and trailing whitespace is ignored.  For simplicity, overflow is not
 7 * detected.  If line can't be read, returns INT_MAX.
 8 */
 9int GetInt(void)
10{
11    // try to get an int from user
12    while (true)
13    {
14        // get line of text, returning INT_MAX on failure
15        string line = GetString();
16        if (line == NULL)
17        {
18            return INT_MAX;
19        }
20
21        // return an int if only an int (possibly with
22        // leading and/or trailing whitespace) was provided
23        int n; char c;
24        if (sscanf(line, " %i %c", &n, &c) == 1)
25        {
26            free(line);
27            return n;
28        }
29        else
30        {
31            free(line);
32            printf("Retry: ");
33        }
34    }
35}
36...

We’re using sscanf, a relative of scanf that lets us get values of particular types out of a string, rather than out of stdin.

We won’t go into why we’re using a %c format string in our call to sscanf as well as the %i format string to actually get the int, but suffice it to say for now that it lets us check that the user actually typed an int without any other junk.

This hasn’t been a huge problem because our programs automatically give back their memory when they exit, but a program that runs for a long time without exiting that has a memory leak will steadily use up your computer’s memory, slowing everything down.

If you’ve left your computer running for some time, opening lots of programs, and it gets slower, then the problem could be with certain programs asking for memory, and forgetting about it, taking it away from other programs and slowing everything else. (In particular, older versions of Firefox were often guilty of this.)

Invalid write means we tried to touch memory that didn’t belong to us, and size 4 means that the section of memory that we touched was 4 bytes.

Our other message, about memory being definitely lost, indicates that we allocated memory but didn’t give it back. To give back memory, we use the function free(), which takes just one argument - the variable that you want to give back.

In line 20, we declare a pointer variable x and assign to it the address returned by malloc, which allocates enough memory for 10 int values, or 40 bytes. This is giving us the 40 bytes in 1 blocks are definitely lost, because we don’t free this memory.

In line 21, we try to write to x[10], but the indices of x only go up to 9 (because it can contain 10 integers, we can access them as x[0] through x[9]). This gives us the Invalid write of size 4, because we’re trying to put an int (4 bytes) somewhere we don’t own.

If we change line 21 to x[9] = 0; and add free(x); right before we exit the function f, then valgrind will show us that we have no memory errors.

The boxes look orderly in the image, but in reality they might be all over the place, with arrows that link each rectangle to the next.

Because these boxes don’t have to be next to each other in memory, we can add more boxes to our list or remove boxes from our list without copying everything over to a new list.

A node is a general computer science term for an element in a data structure.

And we have everyone pointing to either the next node, or in the case of 34, pointing downward to represent NULL (i.e., the end of the list).

In this case, we have to be careful about our order of operations: if we have first point to 5 before we have anything point at 9, then we’ve lost our access to the rest of the list. So we have 5 point at 9 first, then have first point at 5.

Storing the same number of values in a linked list takes twice as much space as in an array - we’re not just storing an int in each node, we’re storing an int and a pointer to the next node.

We have to traverse the linked list one node at a time, so we can’t use the square bracket notation to go directly to a particular node in the list anymore. The ability to index directly into any element of an array is called random access. Without random access, for example, we can only use linear search (and not binary search), because we can’t go straight to the middle of the list.

This represents a data structure appropriately called a stack, or LIFO, for last in, first out (i.e., the last value added to the stack is the first value taken off it).

This represents a data structure called a queue, or FIFO, for first in, first out.