El método consiste en tener un contador asociado a cada celda que contenga
la cantidad de celdas **vivas** que apuntan a ésta. Es decir, es la
cardinalidad del conjunto de aristas que tienen por destino a la celda.
-Formalmente podemos definir el contador math:`rc(v)` (de *reference
+Formalmente podemos definir el contador :math:`rc(v)` (de *reference
counter* en inglés) de la siguiente manera:
.. math::
A continuación se presenta un ejemplo gráfico para facilitar la comprensión
del algoritmo. Por simplicidad se asumen celdas de tamaño fijo con dos
-punteros, ``left`` y ``right`` y se muestra el contador de referencias
-abajo del nombre de cada celda. Se parte con una pequeña estructura ya
-construída y se muestra como opera el algoritmo al eliminar o cambiar una
-referencia (cambios en la conectividad del grafo).
+punteros, ``left`` (``l``) y ``right`` (``r``) y se muestra el contador de
+referencias abajo del nombre de cada celda. Se parte con una pequeña
+estructura ya construída y se muestra como opera el algoritmo al eliminar
+o cambiar una referencia (cambios en la conectividad del grafo). En un
+comienzo todas las celdas son accesibles desde el *root set* por lo tanto
+son todas parte del *live set*.
Se comienza por eliminar la referencia de ``r0`` a ``h1``, que determina
que ``h1`` se convirtió en *basura* (figura :vref:`fig:gc-rc-rm-1`). Esto
.. subfig::
- Se ejecuta ``update(r0, null)``.
+ Estado inicial del grafo de conectividad.
.. digraph:: g3_1
margin = 0;
ratio = fill;
- size = "3.0,3.8";
+ size = "1.9,2.6";
+ edge [ color = gray40 ];
+ node [
+ shape = record,
+ width = 0,
+ height = 0,
+ style = filled,
+ fillcolor = gray25,
+ fontcolor = white
+ ];
+
+ subgraph cluster_all {
+
+ root [
+ label = "root\nset|<r0> r0|<r1> r1",
+ style = filled,
+ fillcolor = gray96,
+ fontcolor = black,
+ ];
+
+ h1 [ label = "h1\n1|<l> l|<r> r" ];
+ h2 [ label = "h2\n2|<l> l|<r> r" ];
+ h3 [ label = "h3\n2|<l> l|<r> r" ];
+ h4 [ label = "h4\n1|<l> l|<r> r" ];
+ h5 [ label = "h5\n1|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
+
+ root:r0 -> h1;
+ root:r1 -> h3;
+ h1:l -> h2;
+ h1:r -> h3;
+ h2:l -> h4;
+ h2:r -> h5;
+ h3:l -> h2;
+ h3:r -> h6;
+
+ }
+
+ .. subfig::
+
+ Al ejecutarse ``update(r0, null)``, se comienza por visitar la celda
+ ``h1``.
+
+ .. digraph:: g3_2
+
+ margin = 0;
+ ratio = fill;
+ size = "1.9,2.6";
edge [ color = gray40 ];
node [
shape = record,
fontcolor = black,
];
- h1 [ label = "h1\n1|<l> left|<r> right" ];
- h2 [ label = "h2\n2|<l> left|<r> right" ];
- h3 [ label = "h3\n2|<l> left|<r> right" ];
- h4 [ label = "h4\n1|<l> left|<r> right" ];
- h5 [ label = "h5\n1|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
+ h1 [ label = "h1\n1|<l> l|<r> r" ];
+ h2 [ label = "h2\n2|<l> l|<r> r" ];
+ h3 [ label = "h3\n2|<l> l|<r> r" ];
+ h4 [ label = "h4\n1|<l> l|<r> r" ];
+ h5 [ label = "h5\n1|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
root:r0 -> h1 [ style = bold, color = black ];
root:r1 -> h3;
.. subfig::
- Se decrementa el contador de ``h1`` y éste queda en 0 (indicando
- que es basura). Esto desencadena la eliminación de las referencias
- ``h1.left`` y ``h1.right``.
+ Se decrementa el contador de ``h1`` quedando en 0 (pasa a ser
+ *basura*). Se elimina primero ``h1.l`` y luego ``h1.r``.
- .. digraph:: g3_2
+ .. digraph:: g3_3
margin = 0;
ratio = fill;
- size = "3.0,3.8";
+ size = "1.9,2.6";
edge [ color = gray40 ];
node [
shape = record,
h1;
};
- h1 [ label = "h1\n0|<l> left|<r> right" ];
- h2 [ label = "h2\n2|<l> left|<r> right" ];
- h3 [ label = "h3\n2|<l> left|<r> right" ];
- h4 [ label = "h4\n1|<l> left|<r> right" ];
- h5 [ label = "h5\n1|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n2|<l> l|<r> r" ];
+ h3 [ label = "h3\n2|<l> l|<r> r" ];
+ h4 [ label = "h4\n1|<l> l|<r> r" ];
+ h5 [ label = "h5\n1|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
root:r0 -> h1 [ style = invis ];
root:r1 -> h3;
}
+
.. fig:: fig:gc-rc-rm-2
Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2).
.. subfig::
- Se decrementa el contador de ``h2`` pero no queda en 0, por lo
- tanto no es necesario descender a sus hijas; se continúa con
- ``h3``.
+ Se decrementa el contador de ``h2`` pero no queda en 0 (permanece en
+ el *live set*).
- .. digraph:: g3_3
+ .. digraph:: g3_4
margin = 0;
ratio = fill;
- size = "3.0,3.8";
+ size = "1.9,2.6";
edge [ color = gray40 ];
node [
shape = record,
h1;
};
- h1 [ label = "h1\n0|<l> left|<r> right" ];
- h2 [ label = "h2\n1|<l> left|<r> right" ];
- h3 [ label = "h3\n2|<l> left|<r> right" ];
- h4 [ label = "h4\n1|<l> left|<r> right" ];
- h5 [ label = "h5\n1|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h3 [ label = "h3\n2|<l> l|<r> r" ];
+ h4 [ label = "h4\n1|<l> l|<r> r" ];
+ h5 [ label = "h5\n1|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
root:r0 -> h1 [ style = invis ];
root:r1 -> h3;
.. subfig::
- El contador de ``h3`` tampoco queda en 0; no hay necesidad de
- descender a sus hijas y finaliza el proceso.
+ El contador de ``h3`` tampoco queda en 0, sigue en el *live set*.
- .. digraph:: g3_4
+ .. digraph:: g3_5
margin = 0;
ratio = fill;
- size = "3.0,3.8";
+ size = "1.9,2.6";
edge [ color = gray40 ];
node [
shape = record,
h1;
};
- h1 [ label = "h1\n0|<l> left|<r> right" ];
- h2 [ label = "h2\n1|<l> left|<r> right" ];
- h3 [ label = "h3\n1|<l> left|<r> right" ];
- h4 [ label = "h4\n1|<l> left|<r> right" ];
- h5 [ label = "h5\n1|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h3 [ label = "h3\n1|<l> l|<r> r" ];
+ h4 [ label = "h4\n1|<l> l|<r> r" ];
+ h5 [ label = "h5\n1|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
root:r0 -> h1 [ style = invis ];
root:r1 -> h3;
Luego se cambia una referencia (en vez de eliminarse) realizándose la
-operación ``update(h3.left, h5)``. Para esto primero se incrementa el
-contador de referencias de ``h5`` para evitar confundirlo accidentalmente
-con *basura* (figura :vref:`fig:gc-rc-up-1`). Luego se procede
-a decrementar el contador de ``h2`` que queda en 0 (transformándose en
-*basura*) y lo mismo pasa cuando se desciende a ``h4`` (figura
-:vref:`fig:gc-rc-up-2`). Finalmente se decrementa el contador de ``h5``
-pero como esta celda va a ser apuntada por ``h3`` (por la operación que
-está ejecutándose) sobrevive y permanece en el *live set*. Finalmente se
-termina de actualizar la referencia ``h3.left`` para que apunte a ``h5``
-(figura :vref:`fig:gc-rc-up-3`).
+operación ``update(h3.l, h5)``. Para esto primero se incrementa el contador
+de referencias de ``h5`` para evitar confundirlo accidentalmente con
+*basura* si se elimina alguna celda que apuntaba a ésta. Luego se procede
+a decrementar el contador de ``h2`` que queda en 0, transformándose en
+*basura* (figura :vref:`fig:gc-rc-up-1`). Lo mismo pasa cuando se desciende
+a ``h4``, pero al descender a ``h5`` y decrementar el contador, éste sigue
+siendo mayor que 0 (pues ``h3`` va a apuntar a ``h5``) así que permanece en
+el *live set*. Finalmente se termina de actualizar la referencia ``h3.l``
+para que apunte a ``h5`` (figura :vref:`fig:gc-rc-up-3`).
.. fig:: fig:gc-rc-up-1
- TODO Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 1).
+ Cambio en la referencia ``h2.l`` :math:`\to` ``h2`` a ``h2.l``
+ :math:`\to` ``h5`` (parte 1).
.. subfig::
- TODO
+ Comienza ``update(h3.l, h5)``, se incrementa el contador de ``h5``.
.. digraph:: g4_1
margin = 0;
ratio = fill;
- size = "3.0,3.8";
+ size = "1.9,2.6";
edge [ color = gray40 ];
node [
shape = record,
h1;
};
- h1 [ label = "h1\n0|<l> left|<r> right" ];
- h2 [ label = "h2\n1|<l> left|<r> right" ];
- h3 [ label = "h3\n1|<l> left\n*|<r> right" ];
- h4 [ label = "h4\n1|<l> left|<r> right" ];
- h5 [ label = "h5\n1|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+ h4 [ label = "h4\n1|<l> l|<r> r" ];
+ h5 [ label = "h5\n2|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
root:r0 -> h1 [ style = invis ];
h1:l -> h2 [ style = invis ];
root:r1 -> h3;
h2:l -> h4;
h2:r -> h5;
- h3:l -> h2 [ style = bold, color = black ];
+ h3:l -> h2;
+ h3:l -> h5 [ style = dotted, color = black ];
h3:r -> h6;
}
.. subfig::
- TODO
+ Luego se procede a visitar las hijas de ``h3``, comenzando por ``h2``.
.. digraph:: g4_2
margin = 0;
ratio = fill;
- size = "3.0,3.8";
+ size = "1.9,2.6";
edge [ color = gray40 ];
node [
shape = record,
h1;
};
- h1 [ label = "h1\n0|<l> left|<r> right" ];
- h2 [ label = "h2\n1|<l> left|<r> right" ];
- h3 [ label = "h3\n1|<l> left\n*|<r> right" ];
- h4 [ label = "h4\n1|<l> left|<r> right" ];
- h5 [ label = "h5\n2|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+ h4 [ label = "h4\n1|<l> l|<r> r" ];
+ h5 [ label = "h5\n2|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
root:r0 -> h1 [ style = invis ];
h1:l -> h2 [ style = invis ];
}
-.. fig:: fig:gc-rc-up-2
-
- TODO Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 2).
-
.. subfig::
- TODO
+ Se decrementa el contador de ``h2`` y queda en 0 (pasa a ser
+ *basura*). Se eliminan las referencias a las hijas.
.. digraph:: g4_3
margin = 0;
ratio = fill;
- size = "3.0,3.8";
+ size = "1.9,2.6";
edge [ color = gray40 ];
node [
shape = record,
h1; h2;
};
- h1 [ label = "h1\n0|<l> left|<r> right" ];
- h2 [ label = "h2\n0|<l> left|<r> right" ];
- h3 [ label = "h3\n1|<l> left\n*|<r> right" ];
- h4 [ label = "h4\n1|<l> left|<r> right" ];
- h5 [ label = "h5\n2|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+ h4 [ label = "h4\n1|<l> l|<r> r" ];
+ h5 [ label = "h5\n2|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
root:r0 -> h1 [ style = invis ];
h1:l -> h2 [ style = invis ];
}
+
+.. fig:: fig:gc-rc-up-2
+
+ Cambio en la referencia ``h2.l`` :math:`\to` ``h2`` a ``h2.l``
+ :math:`\to` ``h5`` (parte 2).
+
.. subfig::
- TODO
+ Se decrementa el contador de ``h4`` quedando en 0, pasa a ser
+ *basura*. Se continúa con ``h5``.
.. digraph:: g4_4
margin = 0;
ratio = fill;
- size = "3.0,3.8";
+ size = "1.9,2.6";
edge [ color = gray40 ];
node [
shape = record,
h1; h2; h4;
};
- h1 [ label = "h1\n0|<l> left|<r> right" ];
- h2 [ label = "h2\n0|<l> left|<r> right" ];
- h3 [ label = "h3\n1|<l> left\n*|<r> right" ];
- h4 [ label = "h4\n0|<l> left|<r> right" ];
- h5 [ label = "h5\n2|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+ h4 [ label = "h4\n0|<l> l|<r> r" ];
+ h5 [ label = "h5\n2|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
root:r0 -> h1 [ style = invis ];
h1:l -> h2 [ style = invis ];
}
-.. fig:: fig:gc-rc-up-3
-
- TODO Eliminación de la referencia ``r0`` :math:`\to` ``h1`` (parte 3).
-
.. subfig::
- TODO
+ Se decrementa el contador de ``h5`` pero sigue siendo mayor que 0.
.. digraph:: g4_5
margin = 0;
ratio = fill;
- size = "3.0,3.8";
+ size = "1.9,2.6";
edge [ color = gray40 ];
node [
shape = record,
h1; h2; h4;
};
- h1 [ label = "h1\n0|<l> left|<r> right" ];
- h2 [ label = "h2\n0|<l> left|<r> right" ];
- h3 [ label = "h3\n1|<l> left\n*|<r> right" ];
- h4 [ label = "h4\n0|<l> left|<r> right" ];
- h5 [ label = "h5\n1|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n1|<l> l|<r> r" ];
+ h3 [ label = "h3\n1|<l> l\n*|<r> r" ];
+ h4 [ label = "h4\n0|<l> l|<r> r" ];
+ h5 [ label = "h5\n1|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
root:r0 -> h1 [ style = invis ];
h1:l -> h2 [ style = invis ];
.. subfig::
- TODO
+ Se termina por actualizar la referencia de ``h3.l`` para que apunte
+ a ``h5``.
.. digraph:: g4_6
margin = 0;
ratio = fill;
- size = "3.0,3.8";
+ size = "1.9,2.6";
edge [ color = gray40 ];
node [
shape = record,
h1; h2; h4;
};
- h1 [ label = "h1\n0|<l> left|<r> right" ];
- h1 [ label = "h1\n0|<l> left|<r> right" ];
- h2 [ label = "h2\n0|<l> left|<r> right" ];
- h3 [ label = "h3\n1|<l> left|<r> right" ];
- h4 [ label = "h4\n0|<l> left|<r> right" ];
- h5 [ label = "h5\n1|<l> left|<r> right" ];
- h6 [ label = "h6\n1|<l> left|<r> right" ];
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h1 [ label = "h1\n0|<l> l|<r> r" ];
+ h2 [ label = "h2\n0|<l> l|<r> r" ];
+ h3 [ label = "h3\n1|<l> l|<r> r" ];
+ h4 [ label = "h4\n0|<l> l|<r> r" ];
+ h5 [ label = "h5\n1|<l> l|<r> r" ];
+ h6 [ label = "h6\n1|<l> l|<r> r" ];
root:r0 -> h1 [ style = invis ];
h1:l -> h2 [ style = invis ];
projects / z.facultad / 75.00 / informe.git / blobdiff