Module 11 – Dynamic Memory

Allocation
BITS Pilani Dr. Pratik Narang & Dr. Jagat Sesh Challa
Pilani Campus
Department of Computer Science & Information Systems
Module Overview

• Stack vs Heap memory

• Dynamic Memory Allocation
• Dynamically allocated arrays
• Memory Management Issues
• Dynamically Allocated Arrays of Structures
• Multi-dimensional arrays using dynamic allocation
• Command Line Arguments

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
 BITS Pilani
Pilani Campus

Stack vs Heap Memory

Welcome back our block
diagram!
• OS loads the
program executable
into the RAM
• Executes it line by
line on CPU

A line Program
from exe Program Executable (P1)
(exe)
Program is Compiled
executed Executable
Program of P1 (exe)
on CPU
CPU Executable gets
line by line
loaded into the
RAM

Memory (RAM) DISK

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Looking at the main memory
only

Note: we
have flipped
Space our memory
allocated layout
to the our
program

Deeper view of space allocated to our program

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Simplifying the layout of memory
allocated to our program

This is stack memory

This is heap memory

For simplicity, now on consider that we have only

TWO PARTITIONS of the memory allocated to our
program – STACK and HEAP
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Stack vs Heap
Stack:
• One frame allocated to each function call
• Auto (or local) variable defined inside the frame allocated for a
function
• Memory allocated to each frame is recalled after the function
execution finishes

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
 Illustrating stack memory
Stack When f1() returns, the
arr
memory allocated memory allocated to it is
1 2 3 4 recalled/erased.
to f1() in stack
So arr declared inside
memory allocated f1() does not exist
to main() in stack anymore. Accessing arr
in main function now
gives a run-time error.
Consider this program:
int f1(){
Heap int arr[4] = {1, 2, 3, 4};
return arr;}
uninitialized data segment
int main(){
int main_arr[] = f1();
printf(”First ele is: %d”, main_arr[0]);
return 0;}
text segment We can solve this if the array gets
Output:
memory allocated in the heap using
Memory allocated to our program seg fault dynamic memory allocation!
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Advantage of Heap over Stack
Stack:
• One frame allocated to each function calls
• Auto (or local) variable defined inside the frame allocated for
a function
• Storage allocated for each frame is recalled after the function
execution finishes

Heap:
• Heap is dynamically and explicitly allocated by programmer
• So allocated storage is not recovered on function return
• Programmer has to deallocate (at his/her convenience)
The memory allocated in heap is accessible globally to all functions

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
 BITS Pilani
Pilani Campus

Dynamic Memory Allocation

Motivation
• Limitation of Arrays
– Amount of memory is fixed at compile time and cannot be modified.
• We tend to oversize Arrays to accommodate our needs.
– We can’t return an array from a function as the memory allocated to
the function gets destroyed on return.
Using malloc()
• Solution: and calloc()
– Allocate memory dynamically at run time. Using
• The size of the array can be taken as user input realloc()

• We can re-allocate the size of the array of it gets full

– Array gets memory in heap, hence can be accessed by all functions
of the program
Using free()
• Flexibility comes with a price:
– Programmer should free up memory when no longer required.
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Allocating memory
dynamically – malloc(): Syntax
<stdlib.h> is the header
file for using malloc() and
other dynamic memory
allocation related operations

#include <stdlib.h>
Convert pointer to byte(s) (generic pointer)
void fun1() to the type pointer to int
{

int * pt = (int *) malloc (sizeof(int));

}

Ask Operating System to Number of bytes of memory

allocate memory required

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Creating a dynamically
allocated array

#include <stdlib.h>
#define MAX_SIZE 10
void fun2()
{

int * arr = (int *) malloc( MAX_SIZE * sizeof(int));

}

Number of bytes of memory

required

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
malloc()
Observations:
– Library stdlib provides a function malloc
– malloc accepts number of bytes and returns a pointer to a block of
memory
– Returned pointer must be “type-cast” (i.e. type converted) to required
type before use.
– malloc doesn’t initialize allocated blocks, each byte has a random
value.
– The block of memory returned by malloc is allocated in heap
Reading between the lines:
– Number of bytes is dynamic – unlike in arrays where size is constant.
– Can number of bytes be arbitrary?
• No! Memory is of finite and fixed size!

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Example
short * p1;
Pointer variable
int * p2; declaration
float * p3;

p1 = (short*) malloc(sizeof(short)); Allocating

p2 = (int*) malloc(sizeof(int)); memory to
p3 = (float*) malloc(sizeof(float)); pointer variable

*p1=256;
*p2=100; Assigning values
*p3=2.654;

printf(“p1 is %hd\n”, *p1);

printf(“p2 is %d\n”, *p2);
printf(“p3 is %f\n”, *p3)
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
 BITS Pilani
Pilani Campus

Dynamically Allocated Arrays

Dynamically Allocated Arrays
Given pi
int *pi;
pi = (int *) malloc(N*sizeof(int));

Where does storage get allocated?

Not inside frames i.e., not inside call stack
But inside the heap

NOTE:
 Usage syntax is same for static array locations and
dynamically allocated locations.
 In both cases pointers are used internally.
 Only difference is: static allocation vs. dynamic allocation
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
 Example
#include <stdio.h>
• This is not copying of array p into q.
#include <stdlib.h>
• This means that the address
int main() {
int *p,*q,i; contained in p is copied into q.
• Which means that now q also points
p = (int*) malloc(5*sizeof(int)); to first location of the array p.

q = p; // assigning array p to q

for (i=0;i<5;i++)
*p++ = i*i;
Both are equivalent
for(i=0;i<5;i++)
printf("Element at index %d is %d\n",i,q[i]);

// for(i=0;i<5;i++)
// printf("Element at index %d is %d\n",i,*(q + i));
}

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Dynamically Allocated Arrays
• We saw that arrays created inside a function could not be
returned.
– Since, arrays declared within a function are allocated in a
frame and they are gone when function returns.
• Solutions:
– Declare array outside function (in some other function) and
pass as parameter (only starting address is passed)
• Passed by reference, so changes get reflected in the calling
function.
– Or declare a pointer inside the function, allocate memory
and return the pointer.
• Since, memory is allocated in the heap, it will remain in the
calling function as well.
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
 Example: copy arrays - 1
The following program calls a function copy(), that copies the contents
of one array into another.
#include <stdio.h> int main()
#include <stdlib.h> {
int a[5] = {1,2,3,4,5};
void copy(int c[], int n, int d[]) int b[5];
{
for (int i=0; i<n; i++) copy(a,5,b);
{
d[i]=c[i]; for(int i=0;i<5;i++)
// or *(b+i)=*(a+i); {
} printf("%d\t",b[i]);
} }

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Example: copy arrays – 2
(using pointers)
#include <stdio.h>
#include <stdlib.h> Can be replaced with
int * a
int * copy(int a[], int n)
{
int * b = (int*) malloc(sizeof(int)*n);
for (int i=0; i<n; i++)
{
b[i]=a[i]; int main(){
// or *(b+i)=*(a+i); int a[5] = {1,2,3,4,5};
} int * b;
return b;
} b = copy(a,5);

for(int i=0;i<5;i++){
printf("%d\t",b[i]);
}
}
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
 Example: copy arrays – that is
incorrect (using pointers)
Solution:
#include <stdio.h>
• Allocate memory to b in
#include <stdlib.h>
main()and then pass. Try This!
• Allocate memory inside
void copy(int * a, int n, int * c)
copy()and return. (last slide)
{
• Use double pointer! (we will see
c = (int*) malloc(sizeof(int)*n);
later)
for (int i=0; i<n; i++)
{
c[i]=a[i]; int main(){
} int a[5] = {1,2,3,4,5};
} int * b;
Will lead to segmentation fault (run-time error). Why?
The contents of b were copied into c during function copy(a,5,b);
call. b was empty (or garbage value) when it was
passed. The memory that was allocated in copy() for(int i=0;i<5;i++){
function, its first element’s address is copied to c during printf("%d\t",b[i]);
the malloc()call. But this was not copied to b, when }
copy()returned. }
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
calloc()
• calloc()is used specifically for arrays and structures.
• It is more intuitive than malloc().
• Example:

int *p = calloc (5, sizeof(int));

// 2 arguments in contrast to malloc()

• The bytes created by calloc() are initialized to 0.

Note:
• After malloc(), the block of memory allocated contains garbage
values.
• malloc() is faster than calloc()

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
realloc()
What if the allocated number of bytes run out?
– We can reallocate!
– Use “realloc” from stdlib

int * pt = (int *)
realloc(pt,2*MAX_SIZE*sizeof(int));

realloc() tries to
• Enlarge existing block
• Else, it creates a new block elsewhere and move existing data to
the new block. It returns the pointer to the newly created block
and frees the old block.
• If neither could be done, it returns a NULL.

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Example
int *p, *q, *r, i;
p = malloc(5*sizeof(int));
q = p;

for (i=0;i<5;i++)
*p++ = i;
p = q;

printf("Array address %p \n", p);

r = realloc(p, 10*sizeof(int));
printf("Relocated address %p\n", r);
for(i=0; i<5; i++)
printf("The elements are %d\n", r[i]);

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Example

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
free()
• Block of memory freed using free() is returned to
Code the heap
• Failure to free memory results in heap depletion.
– which means that malloc() or calloc()
Static Data can return NULL saying that no more memory is
left to be allocated.
• free() syntax:
Stack
int * p = malloc(5*sizeof(int));
…
Free Memory
free(p);

Heap Releases all 5*sizeof(int) bytes allocated

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
 BITS Pilani
Pilani Campus

Memory Management Issues

Memory Management Issues
Dangling Pointer:

#include <stdio.h>
#include <stdlib.h>
int main() {
int * p, *q, *r, i;
p = (int*) malloc(sizeof(int));
printf(“Address pointed by p = %p \n”, p);
free(p); // p becomes dangling pointer
printf(“Address pointed by p = %p \n”, p);
p = NULL;
printf(“Address pointed by p = %p \n”, p);
}

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Memory Management Issues
Memory Leaks: • p is made to point another memory block
without freeing the previous one.
• 1000*sizeof(int) bytes previously
allocated to p are now inaccessible.
• This is memory leak.

#include <stdio.h>
#include <stdlib.h>
int main() {
int * p, *q, *r, i;
p = (int*) malloc(1000*sizeof(int));
q = (int*) malloc(sizeof(int));
p = q;
} Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Memory Management Practices
In C programming it is the responsibility of the programmer to:
• keep freeing the allocated memory after its usage is over so
that malloc() and calloc() don’t fail.
• prevent memory leaks by careful programming practices
• Keep track of dangling pointers and re-use them.

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
 BITS Pilani
Pilani Campus

Dynamically Allocated Array of Structures

Dynamically allocated struct
variable and array of structures
struct stud {
int roll; Rest of the operations are the same as
structures and array of structures.
char dept_code[25]; Only difference is that we have dynamically
float cgpa; allocated memory in the heap.

} class, *ptr;

struct stud * s1 = (struct stud*) malloc(sizeof

(struct stud));

struct stud * studentArray = (struct stud*)

malloc(sizeof(struct stud)*100);

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
 BITS Pilani
Pilani Campus

Multi-dimensional Arrays using dynamic

memory allocation
Multi-dimensional arrays
2D arrays in stack memory:
#define NUM_ROWS 3 Notice the double
#define NUM_COLS 2 pointer
int arr2D[NUM_ROWS][NUM_COLS];

This array of 3 rows and 2 columns resides in stack and has all its problems that we
discussed earlier for 1D arrays

We can declare this array in heap dynamically at run-time by using a pointer to a

groups of pointers:

int ** arr2D = (int **) malloc(NUM_ROWS*sizeof(int*));

for (int i=0; i<NUM_ROWS; i++)
{
arr2D[i] = (int*) malloc(NUM_COLS*sizeof(int));
}
arr2D[1][2] = 10; // is a valid assignment

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
 2D Array
#define NUM_ROWS 3
#define NUM_COLS 2
int ** arr2D = (int **) malloc(NUM_ROWS*sizeof(int*));
…

arr2D

Each of this blocks if the type int

*, i.e., each can hold address of
an int variable or the address of
the first location of an int array

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
 2D Array (contd.)
…
for (int i=0; i<NUM_ROWS; i++)
{
arr2D[i] = (int*) malloc(NUM_COLS*sizeof(int));
}
arr2D

int arrays
of size
NUM_COLS
=2
Each of this blocks if the type int
*, i.e., each can hold address of
an int variable or the address of
the first location of an int array

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
 2D Array (variable size)
One can define each array of variable size as well
arr2D[0] = (int*) malloc(sizeof(int)); // single int variable
arr2D[0] = (int*) malloc(sizeof(int)*3); // int array of size 3
arr2D[0] = (int*) malloc(sizeof(int)*5); // int array of size 5

int
arr2D variable

int arrays
of size 3

This was not possible int arrays

with static arrays of size 5

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Static vs Dynamic Arrays
Arrays (static) are Pointers in C?
– Well, not exactly …
– Arrays cannot be reallocated (starting address and size are
fixed).
– Multi-dimensional arrays (static) are not pointers to pointers.
• They are contiguous memory locations

int a[3][3];

a a+1 a+2 a+3 a+4

a[0][0], a[0][1], a[0][2], a[1][0], a[1][1],
a+5 a+6 a+7 a+8
a[1][2], a[2][0], a[2][1], a[2][2]

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Practice Questions – use pointer
notation only
• Write a C program that computes the transpose of a 2D
array.

• Write a C program that receives a 2D array and sorts the

elements by accessing the 2D array as a 1D array.

• Write a C program that receives a 1D array and an element

as input. Delete the element if it is present in the array and
shift the position of the remaining elements. The array is intact
if the element is not found.
• Observe the number of shifting required for various
elements, when the array is (a) sorted (b) unsorted.

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Remember our incorrect copy
arrays function…
#include <stdio.h> Solution:
#include <stdlib.h> • Allocate memory to b in main()
and then pass. Try This!
void copy(int * a, int n, int * c) • Allocate memory inside copy()
{ and return. (last slide)
c = (int*) malloc(sizeof(int)*n); • Use double pointer!
for (int i=0; i<n; i++)
(we will see NOW)
{
c[i]=a[i]; int main(){
} int a[5] = {1,2,3,4,5};
} int * b;
Will lead to segmentation fault (run-time error). Why?
The contents of b were copied into c during function copy(a,5,b);
call. b was empty (or garbage value) when it was
passed. The memory that was allocated in copy() for(int i=0;i<5;i++){
function, its first element’s address is copied to c printf("%d\t",b[i]);
during the malloc() call. But this was not copied to b, }
when copy() returned. }
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Example: copy arrays – that is
incorrect (using pointers)
#include <stdio.h>
Use of double pointer
#include <stdlib.h>
enables us to not return
void copy(int c[], int n, int ** d) {
anything, yet change getting
*d = (int *) malloc(n*sizeof(int));
reflected in main(). This is call
for (int i=0; i<n; i++)
by reference for dynamically
{
allocated arrays
(*d)[i]=c[i];
}
}
int main(){
int a[5] = {1,2,3,4,5};
int ** b = (int **) malloc(sizeof(int *));

copy(a,5,b);

for(int i=0;i<5;i++){
printf("%d\t",(*b)[i]);
}
} Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
 BITS Pilani
Pilani Campus

Command Line Arguments

 Command Line Arguments
#include <stdio.h>  gcc echo.c –o echoTest
/* echo */
int main(int argc, char **argv)  ./echoTest How do you do?
{  How do you do?
// argc – number of arguments passed • Observe that we printing argv[j]
// argv[0] is the name of the from j=1
(command) file being executed
• argv[0] refers to the name of
for (j=1; j < argc; j++) the executable (in this case
printf(“%s ”, argv[j]); “echoTest”).
return 0; • Each other argv[j] refers to one
word (separated by blank
spaces) of command line
} argument.
• argc has the count of arguments

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Example 1
int main(int argc, char *argv[]) Notice the change
{
printf(“Number of arguments: %d \n", argc);
int i = 0;
while(i < argc){
printf("Argument %d: %s \n",i, argv[i]);
i++;
}
return 0;
}

Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Example 2
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
int a, b, c;

a = atoi(argv[1]);
b = atoi(argv[2]);
c = atoi(argv[3]);

printf("\n %d",a+b+c);
return 0;
}
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
BITS Pilani
Pilani Campus