In this section, we will learn what the Stack and Heap are and how to use them in C.
Note: Before reading this section, we’re assuming you already familiar with functions. If don’t, please read the `functions` section first.
Memory Allocation Analogy: (What is an Allocation)
Let’s say we’re reading a book and on the page 70, we realize that there’s a reference to another book that is the prerequisite to the rest of this first book.
So we stop the first book right on the page 70 and move on to the second book.
We find the second book and put it right on top of the first book and start to read it (basically we’re creating a stack here because our table is not big enough to put the second book somewhere else and also we’re lazy to close the first book and put it aside and after that open the second book!). As we progress on the second book, again, realize that on the page 100 of this book, there’s another reference that we should read before continuing to the rest of the second book.
So we stop the second book right on the page 100 and move on to the third book.
We find the third book and put it on top of the second book and start to read it (So now there’re three books stacked on top of each other).
The third book does not have any reference to other books and we simply finish it and move back to the second book.
So now the third book is off the stack and the second book is ready to be continued from the page 100 (BTW, throughout the time we were reading the third book, the second book was open on the page 100 and waiting for the third book to be finished and get off the stack).
As we progress on each book, we put notes on each page and highlight a few sentences here and there. But remember, these notes and highlights are limited to each book and only accessible via the book itself! (That would be weird if we could access one book’s notes and highlights via another book!!!)
Let’s say we used yellow and green highlighter to highlight sentences and paragraphs in each book. These highlighters are put on the table that we used to read the books. So it doesn’t matter if we are reading the first book or second one or the third one, these highlighters are accessible for each of these books.
Alright, we progressed on the second book and reached the page 400 and it turns out there’s another reference to another book and we need to read that reference book in order to be able to read the rest of the second book.
So we again find the reference and stack it on top of the second book and start to read it.
After a while, the reference book is finished and so off the stack.
Note: the whole time that we were reading the reference book, the second book was open on the page 400 and waiting for the reference to be finished and get off the stack.
Now that we are back to the second book, the reading is continued and we successfully finished the second one as well (it is off the stack now).
Alright, now we are back to the first book on the page 70 and start to keep reading from this page.
Fortunately, the first book did not have any other reference and so we successfully finished that book as well.
The reading is done and nothing left on the stack to be read.
Now let’s go into the C programming world and see what the stack and heap are and how they are working!
Stack and Heap in C
The Stack and Heap are two different areas in the memory where the data of our program will be stored when the program is running.
As mentioned in the computers in general section, CPU is the brain of the computers. You can think about it as the person in our story who started to read the books.
But what is it that CPU read? Well, it’s the instructions within programs (every declaration, expressions, initialization, conditions that involved in a program, line by line, statement by statement, from top to bottom). You can think of a program as the book in our story.
The main() Method in C:
Like any book that has the beginning page and we read from that starting point, a program has an entry as well and CPU starts from there.
In C programming, this entry point is the `main()` function.
At runtime when our program is in the memory and is about to be run, the CPU will figure out where the `main` function of our program is and start to read and execute line-by-line instructions in the body of the `main` function.
The execution of instructions in a program is statement by statement from top to bottom. (Just like when you read a book, you don’t jump from page one to page 50 and then back to page 2 and then randomly choose another page! The usual and accepted way is to follow the book page by page like 1, 2, 3, 4, 5…. This is true for the execution of the instructions within the body of a program as well.)
Example: order of execution in C
#include <stdio.h>
int main() {
int a = 10 ;
int b = 20;
int c = 30 ;
int d = 40;
int result = (a+b) * d; // (10+20) * 40
return 0;
}
If we compile and run the example above, CPU will start from the `main` function (this is the entry point as mentioned above) and from there the first line of instruction for the CPU will be to create a variable named `a` and then assign the value 10 to this variable.
Then the next line is to create the variable `b` and assign the value 20 to this variable.
The next two lines are also to create variables `c` and `d` and assign those values mentioned in the program to them.
Note: when we say a line of instruction, it doesn’t mean if a program has 10 lines, then there’re 10 instructions in that program!
For example, if we had:
#include <stdio.h>
int main() {
int a = 10 ;int b = 20;int c = 30 ;int d = 40;
int result = (a+b) * d; // (10+20) * 40
return 0;
}
The part ` int a = 10 ;int b = 20;int c = 30 ;int d = 40;` is 4 separate statements for the CPU to run!
Also, if we had a line of instruction like:
int a = 10 ;
This is still considered one line of instruction even though it took 5 editor’s line!
Basically, semicolon is one factor of separating lines of instructions from each other.
Alright, moving on to the next line of instruction in our example, we have ` int result = (a+b) * d;`.
Here, in this line, the CPU will first create the variable `result` and then calculate and assign the result of the `(a+b) * d;` expression to this variable.
Moving on to the next line, we see the `return 0; ` which means the function is at its end and the CPU can finish running this program by returning the value 0 to the operating-system.
This last line is like the person of our story when he reached the end of a book and by seeing the end cover of the book, he knows that the book is finished and there’s nothing to read anymore.
Before moving on to a more advanced example, we should talk about memory as well:
Our program at first is stored in the hard-disk (the one that keeps data no-matter if the computer is on or off).
When we want to run a program, that program is moved from the hard-disk to the memory (RAM) in order to be run by the CPU.
Back to our book reading story at the beginning of this section, you can think of the hard-disk as a big library in your house and the memory (RAM) as the table where you can bring books (programs) taken from the library and start to read them.
This memory is divided into multiple segments, but the three sections that are related to this section are:
Data Memory
There’s a region in the memory that is called `data-memory` which is used to store those non-constant variables and data that are declared outside of any function.
Note: non-constant means the variable is able to get and change the value that is already in its memory-space. (Read the const section for more information)
Example: data memory in C
#include <stdio.h>
int simpleNumber = 1000;
int sum (int , int);
int main() {
int a = 10 ;
int b = 20;
return 0;
}
int sum(int valueOne , int valueTwo){
return valueOne + valueTwo;
}
In this example, we have the variable named `simpleNumber` with the value assigned 1000.
This variable is declared outside of any function and basically is considered living in the `data` region of the memory.
The main difference between this `data` region compared to the `stack` memory is the fact that any data live inside `data-section`, will stay here as long as the program is running.
C Stack Memory
Stack is a region of the memory that a function takes place when it is called to run. Think about it this way: when we want to read a book, we bring that book to the table and start reading it. The place where we put the book on our table is called the stack.
Why they call it stack? As mentioned in function section, functions are capable of calling other functions within their body. Calling another function is like reading a book and finding a reference book that needs to be checked and read before continuing with the current book. We mentioned that we bring the second book on top of the first book and start to read it, right?
Same thing happens here in programming: when one of the lines of instructions in the body of a function is to call another function, the second function runs on top of the first function and as long as the second function is running, the first function is stopped and is waiting for the second function to finish in order to get a chance of executing the rest of instructions within its body.
Now the reason that we call it stack is that of its similarity to an actual stack! Basically, a `caller function` goes under the `called function` and will stay there until the `called function` gets finished and leave off the stack.
C Stack Memory Notes:
- When a running function like the `main` function is calling another function, that second function will take its own space in the stack-memory and it’s not like it’ll replace the space of the first function! But when that second function finished its work, the function will be destroyed and its allocated memory will be released as well.
- This is why if we declare a local variable inside a function, this variable will be alive as long as the called function is running. But the moment the function finished its work and returned to the `caller function`, its memory space is taken back and so the local variables and data will be cleared from the stack.
- The amount of space that is given to each function when they are called is limited and it is system dependent. This means we can’t store a large amount of data in the stack-memory!
Example: Stack memory in C
#include <stdio.h>
int sum(int , int);
int main() {
int a = 10 ;
int b = 20;
int result = sum (a, b);
printf ("The result is: %d\n", result);
return 0;
}
int sum (int valueOne , int valueTwo){
return valueOne + valueTwo;
}
Output:
The result is: 30
In the example above, the CPU will start by running the instructions in the `main` function.
Note: just like any other functions that a memory space in the stack will be allocated for them, the `main` function is the first function that a portion of the memory space in the stack will be set aside for it. Also, just like other functions that their memory space in the stack will be gone when their instructions finished, the `main` function will also get destroyed when its instructions finished (which, in that case, the program itself is finished as well).
Now back to our program, the first two lines of instructions in the example above is to declare two variables named `a` and `b` and then assign the values 10 and 20 to these variables, respectively.
On the third line of instructions, things get more interesting!
First, the instruction is to declare a variable named `result`. So this variable will be declared and then it’s time to run the assignment part of this statement.
The instruction here is to call another function named `sum` function.
This is like we are at some page of a book and then we face a reference that is needed to be read first in order to be able to continue with the rest of the first book.
So what happens here is that the first function `main` will stop executing the rest of its instructions by the CPU and the CPU will start to run the instructions within the body of the `sum()` function.
Note: before this function gets the chance of running, part of the memory in the stack will be allocated to this function and every local variable and their values in this function will be stored in the allocated stack. (`int valueOne` and `int valueTwo` are the two variables that are considered being the local variable of the `sum` function).
When we called the `sum` function in the body of `main` function, we put two arguments to the function as well. As explained in the function section, these arguments will be the values to be assigned to each parameter of the function. So now the `valueOne` variable has the value 10 and `valueTwo` variable has the value 20.
Now the `sum` function is on top of the stack and its instructions is about to run while the `main` function is waiting for this function to finish its instruction execution.
Within the body of the `sum` function there’s only one statement to be executed and that is returning the result of `valueOne + valueTwo` expression to the `caller function` which in this example, it would be the `main` function.
The result is 30 and this value is returned to the `main` function and is assigned to the `result` variable.
At this moment, the memory space assigned to the `sum` function is taken back and the function no-longer exists in the stack.
Moving on in the `main` function, we have the next line, which is calling the `printf` function by assigning a set of arguments for it.
By calling the `printf` function a new memory space will be allocated to this function in the stack and basically the `main` function has to wait again until the instructions within the body of the `printf` function get finished.
Note: you can learn more about the `printf` in the printf-function section.
After the `printf` function finished its work, the stack space allocated to this function is taken back and that means the function and its local variables and data will no-longer exist.
So now the CPU will keep running the next instruction within the body of the `main` function, which in this case is nothing but the `return 0; ` statement which is equal to the end of the `main` function and the program itself.
At this stage, the `main` function reaches to its end and the memory space allocated to this function in the stack will be taken back by the OS (operating system) and of course, this is equal to the end of our program.
Heap in Programming
This region of the memory is larger compared to the `stack` and the `data-memory`. Also, in order to allocate a portion of this memory-space to a variable in the program, we use two functions: `malloc` and `calloc`.
You should know that unless we explicitly release a memory space that is allocated from this area to a variable, this memory space will be attached to the program for as long as the program is running.
Note: we use the `free()` function to release such memory space when it’s no-longer needed.
The memory space that is allocated from this area is called dynamic-memory because at anytime during a program’s execution, we can take a portion of the memory of this `heap-area` and release it when we no-longer need it.
Note: we will continue the discussion of the Heap memory in the `malloc` and `calloc` sections.
