whatever -- only used during collection allocate(n) = If allocPtr + n > fromspace + tospace collect() EndIf If allocPtr + n > fromspace + tospace fail “insufficient memory” EndIf o = allocPtr allocPtr = allocPtr + n return o collect() = swap(fromspace, tospace) allocPtr = tospace scanPtr = tospace -- scan every root you've got ForEach root in the stack -- or elsewhere root = copy(root) EndForEach -- scan objects in the to-space (including objects added by this loop) While scanPtr < allocPtr ForEach reference r from o (pointed to by scanPtr) r = copy(r) EndForEach scanPtr = scanPtr + o.size() -- points to the next object in the to-space, if any EndWhile copy(o) = If o has no forwarding address o' = allocPtr allocPtr = allocPtr + size(o) copy the contents of o to o' forwarding-address(o) = o' EndIf return forwarding-address(o) Semispace Cheney based his work on the semispace garbage collector, which was published a year earlier by R.R. Fenichel and J.C. Yochelson. Equivalence to tri-color abstraction Cheney's algorithm is an example of a tri-color marking garbage collector. The first member of the gray set is the stack itself. Objects referenced on the stack are copied into the to-space, which contains members of the black and gray sets. The algorithm moves any white objects (equivalent to objects in the from-space without forwarding pointers) to the gray set by copying them to the to-space. Objects that are between the scanning pointer and the free-space pointer on the to-space area are members of the gray set still to be scanned. Objects below the scanning pointer belong to the black set. Objects are moved to the black set by simply moving the scanning pointer over them. When the scanning pointer reaches the free-space pointer, the gray set is empty, and the algorithm ends. References External links - Android uses a variant of the semi-space garbage collector. Automatic memory management