Memory and Pointers

Comments and questions to John Rowe.

Reminder: memory

We recall how variables are stored in memory. For example the computer might choose to store two variables x and y like this:

               ----------------------- 
Byte number:  | 400 | 401 | 402 | 403 | 404 | 405 | 406 | 407 |
               ----------------------- -----------------------
Value:        |          8.4          |         11.3          |
               ----------------------- ----------------------- 
                <--      x      ---->   <---      y      --->  

When calling scanf() we have used the & operator to find the address of a variable. In this case &x has the value 400 and the type "pointer to float".

An array of floats called farray is declared like this:

        -------------------------------------------------
Byte:   | 640 | 641 | 642 | 643 | 644 | 645 | 646 | 647 |
        -------------------------------------------------
Stores: | <---- farray[0] ----> | <---- farray[1] ----> |
        -------------------------------------------------

In this example farray (without an index) has the value 640 and the type "pointer to float" (exactly the same as &x).

When we needed to "pass the array to another function" we encountered the simple, but key innovation is that whereas previously we had used memory addresses that are constants,  we can now also use memory addresses that are the values of variables.  We can illustrate a trivial example as follows:

#include <stdio.h>
// myfun expects the address of a float (and implicitly that
// this float is the first elemnt of an array)
void myfun(float p[]) {
  p[0] = 3.7; // Set the first element of the array
}

int main() {
  float farray[12];

  myfun(farray);

  printf("%g\n", farray[0]); // Prints 3.7
  return 0;
}

Step through this code

 

Here the parameter declaration p[] identifies p as a pointer to the first element of an array of floats, ie it is a pointer to a float. That is to say, inside myfun() p is a variable whose value is the address of a float, by implication the first element of an array since we have used the p[] convenience notation rather than the formal declaration we shall learn below. When myfun() is called with myfun(farray) then p is given the value farray ie the address of farray[0]. In the above example this would have the value 640.

Inside myfun() the statement p[0] = 3.7; can be interpreted as float@(p+ 4*0) = 3.7. Of course, in this case float@(p+ 4*0) is just the same as float@p. ie float@640.

Pointers have other uses

Pointers have other uses and understanding pointers in more detail will give us new capabilities, including:

• The ability to have more-generalised arrays which can be resized as the program progresses and/or with rows of different sizes.
• The ability to structure related data into groups to enable us to think at a higher level, which we shall deal with in the next lecture.

To a large extent this reflects a transition from the traditional number-crunching programs where all the parameters are known when the process starts to more modern, interactive programs such as word processors where the number of paragraphs or pages changes as the program progresses and new memory has to be allocated  on the fly.

Pointers

A pointer is a variable that contains the address of another variable.

Kernighan and Ritchie, The C Programming Language.

For example in the examples above a pointer with the value 400 would point to x and a pointer with the value 644 would point to farray[1].

Pointers say it where something is stored in memory, not what its value is.

Pointers to variables

The following declares a pointer that can point to a float (note the * after the word "float", without that p would be a float rather than a pointer to a float): This is the "proper" way to declare a pointer to a float, as mentioned before the notation float p[] is a convenience notation that can only be used in a parameter list. Thus in the previous example we could have declared myfun() as:

void myfun(float *p);
 

As started we prefer the "convenience" notation as it makes it clear that p is expected to point to the start of an array not just an ordinary variable. (And the canonical declaration for the two-dimensional case is rather complicated!)

The * operator

The '*' operator does the opposite of '&': given a pointer p whose value is &x *p is just a synonym for x, ie *p means 'the variable whose address is p', eg float@p. Of course this is just the same as p[0] which means float@(p +4*0)

We may then use *p anywhere where we might want to use x to write rather silly code such as:

  float x;
  float *p;

  p = &x;
  *p = 1.414;
 

Although this is legal it's obviously pretty silly: inpractice pointers are almost used to access arrays and other objects that have been created inside other functions.

To use a pointer we need to know its type

Just like arrays, if we wish to be able to use a pointer we must know the type of the thing it points to, Without this the above line has a problem: should the value 1.414 be written as a float or a double? If the former we will need to write four bytes to locations 404-407 inclusive, if a double we will write eight bytes to locations 404-411. (Of course this is exactly the same problem we had when passing memory addresses to scanf().) For this reason pointers must be declared with the type of object they point to.

Pointers must be declared with the type of object they point to.

 For variety we shall illustrate this pointers to doubles, however please note that this example illustrates the principle of pointers, it is not a good example of how to use them!

#include <stdio.h>
void unwise_function(double *pp, double *qq);

int main() {
  double x =17.1, y, *p, *q;  // p, q are pointers

  p = &x; // The value of p is now the address of x.
//   If we do anything with or to *p it's doing it to x:

  printf(" p: %p\n", p);
  printf(" *p: %g\n", *p);

  y = *p;          // Exactly the same as y = x;
  *p = 3.14159;    // Exactly the same as x =  3.14159;
 
  // Now let's make p point to y: 
  p = &y; 
  *p = 1.414;
  q = &x;          // The value of q is now the address of x 

  unwise_function(p, q);  // The same as unwise_function(&y, &x);

  // Now x has the value 73.2, y has the value 2.5 
  printf("x: %f y: %f\n", x, y);
}

void unwise_function(double *p2, double *q2) {
  *p2 = 2.5;
  *q2 = 73.2;
}

Step through this code

Notice the difference between:
p = &x; change the value of p
*p = 3.14159; change the value of the variable whose address is p.

The process of finding the variable whose address is p is called dereferencing p.

Now see what happens when we pass p and q to the function unwise_function(). Inside unwise_function() p2 and q2 have the same value as p and q had in main, ie &y and &x. Therefore when p2 and q2 are dereferenced we are actually accessing y and x inside main and y and x's values gets changed.

Passing a pointer to a function allows the function to change the value of the thing the pointer points to.

We have used this when calling scanf().

At first sight unwise_function() looks like the answer to the question "How do I write a function that returns more than one value?". But as the name unwise_function() implies it isn't a very good answer! We shall see a better way to do this in the next lecture when we learn about C data structures.

The NULL pointer

C has a special value called NULL which it can be guaranteed no legitimate pointer will ever have. We've seen this already: fopen() returns NULL if the open of a file failed, and in general, any function that returns a pointer to something useful will return NULL when it fails, and that should always be checked for.

When pointers attack: random pointer values

It should be clear that the following code has a serious problem:

float *p;    // p has a random value
*p = 3.14;   // write 3.14 to a random location

Although this example is pretty obvious, in other situations it can be less obvious and the temptation is to say that just because we have a pointer we can use it.

Take-home point Every phone has a phone number but merely having a number does not magically create a phone at the end of it!

You don't know Fred's phone number, so you open up your phone's address book and make an entry for Fred with a random, made-up phone number: 01632 314159. You dial Fred in your phone - he picks up!

Take-home point It's not enough to have an entry for Fred in our contact list, it must also contain Fred's correct phone number.

In order to dereference a pointer it is absolutely essential that its value has been explicitly set to the address of a legitimate variable, just as when we dial a phone number it is essential that it is the number of the correct telephone.

The safest bet is whenever we declare a pointer, initialise it to NULL:

  float *p = NULL;

Using a value of NULL by mistake is not safe but it is probably less dangerous than using any other value.

Symptoms of pointer errors

SIGSEGV, SIGBUS and STATUS_ACCESS_VIOLATION crashes

If we are lucky, a pointer error will cause the program to crash with one of the above errors. (Initialising pointers to NULL improves the chance of this happening which is why we recommend it.)

Random results

If we are unlucky, a pointer error will cause our program to behave randomly. Putting in printf() statements to debug may cause the problem to go away...

What to look for

In either case, look for:

• Uninitialised pointers, or pointers to something that no longer exists.
• Bad arguments to scanf()
• Array index errors (see below).

Using pointers to allocate space

So far we have used "ordinary" arrays, declared inside functions. But this requires us to know the sizes of our arrays we will need when we write the program, or at the very least soon after the program starts.

But often the sizes of arrays, or number of items we need to store, will change as the program progresses. For example, a word-processor will have new paragraphs added or removed and a web browser will display new pages or tabs. In a scientific context we may need to wish to use an adaptive mesh whose resolution changes as the program progresses.

Dynamic memory allocation

For this reason, it is also possible to dynamically allocate memory as we need it. In particular we can dynamically allocate anonymous arrays which can then be used like any other memory such as that obtained by declaring arrays. We can also get rid of them when we are finished with them.

Dynamically allocated memory acts as an anonymous (nameless) arrays which we can create and destroy (and with care grow and shrink) at will.

malloc

The malloc function allocates some memory for us to use. It accepts the number of bytes required as an argument, allocates some previously unused memory and returns the address of this memory to the calling function. If the function assigns this to a point p then we can use p[0], p[1] etc just like (a pointer to) any other array. C also provides a handy operator sizeof which tells us the number of bytes need to store an object.

Let's first consider allocating memory to be used as as a one-dimensional array:

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

#define N 100
int main() {
  float *p = NULL;

  p = malloc(N * sizeof *p);
  if (p == NULL) {
    fprintf(stderr, "Out of memory!\n");
    exit(1);
  }

  for(int i = 0; i < N; ++i)
    p[i] = sqrt(i);
  // Use p for something

  return 0;
}

Step through this code

1. Step through this example
2. To illustrate the use of malloc() and the value it returns.
1. Step through the above example.
2. Notice how sizeof *p evaluates to 4 (the number of bytes needed to store a float) so that N * sizeof *p is the correct number of bytes needed to store N floats.
3. Now click until malloc() is called. Notice how an new array of N floats comes into existence with the usual random values. Unlike every other array we have seen before, this one has no name! So we just refer to it by its address.
   
4. Now click once more and notice that the value of p is the address of the first element of the anonymous array.
5. Now go through the rest of the code. Pause at the first assignment to p[i] inside the for() loop (ie the assignment of  p[0]). Check you understand why this means the first element of the array. Carry on for the assignment of p[1] etc.
   

malloc(n) allocates n bytes of memory and returns the address of that memory, or NULL if the allocation failed.

The sizeof operator

For any pointer p the expression sizeof *p returns the number of bytes needed for whatever p points to. It's the ideal argument to malloc()! There's also a version sizeof(float) which is less useful. In this case since we want N floats we use "N*sizeof *p" as the argument to malloc() .

sizeof *p returns the number of bytes needed for whatever p points to

Accessing the allocated memory 

When stepping through the example we see that the allocated memory has an address and that the value of the pointer p is that address. We therefore use p to access this memory. We have to do it this way as memory allocated in this way is anonymous, it has no name to refer to it by.

Allocated memory must have an address which can be reached from the value of a variable, otherwise we cannot access it and it gets "lost".

NULL

AS with fopen, NULL is used to indicate that malloc ran out of memory. We must always check that malloc did not return NULL. We have met the exit() function before, does pretty much what it says and by convention, successful programs exit with zero.

Writing a wrapper function

You are welcome to check the result of malloc every time you call it. You are equally welcome to define a function like:

void *xmalloc(size_t n) {
  void *p = malloc(n);
  if (p == NULL) {
    fprintf(stderr, "Out of memory!\n");
    exit(1);
  }
  return p;
}

and to call xmalloc instead of malloc. Such a function is often referred to as  a wrapper around malloc().

Always check malloc() does not return NULL.

Allocated memory is permanent

Unlike "ordinary" arrays which vanish when their containing function returns, allocated memory is permanent until explicitly released (freed). In general this is a big advantage but it does mean that we have to free memory when no longer needed.

Allocated memory is permanent until explicitly freed.

Freeing memory

When we've finished with some memory we should get rid of it so it can be reused. If we fail to do this our program will gradually use more and more memory until the computer runs out. (When our program finishes it will automatically free any memory it was still using.)

Memory that is no longer required must be released using free() otherwise our program will gradually use more and more memory until the computer runs out (this is called a memory leak). However, memory is automatically freed when the program finishes.

The absolute rule is that we can't use memory after we've freed it and we can free it only once.

  free(p); // Don't use it after this!

free(p) frees the memory pointed to by p which must be a value previously obtained from a dynamic memory allocation.  We cannot free part of an allocation, it's all or nothing.

free()d  memory must never be referenced or freed again.

Advanced: "reallocating" memory with realloc()

Note: the use of realloc() is not really necessary for this course. You should know that it is possible but do not worry too much about the details unless you need to use it.

C's dynamic memory allocation has another useful trick: memory allocations can be "resized". Provided the value of p is something that has been returned by a previous called to malloc() (or realloc()) then we may write: 

  p = malloc(oldnum * sizeof *p);
  // Use p...

  p = realloc(p, newnum * sizeof *p); // This changes the value of p

This allocates the new amount of memory, copies the value of the old memory to the new one (up to the minimum of the old and new sizes), frees the old memory and returns a pointer to the new memory. Note that:

• The old allocation does not get magically extended: it's just a convenient way of doing "allocate new", "copy old", "free old" all in one.
• As with free(), we could have serious problems if some other pointers pointed to the old (now freed) memory.
• Also as with free(), the first argument must be an actual value previously returned by malloc() or realloc(). It cannot point to somewhere "inside" some allocated memory only to the very start.
• The new size may be larger or smaller than the old.

Useful features of realloc()

• If the first argument is NULL realloc() is just the same as malloc()
• If the number of bytes asked for is zero realloc() is just the same as free()

At first sight these features may seem a little strange: why can't the person calling realloc() just work out which function they need and call malloc() if the pointer is NULL and realloc() if it is not? The answer is that functions exist for the convenience of the person calling them, not the other way round so realloc() does the work of deciding what to do rather than expecting the person calling the function to do so.

Example of a bug

  p = alloc(oldsize * sizeof *p);
  q = p;
  ...

  p = realloc(p, newsize * sizeof *p); // q is now dangling

realloc() does not not normally return the same address it was called with.

Multiple memory allocations

Non-rectangular "arrays"

The two-dimensional arrays we met in the last lesson were rectangular. All of the rows were of the same length and the whole matrix was stored together: an M by N array is stored as a single block of N*M items. When used to represent a mathematical matrix this is perfectly sensible as by definition the rows are all the same length and it makes sense to store the data all together.

But sometimes we may want to store a collection of M vectors of different lengths but still refer to the individual vectors by number. Or we may want to "resize" one of them using realloc(). We may even need to change the number of vectors as the program progresses. The answer is not to have a single N*M allocation but M individual allocations each of a different length. We will then need a way of accessing each allocated vector by number. We might refer to this as a two-dimensional pseudo-array; the "pseudo" prefix referring to the fact that that it consists of M separate chunks of memory rather than one large one.

This is a little more complicated than just writing double mat[M][N] but the good news is that when we have done so we can still access the elements using the familiar pseudo[j][k] notation as we have used for true arrays: although they are not the same thing the compiler can generate the correct machine-code in each case as it has already seen the declaration and know which it is.

Multiple memory allocations

Having established that we want several allocations. our first, flawed attempt may look like this:

// Flawed attempt at multiple memory allocations
#include <stdlib.h>
#define M 3
int main() {
  int n;
  float *p;

  printf("Size of each vector?\n");
  scanf("%d", &n);    // Find the row size

  for (int i = 0; i < M; ++i)
    p = xmalloc(n * sizeof *p); // Allocate rows

  // Do something useful...

  return 0;
}

Step through this code

 

The problem with this code is that although we allocate several arrays we have only one pointer so we can only remember the address of one of them: the first M-1 allocations are lost. (This example may seem silly but it's surprising easy to do something similar!)

First working attempt: an array of pointers

Since we need M pointers the obvious solution is to use an array. If the array is called p then each individual pointer is then called p[j] for 0 <= j < M  .
For each of these M pointers we shall call malloc() or realloc() to allocate the space to store the actual row of floating-point numbers.

Advanced point: realloc()

For those who are interested we also demonstrate the use of realloc() to "resize" the individual vectors. Feel free to skip this but if you do step through the code to the end notice how realloc() normally returns a pointer to a different chunk of memory: it does not magically extend the existing allocation.

The code might look like this:

#include <stdlib.h>
#define M 3
int main() {
  int n;
  float *p[M];        // This is the array of pointers

  printf("Size of each vector?\n");
  scanf("%d", &n);    // Find the row size
  
  for (int i = 0; i < M; ++i)
    p[i] = xmalloc(n * sizeof *p[i]); // Allocate rows
  
  p[0][1] = 3.14159;
  // Use p for something 
  
  // Advanced point: resizing the arrays
  // feel free to skip this.
  printf("New size of each vector?\n");
  scanf("%d", &n);   // Find new the row size
  
  for (int i = 0; i < M; ++i)
    p[i] = realloc(p[i], n * sizeof *p[i]); // Resize the rows
  
  // Do something else

  return 0;
}

Step through this code

Since the pointer to the j^th array of floats  is p[j] it follows that the k^th float of the j^th dynamically allocated array is p[j][k]. Thus this "array of pointers and n dynamically allocated arrays of floats" combination gives us an alternative, more flexible way of implementing a two-dimensional matrix of floats.

Points to note

1. The data is stored in M separate, dynamically allocated chunks of n floating point numbers. Compare this to the single M*n chunk which would be used by a true two-dimensional array.
2. Unlike the true two-dimensional array, we have M separate chunks of data each with their own independent address (i.e. knowing one does not enable us to calculate the address of any other). Thus we need M pointers to stores these addresses, which in this case we are storing in an array.

This array of pointers is an example of meta-data (data about data): the floating-point numbers are the end data we actually want, the pointers are just the things we use to access and describe the end data.

This code has an obvious limitation: the length of each row can be changed but the number of rows is fixed. There's a less obvious limitation too: arrays vanish when the function that contains them returns, so when the function returns we have lost the pointers. This isn't a problem for arrays inside main() but makes the program very inflexible.

For this reason hybrid codes such as the one above with an array of pointers are relatively rare. Most codes of this type use a dynamically-allocated array of pointers.

Dynamic arrays of pointers

For a variable type Thing we can create two types of arrays: "ordinary" and dynamically allocated:

Once created we can access either using the same [k] notation. We have already seen an ordinary array of float *, so we can just as easily create a dynamic array of float * using the same code as above:

  // An ordinary array of float *
  float *ar[N];

  // A dynamically allocated array of float *
  float **p;
  p = malloc(N * sizeof *p);
 

Pointers can point to other pointers

1. Six degrees of separation
2. Just an illustration
3. If you had an enormous amount of nerve and you could guarantee that the people in the chain would pass on your call,
   

1. Question: texting, texting
2. Just an illustration
1. Very roughly, how many texts or phone calls do you send/make in a year? (By definition these were to numbers you knew!)
   
2. Very roughly, how many times in the last year have to texted or called somebody to ask them for somebody else's phone number or to forward a text to that person?
   
3. Very roughly, how many times in the last year (or your whole life!) have to texted or called somebody to ask them for somebody else's phone number so you could ask that person for a third person's phone number (or forward a text to that third party)?
   

 Things that can link to other Things (that in turn can link to other Things...) are extremely powerful provided we know how to follow the links!

So far we have seen that if we have a variable type called VARTYPE then we can write:

VARTYPE *p;                 // Pointer to a VARTYPE 
p = malloc(n * sizeof *p);  // Dynamically allocated array of n VARTYPEs

and p can be used as an array in much the same way as if we had written "VARTYPE p[n];" . So for example we can write float *p; and this means that float * is a valid variable type. This means that "float * *" is also a variable type and that means we are able to write:

float **p = NULL;          // Pointer to a pointer to a float
p = malloc(n * sizeof *p);  // Dynamically allocated array of n pointers to a float

Pointers can point to other pointers.

The solution to our previous problem then is to make p a dynamically allocated array of pointers. 

Note there are two stars not one.

The following example declares a pointer that points to the address of a float and then uses it to dynamically allocate an array of pointers. Afterwards it then "reallocates" the memory using realloc() .

#include <stdlib.h>

int main() {
  int m, n;
  float **p = NULL; // This will become the array of pointers

  printf("How many vectors?\n");
  scanf("%d", &m);

  p = xmalloc(m * sizeof *p); // Allocate the array of pointers
  // The rest of the code is now the same with 
  // the variable 'm' instead of the constant 'M'

   printf("Size of each vector?\n");
  scanf("%d", &n);    // Find the row size

 for (int i = 0; i < m; ++i)
    p[i] = xmalloc(n * sizeof *p[i]); // Allocate rows

  p[0][1] = 3.14159;
  // Use p for something 

  printf("New size of each vector?\n");
  scanf("%d", &n);   // Find new the row size

  for (int i = 0; i < m; ++i)
    p[i] = realloc(p[i], n * sizeof *p[i]); // Resize the rows

  // Do something else

  return 0;
}

Step through this code

Freeing the array: allocating and freeing data often has a required order

In this example there was no need to explicitly free the memory as it is freed when the program finished, at the return from main(). Had we needed to free it we would have used the following code:

  for (int i = 0; i < m; ++i)
    free(p[i]);
  free(p);

This code is quite careful in the order it carries out allocations and calls to free(): it frees the unwanted rows first and then frees of the array of pointers. This is quite a common occurrence:

Calls to malloc() and free() are frequently in the reverse order.

Compare the above code's memory map with that of a true two-dimensional array.

Differences from true multi-dimensional arrays

Executive summary: the things above may look like ordinary two-dimensional arrays but they're not

At first sight p above looks just like a "real" array, in that their elements are accessed using the same source-level notation:

  
  double array[M][N];
  double **p = NULL;

  p = xmalloc(M * sizeof *p);
  for (int i = 0; i < M; ++i)
    p[i] = xmalloc(N * sizeof *p[i]);
  p[1][7] = 17.3;
  array[1][7] = 17.4;

However, p and array are different things. p is a pointer to M pointers to N doubless. By contrast, array points to a single block of M*N ints.

They are dereferenced as follows (where we have coloured derefernce pointers red):

p[j][k] => *( *(p+j) + k)  

Double deference: deference: (p+j), add k and dereference the result.

array[j][k] => *(array + (N*j + k))

Single deference: add N*i+k to array and dereference that.

To give a specific example, if p is stored at 200 and ar starts at 600 then assuming a four-byte memory address and an eight-byte double we have:

ar[j][k]	=>	The double stored at: 600 + 8*(N*j + k)
p[j][k]	=>	The float stored at: (the address stored at (the address stored at 200) + 4*j) + 8*k

A true two-dimensional MxN array is one continuous block of M*N values accessed from a single memory address but an MxN pseudo-array is M separate blocks of N values accessed via an array of N pointers which are in turn accessed from another pointer pointing to the start of the pointer array.

Summary

The text of each key point is a link to the place in the web page.