Chrysolites Tech Academy

Introduction to Computer Science: Harvard CS50 · Course book

Chapter 4: Addresses, Pointers and the Heap

Pairs with Lesson 4: Memory, Pointers and Files

Every variable a program uses lives somewhere in the computer's memory, and every location in memory has an address, much like every house on a street has a number. Most languages hide this. C exposes it, which makes C both powerful and dangerous. This chapter explains how addresses are written, what a pointer is, why strings in C behave in surprising ways, how a program asks for more memory while it runs, and how memory is laid out. Understanding these ideas explains a whole class of bugs, and many security problems, that would otherwise seem mysterious.

Addresses and hexadecimal

Memory is a long row of bytes, each with a numbered address. Addresses are large numbers, and programmers usually write them in hexadecimal, base 16, because it maps neatly onto binary. Hexadecimal needs sixteen digits, so after 0 to 9 it uses the letters A to F for ten to fifteen.

DecimalBinaryHexadecimal
000000
910019
101010A
151111F
160001 000010
2551111 1111FF

Each hexadecimal digit stands for exactly four bits, so one byte is always two hex digits. FF is 15 × 16 + 15 = 255, the largest value a byte can hold. To avoid confusion with decimal, hex numbers are written with the prefix 0x: 0x10 means sixteen, not ten. A colour you may have seen in web design, #FF0000, is three bytes in hex: full red, no green, no blue.

Pointers

A pointer is a variable that holds an address. C has two operators for working with them. The ampersand, &, means "the address of": if n is an int, &n is where n is stored. The star, *, used in a declaration, means "a pointer to": int *p declares p as a pointer to an int. Used in an expression, * means "go to the address and use what is there", which is called dereferencing.

int n = 50;
int *p = &n;
printf("%p\n", p);   // prints an address, such as 0x7ffc3a2c
printf("%i\n", *p);  // prints 50, the value at that address
50 n address 0x123 0x123 p (int *) address 0x456 points to *p means "the value at the address in p", which is 50
Figure 4.1 — A pointer holds an address. Following it, by dereferencing, reaches the value stored at that address.

On a modern 64-bit computer an address, and so every pointer, takes 8 bytes. Pointers are easier to understand as arrows than as numbers: what matters is not the particular address but what it points to.

Pointers also explain why some functions need an ampersand. A function that reads a number typed by the user, such as the standard function scanf, cannot simply be given a variable, because it would receive a copy and fill in the copy. Instead it is given the variable’s address, as in scanf("%i", &n), so that it can store the number directly where n lives.

What a string really is

Chapter 3 described a string as an array of characters ending in \0. Behind the scenes, a variable of type string is actually a pointer to the first of those characters, a char *. Functions such as printf follow the pointer and read characters until they reach \0. The teaching library's word string is a convenient name for char *.

The square brackets used with arrays are themselves shorthand for pointer arithmetic. If s points to the first character, s + 1 points to the second, and *(s + 1) is the second character, exactly what s[1] means. Adding 1 to a pointer moves it forward by the size of one element: one byte for a char, four bytes for an int. An array name used in an expression behaves like a pointer to its first element, which is why arrays and pointers are so closely linked in C.

That explains two puzzles. First, comparing two strings with == checks whether the two pointers are equal, meaning whether they hold the same address. Two strings typed separately as "hello" live at different addresses, so == says they differ even though their characters match. The correct tool is the function strcmp, which compares character by character and returns 0 when the strings are the same.

Second, copying a string with = copies only the pointer. After string t = s;, both names point to the same characters, so changing t[0] changes s too. A true copy needs new memory of the right size and a character-by-character copy, which brings us to asking for memory.

Asking for memory, and giving it back

A program can request a block of memory while it runs with the function malloc, short for memory allocate, telling it how many bytes are needed. To copy a string of 5 characters, the program asks for 6 bytes, one more for \0, then copies the characters across with a loop or with the function strcpy. malloc returns the address of the new block, or a special value called NULL if no memory is available, which careful code always checks.

Put together, a correct copy looks like this:

char *t = malloc(strlen(s) + 1);
if (t == NULL)
{
    return 1;
}
strcpy(t, s);
t[0] = toupper(t[0]);
free(t);

The first line asks for one byte more than the length of s, for the null character. The check stops the program cleanly if memory ran out. strcpy copies every character including , after which t is a separate string, so capitalising its first letter leaves s untouched. Finally free returns the memory.

Memory obtained with malloc must be handed back with free when it is no longer needed. Forgetting is called a memory leak: the program holds on to memory it no longer uses, and a long-running program that leaks steadily can slow down or crash the whole computer. Tools exist that run a program and report leaks and other memory errors, such as reading beyond the end of a block.

Uninitialised memory. A newly declared variable in C holds whatever bits were last left in that spot, called a garbage value. Using a pointer before giving it a real address means following an arrow to a random location, one of the most common causes of crashes.

How memory is laid out

A running program's memory is organised into regions with different jobs.

machine code global variables heap free space stack malloc takes memoryfrom here, growing downeach function call addsa frame, growing up
Figure 4.2 — The regions of a program's memory. The heap and the stack grow towards each other into the free space between them.

The stack holds the local variables of each function call. When a function is called, a new frame is added on top; when it returns, its frame is removed. That explains a classic puzzle. A function swap(int a, int b) that exchanges its two parameters appears to do nothing, because a and b are copies living in swap's own frame, which disappears when it returns. The fix is to pass pointers, swap(&x, &y), so that the function can reach the original variables through their addresses.

The stack is fast and automatic, but it is small and its contents vanish when a function returns, so a function must never return the address of one of its own local variables. Anything that needs to outlive the function that created it, such as a string built inside a helper function and used later, belongs on the heap instead. Deciding where each piece of data should live is one of the central skills of programming in C.

The heap holds memory obtained with malloc, which stays until freed. If a program calls functions too deeply, for example through recursion with no base case, the stack runs into the heap: a stack overflow. Writing past the end of an array, a buffer overflow, can overwrite neighbouring data and is a long-standing source of security weaknesses, which is why modern languages check bounds automatically.

The same tools let programs read and write files. Opening a file gives a pointer through which bytes can be read; many file types announce themselves with a few signature bytes at the start, for instance JPEG photographs begin with the bytes 0xFF 0xD8 0xFF, which is how software can recognise an image even without its file name.

Images are stored the same way. A simple bitmap file begins with a short header describing the width, height and colour depth, followed by the pixels themselves, typically three bytes per pixel for red, green and blue. A program that reads the header can work out exactly where each pixel lies in the file and change it, which is how filters that brighten, blur or convert a picture to grey work at their simplest level. Recovering deleted photographs from a memory card relies on the same knowledge: the program scans the raw bytes for the JPEG signature and copies out everything from one signature to the next.

Check your understanding

  • Convert 0x2A to decimal. (Answer: 2 × 16 + 10 = 42.)
  • Write 200 in hexadecimal. (Answer: 12 × 16 = 192, remainder 8, so C8.)
  • If int *p = &n; and n is 7, what is *p? (Answer: 7.)
  • Why does s == t usually give false for two strings with the same characters?
  • How many bytes must be allocated to copy the string "memory"? (Answer: 7.)
  • Why does a swap function that takes two ints not swap the caller's variables?
  • What is a memory leak, and how is it prevented?

Install Chrysolites Tech Academy

Android / Chrome / Edge: open the browser menu and choose Install app or Add to Home screen.

iPhone / iPad (Safari): tap the Share button, then Add to Home Screen.