Week 4, continued

Pointers are one of the more complex topics we cover, so don’t feel bad if your mind feels stretched in the next few weeks. That’s a good thing!

Recall last time we ended with a function that didn’t live up to its name:

#include <stdio.h>

void swap(int a, int b);

int main(void)
{
    int x = 1;
    int y = 2;

    printf("x is %i\n", x);
    printf("y is %i\n", y);
    printf("Swapping...\n");
    swap(x, y);
    printf("Swapped!\n");
    printf("x is %i\n", x);
    printf("y is %i\n", y);
}

void swap(int a, int b)
{
    int tmp = a;
    a = b;
    b = tmp;
}

Though we expected to see x and y have the values 2 and 1, respectively, we actually saw that they still had their original values 1 and 2.

To see why this doesn’t work, let’s bring a volunteer onstage. We’ll ask her to pour orange juice and milk into two separate glasses representing two different int. If we ask her to swap the orange juice and milk, she wisely chooses to use another glass. This glass represents some temporary storage which we call tmp in the swap function above. Interestingly, if we implement the same code directly in main, the swapping actually works:

#include <stdio.h>

int main(void)
{
    int x = 1;
    int y = 2;

    printf("x is %i\n", x);
    printf("y is %i\n", y);
    printf("Swapping...\n");

    int tmp = x;
    x = y;
    y = tmp;

    printf("Swapped!\n");
    printf("x is %i\n", x);
    printf("y is %i\n", y);
}

So why does this logic work in main but not in swap? a and b are actually copies of x and y, so when we swap a and b, x and y are unchanged.

One way to fix this would be to make x and y global variables, declaring them outside of main. In fifteen.c, it made sense to make certain variables global because they were to be used by the whole program. However, in a small program like noswap.c, using global variables is sloppy design.

How can we change the definition of swap to work as intended? Turns out we just need to add asterisks:

void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

What is an int*? It’s the memory address of an int. More properly speaking, it is a pointer to an int. If your computer has 2 gigabytes of RAM, then there are 2 billion bytes, each of which has a memory address. Let’s say the int that a points to is stored at the 123^rd byte of RAM. The value of a then, is 123. To get at the actual integer value that’s stored at byte 123, we write *a. *a = *b says "store at location a whatever is at location b."

Now that we’ve changed swap, we need to change how we call swap. Instead of passing x and y, we want to pass the address of x and the address of y:

swap(&x, &y)

& is the "address-of" operator and * is the dereference operator.

Let’s assume our integers 1 and 2 are stored next to each other in memory and 1 is stored at byte 123. That means 2 is stored 4 bytes away (since an int requires 4 bytes), so we’ll assume that it’s stored at byte 127. The values of a and b, then, are 123 and 127. We can simulate passing those to swap by writing them on pieces of paper and putting them in a black box.

We ask a volunteer to come onstage and retrieve the pieces of paper from the black box. Next he needs to allocate a little bit of memory for variable tmp. In tmp, he stores the value of the int whose address is in a. This is 1.

Next, at address 123, he erases the number 1 and writes in the number 2. This corresponds to the *a = *b line, which says "store at location a whatever is at location b."

Finally, at address 127, he erases the number 2 and writes in the number 2, which was stored in tmp. tmp is a local variable, but goes away when swap returns.

For the first few weeks, we have worked with string as a data type. However, this is a type that we defined for you in the CS50 Library. A string is really a char*. It’s the address of a char. In fact, it’s the address of the first char in the string.

Consider the following program which claims to compare two strings:

#include <cs50.h>
#include <stdio.h>

int main(void)
{
    // get line of text
    printf("Say something: ");
    string s = GetString();

    // get another line of text
    printf("Say something: ");
    string t = GetString();

    // try (and fail) to compare strings
    if (s == t)
    {
        printf("You typed the same thing!\n");
    }
    else
    {
        printf("You typed different things!\n");
    }
}

Here, we simply ask the user for two strings and store them in s and t. Then we ask if s == t. Seems reasonable, no? We’ve used the == operator for all the other data types we’ve seen thus far.

But if we compile and run this program, typing "hello" twice, we always get "You typed different things!"

Recall that a string is just an array of characters, so "hello" looks like this in memory:

Although we’re able to access the first character "h" using bracket notation, under the hood it’s really located at one of 2 billion or so memory addresses. Let’s call it address 123 again. Then "e" is at address 124, "l" is at address 125, and so on. A char only takes 1 byte, so this time the memory addresses are only 1 apart.

If GetString is getting us this string, then what does it actually return? The number 123! Before it does so, it allocates the memory necessary to store "hello" and inserts those characters along with the null terminator.

But if we only know the memory address of the first character, how do we know how long the string is? Recall that strings end with the special \0 character, so we can just iterate until we find it.

compare-0.c is buggy because it’s comparing the memory addresses of the two strings, not the strings themselves. Maybe s is stored at memory address 123 and t is stored at memory address 200. Since 123 does not equal 200, our program says they’re different strings.

Let’s take a look at a program that tries, but fails to copy a string:

#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    // get line of text
    printf("Say something: ");
    string s = GetString();
    if (s == NULL)
    {
        return 1;
    }

    // try (and fail) to copy string
    string t = s;

    // change "copy"
    printf("Capitalizing copy...\n");
    if (strlen(t) > 0)
    {
        t[0] = toupper(t[0]);
    }

    // print original and "copy"
    printf("Original: %s\n", s);
    printf("Copy:     %s\n", t);
}

We check that s isn’t NULL in case the user has given us more characters than we have memory for. NULL is actually the memory address 0. By convention, no user data can ever be stored at byte 0, so if a program tries to access this memory address, it will crash.

Now that we have the user-provided string in s, we assign the value of s to t. But if s is just a memory address, say 123, then t is now the same memory address. Both s and t are pointing to the same chunks of memory.

To prove that this program is buggy, we’ll try to capitalize t, but not s. The output, though, shows that both s and t are capitalized.

To emphasize that their role is to point to other variables, pointers are often represented as arrows.

Finally, a program that truly compares two strings:

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    // get line of text
    printf("Say something: ");
    char* s = GetString();

    // get another line of text
    printf("Say something: ");
    char* t = GetString();

    // try to compare strings
    if (s != NULL && t != NULL)
    {
        if (strcmp(s, t) == 0)
        {
            printf("You typed the same thing!\n");
        }
        else
        {
            printf("You typed different things!\n");
        }
    }
}

Now that we know a string is really just a char*, we need to be careful it’s not NULL.

strcmp is short for "string compare." It’s a function that comes in string.h, which, according to the man page, returns 0 if two strings are identical, a negative number if the first string argument comes before the second string alphabetically, or a positive number if the first string argument comes after the second string alphabetically.

Copying a string is a little more complicated than just using the assignment operator:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

#include <cs50.h>
#include <ctype.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    // get line of text
    printf("Say something: ");
    char* s = GetString();
    if (s == NULL)
    {
        return 1;
    }

    // allocate enough space for copy
    char* t = malloc((strlen(s) + 1) * sizeof(char));
    if (t == NULL)
    {
        return 1;
    }

    // copy string, including '\0' at end
    int n = strlen(s);
    for (int i = 0; i <= n; i++)
    {
        t[i] = s[i];
    }

    // change copy
    printf("Capitalizing copy...\n");
    if (strlen(t) > 0)
    {
        t[0] = toupper(t[0]);
    }

    // print original and copy
    printf("Original: %s\n", s);
    printf("Copy:     %s\n", t);

    // success
    return 0;
}

In line 17, we’re declaring a pointer t and initializing it with the return value of a function named malloc. malloc takes a single argument, the number of bytes of memory requested, and returns the address in memory of the first of those bytes or NULL if the memory couldn’t be allocated.

In this case, we’re allocating enough memory for all the characters in s plus 1 extra for the null terminator. We multiply this number of characters by sizeof(char), which gives the size in bytes of a char on this particular operating system. Normally it will be 1, but we’re handling other cases correctly, too.

Once we have enough memory, we iterate through all of the characters in s and assign them one at a time to t.

Let’s analyze some seemingly innocuous lines of code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

int main(void)
{
    int* x;
    int* y;

    x = malloc(sizeof(int));

    *x = 42;

    *y = 13;

    y = x;

    *y = 13;
}

First, we declare two pointers x and y. We allocate enough memory to store an int and assign its address to x. We store the value 42 in this memory. Then we store in the memory address y the value 13. But wait, we didn’t allocate memory for a second int, so what does y point to? Who knows! That’s the problem. Line 10 is pretty painful for Binky.