Scientific programming in C
Allocating space

Comments and questions to John Rowe.

So far we have used pointers to point to existing structures, arrays and, when using scanf(), variables. But this requires us to know the sizes of our arrays and the number of structures we will need when we write the program. If we write our word processor with enough structures to represent four open documents, what hapens when our user wants to edit five?

For this reason, it is also possible to dynamically allocate memory as we need it. This can then be used like any other memory such as that obtained by declaring structures arrays.

Dynamically allocated memory acts like anonymous (nameless) structures and arrays which we can create and destroy at will.

malloc()

#include <stdio.h>
#include <stdlib.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);
  }
  p[0] = p[1] = 3.14159;
  /* Use p for something */
  return 0;
}

The sizeof operator

  p = malloc(N * sizeof *p);  // Good

  p = malloc(N * sizeof(float));  // Bad

The first example is always going to allocate enough memory to store N of whatever type p points to. The second example relies on us having got the type of p correct. Every time we look at this code we will have to go back to the declaration of p to check it is a float. Even worse, if we were to change p to point to a double we would have to go through the entire code looking for calls to malloc().

• If we assumed that p pointed to the space for N doubles but in fact it only pointed to enough space for N floats then that would be a very nasty bug.
• Bugs split between two parts of the code, where each part looks correct when viewed on its own and its only when we compare the two that we find they are inconsistent can be quite hard to spot. So we avoid the chance of them happening.

Always use the sizeof *p form.

NULL

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;
}

Pointers to pointers

#define N 100
#define M 4
int
main() {
  float *p[M];
  int i;

  for (i = 0; i < M; ++i)
    p[i] = xmalloc(N * sizeof *p[i]);

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

int **
new2dint(int m, int n) {
  int **p;
  int i;

  p = xmalloc(m * sizeof *p);
  for (i = 0; i < m; ++i)
    p[i] = xmalloc(n * sizeof *p[i]);
  return p;
}

int
main() {
  int **p = NULL;
  int n;

  do {
    printf("Size of array (>0)?\n");
    scanf("%i", &n);
  } while (n <= 0);

  p = new2dint(n, n);
  p[0][0] = 17;
  p[n-1][0] = 13;
  p[n-1][n-1] = 10;

  return(0);
}

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

  p = new2dint(M, N);

  p[1][7] = 17;
  array[1][7] = 17;

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

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

int oldstylefun(float array[][N]);
int newstylefun(int n, float array[][n]);
int three_d_fun(int m, int n, float array[][m][n]);

Allocating structures

A major use of malloc() is to dynamically create structures. The mechanics work just as we would expect:

struct thingy *p = NULL;
p = xmalloc(sizeof *p);

Notice how str is a pointer not an array. In order to use it we must make it point at something.

#include <stdlib.h>

typedef struct wotsit {
  float val;
  char *str;
  int length;
} Wotsit;


Wotsit *newwotsit(int len) {
  Wotsit *w = xmalloc(sizeof *w);

  w->length = len;
  w->val = 0;
  w->str = xmalloc(w->length);
  return w;
}

int main() {
  Wotsit *william = newwotsit(100);
  /* Blah, blah, blah */
}

Freeing memory

The absolute rule is that we can't use memory after we've freed it and we can free it only once. To reuse the above example we might define a function freewotsit():

void freewotsit(Wotsit *w) {
  free(w->str);
  free(w);
}

  free(w);
  free(w->str);

Pointers that point to something that no longer exists are referred to as dangling.

It would have been very, very wrong.

We would have the same problem if we tried to defererence w after we had freed the memory it pointed to or another pointer had the same value as w and we tried to derefence that. In practice it is only safe to free() some memory if we are careful to set any pointers that point to it to NULL.

"Reallocating" memory with realloc()

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 = alloc(oldsize * sizeof *p);
  ...

  p = realloc(p, newsize * 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.
• 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.

Example of a bug

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

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

Advantages and disadvantages of using malloc()

malloc() is quite slow

One not very obvious disadvantage of malloc() is that because it's so general it's also quite slow. This means that for, say, short arrays that will be used within a function (and the functions it calls) and then thrown away at the end of the function it is better to use automatic ("normal") arrays and structures if we can.

#include <stdlib.h>

void poorfun(int n) {
  double *x;

  x = xmalloc(n * sizeof *x);
  // .. Do some stuff with x

  free(x);
}
 

void betterfun(int n) {
  double x[n];

  // .. Do some stuff with x
}
 

The first version has more ways to go wrong, we might forget to call free(), and is also slower. (However, until C99 programmers had no choice as array sizes had to be declared at compile time.) It's not unknown for the speed of some programs to be dominated by calls to malloc().

Advantages of malloc()

The obvious advantage of malloc() is that its memory is valid after the function returns. Another, much less obvious one, is that many systems have limits on how large the stack can grow which are much larger than the heap. This may mean that it's wise to obtain very large items via malloc() even when they could have been allocated on the stack.

Summary

• Dynamic allocation allows us to change the number of "things" we have as the program runs.
• We must free memory when we are finished and not try to use it after we have freed it.
• Pointers to pointers can be confusing and are not the same as two-dimensional arrays.
• malloc() can be slow.