Whenever you define a variable in C—whether it is a simple data type, an array, or a structure—you are effectively reserving one or more locations in the computer’s memo-ry to contain the values that will be stored in that variable. The C compiler automatically allocates the correct amount of storage for you.
It is frequently desirable, if not necessary, to be able to dynamically allocate storage while a program is running. Suppose you have a program that is designed to read in a set of data from a file into an array in memory. Suppose, however, that you don’t know how much data is in the file until the program starts execution.You have three choices:
- Define the array to contain the maximum number of possible elements at compile time.
- Use a variable-length array to dimension the size of the array at runtime.
- Allocate the array dynamically using one of C’s memory allocation routines.
Using the first approach, you have to define your array to contain the maximum number of elements that would be read into the array, as in the following:
#define kMaxElements 1000
struct dataEntry dataArray [kMaxElements];
Now, as long as the data file contains 1,000 elements or less, you’re in business. But if the number of elements exceeds this amount, you must go back to the program, change the value of kMaxElements, and recompile it. Of course, no matter what value you select, you always have the chance of running into the same problem again in the future.
With the second approach, if you can determine the number of elements you need before you start reading in the data (perhaps from the size of the file, for example), you can then define a variable-length array as follows:
struct dateEntry dataArray [dataItems];
Here, it is assumed that the variable dataItems contains the aforementioned number of data items to read in.
Using the dynamic memory allocation functions, you can get storage as you need it. That is, this approach also enables you to allocate memory as the program is executing. To use dynamic memory allocation, you must first learn about three functions and one new operator.
1. The calloc and malloc Functions
In the standard C library, two functions, called calloc and malloc, can be used to allo- cate memory at runtime. The calloc function takes two arguments that specify the number of elements to be reserved and the size of each element in bytes. The function returns a pointer to the beginning of the allocated storage area in memory. The storage area is also automatically set to 0.
calloc returns a pointer to void, which is C’s generic pointer type. Before storing this returned pointer inside a pointer variable in your program, it can be converted into a pointer of the appropriate type using the type cast operator.
The malloc function works similarly, except that it only takes a single argument—the total number of bytes of storage to allocate—and also doesn’t automatically set the stor- age area to 0.
The dynamic memory allocation functions are declared in the standard header file <stdlib.h>, which should be included in your program whenever you want to use these routines.
2. The sizeof Operator
To determine the size of data elements to be reserved by calloc or malloc in a machine-independent way, the C sizeof operator should be used. The sizeof operator returns the size of the specified item in bytes. The argument to the sizeof operator can be a variable, an array name, the name of a basic data type, the name of a derived data type, or an expression. For example, writing
gives the number of bytes needed to store an integer. On a Pentium 4 machine, this has the value 4 because an integer occupies 32 bits on that machine. If x is defined to be an array of 100 integers, the expression
gives the amount of storage required for the 100 integers of x (or the value 400 on a Pentium 4). The expression
sizeof (struct dataEntry)
has as its value the amount of storage required to store one dataEntry structure. Finally, if data is defined as an array of struct dataEntry elements, the expression
sizeof (data) / sizeof (struct dataEntry)
gives the number of elements contained in data (data must be a previously defined array, and not a formal parameter or externally referenced array). The expression
sizeof (data) / sizeof (data)
also produces the same result. The macro
#define ELEMENTS(x) (sizeof(x) / sizeof(x))
simply generalizes this technique. It enables you to write code like
if ( i >= ELEMENTS (data) )
for ( i = 0; i < ELEMENTS (data); ++i )
You should remember that sizeof is actually an operator, and not a function, even though it looks like a function. This operator is evaluated at compile time and not at runtime, unless a variable-length array is used in its argument. If such an array is not used, the compiler evaluates the value of the sizeof expression and replaces it with the result of the calculation, which is treated as a constant.
Use the sizeof operator wherever possible to avoid having to calculate and hard- code sizes into your program.
Getting back to dynamic memory allocation, if you want to allocate enough storage in your program to store 1,000 integers, you can call calloc as follows:
intPtr = (int *) calloc (sizeof (int), 1000);
Using malloc, the function call looks like this:
intPtr = (int *) malloc (1000 * sizeof (int));
Remember that both malloc and calloc are defined to return a pointer to void and, as noted, this pointer should be type cast to the appropriate pointer type. In the preceding example, the pointer is type cast to an integer pointer and then assigned to intPtr.
If you ask for more memory than the system has available, calloc (or malloc) returns a null pointer. Whether you use calloc or malloc, be certain to test the pointer that is returned to ensure that the allocation succeeded.
The following code segment allocates space for 1,000 integer pointers and tests the pointer that is returned. If the allocation fails, the program writes an error message to standard error and then exits.
intptr = (int *) calloc (sizeof (int), 1000);
if ( intPtr == NULL )
fprintf (stderr, “calloc failed\n”);
If the allocation succeeds, the integer pointer variable intPtr can be used as if it were pointing to an array of 1,000 integers. So, to set all 1,000 elements to –1, you could write
for ( p = intPtr; p < intPtr + 1000; ++p )
*p = -1;
assuming p is declared to be an integer pointer.
To reserve storage for n elements of type struct dataEntry, you first need to define a pointer of the appropriate type
struct dataEntry *dataPtr;
and could then proceed to call the calloc function to reserve the appropriate number of elements
dataPtr = (struct dataEntry *) calloc (n, sizeof (struct dataEntry));
Execution of the preceding statement proceeds as follows:
- The calloc function is called with two arguments, the first specifying that storage for n elements is to be dynamically allocated and the second specifying the size of each element.
- The calloc function returns a pointer in memory to the allocated storage area. If the storage cannot be allocated, the null pointer is returned.
- The pointer is type cast into a pointer of type “pointer to struct dataEntry” and is then assigned to the pointer variable dataPtr.
Once again, the value of dataPtr should be subsequently tested to ensure that the allo- cation succeeded. If it did, its value is nonnull. This pointer can then be used in the nor- mal fashion, as if it were pointing to an array of n dataEntry elements. For example, if dataEntry contains an integer member called index, you can assign 100 to this member as pointed to by dataPtr with the following statement:
dataPtr->index = 100;
3. The free Function
When you have finished working with the memory that has been dynamically allocated by calloc or malloc, you should give it back to the system by calling the free func- tion. The single argument to the function is a pointer to the beginning of the allocated memory, as returned by a calloc or malloc call. So, the call
returns the memory allocated by the calloc call shown previously, provided that the value of dataPtr still points to the beginning of the allocated memory.
The free function does not return a value.
The memory that is released by free can be reused by a later call to calloc or malloc. For programs that need to allocate more storage space than would otherwise be available if it were all allocated at once, this is worth remembering. Make certain you
give the free function a valid pointer to the beginning of some previously allocated space.
Dynamic memory allocation is invaluable when dealing with linked structures, such as linked lists. When you need to add a new entry to the list, you can dynamically allo- cate storage for one entry in the list and link it into the list with the pointer returned by calloc or malloc. For example, assume that listEnd points to the end of a singly linked list of type struct entry, defined as follows:
struct entry *next;
Here is a function called addEntry that takes as its argument a pointer to the start of the linked list and that adds a new entry to the end of the list.
// add new entry to end of linked list
struct entry *addEntry (struct entry *listPtr)
// find the end of the list
while ( listPtr->next != NULL )
listPtr = listPtr->next;
// get storage for new entry
listPtr->next = (struct entry *) malloc (sizeof (struct entry));
// add null to the new end of the list
if ( listPtr->next != NULL )
(listPtr->next)->next = (struct entry *) NULL;
If the allocation succeeds, a null pointer is placed in the next member of the newly allo- cated linked-list entry (pointed to by listPtr->next).
The function returns a pointer to the new list entry, or the null pointer if the alloca- tion fails (verify that this is, in fact, what happens). If you draw a picture of a linked list and trace through the execution of addEntry, it will help you to understand how the function works.
Another function, called realloc, is associated with dynamic memory allocation. It can be used to shrink or expand the size of some previously allocated storage. For more details, consult Appendix B.
This chapter concludes coverage of the features of the C language. In Chapter 18, “Debugging Programs,” you learn some techniques that will help you to debug your C programs. One involves using the preprocessor. The other involves the use of a special tool, called an interactive debugger.
Source: Kochan Stephen G. (2004), Programming in C: A Complete Introduction to the C Programming Language, Sams; Subsequent edition.