David Chiu

Professor of Computer Science
University of Puget Sound
dchiu@pugetsound.edu


home | teaching | research | people | service | faq for students

CS 475 - Operating Systems

Lab 2: Pointers and Addressing (Not Graded)

This is the second part of a multi-part primer on C. In this tutorial-assignment, you’ll gain an appreciation for the way values and variables are stored in memory. You’ll be introduced to pointers, as well as the connection between pointers and arrays.

Student Outcomes

Instructions

Open your VS Code and get connected to your Remote Development environment. If you don’t know what I’m referring to, then you need to complete Hwk 1.

Preamble: Notepads, Street Addresses, and Buildings

Pointers are powerful structures in C. To get a sense of what pointers are, let’s use a real-world analogy:

Therefore, you wouldn’t ever say that a street address is itself a building, but it does tell you where to go to find it.

Real-World Analogy Explanation
Any building always has a corresponding street address. You just have to ask for it! This is what the *address-of operator & provides.*
You can navigate to the building located at an address: examine it, destroy it, change it. This is what it means to *de-reference a pointer.*
You can reuse the notepad by writing a different building address on it. The pointer variable can be reassigned to point at a different piece of data.
You can write an address on a notepad, and share the notepad with others. A pointer can be passed in as function input-parameters so it can find the piece of data too.
You can check out the neighboring building, and the one after that, … This is called pointer arithmetic. Once you have an address, you can visit the nearby element effortlessly.

Under this scheme, think about what pointers would enable us to do:

Part 1: Memory and Data Types

How is data stored and managed inside your machine? Think of your computer’s memory as being a giant array of bytes. Each byte corresponds to a unique address in memory. Depending on the data’s type, a piece of data may occupy a range of bytes. Consider the following code snippet:

1
2
3

char letter = 'p';    // chars are 1 byte long
int days = 365;       // ints are 4 bytes long
double amt = 90000.75;    // doubles are 8 bytes long

Let’s take a look at a snapshot of what my memory might look like as it runs the above code

There are several things worth noting:

  1. There’s no guarantee that the variables are grouped together like this in memory.
  2. A word (4 contiguous bytes in this figure) is what we call a unit of data transfer between the memory and CPU. Although the figure only shows the starting addresses for each word, it should be noted that each byte is also addressable.
  3. Word Alignment: There are 3 wasted bytes that follow the 'p' character. Sure, we could use those bytes to store 3 out 4 bytes of days, but now days would span across two words. This is not ideal, because it would require 2 transfers just to read/write the days variable. To avoid this, your system prefers to align data on the order of words.
  4. Yes, it would require this system to make 2 transfers to read/write amt since it spans 2 words – a reason why earlier systems preferred avoiding doubles if you didn’t need its range and precision. This is why float types exist – they are only 1 word wide!

Important C Operator: sizeof() Notice from the figure above that that an int takes up four contiguous bytes, a char requires just one byte, and a double requires eight. The specific space requirements for each data type actually vary across architectures, so how did I know these storage requirements apply to my machine? C provides an important operator sizeof() for this purpose. It inputs the name of a variable, a data type, or an expression, and returns the size in bytes that it occupies in memory.

Part 2: Understanding Addressing and Pointers

Every piece of data in your program, whether it’s a variable or a literal (like 3.14), is stored in two pieces: its content and its address. It is possible, for programmers to ask the OS for the addresses of your data, but we can’t tell it where to place them. This section focuses on the support for working with a variable’s location in C. In particular, we will focus on three syntax items: the address-of operator, the pointer-declaration operator, and the de-referencing operators.

  1. Let’s now consider the code below. Read through it before moving on.

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

    char letter = 'p';
int days = 365;
double amt = 90000.75;

int *ptr;       //declare pointer to an int
ptr = &days;    //point ptr at days
printf("There are %d days\n", days);
printf("There are %d days\n", *ptr);

(*ptr)--;   //decrement days by 1
printf("There are now %d days\n", days);
printf("There are now %d days\n", *ptr);

//print addresses
printf("Location of days: %p\n", &days);
printf("Location of ptr: %p\n", &ptr);
printf("Value of ptr: %p\n", ptr);

  2. In this simplified example, we’ll assume that the operating system places days in bytes 1112 to 1115, letter in byte 1116, and amt in bytes 1120 to 1127.

  3. Here is an example output when this program is executed.

    1
2
3
4
5
6
7

    There are 365 days
There are 365 days
There are now 364 days
There are now 364 days
Location of days: 0x458
Location of ptr: 0x8A2C
Value of ptr: 0x458

  4. Let’s now go back and explain the source code.

    • On Line 5, we see a new kind of variable-declaration syntax:

      1

      int *ptr;       //declare pointer to an int

      This declares a new variable named ptr, and unlike anything we’ve seen before, it holds a memory address, which references an int value. In other words, ptr is a pointer to an integer. Of course, ptr is itself a variable that requires storage, and our figure shows that ptr itself is located in byte addresses 35372 to 35375.

    • On Line 6:

      1

      ptr = &days;    //point ptr at the address of days

      The operator &var returns the address of var. Even though day occupies four bytes because it is an int, only the address of its first byte (1112) is returned. Thus, ptr = &days will assign 1112 to ptr. That’s how pointers (called “references” in Java) work! They’re just variables that store addresses to data.

    • Line 8 introduces an important operation, called dereferencing.

      1

      printf("There are %d days\n", *ptr); // *ptr is used to chase the pointer to the content!

      Dereferencing is used when we’re interested in uncovering the content that’s referenced by ptr. If we simply output the value of ptr, we’d still get 1112, which is not what we want in this case. Therefore, when the objective is to “follow” the pointer to its destination, we use the dereferencing operator *var, where var is a pointer variable. (This irks me a bit, because the * operator now has 3 interpretations in C: multiply, declaration of a pointer variable, and pointer dereference. Expect this to lead to headaches down the line.)

    • On Line 10:

      1

      (*ptr)--;   //decrement the content of 'days' by 1

      Okay this is a strange one. ptr is first de-referenced to return the content 365. The de-referenced content is then decremented to 364.

    • On Lines 15-17: shows that we can use the output specifier, %p to print an address (in hexadecimal).

      1
2
3

      printf("Location of days: %p\n", &days);   // 0x458
printf("Location of ptr: %p\n", &ptr);     // 0x8A2C
printf("Value of ptr: %p\n", ptr);         // 0x458

      The addresses of days (0x458 == 1112) and ptr (0x8A2C == 35372) are first printed. This is followed by printing the contents of ptr, which unsurprisingly, stores the address of days.

Part 3: Pointer Operators: &, *

Let’s put everything together.

  1. Address-Of Operator: Given a variable var, &var returns the address of var’s location in memory.

  2. A pointer variable stores the address of some data. This data can be a variable, an array, or even another pointer. To declare a pointer, you use the following syntax:

    1

    data-type *ptr;          // Pointer to some data that's described by the given data type.

    When assigning a pointer q to another pointer p, it causes them both to point to the same data.

    1
2
3
4

    double *a = NULL, *b = NULL;
double c = 10;
b = &c; // point b at c
a = b;  // point a at c (why don't I need to use &b here?)

    • Memory contents after the declaration:

    • Memory contents after the assignment statements on Lines 3, 4:

    • You must first #include <stdlib.h> to get access to the NULL constant.

  3. The De-reference Operator: Given an already-declared pointer ptr, we use *ptr to access the value at the location referenced by ptr. As I lamented earlier, I wish we chose a different syntax for dereferencing, because *ptr already has a different meaning!

    1
2

    *b = 15; // de-reference b to get to c's content! c is now 15
*a += 5; // de-reference a to get to c's content! c is now 20
Part 4: Pointers as Input Parameters

Remember how I mentioned that, for efficiency, you can pass an address/pointer into a function instead of passing the entire building? Consider the following function that modifies a large struct without using pointers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

typedef struct employee_t {
  char ssn[11];
  char name[100];
  int salary;
  // more members omitted
  // ...
} employee_t;

employee_t increaseSalary(employee_t emp) {
  emp.salary *= 1.03;
  return emp;
}

void main() {
  employee_t david;
  strcpy(david.ssn, "123");
  strcpy(david.ssn, "David C");
  david.salary = 20000;
  david = increaseSalary(david); // yikes
}

This code runs, but it’s really cumbersome. To call increaseSalary(david), C needs to package up all those values in the struct and pass the whole thing as a value. Because any changes done in increaseSalary(david) are local to it, they’d be lost if you didn’t return the entire struct back to the caller! Look, we’re moving the entire building … twice!

Intead, let’s just pass the address of the employee to the function. The function can follow the address to make the salary updates. This saves the C runtime system from making a clone of the employee and passing it around!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

typedef struct employee_t {
  char ssn[11];
  char name[100];
  int salary;
  // more members omitted
  // ...
} employee_t;

/** Now inputs a pointer to an employee! */
void increaseSalary(employee_t *emp) {
  emp->salary *= 1.03;  // What's this struct->member operator???? 
}

void main() {
  employee_t david;
  strcpy(david.ssn, "123");
  strcpy(david.ssn, "David C");
  david.salary = 20000;
  increaseSalary(&david); // done in place!
}

In the code above, notice:

  1. Main simply sends along an employee’s address (using the & operator), not their entire content!
  2. If increaseSalary() knows exactly where to go to reach the affected employee, then any changes to it are done directly! No need to return the employee anymore. (That’s what we remember doing in Java!)
  3. Important: When p is a pointer to a struct, you can de-refernce one of p’s members using either:
    • (*p).member = expression – this de-references p first, then applies the usual dot notation to access its member.
    • Or a nice shortcut is usually done in practice: p->member = expression
Part 5: “Output” Parameters

Have you ever wished that a function/method could return more than one thing? To do this Java, you always had to create a new class that stored multiple values and return an object of that class, or you returned an array of values. Sure, you can also do any of the above in C, but pointers give us another way to emulate “returning” multiple values (without actually calling return to do it).

“Output Parameters”: An output parameter refers to a pointer that is input into a function, and the function modifies its contents before exiting. After the function call, one just needs to dereference the pointer to obtain the updated value(s).

Part 6: Connection to Arrays (Pointer Arithmetic)

In this section, we’ll explore the relationship between pointers and arrays.

  1. Study the following source file, then compile and run it.

    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

    #include <stdio.h>

#define BUFFERSIZE 4

int main(int argc, char* argv[])
{
    int arr[BUFFERSIZE] = {9,8,7,6};
    int i;

    printf("*** where is arr[0] stored? ***\n");
    printf("arr[0] location: %p\n", &arr[0]);

    printf("\n*** where is arr stored? ***\n");
    printf("arr location: %p\n", arr);

    printf("\n*** print out contents using pointer arithmetic ***\n");
    for (i = 0; i < BUFFERSIZE; i++)
        printf("%d ", *(arr+i));

    printf("\n\n*** print out contents using familiar subscript syntax ***\n");
    for (i = 0; i < BUFFERSIZE; i++)
        printf("%d ", arr[i]);

    return 0;
}

  2. Arrays represent a contiguous sequence of elements in memory. It is therefore not surprising to find arr being represented as in the figure below, with each int element occupying 4 bytes. When compiled and executed, this program outputs something akin to the following:

    1
2
3
4
5
6
7
8
9
10
11

    *** where is arr[0] stored? ***
arr[0] location: 0x4318

*** where is arr stored? ***
arr location: 0x4318

*** print out contents using pointer arithmetic ***
9 8 7 6

*** print out contents using familiar subscript syntax ***
9 8 7 6

  3. Looking at the source code,

    • Lines 11 and 14: Suppose we want to find the address of the 0th element in arr. We can simply apply the & operator on element arr[0] to get its address:

      1

      printf("arr[0] location: %p\n", &arr[0]);

      The code on Line 14, however, may be slightly unexpected, and it’s equivalent! There’s no address-of operator (that’s not a typo!)

      1

      printf("arr location: %p\n", arr);

      It would appear that an array’s variable name is already a pointer to the location of its 0th element! By the way, 0x4318 is hexadecimal for 17176 (for the figure below).

    • Line 16-18: Knowing this, let’s try something else. Because arr is just a pointer, can we also dereference it to access the array elements? Yes!!

      • *(arr+0), or simply, *arr returns 9

      Pointer Arithmetic Exciting! How would we access the array element at index 1? The runtime is smart enough to know that the next element is 4 bytes away because the array was declared to store ints. So adding 1 to the pointer will automatically skip the next 3 bytes and move the pointer to the next item in the array!

      • *(arr+1) returns 8
      • *(arr+2) returns 7
      • *(arr+3) returns 6

    • Line 20-22 (Important!) Finally, the array indexing syntax [i] we’re all familiar with, is merely a convenience for programmers: Indeed, arr[i] is actually just a shorthand for *(arr+i)

      • (Full circle now – Zero-based Addressing): This may have only come up briefly in a previous course, but now we can appreciate why array indices are 0-based in just about every language, and it’s due to pointer arithmetic! If we store the first item in location [1], then the C compiler would need to subtract 1 when performing each array index lookup. That’s just an unnecessary overhead!

  4. Arrays are “passed by reference”: Now that we know an array variable is just the address of its 0th element, take a look at the following functions that manipulate the array. Each of the following functions have the same effect (initializes all elements to -1)! Make sure you read through each and understand why.

    1
2
3
4
5
6

    void initArray(int *A, const int SIZE) {
  int i;
  for (i = 0; i < SIZE; i++) {
      A[i] = -1;
  }
}

    By the way, the following code also works:

    1
2
3
4
5
6

    void initArray(int A[], const int SIZE) {
  int i;
  for (i = 0; i < SIZE; i++) {
      A[i] = -1;
  }
}

    Important side note: Because arrays are passed as pointers, you can now appreciate why modifications to arrays persist after the function terminates (this is also true in Java!).

Important Summary: Why Do We Need Pointers?

Let’s pause here and ask why pointers are needed at all? There are several reasons to use pointers:

Credits

Written by David Chiu. 2022.