Allocating and keeping track of memory

Comments and questions to John Rowe.

Lists, etc.

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

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

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 we 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 we wrote it on - they have a perfectly good phone but we can't ring it because we've lost the number.

We could try having an array of pointers:

#define NDIMS 3

typedef struct particle {
  double position[NDIMS];
  double velocity[NDIMS];
  double mass;
} Particle;

  struct particle *p[NMAX] = { NULL };

  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.

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

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

Using realloc() allows us to create a "growable array":

Dynamically allocated arrays of structures

One answer is to make the array of structures dynamically allocated. The idea is that we keep track of how the size of our array of structures and how many we are using. In this example we assume we have just one "array" of particles and it might as well be a global.

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

#define NDIMS 3

typedef struct particle {
  double position[NDIMS];
  double velocity[NDIMS];
  double mass;
} Particle;

/* This next is a dynamically-allocated array of stuctures */
Particle *particles = NULL;

void newparticle(void) {
  static int nparticles = 0, partbufsize = 0;

  /* Is our buffer of pointers large enough? */
  if ( nparticles == partbufsize ) {
    partbufsize += 32;
    particles = realloc(particles, partbufsize * sizeof *particles);
    if (particles == NULL ) {
      fprintf(stderr, "Out of memory!\n");
      exit(1);
    }
  }
}

We can then say things such as:

particles[j].mass = 1.7;

If we had more than one such array we would need a value of nparticles and partbufsize for each one and we would put particles, nparticles and partbufsize into a structure:

typedef struct {
  Particle *particles;
  int nparticles;
  int partbufsize;
} System;

We can then access individual particles using syntax such as:

sys->particles[n].mass

where sys is a pointer to a System. In practice the system structure would probably have all sorts of information about the system as a whole, leading to an important point: structures tend to have links to other structures.

Linked lists

The above works well when we have just one set of particles, when we have several it is a little messy, although it is sometimes the right thing to do. A more common solution is for each structure to "reember" the address of the next one.

[Class exercise.]

Applied to computing this is called a list of structures. 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 particle {
  float mass;
  float x[NDIM];
  struct particle *next;
} Particle;

Creating a linked list

In the following code the function newparticle 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 particle {
  float mass;
  float x[NDIM];
  struct particle *next;
} Particle;

void *xmalloc(size_t n);
Particle *newparticle(Particle *first);

Particle *newparticle(Particle *first) {
  Particle *p;

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

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

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

  for (i = 0; i < n; ++i) 
    first = newparticle(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 mass and co-ordinates. 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("%f (%f, %f)\n", p->mass, p->x[0], p->x[1[);

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 newparticle are the same as above */

Particle *freeparticle(Particle *this, Particle *first) {
  Particle *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 printallparticles(Particle *p) {
  for (; p != NULL; p = p->next)
    printf("%f (%f, %f)\n", p->mass, p->x[0], p->x[1]);
  printf("\n");
}

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

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

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

  printallparticles(first);
  if (i > 0) {
    first = freeparticle(first->next, first);
    printallparticles(first);
  }
  first = freeparticle(first, first);
  printallparticles(first);

  return 0;
}

Summary

• Dynamic allocation allows us to change the number of "things" we have as the program runs.
• But these things have no name so we must have a way of remembering where they are.
• 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-dimansional arrays.

Optional material

Dynamically allocated arrays of pointers

Our previous example of a dynamically allocated array had a disadvantage in that it allocated 32 structure sat a time and we might only want one or two. This wasn't a huge problem but we could get round it by allocating an array of pointers (which are only four or eight bytes each) and then allocating the particles one at a time. It looks like this:

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

#define NDIMS 3

typedef struct particle {
  double position[NDIMS];
  double velocity[NDIMS];
  double mass;
} Particle;

/* This next is a dynamically-allocated array or pointers */
Particle **particles = NULL;

void newparticle2(void) {
  static int nparticles = 0, partbufsize = 0;
  Particle *newp;

  /* Is our buffer of pointers large enough? */
  if ( nparticles == partbufsize ) {
    partbufsize += 32;
    particles = realloc(particles, partbufsize * sizeof *particles);
  }

  newp = malloc(sizeof *newp);

  if (newp == NULL || particles == NULL ) {
    fprintf(stderr, "Out of memory!\n");
    exit(1);
  }

  particles[nparticles++] = newp;
}

We can then say things such as:

particles[j]->mass = 1.7;

Our system structure now looks like this:

typedef struct {
  Particle **particles;
  int nparticles;
  int partbufsize;
} System;

We can then access individual particles using syntax such as:

sys->particles[n]->mass;