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:

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:

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)