Browse Prior Art Database

SCANNING LIST STRUCTURES WITHOUT STACKS OR TAG BITS

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

Publishing Venue

Software Patent Institute

Related People

Gary E. Lindstrom: AUTHOR [+3]

Abstract

The management of list-structured data customarily entails some method for systematic scanning or traversal. This need may arise when the contained primitive data must be extracted in some canonical order (e.g. binary sort tree traversal), or when a search must be made for all accessible cells (e.g. LISP-type garbage collection marking). This work improves on space requirements in some special purpose instances of such problems by using neither tag bits in individual list cell3, nor an auxiliary stack. The results focus attention on several open problems, including the possibility of a general list-structure marking algorithm requiring no external stack or dedicated cell bits other than the mark bit.

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

Page 1 of 4

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

SCANNING LIST STRUCTURES WITHOUT STACKS OR TAG BITS

Gary E. Lindstrom

March 15, 1973 Department of Computer Science University of Pittsburgh Pittsburgh, Pennsylvania 15260

1. Summary.

The management of list-structured data customarily entails some method for systematic scanning or traversal. This need may arise when the contained primitive data must be extracted in some canonical order (e.g. binary sort tree traversal), or when a search must be made for all accessible cells (e.g. LISP-type garbage collection marking). This work improves on space requirements in some special purpose instances of such problems by using neither tag bits in individual list cell3, nor an auxiliary stack. The results focus attention on several open problems, including the possibility of a general list-structure marking algorithm requiring no external stack or dedicated cell bits other than the mark bit.

2. List structure scanning.

2.1. Types of list structures. Data structures constructed from linked cells may be organized into three successively generalized categories:

Trees: in which there exists at most one sequence of link accesses connecting any two cells;

ii) T rees with shared subtreas: in which all sequences of link accesses ultimately terminate at primitive data (no link cycles exist), and

1W Re-entrant structures: in which any linking patterns, including cycles, are permitted.

2.2. Processing needs. In managing linked data structures the need customarily arises for processing the component cells of a given structure in a systematic manner. Two types of processing may be distin-guished:

i) Traversal: in which the component cells are each "visited" once in some canonical order based on structural relationships, and

1i) Scanning: in which exhaustive cell accessing is required, but may be done in a repetitive or unpredictable sequence. Traversal is most meaningful in the processing of trees (including those with shared subtrees), where such orders as "preorder," "postorder," and "endorder" are well-defined (ref. 1, p. 315 ff.). Such traversals have applications in the translation and evaluation of expressions and in the outputting of data stored in sort trees. Scanning is best exemplified in list structure marking algorithms, where the task is to set a reserved bit in each cell accessible from a starting cell in an arbitrary list ,structure.

University of Pittsburgh Page 1 Dec 31, 1973

Page 2 of 4

SCANNING LIST STRUCTURES WITHOUT STACKS OR TAG BITS

2.3. Existigg algorithms. All traversal and scanning algorithms known heretofore have required either tag bits in list cells, an auxiliary stack, or both,for successful navigation (we rule out "threaded" struc-tures, e.g. ref. 1, p. 319 ff.). For example, Knuth (ref. 1, p. 562) provides an algorithm for binary tree traversal utilizing no external stack but requiring a tag bit in each cell to guide processing. (See Algorithm 1.) It may be no...