srcs/toolbox/hmap.c

/*
 * Copyright (c) 2005-2012 by KoanLogic s.r.l. - All rights reserved.
 */
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <stdio.h>

#include <toolbox/memory.h>
#include <toolbox/carpal.h>
#include <toolbox/hmap.h>
#include <toolbox/queue.h>
#include <toolbox/str.h>
#include <toolbox/misc.h>

/* default limits handled by policies */
#define U_HMAP_MAX_SIZE      512
#define U_HMAP_MAX_ELEMS     U_HMAP_MAX_SIZE
#define U_HMAP_RATE_FULL     0.75
#define U_HMAP_RATE_RESIZE   3

/* types of operation used for handling policies */
enum {
    U_HMAP_PCY_OP_PUT = 0x1,
    U_HMAP_PCY_OP_GET = 0x2
};

/* policy queue object */
struct u_hmap_q_s
{
    u_hmap_o_t *ho;     
    void *data;         
    TAILQ_ENTRY(u_hmap_q_s) next;
};
typedef struct u_hmap_q_s u_hmap_q_t;

/* hmap policy representation */
struct u_hmap_pcy_s
{
    int (*pop)(u_hmap_t *hmap, u_hmap_o_t **obj);
    int (*push)(u_hmap_t *hmap, u_hmap_o_t *obj,
            u_hmap_q_t **data);
    int ops;    /* bitwise inclusive OR of U_HMAP_PCY_OP_* values */

    TAILQ_HEAD(u_hmap_q_h_s, u_hmap_q_s) queue;
};
typedef struct u_hmap_q_h_s u_hmap_q_h_t;

/* hmap element object */
struct u_hmap_o_s
{
    void *key;
    void *val;

    LIST_ENTRY(u_hmap_o_s) next;

    u_hmap_q_t *pqe;

    u_hmap_t *hmap;
};

/* Map options */
struct u_hmap_opts_s
{
    size_t size,            
           max;             
    u_hmap_type_t type;         
    u_hmap_pcy_type_t policy;   
    int options;                
    u_hmap_options_datatype_t key_type;         
    u_hmap_options_datatype_t val_type;         
    size_t key_sz;                      /* size of key (if OPAQUE) */
    size_t val_sz;                      /* size of value (if OPAQUE) */

    size_t (*f_hash)(const void *key, size_t buckets);
    int (*f_comp)(const void *k1, const void *k2);
    void (*f_free)(u_hmap_o_t *obj);
    void (*f_key_free)(const void *key);
    void (*f_val_free)(void *val);
    u_string_t *(*f_str)(u_hmap_o_t *obj);
    int (*f_pcy_cmp)(void *o1, void *o2);

    unsigned char easy;         
    unsigned char val_free_set; 
};

/* hmap representation */
struct u_hmap_s
{
    u_hmap_opts_t *opts;        /* hmap options */

    size_t sz,                  /* current size */
           size,                /* array size */
           threshold,           /* when to resize */
           px;                  /* index into prime numbers array */

    u_hmap_pcy_t pcy;    /* discard policy */

    LIST_HEAD(u_hmap_e_s, u_hmap_o_s) *hmap;    /* the hashmap */
};
typedef struct u_hmap_e_s u_hmap_e_t;

static int __get (u_hmap_t *hmap, const void *key, u_hmap_o_t **o);

static int __opts_check (u_hmap_opts_t *opts);
static int __pcy_setup (u_hmap_t *hmap);
static const char *__pcy2str(u_hmap_pcy_type_t policy);

static void __o_free (u_hmap_t *hmap, u_hmap_o_t *obj);
static int __o_overwrite (u_hmap_t *hmap, u_hmap_o_t *o, u_hmap_o_t *obj,
        u_hmap_o_t **old);

static u_hmap_q_t *__q_o_new (u_hmap_o_t *ho);
static void __q_o_free (u_hmap_q_t *s);

static size_t __f_hash (const void *key, size_t size);
static int __f_comp (const void *k1, const void *k2);
static u_string_t *__f_str (u_hmap_o_t *obj);

static int __queue_push (u_hmap_t *hmap, u_hmap_o_t *obj, u_hmap_q_t **data);
static int __queue_push_count (u_hmap_t *hmap, u_hmap_o_t *obj,
        u_hmap_q_t **counts);
static int __queue_push_cmp (u_hmap_t *hmap, u_hmap_o_t *obj,
        u_hmap_q_t **counts);
static int __queue_pop_front (u_hmap_t *hmap, u_hmap_o_t **obj);
static int __queue_pop_back (u_hmap_t *hmap, u_hmap_o_t **obj);
static int __queue_del (u_hmap_t *hmap, u_hmap_o_t *obj);

static int __resize(u_hmap_t *hmap);
static int __next_prime(size_t *prime, size_t sz, size_t *idx);

static const char *__datatype2str(u_hmap_options_datatype_t datatype);

int u_hmap_easy_new (u_hmap_opts_t *opts, u_hmap_t **phmap)
{
    u_hmap_opts_t newopts;

    dbg_err_if (opts == NULL);
    dbg_err_if (phmap == NULL);

    u_hmap_opts_init(&newopts);

    dbg_err_if (u_hmap_opts_copy(&newopts, opts));

    /* same defaults as advanced interface, but mark as easy */
    newopts.easy = 1;

    dbg_err_if (u_hmap_new(&newopts, phmap));

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

void u_hmap_easy_clear (u_hmap_t *hmap)
{
    dbg_ifb (hmap == NULL) return;

    u_hmap_clear(hmap);
}

void u_hmap_easy_free (u_hmap_t *hmap)
{
    dbg_return_if (hmap == NULL, );

    u_hmap_free(hmap);

    return;
}

int u_hmap_easy_put (u_hmap_t *hmap, const char *key, const void *val)
{
    int rc = U_HMAP_ERR_NONE;
    u_hmap_o_t *obj = NULL;

    dbg_err_if ((obj = u_hmap_o_new(hmap, key, val)) == NULL);
    dbg_err_if ((rc = u_hmap_put(hmap, obj, NULL)));

    return rc;
err:
    /* don't free 'obj' because hmap owns it and will free it */
    return (rc ? rc : U_HMAP_ERR_FAIL);
}

void *u_hmap_easy_get (u_hmap_t *hmap, const char *key)
{
    u_hmap_o_t *obj = NULL;

    nop_return_if (u_hmap_get(hmap, key, &obj), NULL);

    return obj->val;
}

int u_hmap_easy_del (u_hmap_t *hmap, const char *key)
{
    return (u_hmap_del(hmap, key, NULL));
}

/* Default hash function */
static size_t __f_hash (const void *key, size_t size)
{
    size_t h = 0;
    const unsigned char *k = (const unsigned char *) key;

    dbg_ifb (key == NULL) return -1;

    while (*k)
    {
        h += *k++;
        h += (h << 10);
        h ^= (h >> 6);
    }

    h += (h << 3);
    h ^= (h >> 11);

    return (h + (h << 15)) % size;
}

/* Default comparison function for key comparison */
static int __f_comp (const void *k1, const void *k2)
{
    dbg_ifb (k1 == NULL) return -1;
    dbg_ifb (k2 == NULL) return -1;

    return strcmp((const char *)k1, (const char *)k2);
}

/* Default string representation of objects */
static u_string_t *__f_str (u_hmap_o_t *obj)
{
    enum { MAX_OBJ_STR = 256 };
    char buf[MAX_OBJ_STR];
    u_string_t *s = NULL;
    const char *key, *val;

    dbg_err_if (obj == NULL);

    key = (obj->hmap->opts->key_type == U_HMAP_OPTS_DATATYPE_STRING) ?
        (const char *) obj->key : "";
    val = (obj->hmap->opts->val_type == U_HMAP_OPTS_DATATYPE_STRING) ?
        (const char *) obj->val : "";

    dbg_err_if (u_snprintf(buf, MAX_OBJ_STR, "[%s:%s]", key, val));
    dbg_err_if (u_string_create(buf, strlen(buf)+1, &s));

    return s;

err:
    U_FREE(s);
    return NULL;
}

/* Check validity of options */
static int __opts_check (u_hmap_opts_t *opts)
{
    dbg_err_if (opts == NULL);

    dbg_err_if (opts->size == 0);
    dbg_err_if (opts->max == 0);
    dbg_err_if (opts->type != U_HMAP_TYPE_CHAIN &&
            opts->type != U_HMAP_TYPE_LINEAR);
    dbg_err_if (!U_HMAP_IS_PCY(opts->policy));
    dbg_err_if (opts->f_hash == NULL);
    dbg_err_if (opts->f_comp == NULL);

    /* in the hmap_easy interface, in case of pointer values (default),
       we force setting the value free function to avoid developer mistakes;
       for string or opaque values there is no need because we already know how
       to handle them */
    dbg_err_ifm (opts->easy &&
            opts->val_type == U_HMAP_OPTS_DATATYPE_POINTER &&
            !opts->val_free_set,
                "value free function must be set for pointers!");

    dbg_err_ifm (opts->policy == U_HMAP_PCY_CUSTOM &&
            opts->f_pcy_cmp == NULL,
                "comparison function must be set for custom policy!");

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

/* Setup policy parameters */
static int __pcy_setup (u_hmap_t *hmap)
{
    dbg_return_if (hmap == NULL, ~0);

    switch (hmap->opts->policy)
    {
        case U_HMAP_PCY_NONE:
            hmap->pcy.push = NULL;
            hmap->pcy.pop = NULL;
            hmap->pcy.ops = 0;
            break;
        case U_HMAP_PCY_FIFO:
            hmap->pcy.push = __queue_push;
            hmap->pcy.pop = __queue_pop_back;
            hmap->pcy.ops = U_HMAP_PCY_OP_PUT;
            break;
        case U_HMAP_PCY_LRU:
            hmap->pcy.push = __queue_push;
            hmap->pcy.pop = __queue_pop_back;
            hmap->pcy.ops = U_HMAP_PCY_OP_PUT | U_HMAP_PCY_OP_GET;
            break;
        case U_HMAP_PCY_LFU:
            hmap->pcy.push = __queue_push_count;
            hmap->pcy.pop = __queue_pop_front;
            hmap->pcy.ops = U_HMAP_PCY_OP_PUT | U_HMAP_PCY_OP_GET;
            break;
        case U_HMAP_PCY_CUSTOM:
            hmap->pcy.push = __queue_push_cmp;
            hmap->pcy.pop = __queue_pop_back;
            hmap->pcy.ops = U_HMAP_PCY_OP_PUT;
            break;
        default:
            u_dbg("Invalid policy: %d", hmap->opts->policy);
            return U_HMAP_ERR_FAIL;
    }

    return U_HMAP_ERR_NONE;
}

int u_hmap_new (u_hmap_opts_t *opts, u_hmap_t **phmap)
{
    size_t i;
    u_hmap_t *c = NULL;

    /* allow (opts == NULL) */
    dbg_return_if (phmap == NULL, U_HMAP_ERR_FAIL);

    dbg_return_sif ((c = (u_hmap_t *) u_zalloc(sizeof(u_hmap_t))) == NULL,
            U_HMAP_ERR_FAIL);

    dbg_err_if (u_hmap_opts_new(&c->opts));
    if (opts)
        dbg_err_if (u_hmap_opts_copy(c->opts, opts));

    /* if key or value are strings we know how to display them */
    if (c->opts->f_str == NULL &&
            (c->opts->key_type == U_HMAP_OPTS_DATATYPE_STRING ||
            c->opts->val_type == U_HMAP_OPTS_DATATYPE_STRING))
        c->opts->f_str = &__f_str;

    dbg_err_if (__opts_check(c->opts));
    u_hmap_opts_dbg(c->opts);
    dbg_err_if (__pcy_setup(c));

    c->size = c->opts->size;
    dbg_err_if (__next_prime(&c->size, c->size, &c->px));
    c->threshold = (size_t) (U_HMAP_RATE_FULL * c->size);

    dbg_err_sif ((c->hmap = (u_hmap_e_t *)
                u_zalloc(sizeof(u_hmap_e_t) *
                    c->size)) == NULL);

    /* initialise entries */
    for (i = 0; i < c->size; ++i)
        LIST_INIT(&c->hmap[i]);

    TAILQ_INIT(&c->pcy.queue);

    u_dbg("[hmap]");
    u_dbg("threshold: %u", c->threshold);

    *phmap = c;

    return U_HMAP_ERR_NONE;

err:
    u_free(c);
    *phmap = NULL;
    return U_HMAP_ERR_FAIL;
}

void u_hmap_clear (u_hmap_t *hmap)
{
    u_hmap_o_t *obj;
    u_hmap_q_t *data;
    size_t i;

    dbg_ifb (hmap == NULL) return;

    /* free the hashhmap */
    for (i = 0; i < hmap->size; ++i)
    {
        while ((obj = LIST_FIRST(&hmap->hmap[i])) != NULL)
        {
            LIST_REMOVE(obj, next);
            __o_free(hmap, obj);
        }
    }

    /* free the policy queue */
    while ((data = TAILQ_FIRST(&hmap->pcy.queue)) != NULL)
    {
        TAILQ_REMOVE(&hmap->pcy.queue, data, next);
        __q_o_free(data);
    }
}

void u_hmap_free (u_hmap_t *hmap)
{
    dbg_ifb (hmap == NULL) return;

    u_hmap_clear(hmap);
    u_free(hmap->hmap);
    u_hmap_opts_free(hmap->opts);
    u_free(hmap);
}

int u_hmap_put (u_hmap_t *hmap, u_hmap_o_t *obj, u_hmap_o_t **old)
{
    u_hmap_o_t *o;
    u_hmap_e_t *x;
    int comp;
    int rc;
    size_t hash;
    size_t last;

    dbg_err_if (hmap == NULL);
    dbg_err_if (obj == NULL);

    if (old)
        *old = NULL;

    if (hmap->sz >= hmap->threshold &&
            hmap->opts->policy == U_HMAP_PCY_NONE)
        dbg_err_if (__resize(hmap));

    hash = hmap->opts->f_hash(obj->key, hmap->size);

    /* rehash if strong hash is required */
    if (hmap->opts->f_hash != &__f_hash &&
            !(hmap->opts->options & U_HMAP_OPTS_HASH_STRONG))
    {
        enum { MAX_INT = 20 };
        char h[MAX_INT];

        u_snprintf(h, MAX_INT, "%u", hash);
        hash = __f_hash(h, hmap->size);
    }

    x = &hmap->hmap[hash];

    switch (hmap->opts->type)
    {
        case U_HMAP_TYPE_CHAIN:

            if (LIST_EMPTY(x))
            {
                LIST_INSERT_HEAD(x, obj, next);
                goto end;
            }

            LIST_FOREACH(o, x, next)
            {
                /* object already hmapd */
                if ((comp = hmap->opts->f_comp(obj->key, o->key)) == 0)
                {
                    rc = __o_overwrite(hmap, o, obj, old);
                    dbg_err_if (rc && rc != U_HMAP_ERR_EXISTS);
                    return rc;
                }
                else
                {
                    if (comp < 0)
                    {
                        LIST_INSERT_BEFORE(o, obj, next);
                        goto end;
                    }
                    else if (!LIST_NEXT(o, next))
                    {
                        LIST_INSERT_AFTER(o, obj, next);
                        goto end;
                    }
                }
            }
            break;

        case U_HMAP_TYPE_LINEAR:

            last = ((hash + hmap->size-1) % hmap->size);

            for (; hash != last; hash = ((hash+1) % hmap->size),
                    x = &hmap->hmap[hash])
            {
                if (LIST_EMPTY(x))
                {
                    LIST_INSERT_HEAD(x, obj, next);
                    goto end;
                }

                /* only first node used for linear probing */
                o = LIST_FIRST(x);

                /* object already hmapd */
                if (hmap->opts->f_comp(o->key, obj->key) == 0)
                {
                    rc = __o_overwrite(hmap, o, obj, old);
                    dbg_err_if (rc && rc != U_HMAP_ERR_EXISTS);
                    return rc;
                }
            }
            break;
    }

err:
    return U_HMAP_ERR_FAIL;

end:

    if (hmap->sz >= hmap->opts->max &&
            hmap->opts->policy != U_HMAP_PCY_NONE)
    {
        u_dbg("Cache full - freeing according to policy '%s'",
                __pcy2str(hmap->opts->policy));
        dbg_err_if (hmap->pcy.pop(hmap, old));
    }

    if (hmap->pcy.ops & U_HMAP_PCY_OP_PUT)
        dbg_err_if (hmap->pcy.push(hmap, obj, &obj->pqe));
    hmap->sz++;

    return U_HMAP_ERR_NONE;
}

int u_hmap_get (u_hmap_t *hmap, const void *key, u_hmap_o_t **obj)
{
    dbg_err_if (hmap == NULL);
    dbg_err_if (key == NULL);
    dbg_err_if (obj == NULL);

    if (__get(hmap, key, obj))
    {
        *obj = NULL;
        return U_HMAP_ERR_FAIL;
    }
    dbg_err_if (obj == NULL);

    if (hmap->pcy.ops & U_HMAP_PCY_OP_GET)
        dbg_err_if (hmap->pcy.push(hmap, *obj, &(*obj)->pqe));

    return U_HMAP_ERR_NONE;

err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_del (u_hmap_t *hmap, const void *key, u_hmap_o_t **obj)
{
    u_hmap_o_t *o = NULL;

    dbg_err_if (hmap == NULL);
    dbg_err_if (key == NULL);

    if (obj)
        *obj = NULL;

    if (__get(hmap, key, &o))
        return U_HMAP_ERR_FAIL;

    dbg_err_if (o == NULL);
    LIST_REMOVE(o, next);

    if (hmap->opts->options & U_HMAP_OPTS_OWNSDATA)
        __o_free(hmap, o);
    else
        if (obj)
            *obj = o;

    hmap->sz--;

    return U_HMAP_ERR_NONE;

err:
    return U_HMAP_ERR_FAIL;
}

u_hmap_o_t *u_hmap_o_new (u_hmap_t *hmap, const void *key, const void *val)
{
    u_hmap_o_t *obj = NULL;

    dbg_return_if (hmap == NULL, NULL);
    dbg_return_if (key == NULL, NULL);
    dbg_return_if (val == NULL, NULL);

    dbg_err_sif ((obj = (u_hmap_o_t *) u_zalloc(sizeof(u_hmap_o_t))) == NULL);
    obj->hmap = hmap;

    if (hmap->opts->options & U_HMAP_OPTS_OWNSDATA)
    {
        /* internalise key */
        switch (hmap->opts->key_type)
        {
            case U_HMAP_OPTS_DATATYPE_POINTER:
                memcpy(&obj->key, &key, sizeof(void **));
                break;
            case U_HMAP_OPTS_DATATYPE_STRING:
                dbg_err_if ((obj->key = u_strdup((const char *) key)) == NULL);
                break;
            case U_HMAP_OPTS_DATATYPE_OPAQUE:
                dbg_err_if ((obj->key = u_zalloc(hmap->opts->key_sz)) == NULL);
                memcpy(obj->key, key, hmap->opts->key_sz);
                break;
        }

        /* internalise value */
        switch (hmap->opts->val_type)
        {
            case U_HMAP_OPTS_DATATYPE_POINTER:
                memcpy(&obj->val, &val, sizeof(void **));
                break;
            case U_HMAP_OPTS_DATATYPE_STRING:
                dbg_err_if ((obj->val = u_strdup((const char *) val)) == NULL);
                break;
            case U_HMAP_OPTS_DATATYPE_OPAQUE:
                dbg_err_if ((obj->val = u_zalloc(hmap->opts->val_sz)) == NULL);
                memcpy(obj->val, val, hmap->opts->val_sz);
                break;
        }
    }
    else
    {  /* data owned by user - do not internalise, just set pointers */
        memcpy(&obj->key, &key, sizeof(void **));
        memcpy(&obj->val, &val, sizeof(void **));
    }

    obj->pqe = NULL;

    return obj;

err:
    U_FREEF(obj, u_hmap_o_free);

    return NULL;
}

void u_hmap_o_free (u_hmap_o_t *obj)
{
    dbg_ifb (obj == NULL) return;

    u_free(obj);
}

void *u_hmap_o_get_key (u_hmap_o_t *obj)
{
    return obj->key;
}

void *u_hmap_o_get_val (u_hmap_o_t *obj)
{
    return obj->val;
}

/* Free a data object including content (only if U_HMAP_OPTS_OWNSDATA) */
static void __o_free (u_hmap_t *hmap, u_hmap_o_t *obj)
{
    dbg_ifb (hmap == NULL) return;
    dbg_ifb (obj == NULL) return;

    if (hmap->opts->f_free)
    {
        hmap->opts->f_free(obj);
    }
    else
    {
        switch (hmap->opts->key_type)
        {
            case U_HMAP_OPTS_DATATYPE_POINTER:
                if (hmap->opts->f_key_free)
                    hmap->opts->f_key_free(obj->key);
                break;
            case U_HMAP_OPTS_DATATYPE_STRING:
            case U_HMAP_OPTS_DATATYPE_OPAQUE:
                u_free(obj->key);
                break;
        }
        switch (hmap->opts->val_type)
        {
            case U_HMAP_OPTS_DATATYPE_POINTER:
                if (hmap->opts->f_val_free)
                    hmap->opts->f_val_free(obj->val);
                break;
            case U_HMAP_OPTS_DATATYPE_STRING:
            case U_HMAP_OPTS_DATATYPE_OPAQUE:
                u_free(obj->val);
                break;
        }
    }

    u_hmap_o_free(obj);
}

static int __o_overwrite (u_hmap_t *hmap, u_hmap_o_t *o, u_hmap_o_t *obj,
        u_hmap_o_t **old)
{
    /* overwrite */
    if (!(hmap->opts->options &
                U_HMAP_OPTS_NO_OVERWRITE))
    {
        if (hmap->pcy.ops & U_HMAP_PCY_OP_PUT)
        {
            /* delete old object and enqueue new one */
            dbg_err_if (__queue_del(hmap, o));
            dbg_err_if (hmap->pcy.push(hmap, obj, &obj->pqe));
        }

        /* replace object in hmap list */
        LIST_INSERT_AFTER(o, obj, next);
        LIST_REMOVE(o, next);

        if (hmap->opts->options & U_HMAP_OPTS_OWNSDATA)
            __o_free(hmap, o);
        else
            if (old)
                *old = o;

        return U_HMAP_ERR_NONE;
    }
    else  /* don't overwrite */
    {
        if (hmap->opts->options & U_HMAP_OPTS_OWNSDATA)
            __o_free(hmap, obj);
        else
            if (old)
                *old = o;

        return U_HMAP_ERR_EXISTS;
    }
err:
    return U_HMAP_ERR_FAIL;
}

ssize_t u_hmap_count (u_hmap_t *hmap)
{
    dbg_return_if (hmap == NULL, -1);
    return hmap->sz;
}

int u_hmap_opts_new (u_hmap_opts_t **opts)
{
    u_hmap_opts_t *o;

    dbg_err_if (opts == NULL);

    dbg_err_sif ((o = (u_hmap_opts_t *) u_zalloc(sizeof(u_hmap_opts_t)))
            == NULL);

    u_hmap_opts_init(o);

    *opts = o;

    return U_HMAP_ERR_NONE;
err:
    *opts = NULL;
    return U_HMAP_ERR_FAIL;
}

void u_hmap_opts_free (u_hmap_opts_t *opts)
{
    dbg_ifb (opts == NULL) return;

    u_free(opts);
}

void u_hmap_opts_init (u_hmap_opts_t *opts)
{
    dbg_ifb (opts == NULL) return;

    opts->size = U_HMAP_MAX_SIZE;
    opts->type = U_HMAP_TYPE_CHAIN;
    opts->max = U_HMAP_MAX_ELEMS;
    opts->policy = U_HMAP_PCY_NONE;
    opts->options = U_HMAP_OPTS_NO_OVERWRITE | U_HMAP_OPTS_OWNSDATA;
    opts->f_hash = &__f_hash;
    opts->f_comp = &__f_comp;
    opts->f_free = NULL;
    opts->key_type = U_HMAP_OPTS_DATATYPE_STRING;
    opts->val_type = U_HMAP_OPTS_DATATYPE_POINTER;
    opts->f_key_free = NULL;
    opts->f_val_free = NULL;
    opts->val_free_set = 0;
    opts->f_str = NULL;
    opts->key_sz = sizeof(void *);
    opts->val_sz = sizeof(void *);
    opts->easy = 0;

    return;
}

int u_hmap_opts_copy (u_hmap_opts_t *to, u_hmap_opts_t *from)
{
    dbg_err_if (to == NULL);
    dbg_err_if (from == NULL);

    memcpy(to, from, sizeof(u_hmap_opts_t));

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

void u_hmap_opts_dbg (u_hmap_opts_t *opts)
{
    dbg_return_if (opts == NULL, );

    u_dbg("<hmap_options>");
    u_dbg("  easy: %s", opts->easy ? "yes" : "no");
    u_dbg("  discard policy: %s", __pcy2str(opts->policy));
    u_dbg("  buckets: %u (max: %u -- if discard policy != none)",
            opts->size, opts->max);
    u_dbg("  owns data: %s",
            (opts->options & U_HMAP_OPTS_OWNSDATA) ? "yes" : "no");
    u_dbg("  objects dtor: %s", opts->f_free ? "set" : "not set");
    u_dbg("  keys dtor: %s", opts->f_key_free ? "set" : "not set");
    u_dbg("  values dtor: %s", opts->f_val_free ? "set" : "not set");
    u_dbg("  object serializer: %s", opts->f_str ? "set" : "not set");
    u_dbg("  overwrite equal keys: %s",
            (opts->options & U_HMAP_OPTS_NO_OVERWRITE) ? "no" : "yes");
    u_dbg("  key type: %s", __datatype2str(opts->key_type));
    u_dbg("  value type: %s", __datatype2str(opts->val_type));
    u_dbg("</hmap_options>");

    return;
}

int u_hmap_opts_set_size (u_hmap_opts_t *opts, int sz)
{
    dbg_err_if (opts == NULL || sz <= 0);

    opts->size = sz;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_opts_set_max (u_hmap_opts_t *opts, int max)
{
    dbg_err_if (opts == NULL || max <= 0);

    opts->max = max;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_opts_set_type (u_hmap_opts_t *opts, u_hmap_type_t type)
{
    dbg_err_if (opts == NULL);
    dbg_err_if (!U_HMAP_IS_TYPE(type));

    opts->type = type;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_opts_set_option (u_hmap_opts_t *opts, int option)
{
    dbg_err_if (opts == NULL);

    dbg_err_if ((option != U_HMAP_OPTS_OWNSDATA &&
            option != U_HMAP_OPTS_NO_OVERWRITE &&
            option != U_HMAP_OPTS_HASH_STRONG));

    dbg_err_if (opts->easy &&
            option == U_HMAP_OPTS_OWNSDATA);

    opts->options |= option;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_opts_unset_option (u_hmap_opts_t *opts, int option)
{
    dbg_err_if (opts == NULL);

    dbg_err_if ((option != U_HMAP_OPTS_OWNSDATA &&
            option != U_HMAP_OPTS_NO_OVERWRITE &&
            option != U_HMAP_OPTS_HASH_STRONG));

    dbg_err_if (opts->easy &&
            option == U_HMAP_OPTS_OWNSDATA);

    opts->options &= ~option;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_opts_set_hashfunc (u_hmap_opts_t *opts,
        size_t (*f_hash)(const void *key, size_t buckets))
{
    dbg_err_if (opts == NULL || f_hash == NULL);

    opts->f_hash = f_hash;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_opts_set_compfunc (u_hmap_opts_t *opts,
        int (*f_comp)(const void *k1, const void *k2))
{
    dbg_err_if (opts == NULL || f_comp == NULL);

    opts->f_comp = f_comp;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_opts_set_freefunc (u_hmap_opts_t *opts,
        void (*f_free)(u_hmap_o_t *obj))
{
    dbg_err_if (opts == NULL || opts->easy);

    opts->f_free = f_free;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_opts_set_strfunc (u_hmap_opts_t *opts,
        u_string_t *(*f_str)(u_hmap_o_t *obj))
{
    dbg_err_if (opts == NULL);

    opts->f_str = f_str;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_opts_set_key_type (u_hmap_opts_t *opts,
        u_hmap_options_datatype_t type)
{
    dbg_err_if (opts == NULL);
    dbg_err_if (!U_HMAP_IS_DATATYPE(type));

    /* not available for hmap_easy interface */
    dbg_err_ifm (opts->easy,
            "cannot set data type when \"easy\" interface is in use");

    opts->key_type = type;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_opts_set_key_sz (u_hmap_opts_t *opts, size_t sz)
{
    dbg_err_if (opts == NULL || sz == 0);

    dbg_err_if (opts->easy);
    dbg_err_if (opts->key_type != U_HMAP_OPTS_DATATYPE_OPAQUE);

    opts->key_sz = sz;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_opts_set_key_freefunc (u_hmap_opts_t *opts,
        void (*f_free)(const void *key))
{
    dbg_err_if (opts == NULL);

    dbg_err_if (opts->easy);

    opts->f_key_free = f_free;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_opts_set_val_type (u_hmap_opts_t *opts,
        u_hmap_options_datatype_t type)
{
    dbg_err_if (opts == NULL);
    dbg_err_if (!U_HMAP_IS_DATATYPE(type));

    opts->val_type = type;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_opts_set_val_sz (u_hmap_opts_t *opts, size_t sz)
{
    dbg_err_if (opts == NULL || sz == 0);

    dbg_err_if (opts->val_type != U_HMAP_OPTS_DATATYPE_OPAQUE);

    opts->val_sz = sz;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_opts_set_val_freefunc (u_hmap_opts_t *opts,
        void (*f_free)(void *val))
{
    dbg_err_if (opts == NULL);

    opts->f_val_free = f_free;
    opts->val_free_set = 1;     /* keep track of this because setting it is
                                   FORCED when using easy interface */
    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_opts_set_policy (u_hmap_opts_t *opts, u_hmap_pcy_type_t policy)
{
    dbg_err_if (opts == NULL);
    dbg_err_if (!U_HMAP_IS_PCY(policy));

    opts->policy = policy;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_opts_set_policy_cmp (u_hmap_opts_t *opts,
        int (*f_pcy_cmp)(void *o1, void *o2))
{
    dbg_err_if (opts == NULL || f_pcy_cmp == NULL);
    dbg_err_if (opts->policy != U_HMAP_PCY_CUSTOM);

    opts->f_pcy_cmp = f_pcy_cmp;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

const char *u_hmap_strerror (u_hmap_ret_t rc)
{
    switch (rc)
    {
        case U_HMAP_ERR_NONE:
            return "success";
        case U_HMAP_ERR_FAIL:
            return "general failure";
        case U_HMAP_ERR_EXISTS:
            return "element already exists in table";
    }
    return NULL;
}

int u_hmap_copy (u_hmap_t *to, u_hmap_t *from)
{
    u_hmap_o_t *obj;
    size_t i;

    dbg_err_if (to == NULL);
    dbg_err_if (from == NULL);

    for (i = 0; i < from->size; ++i)
    {
        while ((obj = LIST_FIRST(&from->hmap[i])) != NULL)
        {
            LIST_REMOVE(obj, next);
            dbg_err_if (u_hmap_put(to, obj, NULL));
        }
    }

    return U_HMAP_ERR_NONE;

err:
    return U_HMAP_ERR_FAIL;
}

/* Retrieve an hmap element given a key */
static int __get (u_hmap_t *hmap, const void *key, u_hmap_o_t **o)
{
    u_hmap_o_t *obj;
    u_hmap_e_t *x;
    int comp;
    size_t hash;
    size_t last;

    dbg_err_if (hmap == NULL);
    dbg_err_if (key == NULL);
    dbg_err_if (o == NULL);

    hash = hmap->opts->f_hash(key, hmap->size);

    if (hmap->opts->f_hash != &__f_hash &&
            !(hmap->opts->options & U_HMAP_OPTS_HASH_STRONG))
    {
        enum { MAX_INT = 20 };
        char h[MAX_INT];

        u_snprintf(h, MAX_INT, "%u", hash);
        hash = __f_hash(h, hmap->size);
    }

    x = &hmap->hmap[hash];

    switch (hmap->opts->type)
    {
        case U_HMAP_TYPE_CHAIN:

            LIST_FOREACH(obj, x, next)
            {
                if ((comp = hmap->opts->f_comp(key, obj->key)) == 0)
                { /* object found */
                    *o = obj;
                    return U_HMAP_ERR_NONE;
                }
                else if (comp < 0)  /* cannot be in list (ordered) */
                {
                    *o = NULL;
                    break;
                }
            }
            break;

        case U_HMAP_TYPE_LINEAR:

            last = ((hash + hmap->size -1) % hmap->size);

            for (; hash != last; hash = ((hash +1) % hmap->size),
                    x = &hmap->hmap[hash])
            {
                if (!LIST_EMPTY(x))
                {
                    obj = LIST_FIRST(x);

                    if ((hmap->opts->f_comp(key, obj->key)) == 0)
                    {
                        *o = obj;
                        return U_HMAP_ERR_NONE;
                    }
                }
            }
            break;
    }

err:
    return U_HMAP_ERR_FAIL;
}

/* pop the front of an object queue */
static int __queue_pop_front (u_hmap_t *hmap, u_hmap_o_t **obj)
{
    u_hmap_q_t *first;

    dbg_err_if (hmap == NULL);

    dbg_err_if ((first = TAILQ_FIRST(&hmap->pcy.queue)) == NULL);
    dbg_err_if (u_hmap_del(hmap, first->ho->key, obj));
    TAILQ_REMOVE(&hmap->pcy.queue, first, next);
    __q_o_free(first);

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

/* pop the back of an object queue */
static int __queue_pop_back (u_hmap_t *hmap, u_hmap_o_t **obj)
{
    u_hmap_q_t *last;

    dbg_err_if (hmap == NULL);

    dbg_err_if ((last = TAILQ_LAST(&hmap->pcy.queue, u_hmap_q_h_s))
            == NULL);
    dbg_err_if (u_hmap_del(hmap, last->ho->key, obj));
    TAILQ_REMOVE(&hmap->pcy.queue, last, next);
    __q_o_free(last);

    return U_HMAP_ERR_NONE;

err:
    return U_HMAP_ERR_FAIL;
}

/* push object data onto queue */
static int __queue_push (u_hmap_t *hmap, u_hmap_o_t *obj,
        u_hmap_q_t **data)
{
    u_hmap_q_t *new;

    dbg_err_if (hmap == NULL);
    dbg_err_if (obj == NULL);
    dbg_err_if (data == NULL);

    if (*data == NULL)
    {  /* no existing reference to queue entry -> push to head
          (FIFO will always enter here) */
        dbg_err_if ((new = __q_o_new(obj)) == NULL);
        TAILQ_INSERT_HEAD(&hmap->pcy.queue, new, next);
        *data = new;
    } else {
        /* we already have an element in the queue -> move to head
           (LRU will enter here for all ops after first insert) */
        TAILQ_REMOVE(&hmap->pcy.queue, *data, next);
        TAILQ_INSERT_HEAD(&hmap->pcy.queue, *data, next);
    }

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

/* Increment count data object and push onto queue (LFU) */
static int __queue_push_count (u_hmap_t *hmap, u_hmap_o_t *obj,
        u_hmap_q_t **counts)
{
    u_hmap_q_t *new, *q;
    int *count;

    dbg_err_if (hmap == NULL);
    dbg_err_if (obj == NULL);
    dbg_err_if (counts == NULL);

    if (*counts == NULL)
    {
        /* no reference to queue entry -> count == 0 */
        dbg_err_if ((new = __q_o_new(obj)) == NULL);
        TAILQ_INSERT_HEAD(&hmap->pcy.queue, new, next);
        dbg_err_sif ((count = (int *) u_zalloc(sizeof(int))) == NULL);
        new->data = (void *) count;
        *counts = new;
        /*
        u_dbg(">k: %s, p: %d", new->ho->key, *((int *)new->data));
        */
    }
    else
    {
        /* we already have an element in the queue -> increment count
         and reposition it accordingly */
        count = (int *) (*counts)->data;
        *count = *count + 1;
        /*
        u_dbg("[");
        TAILQ_FOREACH(q, &hmap->pcy.queue, next)
            u_dbg("k: %s, p: %d", q->ho->key, *((int *)q->data));
        u_dbg("]");
        */
        for (q = TAILQ_NEXT(*counts, next);
                q && ((*count) >= *((int *) q->data));
                q = TAILQ_NEXT(q, next))
            ;
        TAILQ_REMOVE(&hmap->pcy.queue, *counts, next);
        if (q)  /* found an object with >= count -> insert just before */
            TAILQ_INSERT_BEFORE(q, *counts, next);
        else  /* we have the largest count -> last element */
            TAILQ_INSERT_TAIL(&hmap->pcy.queue, *counts, next);
    }

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

/* Push elements onto priority queue according to custom comparison function */
static int __queue_push_cmp (u_hmap_t *hmap, u_hmap_o_t *obj,
        u_hmap_q_t **data)
{
    u_hmap_q_t *new, *q;

    dbg_err_if (hmap == NULL);
    dbg_err_if (obj == NULL);
    dbg_err_if (data == NULL);

    /* no internal policy object should exist since it is managed externally */
    dbg_err_if (*data != NULL);

    dbg_err_if ((new = __q_o_new(obj)) == NULL);

    if (TAILQ_EMPTY(&hmap->pcy.queue))
    {
       TAILQ_INSERT_HEAD(&hmap->pcy.queue, new, next);
    }
    else
    {
        TAILQ_FOREACH(q, &hmap->pcy.queue, next)
        {
            /* found an object with >= priority -> insert just before */
            if (hmap->opts->f_pcy_cmp(obj->val, q->ho->val) >= 0)
            {
                TAILQ_INSERT_BEFORE(q, new, next);
                break;
            }
        }
        if (q == NULL)  /* reached end - append */
            TAILQ_INSERT_TAIL(&hmap->pcy.queue, new, next);
    }

    *data = new;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

/* Delete a specific queue element */
static int __queue_del (u_hmap_t *hmap, u_hmap_o_t *obj)
{
    dbg_err_if (hmap == NULL);
    dbg_err_if (obj == NULL);

    TAILQ_REMOVE(&hmap->pcy.queue, obj->pqe, next);
    __q_o_free(obj->pqe);
    obj->pqe = NULL;

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_foreach (u_hmap_t *hmap, int f(const void *val))
{
    u_hmap_o_t *obj;
    size_t i;

    dbg_err_if (hmap == NULL);
    dbg_err_if (f == NULL);

    for (i = 0; i < hmap->size; ++i)
    {
        LIST_FOREACH(obj, &hmap->hmap[i], next)
            dbg_err_if (f(obj->val));
    }

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_foreach_arg (u_hmap_t *hmap,
        int f(const void *val, const void *arg), void *arg)
{
    size_t i;
    u_hmap_o_t *obj;

    dbg_err_if (hmap == NULL);
    dbg_err_if (f == NULL);

    for (i = 0; i < hmap->size; ++i)
    {
        LIST_FOREACH(obj, &hmap->hmap[i], next)
            dbg_err_if (f(obj->val, arg));
    }

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

int u_hmap_foreach_keyval(u_hmap_t *hmap,
        int f(const void *key, const void *val))
{
    struct u_hmap_o_s *obj;
    size_t i;

    dbg_err_if (hmap == NULL);
    dbg_err_if (f == NULL);

    for (i = 0; i < hmap->size; ++i)
    {
        LIST_FOREACH(obj, &hmap->hmap[i], next)
            dbg_err_if (f(obj->key, obj->val));
    }

    return U_HMAP_ERR_NONE;
err:
    return U_HMAP_ERR_FAIL;
}

void u_hmap_dbg (u_hmap_t *hmap)
{
    enum { MAX_LINE = 255 };
    u_string_t *s = NULL, *st = NULL;
    u_hmap_o_t *obj;
    size_t i;

    dbg_ifb (hmap == NULL) return;

    for (i = 0; i < hmap->size; ++i)
    {
        if (LIST_FIRST(&hmap->hmap[i]) == NULL)
            continue;

        dbg_ifb (u_string_create("", 1, &s)) return;
        dbg_err_if (u_string_clear(s));
        dbg_err_if (u_string_aprintf(s, "%5d ", i));

        LIST_FOREACH(obj, &hmap->hmap[i], next)
        {
            if (hmap->opts->f_str == NULL)
            {
                dbg_err_if (u_string_cat(s, "[]"));
            }
            else
            {
                st = hmap->opts->f_str(obj);
                dbg_err_if (u_string_append(s, u_string_c(st),
                            u_string_len(st)-1));
                u_string_free(st);
            }
        }
        u_dbg(u_string_c(s));
        u_string_free(s);
    }

    return;
err:
    U_FREEF(st, u_string_free);
    U_FREEF(s, u_string_free);
    return;
}

void u_hmap_pcy_dbg (u_hmap_t *hmap)
{
    u_hmap_q_t *q;
    u_string_t *s = NULL, *s2 = NULL;

    dbg_ifb (hmap == NULL) return;

    dbg_ifb (u_string_create("", 1, &s)) return;
    dbg_err_if (u_string_clear(s));
    dbg_err_if (u_string_cat(s, "Policy: "));

    TAILQ_FOREACH(q, &hmap->pcy.queue, next)
    {
        s2 = hmap->opts->f_str(q->ho);
        dbg_err_if (u_string_cat(s, u_string_c(s2)));
        if (hmap->opts->policy == U_HMAP_PCY_LFU)  /* print count */
            dbg_err_if (u_string_aprintf(s, "-%d", *((int *)q->data)));
        u_string_free(s2);
    }

    u_dbg(u_string_c(s));
    u_string_free(s);

    return;
err:
    U_FREEF(s, u_string_free);
    U_FREEF(s2, u_string_free);
    return;
}

/* Allocate a new queue data object */
static u_hmap_q_t *__q_o_new (u_hmap_o_t *ho)
{
    u_hmap_q_t *qo = NULL;

    dbg_return_if (ho == NULL, NULL);

    dbg_err_sif ((qo = (u_hmap_q_t *)
                u_zalloc(sizeof(u_hmap_q_t))) == NULL);

    qo->ho = ho;
    qo->data = NULL;

    return qo;
err:
    u_free(qo);
    return NULL;
}

/* Free a data queue object */
static void __q_o_free (u_hmap_q_t *qo)
{
    dbg_ifb (qo == NULL) return;

    if (qo->data)
        u_free(qo->data);
    u_free(qo);
}

/* Get a string representation of a policy */
static const char *__pcy2str (u_hmap_pcy_type_t policy)
{
    switch (policy)
    {
        case U_HMAP_PCY_NONE:
            return "none";
        case U_HMAP_PCY_FIFO:
            return "fifo";
        case U_HMAP_PCY_LRU:
            return "lru";
        case U_HMAP_PCY_LFU:
            return "lfu";
        case U_HMAP_PCY_CUSTOM:
            return "custom";
    }
    return NULL;
}

/* Get a string representation of a policy */
static const char *__datatype2str(u_hmap_options_datatype_t datatype)
{
    switch (datatype)
    {
        case U_HMAP_OPTS_DATATYPE_POINTER:
            return "pointer";
        case U_HMAP_OPTS_DATATYPE_STRING:
            return "string";
        case U_HMAP_OPTS_DATATYPE_OPAQUE:
            return "opaque";
    }

    return NULL;
}

static int __next_prime(size_t *prime, size_t sz, size_t *idx)
{
    static size_t primes[] = {
        13, 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031,
        1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783, 19219,
        24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941, 204047,
        265271, 344857, 448321, 582821, 757693, 985003, 1280519, 1664681,
        2164111, 2813353, 3657361, 4754591, 6180989, 8035301, 10445899,
        13579681, 17653589, 22949669, 29834603, 38784989, 50420551, 65546729,
        85210757, 110774011, 144006217, 187208107, 243370577, 316381771,
        411296309, 534685237, 695090819, 903618083, 1174703521, 1527114613,
        1837299131, 2147483647
    };

    size_t i;

    dbg_err_if (prime == NULL);
    dbg_err_if (sz == 0);
    dbg_err_if (idx == NULL);

    for (i = *idx; i < sizeof(primes)/sizeof(size_t); ++i)
    {
        if (primes[i] >= sz)
        {
            *idx = i;
            *prime = primes[i];
            goto ok;
        }
    }
    dbg_err_ifm (1, "hmap size limit exceeded");

ok:
    return 0;

err:
    return ~0;
}

static int __resize(u_hmap_t *hmap)
{
    u_hmap_opts_t *newopts = NULL;
    u_hmap_t *newmap = NULL;

    dbg_err_if (hmap == NULL);

    if (hmap->opts->policy != U_HMAP_PCY_NONE)
        return 0;

    u_dbg("resize from: %u", hmap->size);

    /* copy old options */
    dbg_err_if (u_hmap_opts_new(&newopts));
    dbg_err_if (u_hmap_opts_copy(newopts, hmap->opts));

    /* set rate and create the new hashmap */
    dbg_err_if (__next_prime(&newopts->size,
            U_HMAP_RATE_RESIZE * newopts->size,
            &hmap->px));
    dbg_err_if (u_hmap_new(newopts, &newmap));
    u_hmap_opts_free(newopts);

    /* remove any ownership from old map to copy elements */
    hmap->opts->options &= !U_HMAP_OPTS_OWNSDATA;

    /* copy old elements to new map policy */
    dbg_err_if (u_hmap_copy(newmap, hmap));

    /* free old allocated objects */
    u_hmap_opts_free(hmap->opts);
    u_free(hmap->hmap);

    /* copy new map to this hmap */
    memcpy(hmap, newmap, sizeof(u_hmap_t));
    u_free(newmap);

    u_dbg("resized to: %u", hmap->size);

    return 0;
err:
    return ~0;
}