Marwan's Tutorial Blog

My blog for technical tutorials and related stuff (from beginner to more advanced.)

Pointers

23 Jul 2018

Let’s talk about pointers and memory. it is one of my favorite subjects and in my opinion one of the most important notions in programming.

Of course, talking about pointers implies talking about C or C++, they are the two languages where you need them most, and while you can avoid them, pointers are everywhere in programming, it is just that sometimes they’re hidden by the language.

This post requires at least some basic knowledge of C, mostly its syntax and the most obvious part of its semantics. If you’re not a C programmer (but you’re familiar with languages that use C syntax like Java) don’t be afraid, you will probably be able to understand most of the text and, I hope, you will learn something useful.

A bit of theory

For the sake of clarity, the rest of the text will assume a simple memory model which more or less maps to what you could find on modern PCs running Linux. That is, a model where memory addresses are just unsigned integers indexing bytes.

The semantics of the C programming language, in order to support (almost) any kind of architecture, is more complex. This model explains some particular undefined behaviors.

In short, what is defined is that you got addresses and you don’t know their nature. The language only guarantees the expected behavior of arrays and of pointers used as arrays. The whole definition of pointers is a bit obscure and it defines mostly when pointers are supposed to be equivalent to one another and/or defined.

That is to say, you can live with it as long as you don’t try to rely too much on the numerical nature of pointers outside of arrays. But keep in mind that anything that is not explicitly defined (or defined as implementation dependent) may be compiled differently than what you expect.

So far for the theory.

there is no arrow

The most common illustration of pointers involves boxes and arrows. After several years of teaching C, it appears to me that this is the worst way of presenting pointers.

A pointer is a value (often numerical) like any other. In order to manipulate it, you need to store it (in a variable, a field of a structure, an array cell…) and you can copy it to another storage. It can be valid or uninitialized, it can become invalid…

int x = 42;	// we need an address to init our pointer
int *p;		// p is a variable that can contain a pointer to an int
p = NULL;	// p contains the null address, an existing but unusable pointer
p = &x;		// p now contains the address of x
int *q = p;	// q is a variable containing the same address as p
int y = 0;	// another variable in order to have an address
p = &y;		// p contains the address of y, q still contains the one of x
printf("%d %d\n", *p, *q);

When declaring a pointer as in int *p, you define a storage (a variable) where you can put an address ; but until you initialize it with a proper address, it is unusable, just like any other variable.

Just like an address in real life, if you write it in your contact book, it doesn’t mean that it will be updated when the people living here move or if the house is destroyed. And if you have a line for the address of a contact but don’t put anything inside (or put something that is not an address) you won’t be able to send any letter to that address as it is not valid !

Once you have this in mind, you will be able to understand most errors related to pointers. It doesn’t mean that you won’t make errors, or that you will find them easily, but at least you know what you’re playing with.

Let’s now move to the basics.

Basic usage of pointers

The following piece of code illustrates classical usage of pointers. Read it and read the comments !

#include <stdio.h>
#include <stdlib.h>

/*
 * reset(a) puts 0 at the address a
 */
void reset(int *a)
{
  *a = 0;
}

/*
 * swap(a, b) swaps the integers stored at address a and b
 */
void swap(int *a, int *b)
{
  int c = *a; // copy in C the value stored at address a
  *a = *b;    // copy at the address in a the value at b
  *b = c;     // copy the value from c at the address in b
}

/*
 * divide(a, b, m) returns a/b (as int) an stores at m the rest
 * if b is null, returns 0 and don't touch what m points to
 */
int divide(int a, int b, int *m)
{
  if (b == 0) {
    return 0;
  }
  *m = a % b;
  return a / b;
}

int main()
{
  int x = 27;
  printf("x = %d\n", x);
  reset(&x); // send to reset the address of x
  printf("x = %d\n", x);

  int a = 2, b = 42;
  printf("a = %d\nb = %d\n", a, b);
  swap(&a, &b);
  printf("a = %d\nb = %d\n", a, b);

  int m = -1;
  printf("a/b = %d\n", divide(a, b, &m));
  printf("m = %d\n", m);

  return 0;
}

You can compile that code and run it:

> make basic
cc basic -o basic.c
> ./basic
x = 27
x = 0
a = 2
b = 42
a = 42
b = 2
a/b = 21
m = 0

Just to resume what we have seen: reset(a) is a function that uses a pointer to store a value outside of its scope; swap(a, b) exchanges the content of 2 addresses and divide(a, b, m) computes integer division and stores the rest at an address provided. These three functions illustrate a common (basic) use case of pointers: being able to modify variables (or any storage) outside of the current function.

Even if it is not the official vocabulary, you can see this as a reference call semantics, you pass a reference to a local variable in order to modify it.

The traditional call semantics of almost every language is a call by value: a function’s parameters’ values are copied into the parameter storage. If you want to modify variables local to the caller, you must pass the address of those variables. The callee always assumes that you pass valid addresses (it can’t verify them anyway…).

Note: in many higher level programming languages (dynamic or not like Python, Java, OCaml…), complex values are always manipulated through pointers This means that when you pass them to a function, you pass them by reference. This is often called pass by object reference. In my experience for beginners never exposed to pointers before, the induced behavior is often disturbing: you are able to do some operations that modify the parameters in the caller scope, but some modifications are still local. Explained through pointers, this is far more simple: you have this address on an object, you can modify what the address point at but any operations modifying the address itself acts only at the local scope.

To illustrate this last point (still in C), let’s write a function that swaps two pointers. Not the content pointed to but really the addresses:

void swap_pointer(int **a, int **b)
{
  int *c = *a;
  *a = *b;
  *b = c;
}

We just add a level of stars, this way we can change the address since we have a pointer to a location containing an address. The only differences are on type, the rest of the swap is similar.

Common mistakes

there is an infinte number of ways to misuse pointers. Let’s see some classical errors.

Returning pointers

A pointer is a value and like any other value. You can return a pointer in a function.

// Global variable for the sake of the example
int my_global = 42;


/*
 * a useless function
 */
int* address_of_my_global()
{
  return &my_global;
}

when an address is returned by a function, you can expect that callers of this function will use it. This means that: it must be valid (eventually NULL). To be valid and dereferencable, it must point to a storage that has a sufficiently long life time, like the example above (my_global will stay as long as the program runs). Returning the address of a local variable (or of a parameter) will inevitably leads to bugs, in fact this an obvious case of undefined behavior. As usual in C, it will seem to work in certain cases: local variables are stored on the stack which is a kind of draft for functions, right after the call, the content of the local variable may probably still be available, but as soon as another part of the program uses the stack it will be overriden.

/*
 * writing this code in real programs deserves being ashamed for life
 */
int* dont_do_that()
{
  int x = 42;
  return &x;
}

In obvious cases like this one, the compiler will be able to warn you:

shell> cc -Wall -Wextra -std=c11 -c dont_do_that.c
dont_do_that.c: In function ‘dont_do_that’:
dont_do_that.c:7:10: warning: function returns address of local variable [-Wreturn-local-addr]
   return &x;
          ^~

Note: I have used the the flags -Wall -Wextra. They activate the standard warnings (depending on your compiler, you can activate more warnings, clang for example provides a flag -Weverything that activates all possible warnings). You should always do that. Warnings are always the sign of something wrong. Sometimes you have a good reason, but it is more likely that the code will break at a later time.

Invalid and null pointers

Pointers (strictly speaking, variables of type pointer) can be in three states:

  • initialized and valid: the address stored in the variable points to a living object in memory
  • null: the pointer contained the so called null pointer, usually the address 0, represented by the macro NULL, in this case the pointer is valid but you can’t dereference it (access the value it is pointing to).
  • invalid: the pointer has not been initialized, it contains garbage or the object at the referenced address no longer exits.

Dereferencing an invalid or null pointer is a case of undefined behavior and may lead to an error at execution (always for the null pointer, but for an invalid address you may have accidentaly gotten the address of another existing object).

Using an invalid pointer in an other kind of operation (like pointer arithmetic or even passing it to a function) is a case of undefined behavior. Note that you can use a null pointer in any operation not involving dereferencing. In the same vein, the address right after the one of an object (or the last object of an array) can be used in non-dereferencing operations.

This is the perfect time to talk about arrays and pointers arithmetic.

Arrays and pointers arithmetic

In most programming languages, an array is a contiguous area containing a collection of objects of the same type. They are of a fixed size (at some point at least, but you may be able to update their size).

In C, the implementation of arrays is related to pointers, but to the contrary of what a lot of people think, arrays and pointers are not exactly the same. But I will show you that later.

If my addresses are numerical, accessing an element of an array is as simple as taking the address of the first element and adding the amount of bytes corresponding to the number of elements to skip. For example, if I have 4 bytes integers and I want to access the third element, I will shift the address of the first by 4*2=8 bytes to skip the first two). Knowing the size of the elements is annoying, the compiler knows their type and thus their size. This is where pointer arithmetic shows up !

Adding an integer n to a pointer moves the address by n objects, provided that this pointer points to an array of at least n objects (the language guarantees the existence of the address of the last object plus one). So, you can navigate in arrays using additions!

/*
 * sums up the content of an array using the classical [] notation
 */
int index_sum(int array[], unsigned size)
{
  int res = 0;
  for (unsigned i = 0; i < size; ++i) {
    res += array[i];
  }
  return res;
}

/*
 * sums up the content using only pointers
 */
int pointer_sum(int array[], unsigned size)
{
  int res = 0;
  for (int *it = array; it != array + size; ++it) {
    res += *it;
  }
  return res;
}

These two functions are completely equivalent, and your compiler will probably generate a similar machine code for both.

In fact, the expression array[i] is completely equivalent to *(array + i) or, for pedantic C programmers, *(&array[0] + i).

Fun fact: we all know that addition is commutative, that is a + b is equivalent to b + a, in most algebra. This is true for pointers as well. It turns out that *(array + i) is equivalent to *(i + array) which means that you can write (but that’s naughty) i[array] !

A lot of code is using pointers directly rather than arrays, for a lot of reasons and this leads also to the concept of iterators in C++. If I rewrote my sum function this way:

int iterator_sum(int *begin, int *end)
{
  int res = 0;
  for (; begin != end; ++begin) {
    res += *begin;
  }
  return res;
}

It may look familliar to C++ programmers !

Using pointers arithmetic is useful in a lot of cases. This is a classical recursive implementation of a binary search (a lower bound in fact) using only pointers:

/*
 * find(begin, end, x) finds x in the sorted range between begin and end
 * returns the address of the first element not smaller than x if it is not
 * present
 */
int *find(int *begin, int *end, int x)
{
  if (end - begin < 1)
    return begin;
  int *mid = begin + (end - begin) / 2;
  if (x == *mid)
    return mid;
  if (x < *mid)
    return find(begin, mid, x);
  return find(mid + 1, end, x);
}

/*
 * iterative version
 */
int *find_iter(int *begin, int *end, int x)
{
  while (begin < end) {
    int *mid = begin + (end - begin) / 2;
    if (x == *mid)
      return mid;
    if (x < *mid)
      end = mid;
    else
      begin = mid + 1;
  }
  return begin;
}

In the previous functions, we have seen several interesting constructions:

  • end - begin: pointers substraction yields the distance (in number of objects) between them
  • find(begin, mid, x): a way to call with a smaller array
  • find(mid + 1, end, x): a way to call a function in the middle of an array
  • begin + (end - begin) / 2: computes the mid point. Note that we use half of the distance rather than the classical arithmetic mean ((begin + end) / 2) to avoid possible overflows (which, when manipulating pointers, will occur).

In all of the previous examples, I have used pointers to designate a range of objects, using the implicit convention that begin is the first element and end the first element outside of the range (half-open/exclusive range). This is a classical choice in programming. Not doing things that way, you will have to play a bit more at the risk of doing out-of-bounds access or forgetting elements.

Always use half-open ranges, with left bound included and right bound excluded.

What’s the difference between arrays and pointers ?

In most cases, there is almost no difference between arrays and pointers, in the sense that a pointer to a memory area containing several objects of the same type can be used as an array.

But, arrays (or static arrays) in C have a different nature. If you declare a variable that way (at local or global scope, it doesn’t matter):

int array[8];

array is not a pointer, in fact what you have just created is a block of 8 integers. But in most cases, if you use the variable array it will be replaced by the address of the first element, that is &array[0]. Thus, you can pass it to a function expecting a pointer to an int and you can assign a pointer with it, but, and this is important, it is not a left-value so it can’t be reassigned.

Array variables are not replaced by the address of the first element in cases where they are used for their types. Like when passing them to the operator sizeof (which will then return the size of the array itself in bytes rather than that of its elements), or when taking their address. Here are some examples illustrating the difference:

#include <stdio.h>
#include <stdlib.h>

int main()
{
  // an int
  int a = 0;
  // a pointer in order to have an address
  int *p = &a;
  // a traditional array
  int array[4] = {1,2,3,4};

  // Let's print some sizes
  printf("sizeof (p) = %zu\n", sizeof (p));
  printf("sizeof (array) = %zu\n", sizeof (array));

  return 0;
}

Compile and run:

shell> cc -Wall -Wextra -std=c11 -o array array.c
shell> ./array 
sizeof (p) = 8
sizeof (array) = 16

OK, you can see that the size of array is as expected 16 (4 * 4) and p being a pointer it is 8 (when executed on a 64-bit machine).

C99 introduces the notion of VLA (Variable Length Arrays). They are not strictly speaking dynamic arrays, but arrays whose size will be known at run-time. But once declared, they behave exactly as other arrays.

Dynamic ?

Arrays is a good topic to introduce dynamic memory allocation. Since the beginning, I have only used addresses of variables (or context where you didn’t know where the pointer came from). We have also seen arrays, but only static ones.

Sometimes, we need entities that have a longer lifespan than that of a function scope, a size that is not compatible with the size of the stack (where our local variables go) or simply a size that will only be known after some computations. For that, we are able to ask for memory using the function malloc(3) from the standard library (the 3 in the parenthesis refers to the section in the Unix man pages, not to a parameter. i.e. documentation is available via man 3 malloc).

This function takes a number of bytes and returns a pointer to an area of this size that you can use as you want. Where it is exactly depends on your system and your standard library. We often say that it is on the heap by opposition to the stack (what is the heap exactly? Where malloc allocates memory of course…)

malloc(3) doesn’t know what usage you will make of this pointer, which is why it returns the generic type of pointers, namely void*. Which can be seen as pointer to nothing or to anything… You can safely assign a generic pointer to any pointer variables and you can assign any pointer to a variable of type void*. But, you can’t dereference a generic pointer, nor can you do arithmetic with it.

malloc(3) guarantees that the memory area pointed to by its return value will be exclusively yours until you free it with free(3), you reallocate it with realloc(3) or the end of the program.

The most common usage of dynamically allocated memory is arrays, strings (which are in fact arrays of characters) and structures. You can allocate memory for a single basic object like an integer, but it is probably a waste of space…

Let’s illustrate it with an example:

#include <stdio.h>
#include <stdlib.h>

int sum(int *begin, int *end)
{
  int res = 0;
  for (; begin != end; ++begin) {
    res += *begin;
  }
  return res;
}

int main()
{
  // a dynamic array of 8 integers
  int *a = malloc(8 * sizeof (int));
  // malloc(3) can fail
  if (a == NULL) {
    fprintf(stderr, "malloc(3) has failed !\n");
    exit(1);
  }
  // Fill the array with 1,2,3,4,5,6,7,8
  for (int i = 0; i < 8; ++i) {
    a[i] = i + 1;
  }
  // Compute and print the sum
  printf("sum of a: %d\n", sum(a, a + 8));
  // Free your memory !
  free(a);
  return 0;
}

And we get:

shell> cc -Wall -Wextra -std=c11 -o dyn_arrays dyn_arrays.c 
shell> ./dyn_arrays 
sum of a: 36

Note the test on the return value, malloc(3) can fail, mostly because you don’t have enough memory (or you hit the limit granted to your program by the OS). For various reason, on most modern systems, malloc(3) succeeds in most cases even if not enough memory is available, this is because modern system only binds memory to your program when you concretly access it. But anyway, always check the return value of malloc(3)! (at least in real-life programs)

Other functions related to malloc(3) are calloc(3) and realloc(3):

  • calloc(3) is a different interface. It takes a size and a number of objects, and, the most important thing, it ensures that the memory allocated is filled with zeroes beforehand. (it may also check that the product between the size and the number of objects doesn’t overflow or isn’t greater than a possible upper bound).
  • realloc(3) is a little bit interesting, it resizes the memory area allocated. In fact, it is not exactly a resize but really is a new allocation. In the general case, it searches for an area of at least the new requested size, copie the content of the old area into it and frees the old area. In some cases it may be able to resize in place. Or fails, like malloc(3).

Examples are often better than words:

#include <stdio.h>
#include <stdlib.h>

struct vector
{
  size_t size, capacity;
  int *data;
};

/*
 * init an already allocated vector
 * with initial size and capacity set to 0
 */
void init_vector(struct vector *this)
{
  this->size = 0;
  this->capacity = 0;
  // capacity 0, then no array so far
  this->data = NULL;
}

/*
 * adds an element at the end of the vector
 * resizes it if necessary
 * we choose to double the size each time
 * returns false if something wrong happen
 */
int vector_push_back(struct vector *this, int x)
{
  if (this->size == this->capacity) {
    int *newdata = realloc(this->data, 2 * (this->capacity + 1) * sizeof (int));
    if (newdata == NULL) {
      // realloc is fair enough to not invalidate data in that case
      return 0;
    }
    this->data = newdata;
    this->capacity = 2 * (this->capacity + 1);
  }
  this->data[this->size] = x;
  this->size += 1;
  return 1;
}

/*
 * resets the vector
 * size and capacity go back to 0
 * data is free, thus the vector can be destroyed transparently
 * ... or reuse ...
 */
void vector_reset(struct vector *this)
{
  free(this->data);
  // Important: otherwise we may try to reuse the invalid address
  this->data = NULL;
  this->capacity = 0;
  this->size = 0;
}

// Demo
int main()
{
  // no need to allocate dynamic memory for the struct, we use it in place
  struct vector vec;
  init_vector(&vec); // now we can use it
  // Add some element
  for (int i = 1; i <= 10; ++i) {
    if (!vector_push_back(&vec, i)) {
      fprintf(stderr, "something goes wrond !\n");
      vector_reset(&vec); // free the memory for us
      exit(1);
    }
  }
  // Print the content
  for (unsigned i = 0; i < vec.size; ++i) {
    printf("%d ", vec.data[i]);
  }
  printf("\n");
  vector_reset(&vec);
  return 0;
}

I let you read, understand and run the code, but here are some important details:

  • structs in C are basiccally heterogenous boxes, it is just a way to pack together some values ;
  • realloc(3) and free(3) accept null pointers;
  • realloc(3) when it fails returns NULL like malloc(3). You need to catch the result before replacing your pointer, otherwise you will loose it.

I opted for a very C++ style here (I know, C++ comes from C, so this is arguably C style too). In particular, the init function doesn’t allocate the structure of the vector, only the data (and in fact, not even the data since we chose to start with an empty vector). This way, we can have a temporary vector on the stack without allocating dynamic memory for it. We only have to care about freeing the inner pointer once we’re done.

One more

There are so many other topics to explore and this post is becoming lengthy. I will play with a last example (the choice was hard…) to illustrate pointer manipulations.

Let’s first start with the notion of linked list. A linked list is a collection of values, a little bit like an array, but with dynamic behaviors. The idea is that rather than storing all the values in a contiguous area, you store them in little boxes (that can be non-contiguous), which are connected by pointers from one to another. This way you can easily add new elements, remove old ones, insert new ones anywhere, etc. all without having to move everything like with arrays to preserve contiguity…

I won’t describe the whole set of list operations, but rather show you a little funny piece of code.

First the definition of list:

// note: this is not the list, but the cell of the list
struct list
{
  struct list *next; // the next element
  int value;         // the data
};

Let’s add some context for my example: you have a list already built, and the pointer to one of the cells. Our task is to detach the cell from the list.

The issue is that in order to do that, we need to find the cell that comes before ours, in order to make its next value point to the target one’s next.

Second problem, if the cell is the first one of the list, we need to update the variable that contains the entry point of the list, otherwise we will end up in an inconsistent state (and probably loose access to the list).

Here is a first naive version:

void detach(struct list **entry, struct list *cell)
{
  // save the previous element
  struct list *prev = NULL;
  for (struct list *it = *entry; it != cell; it = it->next) {
    prev = it;
  }
  // cell is assumed to be in the list
  // so now, prev should point to the element that is just before cell
  // or NULL if cell was the first one
  if (prev == NULL) {
    *entry = cell->next;
  } else {
    prev->next = cell->next;
  }
}

OK, even after removing the comments, this function doesn’t look good. Why? Mostly because there is a if. And worst, the code in both branches is very similar. And there is this story of keeping a pointer to the previous element that is not defined in all cases. Even if it is a rather small function, it contains some traps.

How can we solve that ? Thinking more with pointers! When looking at the final if, we are updating a place containing a pointer, it can be the location containing the entry point or the next field of the previous cell. If we have a pointer to this location, it can contain the address we want ! Here is the code, I let you read it as exercise:

void detach(struct list **entry, struct list *cell)
{
  for (; *entry != cell; entry = &((*entry)->next))
    continue;
  *entry = cell->next;
}

Just a little hint: &((*entry)->next) gives you the address of the field next of the list cell pointed to by the address in entry.

While I really find this version interesting, there is a better trick in some cases. This is pretty good illustration of the principle that states that it is always better to have smart data structures and simpler code.

The idea is that we can have a fake element at the begining of our list, we call that a sentinel. The sentinel never moves, it doesn’t contain a value (or we don’t care about it). This way the empty list is no longer a null pointer but a single element. This also means that when we have to detach the head of the list we always have a previous element! The new code:

void detach(struct list *sentinel, struct list *cell)
{
  for (; sentinel->next != cell; sentinel = sentinel->next)
    continue;
  sentinel->next = cell->next;
}

Elegant, isn’t it ? In fact, the sentinel plays the same role as our double pointer in the previous version.

Goodbye

There is a lot more to tell, but I think that I have covered the important parts of the subject, or at least an important part of the foundations of the subject. I could have spoken about how an allocator works, or how to implement reference counters, or intrusive data structures (I have already done that in my old blog)…

But now it is up to you to practice.

If you’re not a C programmer but survived until here, I hope that you have learned something that could be useful for you and maybe you will try C ?