Algorithms Design   |   C language   |   Index

Dynamic memory allocation

The declarations below allocate space in memory for some variables. The allocation is static (no relation to the static keyword), that is, it happens before the program begins to be executed.

char c; 
int i; 
int v[10]; 

In many applications, the amount of memory to allocate only becomes known during the execution of the program. To deal with this situation we must resort to dynamic memory allocation. The dynamic allocation is managed by the functions malloc, realloc, and free, from the stdlib library.  To use this library, you must include the corresponding interface in your program:

#include <stdlib.h>

The malloc function

The  malloc  function (the name is a shorthand for memory allocation) allocates space for a block of consecutive bytes in the random access memory (RAM) of the computer and returns the address of the block.  The number de bytes is specified by the argument of the function. In the following code fragment, malloc allocates 1 byte:

char *ptr;
ptr = malloc (1);
scanf ("%c", ptr);

The address returned by malloc is of the generic type  void *.  The programmer stores this address in a pointer of the appropriate type. In the example above, the address is stored in the pointer ptr, of type pointer-to-char.  The transformation of the generic pointer into a pointer-to-char is automatic; there is no need to write ptr = (char *) malloc (1);.

In order to allocate space for an object that needs more than 1 byte, we often use the sizeof operator (which says how many bytes the object in question has):

typedef struct {
   int day, month, year; 
} date;
date *d;
d = malloc (sizeof (date));
d->day = 31; d->month = 12; d->year = 2019;

Note that sizeof is not a function but an operador, such as return, for example. The parentheses in the expression sizeof (date) are necessary because date is a data type  (the parentheses are analogous to those of the casting).  The operador sizeof can also be applied directly to a variable:  if var is a variable then  sizeof var  is the number de bytes occupied by var.  We could have written d = malloc (sizeof *d) in the example above.

Exercises 1

The free function

The variables that are statically allocated inside a function, also known as automatic or local variables, disappear as soon as the execution of the function ends. The dynamically allocated variables, however, continue to exist after the execution of the function ends. If you no longer need such a variable, you must call the free function to liberate the corresponding chunk of memory.

The function free deallocates the bytes allocated by malloc. The instruction free (ptr) tells the operating system that the block of bytes pointed to by ptr is available for recycling. The next call to malloc may use these bytes.

Never call the free function on a part of the block of bytes allocated by malloc (or realloc). The free function should only be applied to the whole block.

Exercises 2

Arrays and matrices

Here is how an n-element integer array can be allocated (and then deallocated) during the execution of a program:

int *v; 
int n;
scanf ("%d", &n);
v = malloc (n * sizeof (int));
for (int i = 0; i < n; ++i) 
   scanf ("%d", &v[i]);
. . . 
free (v);

(By the way, see the section Address arithmetic in chapter Addresses and pointers.)  From the conceptual point of view (but only from that point of view) the effect of the instruction

v = malloc (100 * sizeof (int));

is analogous to the static allocation

int v[100];

Matrices.  Two-dimensional matrices are implemented as arrays of arrays. A matrix with m rows and n columns is an m-element array each of whose elements is an n-element array. The following code fragment does a dynamic allocation of such a matrix:

int **M; 
M = malloc (m * sizeof (int *));
for (int i = 0; i < m; ++i)
   M[i] = malloc (n * sizeof (int));

Therefore, M[i][j] is the element of M sitting at the intersection of row i and column j.

Exercises 3

Resizing and the realloc function

Sometimes it is necessary to change, during the execution of a program, the size of a block of bytes previously allocated by malloc.  This happens, for example, when reading a file that turns out to be larger than expected.  In this case, we can resort to the realloc function in order to resize the allocated block of bytes.

The realloc function increases the size of a block of memory that has been dynamically allocated. The function receives the address of a block of bytes previously allocated by malloc (or by realloc itself) as well as the number of bytes that the resized block should have. The function allocates a block of the desired size, transfers the contents of the old block to the new one, and returns the address of the new block. The function deallocates the old block by a call to free.

The realloc function can also decrease the size of a dynamically allocated block of memory. This happens if the requested number of bytes is smaller that the size of the original block. In this case, no new block of memory is allocated and the contents of the original block is not moved. The address of the new, smaller, block is the same as that of the original one.

Suppose, for example, that we allocated an array of 1000 integers and later decided that we need twice as much space. Here is a silly example:

int *v;
v = malloc (1000 * sizeof (int));
for (int i = 0; i < 990; i++)
   scanf ("%d", &v[i]);
// oops! we need more
v = realloc (v, 2000 * sizeof (int));
for (int i = 990; i < 2000; i++)
   scanf ("%d", &v[i]);

In this example, we could use the following ad hoc implementation of realloc:

int *realloc (int *v, unsigned int N) {
   int *new = malloc (N);
   for (int i = 0; i < 1000; i++)
      new[i] = v[i];
   free (v);
   return new;
}

The implementation of realloc in the stdlib library is, of course, more general and more efficient.

Exercises 4

The memory is finite

If the memory of the machine is already full, malloc is unable to allocate more space and returns NULL. One should check for this possibility before proceeding:

ptr = malloc (sizeof (date));
if (ptr == NULL) {
   printf ("Help! malloc returned NULL!\n");
   exit (EXIT_FAILURE);
}  

To avoid typing this check again and again, we shall use the following wrapper in place of malloc:

void *mallocc (size_t nbytes) {
   void *ptr;
   ptr = malloc (nbytes);
   if (ptr == NULL) {
      printf ("Help! malloc returned NULL!\n");
      exit (EXIT_FAILURE);
   }
   return ptr;
}

The parameter of mallocc is of type  size_t  (shorthand for size data type); in many computers, size_t is the same as unsigned int.

Similarly, we can prepare a wrapper function for reallocc to take care of the situations in which realloc returns NULL.