Document Type

Report

Date

2-1977

Embargo Period

4-25-2012

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.

Source

local

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.