hashmap.c

/*====================================================================*
 -  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                     *
 *--------------------------------------------------------------------------*/
L_HASHMAP *
l_hmapCreate(l_int32  ninit,
             l_int32  maxocc)
{
l_uint32    size, tabsize;
L_HASHMAP  *hmap;
 
    PROCNAME("l_hmapCreate");
 
    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",
                  procName, maxocc, DefaultMaxOcc);
        maxocc = DefaultMaxOcc;
    }
    size = ninit / maxocc;
    if (size > MaxTabsize) {
        L_ERROR("ninit/maxocc = %d > MaxTabsize = %d\n", procName,
                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", procName, NULL);
    }
 
    hmap->nitems = 0;
    hmap->ntogo = ninit;
    hmap->maxocc = maxocc;
    hmap->tabsize = tabsize;
    return hmap;
}
 
 
void
l_hmapDestroy(L_HASHMAP  **phmap)
{
l_int32      i;
L_HASHITEM  *hitem, *next;
L_HASHMAP   *hmap;
 
    PROCNAME("l_hmapDestroy");
 
    if (phmap == NULL) {
        L_WARNING("ptr address is NULL!\n", procName);
        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                      *
 *--------------------------------------------------------------------------*/
L_HASHITEM *
l_hmapLookup(L_HASHMAP  *hmap,
             l_uint64    key,
             l_uint64    val,
             l_int32     op)
{
l_uint32     index;
L_HASHITEM  *hlist, *hitem;
 
    PROCNAME("l_hmapLookup");
 
    if (!hmap)
        return (L_HASHITEM *)ERROR_PTR("hmap not defined", procName, NULL);
    if (op != L_HMAP_CHECK && op != L_HMAP_CREATE)
        return (L_HASHITEM *)ERROR_PTR("invalid op", procName, 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;
}
 
 
l_ok
l_hmapRehash(L_HASHMAP  *hmap)
{
l_int32      i, index;
l_uint32     tabsize;
L_HASHITEM  *hstore, *hitem, *next;
 
    PROCNAME("l_hmapRehash");
 
    if (!hmap)
        return ERROR_INT("hmap not defined", procName, 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", procName, 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;
}