26. Where’s More Memory?

Try the Heap

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.

Thinking of 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.

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!)

But WHY Do I Need the Heap?

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.

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.

How Do I Allocate the Heap?

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.

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):

1. Allocate the number of bytes you request and make sure that no other program can overwrite that memory until your program frees it.
2. Assign your pointer to the first allocated value.

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.

If There’s Not Enough Heap Memory

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.

Freeing Heap Memory

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.

Multiple Allocations

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.

Rewards

• 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.

Pitfalls

• 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.

In Review

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.

Code Example

Code Analysis

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.