Una vez que no hay más celdas grises, tenemos la garantía de que las celdas
negras serán el *live set* y las celdas blancas *basura*. Esto se debe a que
siempre se mantiene esta invariante: **ninguna celda negra apunta directamente
-a una celda blanca**. Las celdas blancas siempre son apuntadas por celdas
-blancas o grises. Entonces, siempre que el conjunto de celdas grises sea
-vacío, no habrán celdas negras conectadas a blancas, siendo las celdas blancas
-*basura*.
+a una celda blanca** (considerando como atómica la operación de pintar una
+celda de negro y a sus hijas directas de gris). Las celdas blancas siempre son
+apuntadas por celdas blancas o grises. Entonces, siempre que el conjunto de
+celdas grises sea vacío, no habrán celdas negras conectadas a blancas, siendo
+las celdas blancas *basura*.
El algoritmo básico para marcar con tres colores es el siguiente (asumiendo
que todas las celdas parten pintadas de blanco, es decir, el conjunto blanco
};
h1 [ label = "h1\n0|<l> l|<r> r" ];
- h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h2 [ label = "h2\n0|<l> l|<r> r" ];
h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
h4 [ label = "h4\n1|<l> l|<r> r" ];
h5 [ label = "h5\n2|<l> l|<r> r" ];
};
h1 [ label = "h1\n0|<l> l|<r> r" ];
- h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h2 [ label = "h2\n0|<l> l|<r> r" ];
h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
h4 [ label = "h4\n0|<l> l|<r> r" ];
h5 [ label = "h5\n2|<l> l|<r> r" ];
};
h1 [ label = "h1\n0|<l> l|<r> r" ];
- h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h2 [ label = "h2\n0|<l> l|<r> r" ];
h3 [ label = "h3\n2|<l> l\n*|<r> r" ];
h4 [ label = "h4\n0|<l> l|<r> r" ];
h5 [ label = "h5\n1|<l> l|<r> r" ];
allocator*, ya que la organización del *heap* y la forma de asignar memoria es
parte fundamental de este algoritmo. Se asume que ya hay dos áreas de memoria
del mismo tamaño destinadas al *Fromspace* y *Tospace*, y la existencia de
-4 variables: ``fromspace`` (que apunta a la base del *Fromspace*), ``tospace``
-(que apunta a la base del *Tospace*), ``spacesize`` (que contiene el tamaño de
-un semi-espacio) y ``free`` (que apunta al lugar del *Fromspace* donde
-comienza la memoria libre). También vale aclarar que este algoritmo soporta
-inherentemente celdas de tamaño variable, por lo que los servicios ``alloc()``
-y ``new()`` [#gccopynew]_ reciben como parámetro el tamaño de la celda
-a asignar::
+4 variables globales: ``fromspace`` (que apunta a la base del *Fromspace*),
+``tospace`` (que apunta a la base del *Tospace*), ``spacesize`` (que contiene
+el tamaño de un semi-espacio) y ``free`` (que apunta al lugar del *Fromspace*
+donde comienza la memoria libre). También vale aclarar que este algoritmo
+soporta inherentemente celdas de tamaño variable, por lo que los servicios
+``alloc()`` y ``new()`` [#gccopynew]_ reciben como parámetro el tamaño de la
+celda a asignar::
function alloc(size) is
if free + size > fromspace + spacesize
function copy(cell) is
if cell.forwarding_address is null
cell.forwarding_address = free
+ cell.copy_to(free)
free = free + cell.size
foreach child in cell
child = copy(child)