Functions with heap and stack

Disclaimer: This presentation is prepared by trainees of
baabtra as a part of mentoring program. This is not official
document of baabtra –Mentoring Partner
Baabtra-Mentoring Partner is the mentoring division of baabte System Technologies Pvt .
Ltd

Functions with heap and
stack
Jaseena A P
jsnp65@gmail.com
www.facebook.com/Jaseena
Muhammed A P
twitter.com/username
in.linkedin.com/in/profilena
me
9539443588

WHAT IS THE STACK?
The stack is a LIFO structure similar to packing items
in a box
•The last item placed into the box is the first item removed from the
box.
•However, the stack –like the box –has a fixed size and should NOT be
overflowed.
PUSH
POP

WHAT IS THE HEAP?
 A heap is a binary tree T that stores a key-element
pairs at its internal nodes
 It satisfies two properties:
• MinHeap: key(parent)  key(child)
• [OR MaxHeap: key(parent) ≥ key(child)]
• all levels are full, except the last one,
which is left-filled

4
6
207
811
5
9
1214
15
2516
WHAT IS THE HEAP?(contd..)
EXAMPLE FOR A MIN HEAP

MEMORY
What is memory?
Huge linear array of storage
How is memory divided?
Kernel space and user space
Who manages memory?
OS assigns memory to processes
Processes manage the memory they’ve been assigned

MEMORY ALLOCATION
 Memory allocation is a process by which computer programs
and services are assigned with physical or virtual memory space.
 Memory allocation is primarily a computer hardware operation
but is managed through operating system and software
applications.
 Programs and services are assigned with a specific memory as
per their requirements when they are executed. Once the
program has finished its operation or is idle, the memory is
released and allocated to another program or merged within the
primary memory.

ALLOCATION WITH STACK
When we have a declaration of the form “int a;”:
 a variable with identifier “a” and some memory allocated to it is
created in the stack. The attributes of “a” are:
• Name: a
• Data type: int
• Scope: visible only inside the function it is defined, disappears once
we exit the function
• Address: address of the memory location reserved for it.
Note: Memory is allocated in the stack for a even before it is
initialized.
• Size: typically 2 bytes
• Value: Will be set once the variable is initialized

Since the memory allocated for the variable is set in
the beginning itself, we cannot use the stack in
cases where the amount of memory required is not
known in advance. This motivates the need for
HEAP
ALLOCATION WITH STACK(CONTD..)

 The stack is a fixed block of memory, divided into two parts:
•Allocated memory used by the function that called the current
function, and the function called it etc.
•Free memory that can be allocated
 The borderline between the two areas is called the top of
stack and is represented by the stack pointer (SP), which is a
dedicated processor register
 Memory is allocated on the stack by moving the stack
pointer

 very fast access

 The main advantage of the stack is that functions in
different parts of the program can use the same
memory space to store their data
 Unlike a heap, a stack will never become fragmented
or suffer from memory leaks
 It is possible for a function to call itself—a recursive
function—and each invocation can store its own data
on the stack

AN EXAMPLE
#include<stdio.h>
int factor(int );
void main()
{
int n,fact;
printf("Enter the numbern");
scanf("%d",&n);
fact=factor(n);
printf("Facorial is %d",fact);
}
int factor(int n)
{
int fct;
if(n==0)
fct=1;
else
fct=n*factor(n-1);
return fct;
}
Suppose n=4
Main()
n-2 bytes
Fact-2bytes
Factor(4)
fct-2bytes
Factor(3)
Factor(2)
Factor(1)
Factor(0)
fct-2bytes
fct-2bytes
fct-2bytes
fct-2bytes
Order of de-allocation

PROBLEMS WITH STACK
 The way the stack works makes it impossible to store
data that is supposed to live after the function returns.
The following function demonstrates a common
programming mistake. It returns a pointer to the variable
x, a variable that ceases to exist when the function
returns:
int*MyFunction()
{
intx;
/* Do something here. */
return &x; /* Incorrect */
}

PROBLEMS WITH STACK(contd..)
Another problem is the risk of running out of stack. This
will happen when one function calls another, which in
turn calls a third, etc., and the sum of the stack usage of
each function is larger than the size of the stack.
(STACK OVERFLOW)
•The risk is higher if large data objects are stored on
the stack, or when recursive functions are stored.

AN EXAMPLE
#include<stdio.h>
int factor(int );
void main()
{
int n,fact;
printf("Enter the numbern");
scanf("%d",&n);
fact=factor(n);
printf("Facorial is %d",fact);
}
int factor(int n)
{
int fct;
fct=n*factor(n-1);
return fct;
}
Main()-4 bytesSuppose n=4
Factor(4)-2 bytes
Factor(3)-2 bytes
Factor(2)-2 bytes
Factor(1)-2 bytes
Factor(0)-2 bytes
Factor(-1)-2 bytes
STACK OVERFLOW!!!
16bytes

PROBLEMS WITH STACK(contd..)
If the given stack size is too large, RAM will be wasted
If the given stack size is too small, two things can
happen, depending on where in memory ,the stack is
located:
•Variable storage will be overwritten, leading to undefined
behavior.
•The stack will fall outside of the memory area, leading to an
abnormal termination.

ALLOCATION WITH HEAP
•The heap is an area of memory reserved for dynamic
memory allocation
•When an application needs to use a certain amount of
memory temporarily it can allocate, or borrow, this
memory from the heap by calling the malloc( ) function in C
or by using the 'new' operator in C++
•When this memory is no longer needed it can be freed up
by calling free( ) or by using the delete operator. Once the
memory is freed it can reused by future allocations

ALLOCATION WITH HEAP(contd..)
•Variables can be accessed globally
•No limit on memory size
•(Relatively) slower access
•No guaranteed efficient use of space, memory may become fragmented
over time as blocks of memory are allocated, then freed
•Programmer must manage memory (he/she is in charge of allocating
and freeing variables)
•Variables can be resized using realloc()

AN EXAMPLE
#include <stdio.h>
int *sum(int *a,int *b)
{
int *c=malloc(sizeof(int));
/*find the sum here*/
return c;//return the sum
}
Void main()
{
int *x=malloc(sizeof(int));
int *y=malloc(sizeof(int));
int *z=malloc(sizeof(int));
/*read x and y*/
z=sum(x,y);
/*print the sum*/
free(x);
free(y);
free(z);
}

POTENTIAL PROBLEMS(contd..)
 Most common problems with dynamic memory
allocation occurs when blocks of memory of varying
size are frequently allocated and freed.
•When memory is freed, there will be a memory hole
•This can be a problem if the next allocation is larger than any of the
available hole.
•This can lead to difficulties in debugging since the total amount of
free space on the heap may be sufficient for a desired allocation but
allocation may fail since the free space is not contiguous.

POTENTIAL PROBLEMS(contd…)
7 bytes
12 bytes

STACK VS HEAP MEMORY ALLOCATION
STACK HEAP
Very fast access (Relatively) slower access
Don't have to explicitly de-allocate variables Explicit de-allocation is needed.
Space is managed efficiently by OS, memory
will not become fragmented
No guaranteed efficient use of space,
memory may become fragmented over time
as blocks of memory are allocated, then
freed
Local variables only Variables can be accessed globally
Limit on stack size (OS-dependent) No limit on memory size
Variables cannot be resized variables can be resized using realloc()

If this presentation helped you, please visit our
page facebook.com/baabtra and like it.
Thanks in advance.
www.baabtra.com | www.massbaab.com |www.baabte.com

Contact Us
Emarald Mall (Big Bazar Building)
Mavoor Road, Kozhikode,
Kerala, India.
Ph: + 91 – 495 40 25 550
NC Complex, Near Bus Stand
Mukkam, Kozhikode,
Kerala, India.
Ph: + 91 – 495 40 25 550
Start up Village
Eranakulam,
Kerala, India.
Email: info@baabtra.com

Functions with heap and stack

Recommended

More Related Content

What's hot (20)

Similar to Functions with heap and stack (20)

More from baabtra.com - No. 1 supplier of quality freshers (20)

Recently uploaded (20)

Functions with heap and stack