Cheney's algorithm: Difference between revisions

Revision as of 18:54, 1 April 2016

Revision as of 03:06, 6 April 2016

Line 19:

==Sample algorithm==

<source>

initialize() =

tospace = 0

fromspace = N/2

allocPtr = tospace

</source>

<source>

allocate(n) =

If allocPtr + n > tospace + N/2

collect()

collect()

EndIf

EndIf
If allocPtr + n > tospace + N/2

fail “insufficient memory”

EndIf

o = allocPtr

allocPtr = allocPtr + n

return o

</source>

<source>

collect() =

collect() =

swap( fromspace, tospace )

allocPtr = swap( fromspace, tospace )

allocPtr = tospace

root = copy(root)

</source>

<source>

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’

ForEach reference r from o’

r = copy(r)

EndForEach

EndIf

EndIf

return forwarding-address(o)

</source>

== Semispace ==