Cheney's algorithm: Difference between revisions

Revision as of 09:04, 22 February 2025

Latest revision as of 22:06, 9 July 2025

(One intermediate revision 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 16 ⟶ 17:

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