Chapter 8
Heap Memory
8.1 Creating Array with malloc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
8.2 The Stack and the Heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
8.3 Functions that Return a Heap Address . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
8.4 Two-Dimensional Arrays in C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
8.5 Pointers and Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
Chapter 2 describes one type of memory: stack memory (also called the call stack). Stack
memory follows a simple rule: first in, last out. The call stack is automatically managed by
the code generated by the compiler. Every time a function is called, a new frame is pushed.
Every time a function ends, the frame is popped. Programmers have no direct control
over this process. One consequence is that a function may read from or write to memory
addresses in lower frames; however, a function can never “look upward” into memory above
its frame. This is because whenever a function is actively executing, there are not valid
memory addresses “above” it.
This is natural and convenient for a lot of programming tasks; however, sometimes
programmers need more control over memory. They want to be able to allocate memory
when necessary and release memory when the allocated memory is no longer needed. For
this purpose, computers have another type of memory: heap memory.
Computers also have the third type of memory where the compiled code resides. In
general, this memory cannot be modified. Programs can access only stack memory and
heap memory. Thus, the rest of this book does not explain the memory where programs are
stored.
8.1 Creating Array with malloc
If a called function can access the frame of the calling (lower) function through pointers,
would this be sufficient? No. At the bottom of the call stack is the frame of the main
function. Can a program store all of its data in the main function, since this data can be
accessed by all the other functions? This would make the main function rather complex for
even a simple program. We would need to consider every possible way the data could be
read or written and the main would have to manage space for all of the data. Even if we
are willing to do this analysis and write this main function, we still have problems. Most
programs take some form of input. For example, we may need to read an image file from a
disk. At the time the code is being written, we cannot know precisely what input will be
given to the program. In particular, we do not know the size of the input. We cannot write
a program that can handle the inputs whose size is greater than our expectation. This is
a severe limitation. We could create an array in main and make its size greater than all
113
114 Intermediate C Programming
possible input size. This is very inefficient. What we need is a way to allocate memory as
needed while the program is running.
Before talking about how to use heap memory, let’s review how to create a fixed-size
array. The following example creates an array of six integers and assigns the first three
elements to 11, −29, and 74.
int arr1 [6];1
arr1 [0] = 11;2
arr1 [1] = -29;3
arr1 [2] = 74;4
This array is stored inside a frame in the call stack. The values of the other three elements
(arr[3], arr[4], and arr[5]) are still garbage. To create a fixed-size array, the array’s size
must be specified in the source code. This is problematic because the size may be unknown
at the time the code is written. For example,
int num ;1
printf (" Please enter a number : ") ;2
scanf (" %d" , & num ) ;3
Note that the number is given after the program starts running. We can use this number
to create an integer array with num elements. The program uses malloc to create the array:
int * arr2 ;1
arr2 = malloc ( num * s i z e o f ( in t ) ); // no * inside sizeof2
Notice * in front of arr2. The value of num is entered by a user. To create an array
of integers, an integer pointer is needed. This allocation must use sizeof(int) because
the size of an integer can be different on different machines. If sizeof(int) is 4 (typical
among computers), then the program allocates num * 4 bytes of memory. If sizeof(int)
is 2 (common in some types of micro controller), then the program allocates num * 2 bytes
of memory. The type of the pointer must match what is in sizeof(...). The following
example has mistakes.
int * arr3 ;1
arr3 = malloc ( length * s i z e o f ( char )); /* WRONG */2
/* types do not match , one is int , the other is char */3
int * arr4 ;4
arr4 = malloc ( length * s i z e o f ( double)); /* WRONG */5
/* types do not match , one is int , the other is double */6
The program will behave strangely when types do not match. Programs should check
whether malloc succeeds. If it fails, then it is NULL. Programs should handle this prob-
lem before doing anything else. Why would malloc fail? This happens when the system
cannot provide the requested memory. Perhaps the request is unreasonably large. C uses
NULL to indicate an invalid value for a memory address.
int * arr5 ;1
arr5 = malloc ( length * s i z e o f ( in t ) );2
i f ( arr5 == NULL )3
{4
// malloc has failed , handle the problem here .5
}6
If a program allocates memory successfully, then the program can assign values to the
elements in the same way as an array:
Heap Memory 115
arr2 [0] = 11;3
arr2 [1] = -29;4
arr2 [2] = 74;5
When using malloc to allocate an array, the memory addresses of the elements are
contiguous. When the memory is no longer needed, the program must release (also called
free) the memory by calling:
free ( arr2 ) ;6
It is impossible to release only one part of the memory. All the memory allocated in a given
call to malloc must be freed at once. One common mistake is assuming that arr2’s value
becomes NULL. This is wrong. The value of arr2 is still a memory address but that address
is no longer valid. It is a good habit to type free right after typing malloc so that it is not
forgotten. After typing malloc and free next to each other, insert code between them:
int * an_array = malloc ( s o me_size * s i z e o f ( i nt )) ;1
/* insert code here to use the array */2
free ( an_array );3
To use malloc, it is necessary to specify the number of elements in the array. When
using free, you cannot specify the number of elements. The malloc and free function
work together, and free knows how much memory should be freed. If a program calls
malloc without calling free, then the program has a memory leak. Memory leaks are
serious problems because a program has a limited amount of memory that can be allocated
by calling malloc. The limit depends on the hardware and also the operating systems. Later
in this chapter, we will explain how to use valgrind to detect memory leaks.
8.2 The Stack and the Heap
When a program declares a pointer, the pointer exists somewhere in the call stack. For
example,
int * arr2 ;1
Symbol Address Value
arr2 200 ?
The address is arbitrarily chosen to be 200. If you prefer, you can choose 400, 5000,
or whatever number. Even though the pointer is on the stack, we can create an array on
the heap. Remember that the pointer’s address and value are independent. This example
allocates memory for an array of 6 integers. This is how to create the array on the heap:
arr2 = malloc (6 * s i z e o f ( in t ) );2
Section 4.8 mentioned that different types have different sizes. That is the reason why
malloc is used in conjunction with sizeof. From now on, let us assume that each integer
requires 4 bytes and the addresses of two adjacent array elements is different by 4. Calling
malloc returns a valid heap address to a piece of memory large enough to store 6 integers,
and arr2’s value stores that address. Heap memory is pretty far away from the stack
memory. In this example, we use 10000 for the heap address. The memory is uninitialized,
so we use “?” for each integer’s value.
116 Intermediate C Programming
Symbol Address Value Address Value
arr2 200 10000 10020 ?
10016 ?
10012 ?
10008 ?
10004 ?
10000 ?
(a) Stack Memory (b) Heap Memory
The following assignment changes the first element of the array:
arr2 [0] = 11;3
This causes the heap memory at 10000 to change:
Symbol Address Value Address Value
arr2 200 10000 10020 ?
10016 ?
10012 ?
10008 ?
10004 ?
10000 11
(a) Stack Memory (b) Heap Memory
arr2 [2] = 74;4
This changes the heap memory at 10008:
Symbol Address Value Address Value
arr2 200 10000 10020 ?
10016 ?
10012 ?
10008 74
10004 ?
10000 11
(a) Stack Memory (b) Heap Memory
How does this work? What happens when the program executes this line?
arr2 [2] = 74;4
This is what this statement does precisely:
1. Takes arr2’s value as an address. In this example the value is 10000.
2. The index is 2, so sizeof(int) × 2 = 4 × 2 = 8 is added to 10000 and the new
address is 10008.
3. Since this is at the left of the assignment, the value at the address of 10008 is changed
to 74.
The following example creates an array whose length is determined by argc. The pro-
gram converts the command line arguments—the elements of argv—into integers. This is
necessary because each element of argv is a string. Then, the program adds up the integers’
values and prints the sum.
Heap Memory 117
// malloc . c1
// create an array whose size is s pecified at run time .2
// The array ’s elements are the command line arguments .3
// The program adds the element s and prints the sum .4
#in clude < stdio .h >5
#in clude < stdlib .h >6
int main ( i n t argc , char * argv [])7
{8
int * arr2 ;9
int iter ;10
int sum = 0;11
i f ( argc < 2)12
{13
printf (" Need to provide some integers . n ");14
return EXIT _FAILUR E ;15
}16
arr2 = malloc ( argc * s i z e o f ( i n t ) );17
i f ( arr2 == NULL )18
{19
printf (" malloc fails . n") ;20
return EXIT _FAILUR E ;21
}22
/* iter starts at 1 because argv [0] is the program ’s name */23
for ( iter = 1; iter < argc ; iter ++)24
{25
arr2 [ iter ] = ( in t ) strtol ( argv [ iter ] , NULL , 10) ;26
}27
printf (" The sum of " );28
for ( iter = 1; iter < argc ; iter ++)29
{30
printf (" %d ", arr2 [ iter ]) ;31
sum += arr2 [ iter ];32
}33
printf (" is %d . n" , sum );34
35
free ( arr2 );36
return EXIT _SUCCES S ;37
}38
The program uses strtol to convert the strings into integers. Some books suggest using
atoi but strtol is preferred for two reasons: (i) strtol is more general because it is not
limited to decimal bases. For example, strtol can be used to convert binary numbers, or
hexadecimal (base 16) numbers. (ii) More important, strtol allows the calling program to
check whether the conversion fails. The conversion fails when the string contains no number.
In contrast, atoi provides no information about whether the conversion fails. Use gcc to
convert the program into an executable file called malloc:
$ gcc -Wall -Wshadow malloc.c -o malloc
The following shows two examples running this program. If an argument is not an integer
(“hello” and “C” in the second example), then the value of that argument is zero.
$ ./malloc 5 8 −11 4 3 27
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.