Document Type
Report
Date
2-1977
Keywords
Garbage collection, compaction, compactification, storage reclamation, storage allocation, record structures, relocation, list processing, free storage, pointers, data structures
Language
English
Disciplines
Computer Sciences
Description/Abstract
Given an area of storage containing scattered marked nodes, one may wish to rearrange them into a compact mass at one end of the area, meanwhile revising all pointers to marked nodes to show their new locations. An algorithm is here described which accomplishes this task in Iinear time relative to the size of the storage area, and in space of the order of one bit for each pointer. The algorithm operates by reversibly encoding the situation that a collection of locations point to a single location by a linear list, emanating from the pointed-to location, passing through the pointing locations, and terminating with the pointed-to location's transplanted contents.
Recommended Citation
Morris, F. Lockwood, "A Time- and Space-Efficient Garbage Compaction Algorithm" (1977). Electrical Engineering and Computer Science - Technical Reports. 43.
https://surface.syr.edu/eecs_techreports/43
Source
local
