Implementar diccionario en C

ISO C no define un tipo de diccionario integrado. Si el entorno de destino ofrece la interfaz POSIX hsearch, sus rutinas de tabla hash permiten almacenar y recuperar pares clave-valor. El ejemplo siguiente crea una tabla, inserta dos entradas, busca una clave presente y otra ausente, comprueba los punteros devueltos y libera la tabla. Muestra un enfoque, no todos los diseños posibles de diccionario.

Usar las rutinas POSIX hsearch para implementar un diccionario en C

hcreate, hsearch y hdestroy son rutinas POSIX declaradas en <search.h>, no funciones de la biblioteca ISO C. Su disponibilidad depende del sistema operativo y de la biblioteca C de destino, así que confirma que tu entorno ofrece esta interfaz antes de usar el ejemplo. La especificación POSIX de hcreate y hsearch define la interfaz y permite consultar sus requisitos. El material proporcionado no identifica una plataforma ni una versión concreta de la biblioteca.

Crear una tabla hash y añadir entradas con hcreate y hsearch

Llama a hcreate una vez para crear una tabla con la capacidad solicitada. Devuelve un valor distinto de cero si la operación se completa correctamente y cero si no puede crear la tabla. ENTRY contiene una clave char * y un puntero de datos void *. Pasa una ENTRY y un valor ACTION a hsearch: ENTER solicita una inserción y FIND, una búsqueda. Si la llamada se completa correctamente, devuelve un puntero a una entrada; si falla, devuelve NULL.

Ejecuta este ejemplo:

El código y las etiquetas o salidas visibles de esta sección se mantienen en inglés.

#define _XOPEN_SOURCE 700
#include <search.h>
#include <stdio.h>

int main(void) {
    if (hcreate(4) == 0) {
        fputs("could not create table\n", stderr);
        return 1;
    }

    ENTRY item = {"language", "C"};
    if (hsearch(item, ENTER) == NULL) {
        fputs("could not insert language\n", stderr);
        hdestroy();
        return 1;
    }

    item.key = "standard";
    item.data = "POSIX";
    if (hsearch(item, ENTER) == NULL) {
        fputs("could not insert standard\n", stderr);
        hdestroy();
        return 1;
    }

    ENTRY query = {"language", NULL};
    ENTRY *found = hsearch(query, FIND);
    if (found == NULL) {
        puts("language: not found");
    } else {
        printf("language: %s\n", (char *)found->data);
    }

    query.key = "compiler";
    found = hsearch(query, FIND);
    if (found == NULL) {
        puts("compiler: not found");
    } else {
        printf("compiler: %s\n", (char *)found->data);
    }

    hdestroy();
    return 0;
}

language: C
compiler: not found

Buscar claves y gestionar las entradas ausentes

La primera llamada a FIND busca language, que el programa insertó con el valor C; la segunda busca compiler, que no se insertó. El programa comprueba cada resultado antes de leer data, por lo que puede gestionar de forma segura un resultado NULL como «no encontrado». Si la búsqueda de una clave que debería existir devuelve NULL, el ejemplo tampoco desreferencia el puntero e informa del resultado. Adapta los mensajes o la política de retorno a las necesidades de tu aplicación.

hsearch también devuelve NULL si no puede completar una inserción, así que comprueba el resultado de cada llamada a ENTER antes de continuar. El ejemplo gestiona los errores de creación e inserción escribiendo un diagnóstico en stderr, liberando una tabla que ya se hubiera creado y devolviendo un estado de fallo. Mantén estas comprobaciones junto a cada operación para que el código posterior solo lea una entrada después de verificar su puntero.

El bloque de salida del ejemplo conserva la línea «compiler: not found» en inglés. Indica que no se encontró el compilador; la línea permanece en inglés porque el bloque es inmutable.

Liberar la tabla y comprender sus límites

Llama a hdestroy cuando ya no necesites la tabla. Esta rutina la libera, pero el llamador sigue siendo responsable del almacenamiento asignado dinámicamente para las claves o los valores referenciados por sus entradas; conserva esos punteros y libera por separado las asignaciones que te pertenezcan. El ejemplo usa literales de cadena, así que no tiene asignaciones de ese tipo que liberar. La interfaz POSIX mostrada aquí no ofrece una operación para eliminar una entrada individual. Elige una capacidad adecuada al crear la tabla: se pasa a hcreate la capacidad solicitada y, en el flujo mostrado, esta interfaz no ofrece una operación para cambiar el tamaño de la tabla.