Diferencias entre las revisiones 3 y 4
Versión 3 con fecha 2007-12-14 21:25:59
Tamaño: 34861
Comentario: 1° revision, ajustado el codigo a guia de estilo y otros cambios cosmeticos
Versión 4 con fecha 2008-12-04 08:48:56
Tamaño: 34968
Editor: localhost
Comentario: converted to 1.6 markup
Los textos eliminados se marcan así. Los textos añadidos se marcan así.
Línea 3: Línea 3:
[[TableOfContents()]] <<TableOfContents>>
Línea 28: Línea 28:
Para crear una tabla de dispersión se tiene que indicar la función de dispersión y la función que se utilizará para comparar dos claves. Estas dos funciones se deben pasar como parámetros a la función ''[#g_hash_table_new g_hash_table_new]''

[[Anchor(g_hash_table_new)]]
Para crear una tabla de dispersión se tiene que indicar la función de dispersión y la función que se utilizará para comparar dos claves. Estas dos funciones se deben pasar como parámetros a la función ''[[#g_hash_table_new|g_hash_table_new]]''

<<Anchor(g_hash_table_new)>>
Línea 51: Línea 51:
[[Anchor(g_hash_table_new_full)]] <<Anchor(g_hash_table_new_full)>>
Línea 59: Línea 59:
La función ''[#g_hash_table_new_full g_hash_table_new_full]'' es muy parecida a ''[#g_hash_table_new g_hash_table_new]'', pero a diferencia de esta última, introduce la utilización de dos nuevas funciones, la primera de ellas para de liberar la memoria asignada para la clave y la segunda es usada para liberar la memoria asignada para el valor, ambas funciones son utilizadas al eliminarse una entrada de la tabla de dispersión, y en ambos casos pueden ser reemplazadas por `NULL`, si no se deseara proveer de dichas funciones. La función ''[[#g_hash_table_new_full|g_hash_table_new_full]]'' es muy parecida a ''[[#g_hash_table_new|g_hash_table_new]]'', pero a diferencia de esta última, introduce la utilización de dos nuevas funciones, la primera de ellas para de liberar la memoria asignada para la clave y la segunda es usada para liberar la memoria asignada para el valor, ambas funciones son utilizadas al eliminarse una entrada de la tabla de dispersión, y en ambos casos pueden ser reemplazadas por `NULL`, si no se deseara proveer de dichas funciones.
Línea 71: Línea 71:
Ahora se pasará a describir las funciones de manipulación de este TAD. Para añadir y eliminar elementos de una tabla se dispone de estas dos funciones: ''[#g_hash_table_insert g_hash_table_insert]'' y ''[#g_hash_table_remove g_hash_table_remove]''. La primera insertará un valor en la tabla hash y le indicará la clave con la que después podrá ser referenciado. En cuanto a la segunda, borrará el valor que corresponda a la clave que se le pase como parámetro a la función.

[[Anchor(g_hash_table_insert)]]
Ahora se pasará a describir las funciones de manipulación de este TAD. Para añadir y eliminar elementos de una tabla se dispone de estas dos funciones: ''[[#g_hash_table_insert|g_hash_table_insert]]'' y ''[[#g_hash_table_remove|g_hash_table_remove]]''. La primera insertará un valor en la tabla hash y le indicará la clave con la que después podrá ser referenciado. En cuanto a la segunda, borrará el valor que corresponda a la clave que se le pase como parámetro a la función.

<<Anchor(g_hash_table_insert)>>
Línea 79: Línea 79:
[[Anchor(g_hash_table_remove)]] <<Anchor(g_hash_table_remove)>>
Línea 84: Línea 84:
En caso que se desee modificar el valor asociado a una clave, hay dos opciones a seguir en forma de funciones: ''[#g_hash_table_insert g_hash_table_insert]'' (vista anteriormente) o ''[#g_hash_table_replace g_hash_table_replace]''. La única diferencia entre ambas es qué pasa cuando la clave ya existe. En el caso de la primera, se conservará la clave antigua mientras que, en el caso de la segunda, se usará la nueva clave. Obsérvese que dos claves se consideran la misma si la función de comparación devuelve TRUE, aunque sean diferentes objetos.

[[Anchor(g_hash_table_replace)]]
En caso que se desee modificar el valor asociado a una clave, hay dos opciones a seguir en forma de funciones: ''[[#g_hash_table_insert|g_hash_table_insert]]'' (vista anteriormente) o ''[[#g_hash_table_replace|g_hash_table_replace]]''. La única diferencia entre ambas es qué pasa cuando la clave ya existe. En el caso de la primera, se conservará la clave antigua mientras que, en el caso de la segunda, se usará la nueva clave. Obsérvese que dos claves se consideran la misma si la función de comparación devuelve TRUE, aunque sean diferentes objetos.

<<Anchor(g_hash_table_replace)>>
Línea 94: Línea 94:
Llegados a este punto, en el que se ha explicado como insertar, borrar y modificar elementos dentro de una tabla de este tipo, parece obvio que el siguiente paso es cómo conseguir encontrar información dentro de una tabla de dispersión. Para ello se dispone de la función ''[#g_hash_table_lookup g_hash_table_lookup]''. Esta función tiene un funcionamiento muy simple al igual que las funciones anteriormente explicadas. Lo único que necesita es que se le pase como parámetro la tabla de dispersión y la clave que desea buscar en la misma y la función devolverá un puntero al valor asociado a la clave en caso de existir o el valor `NULL` en caso de no existir.

[[Anchor(g_hash_table_lookup)]]
Llegados a este punto, en el que se ha explicado como insertar, borrar y modificar elementos dentro de una tabla de este tipo, parece obvio que el siguiente paso es cómo conseguir encontrar información dentro de una tabla de dispersión. Para ello se dispone de la función ''[[#g_hash_table_lookup|g_hash_table_lookup]]''. Esta función tiene un funcionamiento muy simple al igual que las funciones anteriormente explicadas. Lo único que necesita es que se le pase como parámetro la tabla de dispersión y la clave que desea buscar en la misma y la función devolverá un puntero al valor asociado a la clave en caso de existir o el valor `NULL` en caso de no existir.

<<Anchor(g_hash_table_lookup)>>
Línea 103: Línea 103:
[[Anchor(g_hash_table_lookup_extended)]] <<Anchor(g_hash_table_lookup_extended)>>
Línea 141: Línea 141:
[[Anchor(g_tree_new)]] <<Anchor(g_tree_new)>>
Línea 146: Línea 146:
[[Anchor(g_tree_new_with_data)]] <<Anchor(g_tree_new_with_data)>>
Línea 152: Línea 152:
[[Anchor(g_tree_new_full)]] <<Anchor(g_tree_new_full)>>
Línea 162: Línea 162:
En caso de no utilizar la última función, es tarea del usuario liberar la memoria utilizada por claves y/o datos cuando se destruye el árbol o cuando se elimina algún dato del mismo utilizando ''[#g_tree_remove g_tree_remove]''.

Para destruir un árbol se utiliza la función ''[#g_tree_destroy g_tree_destroy]''.

[[Anchor(g_tree_destroy)]]
En caso de no utilizar la última función, es tarea del usuario liberar la memoria utilizada por claves y/o datos cuando se destruye el árbol o cuando se elimina algún dato del mismo utilizando ''[[#g_tree_remove|g_tree_remove]]''.

Para destruir un árbol se utiliza la función ''[[#g_tree_destroy|g_tree_destroy]]''.

<<Anchor(g_tree_destroy)>>
Línea 173: Línea 173:
Para insertar un nuevo elemento en el árbol se utiliza ''[#g_tree_insert g_tree_insert]'' o ''[#g_tree_replace g_tree_replace]''. La diferencia entre ambas vale sólo en el caso de que en el árbol ya exista una clave igual a la que se intenta agregar y sólo cuando, en la creación del árbol, se especificó una función de destrucción de claves. Para g_tree_insert la clave que se pasó como parámetro se destruye, llamando a `key_destroy_func` y la del árbol permanece inalterada. Para el caso de ''[#g_tree_replace g_tree_replace]'', la clave ya existente se destruye y se reemplaza por la nueva. En ambos casos, de existir el elemento, el dato anterior se destruye llamando a `value_destroy_func`, siempre que se haya especificado en la creación del árbol.

[[Anchor(g_tree_insert)]]
Para insertar un nuevo elemento en el árbol se utiliza ''[[#g_tree_insert|g_tree_insert]]'' o ''[[#g_tree_replace|g_tree_replace]]''. La diferencia entre ambas vale sólo en el caso de que en el árbol ya exista una clave igual a la que se intenta agregar y sólo cuando, en la creación del árbol, se especificó una función de destrucción de claves. Para g_tree_insert la clave que se pasó como parámetro se destruye, llamando a `key_destroy_func` y la del árbol permanece inalterada. Para el caso de ''[[#g_tree_replace|g_tree_replace]]'', la clave ya existente se destruye y se reemplaza por la nueva. En ambos casos, de existir el elemento, el dato anterior se destruye llamando a `value_destroy_func`, siempre que se haya especificado en la creación del árbol.

<<Anchor(g_tree_insert)>>
Línea 180: Línea 180:
[[Anchor(g_tree_replace)]] <<Anchor(g_tree_replace)>>
Línea 185: Línea 185:
`key` es la clave con la cual se recuperará el dato luego y `value` el dato en sí. Para eliminar un elemento del árbol se pueden utilizar ''[#g_tree_remove g_tree_remove]'' o ''[#g_tree_steal g_tree_steal]''. La diferencia entre ambas es que, si se invoca ''[#g_tree_steal g_tree_steal]'' no se destruyen la clave y el valor aunque se hayan especificado funciones para tal fin en la creación del árbol.

[[Anchor(g_tree_remove)]]
`key` es la clave con la cual se recuperará el dato luego y `value` el dato en sí. Para eliminar un elemento del árbol se pueden utilizar ''[[#g_tree_remove|g_tree_remove]]'' o ''[[#g_tree_steal|g_tree_steal]]''. La diferencia entre ambas es que, si se invoca ''[[#g_tree_steal|g_tree_steal]]'' no se destruyen la clave y el valor aunque se hayan especificado funciones para tal fin en la creación del árbol.

<<Anchor(g_tree_remove)>>
Línea 192: Línea 192:
[[Anchor(g_tree_steal)]] <<Anchor(g_tree_steal)>>
Línea 199: Línea 199:
Existen dos funciones para buscar en un árbol binario, similares a las utilizadas en tablas de hash: ''[#g_tree_lookup g_tree_lookup]'' y ''[#g_tree_lookup_extended g_tree_lookup_extended]''.

[[Anchor(g_tree_lookup)]]
Existen dos funciones para buscar en un árbol binario, similares a las utilizadas en tablas de hash: ''[[#g_tree_lookup|g_tree_lookup]]'' y ''[[#g_tree_lookup_extended|g_tree_lookup_extended]]''.

<<Anchor(g_tree_lookup)>>
Línea 208: Línea 208:
[[Anchor(g_tree_lookup_extended)]] <<Anchor(g_tree_lookup_extended)>>
Línea 216: Línea 216:
La versión extendida de la búsqueda es particularmente útil cuando se quiere eliminar un elemento del árbol sin destruirlo, utilizando la función ''[#g_tree_steal g_tree_steal]'' (p.e. para ser agregado a otro árbol).

Por último para recorrer todos los elementos de un árbol se utiliza ''[#g_tree_foreach g_tree_foreach]''. Los elementos son tomados en orden y pasados como parámetro a la función de iteración especificada.

[[Anchor(g_tree_foreach)]]
La versión extendida de la búsqueda es particularmente útil cuando se quiere eliminar un elemento del árbol sin destruirlo, utilizando la función ''[[#g_tree_steal|g_tree_steal]]'' (p.e. para ser agregado a otro árbol).

Por último para recorrer todos los elementos de un árbol se utiliza ''[[#g_tree_foreach|g_tree_foreach]]''. Los elementos son tomados en orden y pasados como parámetro a la función de iteración especificada.

<<Anchor(g_tree_foreach)>>
Línea 231: Línea 231:
Si dicha función devuelve TRUE, la iteración se interrumpe. data es el valor que se especificó como `user_data` en la función ''[#g_tree_foreach g_tree_foreach]''. Si dicha función devuelve TRUE, la iteración se interrumpe. data es el valor que se especificó como `user_data` en la función ''[[#g_tree_foreach|g_tree_foreach]]''.
Línea 255: Línea 255:
Para crear un nodo se utiliza ''[#g_node_new g_node_new]'':

[[Anchor(g_node_new)]]
Para crear un nodo se utiliza ''[[#g_node_new|g_node_new]]'':

<<Anchor(g_node_new)>>
Línea 264: Línea 264:
[[Anchor(g_node_insert)]] <<Anchor(g_node_insert)>>
Línea 269: Línea 269:
[[Anchor(g_node_insert_before)]] <<Anchor(g_node_insert_before)>>
Línea 274: Línea 274:
[[Anchor(g_node_insert_after)]] <<Anchor(g_node_insert_after)>>
Línea 279: Línea 279:
[[Anchor(g_node_append)]] <<Anchor(g_node_append)>>
Línea 284: Línea 284:
[[Anchor(g_node_prepend)]] <<Anchor(g_node_prepend)>>
Línea 290: Línea 290:
`sibling` es un nodo hijo de parent que se toma como referencia para insertar el nuevo nodo antes o después de él mismo. En ambos casos, ''[#g_node_insert_after g_node_insert_after]'' y ''[#g_node_insert_before g_node_insert_before]'', si `sibling` es `NULL`, el nuevo nodo se inserta al final de la lista de hijos.

Con ''[#g_node_n_children g_node_n_children]'' se obtiene la cantidad de hijos de un nodo y, a partir de este dato, se puede especificar una posición relativa dentro de la lista de hijos `position`. Las formas ''[#g_node_append g_node_append]'' y ''[#g_node_prepend g_node_prepend]'' agregan el nuevo nodo al final o al principio de la lista de hijos.
`sibling` es un nodo hijo de parent que se toma como referencia para insertar el nuevo nodo antes o después de él mismo. En ambos casos, ''[[#g_node_insert_after|g_node_insert_after]]'' y ''[[#g_node_insert_before|g_node_insert_before]]'', si `sibling` es `NULL`, el nuevo nodo se inserta al final de la lista de hijos.

Con ''[[#g_node_n_children|g_node_n_children]]'' se obtiene la cantidad de hijos de un nodo y, a partir de este dato, se puede especificar una posición relativa dentro de la lista de hijos `position`. Las formas ''[[#g_node_append|g_node_append]]'' y ''[[#g_node_prepend|g_node_prepend]]'' agregan el nuevo nodo al final o al principio de la lista de hijos.
Línea 296: Línea 296:
[[Anchor(g_node_insert_data)]] <<Anchor(g_node_insert_data)>>
Línea 301: Línea 301:
[[Anchor(g_node_insert_data_before)]] <<Anchor(g_node_insert_data_before)>>
Línea 306: Línea 306:
[[Anchor(g_node_append_data)]] <<Anchor(g_node_append_data)>>
Línea 311: Línea 311:
[[Anchor(g_node_prepend_data)]] <<Anchor(g_node_prepend_data)>>
Línea 318: Línea 318:
Al igual que con las listas, hay dos formas de quitar un dato de un árbol: ''[#g_tree_unlink g_tree_unlink]'' y ''[#g_tree_destroy g_tree_destroy]''.

[[Anchor(g_node_unlink)]]
Al igual que con las listas, hay dos formas de quitar un dato de un árbol: ''[[#g_tree_unlink|g_tree_unlink]]'' y ''[[#g_tree_destroy|g_tree_destroy]]''.

<<Anchor(g_node_unlink)>>
Línea 325: Línea 325:
[[Anchor(g_node_destroy)]] <<Anchor(g_node_destroy)>>
Línea 330: Línea 330:
''[#g_node_unlink g_node_unlink]'' quita el nodo especificado del árbol, resultando en un nuevo árbol que lo tiene como raíz. ''[#g_node_destroy g_node_destroy]'' no sólo elimina el nodo del árbol, sino que, además, libera toda la memoria utilizada por el nodo y por sus hijos. GLib, sin embargo, no tiene forma de liberar la memoria de los datos que contenían los nodos: eso es responsabilidad del usuario. ''[[#g_node_unlink|g_node_unlink]]'' quita el nodo especificado del árbol, resultando en un nuevo árbol que lo tiene como raíz. ''[[#g_node_destroy|g_node_destroy]]'' no sólo elimina el nodo del árbol, sino que, además, libera toda la memoria utilizada por el nodo y por sus hijos. GLib, sin embargo, no tiene forma de liberar la memoria de los datos que contenían los nodos: eso es responsabilidad del usuario.
Línea 338: Línea 338:
[[Anchor(g_node_n_nodes)]] <<Anchor(g_node_n_nodes)>>
Línea 343: Línea 343:
''[#g_node_n_nodes g_node_n_nodes]'' recorre el árbol desde el nodo especificado y cuenta los nodos. El parámetro flags indica qué nodos debe contar y puede tener como valores: ''[[#g_node_n_nodes|g_node_n_nodes]]'' recorre el árbol desde el nodo especificado y cuenta los nodos. El parámetro flags indica qué nodos debe contar y puede tener como valores:
Línea 349: Línea 349:
[[Anchor(g_node_is_ancestor)]] <<Anchor(g_node_is_ancestor)>>
Línea 354: Línea 354:
''[#g_node_is_ancestor g_node_is_ancestor]'' devolverá TRUE si node es un ancestro (padre, padre del padre, etc.) de `descendant`. ''[[#g_node_is_ancestor|g_node_is_ancestor]]'' devolverá TRUE si node es un ancestro (padre, padre del padre, etc.) de `descendant`.
Línea 358: Línea 358:
[[Anchor(g_node_child_index)]] <<Anchor(g_node_child_index)>>
Línea 363: Línea 363:
[[Anchor(g_node_child_position)]] <<Anchor(g_node_child_position)>>
Línea 368: Línea 368:
''[#g_node_child_index g_node_child_index]'' y ''[#g_node_child_position g_node_child_position]'' son funciones similares que devuelven la posición de un hijo en la lista de hijos de un nodo (la primera busca el dato en lugar del nodo en sí). En caso de que el nodo no sea hijo del padre especificado, ambas funciones devolverán -1. ''[[#g_node_child_index|g_node_child_index]]'' y ''[[#g_node_child_position|g_node_child_position]]'' son funciones similares que devuelven la posición de un hijo en la lista de hijos de un nodo (la primera busca el dato en lugar del nodo en sí). En caso de que el nodo no sea hijo del padre especificado, ambas funciones devolverán -1.
Línea 378: Línea 378:
[[Anchor(g_node_find)]] <<Anchor(g_node_find)>>
Línea 384: Línea 384:
[[Anchor(g_node_find_child)]] <<Anchor(g_node_find_child)>>
Línea 389: Línea 389:
''[#g_node_find g_node_find]'' y ''[#g_node_find_child g_node_find_child]'' buscan a partir de node el nodo del árbol que contenga el data especificado. ''[#g_node_find g_node_find]'' busca en todo el árbol, mientras que ''[#g_node_find_child g_node_find_child]'' se limita a los hijos inmediatos del nodo.

En ambos casos flags especifica que clase de nodos se buscarán, y en ''[#g_node_find g_node_find]'', order indica el orden de búsqueda. Este último puede tener uno de estos cuatro valores:
''[[#g_node_find|g_node_find]]'' y ''[[#g_node_find_child|g_node_find_child]]'' buscan a partir de node el nodo del árbol que contenga el data especificado. ''[[#g_node_find|g_node_find]]'' busca en todo el árbol, mientras que ''[[#g_node_find_child|g_node_find_child]]'' se limita a los hijos inmediatos del nodo.

En ambos casos flags especifica que clase de nodos se buscarán, y en ''[[#g_node_find|g_node_find]]'', order indica el orden de búsqueda. Este último puede tener uno de estos cuatro valores:
Línea 400: Línea 400:
[[Anchor(g_node_traverse)]] <<Anchor(g_node_traverse)>>
Línea 407: Línea 407:
[[Anchor(g_node_children_foreach)]] <<Anchor(g_node_children_foreach)>>
Línea 413: Línea 413:
`max_depth` especifica la profundidad máxima de iteración. Si este valor es -1 se recorre todo el árbol; si es 1 sólo `root`; y así sucesivamente. order indica cómo recorrer los nodos y flags qué clase de nodos visitar. Notar que al igual que ''[#g_node_find_child g_node_find_child]'', ''[#g_node_children_foreach g_node_children_foreach]'' se limita a los hijos directos del nodo. `max_depth` especifica la profundidad máxima de iteración. Si este valor es -1 se recorre todo el árbol; si es 1 sólo `root`; y así sucesivamente. order indica cómo recorrer los nodos y flags qué clase de nodos visitar. Notar que al igual que ''[[#g_node_find_child|g_node_find_child]]'', ''[[#g_node_children_foreach|g_node_children_foreach]]'' se limita a los hijos directos del nodo.
Línea 437: Línea 437:
Pero el primer paso, como siempre, es crear el caché en cuestión. Para ello se usa la función ''[#g_cache_new g_cache_new]'', que, a primera vista, parece un tanto compleja:

[[Anchor(g_cache_new)]]
Pero el primer paso, como siempre, es crear el caché en cuestión. Para ello se usa la función ''[[#g_cache_new|g_cache_new]]'', que, a primera vista, parece un tanto compleja:

<<Anchor(g_cache_new)>>
Línea 452: Línea 452:
 * Creación de nuevas entradas en el caché (`value_new_func`). Esta función será llamada por ''[#g_cache_insert g_cache_insert]'' (ver más adelante) cuando se solicite la creación de un elemento cuya clave no existe en el caché.  * Creación de nuevas entradas en el caché (`value_new_func`). Esta función será llamada por ''[[#g_cache_insert|g_cache_insert]]'' (ver más adelante) cuando se solicite la creación de un elemento cuya clave no existe en el caché.
Línea 456: Línea 456:
 * Gestión de la tabla de claves incorporada en `GCache`. Al igual que cuando se usan los `GHashTable`, con `GCache` tambien es necesario especificar las funciones de manejo de la tabla de claves asociada, y para ello se usan los tres últimos parámetros de ''[#g_cache_new g_cache_new]''.  * Gestión de la tabla de claves incorporada en `GCache`. Al igual que cuando se usan los `GHashTable`, con `GCache` tambien es necesario especificar las funciones de manejo de la tabla de claves asociada, y para ello se usan los tres últimos parámetros de ''[[#g_cache_new|g_cache_new]]''.
Línea 466: Línea 466:
La primera operación que viene a la mente es la inserción y obtención de datos de ese caché. Esto se realiza mediante el uso de una única función: ''[#g_cache_insert g_cache_insert]''.

[[Anchor(g_cache_insert)]]
La primera operación que viene a la mente es la inserción y obtención de datos de ese caché. Esto se realiza mediante el uso de una única función: ''[[#g_cache_insert|g_cache_insert]]''.

<<Anchor(g_cache_insert)>>
Línea 473: Línea 473:
Esta función busca el objeto con la clave key especificada. Si lo encuentra ya disponible en el caché, devuelve el valor asociado a esa clave. Si no lo encuentra, lo crea, para lo cual llama a la función especificada en el parámetro `value_new_func` en la llamada a ''[#g_cache_new g_cache_new]''. Así mismo, si el objeto no existe, la clave es duplicada, para lo cual, como no podía ser de otra forma, se llama a la función especificada en el parámetro `key_dup_func` de ''[#g_cache_new g_cache_new]''. Esta función busca el objeto con la clave key especificada. Si lo encuentra ya disponible en el caché, devuelve el valor asociado a esa clave. Si no lo encuentra, lo crea, para lo cual llama a la función especificada en el parámetro `value_new_func` en la llamada a ''[[#g_cache_new|g_cache_new]]''. Así mismo, si el objeto no existe, la clave es duplicada, para lo cual, como no podía ser de otra forma, se llama a la función especificada en el parámetro `key_dup_func` de ''[[#g_cache_new|g_cache_new]]''.
Línea 479: Línea 479:
[[Anchor(g_cache_key_foreach)]] <<Anchor(g_cache_key_foreach)>>
Línea 484: Línea 484:
[[Anchor(g_cache_value_foreach)]] <<Anchor(g_cache_value_foreach)>>
Línea 489: Línea 489:
Ambas funciones operan de la misma forma, que es llamar retroactivamente a la función especificada en el parámetro `func` por cada una de las entradas en el caché. La diferencia entre ellas es que ''[#g_cache_key_foreach g_cache_key_foreach]'' opera sobre las claves y ''[#g_cache_value_foreach g_cache_value_foreach]'' opera sobre los valores. Ambas funciones operan de la misma forma, que es llamar retroactivamente a la función especificada en el parámetro `func` por cada una de las entradas en el caché. La diferencia entre ellas es que ''[[#g_cache_key_foreach|g_cache_key_foreach]]'' opera sobre las claves y ''[[#g_cache_value_foreach|g_cache_value_foreach]]'' opera sobre los valores.
Línea 499: Línea 499:
Otra operación importante que se puede realizar en un caché es la eliminación de entradas. Para ello, se usa la función ''[#g_cache_remove g_cache_remove]''.

[[Anchor(g_cache_remove)]]
Otra operación importante que se puede realizar en un caché es la eliminación de entradas. Para ello, se usa la función ''[[#g_cache_remove|g_cache_remove]]''.

<<Anchor(g_cache_remove)>>
Línea 506: Línea 506:
Esta función marca la entrada identificada por value para ser borrada. No la borra inmediatamente, sino que decrementa un contador interno asociado a cada entrada, que especifica el número de referencias que dicha entrada tiene. Dichas referencias se asignan a 1 cuando se crea la entrada, y se incrementan cada vez que ''[#g_cache_insert g_cache_insert]'' recibe una petición de creación de esa misma entrada. Así, cuando dicho contador llega a 0, significa que no hay ninguna referencia a la entrada del caché, y por tanto, puede ser eliminada. Cuando la entrada es eliminada, se realizan llamadas a las funciones `value_destroy_func` para la destrucción de la entrada y `key_destroy_func` para la destrucción de la clave, tal y como se especificó en la explicación de la función ''[#g_cache_new g_cache_new]''. Esta función marca la entrada identificada por value para ser borrada. No la borra inmediatamente, sino que decrementa un contador interno asociado a cada entrada, que especifica el número de referencias que dicha entrada tiene. Dichas referencias se asignan a 1 cuando se crea la entrada, y se incrementan cada vez que ''[[#g_cache_insert|g_cache_insert]]'' recibe una petición de creación de esa misma entrada. Así, cuando dicho contador llega a 0, significa que no hay ninguna referencia a la entrada del caché, y por tanto, puede ser eliminada. Cuando la entrada es eliminada, se realizan llamadas a las funciones `value_destroy_func` para la destrucción de la entrada y `key_destroy_func` para la destrucción de la clave, tal y como se especificó en la explicación de la función ''[[#g_cache_new|g_cache_new]]''.
Línea 510: Línea 510:
Una vez que no sea necesario por más tiempo el caché, hay que destruirlo, como con cualquier otra estructura de GLib, de forma que se libere toda la memoria ocupada. Esto se realiza con la función ''[#g_cache_destroy g_cache_destroy]'', cuyo único parámetro es el caché que se quiere destruir.

[[Anchor(g_cache_destroy)]]
Una vez que no sea necesario por más tiempo el caché, hay que destruirlo, como con cualquier otra estructura de GLib, de forma que se libere toda la memoria ocupada. Esto se realiza con la función ''[[#g_cache_destroy|g_cache_destroy]]'', cuyo único parámetro es el caché que se quiere destruir.

<<Anchor(g_cache_destroy)>>
Línea 518: Línea 518:
'''''Volver a:''''' [:Documentacion/Desarrollo/Glib:GLib] '''''Volver a:''''' [[Documentacion/Desarrollo/Glib|GLib]]

Estructuras de datos avanzadas

Tablas de dispersión.

Qué es una tabla de dispersión.

Las tablas de dispersión, más conocidas como tablas hash, son unas de las estructuras de datos más frecuentemente usadas. Para tener una idea inicial, las tablas de dispersión posibilitan tener una estructura que relaciona una clave con un valor, como un diccionario. Internamente, las tablas de dispersión son un array. Cada una de las posiciones del array puede contener ninguna, una o varias entradas del diccionario. Normalmente contendrá una como máximo, lo que permite un acceso rápido a los elementos, evitando realizar una búsqueda en la mayoría de los casos. Para saber en qué posición del array se debe buscar o insertar una clave, se utiliza una función de dispersión. Una función de dispersión relaciona a cada clave con un valor entero. Dos claves iguales deben tener el mismo valor de dispersión, también llamado hash value, pero dos claves distintas pueden tener el mismo valor de dispersión, lo cual provocaría una colisión.

El valor de dispersión es un entero sin signo entre 0 y el máximo entero de la plataforma, por lo que la tabla de dispersión usa el resto de dividir el valor de dispersión entre el tamaño del array para encontrar la posición. Cuando dos claves tienen que ser almacenadas en la misma posición de la tabla se produce una colisión. Esto puede ser debido a que la función de dispersión no distribuye las claves lo suficiente, o a que hay más claves en la tabla hash que el tamaño del array. En el segundo caso, GLib se encargará de redimensionar el array de forma automática.

Para aclarar los conceptos, se examinará el siguiente ejemplo a lo largo de todo el capítulo con el fin de facilitar la comprensión del mismo. Póngase que se desea tener una relación de la información de los activistas de GNOME. Para ello se usará una tabla de dispersión usando como clave el apodo que usa cada desarrollador dentro del proyecto. Y como valor una relación de sus datos personales. Esta relación de datos personales vendría dada por la siguiente estructura.

   1                 struct
   2                 DatosDesarrollador {
   3                    gchar *apodo;
   4                    gchar *nombre;
   5                    gchar *proyecto;
   6                    gchar *telefono;
   7                 };

Ahora, si se hace un recuento de datos, se obtiene una curiosa información. Por ejemplo, si tenemos en cuenta que cada apodo tiene como mucho diez caracteres y que el alfabeto tiene veintiseis letras, el resultado es que tendremos 26^10 posibles llaves, lo que supera con creces el número de claves que vamos a utilizar. Con ésto se quiere hacer hincapié en que el uso de esta estructura es útil cuando el número de llaves libres excede con mucho a las llaves que van a ser ocupadas.

Cómo se crea una tabla de dispersión.

Para crear una tabla de dispersión se tiene que indicar la función de dispersión y la función que se utilizará para comparar dos claves. Estas dos funciones se deben pasar como parámetros a la función g_hash_table_new

GHashTable* g_hash_table_new (GHashFunc funcion_de_dispersion,
                              GEqualFunc funcion_de_comparación );

GLib tiene implementadas una serie de funciones de dispersión y comparación. De este modo, el desarrollador no ha de reinventar la rueda. Las funciones de dispersión trabajan siempre de la misma manera. A este tipo de funciones se les pasa un valor y devuelven la clave. En cuanto a las funciones de comparación, se les pasa como parámetros dos valores y devuelve TRUE si son los mismos valores y FALSE si no son iguales.

Estas funciones son implementadas basándose en el siguiente esquema. Si se diera el caso de que las funciones existentes en GLib no satisfacen sus necesidades, lo único que tendrá que hacer será implementar un par de funciones que siguieran estos esquemas.

guint (*GHashFunc) (gconstpointer clave );

gboolean (*GEqualFunc) (gconstpointer clave_A , gconstpointer clave_B );

Una vez se tiene presente este esquema, se puede comprender mejor el funcionamiento de las funciones que se describirán a continuación. La primera pareja de funciones son g_str_hash y g_str_equal, que son de dispersión y de comparación respectivamente. Con la función g_str_hash podremos convertir una clave en forma de cadena en un valor de dispersión. Lo cual quiere decir que el desarrollador podrá usar, con estas funciones, una clave en forma de cadena para la tabla hash.

Otras funciones de carácter similar son g_int_hash, g_int_equal, g_direct_hash o g_direct_equal, que posibilitan usar como claves para la tabla de dispersión números enteros y punteros genéricos respectivamente.

GHashTable* g_hash_table_new_full (GHashFunc       funcion_de_dispersion,
                                   GEqualFunc      funcion_de_comparacion,
                                   GDestroyNotify  key_destroy_func,
                                   GDestroyNotify  value_destroy_func)

La función g_hash_table_new_full es muy parecida a g_hash_table_new, pero a diferencia de esta última, introduce la utilización de dos nuevas funciones, la primera de ellas para de liberar la memoria asignada para la clave y la segunda es usada para liberar la memoria asignada para el valor, ambas funciones son utilizadas al eliminarse una entrada de la tabla de dispersión, y en ambos casos pueden ser reemplazadas por NULL, si no se deseara proveer de dichas funciones.

Ahora, siguiendo con el ejemplo que se comenzó al principio del capitulo, se pasará a ver cómo se creará la tabla de dispersión que contendrá la información de los desarrolladores de GNOME. Recuérdese que se iba a usar, como clave, el apodo del desarrollador. Así que, como función de dispersión y de comparación, se usaran g_str_hash y g_str_equal, respectivamente. Ya que el apodo es una cadena y estas funciones satisfacen perfectamente el fin que se persigue.

Ejemplo 6-10.1. Utilización de tabla de dispersión.

   1 #include <glib.h>
   2 

Cómo manipular un tabla de dispersión.

Ahora se pasará a describir las funciones de manipulación de este TAD. Para añadir y eliminar elementos de una tabla se dispone de estas dos funciones: g_hash_table_insert y g_hash_table_remove. La primera insertará un valor en la tabla hash y le indicará la clave con la que después podrá ser referenciado. En cuanto a la segunda, borrará el valor que corresponda a la clave que se le pase como parámetro a la función.

void g_hash_table_insert (GHashTable tabla_hash, gpointer clave,
                          gpointer valor);

gboolean g_hash_table_remove (GHashTable tabla_hash, gpointer clave );

En caso que se desee modificar el valor asociado a una clave, hay dos opciones a seguir en forma de funciones: g_hash_table_insert (vista anteriormente) o g_hash_table_replace. La única diferencia entre ambas es qué pasa cuando la clave ya existe. En el caso de la primera, se conservará la clave antigua mientras que, en el caso de la segunda, se usará la nueva clave. Obsérvese que dos claves se consideran la misma si la función de comparación devuelve TRUE, aunque sean diferentes objetos.

void g_hash_table_replace (GHashTable tabla_hash, gpointer clave,
                           gpointer valor );

Búsqueda de información dentro de la tabla.

Llegados a este punto, en el que se ha explicado como insertar, borrar y modificar elementos dentro de una tabla de este tipo, parece obvio que el siguiente paso es cómo conseguir encontrar información dentro de una tabla de dispersión. Para ello se dispone de la función g_hash_table_lookup. Esta función tiene un funcionamiento muy simple al igual que las funciones anteriormente explicadas. Lo único que necesita es que se le pase como parámetro la tabla de dispersión y la clave que desea buscar en la misma y la función devolverá un puntero al valor asociado a la clave en caso de existir o el valor NULL en caso de no existir.

gpointer g_hash_table_lookup (GHashTable tabla_hash, gpointer clave );

También se dispone de otra función para realizar las búsquedas de datos dentro de una tabla de dispersión. Esta función es más compleja en su uso pero provee de un sistema de búsqueda más eficiente que el anterior que ayudará a suplir las necesidades más complejas de un desarrollador.

   1 gboolean g_hash_table_lookup_extended (GHashTable tabla_hash,
   2                                        gconstpointer clave_a_buscar,
   3                                        gpointer* clave_original,
   4                                        gpointer* valor );

La función anterior devolverá TRUE si encuentra el valor buscado, o FALSE en caso contrario. En el supuesto de encontrar el valor, el puntero clave_original apuntará a la clave con la que fue almacenado en la tabla, y el puntero valor apuntará al valor almacenado. Téngase en cuenta que la clave usada para la realizar la búsqueda, clave_a_buscar, no tiene por qué ser la misma que la encontrada, clave_original, aunque ambas serán iguales según la función de comparación que hayamos indicado al crear la tabla de dispersión.

Manipulación avanzada de tablas de dispersión.

TODO

Arboles binarios balanceados

Los árboles binarios balanceados son estructuras de datos que almacenan pares clave - dato, de manera ordenada según las claves, y posibilitan el acceso rápido a los datos, dada una clave particular, y recorrer todos los elementos en orden.

Son apropiados para grandes cantidades de información y tienen menor overhead que una tabla de dispersión, aunque el tiempo de acceso es de mayor complejidad computacional.

Si bien internamente la forma de almacenamiento tiene estructura de árbol, esto no se exterioriza en la API, haciendo que el manejo de los datos resulte transparente. Se denominan balanceados porque, cada vez que se modifican, las ramas se rebalancean de tal forma que la altura del árbol sea la mínima posible, acortando de esta manera el tiempo promedio de acceso a los datos.

Creación de un árbol binario.

Para crear un árbol binario balanceado es necesaria una función de comparación que pueda ordenar un conjunto de claves. Para ello se adopta la convención utilizada por strcmp. Esto es, dados dos valores, la función devuelve 0 si son iguales, un valor negativo si el primer parámetro es anterior al segundo, y un valor positivo si el primero es posterior al segundo. La utilización de esta función permite flexibilidad en cuanto a claves a utilizar y en como se ordenan. El prototipo es el siguiente:

gint (*GCompareFunc)(gconstpointer a, gconstpointer b);

o bien, para el caso en que sea necesario proveer algún dato adicional a la función:

gint (*GCompareDataFunc)(gconstpointer a, gconstpointer b, gpointer user_data);

Una vez definida dicha función el árbol se crea con alguna de las siguientes formas:

GTree *g_tree_new(GCompareFunc key_compare_func);

GTree *g_tree_new_with_data(GCompareDataFunc key_compare_func,
                            gpointer key_compare_data);

GTree *g_tree_new_full(GCompareDataFunc key_compare_func,
                       gpointer key_compare_data,
                       GDestroyNotify key_destroy_func,
                       GDestroyNotify value_destroy_func);

donde key_compare_func es la función previamente mencionada, key_compare_data es un dato arbitrario a enviar a la función de comparación y key_destroy_func y value_destroy_func funciones de retrollamada cuando alguna clave o dato se eliminan del árbol.

En caso de no utilizar la última función, es tarea del usuario liberar la memoria utilizada por claves y/o datos cuando se destruye el árbol o cuando se elimina algún dato del mismo utilizando g_tree_remove.

Para destruir un árbol se utiliza la función g_tree_destroy.

void g_tree_destroy(GTree *tree);

Agregar y eliminar elementos a un árbol binario.

Para insertar un nuevo elemento en el árbol se utiliza g_tree_insert o g_tree_replace. La diferencia entre ambas vale sólo en el caso de que en el árbol ya exista una clave igual a la que se intenta agregar y sólo cuando, en la creación del árbol, se especificó una función de destrucción de claves. Para g_tree_insert la clave que se pasó como parámetro se destruye, llamando a key_destroy_func y la del árbol permanece inalterada. Para el caso de g_tree_replace, la clave ya existente se destruye y se reemplaza por la nueva. En ambos casos, de existir el elemento, el dato anterior se destruye llamando a value_destroy_func, siempre que se haya especificado en la creación del árbol.

void g_tree_insert(GTree *tree, gpointer key, gpointer value);

void g_tree_replace(GTree *tree, gpointer key, gpointer value);

key es la clave con la cual se recuperará el dato luego y value el dato en sí. Para eliminar un elemento del árbol se pueden utilizar g_tree_remove o g_tree_steal. La diferencia entre ambas es que, si se invoca g_tree_steal no se destruyen la clave y el valor aunque se hayan especificado funciones para tal fin en la creación del árbol.

void g_tree_remove(GTree *tree, gconstpointer key);

void g_tree_steal(GTree *tree, gconstpointer key);

Búsqueda y recorrida en un árbol binario.

Existen dos funciones para buscar en un árbol binario, similares a las utilizadas en tablas de hash: g_tree_lookup y g_tree_lookup_extended.

gpointer g_tree_lookup(GTree *tree, gconstpointer key);

En este caso, se busca un elemento del árbol cuya clave sea igual (en los términos de la función especificada al momento de la creación) a key. Devuelve el dato del elemento encontrado. Si la búsqueda fue infructuosa devuelve NULL.

gboolean g_tree_lookup_extended(GTree *tree, gconstpointer lookup_key,
                                gpointer *orig_key, gpointer *value);

Esta función no sólo busca el elemento cuya clave coincida con la especificada, sino que además devuelve la clave y dato del elemento encontrado en los parámetros de salida orig_key y value. A diferencia del caso anterior, la función devuelve un booleano indicando si la búsqueda fue exitosa o no.

La versión extendida de la búsqueda es particularmente útil cuando se quiere eliminar un elemento del árbol sin destruirlo, utilizando la función g_tree_steal (p.e. para ser agregado a otro árbol).

Por último para recorrer todos los elementos de un árbol se utiliza g_tree_foreach. Los elementos son tomados en orden y pasados como parámetro a la función de iteración especificada.

void g_tree_foreach(GTree *tree, GTraverseFunc func, gpointer user_data);

Es importante decir que durante el recorrido, no se puede modificar el árbol (agregar y/o eliminar elementos). Si se quieren eliminar algunos elementos, se deben agregar las claves a una lista (o cualquier estructura auxiliar) y finalizada la iteración proceder a eliminar uno por uno los elementos seleccionados. La función de iteración debe tener la siguiente forma:

gboolean (*GTraverseFunc)(gpointer key, gpointer value, gpointer data);

Si dicha función devuelve TRUE, la iteración se interrumpe. data es el valor que se especificó como user_data en la función g_tree_foreach.

GNode : Arboles de orden n.

Para representar datos de manera jerárquica, GLib ofrece el tipo de dato GNode que permite representar árboles de cualquier orden.

Al igual que con las listas y a diferencia de árboles binarios balanceados o tablas hash, los GNode son elementos independientes: sólo hay conexiones entre ellos, pero nada en la estructura dice, por ejemplo, cuál es la raíz del árbol. NULL es el árbol vacío. La estructura GNode tiene la siguiente forma:

   1       struct GNode {
   2          gpointer  data;
   3          GNode    *next;
   4          GNode    *prev;
   5          GNode    *parent;
   6          GNode    *children;
   7       };

data contiene el dato en sí del nodo. parent apunta al nodo padre: éste es NULL para el nodo raíz. children apunta al primer hijo del nodo, accediéndose a los demás hijos mediante los campos next y prev.

Agregar nodos a un árbol.

GLib tiene una serie de funciones para agregar nodos a un árbol. Se puede crear el nodo aislado primero e insertarlo en una posición dada, pero también hay macros definidas que crean el nodo y lo insertan directamente. No hay diferencia en el resultado final, simplemente una línea menos de código.

Para crear un nodo se utiliza g_node_new:

GNode *g_node_new(gpointer data);

Una vez obtenido el GNode, se inserta a un árbol especificando el nodo padre (parent) ya existente y la posición relativa entre los hijos de dicho padre. Hay cinco funciones diferentes en función de la posición y las condiciones en que se quiera insertar. En todos los casos el valor devuelto es el mismo nodo node insertado.

GNode *g_node_insert(GNode *parent, gint position, GNode *node);

GNode *g_node_insert_before(GNode *parent, GNode *sibling, GNode *node);

GNode *g_node_insert_after(GNode *parent, GNode *sibling, GNode *node);

GNode *g_node_append(GNode *parent, GNode *node);

GNode *g_node_prepend(GNode *parent, GNode *node);

sibling es un nodo hijo de parent que se toma como referencia para insertar el nuevo nodo antes o después de él mismo. En ambos casos, g_node_insert_after y g_node_insert_before, si sibling es NULL, el nuevo nodo se inserta al final de la lista de hijos.

Con g_node_n_children se obtiene la cantidad de hijos de un nodo y, a partir de este dato, se puede especificar una posición relativa dentro de la lista de hijos position. Las formas g_node_append y g_node_prepend agregan el nuevo nodo al final o al principio de la lista de hijos.

Cuatro de estas cinco funciones tienen su equivalente de inserción de nodo directa a partir de el dato. Como se dijo antes, la diferencia es que en estos casos se especifica el dato y la creación del nodo es transparente al usuario aunque, de ser requerido, se retorna en el valor de la función. Estas cuatro nuevas formas son macros que utilizan las funciones anteriores. En todos los casos, data es el dato que contendrá el nuevo nodo.

GNode *g_node_insert_data(GNode *parent, gint position, gpointer data);

GNode *g_node_insert_data_before(GNode *parent, GNode *sibling, gpointer data);

GNode *g_node_append_data(GNode *parent, gpointer data);

GNode *g_node_prepend_data(GNode *parent, gpointer data);

Eliminar Vs. desvincular.

Al igual que con las listas, hay dos formas de quitar un dato de un árbol: g_tree_unlink y g_tree_destroy.

void g_node_unlink(GNode *node);

void g_node_destroy(GNode *node);

g_node_unlink quita el nodo especificado del árbol, resultando en un nuevo árbol que lo tiene como raíz. g_node_destroy no sólo elimina el nodo del árbol, sino que, además, libera toda la memoria utilizada por el nodo y por sus hijos. GLib, sin embargo, no tiene forma de liberar la memoria de los datos que contenían los nodos: eso es responsabilidad del usuario.

Información sobre los nodos.

G_NODE_IS_LEAF devuelve TRUE si el nodo es un terminal u hoja del árbol. En otras palabras si el campo children es NULL. Análogamente, G_NODE_IS_ROOT devuelve TRUE si el nodo especificado es la raíz del árbol, o bien, si el campo parent es NULL.

g_node_depth devuelve la profundidad de un nodo (cuantos niveles hay hasta subir a la raíz); g_node_n_children la cantidad de nodos hijos inmediatos y g_node_max_height, la cantidad máxima de niveles inferiores (es decir, iterando hacia los hijos). g_node_depth y g_node_max_height miden alturas. Un árbol vacío tiene altura 0, un único nodo 1 y así sucesivamente.

guint g_node_n_nodes(GNode *node, GTraverseFlags flags);

g_node_n_nodes recorre el árbol desde el nodo especificado y cuenta los nodos. El parámetro flags indica qué nodos debe contar y puede tener como valores:

G_TRAVERSE_LEAFS: Sólo contar los nodos terminales G_TRAVERSE_NON_LEAFS: Sólo contar los nodos intermedios G_TRAVERSE_ALL: Contar todos los nodos

gboolean g_node_is_ancestor(GNode *node, GNode *descendant);

g_node_is_ancestor devolverá TRUE si node es un ancestro (padre, padre del padre, etc.) de descendant.

g_node_get_root devuelve la raíz del árbol que contiene al nodo especificado.

gint g_node_child_index(GNode *node, gpointer data);

gint g_node_child_position(GNode *node, GNode *child);

g_node_child_index y g_node_child_position son funciones similares que devuelven la posición de un hijo en la lista de hijos de un nodo (la primera busca el dato en lugar del nodo en sí). En caso de que el nodo no sea hijo del padre especificado, ambas funciones devolverán -1.

Para acceder a los hijos de un nodo dado se pueden utilizar los campos de la estructura o funciones que provee GLib: g_node_first_child, g_node_last_child y g_node_nth_child.

En forma similar, se puede recorrer la lista de hijos usando los campos prev y next, o mediante g_node_first_sibling, g_node_prev_sibling, g_node_next_sibling y g_node_last_sibling.

Buscar en el árbol y recorrerlo.

Para buscar un nodo determinado, GLib tiene dos funciones:

GNode *g_node_find(GNode *node, GTraverseType order, GTraverseFlags flags,
                   gpointer data);

GNode *g_node_find_child(GNode *node, GTraverseFlags flags, gpointer data);

g_node_find y g_node_find_child buscan a partir de node el nodo del árbol que contenga el data especificado. g_node_find busca en todo el árbol, mientras que g_node_find_child se limita a los hijos inmediatos del nodo.

En ambos casos flags especifica que clase de nodos se buscarán, y en g_node_find, order indica el orden de búsqueda. Este último puede tener uno de estos cuatro valores:

  • G_IN_ORDER: para cada nodo, visitar el primer hijo, luego el nodo mismo y por último el resto de los hijos.

  • G_PRE_ORDER: para cada nodo, visitar primero el nodo y luego los hijos.

  • G_POST_ORDER: para cada nodo, visitar primero los hijos y luego el nodo.

  • G_LEVEL_ORDER: visitar los nodos por niveles, desde la raíz (es decir la raíz, luego los hijos de la raíz, luego los hijos de los hijos de la raíz, etc.)

Al igual que con otros tipos de dato, es posible recorrer el árbol con dos funciones de GLib, que son análogas a las de búsqueda:

void g_node_traverse(GNode *root, GTraverseType order,
                     GTraverseFlags flags, gint max_depth,
                     GNodeTraverseFunc func, gpointer data);

void g_node_children_foreach(GNode *node, GTraverseFlags flags,
                             GNodeForeachFunc func, gpointer data);

max_depth especifica la profundidad máxima de iteración. Si este valor es -1 se recorre todo el árbol; si es 1 sólo root; y así sucesivamente. order indica cómo recorrer los nodos y flags qué clase de nodos visitar. Notar que al igual que g_node_find_child, g_node_children_foreach se limita a los hijos directos del nodo.

La forma de las funciones de iteración es la siguiente:

gboolean (*GNodeTraverseFunc)(GNode *node, gpointer data);

gboolean (*GNodeForeachFunc)(GNode *node, gpointer data);

Al igual que con las funciones de iteración de los árboles binarios, en caso de necesitar interrumpir la iteración, la función debe devolver TRUE.

Caches

Los cachés son algo que, tarde o temprano, cualquier programador acaba implementando, pues permiten el almacenamiento de datos costosos de conseguir (un fichero a través de la red, un informe generado a partir de datos en una base de datos, etc) para su posterior consulta, de forma que dichos datos sean obtenidos una única vez, y leídos muchas.

Como librería de propósito general que es, GLib incluye, no un sistema de caché superfuncional, si no una infraestructura básica para que se puedan desarrollar cachés de todo tipo. Para ello, GLib incluye GCache, que, básicamente, permite la compartición de estructuras complejas de datos. Esto se usa, principalmente, para el ahorro de recursos en las aplicaciones, de forma que, si se tienen estructuras de datos complejas usadas en distintas partes de la aplicación, se pueda compartir una sola copia de dicha estructura compleja de datos entre todas esas partes de la aplicación.

Creación del caché.

GCache funciona de forma muy parecida a las tablas de claves (GHashTable), es decir, mediante el uso de claves para identificar cada objeto, y valores asociados con esas claves.

Pero el primer paso, como siempre, es crear el caché en cuestión. Para ello se usa la función g_cache_new, que, a primera vista, parece un tanto compleja:

GCache g_cache_new (GCacheNewFunc value_new_func,
                    GCacheDestroyFunc value_destroy_func,
                    GCacheDupFunc key_dup_func,
                    GCacheDestroyFunc key_destroy_func,
                    GHashFunc hash_key_func,
                    GHashFunc hash_value_func,
                    GEqualFunc key_equal_func);

Todos los parámetros que recibe esta función son parámetros a funciones y, para cada uno de ellos, se debe especificar la función que realizará cada una de las tareas, que son:

  • Creación de nuevas entradas en el caché (value_new_func). Esta función será llamada por g_cache_insert (ver más adelante) cuando se solicite la creación de un elemento cuya clave no existe en el caché.

  • Destrucción de entradas en el caché (value_destroy_func). En esta función, que es llamada cuando se destruyen entradas en el caché, se debe liberar toda la memoria alojada para la entrada del caché que va a ser destruida. Normalmente, esto significa liberar toda la memoria alojada en value_new_func.

  • Duplicación de claves. Puesto que las claves son asignadas fuera del interfaz de GCache (es decir, por la aplicación que haga uso de GCache), es tarea de la aplicación la creación o duplicación de claves. Así, esta función es llamada cada vez que GCache necesita duplicar una clave.

  • Destrucción de claves. Al igual que en el caso de las entradas, las claves también deben ser destruidas, liberando toda la memoria que estén ocupando.
  • Gestión de la tabla de claves incorporada en GCache. Al igual que cuando se usan los GHashTable, con GCache tambien es necesario especificar las funciones de manejo de la tabla de claves asociada, y para ello se usan los tres últimos parámetros de g_cache_new.

Como se puede observar, GCache está pensado para ser extendido, no para ser usado directamente. Esto es a lo que se hacía referencia en la introducción, de que es una infraestructura para la implementación de cachés. GCache implementa la lógica del caché, mientras que el manejo de los datos de ese caché se dejan de la mano de la aplicación, lo cual se obtiene mediante la implementación de todas estas funciones explicadas en este punto.

Es necesario en este punto hacer un pequeño alto y ver con detalle cómo debe ser la implementación de estas funciones.

Gestión de los datos del caché.

Una vez que el manejo de los datos del caché están claramente definidos en las funciones comentadas, llega el momento de usar realmente el caché. Para ello, se dispone de un amplio conjunto de funciones.

La primera operación que viene a la mente es la inserción y obtención de datos de ese caché. Esto se realiza mediante el uso de una única función: g_cache_insert.

gpointer g_cache_insert (GCache *cache, gpointer key);

Esta función busca el objeto con la clave key especificada. Si lo encuentra ya disponible en el caché, devuelve el valor asociado a esa clave. Si no lo encuentra, lo crea, para lo cual llama a la función especificada en el parámetro value_new_func en la llamada a g_cache_new. Así mismo, si el objeto no existe, la clave es duplicada, para lo cual, como no podía ser de otra forma, se llama a la función especificada en el parámetro key_dup_func de g_cache_new.

Podría ser una buena idea usar cadenas como claves para especificar determinados recursos y, mediante esos identificadores, crear la estructura compleja de datos asociada en la función de creación de entradas del caché. De esta forma, por ejemplo, se podría implementar fácilmente un caché de ficheros obtenidos a través de diferentes protocolos: las claves usadas serían los identificadores únicos de cada fichero (URLs), mientras que la entrada en el caché contendría el contenido mismo del fichero.

Pero, puesto que no siempre se accede al contenido del caché conociendo de antemano las claves, GLib incluye funciones que permiten acceder secuencialmente a todos los contenidos del caché. Esto se puede realizar de dos formas, y, por tanto, con dos funciones distintas:

void g_cache_key_foreach(GCache *cache, GHFunc func, gpointer user_data);

void g_cache_value_foreach(GCache *cache, GHFunc func, gpointer user_data);

Ambas funciones operan de la misma forma, que es llamar retroactivamente a la función especificada en el parámetro func por cada una de las entradas en el caché. La diferencia entre ellas es que g_cache_key_foreach opera sobre las claves y g_cache_value_foreach opera sobre los valores.

En cualquiera de los dos casos, cuando se realice una llamada a una de estas funciones, se deberá definir una función con la siguiente forma:

   1           void foreach_func (gpointer key, gpointer value, gpointer user_data);

En key se recibe la clave de cada una de las entradas (una cada vez), mientras que value recibe el valor de dicha entrada. Por su parte, user_data es el mismo dato que el que se especifica en la llamada a g_cache_*_foreach, y que permite pasar datos de contexto a la función de retrollamada.

Otra operación importante que se puede realizar en un caché es la eliminación de entradas. Para ello, se usa la función g_cache_remove.

void g_cache_remove(GCache *cache, gconstpointer value);

Esta función marca la entrada identificada por value para ser borrada. No la borra inmediatamente, sino que decrementa un contador interno asociado a cada entrada, que especifica el número de referencias que dicha entrada tiene. Dichas referencias se asignan a 1 cuando se crea la entrada, y se incrementan cada vez que g_cache_insert recibe una petición de creación de esa misma entrada. Así, cuando dicho contador llega a 0, significa que no hay ninguna referencia a la entrada del caché, y por tanto, puede ser eliminada. Cuando la entrada es eliminada, se realizan llamadas a las funciones value_destroy_func para la destrucción de la entrada y key_destroy_func para la destrucción de la clave, tal y como se especificó en la explicación de la función g_cache_new.

Destrucción del caché.

Una vez que no sea necesario por más tiempo el caché, hay que destruirlo, como con cualquier otra estructura de GLib, de forma que se libere toda la memoria ocupada. Esto se realiza con la función g_cache_destroy, cuyo único parámetro es el caché que se quiere destruir.

void g_cache_destroy(GCache *cache);


Volver a: GLib

Documentacion/Desarrollo/Glib/EstructurasDeDatosAvanzadas (última edición 2008-12-04 08:48:56 efectuada por localhost)