path: root/src/hashmap.c

#include <bh/internal/hashmap.h>
#include <stdlib.h>
#include <string.h>

/**
 * \defgroup hashmap Hashmap
 *
 * Data stucture for storing pointers in the hashmap.
 * \{
 */

/**
 * Creates the new hashmap object.
 *
 * \param equal Comparision function
 * \param hash  Key hash function
 *
 * \return  On success, returns the pointer to the new hashmap object.
 * \return  On failure, returns a null pointer.
 */
bh_hashmap_t *bh_hashmap_new(bh_equal_cb_t equal,
                             bh_hash_cb_t hash)
{
    bh_hashmap_t *result;

    result = malloc(sizeof(*result));
    if (result)
        bh_hashmap_init(result, equal, hash);

    return result;
}

/**
 * Frees the \a hashmap object.
 *
 * \param hashmap   Pointer to the hashmap object to be freed
 */
void bh_hashmap_free(bh_hashmap_t *hashmap)
{
    bh_hashmap_destroy(hashmap);
    free(hashmap);
}

/**
 * Initializes the \a hashmap object.
 *
 * \warning This is an internal function.
 *
 * \param hashmap   Pointer to the hashmap object to be initialized
 * \param equal     Comparision function
 * \param hash      Key hash function
 */
void bh_hashmap_init(bh_hashmap_t *hashmap,
                     bh_equal_cb_t equal,
                     bh_hash_cb_t hash)
{
    memset(hashmap, 0, sizeof(*hashmap));
    hashmap->factor = 0.75f;
    hashmap->equal = equal;
    hashmap->hash = hash;
}

/**
 * Destroys the \a hashmap object.
 *
 * \warning This is an internal function.
 *
 * \param hashmap   Pointer to the hashmap object to be destroied
 */
void bh_hashmap_destroy(bh_hashmap_t *hashmap)
{
    if (hashmap->capacity)
    {
        free(hashmap->data);
        free(hashmap->psls);
    }
}

/**
 * Clears the \a hashmap object.
 *
 * \param hashmap   Pointer to the hashmap object to be cleared
 */
void bh_hashmap_clear(bh_hashmap_t *hashmap)
{
    if (hashmap->capacity)
        memset(hashmap->psls, 0, hashmap->capacity * sizeof(size_t));
    hashmap->size = 0;
}

/**
 * Reserves the space for \a size elements in the \a hashmap.
 *
 * This function can both expand and shrink the available space in \a hashmap.
 * This function takes into account current hashmap load factor.
 *
 * \param hashmap   Pointer to the hashmap object to be resized in terms of
 *                  capacity
 * \param size      New capacity of the hashmap
 *
 * \note Calling this function will invalidate iterators.
 * \note Actual hashmap capacity can be bigger then requested.
 *
 * \return  On success, returns zero value.
 * \return  On failure, returns error code.
 */
int bh_hashmap_reserve(bh_hashmap_t *hashmap,
                       size_t size)
{
    bh_hashmap_t other;
    size_t capacity, max_capacity, threshold;

    /* Calculate hashmap max capacity and capacity threshold */
    capacity = hashmap->capacity;
    threshold = hashmap->capacity * hashmap->factor;
    max_capacity = ((size_t)-1) / sizeof(bh_hashmap_node_t);

    /* New capacity can't be smaller then current hashmap size */
    if (size < hashmap->size)
        size = hashmap->size;

    /* Find new hashmap capacity */
    if (!size)
    {
        /* No capacity needed */
        capacity = 0;
        threshold = 0;
    }
    else if (size > threshold)
    {
        /* Bigger capacity needed - grow the hashmap */
        while (size > threshold)
        {
            capacity = (capacity) ? (capacity * 2) : (16);
            threshold = capacity * hashmap->factor;

            /* Capacity can't be bigger than max capacity and overflow */
            if (capacity > max_capacity || capacity < 16)
                return BH_OOM;
        }
    }
    else
    {
        /* Smaller capacity needed - shrink the hashmap */
        while (size <= threshold / 2 && capacity > 16)
        {
            capacity /= 2;
            threshold = capacity * hashmap->factor;
        }
    }

    /* Prevent same size reallocation */
    if (capacity == hashmap->capacity)
        return BH_OK;

    /* Initialize new hashmap */
    bh_hashmap_init(&other, hashmap->equal, hashmap->hash);
    other.factor = hashmap->factor;

    if (capacity)
    {
        void *iter;

        /* Allocate new memory for the hashmap */
        other.data = malloc(sizeof(*other.data) * capacity);
        other.psls = malloc(sizeof(size_t) * capacity);
        other.threshold = threshold;
        other.capacity = capacity;

        /* Check for allocations failure */
        if (!other.data || !other.psls)
        {
            if (other.data)
                free(other.data);
            if (other.psls)
                free(other.psls);
            return BH_OOM;
        }

        /* Reset probe sequence lengths */
        memset(other.psls, 0, sizeof(size_t) * other.capacity);

        /* Iterate and insert data into hashmap */
        iter = bh_hashmap_iter_next(hashmap, NULL);
        while (iter)
        {
            void *key, *value;

            key = bh_hashmap_iter_key(iter);
            value = bh_hashmap_iter_value(iter);
            bh_hashmap_insert(&other, key, value);

            iter = bh_hashmap_iter_next(hashmap, iter);
        }
    }

    /* Swap hashmaps */
    bh_hashmap_destroy(hashmap);
    *hashmap = other;
    return BH_OK;
}

/**
 * Inserts the pair of \a key and \a value into the \a hashmap. This function
 * allows duplicates to be inserted.
 *
 * \param hashmap   Pointer to the hashmap object
 * \param key       Key to be inserted
 * \param value     Value to be inserted
 *
 * \note Calling this function will invalidate iterators.
 *
 * \return  On success, returns zero value.
 * \return  On failure, returns error code.
 */
int bh_hashmap_insert(bh_hashmap_t *hashmap,
                      void *key,
                      void *value)
{
    size_t bucket, psl, tmp_psl;
    bh_hashmap_node_t item, tmp;

    /* Try to stay below hashmap threshold */
    if (hashmap->size + 1 > hashmap->threshold)
        if (bh_hashmap_reserve(hashmap, hashmap->size + 1))
            if (hashmap->size >= hashmap->capacity)
                return BH_OOM;

    /* Prepare inserted data and set PSL to 1 */
    item.key = key;
    item.value = value;
    psl = 1;

    /* Calculate prefered bucket index */
    bucket = hashmap->hash(key) & (hashmap->capacity - 1);

    /* Find empty bucket */
    while (hashmap->psls[bucket])
    {
        /* Current bucket is richer then us - swap elements */
        if (psl > hashmap->psls[bucket])
        {
            tmp = hashmap->data[bucket];
            tmp_psl = hashmap->psls[bucket];
            hashmap->data[bucket] = item;
            hashmap->psls[bucket] = psl;
            item = tmp;
            psl = tmp_psl;
        }

        bucket = (bucket + 1) & (hashmap->capacity - 1);
        psl++;
    }

    /* Found empty bucket - place item here */
    hashmap->data[bucket] = item;
    hashmap->psls[bucket] = psl;
    hashmap->size++;

    return BH_OK;
}

/**
 * Removes value from the \a hashmap by \a key.
 *
 * \param hashmap   Pointer to the hashmap object
 * \param key       Key value
 *
 * \note Calling this function will invalidate iterators.
 * \note If hashmap contains several key-value pairs with the same key, only
 *       one pair will be removed.
 */
void bh_hashmap_remove(bh_hashmap_t *hashmap,
                       void *key)
{
    void *iter;

    iter = bh_hashmap_iter_at(hashmap, key);
    if (iter)
        bh_hashmap_iter_remove(hashmap, iter);
}

/**
 * Returns the value from the \a hashmap by the specified \a key.
 *
 * If the \a exists is not null pointer, the value will be stored to indicated,
 * whether the \a key exists in the hashmap or not.
 *
 * \param hashmap   Pointer to the hashmap object
 * \param key       Key value
 * \param exists    Pointer to the exists flag variable (optional)
 *
 * \return  On success, returns value.
 * \return  On failure, return null pointer.
 */
void *bh_hashmap_at(bh_hashmap_t *hashmap,
                    void *key,
                    int *exists)
{
    void *iter;

    iter = bh_hashmap_iter_at(hashmap, key);
    if (iter)
    {
        /* If exists flag passed - set to 1 */
        if (exists)
            *exists = 1;
        return bh_hashmap_iter_value(iter);
    }

    /* If exists flag passed - set to 0 */
    if (exists)
        *exists = 0;
    return NULL;
}

/**
 * Checks if the \a hashmap is empty.
 *
 * \param hashmap   Pointer to the hashmap object
 *
 * \return  If hashmap is empty, returns non-zero value
 * \return  If hashmap is not empty, returns zero value
 */
int bh_hashmap_empty(bh_hashmap_t *hashmap)
{
    return !hashmap->size;
}

/**
 * Returns the size of the \a hashmap.
 *
 * \param hashmap   Pointer to the hashmap object
 *
 * \return  Returns the size of the hashmap.
 */
size_t bh_hashmap_size(bh_hashmap_t *hashmap)
{
    return hashmap->size;
}

/**
 * Returns the capacity of the \a hashmap.
 *
 * \param hashmap   Pointer to the hashmap object
 *
 * \return  Returns the capacity of the hashmap.
 */
size_t bh_hashmap_capacity(bh_hashmap_t *hashmap)
{
    return hashmap->capacity;
}

/**
 * Returns the load factor of the \a hashmap.
 *
 * \param hashmap   Pointer to the hashmap object
 *
 * \return  Returns the load factor of the hashmap.
 */
float bh_hashmap_factor(bh_hashmap_t *hashmap)
{
    return hashmap->factor;
}

/**
 * Sets the load \a factor of the \a hashmap.
 *
 * \param hashmap   Pointer to the hashmap object
 * \param factor    Load factor value
 *
 * \note New load factor will be applied on the next reserve/insert operation.
 */
void bh_hashmap_set_factor(bh_hashmap_t *hashmap,
                           float factor)
{
    /* Limit the factor value to [0.15, 1.0] */
    factor = (factor > 1.0f) ? (1.0f) : (factor);
    factor = (factor < 0.15f) ? (0.15f) : (factor);

    /* Calculate new threshold value */
    hashmap->factor = factor;
    hashmap->threshold = hashmap->capacity * factor;
}

/**
 * Returns the iterator to the element in the \a hashmap with specified \a key.
 *
 * \param hashmap   Pointer to the hashmap object
 * \param iter      Opaque iterator value
 *
 * \return  On success, returns iterator value.
 * \return  On failure, returns null pointer.
 *
 * \note If hashmap contains several key-value pairs with the same key, only
 *       iterator to the one of the pairs will returned.
 */
void *bh_hashmap_iter_at(bh_hashmap_t *hashmap,
                         void *key)
{
    size_t bucket, psl;

    /* Nothing can be in empty map */
    if (!hashmap->size)
        return NULL;

    /* Calculate prefered bucket index and set PSL to 1 */
    bucket = hashmap->hash(key) & (hashmap->capacity - 1);
    psl = 1;

    /* Iterate hashmap until we find element or find richer bucket */
    while (hashmap->psls[bucket] >= psl && hashmap->equal(hashmap->data[bucket].key, key))
    {
        bucket = (bucket + 1) & (hashmap->capacity - 1);
        psl++;
    }

    /* If bucket is poorer or equal to us - we found our element */
    if (hashmap->psls[bucket] >= psl)
        return hashmap->data + bucket;

    return NULL;
}

/**
 * Returns the iterator to the next element in the \a hashmap.
 *
 * \param hashmap   Pointer to the hashmap object
 * \param iter      Opaque iterator value
 *
 * \return  If the \a iter doesn't point to the last element of the hashmap,
 *          returns next iterator value.
 * \return  If the \a iter point to the last element of the hashmap, returns
 *          null pointer.
 * \return  If the \a iter is the null pointer, returns iterator to the
 *          first element of the hashmap.
 */
void *bh_hashmap_iter_next(bh_hashmap_t *hashmap,
                           void *iter)
{
    bh_hashmap_node_t *item;

    item = (bh_hashmap_node_t *)iter;
    while (1)
    {
        /* Advance or set iterator to the first element */
        if (item)
            item++;
        else
            item = hashmap->data;

        /* Check iterator for validity */
        if (item >= hashmap->data + hashmap->capacity)
            return NULL;

        /* Check iterator's item PSL */
        if (hashmap->psls[item - hashmap->data])
            return item;
    }
}

/**
 * Removes value from the \a hashmap by iterator \a iter.
 *
 * \param hashmap   Pointer to the hashmap object
 * \param iter      Iterator value
 *
 * \note Calling this function will invalidate iterators.
 */
void bh_hashmap_iter_remove(bh_hashmap_t *hashmap,
                            void *iter)
{
    size_t bucket, next_bucket;

    /* Check if hashmap is empty or we are given NULL iterator */
    if (!iter || !hashmap->size)
        return;

    /* Adjust hashmap size, calculate current and next bucket index */
    hashmap->size--;
    bucket = (bh_hashmap_node_t *)iter - hashmap->data;
    next_bucket = (bucket + 1) & (hashmap->capacity - 1);

    /* Shift all elements toward their preffered place */
    while (hashmap->psls[next_bucket] > 1)
    {
        /* Copy item and adjust PSL */
        hashmap->data[bucket] = hashmap->data[next_bucket];
        hashmap->psls[bucket] = hashmap->psls[next_bucket] - 1;

        /* Calculate next bucket index */
        bucket = next_bucket;
        next_bucket = (bucket + 1) & (hashmap->capacity - 1);
    }

    /* Reset bucket's PSL (mark empty) */
    hashmap->psls[bucket] = 0;
}

/**
 * Returns the key, pointed by the hashmap iterator \a iter.
 *
 * \param iter  Opaque iterator value
 *
 * \return  Returns key, pointed by iterator.
 */
void *bh_hashmap_iter_key(void *iter)
{
    return ((bh_hashmap_node_t *)iter)->key;
}

/**
 * Returns the value, pointed by the hashmap iterator \a iter.
 *
 * \param iter  Opaque iterator value
 *
 * \return  Returns value, pointed by iterator.
 */
void *bh_hashmap_iter_value(void *iter)
{
    return ((bh_hashmap_node_t *)iter)->value;
}

/**
 * \}
 */