File CellHeap.h

↰ Parent directory (ADS/memory)

A heap of cells of two fields with a garbage collector, beyond the book: the memory of a LISP, where a field holds nil, an atom or the address of a cell, and the cells not reachable from the roots are garbage.

Definition (ADS/memory/CellHeap.h)

Detailed Description

collect() marks the reachable cells and sweeps the others onto the free list, and cons() collects when the free list is empty. The marking is that of Deutsch, Schorr and Waite (Algorithm 2.3.5E): the depth-first visit keeps its path in the fields of the cells themselves, reversing each pointer it follows and restoring it on the way back, with one bit per cell telling which field holds the reversed pointer; it needs no stack, which a collector cannot count on when the memory is exhausted, and takes time linear in the cells reached. A recursive marking with a stack is kept for the comparison.

The contracts [see File Contract.h]: an address is a cell of the heap; cons() needs a free cell after a collection; collect() ensures that it frees exactly the cells that are not reachable and leaves the fields of the others as they were, an audit. The operations are defined in CellHeap.tpp.

    1. Knuth, The Art of Computer Programming, vol. 1, 3rd ed., Addison-Wesley, 1997, section 2.3.5

  1. Schorr, W. M. Waite, An efficient machine-independent procedure for garbage collection in various list structures, Communications of the ACM 10(8), 501-506, 1967, doi:10.1145/363534.363554

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes