Thumbnail
Access Restriction
Subscribed

Author Morris, F. Lockwood
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Garbage collection ♦ Storage reclamation ♦ List processing ♦ Pointers ♦ Compactification ♦ Data structures ♦ Record structures ♦ Compaction ♦ Storage allocation ♦ Free storage ♦ Relocation
Abstract 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.
Description Affiliation: Syracuse Univ., Syracuse, NY (Morris, F. Lockwood)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 21
Issue Number 8
Page Count 4
Starting Page 662
Ending Page 665


Open content in new tab

   Open content in new tab
Source: ACM Digital Library