As a C/C++ programmer you need to worry about three types of internal storage: automatic, static, and dynamic. When you define automatic variables inside a block, most compilers generate code to allocate space for those variables on the program stack. When execution leaves a block, the stack pointer moves back up to where it was before that block was entered, in effect destroying that block's automatic variables. When execution reenters the block, it creates all automatic variables afresh, with the same initial values as before. Static objects are declared either at file scope or inside a block with the static specifier. They reside at a fixed location in the program's data space and are initialized once at program startup.
Dynamic objects are created at run time by special library function calls and reside on the heap, a special data area set aside for user-controlled, run-time memory allocation. When you request heap space for an object you get an address in return. The system reserves the memory at that address for your use until you're through with it. In this article I will discuss common C/C++ techniques for using dynamic memory.
Ragged Arrays
The heap comes in handy when you don't know at compile time how much space you will need to store an object, or how many objects you will need. For example, a common practice in processing text files allocates separate heap space for each line of text, storing the address of each heap space in an array of pointers to char. The program in Listing 1 reads up to MAXLINES lines of text into memory and sorts them in ascending order using qsort. As the program reads each line, it calls malloc, a <stdlib.h> function, to get enough heap space to hold the line and its terminating null byte. The program stores the address that malloc returns in the array strings[]. This flexible storage mechanism is called a ragged array, because it only allocates the memory required by each line of text, as illustrated by Figure 1.Although this scheme imposes an overhead penalty of one pointer per line, it's likely to be more efficient than a two-dimensional storage scheme with a large line length, as in Figure 2.
When you are through with dynamic memory, send its address as a parameter to free which makes the space available for reuse by any future calls to malloc. (For an explanation of the qsort function, see Code Capsules: "Sorting with qsort," CUJ, April, 1993, p. 107.)
Using the Heap in Standard C
The standard header <stdlib.h> declares four functions for using dynamic memory:1. void *malloc(size_t siz) — Returns a pointer to the first of siz bytes. Used for allocating single objects.
2. void *calloc(size_t nelems, size_t elem_size) — Returns a pointer to nelems*elem_size bytes, initialized to zero. Used for allocating arrays of objects.
3. void *realloc(void *ptr, size_t siz) — Used to expand or shrink a heap allocation. ptr must have originated from a previous call to malloc or calloc, except that if ptr is null, the result is the same as malloc(siz). If there is enough space for the new allocation, realloc copies the original data to the new location, then returns the new address.
4. void free(void *ptr) — Makes previously allocated heap memory available for reuse. ptr must have been returned by a previous call to one of the above allocation functions. free(NULL) is a no-op.
The three allocation functions return a null pointer if the amount of memory requested is not available.
The program in Listing 2 and Listing 3 illustrates all four functions. This program extends the traditional argc/argv mechanism for reading command-line arguments by allowing you to specify files of arguments. Any program argument that begins with the '@' character names an indirect file, i.e., a file that contains more arguments. For example, the command
getargs @arg.datcauses the system to read file arg.dat for more arguments. Such command files can be nested (see Listing 4, Listing 5, and Listing 6) .The arglist function returns a pointer to a dynamically-sized, ragged array of strings, which is the fully-expanded list of program arguments. The function free_args frees all of the memory used in the creation of the array.
arglist uses calloc to dynamically allocate an array large enough to hold argc-1 arguments, the original number of arguments on the command line. arglist calls add to insert a new argument into the list. If the array is full, add calls realloc to increase the size of the array by a predetermined amount (CHUNK). add calls malloc to place all argument strings on the heap. The function expand processes indirect file arguments. Since indirect files can be nested, expand is a recursive function. If there are no indirect file arguments, then realloc never gets called.
Dynamic Data Structures
Dynamic memory allocation eases the creation of data structures that change at run time, such as lists and trees. Such data structures usually contain a pointer to their own type (sometimes called a self-referential pointer) to connect components of the structure together. For example, the definition of a linked-list node looks like this:
struct List { /* Put data components here: */ int num; /* etc. */ /* Here's the link: */ struct List *next; };Figure 3 depicts the topology of a linkedlist in memory.A null link means nothing follows. You call malloc and free respectively to create and delete nodes as needed at run time. A linked-list is especially efficient for insert and delete operations, since you don't have to shuffle elements to create or delete gaps like you do with arrays.
A binary search tree is a non-linear data structure suitable for storing ordered data for fast retrieval. Each node in the tree contains two self-referential pointers:
struct Tree { /* Data here */ char *data; /* etc. */ /* Links here */ struct Tree *left; struct Tree *right; };By convention, all items to the left of a tree node precede it in sort order, and the ones to the right sort after it. For example, the words "little boy blue come blow your horn" might result in the binary search tree shown in Figure 4. This arrangement makes the following binary search algorithm faster than a sequential search:
struct Tree *search(char *s, struct Tree *tp) { if (tp == NULL) return NULL; /* not found */ else if (strcmp(s,tp->data) > 0) return search(s,tp->right); else if (strcmp(s,tp->data) < 0) return search(s,tp->left); else return tp; /* found it */ }To print the items in sorted order, you do an end-order traversal of the tree, which recursively processes the left subtree, the root node, then the right subtree:
void print_tree(struct Tree *tp) { if (tp) { print_tree(tp->left); puts(tp->data); print_tree(tp->right); } }(If this puzzles you, review your favorite book on data structures. Mine is The Design And Analysis Of Computer Algorithms, by Aho, Hopcroft, and Ullman, Addison-Wesley, 1974.)The program in Listing 7 uses both of these data structures to create a cross-reference listing of words in a text file. Each word occupies a distinct node in a binary search tree. A list of line numbers accompanies each word to indicate where in the text the word appears. Sample output is in Listing 8.
Managing the Heap
Have you ever wondered how the heap management system knows how much memory to release when you call free(p)? Since you don't tell it, it must keep that information somewhere. In most systems that somewhere is right before the block pointed at by p, so instead of getting the block shown in Figure 5a, you're really getting an extra prepended block (usually a few bytes), as shown in Figure 5b. This overhead can be rather costly when you allocate a large number of small objects.Another phenomenon that occurs is fragmentation. After allocating many objects and then deleting some, gaps appear in the heap, as shown in Figure 6. Although the heap contains enough combined space for another object, since the space is not contiguous, the allocation may fail.
A relatively painless way to sidestep these problems is to allocate a large pool of memory and manage it yourself. The cross-reference program in Listing 9 maintains a separate pool for the tree and list. The key to its use is the following union:
union List_shell { union List_shell *next; List dummy; };The function init_list_pool allocates an array of List_shell objects, which are the same size as a list node. init_list_pool then connects each object together in linked-list fashion, with free_list_ptr pointing to the first array element, as shown in Figure 7.No space is wasted because the List_shell structure overlays a List object. You replace calls to malloc in the original program with calls to get_list_node, which returns the next free object and updates free_list_ptr. All of the above applies to pools of tree nodes, of course.
Exercise
The program in Listing 9 has two limitations: 1) the pools are fixed in size, and 2) the code for the list and tree pools is identical, except for names and sizes of objects, which is a waste of good logic. Write a generic memory pool manager with the following interface:
Pool *pool_create(size_t elem_size, size_t init_alloc, size_t extent);Creates a pool to manage elements of size elem_size. Allocates init-alloc elements initially.
void *pool_get_elem(Pool *p);Returns a pointer to the next free element in the pool, and updates the free pointer. Increases the pool by extent elements as needed.
void pool_release_elem(Pool *p, void *elem);Returns an element to the pool.
void pool_free(Pool *p);Releases all the memory used by the pool.My solution will appear next month.
C++ and Memory Management
As an alternative to the memory management functions in <stdlib.h>, C++ offers the new and delete operators. To dynamically create a List node in C++, you could do this:
List *list_p = new List;which corresponds to a call to malloc. If you want an array of nodes instead, do this:
List *list_array_p = new List[LIST_CHUNK];which is similar to calloc, except you don't have to compute the number of bytes yourself. Since new is an operator, and not a function call, the compiler can compute the amount of memory needed, so you don't have to. When you are through with these objects, use the delete operator to release the dynamic memory:
delete list_p; // delete an object delete [] list_array_p; // delete an arrayIt is important to use the array version to free an array allocation. One important reason is that if the type of object you are deleting has a destructor, the system will call that destructor for each element of the array only if you use delete []. (See Listing 10 and Listing 11. )The class definition in Listing 12 encapsulates the functionality of the argument list processing program in Listing 3. The implementation in Listing 13 uses new and delete in place of malloc, calloc, realloc, and free, as appropriate. Since there is no equivalent of realloc in C++, Arglist::add() does an explicit new followed by a copy and a delete to accomplish the same thing. The sample program in Listing 14 shows how to create multiple Arglist objects.
Let Class Libraries Do The Work
The key feature of the standard C++ string class is memory management. The string class handles the details of dynamic memory so you don't have to. The version of the Arglist class in Listing 15 and 16 uses arrays of strings instead of arrays of pointers to char so I don't have to allocate individual strings on the heap myself. (Note: Listing 15 through Listing 18 are specific to the Borland C++ compiler.)Better yet is to use a container class that implements dynamic arrays, like Borland's TArrayAsVector<> template class. The following statement from Listing 17 instantiates a dynamic array of strings:
TArrayAsVector<string> args;The constructor for TArrayAsVector requires an upper bound, lower bound, and reallocation amount, so I pass these in the member initialization list in Listing 18:
Arglist::Arglist(/* ... */) : args(arg_count,0,CHUNK)The following TArrayAsVector<class T> member functions do everything I need:
size_t GetItemsInContainer(); T operator[](size_t); int Add(const T&);In order to use the string or dynamic array implementations, you only need to change the header file included in Listing 14.
Summary
Dynamic memory allocation provides the support that flexible data structures require. You may need to do your own heap management, however, to avoid undue overhead or memory fragmentation. Next month I'll explore memory management in C++ more deeply, including how to handle out-of-memory exceptions and overloading new and delete both globally and on a per-class basis.