Dynamic Memory Allocation

Here is one of the more interesting topics in C.
Recall the previous diagram we had of memory.

int q;

memory_table2
As you can see, it just shows a single long lane of addresses.
However, we can actually break down memory into more specific categories.
For the purpose of this tutorial, we’ll divide it into 2 segments. Though if you go into more details, it does get more complicated.
Memory is divided into a stack, and a heap.
It can be visualized like so:
stackvsheap
All of our variables that we have been using so far, pointers, arrays, integers, etc. These have all been allocated on the stack.
Stack
The stack, is a type of data structure. The best way to visualize it, is to think of a Pez Dispenser.
tweety-pez-dispenser6
How do you load a Pez Dispenser?
Pull down the bottom and load the candy one by one, starting at the bottom and ending with the last piece at the very top.
Now, say were hungry. How do we take out candy? We pull back on the head, releasing a tablet, note that: the last piece you loaded into the dispenser, is the first to come out
This is called a LIFO structure. Last in first out.
This analogy works great with the pez dispenser, for our friends in the south, it can be made just as easily using the magazine of a 9mm handgun. The last bullet inserted into the magazine, is the first to be fired.

So, you are probably wondering, what exactly are we inserting and removing from this data structure?
The answer is: functions.
When the first function of the program executes, main(), a new item is inserted into the stack.
Any variables declared in main, are local to that stack.
Any following function calls, result in more items pushed on top of the stack. As a function returns it’s popped from the stack.
Let’s look at an example to make this all clear.
Let’s write a program that will be comprised of a main function, the main function takes 2 integers as an input, and calls a function called Divide passing those 2 integers as arguments.
prototype:

double Divide(int numerator, int denominator); 

the function Divide will call another function isZero, this function checks if the denominator is a zero, returns true if it is, otherwise returns false.
prototype:

bool isZero(int a);

Okay let’s write this program, then look and see what’s happening with the stack.

#include <stdio.h>

double Divide(int numerator, int denominator)
{
   if !(isZero(denominator)) //if isZero doesn't return true
          return numerator / denominator; 
   else //denominator is zero
         return 0; //just return 0 for this example

}

bool isZero(int a)
{
    if(a == 0)
       return true;
    else //note that this else statement is redundant, since in the case that return true executes, we instantly exit this function and have no way of unintentionally executing the next line.
       return false;

//you can simplify this code by just writing 
//   return !a; 
//if a is a zero it will negate that and return non-zero, ie. true
//if a is non-zero, ie. false, it will negate it and return false
}

int main()
{

int x; 
int y;
int Quotient; 

printf("Enter 2 integers: ");
scanf("%d %d", &x, &y);

Quotient = Divide(x,y);


return 0;
}

Okay, let’s look at what is happening in the memory.
Note, we will disregard “the heap” for now, as we are just dealing with the stack right now.
Okay, first step, main function gets called. In main we declare 3 integers: x, y Quotient.
stackexample_step1
As you can see it’s at the bottom of the stack.
Okay, in main, we call the function divide. And we pass into divide 2 variables, x and y.
This is a VERY IMPORTANT point. I’ll go into more detail later, however it is important to distinguish that x and y are passed into the function divide BY VALUE this means that you make a copy of them and send them off into the function Divide. That function can do anything it wants with these variables and IT WILL HAVE NO IMPACT on x,y declared inside main.
Let’s see the stack.
stackexample_step2
As you can see, Divide is its own stack, and is completely independent of Main, it has its own variables that are local to it.
Finally, we call the function isZero, and once again pass “denominator” BY VALUE.
stackexample
Thus, we have 3 items in our stack.
Now, let’s exit this program, isZero, will hit the line “return” in the code, at this moment the function isZero, gets popped out of the stack and all variables declared in that function are destroyed as they only existed inside that token in the stack.
Next the function Divide hits a return statement and now this token is popped from the stack. Once again all variables local to this function are destroyed.
Finally, in main we hit the line return 0. Main is popped, all variables declared in main are destroyed.

Pass by Value vs. Pass by Pointer
Okay, so up to now, every time we’ve been passing variables into functions, we have been doing something called: pass by value. What this means is, if you have a variable:

int x = 2;

And you wish to pass this into some function that accepts an integer:

int foo(int a)

You aren’t actually passing the variable x into the function, but rather making a copy of x, and passing that value into foo.
Let’s look at a good example of a limitation that pass by value presents us with.
Let’s write a function that will take 2 variables of type int, and swap their values.
So in main, if we declare

int x = 2;
int y = 3;

We want to pass these 2 variables into a function called Swap, that will swap their values. When we print x and y out, x should print out a 3 and y should print as 2.
A function can only return a single value, so when we swap the values of these integers, we don’t want to return anything, we just do the swap operation in the function, and the variables in main should be swapped accordingly right?

void Swap(int a, int b)
{
   int temp = a;
   a = b;
   b = temp;
}

Okay, so here is a straightforward function, you take a and b as arguments. To swap them, just do the following:
Copy a into a temporary variable.
Copy b’s value into a.
Now copy the temporary variables value, which is a, into b.
Done.
Let’s now actually call this function in main.

#include <stdio.h>;

void Swap(int a, int b)d
{
   int temp = a;
   a = b;
   b = temp;
}

int main()
{
    int x = 2;
    int y = 3;

    Swap(x,y);

    printf("The new value of x is: %dnThe new value of y is: %dn";, x y);

    return 0; 
}

Okay, so the question is, does this work as we need it to?
You can run this code on your machine to test out the outputs of the printf to see for yourself.
But let’s just analyze what we’re doing using our diagram of the stack.
So first thing we do, we are jumping into main.
Our stack just has main, with the variables x and y declared inside it.
stackex1
Alright, so now let’s call the Swap function in main, and we’ll see what is happening to our x and y.
stackex2
So, we add a new token into our stack, this is the Swap function.
As you can see, Swap has 2 variables: a and b with the values 2 and 3 respectively.
These variables are COPIES of x and y that were passed in by VALUE.
Hence, A and B are completely independent of x and y.
Now, let’s do the swapping and see what changes.
stackex3
So, what happened? We made a new variable called temp, which took a’s original value.
Then we assigned b to a, and copied temp into b.
So, we successfully swapped the values of a and b.
The values of a and b.
But as you can clearly see, inside our main function, nothings happened.
Let’s now exit the Swap function and see what happens.
stackex1
As you can see, we exit out of Swap and the variables a, b and temp all go out of scope, and they are immediately deleted. We are back in main, the values of x and y still hold their original values.
So, the question is, how can we actually accomplish this task of swapping x and y in a different function?
The answer to that, is pass by pointer
Okay, so the idea is simple. Remember what pointers where? They hold addresses.
So what if, instead of passing the function Swap two integers, we passed two locations.
We are essentially “telling” the Swap function, here are the locations of these 2 variables, take those addresses, you can dereference them and swap them around.
Let’s take a look at our new Swap function.

void Swap(int* a, int* b)
{
   int temp = *a;
   *a = *b;
   *b = temp;
}

Okay, so let’s break this down.
The function header:

void Swap(int* a, int* b)

This says, the function accepts 2 pointers to integers. This is exactly what we want, we don’t want to pass copies of our variables, we want to pass in their locations in memory.
Now, let’s look at our function body.


   int temp = *a;
   *a = *b;
   *b = temp;

As you can see, temp is still just your standard integer variable. We then dereference a, and say, whatever value is stored at a’s address, put that inside the integer variable temp.
Now, whatever the pointer, b, is pointing to, we want to take that value and put it where a is pointing.
Finally, we take the integer temp’s value, and store that in the location where b is pointing to.
Note, if you don’t dereference these pointers, the code will not work. You must dereference them, otherwise you change what they are pointing to, not the value that they are pointing to.
Okay, so now let’s see how we will call this function in main.

#include <stdio.h>;

void Swap(int* a, int* b)
{
   int temp = *a;
   *a = *b;
   *b = temp;
}

int main()
{
    int x = 2;
    int y = 3;

    Swap(&x,&y);

    printf("The new value of x is: %dnThe new value of y is: %dn";, x y);

    return 0; 
}

One very important line I’d like to draw your attention to is in Main().

Swap(&x,&y);

Note the key difference here. We aren’t passing in 2 variables into Swap. We are passing their addresses!
Okay, let’s now take a look at what our stack is doing.
stackex1
So far, it’s the same as before. We’re just in main, 2 integer variables declared: x and y.
Let’s see what the call to Swap will look like visually.

stackex4
As you can see, a and b are now pointers. They are pointing to x and y. This is a great visual to understand the difference between what pass by value is and pass by pointer.
Okay, so let’s now do the swapping and see what happens.
stackex5
And there you have it, we successfully changed the values of x and y by swapping them in a different function.
Now, let’s exit from Swap and get back to Main().
stackex6

Dynamic Memory Allocation
So far, every time we’ve declared a variable, it’s been created on the stack. The memory allocation for these stack variables is automatic. Variables on the stack are deleted once they go out of scope, we don’t have to actually worry about what happens to that memory.
When do we want to allocate memory dynamically?
Say you want to store peoples names.
We can’t make arrays of variable size the way we know now.

char Name[100]; 

The only way to do this would be to make a really large character array to make sure that no one will have a longer name.
However the problem is that we’re wasting space. Imagine a thousand different names, or a million. It really adds up.
So, what we need to do is allocate memory dynamically.
We use a function called: malloc.
Malloc takes one argument, an integer. We need to tell malloc how much space we are allocating. It then returns a pointer to this memory.
It says, okay so I reserved a chunk of memory for you, here is a pointer to it.
It’s worth noting that Malloc returns a void pointer. This means it’s not of any specified type.
We need to use something called “type casting” to convert this void pointer into what we desire.
For example, if we wish to allocate space for n-integers, we need to type cast Malloc to an integer pointer, if we’re allocating space for n-floating point variables, or n-chars, we would cast it into a float pointer or char pointer respectively.
How do we tell Malloc how much space we need?
This isn’t exactly obvious as an integer and char take up different amounts of space.
An integer declared on a 32-bit system is also different than an integer declared on a 64-bit system.
So how do we know how much space to allocate?
Recall the function sizeof().
We can use this function to get the exact size of any variable on the system we’re working on.
So to allocate n-integers, we pass: n * sizeof(int) into Malloc.
Let’s look at some actual code.
For this example, we’re going to compare an integer array of 10 elements declared automatically to a 10 element integer array declared dynamically.

int myArr[10]; 

int* myDArr = (int*)malloc(10 * sizeof(int));

So, the code on the top is self explanatory, it’s a regular 10 element array, declared automatically. This means it exists on the stack. As soon as myArr goes out of scope, the memory reserved for those 10 elements is immediately returned back to us and the variable is destroyed.
Now let’s take a look at the dynamic array.
As you can see we use Malloc. Since we need an integer array of 10 elements, our argument is 10 * the size of an integer.
As previously mentioned Malloc returns a void pointer, hence by writing (int*) in front of it, we are type casting the void pointer to an integer pointer.
And lastly, we assign this to an integer pointer.
The Heap
Okay, let’s have a look at how this dynamic memory allocation looks like with our memory diagrams.
Here’s some sample code.
Note: To use Malloc, we need to include a new C-Library called the Standard Library.

#include <stdio.h>
#include <stdlib.h> //need this for Malloc

int main()
{
    int* myAr = (int*)malloc(5* sizeof(int));

    return 0;
}

Let’s look at the following diagram.
dynamicmemex1
The right side of the diagram is called the heap.
All memory allocated using Malloc is on the heap.
The pointer however, as you can see is a regular pointer on the stack.
Now, let’s have a look at some problems we can have if we’re not careful using Malloc.
Let’s take a look at the following code:

#include <stdio.h>
#include <stdlib.h> //need this for Malloc

void makeArray(void)
{
    int* q = (int*)malloc(5* sizeof(int));
}

int main()
{
    makeArray();

    return 0;
}

Okay, so what is our function doing? It’s just allocating space for 5 integers. Can you spot the problem?
Let’s have a look at the diagram.
dynamicmemex2
Okay, this looks fine, as we’ve seen before the function makeArray has an integer pointer declared inside it, this points to some memory allocated on the heap.
Now let’s see what happens when we exit from this function.
dynamicmemex3
Naturally, makeArray is popped from our stack and it’s local variable, the integer pointer, is destroyed.
But what happens to the memory it was pointing to in the heap?
Nothing.
It stays there until you manually free it up.
This is a memory leak.
To avoid such problems we have to always remember to free memory when we’re finished with it.
This is done with the function free().
Let’s fix the code now and see the result.

#include <stdio.h>
#include <stdlib.h> //need this for Malloc

void makeArray(void)
{
    int* q = (int*)malloc(5* sizeof(int));
    free(q);
}

int main()
{
    makeArray();

    return 0;
}

This fixes our problem, as we can see after the line free(q) is executed, we can observe the following.
dynamicmemex4

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s