/*====================================================================*
 -  Copyright (C) 2001 Leptonica.  All rights reserved.
 -
 -  Redistribution and use in source and binary forms, with or without
 -  modification, are permitted provided that the following conditions
 -  are met:
 -  1. Redistributions of source code must retain the above copyright
 -     notice, this list of conditions and the following disclaimer.
 -  2. 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.
 -
 -  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 ANY
 -  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.
 *====================================================================*/

/*
 * \file  hashmap.c
 * <pre>
 *
 *      Hashmap creation, destruction
 *          L_HASHMAP    *l_hmapCreate()
 *          void          l_hmapDestroy()
 *
 *      Hashmap: Accessors and modifiers
 *          L_HASHITEM   *l_hmapLookup()
 *          l_int32       l_hmapRehash()
 *
 *    (1) See also hashmap.h for a brief description of the design.
 *    (2) In a typical use, a set of objects (in an array or associated
 *        with image pixels) is represented by a hashmap.  A uint64 key is
 *        produced for each object.  This integer is then hashed into an
 *        index in a hashtable, using the mod function with the table size
 *        which is a prime number.  Each entry in the hash table is a list
 *        of hash items.  In lookup, the appropriate list is traversed,
 *        looking for the object key found earlier.
 *    (3) Hash functions that map points, strings and float64 to uint64
 *        are given in utils1.c.
 *    (4) Use of the hashmap on points, strings and float64 data are
 *        given in ptafunc2.c, sarray2.c and dnafunc1.c.
 *    (5) Useful rule of thumb for hashing collisions:
 *        For a random hashing function (say, from strings to l_uint64),
 *        the probability of a collision increases as N^2 for N much
 *        less than 2^32.  The quadratic behavior switches over to
 *        approaching 1.0 around 2^32, which is the square root of 2^64.
 *        So, for example, if you have 10^7 strings, the probability
 *        of a single collision using an l_uint64 key is on the order of
 *            (10^7/4x10^9)^2 ~ 10^-5.
 *        For a million strings, collisions are very rare (~10^-7 probability).
 * </pre>
 */

#ifdef HAVE_CONFIG_H
#include <config_auto.h>
#endif  /* HAVE_CONFIG_H */

#include "allheaders.h"

    /* Limit on the hashtable size */
static const l_uint32  MaxTabsize = 50000000;
    /* Default values for creating the hashmap. */
static const l_int32   DefaultInitNItems = 2000;
static const l_int32   DefaultMaxOcc = 2;

/*--------------------------------------------------------------------------*
 *                     Hashmap creation and destruction                     *
 *--------------------------------------------------------------------------*/
/*!
 * \brief  l_hmapCreate()
 *
 * \param[in]   ninit   initial estimate of the number of items to be stored;
 *                      use 0 for default value.
 * \param[in]   maxocc  max average occupancy of each list of hashitme;
 *                      it should be in range [1 ... 5]; use 0 for default
 * \return      ptr to new hashmap, or NULL on error
 *
 * <pre>
 * Notes:
 *      (1) If the maximum number n of items to be hashed is known in
 *          advance, suggested values are:
 *                 %nint = 0.51 * n
 *                 %maxocc = 2
 *          With these values, the table will not need to be rehashed,
 *          even if all items have unique keys.
 *      (2) The actual initial size of the hashtab is the first prime
 *          number larger than %ninit/%maxocc.
 *      (3) Each entry into the hashtab points to alist of hash items
 *          (key, val, count).
 * </pre>
 */
L_HASHMAP *
l_hmapCreate(l_int32  ninit,
             l_int32  maxocc)
{
l_uint32    size, tabsize;
L_HASHMAP  *hmap;

    ninit = L_MAX(ninit, DefaultInitNItems);
    if (maxocc <= 0) maxocc = DefaultMaxOcc;
    if (maxocc > 5) {
        L_WARNING("maxocc = %d; non-optimal value. Set to default = %d\n",
                  __func__, maxocc, DefaultMaxOcc);
        maxocc = DefaultMaxOcc;
    }
    size = ninit / maxocc;
    if (size > MaxTabsize) {
        L_ERROR("ninit/maxocc = %d > MaxTabsize = %d\n", __func__,
                size, MaxTabsize);
        return NULL;
    }

    hmap = (L_HASHMAP *)LEPT_CALLOC(1, sizeof(L_HASHMAP));
    findNextLargerPrime(size, &tabsize);  /* at least 101 */
    if ((hmap->hashtab =
        (L_HASHITEM **)LEPT_CALLOC(tabsize, sizeof(L_HASHITEM *))) == NULL) {
        LEPT_FREE(hmap);
        return (L_HASHMAP *)ERROR_PTR("hashtab not made", __func__, NULL);
    }

    hmap->nitems = 0;
    hmap->ntogo = ninit;
    hmap->maxocc = maxocc;
    hmap->tabsize = tabsize;
    return hmap;
}


/*!
 * \brief  l_hmapDestroy()
 *
 * \param[in,out]   phmap  to be nulled, if it exists
 * \return          void
 */
void
l_hmapDestroy(L_HASHMAP  **phmap)
{
l_int32      i;
L_HASHITEM  *hitem, *next;
L_HASHMAP   *hmap;

    if (phmap == NULL) {
        L_WARNING("ptr address is NULL!\n", __func__);
        return;
    }

    if ((hmap = *phmap) == NULL)
        return;

    for (i = 0; i < hmap->tabsize; i++) {
        for (hitem = hmap->hashtab[i]; hitem != NULL; hitem = next) {
            next = hitem->next;
            LEPT_FREE(hitem);
        }
    }
    LEPT_FREE(hmap->hashtab);
    LEPT_FREE(hmap);
    *phmap = NULL;
}


/*--------------------------------------------------------------------------*
 *                    Hashmap: Accessors and modifiers                      *
 *--------------------------------------------------------------------------*/
/*!
 * \brief  l_hmapLookup()
 *
 * \param[in]   hmap
 * \param[in]   key     to be hashed into an index in the hashtab
 * \param[in]   val     to be stored in the hitem if creating it
 * \param[in]   op      L_HMAP_CHECK, L_HMAP_CREATE
 * \return      ptr     hitem; or null either on error or if not found
 *                      with op == L_HMAP_CHECK.
 *
 * <pre>
 * Notes:
 *      (1) This lookup function will also create a new hitem if requested.
 *      (2) The %op parameter does the following:
 *          op == L_HMAP_CHECK: return the hitem, or null if not found
 *          op == L_HMAP_CREATE: if found, increment the count; otherwise, make
 *                               and store a new hitem; always return the hitem.
 *      (3) The key is a uint64.  It is made by hashing some data in the object.
 *      (4) The value is an index into an array of the objects from which
 *          the hashtable has been constructed.
 *      (5) If an hitem is found, a pointer to it is returned.  It is owned
 *          by the hashtable; do not destroy it.
 * </pre>
 */
L_HASHITEM *
l_hmapLookup(L_HASHMAP  *hmap,
             l_uint64    key,
             l_uint64    val,
             l_int32     op)
{
l_uint32     index;
L_HASHITEM  *hlist, *hitem;

    if (!hmap)
        return (L_HASHITEM *)ERROR_PTR("hmap not defined", __func__, NULL);
    if (op != L_HMAP_CHECK && op != L_HMAP_CREATE)
        return (L_HASHITEM *)ERROR_PTR("invalid op", __func__, NULL);

        /* If found, return a ptr to the hitem (not a copy) */
    index = key % hmap->tabsize;  /* into hashtab */
    hlist = hmap->hashtab[index];  /* head of the list */
    for (hitem = hlist; hitem != NULL; hitem = hitem->next) {
        if (key == hitem->key) {
            if (op == L_HMAP_CREATE) hitem->count++;
            return hitem;
        }
    }
    if (op == L_HMAP_CHECK) return NULL;

        /* Not found and %op == L_HMAP_CREATE.
         * Make a new hitem and add to the head of the list */
    hitem = (L_HASHITEM *)LEPT_CALLOC(1, sizeof(L_HASHITEM));
    hitem->key = key;
    hitem->val = val;
    hitem->count = 1;
    hitem->next = hlist;
    hmap->hashtab[index] = hitem;
    hmap->nitems++;
    hmap->ntogo--;

        /* If hmap is full based on average occupancy, rehash */
    if (hmap->ntogo == 0)
        l_hmapRehash(hmap);

    return hitem;
}


/*!
 * \brief  l_hmapRehash()
 *
 * \param[in]  hmap
 * \return     0 if OK; 1 on error
 *
 * <pre>
 * Notes:
 *      (1) This is called when the average occupancy reaches maxocc.
 *          It doubles the size of the hashtab, and reuses the hash items.
 * </pre>
 */
l_ok
l_hmapRehash(L_HASHMAP  *hmap)
{
l_int32      i, index;
l_uint32     tabsize;
L_HASHITEM  *hstore, *hitem, *next;

    if (!hmap)
        return ERROR_INT("hmap not defined", __func__, 1);

        /* Put hash items in temporary storage in a single list,
         * successively adding each to the list head. */
    hstore = NULL;  /* ptr to resulting list */
    for (i = 0; i < hmap->tabsize; i++) {
        for (hitem = hmap->hashtab[i]; hitem != NULL; hitem = next) {
            next = hitem->next;
            hitem->next = hstore;
            hstore = hitem;
        }
    }

        /* Destroy the old hashtab and make a new one that is twice as big */
    LEPT_FREE(hmap->hashtab);
    findNextLargerPrime(2 * hmap->tabsize, &tabsize);
    hmap->tabsize = tabsize;
    hmap->hashtab = (L_HASHITEM **)LEPT_CALLOC(tabsize, sizeof(L_HASHITEM *));
    if (hmap->hashtab == NULL) {
        hmap->tabsize = 0;
        return ERROR_INT("hashtab ptr array not made", __func__, 1);
    }
    hmap->ntogo = hmap->maxocc * tabsize - hmap->nitems;

        /* Populate with the stored hash items */
    for (hitem = hstore; hitem != NULL; hitem = next) {
        next = hitem->next;
        index = hitem->key % tabsize;  /* into new hashtab */
        hitem->next = hmap->hashtab[index];  /* link to head of existing list */
        hmap->hashtab[index] = hitem;  /* put at head */
    }

    return 0;
}