The occasional appendices and optional examples in this module are for advanced material that you will not need for this module. They are intended for enthusiastic students who are interested in going further in programming for its own sake.

Optional example: using pointers to pointers to create a 2-D symmetric matrix

Physical problems often involve arrays that are symmetric: ar[j][[k] == ar[k][j] Rather than store every off-diagonal value twice we can consider a "triangular matrix" where the first row is of length one, the second of length two etc and make sure we only access ar[j][k] where k <= j  (Even if we didn't want to resize the "matrix", ordinary arrays wouldn't be able to handle this as the rows are of different lengths.)

This has the interesting property that if we do want to resize the matrix we don't need to resize the rows: the first row always has length one, the second length two etc. Rather, if we shrink the array we just free() the unwanted rows, if we grow the array we just allocate more rows. What we will need to do is to change the number of pointers to the rows. Thus this is essentially the miror image of the example in the lecture where we could change the length of the rows but not the number of rows.

Using realloc(NULL,...) as malloc() and free()

If we assume that we will need to resize the array and that we are using floats then we will need a function with a prototype such as:

// Shrink or extend a symmetric array
float **resizesymarray(float **p, int oldm, int newm);

This impies that the function to create a new array could just look like:

// Create a new symmetric array
float **newsymarray(int m) {
  return resizesymarray(NULL, 0, m);
}

And the function to free a symmetric array could ust be:

// Free a symmetric array
void freesymarray(float **p, int m) {
  resizesymarray(p, m, 0);
}

(We could just not bother to have these functions, and just call resizesymarray() directly. But it is much easier for the user of these functions to call an intuitive function such as one of these rather than a non-intuitive call to resizesymarray().)

The complete program looks like this:

#include<stdio.h>
#include<stdlib.h>
// Shrink or extend a symmetric array
float **resizesymarray(float **p, int oldm, int newm) {
  int i;

  // Is the new one smaller?
  for (i = newm; i < oldm; ++i) 
    free(p[i]);

  p = realloc(p, newm * sizeof *p); 
  
  // Is the new one bigger?
  for (i = oldm; i < newm; ++i) 
    p[i] = malloc((i+1) * sizeof *p[i]);
  
  return p;
}

// Create a new symmetric array
float **newsymarray(int m) {
  return resizesymarray(NULL, 0, m);
}

// Free a symmetric array
void freesymarray(float **p, int m) {
  resizesymarray(p, m, 0);
}
  
int main() {
  float **p = NULL;
  int n, newn;

  printf("Size of array (>0)?\n");
  scanf("%i", &n);

  p = newsymarray(n);
  p[0][0] = 17;
  p[n-1][1] = 11.3;

  printf("New size of array (>0)?\n");
  scanf("%i", &newn);

  p = resizesymarray(p, n, newn);
  // Do stuff here
  
  freesymarray(p, newn);
  // Do more stuff not requiring p

  return 0;
}

Step through this code

Allocating and freeing data often has a required order

The resizesymarray() function is quite careful in the order it carries out allocations and calls to free().

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

Whenever we increase the size of the matrix we first grow the array of pointers and then populate the array with the actual rows of data. Conversely, when we shrink the matrix we have to free the unwanted rows first and then reduce the size of the array of pointers. This is quite a common occurrence:

An improved version of the array

The version above makes a lot of calls to malloc(), some for very small allocations (the first is just four bytes long for example).

However there's an important simplication we can make: we can store an entire NxN triangular martix as a single block of N*(N+1)/2 values with the first row in location 0, the second row in locations from 1 to 2 and the n^th row going from locations (n-1)*n/2 to n*(n+1)/2 - 1. Notice that for a given n this is independent of the size, N, of the matrix. This is only true for a triangular matrix; for a square matrix row n is stored from location (n-1)*N to n*N-1 which depends on N.

This means that if we increase the size of the matrix from N to M (assuming M > N) then the first N rows of the new matrix occupy the same positions as the old one, and if we shrink it then the new matrix is just the first part of the old one.

So now we have a single block of data to (re)allocate which is both quicker and simpler.

Our improved code now looks like this:

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

// Shrink or extend a symmetric array
float **resizesymarray(float **p, int oldm, int newm) {
  int i, siz;
  float *dat = NULL;
  
  siz = newm * (newm+1)/2;

  if ( p != NULL )
    dat = p[0];

  dat = realloc(dat, siz * sizeof *dat); 
  p = realloc(p, newm * sizeof *p); 

  for (i = 0; i < newm; ++i) 
    p[i] = dat + i * (i+1)/2;
  
  return p;
}

// Create a new symmetric array
float **newsymarray(int m) {
  return resizesymarray(NULL, 0, m);
}

// Free a symmetric array
void freesymarray(float **p, int m) {
  resizesymarray(p, m, 0);
}

int main() {
  float **p = NULL;
  int n, newn;

  printf("Size of array (>0)?\n");
  scanf("%i", &n);

  p = newsymarray(n);
  p[0][0] = 17;
  p[n-1][1] = 11.3;

  printf("New size of array (>0)?\n");
  scanf("%i", &newn);

  p = resizesymarray(p, n, newn);
  // Do stuff here

  freesymarray(p, newn);
  // Do more stuff not requiring p

  return 0;
}

Step through this code

Address arithmetic

One line from the new resizesymarray() function deserves a little explanation:

    p[i] = dat + i * (i+1)/2;

First, what is it trying to do? Well we have a solid block of memory for the entire array but we need pointers to the start of each row and that is what we are doing here.

Second, the value of the expression.

• The value of dat is the address of the dynamically array of floats.
• When a memory address addr pointing to a "thing" has an integer n added to it the result is the address of the n^ththing along from addr.

(Try stepping through the code to see this in action.)