A bounded storage algorithm for copying cyclic structures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A bounded storage algorithm for copying cyclic structures

Full text

Pdf (236 KB)

Source

Communications of the ACM archive
Volume 20 , Issue 6 (June 1977) table of contents

Pages: 431 - 433

Year of Publication: 1977

ISSN:0001-0782

Author

J. M. Robson

Univ. of Lancaster, Lancaster, England

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 24, Citation Count: 8

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/359605.359628 What is a DOI?

ABSTRACT

A new algorithm is presented which copies cyclic list structures using bounded workspace and linear time. Unlike a previous similar algorithm, this one makes no assumptions about the storage allocation system in use and uses only operations likely to be available in a high-level language. The distinctive feature of this algorithm is a technique for traversing the structure twice, using the same spanning tree in each case, first from left to right and then from right to left.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Gary Lindstrom, Copying list structures using bounded workspace, Communications of the ACM, v.17 n.4, p.198-202, April 1974 [doi>10.1145/360924.360936]
	2	David A. Fisher, Copying cyclic list structures in linear time using bounded workspace, Communications of the ACM, v.18 n.5, p.251-252, May 1975 [doi>10.1145/360762.360764]
	3	Woodward, P.M., and Bond, S.G. Algol 68-R Users' Guide. Her Majesty's Stationery Office, London, England, 1974.

CITED BY 8

	Douglas W. Clark, A fast algorithm for copying list structures, Communications of the ACM, v.21 n.5, p.351-357, May 1978
	K. P. Lee, A linear algorithm for copying binary trees using bounded workspace, Communications of the ACM, v.23 n.3, p.159-162, March 1980
	Norihisa Suzuki, Analysis of pointer “rotation”, Communications of the ACM, v.25 n.5, p.330-335, May 1982
	Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981
	Stanley Lee , Willem P. deRoever , Susan L. Gerhart, The evolution of list-copying algorithms and the need for structured program verification, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.53-67, January 29-31, 1979, San Antonio, Texas
	R. J. R. Back , Heikki Mannila , Kari-Jouko Räihä, Derivation of efficient DAG marking algorithms, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.20-27, January 24-26, 1983, Austin, Texas
	Norihisa Suzuki, Analysis of pointer rotation, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-11, January 28-30, 1980, Las Vegas, Nevada
	Nandakumar Sankaran, A bibliography on garbage collection and related topics, ACM SIGPLAN Notices, v.29 n.9, p.149-158, Sept. 1994

INDEX TERMS

Keywords:
copying, cyclic structures, shared subtrees

Collaborative Colleagues:

J. M. Robson: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player