Computational Physics
Dynamic memory allocation

Comments and questions to John Rowe.

Allocating memory is the easy bit and in reality is just the first of three tasks:

1. Getting more memory.
2. Releasing it when we have finished with it.
3. Keeping track of the memory we have obtained.

We have already covered 1 (malloc) and 3 (free) ; this section is about 2.

Keeping track of memory

We can call malloc as often as we like to give ourselves more and more structures but there's a problem: once you have lost the value of a pointer to memory allocated by malloc there is no way to find it out again so how do we remember where all our structures are?

The following code illustrates the problem: it allocates memory for n structures but promptly forgets where the first n-1 are stored:

  for (i = 0; i < n; ++i)
    p = malloc(sizeof *p);

The first n-1 structures are thus inaccessible: we have allocated the memory but forgotten where it was. It's like writing down someone's phone number and losing the piece of paper you wrote it on - they have a perfectly good phone but you can't ring it because you've lost the number.

We could try having an array of pointers:

  struct coord *p[NMAX];

  for (i = 0; i < n; ++i)
    p[i] = malloc(sizeof *p[i]);

but of course we are back to the same problem: how big do we make NMAX? Clearly we need a method that can handle an arbitrary number of pointers to structures.

[Class exercise.]

Linked lists

The answer to this problem is to make a list of pointers. To make a list we need to add a new element to our structure: a pointer to the next one. The pointer is NULL if there is no next one, ie this element is the last one in the list:

typedef struct coord {
  int x;
  int y;
  struct coord *next;
} Coord;

Creating a linked list

In the following code the function newcoord allocates and initialises a new structure, and adds it on to the beginning of an existing linked list:

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

typedef struct coord {
  int x;
  int y;
  struct coord *next;
} Coord;

void *xmalloc(size_t n);
Coord *newcoord(Coord *first);

Coord *newcoord(Coord *first) {
  Coord *p;

  p = xmalloc(sizeof *p);
  printf("Please enter the x and y values.\n");
  scanf("%d %d", &p->x, &p->y);
  p->next = first;
  return p;
}

main() {
  int i, n;
  Coord *first = NULL;

  printf("How many structures would you like?\n");
  scanf("%d", &n);

  for (i = 0; i < n; ++i) 
    first = newcoord(first);
}

Notice:

• We initialised the first element to NULL to show that the list started off empty: this is vital.

• We put all the checking that malloc didn't fail into a utility function called xmalloc that we can now use just like malloc but without the tedious checking.

Accessing every member of a list

The following for loop loops over every element of the list in turn printing out their x and y values. The pointer p is initially equal to first and then becomes first->next and so on.

  for (p = first; p != NULL; p = p->next)
    printf("%d %d\n", p->x, p->y);

Removing and freeing a member of a list

This introduces an extra complication: as well as freeing the structure itself we also have to remove it from the list.

To remove the first member of a list we simply set the new first member to old_first->next and free old_first. For every member except the first we find its predecessor and change its next pointer to the next of the one we want to free:

Initial list

A -> B -> C -> D -> NULL

After removing 'B'

A -> C -> D -> NULL

free(B)

After removing 'A'

C -> D -> NULL

free(A)

A complete example

/* The structure definition and newcoord are the same as above */

Coord *freecoord(Coord *this, Coord *first) {
  Coord *newfirst = first;

  if (this == NULL)
    return newfirst;

  if (this == first)
    newfirst = first->next;
  else {  /* Find its predecessor */
    while (first != NULL && first->next != this)
      first = first->next;
    if (first == NULL) {
      fprintf(stderr, "%p isn't in the list!\n", this);
      return newfirst;
    }
    first->next = this->next;
  }

  free(this);
  return newfirst;
}

void printallcoords(Coord *p) {
  for (; p != NULL; p = p->next)
    printf("%d %d\n", p->x, p->y);
  printf("\n");
}

int main() {
  int i, n;
  Coord *first = NULL;

  printf("How many structures would you like?\n");
  scanf("%d", &n);

  for (i = 0; i < n; ++i) 
    first = newcoord(first);

  printallcoords(first);
  if (i > 0) {
    first = freecoord(first->next, first);
    printallcoords(first);
  }
  first = freecoord(first, first);
  printallcoords(first);

  return 0;
}