Managing Reentrant Structures Using Reference Counts

ABSTRACT

Automatic storage management requires that one identify storage unreachable by a user's program and return it to free status. One technique maintains a count of the references from user's programs to each cell, since a count of zero implies the storage is unreachable. Reentrant structures are self-referencing; hence no cell in them will have a count of zero, even though the entire structure is unreachable. A modification of standard reference counting can be used to manaage the deallocation of a large class of frequently used reentrant structures, including two-way and circularly linked lists. All the cells of a potentially reentrant structure are considered as part of a single group for deallocation purposes. Information associated with each cell specifies its group membership. Internal references (pointers from one cell of the group to another) are not reference counted. External references to any cell of this group are counted as references to the group as a whole. When the external reference count goes to zero, all the cells of the group can be deallocated. This paper describes several ways of specifying group membership, properties of each implementation, and properties of mutable and immutable group membership.

REFERENCES

• 1: Robert R. Fenichel, List tracing in systems allowing multiple cell-types, Communications of the ACM, v.14 n.8, p.522-526, Aug. 1971 [doi>10.1145/362637.362646]
• 2: FRIEDMAN, D.P., AND WINE, D.S. Reference counting can manage the circular environments of mutual recursion. Inform. Process. Lett. 8, 1 (1979).
• 3: HOPCRAFT, J.E., A~D ULLMAN, J.D. Set merging algorithms. SIAM J. Comput. 2 (1973).
• 4: K~VTH, D.E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison- Wesley, Reading, Mass., 1973.
• 5: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 6: J. Weizenbaum, Symmetric list processor, Communications of the ACM, v.6 n.9, p.524-536, Sept. 1963 [doi>10.1145/367593.367617]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

General Terms:
Design, Languages, Performance, Theory