Browse Prior Art Database

COPYING LIST STRUCTURES USING BOUNDED WORKSPACE

IP.com Disclosure Number: IPCOM000128600D
Original Publication Date: 1973-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 5 page(s) / 22K

Publishing Venue

Software Patent Institute

Related People

Gary Lindstrom: AUTHOR [+3]

Abstract

When working with link-structured data the need often arises to copy an entire data structure accessible from a given starting cell. Unlike the task of moving a data structure [1], copying requires the original structure to be left intact after the copy is created. In addition to their own utility, copying algorithms are of interest for their adaptability to other list processing operations such as data structure marking and printing.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 24% of the total text.

Page 1 of 5

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

COPYING LIST STRUCTURES USING BOUNDED WORKSPACE

Gary Lindstrom

September 14, 1973 Department of Computer Science University of Pittsburgh Pittsburgh, Pennsylvania 15260

1. List Structure Copying.

When working with link-structured data the need often arises to copy an entire data structure accessible from a given starting cell. Unlike the task of moving a data structure [1], copying requires the original structure to be left intact after the copy is created. In addition to their own utility, copying algorithms are of interest for their adaptability to other list processing operations such as data structure marking and printing. This paper reports two'new algorithms for copying arbitrarily linked LISP-like structures using bounded workspace.

2. Algorithms for Copying.

Copying is customarily accomplished with the aid of temporary workspace at least proportional in size to the number of cells to be copied. Typically, a relocation directory of some form is used, separate from both the original structure and the copy being created. Furthermore, additional space in the form of a stack or cell tag bits is at times used to guide traversal. Bounded workspace algorithms do exist for special cases, such as SLIP-like ring structures with header cells ( r2l , pp. 421, 594), and for binary trees [3]. Vj

This paper reports two'new algorithms for copying arbitrarily linked LISP-like structures using bounded workspace. The first algorithm,

Cl, uses tag-free cells to copy an n-cell structure in time propor-

2 tional to n . While this speed limits practical utility, the result does establish an upper bound on the time complexity~of this task under the severest workspace limitation.

The second algorithm, C2, assumes an available tag bit in both original and copy cells. This small added space permits attractive practical speed. Any non-cyclic structure, including those with multiply referenced substructures, is copied in linear time. A structure containing cyclic links is copied in average time less than n log n. Moreover, the speed benefit for non-cyclic structures is automatically obtained without foreknowledge of cycle absence.

Finally, as an example of copying algorithm adaptability, a general list structure marking algorithm MI is presented, derived from C2. MI will mark an arbitrary list structure in average time R log a, using bounded workspace and no extra cell tag bits beyond the single mark bit. This result solves an open problem posed in [3].

3. Algorithm Cl: Copying with No Tag Bits.

University of Pittsburgh Page 1 Dec 31, 1973

Page 2 of 5

COPYING LIST STRUCTURES USING BOUNDED WORKSPACE

Consider a data store organized into cells comprising two link fields, LLINK and RLINK. Each link field is capable of addressing any cell or containing an uninterpreted atomic value from some atom set A . Cells and atoms together will be termed nodes.

The process of copying a structure represent...