A Time- and Space- Efficient Garbage Compaction Algorithm

Given an area of storage containing scattered,
marked nodes of differing sizes, one may wish 
to rearrange them into a compact mass at one end of the
area while revising all pointers to marked nodes 
to show their new locations.  An algorithm is described
here which accomplishes this task in linear time 
relative to the size of the storage area, and in a 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.

CACM August, 1978

Morris, F.

Garbage collection, compaction, compact ification,
storage reclamation, storage allocation, record 
structures, relocation, list processing, free storage, pointers, data structures

4.34 4.49 5.32

CA780804 DH February 7, 1979  10:16 AM

1972	4	3074
1972	4	3074
2156	4	3074
2156	4	3074
2168	4	3074
2249	4	3074
2361	4	3074
2438	4	3074
2513	4	3074
2723	4	3074
2736	4	3074
2736	4	3074
2736	4	3074
2833	4	3074
2838	4	3074
2855	4	3074
2855	4	3074
2896	4	3074
3039	4	3074
3074	4	3074
3074	4	3074
3074	4	3074
3074	4	3074
3106	4	3074
3112	4	3074
3112	4	3074
3112	4	3074
1826	5	3074
1853	5	3074
1972	5	3074
2723	5	3074
3074	5	3074
3074	5	3074
3074	5	3074