u_hmap

Hmap provides a simple yet flexible hashmap library. It gives developers a high degree of flexibility by allowing for the following customisations:

• any pointer type (void *)
• object comparison and string functions
• hash/free functions
• discard policy
• array size and maximum number of elements

The hashmap is implemented using the common “hash-bucket chaining” method: the hash function maps keys to a specific bucket, and clashes in the hash function are handled by holding a list of items in each bucket.

Simple Example

Let’s have a look at an example which uses the default values provided by the library to store simple strings.

The first step is to initialise the basic Hmap structure (u_hmap_t), the options structure (u_hmap_opts_t) and a variable of the (char *)

#include <u/libu.h>
 
int main()
{
    u_hmap_opts_t *opts = NULL;
    u_hmap_t *hmap = NULL;
    char *s = NULL;
 
    con_err_if (u_hmap_opts_new(&opts));
    con_err_if (u_hmap_new(opts, &hmap));
    /* ... code follows ... */
 
    return 0;
err:
    return ~0;
}

now let’s insert some sample elements:

con_err_if (u_hmap_put(hmap, "english", (void *) strdup("Hello world!")));
con_err_if (u_hmap_put(hmap, "italian", (void *) strdup("Ciao mondo!")));
con_err_if (u_hmap_put(hmap, "german", (void *) strdup("Hallo Welt!")));

then retrieve and print their values to the console:

con_err_if (u_hmap_get(hmap, "english", (void **) &s)); con(s);
con_err_if (u_hmap_get(hmap, "italian", (void **) &s)); con(s);
con_err_if (u_hmap_get(hmap, "german", (void **) &s)); con(s);

hence we free the hmap structure. This will deallocate the options structure as well as all the objects contained within the hashmap:

u_hmap_free(hmap);

Basic customisation

Now let’s have a look at an example which is customised to suit the developer’s specific needs. It shall contain objects of type foo_t.

After initialisation, we customise the u_hmap_opts_t structure:

opts->max_size = 128;
opts->max_elems = 2 * opts->max_size;
opts->policy = U_HMAP_PCY_FIFO;
opts->f_hash = foo_hash;
opts->f_comp = foo_comp;
opts->f_free = foo_free;
opts->f_str = foo_str;

A brief description of each parameter is given here:

max_size: the size of the hashmap array (number of buckets). this does not enforce a limit to the number of elements, but should be proportial to the expected maximum. In this example 128 buckets are used because the average number of approximately 100 elements is expected. Using the standard hash function, a low number of clashes should occur.

max_elems: by default this limit does not apply, as the default policy U_HMAP_PCY_NONE never discards old elements. For other policies, it imposes a limit to the number of elements which the hmap can contain. If this limit is violated the policy will be applied to discard elements.

policy: if the max_elems limit is exceeded, the U_HMAP_PCY_FIFO policy will discard elements inserted earliest into the hmap

f_hash: a custom hash function

f_comp: a comparison function for foo_t objects

f_free: a free function for foo_t objects

f_str: a string representation function for foo_t objects