Cheney's algorithm: Difference between revisions

Revision as of 01:10, 8 November 2023

Latest revision as of 22:06, 9 July 2025

(2 intermediate revisions by one other user not shown)

Line 1:

{{Short description|Computer software algorithm}}

{{Use dmy dates|date=September 2021}}

{{more footnotes|date=April 2014}}

Line 15 ⟶ 16:

The forwarding pointer (sometimes called a "broken heart") is used only during the garbage collection process; when a reference to an object already in to-space (thus having a forwarding pointer in from-space) is found, the reference can be updated quickly simply by updating its pointer to match the forwarding pointer.

Because the strategy is to exhaust all live references, and then all references in referenced objects, this is known as a ''[[breadth-first]]'' list copying garbage collection scheme.

==Sample algorithm==

<pre>

initialize() =

tospace = N/2

fromspace = 0

allocPtr = fromspace

scanPtr = whatever -- only used during collection

</pre>

<pre>

allocate(n) =

If allocPtr + n > fromspace + N/2

collect()

EndIf

If allocPtr + n > fromspace + N/2

fail “insufficient memory”

EndIf

o = allocPtr

allocPtr = allocPtr + n

return o

</pre>

<pre>

collect() =

swap(fromspace, tospace)

allocPtr = fromspace

scanPtr = fromspace

-- 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

</pre>

<pre>

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)

</pre>

== Semispace ==