X-Git-Url: https://git.llucax.com/z.facultad/75.00/informe.git/blobdiff_plain/66a118f6c023835898f113380cfa401199b490a3..b181be56b09270908bde048ba43b4f9d217fdd16:/source/gc.rst?ds=inline diff --git a/source/gc.rst b/source/gc.rst index c37672f..2da1a95 100644 --- a/source/gc.rst +++ b/source/gc.rst @@ -805,10 +805,12 @@ Ejemplo 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 @@ -823,13 +825,60 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el .. 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| r1", + style = filled, + fillcolor = gray96, + fontcolor = black, + ]; + + h1 [ label = "h1\n1| l| r" ]; + h2 [ label = "h2\n2| l| r" ]; + h3 [ label = "h3\n2| l| r" ]; + h4 [ label = "h4\n1| l| r" ]; + h5 [ label = "h5\n1| l| r" ]; + h6 [ label = "h6\n1| l| 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, @@ -849,12 +898,12 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el fontcolor = black, ]; - h1 [ label = "h1\n1| left| right" ]; - h2 [ label = "h2\n2| left| right" ]; - h3 [ label = "h3\n2| left| right" ]; - h4 [ label = "h4\n1| left| right" ]; - h5 [ label = "h5\n1| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; + h1 [ label = "h1\n1| l| r" ]; + h2 [ label = "h2\n2| l| r" ]; + h3 [ label = "h3\n2| l| r" ]; + h4 [ label = "h4\n1| l| r" ]; + h5 [ label = "h5\n1| l| r" ]; + h6 [ label = "h6\n1| l| r" ]; root:r0 -> h1 [ style = bold, color = black ]; root:r1 -> h3; @@ -869,15 +918,14 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el .. 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, @@ -902,12 +950,12 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h1; }; - h1 [ label = "h1\n0| left| right" ]; - h2 [ label = "h2\n2| left| right" ]; - h3 [ label = "h3\n2| left| right" ]; - h4 [ label = "h4\n1| left| right" ]; - h5 [ label = "h5\n1| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n2| l| r" ]; + h3 [ label = "h3\n2| l| r" ]; + h4 [ label = "h4\n1| l| r" ]; + h5 [ label = "h5\n1| l| r" ]; + h6 [ label = "h6\n1| l| r" ]; root:r0 -> h1 [ style = invis ]; root:r1 -> h3; @@ -920,21 +968,21 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el } + .. 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, @@ -959,12 +1007,12 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h1; }; - h1 [ label = "h1\n0| left| right" ]; - h2 [ label = "h2\n1| left| right" ]; - h3 [ label = "h3\n2| left| right" ]; - h4 [ label = "h4\n1| left| right" ]; - h5 [ label = "h5\n1| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n1| l| r" ]; + h3 [ label = "h3\n2| l| r" ]; + h4 [ label = "h4\n1| l| r" ]; + h5 [ label = "h5\n1| l| r" ]; + h6 [ label = "h6\n1| l| r" ]; root:r0 -> h1 [ style = invis ]; root:r1 -> h3; @@ -979,14 +1027,13 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el .. 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, @@ -1011,12 +1058,12 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el h1; }; - h1 [ label = "h1\n0| left| right" ]; - h2 [ label = "h2\n1| left| right" ]; - h3 [ label = "h3\n1| left| right" ]; - h4 [ label = "h4\n1| left| right" ]; - h5 [ label = "h5\n1| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n1| l| r" ]; + h3 [ label = "h3\n1| l| r" ]; + h4 [ label = "h4\n1| l| r" ]; + h5 [ label = "h5\n1| l| r" ]; + h6 [ label = "h6\n1| l| r" ]; root:r0 -> h1 [ style = invis ]; root:r1 -> h3; @@ -1031,31 +1078,31 @@ conduce al decremento del contador de ``h2`` y ``h3`` que permanecen en el 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, @@ -1080,12 +1127,12 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5`` h1; }; - h1 [ label = "h1\n0| left| right" ]; - h2 [ label = "h2\n1| left| right" ]; - h3 [ label = "h3\n1| left\n*| right" ]; - h4 [ label = "h4\n1| left| right" ]; - h5 [ label = "h5\n1| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n1| l| r" ]; + h3 [ label = "h3\n1| l\n*| r" ]; + h4 [ label = "h4\n1| l| r" ]; + h5 [ label = "h5\n2| l| r" ]; + h6 [ label = "h6\n1| l| r" ]; root:r0 -> h1 [ style = invis ]; h1:l -> h2 [ style = invis ]; @@ -1093,20 +1140,21 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5`` 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, @@ -1131,12 +1179,12 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5`` h1; }; - h1 [ label = "h1\n0| left| right" ]; - h2 [ label = "h2\n1| left| right" ]; - h3 [ label = "h3\n1| left\n*| right" ]; - h4 [ label = "h4\n1| left| right" ]; - h5 [ label = "h5\n2| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n1| l| r" ]; + h3 [ label = "h3\n1| l\n*| r" ]; + h4 [ label = "h4\n1| l| r" ]; + h5 [ label = "h5\n2| l| r" ]; + h6 [ label = "h6\n1| l| r" ]; root:r0 -> h1 [ style = invis ]; h1:l -> h2 [ style = invis ]; @@ -1150,19 +1198,16 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5`` } -.. 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, @@ -1187,12 +1232,12 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5`` h1; h2; }; - h1 [ label = "h1\n0| left| right" ]; - h2 [ label = "h2\n0| left| right" ]; - h3 [ label = "h3\n1| left\n*| right" ]; - h4 [ label = "h4\n1| left| right" ]; - h5 [ label = "h5\n2| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n1| l| r" ]; + h3 [ label = "h3\n1| l\n*| r" ]; + h4 [ label = "h4\n1| l| r" ]; + h5 [ label = "h5\n2| l| r" ]; + h6 [ label = "h6\n1| l| r" ]; root:r0 -> h1 [ style = invis ]; h1:l -> h2 [ style = invis ]; @@ -1206,15 +1251,22 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5`` } + +.. 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, @@ -1239,12 +1291,12 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5`` h1; h2; h4; }; - h1 [ label = "h1\n0| left| right" ]; - h2 [ label = "h2\n0| left| right" ]; - h3 [ label = "h3\n1| left\n*| right" ]; - h4 [ label = "h4\n0| left| right" ]; - h5 [ label = "h5\n2| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n1| l| r" ]; + h3 [ label = "h3\n1| l\n*| r" ]; + h4 [ label = "h4\n0| l| r" ]; + h5 [ label = "h5\n2| l| r" ]; + h6 [ label = "h6\n1| l| r" ]; root:r0 -> h1 [ style = invis ]; h1:l -> h2 [ style = invis ]; @@ -1258,19 +1310,15 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5`` } -.. 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, @@ -1295,12 +1343,12 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5`` h1; h2; h4; }; - h1 [ label = "h1\n0| left| right" ]; - h2 [ label = "h2\n0| left| right" ]; - h3 [ label = "h3\n1| left\n*| right" ]; - h4 [ label = "h4\n0| left| right" ]; - h5 [ label = "h5\n1| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n1| l| r" ]; + h3 [ label = "h3\n1| l\n*| r" ]; + h4 [ label = "h4\n0| l| r" ]; + h5 [ label = "h5\n1| l| r" ]; + h6 [ label = "h6\n1| l| r" ]; root:r0 -> h1 [ style = invis ]; h1:l -> h2 [ style = invis ]; @@ -1316,13 +1364,14 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5`` .. 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, @@ -1347,13 +1396,13 @@ termina de actualizar la referencia ``h3.left`` para que apunte a ``h5`` h1; h2; h4; }; - h1 [ label = "h1\n0| left| right" ]; - h1 [ label = "h1\n0| left| right" ]; - h2 [ label = "h2\n0| left| right" ]; - h3 [ label = "h3\n1| left| right" ]; - h4 [ label = "h4\n0| left| right" ]; - h5 [ label = "h5\n1| left| right" ]; - h6 [ label = "h6\n1| left| right" ]; + h1 [ label = "h1\n0| l| r" ]; + h1 [ label = "h1\n0| l| r" ]; + h2 [ label = "h2\n0| l| r" ]; + h3 [ label = "h3\n1| l| r" ]; + h4 [ label = "h4\n0| l| r" ]; + h5 [ label = "h5\n1| l| r" ]; + h6 [ label = "h6\n1| l| r" ]; root:r0 -> h1 [ style = invis ]; h1:l -> h2 [ style = invis ];