Pointers

Pointers lets us share data. Instead of passing in a copy of a value to a function, I can share the value with the function. No matter the size of the value – hundreds of bytes to gigabytes – its address still fits in 8 bytes (on a 64 bit machine), so that way of sharing is clearly more efficient.

In C, pointers allow us to define recursive data structures because implicit in each pointer value is its possibility of being NULL, i.e., the absence of the location of some value.

The main problem with pointers surface when you use them to share mutable state. This is a typical C pattern, but one that must be handled with care. The most subtle problems happen when two or more “agents” unknowingly shares a common value via pointers. A simple example:

void example(int *a, int *b)
{
  *a = 42;
  *b = 4711;
}

void%20example%28int%20%2Aa%2C%20int%20%2Ab%29%0A%7B%0A%20%20%2Aa%20%3D%2042%3B%0A%20%20%2Ab%20%3D%204711%3B%0A%7D%0A

If example() happens to get called with the same pointer as both a and b, the second update will overwrite the first! This might come as a surprise!

Furthermore, pointers in combination with malloc() needs to be freed using free(). However, in many programs it can be very hard to figure out e.g.,

• Who is responsible for freeing something?
• When is it safe to free something? (What if it is shared!?)

Not freeing causes the program to leak memory. Freeing more than once usually causes the program to explode.

Last, a pointer is just an address which is in no way connected to the value it points to. For example, I can do this:

int *x = ...;
free(x);
printf("x: %d\n", *x);
*x = 42;

int%20%2Ax%20%3D%20...%3B%0Afree%28x%29%3B%0Aprintf%28%22x%3A%20%25d%5Cn%22%2C%20%2Ax%29%3B%0A%2Ax%20%3D%2042%3B%0A

This code accesses x twice after it is freed: once to dereference it and read its value, and once to dereference and update the value. Neither is legal after the free() call! After the free() call, x holds a dangling pointer which must never be referenced. A defensive programming technique is to always set a varialble you have free()’d to NULL so that accesses segfault rather than live on for some part of some program!

Throughout the course, we will see examples of when pointers are both great and cause all kinds of problems.

To grasp the use of pointers to pointers in the upcoming example, we must first talk about pointers into structures. Commonly, malloc() and calloc()¹ allocate some consecutive bytes on the heap and return a pointer to the “start” of this structure. For example, remember the link structure from before.

typedef struct link link_t; 
struct link 
{
  elem_t elem; 
  link_t *next;
};

typedef%20struct%20link%20link_t%3B%20%0Astruct%20link%20%0A%7B%0A%20%20elem_t%20elem%3B%20%0A%20%20link_t%20%2Anext%3B%0A%7D%3B%0A

Executing ptr = malloc(sizeof(link_t)) makes ptr a pointer to the start of some space large enough to hold at least a link_t. Given the layout of the link_t struct, we can see that first in the struct is an elem_t followed by a pointer to a link_t. So, since the first field in a struct is at the beginning of the struct, the address denoted by ptr, not only could ptr be typed as a pointer to a link_t, but also as a pointer to an elem_t (and both at the same time). In a similar fashion, we can get a pointer to the second field, whose type is link_t *. Let’s write some code to make this concrete:

void *ptr = malloc(sizeof(link_t)); 
link_t *a = ptr;
elem_t *b = ptr;
link_t **c = ptr + offsetof(link_t, next);

void%20%2Aptr%20%3D%20malloc%28sizeof%28link_t%29%29%3B%20%0Alink_t%20%2Aa%20%3D%20ptr%3B%0Aelem_t%20%2Ab%20%3D%20ptr%3B%0Alink_t%20%2A%2Ac%20%3D%20ptr%20%2B%20offsetof%28link_t%2C%20next%29%3B%0A

Above, ptr, a and b are aliases, and allow us to access the same memory as different types. Let’s refer to ptr as the address of the place in memory where the link_t struct is defined. Through b, we are allowed to access the memory at ptr to read and write in elem_t-sized chunks², because that’s what the type says is found at b. Similarly, through a, we are allowed read and write accesses in link_t-sized chunks³.

Figure 2 illustrates the code above. The coloured line on each black pointer shows what part of the structure can be read through that pointer. Note that the void pointer cannot be dereferenced, meaning it cannot be used to read the structure at all.

The macro offsetof() allows us to calculate the relative starting address in memory of a field in a struct.⁴ On the machine where this is written, offsetof(link_t, next) is 8. Thus the addressed stored in c is ptr + 8. Note that this address is inside the struct pointed to by a, that is a < c < a + sizeof(*a).

Because c is a pointer to a field in a struct that stores a pointer, c is a pointer to a pointer, which is clearly reflected by its type: link_t **. Thus, c denotes an address in memory⁵ where a pointer is stored. In the code example above, the value of this pointer is undefined, because we used malloc(). Dereferencing this pointer – aka following this pointer to read the memory at the location it points to – *c, denotes an address in memory where a pointer to a link_t is stored. We may dereference this pointer too, adding another * to the expression: **c denotes a value of type link_t. In summary:

This clearly shows how the number of *’s are “balanced” – to get closer to the value, add another star in front of the expression. Taking the address using & adds a * to the type, reflecting the additional pointer indirection. The number of *’s in the type of some variable x upper bounds how many times we can dereference x, i.e., write *x, **x, etc.

Above, c exemplifies a pointer into a structure.

Pointers to pointers can often simplify implementations by making things more regular, and getting rid of corner cases.

When we implemented linked lists, we used a clever trick of inserting a sentinel link at the start of the node to simplify the implementation. This allowed us to define a find function that returned the preceding node. This allowed the find function to be used across multiple list functions such as insert, remove, and get.

We will now see how we can implement a similar function but without the need for a sentinel. The trick is to return a pointer – not to a link, but to a pointer to a link. Such a pointer can be used both for reading and writing, allowing its use across multiple list functions such as insert, remove, and get, like before. Because a link_t * can be found both in the next fields of links and in the first and last fields of lists, a link_t ** can cover both these cases. Thus, there is no need for a sentinel link to be able to easily update the pointer to a link.

static 
link_t **list_find(list_t *list, int index)
{
  link_t **cursor = &list->first;

  for (int i = 0; i < index && *cursor; ++i)
    {
      cursor = &(*cursor)->next;
    }

  return cursor; 
}

static%20%0Alink_t%20%2A%2Alist_find%28list_t%20%2Alist%2C%20int%20index%29%0A%7B%0A%20%20link_t%20%2A%2Acursor%20%3D%20%26list-%3Efirst%3B%0A%0A%20%20for%20%28int%20i%20%3D%200%3B%20i%20%3C%20index%20%26%26%20%2Acursor%3B%20%2B%2Bi%29%0A%20%20%20%20%7B%0A%20%20%20%20%20%20cursor%20%3D%20%26%28%2Acursor%29-%3Enext%3B%0A%20%20%20%20%7D%0A%0A%20%20return%20cursor%3B%20%0A%7D%0A

We start by defining cursor – a pointer to a pointer – by taking the address of list->first using the & operator. Like we saw in the table above, list->first is a link_t * but &list->first is a link_t **. This pointer points to the first field in the list struct. Thus, even if an empty list is represented as a list whose first and last fields are both NULL, &list->first is defined, and not NULL⁶. Figure 3 shows the value of cursor after the first line of list_find() is executed.

As is visible from the code, swinging cursor forward through the list is somewhat involved. Previous iteration in the list implementation used code like cursor = cursor->next. Now, we are forced to dereference cursor to read next and then take the address of the result: cursor = &(*cursor)->next.

In plain English what this means is: read the address of the variable cursor, then take the address of the next field of the object stored at that location, and store the result in cursor.

Note that turning this operation into two discrete steps is not possible. Consider declaring a temporary variable tmp to store the value of the next field, and then using &tmp to swing cursor forward. When list_find() returns, its will return a pointer to a variable (tmp) located on the stack frame that is just popped!

link_t *tmp = (*cursor)->next;
cursor = &tmp;
...
return cursor;

link_t%20%2Atmp%20%3D%20%28%2Acursor%29-%3Enext%3B%0Acursor%20%3D%20%26tmp%3B%0A...%0Areturn%20cursor%3B%0A

In plain English what the first line means is: read the address of the variable cursor, then read the value of the next field of the object stored at that location, and store the result in tmp. The interpretation of the 2nd line: take the address of the local variable tmp and store that address in cursor. Figure 4 shows the difference between &(*cursor)->next and &tmp pictorially.

Even if the stack frame is not overwritten by a subsequent function call, *cursor = new_link() will only update the (useless) value of tmp, a variable on a popped stack frame.

Using the list_find() function is very similar to how we used list_find() in the past, except that we use *cursor both to read and write the field that cursor points to⁷.

void list_insert(list_t *list, int index, elem_t element)
{
  link_t **cursor = list_find(list, index);

  if (*cursor)
    {
      *cursor = link_new(element, *cursor); 
    }
}

void%20list_insert%28list_t%20%2Alist%2C%20int%20index%2C%20elem_t%20element%29%0A%7B%0A%20%20link_t%20%2A%2Acursor%20%3D%20list_find%28list%2C%20index%29%3B%0A%0A%20%20if%20%28%2Acursor%29%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%2Acursor%20%3D%20link_new%28element%2C%20%2Acursor%29%3B%20%0A%20%20%20%20%7D%0A%7D%0A

Above, we iterated over a list by pointing to the pointer to the next link_t in the list. This allows us to very easily implement functions that insert or unlink a specific link.

This is even more powerful when it comes to less linear data structures. For example, when navigating a binary search tree, it is useful to keep a pointer to the parent pointer’s pointer to a subtree instead of simply the pointer to a subtree. This allows us to navigate to the subtree, but also update it, without caring whether the pointer is the left or right subtree.

static
node_t **tree_inner_find_node(node_t **n, elem_t e)
{
  node_t **cursor = n;

  while (*cursor)
    {
      /// Logic left as exercise to the reader (no recursion!)
    }

  return cursor;
}

static%0Anode_t%20%2A%2Atree_inner_find_node%28node_t%20%2A%2An%2C%20elem_t%20e%29%0A%7B%0A%20%20node_t%20%2A%2Acursor%20%3D%20n%3B%0A%0A%20%20while%20%28%2Acursor%29%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%2F%2F%2F%20Logic%20left%20as%20exercise%20to%20the%20reader%20%28no%20recursion%21%29%0A%20%20%20%20%7D%0A%0A%20%20return%20cursor%3B%0A%7D%0A

With this code, we can now in an easy way implement insertion. We simply obtain a pointer to the pointer to the place in the tree where we should add the new node. Let n be this pointer. Below, if *n is NULL we “fell out of the tree” going down some subtree where we expected to the key. In that case, we simply create a new subtree and update *n to point to that subtree instead of NULL.

bool tree_insert(tree_t *t, key_t k, elem_t e)
{
  node_t **n = tree_inner_find_node(t->root); 

  if (*n)
    {
      *n = node_new(k, e, NULL, NULL); 
    }
}

bool%20tree_insert%28tree_t%20%2At%2C%20key_t%20k%2C%20elem_t%20e%29%0A%7B%0A%20%20node_t%20%2A%2An%20%3D%20tree_inner_find_node%28t-%3Eroot%29%3B%20%0A%0A%20%20if%20%28%2An%29%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%2An%20%3D%20node_new%28k%2C%20e%2C%20NULL%2C%20NULL%29%3B%20%0A%20%20%20%20%7D%0A%7D%0A

Pointers to values allows values to be shared across several places in the code such that a modification from one part becomes visible to another. Since pointers are just a form of value, a pointer to another pointer follows no special rules that do not apply to, say, a pointer to an integer.

In linked structures, having a pointer to a next field instead of the value in that next field is often convenient, because that same pointer will allow you to both get the contents of the next field and set the contents. For a linked list, this is similar to having a pointer to the preceding link, but for a tree-shaped data structure, there is no “clean” alternative.

Questions about stuff on these pages? Use our Piazza forum.

Want to report a bug? Please place an issue here. Pull requests are graciously accepted (hint, hint).

Nerd fact: These pages are generated using org-mode in Emacs, a modified ReadTheOrg template, and a bunch of scripts.

Ended up here randomly? These are the pages for a one-semester course at 67% speed on imperative and object-oriented programming at the department of Information Technology at Uppsala University, ran by Tobias Wrigstad.