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.
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;
}
VÉASE TAMBIÉN¶
bsearch(3),
lsearch(3),
tsearch(3),
malloc(3)