3.7.2 Using Dynamic Memory

Having taken this relevant digression, let's return to the job of managing dynamic memory. This will show how dynamic memory itself might function, and give us the means to create our own when desirable. In fact, you will see when this might be advantageous.

Pointers are used in C to eliminate the problem of dynamic storage management for the programmer. Pointers allow the declaration of a variable of a complex data type and allocate storage for it by merely assigning to its pointer a value that points to that storage. The C function malloc is used for this purpose. This section develops a function avail that will have the same effect as malloc but will manage storage in the records array for Section 3.6.2.

In the general case of list processing, records need to be inserted in and deleted from lists. It is deletion, you may recall, that makes the solution of larger problems feasible. When records are deleted, their storage in the records array may be reused. Reclaiming storage in this way allows larger problems to be solved than would otherwise be possible, by allowing the program to execute to completion.

Records of one or more lists may be stored in the records array at any moment during the execution of a program. Assume that all these records have the same length, and that no sharing of storage occurs. No sharing means that no list record has more than one pointer to it at any time. The more typical case of variable-length records and sharing of storage is more complex and will be dealt with in a later chapter. The issue is now how to implement avail.

Suppose that, by looking at a record, you can tell whether or not it is in use. This would be the case if, whenever a record were deleted from a list, it were marked unused. An available record could be found by traversing the records array until a record marked unused were found. Avail could then return a pointer to that record, after marking it as now in use. In Figure 3.12, this would require the first three records to be accessed before avail could return to point to position 2. The time to carry out this procedure is proportional to the length of the records array in the worst case.

A very significant improvement would be to keep track of the available records so that the search may be avoided and the time for avail to do its task reduced to a constant. This is achieved by using the link fields of each unused record to create a list of available records. Initially all entries of records are unused, so the list should contain every record of the array. Figure 3.13 shows how this list might appear for the configuration of Figure 3.12, with availist taken as its head. Avail now carries out its task by simply deleting the first record from availist and returning a pointer to the deleted record. This yields the desired constant time for avail.

Figure 3.12 Typical Configuration of Used and Unused List Records in the RECORDS Array

Figure 3.13 The List of Available Records Corresponding to Figure 3.12

When records are deleted from a list in programs, it is convenient to keep track of their storage for future use. This requires inserting the deleted records' storage on availist. Again, this operation can be done in constant time if the newly available record is inserted at the front of availist?/FONT>as its new first record. The function that carries out this task will be called reclaim. What time is required for insertion if the record is inserted in the list other than at the front?

The programmer invokes p = avail() to request storage for a record to be stored in records, and p points to that storage when avail returns. The programmer invokes reclaim(p) to request that the storage in records pointed to by p be inserted on availist. By employing avail and reclaim appropriately, the programmer can dynamically allocate and reclaim storage for lists. This means that records can be viewed as the repository of all list records, thus acting as a miniature dynamic memory. Such routines are the heart of storage management algorithms. When the records of a list are not all of the same length, more complex management techniques must be used. When records can be shared, still more complexity is added to the storage management problem, as will be illustrated subsequently.

Malloc is the general C allocation function provided for the programmer's use, so that dynamic memory appears as an abstract facility for storing records. When no memory is available to be allocated, malloc returns a NULL value. Consequently, on each call to malloc the value returned should be checked to be certain it is not the NULL value. Avail may be written to abort or take whatever action is necessary for your application in the event memory is not available.

The C function free is provided to carry out the general task of reclaim. Free deallocates memory that was previously allocated by malloc. The argument to free has to be a pointer previously returned by malloc that has not already been freed. Once memory is freed, it can be used to satisfy new requests through malloc.

In languages such as FORTRAN, which do not provide dynamic memory, you can implement it through avail and reclaim. Once avail and reclaim are written, for all intents and purposes the language has dynamic memory for record storage. You have tailored it to your needs.