13.5: Storage Reclamation Techniques

Saying that a node or component of a data structure is to be reclaimed for use means that the storage used for its records is to become known to the avail function. That is, the storage no longer needed by its records is to be inserted on the list of available space. There are two basic methods of reclaiming released nodes, garbage collection and reference counters. Other methods are essentially combinations of these. These methods are the two extremes with respect to the time at which storage is reclaimed. Garbage collection does not make storage available for reuse until it is needed, putting off reclamation as long as possible. Reference counters make storage available for reuse as soon as it actually becomes reclaimable.

13.5.1 Garbage Collection

13.5.2 The Reference Counter Method

13.5.3 Overview of Storage Reclamation