Absolute beginners to C aren’t the only ones who might, at first, find this chapter’s concepts confusing. Even advanced C programmers get mixed up when dealing with the heap. The heap is the collection of unused memory in your computer. The memory left over—after your program, your program’s variables, and your operating system’s workspace—comprises your computer’s available heap space, as Figure 26.1 shows.
Figure 26.1. The heap is unused memory.
There will be many times when you’ll want access to the heap because there will be times when your program will need more memory than you initially defined in variables and arrays. This chapter gives you some insight into why and how you would want to use heap memory instead of variables.
You don’t assign variable names to heap memory. The only way to access data stored in heap memory is through pointer variables. Aren’t you glad you learned about pointers already? Without pointers, you couldn’t learn about the heap.
The free heap memory is called free heap or unallocated heap memory. The part of the heap in use by your program at any one time is called the allocated heap. Your program might use varying amounts of heap space as the program executes. So far, no program in this book used the heap.
Now that you’ve learned what the heap is—the unused section of contiguous memory—throw out what you’ve learned! You’ll more quickly grasp how to use the heap if you think of the heap as just one big heap of free memory stacked up in a pile. The next paragraph explains why.
You’ll be allocating (using) and deallocating (freeing back up) heap memory as your program runs. When you request heap memory, you don’t know exactly from where on the heap the new memory will come. Therefore, if one statement in your program grabs heap memory, and then the very next statement also grabs another section of heap memory, that second section of the heap may not physically reside right after the first section you allocated.
Just like scooping dirt from a big heap, one shovel does not pick up dirt granules that were right below of the last shovel of dirt. Also, when you throw the shovel of dirt back on the heap, that dirt doesn’t go right back to where it was. Although this analogy might seem to stretch the concept of computer memory, you’ll find that you’ll understand the heap much better if you think of the heap of memory like you think of the heap of dirt: You have no idea exactly where the memory you allocate and deallocate will come from or go back to. You know only that the memory comes and goes from the heap.
If you allocate 10 bytes of heap memory at once, those 10 bytes will be contiguous. The important thing to know is that the next section of heap memory you allocate will not necessarily follow the first, so you shouldn’t count on anything like that.
Your operating system uses heap memory along with your program. If you work on a networked computer, or use a multitasking operating environment such as Windows, other tasks may be grabbing heap memory along with your program. Therefore, another routine may have come in between two of your heap-allocation statements and allocated or deallocated memory.
You will have to keep track of the memory you allocate. You do this with pointer variables. For instance, if you want to allocate 20 integers on the heap, you’ll use an integer pointer. If you want to allocate 400 floating-point values on the heap, you’ll use a floating-point pointer. The pointer will always point to the first heap value of the section you just allocated. Therefore, a single pointer points to the start of the section of heap you allocate. If you want to access the memory after the first value on the heap, you can use pointer notation or array notation to get to the rest of the heap section you allocated. (See, the last chapter’s pointer/array discussion really does come in handy!)
Okay, before learning exactly how you allocate and deallocate heap memory, you probably want more rationalization about why you even need to worry about the heap. After all, the variables, pointers, and arrays you’ve learned about so far have sufficed nicely for program data.
The heap memory will not always replace the variables and arrays you’ve been learning about. The problem with the variables you’ve learned about so far is that you must know in advance exactly what kind and how many variables you will want. Remember, you must define all variables before you use them. If you define an array to hold 100 customer IDs, but the user has 101 customers to enter, your program can’t just expand the array at runtime. Some programmer (like you) has to change the array definition and recompile the program before the array can hold more values.
With the heap memory, however, you don’t have to know in advance how much memory is needed. Like an accordion, the heap memory your program uses can grow or shrink as needed. If you need another 100 elements to hold a new batch of customers, your program can allocate that new batch at runtime without needing another compilation.
This book won’t try to fool you into thinking all your questions will be answered in this chapter. Mastering the heap takes practice and, in reality, programs that really need the heap are beyond the scope of this book. Nevertheless, when you finish this chapter, you’ll have a more solid understanding of how to access the heap than you would get from most books because of the approach that’s used. (Perilous Perry might take you on a rough journey, but he’ll always get you back safely!)
Commercial programs such as spreadsheets and word processors must rely heavily on the heap. After all, the programmer who designs the program cannot know exactly how large or small a spreadsheet or word processing document will be. Therefore, as you type data into a spreadsheet or word processor, the underlying program allocates more data. Probably, the program does not allocate the data 1 byte at a time as you type, because memory allocation is not always extremely efficient when done 1 byte at a time. More than likely, the program will allocate memory in chunks of code, such as 100-byte or 500-byte sections.
So why can’t the programmers simply allocate huge arrays that can hold a huge spreadsheet or document instead of messing with the heap? For one thing, memory is one of the most precious resources in your computer. As we move into networked and windowed environments, memory becomes even more precious. Your programs can’t allocate huge arrays for those rare occasions when a user might need that much memory. All that memory would be used solely by your program, and other tasks could not access that allocated memory.
The heap enables your program to use only as much memory as it needs. When your user needs more memory, (for instance, to enter more data), your program can allocate the memory. When your user is finished using that much memory (such as clearing a document to start a new one in a word processor), you can deallocate the memory, making it available for other tasks that might have a need for the memory.
You must learn only two new functions to use the heap. The malloc()
(for memory allocate) function allocates heap memory, and the free()
function deallocates heap memory.
Be sure to include the STDLIB.H header file in all the programs you write that use malloc()
and free()
.
We might as well get to the rough part. malloc()
is not the most user-friendly function for newcomers to understand. Perhaps looking at an example of malloc()
would be the best place to start. Suppose you were writing a temperature-averaging program for a local weather forecaster. The more temperature readings the user enters, the more accurate the correct prediction will be. You decide that you will allocate 10 integers to hold the first 10 temperature readings. If the user wants to enter more, your program can allocate another batch of 10, and so on.
You first need a pointer to the 10 heap values. The values are integers, so you need an integer pointer. You’ll need to define the integer pointer like this:
int * temps; /* Will point to the first heap value */
Here is how you can allocate 10 integers on the heap using malloc()
:
temps = (int *) malloc(10 * sizeof(int)); /* Yikes! */
That’s a lot of code just to get 10 integers. The line is actually fairly easy to understand when you see it broken into pieces. The malloc()
function requires only a single value—the number of bytes you want allocated. Therefore, if you wanted 10 bytes, you could do this:
malloc(10).
The problem is that the previous description did not require 10 bytes, but 10 integers. How many bytes of memory do 10 integers require? 10? 20? The answer, of course, is that it depends. Only sizeof()
knows for sure.
Therefore, if you want 10 integers allocated, you must tell malloc()
that you want 10 sets of bytes allocated, with each set of bytes being enough for an integer. Therefore, the previous line included the following malloc()
function call:
malloc(10 * sizeof(int))
This part of the statement told malloc()
to allocate, or set aside, 10 contiguous integer locations on the heap. In a way, the computer puts a fence around those 10 integer locations so that subsequent malloc()
calls do not intrude on this allocated memory. Now that you’ve mastered that last half of the malloc()
statement, there’s not much left to understand. The first part of malloc()
is fairly easy.
malloc()
will always do the following two steps (assuming there is enough heap memory to satisfy your allocation request):
Figure 26.2 shows the result of the previous temperature malloc()
function call. As you can see from the figure, the heap of memory (shown here as just that, a heap) now contains a fenced-off area of 10 integers, and the integer pointer variable named temps
points to the first integer. Subsequent malloc()
function calls will go to other parts of the heap and will not tread on the allocated 10 integers.
Figure 26.2. After allocating the 10 integers.
There is still one slight problem with the malloc()
allocation. The left-hand portion of the temperature malloc()
has yet to be explained. What is the (int *)
for?
The (int *)
is a typecast. You’ve seen other kinds of typecasts in this book. To convert a float
value to an int
, you place (int)
before the floating-point value like this:
aVal = (int)salary;
The * inside a typecast means that the typecast is a pointer typecast. malloc()
always returns a character pointer. If you want to use malloc()
to allocate integers, floating points, or any kind of data other than char
, you have to typecast the malloc()
so the pointer variable that receives the allocation (such as temps
) receives the correct pointer data type. temps
is an integer pointer; you should not assign temps
to malloc()
’s allocated memory unless you typecast malloc()
into an integer pointer. Therefore, the left side of the previous malloc()
simply tells malloc()
that an integer pointer, not the default character pointer, will point to the first of the allocated values.
Besides defining an array at the top of main()
, what have you gained by using malloc()
? For one thing, you can use the malloc()
function anywhere in your program, not just where you define variables and arrays. Therefore, when your program is ready for 100 double
values, you can allocate those 100 double
values. If you used a regular array, you would need a statement like this:
double myVals[100]; /* A regular array of 100 doubles */
towards the top of main()
. Those 100 double
values would sit around for the life of the program taking up valuable memory resources from the rest of the system, even if the program only needed the 100 double
values for a short time. With malloc()
, you need to define only the pointer that points to the top of the allocated memory for the program’s life, not the entire array.
In extreme cases, there may not be enough heap memory to satisfy malloc()
’s request. The user’s computer may not have a lot of memory, another task might be using a lot of memory, or your program may have previously allocated everything already. If malloc()
fails, its pointer variable will point to a null value, 0
. Therefore, many programmers follow a malloc()
with an if
like this:
If malloc()
works, temps
contains a valid address that points to the start of the allocated heap. If malloc()
fails, the invalid address of 0
is pointed to (heap memory never begins at address zero) and the error prints on-screen.
Often, programmers use the not operator, !
, instead of testing a value against 0
, as done here. Therefore, the previous if
test would more likely be coded like this:
if (!temps) /* Means, if not true */
When you’re done with the heap memory, give it back to the system. Use free()
to do that. free()
is a lot easier than malloc()
. To free the 10 integers allocated with the previous malloc()
, use free()
in the following manner:
free(temps); /* Gives the memory back to the heap */
If you originally allocated 10 values, 10 are freed. If the malloc()
that allocated memory for temps
had allocated 1,000 values, all 1,000 would be freed. Once freed, you can’t get the memory back; remember, free()
tosses the allocated memory back onto the heap of memory, and once tossed, the memory might be grabbed by another task (always remember the dirt heap analogy). If you use temps
after the previous free()
, you run the risk of overwriting memory and, possibly, locking up your computer, requiring rebooting.
If you fail to free allocated memory, your operating system will reclaim that memory once your program ends. However, forgetting to call free()
de-feats the purpose of using heap memory in the first place. The goal of the heap is to give your program the opportunity to allocate memory at the point the memory is needed and deallocate that memory when you’re through with it.
Often, an array of pointers helps you allocate many different sets of heap memory. Going back to the weather forecaster’s problem, suppose the forecaster wanted to enter historical temperature readings for several different cities. The forecaster, though, has a different number of readings for each of the different cities.
An array of pointers is useful for such a problem. Here is how you could allocate an array of 50 pointers:
int * temps[50]; /* 50 integer pointers */
The array will not hold 50 integers (because of the dereferencing operator in the definition); instead, the array holds 50 pointers. The first pointer is called temps[0]
, the second pointer is temps[1]
, and so on. Each of the array elements (each pointer) can point to a different set of allocated heap memory. Therefore, even though the 50 pointer array elements must be defined for all of main()
, you can allocate and free the data pointed to as you need extra memory.
Consider the following section of code that might be used by the forecaster:
Of course, such code requires massive data-entry. The values would most likely come from a historical disk file instead of from the user. Nevertheless, the code gives you insight into the advanced data structures available by using the heap. Also, real-world programs aren’t usually of the 20-line variety you often see in this book. Real-world programs, although not necessarily harder than those here, are usually many pages long. Throughout the program, some sections may need extra memory, whereas other sections do not need the memory. The heap lets you use memory efficiently.
Figure 26.3 shows you what the heap memory might look like during the allocating of the temps
array memory (after the first four of the fifty malloc()
calls). As you can see, temps
belongs to the program’s data area, but the memory pointed to by each temps
element belongs to the heap. You can free up the data pointed to by temps
when you no longer need the extra workspace.
Figure 26.3. Each temps
element points to a different part of the heap.
• Use malloc()
and free()
to allocate and release heap memory.
• Tell malloc()
exactly how large each allocation must be by using the sizeof()
operator inside malloc()
’s parentheses.
• Allocate only the pointer variables at the top of your function along with the other variables. Put the data itself on the heap when you need data values other than simple loop counters and totals.
• If you must track several chunks of heap memory, use an array of pointers. Each array element can point to a different amount of heap space.
• Check to make sure malloc()
worked properly. malloc()
returns a 0
if the allocation fails.
• Don’t always rely on regular arrays to hold a program’s data. Sometimes, a program needs data for just a short time, and using the heap will make better use of your memory resources.
• Don’t get discouraged if the heap is beyond your grasp at this point. Using the heap is considered one of the most difficult parts of C programming, and yet, as you saw in this chapter, using the heap isn’t that hard.
Are you thoroughly confused yet, or do you want more information on malloc()
and free()
? Well, memory allocation isn’t as easy as a puts()
function call, but you’ve seen about all there is to malloc()
and free()
. You have a long future ahead of you as a C programmer, and malloc()
will probably confuse you a few more times before malloc()
becomes second nature.
Nevertheless, hopefully memory allocation and deallocation makes more sense to you now than before you started this chapter. (I know, you had never heard of memory allocation before this chapter!) As you progress in your C programming career, keep your eyes open for other programmer’s examples of malloc()
and free()
.
In review, malloc()
allocates heap memory for your programs. You access that heap via a pointer variable, and you can then get to the rest of the allocated memory using array notation based on the pointer assigned by the malloc()
.
When you are done with heap memory, deallocate that memory with the free()
function. free()
tosses the memory back to the heap so other tasks can use it.
This code allocates three groups of heap memory. The iPtr
integer pointer variable points to the first of the 100 allocated integer heap values, fPtr
points to the first of the 50 allocated floating-point values, and dPtr
points to the first of the 450 allocated double floating-point values.
After each malloc()
, the pointer value is checked to make sure that the allocation worked successfully.
Three for
loops then store sequential numbers, starting at 0
, in the allocated memory. The integer loop counter ctr
is used to initialize the three sections of the heap, so a float
and double
typecast is used to convert ctr
to the correct data type before storing the value on the heap. Just for grins, the floating-point heap was initialized using pointer notation instead of array notation.
Remember to deallocate heap memory when you’re done with it. The three free()
function calls deallocate all 600 values allocated by the previous three malloc()
calls.