Browse Prior Art Database

AN ALGORITHM FOR GARBAGE COLLECTING IN A HASHING ENVIRONMENT

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

Publishing Venue

Software Patent Institute

Related People

Daniel P. Friedman: AUTHOR [+4]

Abstract

A new algorithm is introduced for garbage collecting a heap which contains shared data structures accessed from a scatter table. The scheme provides for the purging of useless entries from the scatter table with no traversals beyond the two required by classic collection schemes. Since the scatter table is completely restructured during the course of execution, the hashing scheme itself is easily altered during garbage collection .whenever skewed loading of the scatter table warrants abandonment of the old hashing. This procedure is applicable to the mainte-nance of dynamic structures such as those in information retrieval schemes or in languages like LISP.

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

Page 1 of 4

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

AN ALGORITHM FOR GARBAGE COLLECTING IN A HASHING ENVIRONMENT

Daniel P. Friedman David S. Wise

Computer Science Department Indiana University Bloomington, Indiana TECHNICAL REPORT No. 34

AN ALGORITHM FOR GARBAGE COLLECTING IN A HASHING ENVIRONMENT

DANIEL P. FRIEDMAN DAVID S. WISE

REVISED: FEBRUARY, An Algorithm for Garbage Collecting in a Hashing Environment

Daniel P. Friedman David S. Wise

Computer Science Department Indiana University

Bloomington, Indiana 47401

Abstract:

A new algorithm is introduced for garbage collecting a heap which contains shared data structures accessed from a scatter table. The scheme provides for the purging of useless entries from the scatter table with no traversals beyond the two required by classic collection schemes. Since the scatter table is completely restructured during the course of execution, the hashing scheme itself is easily altered during garbage collection .whenever skewed loading of the scatter table warrants abandonment of the old hashing. This procedure is applicable to the mainte-nance of dynamic structures such as those in information retrieval schemes or in languages like LISP.

Key words and phrases: scatter table, bucket, key, inverted tree, oriented tree, chaining, rehashing, LISP.

CR categories: 3.74, 4.1, 4.34.

Research reported herein was supported (in part) by the National

Science Foundation under grant no. DCR75-o6678 and no. MCS75-o Garbage collection [
2.3.51* is generallya two-pass scheme for recovering unused nodes from a heap, a region of computer memory divided into nodes accessed by the user only via references. During the first pass all useful structures represented within the heap are traversed and a mark bit is set within every node en-countered. Then the heap is traversed or swept completely and every unmarked node is added to a list of available space. Addi-tional traversals may provide for repacking the structures into adjacent nodes at one end of the heap [ 2.3.6-9] and for such re-packing when nodes are of variable size [2]. In this paper we assume that all nodes in the heap are of equal size and that no repacking is necessary; if these features are needed then the scheme presented here can be easily extended.

Indiana University Page 1 Dec 31, 1976

Page 2 of 4

AN ALGORITHM FOR GARBAGE COLLECTING IN A HASHING ENVIRONMENT

A scatter table E 6.41 is a dynamic structure often used for efficiently associating ALGOL 60 style identifiers with values. It is a common part of the input phase of a computer program used to associate new occurrences of an identifier with information established earlier; the symbol table in an interpreter or compiler is an example of its application. The common structure of such a table is' a fixed size sequential array of references to linearly linked lists [1]. The array is accessed by a pseudo-random function, the hash function, mapping identifiers to array indices hopefully sc...