martes, 10 de julio de 2012

Hashtables con hsearch_r y hcreate_r, hecho fácil


hsearch_r(), hcreate_r() y hdestroy_r() son funciones POSIX para el manejo de hashtables. No son las más intuitivas, ni tampoco las más portables, pero el hecho de que vengan con cualquier sistema GNU y no tengas que instalarlas las hace muy cómodas.

Dado que trabajar con ellas es poco práctico he creado unas macros que facilitan su uso y hacen el código más legible. Son las siguientes:


#define _GNU_SOURCE
#include <search.h>


#define HASHTABLE_CREATE(name, sz) \
   struct hsearch_data *name = calloc(sz, sizeof(struct htsearch_data*)); \
   hcreate_r(sz, name); 

#define HASHTABLE_DESTROY(name) hdestroy_r(name)

#define HASHTABLE_SET(name, strkey, value) \
{ \
   ENTRY e, *r; \
   e.key = strkey; \
   if(hsearch_r(e, FIND, &r, name)) \
   { \
      r->data = (void*) (value); \
   } \
   else \
   { \
      e.data = (void*) (value); \
      hsearch_r(e, ENTER, &r, name); \
   } \
}


#define HASHTABLE_GET(name, strkey, value) \
{ \
   ENTRY e, *r; \
   e.key = strkey; \
   if(hsearch_r(e, FIND, &r, name)) \
   { \
      value=(int)r->data; \
   } \
   else \
   { \
      value=(int)0; \
   } \
}


Pegando este código en el programa, se pueden usar fácilmente hashtables, como se muestra en el ejemplo:



   HASHTABLE_CREATE(ht, 100);

   HASHTABLE_SET(ht, "e1", 1);
   HASHTABLE_SET(ht, "e2", 2);
   HASHTABLE_SET(ht, "e3", 3);
   HASHTABLE_SET(ht, "e4", 4);
   HASHTABLE_SET(ht, "e5", 5);

   int i;
   HASHTABLE_GET(ht, "e1", i);
   printf("val: %d\n", i);
   HASHTABLE_GET(ht, "e2", i);
   printf("val: %d\n", i);
   HASHTABLE_GET(ht, "e3", i);
   printf("val: %d\n", i);
   HASHTABLE_GET(ht, "e4", i);
   printf("val: %d\n", i);

   HASHTABLE_DESTROY(ht);


Como se ve, el ejemplo es muy sencillo. Primero creamos una estructura con espacio para 100 elementos (caben más, pero habrá colisiones y no será óptimo). Después añadimos elementos, y posteriormente los consultamos. Finalmente, eliminamos la estructura.

A tener en cuenta que HASHTABLE_GET almacena el resultado en "i", lo cual puede confundir un poco al leer el código.

Las macros están hechas para trabajar con valores enteros, pero son fácilmente modificables.