NOMBRE
hcreate, hdestroy, hsearch − funciones para manejar una tabla dispersa (hash)
SINOPSIS
#include <search.h>
int hcreate(size_t nel);
ENTRY *hsearch(ENTRY item, ACTION action);
void hdestroy(void);
#define
_GNU_SOURCE
#include <search.h>
int hcreate_r(size_t nel, struct hsearch_data *tab);
int *hsearch_r(ENTRY item, ACTION action, ENTRY **ret, struct hsearch_data *tab);
void hdestroy_r(struct hsearch_data *tab);
DESCRIPCIÓN
Las tres funciones hcreate, hsearch, y hdestroy permiten al usuario crear una tabla dispersa (sólo una al mismo tiempo) que asocia una clave con cualquier dato. Las tres funciones hcreate_r, hsearch_r, hdestroy_r son versiones reentrantes que permiten el uso de más de una tabla.
En primer lugar, se debe crear la tabla con la función hcreate(). El argumento nel es una estimación del número de entradas de la tabla. La función hcreate() puede incrementar este valor para mejorar el rendimiento de la tabla dispersa resultante.
La función correspondiente hdestroy() libera la memoria ocupada por la tabla dispersa de tal forma que se pueda construir una nueva tabla.
El argumento item es del tipo ENTRY, que se define mediante typedef en <search.h> e incluye estos elementos:
|
typedef struct entry { | ||
|
char *key; | ||
|
void *data; | ||
|
} ENTRY; |
El campo key apunta a una cadena terminada en NUL que es la clave de búsqueda. El campo data apunta a los datos asociados con esa clave. La función hsearch() busca en la tabla dispersa un elemento con la misma clave que item (donde "la misma" se determina usando strcmp(3)), y si tiene éxito devuelve un puntero al mismo. El argumento action determina qué debe hacer hsearch() tras una búsqueda sin éxito. El valor ENTER le indica que debe insertar una copia de item, mientras que un valor FIND significa que debe devolver NULL.
VALOR DEVUELTO
hcreate() y hcreate_r() devuelven 0 cuando falla la reserva de memoria para la tabla dispersa, o un valor distinto de cero en otro caso.
hsearch() devuelve NULL si action es ENTER y la tabla dispersa está completa, o action es FIND e item no puede ser encontrado en la tabla dispersa.
hsearch_r() devuelve 0 si action es ENTER y la tabla dispersa está completa, y un valor distinto de cero en otro caso.
ERRORES
|
ENOMEM |
Memoria insuficiente. |
CONFORME A
Las funciones hcreate, hsearch, y hdestroy son de SVID, y están descritas en POSIX 1003.1-2001. Las funciones hcreate_r, hsearch_r, hdestroy_r son extensiones de GNU.
FALLOS
SVID y POSIX 1003.1-2001 especifican que el argumento action es significativo sólo para búsquedas sin éxito, por lo que ENTER no debería hacer nada para una búsqueda exitosa. Las implementaciones de libc y glibc actualizan data para una clave key dada en este caso.
Se pueden añadir a la tabla dispersa entradas individuales pero no se pueden eliminar.
EJEMPLO
El siguiente programa inserta 24 elementos en una tabla dispersa y a continuación imprime algunos de ellos.
#include
<stdio.h>
#include <search.h>
char *data[] =
{ "alpha", "bravo", "charlie",
"delta",
"echo", "foxtrot", "golf",
"hotel", "india", "juliet",
"kilo", "lima", "mike",
"november", "oscar", "papa",
"quebec", "romeo", "sierra",
"tango", "uniform",
"victor", "whisky", "x-ray",
"yankee", "zulu"
};
int main() {
ENTRY e, *ep;
int i;
/* Comencemos
con una pequeña tabla y dejémosla que crezca
*/
hcreate(30);
for (i = 0; i < 24; i++) {
e.key = data[i];
/* Los datos son enteros, en lugar de punteros a alguna cosa
*/
e.data = (char *)i;
ep = hsearch(e, ENTER);
/* No debe haber fallos */
if(ep == NULL) {
fprintf(stderr, "Fallo en la entrada\n");
exit(1);
|
} |
}
for (i = 22; i < 26; i++) {
/* Imprime dos entradas de la tabla y demuestra que otras
dos no
están en la tabla */
e.key =
data[i];
ep = hsearch(e, FIND);
printf("%9.9s -> %9.9s:%d\n", e.key,
|
ep?ep->key:"NULL", |
ep?(int)(ep->data):0);
}
return 0;
}