Reclaiming Space Dynamically

---

Storage compaction is the simplest and most widely used of the storage reclamation methods. However, in some situations, we want to reuse the space from deleted records as soon as possible. We will consider two cases separately to speed up dynamic space reclaiming: i) fixed-length record deletion, and ii) variable-length record deletion.

Fixed-Length Record Deletion
Space re-utilization can take the form of looking through the file, record by record, until a deleted record is found. If the program reaches the end of the file without finding a deleted record, the new record can be appended at the end. This approach makes adding records an intolerably slow process.

A linked list can be used to help speed up the dynamic space reclaiming.

In a linked list, each element contains a pointer to the next element, thus forming a linear list. When a list is made up of deleted records that have become available space within the file, the list is called an avail list.

A simplest way to handle a list is as a stack, in which items are to be accessed in last-in first-out order. For example, an avail list is managed as a stack that initially contained relative record numbers (RRN) 5 and 2, and then added RRN 3, which was just deleted.

When a request for some available space is submitted, the request is filled by taking RRN 3 from the avail list.

Initial Contents Offset Stack Bottom RRN 2 Top RRN 5         PUSH RRN 3 Offset Stack Bottom RRN 2   RRN 5 Top RRN 3     POP Offset Stack Bottom RRN 2 Top RRN 5