\begin{slide}{Stop-and-copy (Plan)}

Plan:
\begin{itemize}
\item zwei Speicherbereiche (Fromspace, Tospace)
\item Allokation im Fromspace
\item wenn Fromspace voll, kopiere lebende Zellen in Tospace
  und vertausche dann Fromspace $\leftrightarrow$ Tospace
\end{itemize}

auch hier: Verwaltung ohne Zusatzspeicher (Stack)

C. J. Cheney: 
\emph{A nonrecursive list compacting algorithm},
Communications of the ACM, 13(11):677--678, 1970.

\end{slide}

\begin{slide}{Stop-and-copy (Invariante)}

fromspace, tospace $:$ array [ 0 \dots $N$ ] of cell

Variablen: $0 \le \text{scan} \le \text{free} \le N$

einige Zellen im fromspace enthalten Weiterleitung
($=$ Adresse im tospace)

Invarianten:
\begin{itemize}
\item $\text{scan} \le \text{free}$
\item Zellen aus tospace [0 \dots \text{scan}-1] 
  zeigen in tospace
\item Zellen aus tospace [\text {scan} \dots \text{free}-1] 
  zeigen in fromspace
\item
  wenn man in $G$ (mit Wurzel tospace[0])
  allen Weiterleitungen folgt,
  erhält man isomorphes Abbild von $G_0$ (mit Wurzel fromspace[0]).
\end{itemize}

\end{slide}


\begin{slide}{Stop-and-copy (Ablauf)}

  \begin{itemize}\itemsep 0pt
  \item pre: tospace[0] $=$ Wurzel, scan $=$ 0,free $=$ 1.
  \item post: scan $=$ free
  \end{itemize}

Schritt: while scan $<$ free:
\begin{itemize}\itemsep 0pt
\item für alle Zeiger $p$ in tospace[scan]:
  \begin{itemize}\itemsep 0pt
  \item falls fromspace[$p$] weitergeleitet auf $q$,
    ersetze $p$ durch $q$.
  \item falls keine Weiterleitung
    \begin{itemize}\itemsep 0pt
    \item  kopiere fromspace[$p$]    nach tospace[free], 
    \item Weiterleitung fromspace[$p$] nach free eintragen,
    \item ersetze $p$ durch free, erhöhe free.
    \end{itemize}
  \end{itemize}
\item  erhöhe scan.
\end{itemize}

Besucht Knoten in Reihenfolge einer Breitensuche.

\end{slide}

\begin{slide}{Stop-and-copy (Eigenschaften)}

  \begin{itemize}
  \item benötigt \glqq doppelten\grqq\ Speicherplatz
  \item Laufzeit $\sim$ $|$ lebender Speicher $|$
  \item kompaktierend
  \item Breitensuch-Reihenfolge zerstört Lokalität.
  \end{itemize}

\end{slide}
