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