To share this page click on the buttons below;

Dynamic memory allocation

There are times you don‘t know the number of variables your program is going to handle. Let‘s suppose for example that you want to write a program that allows the user to draw circles on the screen. The program needs to store each circle the user draws into a variable.

For each circle we need to store the center and the radius, so that a suitable type variable is a structure holding those values all together.

But here it comes a question: how many circle variables do we need? There are two possible approaches: the first one is to decide a maximum number of circles the user is allowed to draw at compile time (when you write the program), the second is to create new variables at run time (when the program is running) just when you need them.

Is the maximum enough?

The first approach is easy: all you have to do is to declare an array of circle structures, this array will have a number of elements equal to the maximum number of circles the user can draw. Every time a circle is drawn, an element of the array is used: once the array is full the user is not more allowed to draw.

But this approach relies on your ability to define a sensible amount for the maximum number of circles you made available to the user. The point here is that we do not have any clue about what sensible means. Suppose that you define the maximum as 100: that seems to be a quite reasonable number of circles, but what if the user wants to draw 103 circles? With that in mind you can think the more the better: so you might think to fix the maximum to a very high value (a billion perhaps). In this case however you are probably wasting a lot of memory: none in the world will be so patient to draw more than some thousand of circles, but since you have declared the array to be a billion big, that space is actually reserved and cannot be used for any other purpose.

There must be a better approach and it turns out there is with the dynamic allocation of variables at run time.

A variable when you need

First let‘s start with some terminology: when you define a variable in your program the compiler is reserving a space in memory for that variable. That space is allocated to that variable. There is more, that allocation is "static" because it cannot change when the program runs: that is a static memory allocation.

However we could need to allocate new variables when the program runs: these variables will be allocated (and deleted) only when needed and so we talk about dynamic memory allocation.

A second important point to bear in mind is that every program has a special part of unallocated memory it can use when it needs: that is called the heap. There is nothing special about the heap: it is simple a space in memory which is not assigned to any variable or function when the program starts, it is an available free space of memory.

The program itself can grab some of that space when it is needed to store new variables. To do that it needs to use some library functions that are defined in stdlib.h.

When those functions grab space into the heap two things happen: some space of the heap is now (dynamically) allocated, so it is reserved for some purpose and it is no longer available (so that the dimension of the heap, the portion of the free available memory becomes smaller) and one or more new variables are made available to the application: those variables will be accessible via pointers.

Pointers are the right tool because they have the ability to point to different addresses in memory and so they are perfectly able to to point to a new allocated variable (that does not have its own name). The * operator, on the other hand, will give you exactly what you need to access the newly allocated variables.

There is another point that is worth to note here: once you allocate a new variable on the heap, the heap will become smaller so that you cannot continue to allocate new variables indefinitely, after all the memory is always finite. What you can do (to say better what you have to do) is to delete the variables you no longer need. That is a crucial point for an healthy memory management: allocate new variables when needed and delete when you no longer use them, this will prevent your program to run out of memory.

All dynamic allocated variables must be deleted.

Unfortunately C does not have any automatically mechanism to free the (no more used) memory itself (what is called "garbage collector" for some other languages like Java or C#) and you must remember to delete the previously (dynamically) allocated variables when they are no more used.

That fact of freeing memory is often underestimated and can lead to problems that are very hard to discover. For example suppose you have to write a program that processes images: each image can take up a lot of memory, if you do not delete variables responsible to held back images you can have the risk to finish the heap space, your program, that was working fine, will be (suddenly) no more able to work.

On the other hand (especially in large project) the allocation and deallocation of the variables are performed in very different places so that if you forget to proper delete a variable it may become hard to find which variable and when to delete it. My suggestion is to pay attention when you allocate new memory: always ask yourself how and when am I going to deallocate it? And write the correspondent piece of code. Remember that a well written C program always releases all the memory it has dynamically allocated.

The fact that you can actually run out of memory lead us to another important point: you are not guarantee that your dynamical variables can actually be allocated. It depends on the amount of free space available on the heap. If you ask more that what is available the dynamic allocation will fail and you won't get the variables space you asked. That is another frequent cause of problem: every time you ask for a new allocation you need to verify if that operation has been successfully performed or the program might suddenly crash.

Always check that the memory allocation succeed before to use the dynamic allocated variable.

The functions to allocate and free memory

The functions to allocate and free memory are defined in stdlib.h so that you have to include that file if you want to perform dynamical memory allocation.

There are just 4 functions and so we are going to see them in detail.

malloc

malloc is the contraction of "m"emory "alloc"ation and it does exactly that: it looks on the heap to find a contiguous part of that memory space big enough, if available it reserves it and then it returns a pointer to the beginning of that space. This is the signature of the function:

void *malloc(size_t size);

The argument is just the size of the memory block you need (in bytes), the argument type is size_t which is just an integer (I know that this could sound strange, but we have not yet seen the type definition, so for the moment let‘s just see size_t as an integer) and the return value is a pointer to void. Why a pointer to void?

Well, when you ask for memory you always want to map you memory to a variable (an integer, a double, a structure and so on) and the malloc function cannot be aware of what type you want to use, so it returns a generic pointer to void, it is your responsibility to correctly cast that generic pointer to the desired type.

malloc reserves spaces but does not initialize it, the content of the memory space grabbed using that function must be considered completely random.

free

free performs the opposite operation: it frees a part of memory previously allocated. That is its signature:

void free(void *ptr);

It takes a pointer to void (that would be one of the previously allocated pointers) and it returns nothing (because it is assumed that a free operation will always succeed). Again it takes a generic void pointer because this way it can free whatever variable type was previously allocated.

malloc & free example

The following example shows how to use the malloc and free functions (in the case of our example of circles):

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

struct Circle {  
   int x;
   int y;
   double radius;
};

int main(void) {

   struct Circle *myCircle = (struct Circle *)malloc (sizeof(struct Circle));

   if(myCircle !=  NULL) {
      myCircle->x = 5;
      myCircle->y = 3;
      myCircle->radius = 1.2;
      printf("Center of the circle: (%i,%i)\n", myCircle->x, myCircle->y);
      printf("Radius of the circle: %f\n", myCircle->radius);
   }

   free(myCircle);

   return 0;
}

There are a few comments worth to note:

you can see malloc at work, you ask for a space big enough to contain a Circle structure using sizeof and you cast the returned value to a pointer to a Circle structure (that must be done, otherwise the compiler would not understand how to treat this space in memory)
the if(myCircle != NULL) is the check on the result of the allocation (never forget!), if the allocation failed malloc would return NULL (that is a constant defined in stdio.h) which means that was impossible to allocate the space (probably because there is no more space available). You must always check that because if you try to access the value of an invalid pointer the program will inexorably crash.
last you see the free function in action (in this case you do not need to cast the pointer to void * because a void pointer means exactly that: any kind of pointer).

calloc

calloc is another function that can be used to allocate new variables, the reason to have another function is that this one is more suitable for array allocation and it does also perform an initialization of the allocated memory block: a block of memory allocated using calloc is guarantee to contain zero everywhere.

The signature of the function is:

void *calloc(size_t num, size_t size);

The first argument num is the number of element of the array and the second argument size is the size of each element of the array. Again the value returned is a pointer to void that you are requested to cast to the correct type. Also for calloc the space allocated must be always released using free.

realloc

The last function to allocate memory is realloc. That function is suitable when you have already allocated some space and you need more. realloc searches for a bigger space, allocates it and copy the content of the previously allocated block (the one you want to enlarge) to the new allocated space. realloc however does not free automatically the old (smaller) space.

The signature of the function is:

void *realloc(void *ptr, size_t size);

The first argument (prt) is a pointer to a previously allocated memory block you want to enlarge (it can be NULL and in this case realloc works exactly like malloc) and the second argument (size) is the desired dimension of the new enlarged block. The value returned is a pointer to void that you are requested to cast to the correct type. Also in this case the space allocated must be always released using free.

A first (unsatisfactory) solution

Now we know how to allocate variables "on the fly" while the program is running. How we can use them? Let's recap: we have to deal with an unknown number of Circle the user draws, we do not want to put a limit on the number of Circle the user is able to draw, we do not want to waste memory to reserve space for Circles the user is not actually drawing. We know that we can allocate the variables just when we need.

If we have a look on the previous malloc & free example we can immediately understand how our approach is still limited. In fact we can allocate as many Circle variable we want, but since we have just one pointer, if we re-use it to allocate a new Circle we lose the track of the previous one.

struct Circle *myCircle = (struct Circle *)malloc (sizeof(struct Circle));
myCircle = (struct Circle *)malloc (sizeof(struct Circle));

If we use the pointer myCircle twice like in the previous code we are actually allocating two variables, but starting from the second malloc there is no more way to access the Circle variable created with the first malloc. Pay attention: the variable is somewhere in the memory (because we did not delete it using free) but since we overwrote its address (contained in the pointer myCirlce) with a new malloc we lose the possibilty to reach it.

We can achieve better results using calloc or realloc like this:

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

struct Circle {  
   int x;
   int y;
   double radius;
};

int main(void) {

   int allocate_circles = 0;
   int j = 0;

   /* first allocation */

   struct Circle *myCircle = (struct Circle *)malloc (sizeof(struct Circle));


   if(myCircle != NULL) {
      /* keep track of how many Circle allocation have been performed */
      allocate_circles++;
      myCircle->x = 5;
      myCircle->y = 9;
      myCircle->radius = 10.5;

      printf("First Circle: (x,y)=(%i,%i) radius=%.2f\n\n", (myCircle)->x,(myCircle)->y,(myCircle)->radius);
   }

   /* second allocation, we use realloc so that the previous Circle is
      automatically copied */   

   struct Circle *old_ptr = myCircle; 
   myCircle = (struct Circle *)realloc (myCircle, 2 * sizeof(struct Circle));

   if(myCircle != NULL) {
      /* keep track of how many Circle allocation have been performed */
      allocate_circles++;
      /* we can safely free the first allocation, because we have a copy,
         but only if our pointer is changed, otherwise we may free a used 
         piece of memory */
      if(myCircle != old_ptr) {
        free(old_ptr);
      }
      /* we can use pointer arithmetic to access the second allocated Circle 
         NOTE that myCircle now is pointing to an array made of 2 Circles 
              but (remember?) array "are" pointers, so... */
      (myCircle + 1)->x = 6;
      (myCircle + 1)->y = 3;
      (myCircle + 1)->radius = 8.56;

      /* BUT the first Circle is still there and we can access it */
      for(j = 0; j < allocate_circles; j++) {
         printf("Circle n: %i (x,y)=(%i,%i) radius=%.2f\n", j + 1, (myCircle + j)->x,(myCircle + >y,(myCircle + j)->radius);
      }

   }

   /* Now we can free all togheter*/
   free(myCircle);

   return 0;
}

Now things are starting to work as expected: first we allocate a Circle as using malloc, then we realize we need another Circle and so we call realloc to double the space. Now we can trait the pointer myCircle as an array (because array are pointer, isn‘t it?) and we can access both the first and the second Circle we just created. Here we can really appreciate why is so important that arrays and pointer are exactly the same thing.

Probably a little extra explanation is necessary when we use realloc. realloc always tries to preserve the allocated space (it tries to enlarge a previously allocated space) so that it is not necessary copy data from the old allocated space to the new one. That is done to preserve performances because the copy is time consuming. The old pointer cannot be freed in this case or we delete also our new allocated space. So when we use realloc 2 things can happen:

there is enough space right after our previous allocated variable and so realloc does not need to move the data: it simply enlarge the space associated with the first allocated variable; this also means that the returned pointer does not change (the address remains the same)
there is not enough space and so realloc looks for a bigger contiguous space and move the previously allocated variable in that new position.

In both cases we need to perform some checks on the old value of the pointer (*old_ptr in our example): if the address held by the pointer is changed by the realloc call then we need to free the old used space in memory (because realloc does not perform such task), but if the address does not change we cannot free the pointer or we delete some used variables. I hope the following image can help to understand this point:

Visual reprentation of a re-allocation memory process

This approach now works and solves our problem, nevertheless is still a little bit naive: realloc has the problem of the copy that can slow down the performances, furthermore the space allocated in this way is always contiguous. This means that realloc is requested to find a space big enough to contain all our variables together, that may become rapidly impossible if the heap is heavily used and many different allocations are requested by the application.

A better solution can be achieved using complex data structures like linked list, but this will be perhaps the argument of another chapter.