/* Hash table implementation.

 *

 * This file implements in memory hash tables with insert/del/replace/find/

 * get-random-element operations. Hash tables will auto resize if needed

 * tables of power of two in size are used, collisions are handled by

 * chaining. See the source code for more information... :)

 *

 * Copyright (c) 2006-2010, Salvatore Sanfilippo <antirez at gmail dot com>

 * All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions are met:

 *

 *   * Redistributions of source code must retain the above copyright notice,

 *     this list of conditions and the following disclaimer.

 *   * Redistributions in binary form must reproduce the above copyright

 *     notice, this list of conditions and the following disclaimer in the

 *     documentation and/or other materials provided with the distribution.

 *   * Neither the name of Redis nor the names of its contributors may be used

 *     to endorse or promote products derived from this software without

 *     specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE

 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE

 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF

 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS

 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN

 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)

 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE

 * POSSIBILITY OF SUCH DAMAGE.

 */

#include "fmacros.h"

#include "alloc.h"

#include <stdlib.h>

#include <assert.h>

#include <limits.h>

#include "dict.h"

/* -------------------------- private prototypes ---------------------------- */

static int _dictExpandIfNeeded(dict *ht);

static unsigned long _dictNextPower(unsigned long size);

static int _dictKeyIndex(dict *ht, const void *key);

static int _dictInit(dict *ht, dictType *type, void *privDataPtr);

/* -------------------------- hash functions -------------------------------- */

/* Generic hash function (a popular one from Bernstein).

 * I tested a few and this was the best. */

static unsigned int dictGenHashFunction(const unsigned char *buf, int len) {

    unsigned int hash = 5381;

    while (len--)

        hash = ((hash << 5) + hash) + (*buf++); /* hash * 33 + c */

    return hash;

}

/* ----------------------------- API implementation ------------------------- */

/* Reset an hashtable already initialized with ht_init().

 * NOTE: This function should only called by ht_destroy(). */

static void _dictReset(dict *ht) {

    ht->table = NULL;

    ht->size = 0;

    ht->sizemask = 0;

    ht->used = 0;

}

/* Create a new hash table */

static dict *dictCreate(dictType *type, void *privDataPtr) {

    dict *ht = hi_malloc(sizeof(*ht));

    if (ht == NULL)

        return NULL;

    _dictInit(ht,type,privDataPtr);

    return ht;

}

/* Initialize the hash table */

static int _dictInit(dict *ht, dictType *type, void *privDataPtr) {

    _dictReset(ht);

    ht->type = type;

    ht->privdata = privDataPtr;

    return DICT_OK;

}

/* Expand or create the hashtable */

static int dictExpand(dict *ht, unsigned long size) {

    dict n; /* the new hashtable */

    unsigned long realsize = _dictNextPower(size), i;

    /* the size is invalid if it is smaller than the number of

     * elements already inside the hashtable */

    if (ht->used > size)

        return DICT_ERR;

    _dictInit(&n, ht->type, ht->privdata);

    n.size = realsize;

    n.sizemask = realsize-1;

    n.table = hi_calloc(realsize,sizeof(dictEntry*));

    if (n.table == NULL)

        return DICT_ERR;

    /* Copy all the elements from the old to the new table:

     * note that if the old hash table is empty ht->size is zero,

     * so dictExpand just creates an hash table. */

    n.used = ht->used;

    for (i = 0; i < ht->size && ht->used > 0; i++) {

        dictEntry *he, *nextHe;

        if (ht->table[i] == NULL) continue;

        /* For each hash entry on this slot... */

        he = ht->table[i];

        while(he) {

            unsigned int h;

            nextHe = he->next;

            /* Get the new element index */

            h = dictHashKey(ht, he->key) & n.sizemask;

            he->next = n.table[h];

            n.table[h] = he;

            ht->used--;

            /* Pass to the next element */

            he = nextHe;

        }

    }

    assert(ht->used == 0);

    hi_free(ht->table);

    /* Remap the new hashtable in the old */

    *ht = n;

    return DICT_OK;

}

/* Add an element to the target hash table */

static int dictAdd(dict *ht, void *key, void *val) {

    int index;

    dictEntry *entry;

    /* Get the index of the new element, or -1 if

     * the element already exists. */

    if ((index = _dictKeyIndex(ht, key)) == -1)

        return DICT_ERR;

    /* Allocates the memory and stores key */

    entry = hi_malloc(sizeof(*entry));

    if (entry == NULL)

        return DICT_ERR;

    entry->next = ht->table[index];

    ht->table[index] = entry;

    /* Set the hash entry fields. */

    dictSetHashKey(ht, entry, key);

    dictSetHashVal(ht, entry, val);

    ht->used++;

    return DICT_OK;

}

/* Add an element, discarding the old if the key already exists.

 * Return 1 if the key was added from scratch, 0 if there was already an

 * element with such key and dictReplace() just performed a value update

 * operation. */

static int dictReplace(dict *ht, void *key, void *val) {

    dictEntry *entry, auxentry;

    /* Try to add the element. If the key

     * does not exists dictAdd will succeed. */

    if (dictAdd(ht, key, val) == DICT_OK)

        return 1;

    /* It already exists, get the entry */

    entry = dictFind(ht, key);

    if (entry == NULL)

        return 0;

    /* Free the old value and set the new one */

    /* Set the new value and free the old one. Note that it is important

     * to do that in this order, as the value may just be exactly the same

     * as the previous one. In this context, think to reference counting,

     * you want to increment (set), and then decrement (free), and not the

     * reverse. */

    auxentry = *entry;

    dictSetHashVal(ht, entry, val);

    dictFreeEntryVal(ht, &auxentry);

    return 0;

}

/* Search and remove an element */

static int dictDelete(dict *ht, const void *key) {

    unsigned int h;

    dictEntry *de, *prevde;

    if (ht->size == 0)

        return DICT_ERR;

    h = dictHashKey(ht, key) & ht->sizemask;

    de = ht->table[h];

    prevde = NULL;

    while(de) {

        if (dictCompareHashKeys(ht,key,de->key)) {

            /* Unlink the element from the list */

            if (prevde)

                prevde->next = de->next;

            else

                ht->table[h] = de->next;

            dictFreeEntryKey(ht,de);

            dictFreeEntryVal(ht,de);

            hi_free(de);

            ht->used--;

            return DICT_OK;

        }

        prevde = de;

        de = de->next;

    }

    return DICT_ERR; /* not found */

}

/* Destroy an entire hash table */

static int _dictClear(dict *ht) {

    unsigned long i;

    /* Free all the elements */

    for (i = 0; i < ht->size && ht->used > 0; i++) {

        dictEntry *he, *nextHe;

        if ((he = ht->table[i]) == NULL) continue;

        while(he) {

            nextHe = he->next;

            dictFreeEntryKey(ht, he);

            dictFreeEntryVal(ht, he);

            hi_free(he);

            ht->used--;

            he = nextHe;

        }

    }

    /* Free the table and the allocated cache structure */

    hi_free(ht->table);

    /* Re-initialize the table */

    _dictReset(ht);

    return DICT_OK; /* never fails */

}

/* Clear & Release the hash table */

static void dictRelease(dict *ht) {

    _dictClear(ht);

    hi_free(ht);

}

static dictEntry *dictFind(dict *ht, const void *key) {

    dictEntry *he;

    unsigned int h;

    if (ht->size == 0) return NULL;

    h = dictHashKey(ht, key) & ht->sizemask;

    he = ht->table[h];

    while(he) {

        if (dictCompareHashKeys(ht, key, he->key))

            return he;

        he = he->next;

    }

    return NULL;

}

static void dictInitIterator(dictIterator *iter, dict *ht) {

    iter->ht = ht;

    iter->index = -1;

    iter->entry = NULL;

    iter->nextEntry = NULL;

}

static dictEntry *dictNext(dictIterator *iter) {

    while (1) {

        if (iter->entry == NULL) {

            iter->index++;

            if (iter->index >=

                    (signed)iter->ht->size) break;

            iter->entry = iter->ht->table[iter->index];

        } else {

            iter->entry = iter->nextEntry;

        }

        if (iter->entry) {

            /* We need to save the 'next' here, the iterator user

             * may delete the entry we are returning. */

            iter->nextEntry = iter->entry->next;

            return iter->entry;

        }

    }

    return NULL;

}

/* ------------------------- private functions ------------------------------ */

/* Expand the hash table if needed */

static int _dictExpandIfNeeded(dict *ht) {

    /* If the hash table is empty expand it to the initial size,

     * if the table is "full" double its size. */

    if (ht->size == 0)

        return dictExpand(ht, DICT_HT_INITIAL_SIZE);

    if (ht->used == ht->size)

        return dictExpand(ht, ht->size*2);

    return DICT_OK;

}

/* Our hash table capability is a power of two */

static unsigned long _dictNextPower(unsigned long size) {

    unsigned long i = DICT_HT_INITIAL_SIZE;

    if (size >= LONG_MAX) return LONG_MAX;

    while(1) {

        if (i >= size)

            return i;

        i *= 2;

    }

}

/* Returns the index of a free slot that can be populated with

 * an hash entry for the given 'key'.

 * If the key already exists, -1 is returned. */

static int _dictKeyIndex(dict *ht, const void *key) {

    unsigned int h;

    dictEntry *he;

    /* Expand the hashtable if needed */

    if (_dictExpandIfNeeded(ht) == DICT_ERR)

        return -1;

    /* Compute the key hash value */

    h = dictHashKey(ht, key) & ht->sizemask;

    /* Search if this slot does not already contain the given key */

    he = ht->table[h];

    while(he) {

        if (dictCompareHashKeys(ht, key, he->key))

            return -1;

        he = he->next;

    }

    return h;

}