Reminder from the last lecture

Memory and arrays

In the last lecture we recalled how variables are stored in memory. An array of floats called farray is declared like this:

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

Rather surprisingly we learnt that computers have no direct support for arrays but merely for expressions of the form float@(expression) and that arrays are essentially implemented in software by programmer and the compiler creating the correct instructions to tell the computer the correct location for an array element. In this example farray (without an index) has the value 640 and the type "pointer to float" (exactly the same as &x if x is an ordinary float variable).

Pointers

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

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

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 called pointers. 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 of the address of farray[0]. In the above example this would have the value 640.

Inside myfun() the term p[0] is be interpreted as float@(p+ 4*0) or just float@p. ie float@640.

We summarised their use as:
 

We will now start to look at these 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 next week.

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

Pointers to variables

Our first ever use of memory addresses was when we passed the the addresses of variables to scanf() to enable it to change their values. We have not yet learnt how scanf() uses these values and whilst we are unlikely to need to do this ourselves we will briefly show how it is done.

The "convenience" way of declaring a pointer to a type (type p[]) is only available in a function declaration (and by implication suggests that p points to the first element of an array).

The canonical declaration for a pointer to a type is: type *p; . Note the * before the variable name. Thus the following two prototypes are equivalent but the second form of the declaration of p can also be used to declare pointers inside functions:

void myfun(float p[]); // Convenience - only for function parameters
void myfun(float *p);  // Canonical - can be used anywhere
 

As stated in the last lecture we prefer the "convenience" notation when used within a function declaration or prototype 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

Given a pointer to a float called p we can in theory set the value of the thing it points to by using p[0] = value; which just means "find the value of p, add zero and go to that address". Of course that's pretty convoluted and any normal programmer seeing that code would assume that p pointed to the start of an array. The direct and canonical way to access the variable pointed to by a pointer is to use * operator.

The '*' operator does the opposite of '&': if we have a pointer p whose value is &x then *p is just a synonym for x, ie *p means "the variable whose address is p", or in our pseudo-machine-code float@p.

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

#include <stdio.h>
// Silly example of using a pointer
int main() {
  float x;
  float *p;

  p = &x;
  *p = 1.414;
  printf("x is: %f\n", x);

  return 0;
}

Step through this code

 

1. Step through the above example.
2. To see a pointer being used in a non-array context
1. Step through the above example in a new window.
2. Step through until the assignment p=&x; and notice how the value of p is now the address of x.
3. Notice how the next statement *p=1.414; changes the value of the thing p points to not p itself. It is exactly equivalent to p[0]=1.414;

Although this is legal it's obviously pretty silly: in practice 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.

Passing pointers to functions

We have used this when calling scanf() and it works pretty much as we would expect, as in this silly example:

/*
 * Silly example of passing a pointer to a function
 */
#include <stdio.h>

void makeit7(int *p);

int main() {
  int seven;

  makeit7(&seven);

  printf("The value is %d\n", seven);

  return 0;
}

void makeit7(int *p) {
  *p = 7;
}

Step through this code

It's worth stepping through the above code to see how p inside makeit7() points to seven inside main() and changes its value.

However, as we have already said pointers to ordinary variables only really get used with scanf() and since that has already been written for us we will move on.

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 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.

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

The symptoms of pointer errors are the same as those of giving a random index to an array and for exactly the same reason: we are trying to access a random memory location.

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

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

malloc

The malloc() function, which is declared inside <stdlib.h>, 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 the above "Key example".
2. To illustrate the use of malloc() and the value it returns.
1. Step through the above "Key example" in a new window.
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. Notice too that the anonymous array has not disappeared when malloc() returned.
6. 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 is the sibling of & : & finds the address of a variable and sizeof tells us how many bytes would needed to store it. Neither evaluates the thing it operates on.

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".

1. Use malloc() to dynamically allocate an array of doubles.
2. To practice using malloc().
3. Be sure to understand and folow the code in the Key example, but of course don't copy and paste it! If your program does not work compare it with the relevant part of the examle to see what is wrong.
1. Create a new on-line program in a new window, with a suitable title and opening comment.
2. Make sure you include <stdlib.h>
3. Inside main() declare an int variable to hold the size of the dynamically-allocated array and a double pointer, eg double *ar.
4. Ask the user how many doubles they want and use scanf("%d", &varname) to read that number from the keyboard into your int variable.
5. At this stage it would be wise to print out the integer you have just read in, to check it is correct.
6. Build & run. Check the output is correct.. (The compiler may warn you that you have not used your pointer.)
7. Now after you have printed out the variable name call malloc() to allocate some memory and assign the location of that memory to your pointer variable. Look very carefully at the call to malloc() in the Key example, which for convenience we repeat here:
    
   p = malloc(N * sizeof *p);
    
   (There is no need to check for NULL at this time.)
8. Now write a simple loop to assign some simple values to your new array in the same way as the example (for example a loop containing the assignment pointername[j] = j*j;) and another to print out the values of the array.
9. Build & run. Check the output is correct.
10. Deliberate mistake: comment out the statement containing the call to malloc().
11. Build & run. What happens?
12. Fix the mistake. Build & run to check it's OK.

The type of the malloc() function

The malloc() function is unusual in that although it obtains some memory it never needs to use it. It does not care if the calling function wants to use it store an array of ints, floats or anything else. It therefore has the return type void * meaning a "raw" memory address with no suggestion of what it points to.

The argument to malloc() must be some sort of integer and that integer must be able to be large enough for the largest amount of memory malloc() can return. Since this can vary from system to system C defines a special integer type size_t which is the correct type on each system. We will use these pieces of information below.

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

We are welcome to check the result of malloc every time you call it. We are equally welcome to define a function like and to call xmalloc instead of malloc. Such a function is often referred to as  a wrapper around malloc():

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

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 reallocated to larger or smaller allocations with the old values copied to the new memory. 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.

1. Use realloc() to "grow or shrink" your allocation.
2. To practice using realloc().
3. After the intial assignent loop but before the printout ask the user for a new size and then call realloc() to give your partition a new size. Remember: there is no guarrentee your pointer will point to the same block of memory but if it does not the old contents will have been copied to the new one, up to the lessor of the two sizes.
4. Build & run. Check the output is correct.. Try for a new size both greater and smaller than the old one and see if what happens is what you expect.

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 "pseudo-arrays"

In the last lecture we encountered two ways of having more than one vector (ie multiple one-dimensional arrays).

• Three individual arrays with individual names a, b and c with different lengths stored in three separate blocks of memory.
• A single two-dimensional array stored as a single block of memory allowing us to refer to individual rows by number subject to the the constraint that all of the rows were of the same length.

Both methods had the additional constraints that neither the number of vectors nor their lengths could be changed after their inital declaration.

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 (a two-dimensional array) 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 blocks 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 memory 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

 

1. Step through the above example.
2. To see how we can lose two memory allocations (a simple memory leak).
1. Step through the above example in a new window.
2. Step through the code until just after the third call to malloc() and the assigment to p.
3. Notice how we have three separate blocks of memory but we only know where one of them is.

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

Anything we can have one of we can have an array of.

Since we need M pointers and we are looking to refer to them by number the obvious solution is to use an array of M pointers. 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.

The declaration for an array of M pointers follows the usaul array-declaration rule of typename p[m];, in this case typename is float * so the declaration is float *p[m];.

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 block 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

1. Step through the above example.
2. To see one method to keep track of several memory allocations.
1. Step through the above example in a new window.
2. Step through the code until just after the third call to malloc() and the assigment to p[2].
3. Notice how we have three separate blocks of memory and now have three pointers so we know where each one is.
4. Now step forward to just before the assignment to p[0][1].
5. Try to work out which piece of memory will have its value changed to 3.14159.
   1. Find p[0].
   2. Trace that to the block of memory it points to.
   3. Within that block find element [1].
6. Step through and see if you were right. If not, work out why.
7. Optionally, step through the calls to realloc() and see how we end up with three new blocks of memory.
8. Observe how the value of p[0][1] is still 3.14159 even though the block of memory has moved.

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 blocks of n floating point numbers. Compare this to the single M*n block which would be used by a true two-dimensional array.
2. Unlike the true two-dimensional array, we have M separate blocks 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.
3. We can still access the individual elements using the same p[j][k] notation. The compiler knows that p is an array of pointers rather than a two-dimenmsional array so it generates the correct machine code. We don't need to worry about it.

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

All of the limitations of the previous code arise from the fact that we have used a fixed, declared array of pointers that disappears when the function contining it returns. But of course the whole point of this lecture is that we can dynamically allocate arrays so the answer is simple: `we don't just dynamically allocate the individual arrays of data, we dynamically allocate the array of pointers too,

Dynamically allocating an array of M pointers

Dynamically allocating an array of pointers follows the same rule as arrays of any type:

  type *p;
  p = malloc(m* sizeof *p);

In this case type is float * so the code is:

  float **p;
  
  p = malloc(m * sizeof *p);
 

Note there are two stars not one.

This is the same principle applied twice

As so often in programming all we have done here is to apply the same principle twice:

• A float is a data type, so to get a dynamic array of floats we write:

  	float *p;
  	p = malloc(n * sizeof *p);
        

• A float * is a data type, so to get a dynamic array of float *s we write:

    float **p;
    
    p = malloc(m * sizeof *p);
   
  

The following example is our final code. It 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(). For variety we make each successive allocations one element longer than the previous one.

#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

   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 first vector?\n");
  scanf("%d", &n);

  // For variety we are making the vectors different sizes
  for (int i = 0; i < m; ++i)
    p[i] = realloc(p[i], (n+i) * sizeof *p[i]);

  // 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

We saw in the previous lecture that a true two-dimensional MxN array was one continuous block of M*N values accessed from a single memory address. This pseudo-array is a little more complicated: we have a single pointer pointing to an array of 3 pointers each pointing to a separate block of floats with each block a different length.

As we stated earlier, the good news is that we can access them both via the same x[j][k] notation but that does not mean they are the same thing.

A true two-dimensional MxN array is one continuous block of M*N values accessed from a single memory address. A two-dimensional pseudo-array has a separate block of data for vector, accessed via pointers.

Passing them to functions

Because two dimensional true arrays and pseudo arrays are different things it's not possible to write a single function that can accept either. The prototypes for functions accepting these are:

// Function accepting a true two-dimensional array
void matfun(int n, int m, float ar[][m]);

// Function accepting a two-dimensional pseudo-array
void pseudofun(int n, int m, float **pseudo);

Here we have implicitly assumed the rows of our pseudo-array are all of the same length so we were able to pass just two numbers, m and n, to enable our function to loop over it. But what if all the rows were of different lenghts?

The real work is in keeping track

No high-level functions

Much like in our discussions of ordinary, declared arrays the system does not provide anything in the way of high-level functions to help us keep track of memory:

• There is no standard way of getting a list of what allocations have been made.
• There is no standard way of finding out the size of any individual allocation.
• There is no standard way of knowing if an address is that of a declared or dynamically allocated array.

The three functions malloc(), realloc() and free() are therefore very simple to use and in one sense there is nothing more to know about them. In practice the real work is in keeping track of how many chucks of memory we have allocated and how long they are. There are a number of methods of doing this, some of which we will meet in later lectures.