13.2: The Heap or Dynamic Memory

As one or more programs execute, they may require storage for the creation of new records, which typically are to be inserted into dynamic data structures. How can a fixed amount of storage that is made available for the creation of these records be managed efficiently?

The records, or more generally, the components of dynamic data structures, are referred to as nodes. The region of memory consisting of contiguous elements that is dedicated to the storage of these nodes is called the heap or dynamic memory. We will use the term heap in the further discussion. In the heap all nodes need not be the same length, and nodes may appear as part of more than one data structure. Associated with each node is a length field, indicating the size of the node (that is, the number of memory elements it uses). If all nodes were the same size, there would be no need to store size information within each node. All dynamic data structures reside in the heap. At all times, the heap may contain three kinds of nodes:

n Nodes that are in use because they appear in dynamic data structures

n Nodes that are not in use and appear in no dynamic data structure but are on the current list of available space

n Nodes that are not in use because they are in no dynamic data structure but are not on the list of available space

Nodes on the list of available space are said to be known. Nodes that are available but not on the list of available space are called garbage. All heads (names) of dynamic data structures, which point to their first records, are outside the heap and are kept track of in some way. This means that at all times the program knows what dynamic data structures are in existence, since their names are known.

Example 13.4

Suppose av, 1, and t are, respectively, the heads of the available space list, a list, and a binary tree. A heap containing these dynamic data structures may be visualized as in Figure 13.1. Each node has been labeled to indicate its current status:

1梚n use since the node appears on l or t

2?/FONT>not in use but on the available space list

3?/FONT>not in use and not on the available space list, hence garbage n

Storage allocation now involves three tasks:

1. Decide which node on the list of available space will be made available when a request for creation of a node is made.

2. Delete that node from the list of available space.

3. Set a pointer value to point to the node.

An avail-like function, discussed in Chapter 3, will perform these three tasks.