tif_hash_set.c

Go to the documentation of this file.

/**********************************************************************
 *
 * Name:     tif_hash_set.c
 * Purpose:  Hash set functions.
 * Author:   Even Rouault, <even dot rouault at spatialys.com>
 *
 **********************************************************************
 * Copyright (c) 2008-2009, Even Rouault <even dot rouault at spatialys.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 ****************************************************************************/
 
#include "tif_config.h"
 
#include "tif_hash_set.h"
 
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
 
typedef struct _TIFFList TIFFList;
 
struct _TIFFList
{
    void *pData;
    struct _TIFFList *psNext;
};
 
struct _TIFFHashSet
{
    TIFFHashSetHashFunc fnHashFunc;
    TIFFHashSetEqualFunc fnEqualFunc;
    TIFFHashSetFreeEltFunc fnFreeEltFunc;
    TIFFList **tabList;
    int nSize;
    int nIndiceAllocatedSize;
    int nAllocatedSize;
    TIFFList *psRecyclingList;
    int nRecyclingListSize;
    bool bRehash;
#ifdef HASH_DEBUG
    int nCollisions;
#endif
};
 
static const int anPrimes[] = {
    53,        97,        193,       389,       769,       1543,     3079,
    6151,      12289,     24593,     49157,     98317,     196613,   393241,
    786433,    1572869,   3145739,   6291469,   12582917,  25165843, 50331653,
    100663319, 201326611, 402653189, 805306457, 1610612741};
 
/************************************************************************/
/*                    TIFFHashSetHashPointer()                          */
/************************************************************************/
 
static unsigned long TIFFHashSetHashPointer(const void *elt)
{
    return (unsigned long)(uintptr_t)((void *)(elt));
}
 
/************************************************************************/
/*                   TIFFHashSetEqualPointer()                          */
/************************************************************************/
 
static bool TIFFHashSetEqualPointer(const void *elt1, const void *elt2)
{
    return elt1 == elt2;
}
 
/************************************************************************/
/*                          TIFFHashSetNew()                             */
/************************************************************************/
 
TIFFHashSet *TIFFHashSetNew(TIFFHashSetHashFunc fnHashFunc,
                            TIFFHashSetEqualFunc fnEqualFunc,
                            TIFFHashSetFreeEltFunc fnFreeEltFunc)
{
    TIFFHashSet *set = (TIFFHashSet *)malloc(sizeof(TIFFHashSet));
    if (set == NULL)
        return NULL;
    set->fnHashFunc = fnHashFunc ? fnHashFunc : TIFFHashSetHashPointer;
    set->fnEqualFunc = fnEqualFunc ? fnEqualFunc : TIFFHashSetEqualPointer;
    set->fnFreeEltFunc = fnFreeEltFunc;
    set->nSize = 0;
    set->tabList = (TIFFList **)(calloc(53, sizeof(TIFFList *)));
    if (set->tabList == NULL)
    {
        free(set);
        return NULL;
    }
    set->nIndiceAllocatedSize = 0;
    set->nAllocatedSize = 53;
    set->psRecyclingList = NULL;
    set->nRecyclingListSize = 0;
    set->bRehash = false;
#ifdef HASH_DEBUG
    set->nCollisions = 0;
#endif
    return set;
}
 
/************************************************************************/
/*                          TIFFHashSetSize()                            */
/************************************************************************/
 
int TIFFHashSetSize(const TIFFHashSet *set)
{
    assert(set != NULL);
    return set->nSize;
}
 
/************************************************************************/
/*                       TIFFHashSetGetNewListElt()                      */
/************************************************************************/
 
static TIFFList *TIFFHashSetGetNewListElt(TIFFHashSet *set)
{
    if (set->psRecyclingList)
    {
        TIFFList *psRet = set->psRecyclingList;
        psRet->pData = NULL;
        set->nRecyclingListSize--;
        set->psRecyclingList = psRet->psNext;
        return psRet;
    }
 
    return (TIFFList *)malloc(sizeof(TIFFList));
}
 
/************************************************************************/
/*                       TIFFHashSetReturnListElt()                      */
/************************************************************************/
 
static void TIFFHashSetReturnListElt(TIFFHashSet *set, TIFFList *psList)
{
    if (set->nRecyclingListSize < 128)
    {
        psList->psNext = set->psRecyclingList;
        set->psRecyclingList = psList;
        set->nRecyclingListSize++;
    }
    else
    {
        free(psList);
    }
}
 
/************************************************************************/
/*                   TIFFHashSetClearInternal()                          */
/************************************************************************/
 
static void TIFFHashSetClearInternal(TIFFHashSet *set, bool bFinalize)
{
    assert(set != NULL);
    for (int i = 0; i < set->nAllocatedSize; i++)
    {
        TIFFList *cur = set->tabList[i];
        while (cur)
        {
            if (set->fnFreeEltFunc)
                set->fnFreeEltFunc(cur->pData);
            TIFFList *psNext = cur->psNext;
            if (bFinalize)
                free(cur);
            else
                TIFFHashSetReturnListElt(set, cur);
            cur = psNext;
        }
        set->tabList[i] = NULL;
    }
    set->bRehash = false;
}
 
/************************************************************************/
/*                         TIFFListDestroy()                            */
/************************************************************************/
 
static void TIFFListDestroy(TIFFList *psList)
{
    TIFFList *psCurrent = psList;
 
    while (psCurrent)
    {
        TIFFList *const psNext = psCurrent->psNext;
        free(psCurrent);
        psCurrent = psNext;
    }
}
 
/************************************************************************/
/*                        TIFFHashSetDestroy()                          */
/************************************************************************/
 
void TIFFHashSetDestroy(TIFFHashSet *set)
{
    if (set)
    {
        TIFFHashSetClearInternal(set, true);
        free(set->tabList);
        TIFFListDestroy(set->psRecyclingList);
        free(set);
    }
}
 
#ifdef notused
/************************************************************************/
/*                        TIFFHashSetClear()                             */
/************************************************************************/
 
void TIFFHashSetClear(TIFFHashSet *set)
{
    TIFFHashSetClearInternal(set, false);
    set->nIndiceAllocatedSize = 0;
    set->nAllocatedSize = 53;
#ifdef HASH_DEBUG
    set->nCollisions = 0;
#endif
    set->nSize = 0;
}
 
/************************************************************************/
/*                       TIFFHashSetForeach()                           */
/************************************************************************/
 
void TIFFHashSetForeach(TIFFHashSet *set, TIFFHashSetIterEltFunc fnIterFunc,
                        void *user_data)
{
    assert(set != NULL);
    if (!fnIterFunc)
        return;
 
    for (int i = 0; i < set->nAllocatedSize; i++)
    {
        TIFFList *cur = set->tabList[i];
        while (cur)
        {
            if (!fnIterFunc(cur->pData, user_data))
                return;
 
            cur = cur->psNext;
        }
    }
}
#endif
 
/************************************************************************/
/*                        TIFFHashSetRehash()                           */
/************************************************************************/
 
static bool TIFFHashSetRehash(TIFFHashSet *set)
{
    int nNewAllocatedSize = anPrimes[set->nIndiceAllocatedSize];
    TIFFList **newTabList =
        (TIFFList **)(calloc(nNewAllocatedSize, sizeof(TIFFList *)));
    if (newTabList == NULL)
        return false;
#ifdef HASH_DEBUG
    TIFFDebug("TIFFHASH",
              "hashSet=%p, nSize=%d, nCollisions=%d, "
              "fCollisionRate=%.02f",
              set, set->nSize, set->nCollisions,
              set->nCollisions * 100.0 / set->nSize);
    set->nCollisions = 0;
#endif
    for (int i = 0; i < set->nAllocatedSize; i++)
    {
        TIFFList *cur = set->tabList[i];
        while (cur)
        {
            const unsigned long nNewHashVal =
                set->fnHashFunc(cur->pData) % nNewAllocatedSize;
#ifdef HASH_DEBUG
            if (newTabList[nNewHashVal])
                set->nCollisions++;
#endif
            TIFFList *psNext = cur->psNext;
            cur->psNext = newTabList[nNewHashVal];
            newTabList[nNewHashVal] = cur;
            cur = psNext;
        }
    }
    free(set->tabList);
    set->tabList = newTabList;
    set->nAllocatedSize = nNewAllocatedSize;
    set->bRehash = false;
    return true;
}
 
/************************************************************************/
/*                        TIFFHashSetFindPtr()                          */
/************************************************************************/
 
static void **TIFFHashSetFindPtr(TIFFHashSet *set, const void *elt)
{
    const unsigned long nHashVal = set->fnHashFunc(elt) % set->nAllocatedSize;
    TIFFList *cur = set->tabList[nHashVal];
    while (cur)
    {
        if (set->fnEqualFunc(cur->pData, elt))
            return &cur->pData;
        cur = cur->psNext;
    }
    return NULL;
}
 
/************************************************************************/
/*                         TIFFHashSetInsert()                          */
/************************************************************************/
 
bool TIFFHashSetInsert(TIFFHashSet *set, void *elt)
{
    assert(set != NULL);
    void **pElt = TIFFHashSetFindPtr(set, elt);
    if (pElt)
    {
        if (set->fnFreeEltFunc)
            set->fnFreeEltFunc(*pElt);
 
        *pElt = elt;
        return true;
    }
 
    if (set->nSize >= 2 * set->nAllocatedSize / 3 ||
        (set->bRehash && set->nIndiceAllocatedSize > 0 &&
         set->nSize <= set->nAllocatedSize / 2))
    {
        set->nIndiceAllocatedSize++;
        if (!TIFFHashSetRehash(set))
        {
            set->nIndiceAllocatedSize--;
            if (set->fnFreeEltFunc)
                set->fnFreeEltFunc(elt);
            return false;
        }
    }
 
    const unsigned long nHashVal = set->fnHashFunc(elt) % set->nAllocatedSize;
#ifdef HASH_DEBUG
    if (set->tabList[nHashVal])
        set->nCollisions++;
#endif
 
    TIFFList *new_elt = TIFFHashSetGetNewListElt(set);
    if (new_elt == NULL)
    {
        if (set->fnFreeEltFunc)
            set->fnFreeEltFunc(elt);
        return false;
    }
    new_elt->pData = elt;
    new_elt->psNext = set->tabList[nHashVal];
    set->tabList[nHashVal] = new_elt;
    set->nSize++;
 
    return true;
}
 
/************************************************************************/
/*                        TIFFHashSetLookup()                           */
/************************************************************************/
 
void *TIFFHashSetLookup(TIFFHashSet *set, const void *elt)
{
    assert(set != NULL);
    void **pElt = TIFFHashSetFindPtr(set, elt);
    if (pElt)
        return *pElt;
 
    return NULL;
}
 
/************************************************************************/
/*                     TIFFHashSetRemoveInternal()                      */
/************************************************************************/
 
static bool TIFFHashSetRemoveInternal(TIFFHashSet *set, const void *elt,
                                      bool bDeferRehash)
{
    assert(set != NULL);
    if (set->nIndiceAllocatedSize > 0 && set->nSize <= set->nAllocatedSize / 2)
    {
        set->nIndiceAllocatedSize--;
        if (bDeferRehash)
            set->bRehash = true;
        else
        {
            if (!TIFFHashSetRehash(set))
            {
                set->nIndiceAllocatedSize++;
                return false;
            }
        }
    }
 
    int nHashVal = (int)(set->fnHashFunc(elt) % set->nAllocatedSize);
    TIFFList *cur = set->tabList[nHashVal];
    TIFFList *prev = NULL;
    while (cur)
    {
        if (set->fnEqualFunc(cur->pData, elt))
        {
            if (prev)
                prev->psNext = cur->psNext;
            else
                set->tabList[nHashVal] = cur->psNext;
 
            if (set->fnFreeEltFunc)
                set->fnFreeEltFunc(cur->pData);
 
            TIFFHashSetReturnListElt(set, cur);
#ifdef HASH_DEBUG
            if (set->tabList[nHashVal])
                set->nCollisions--;
#endif
            set->nSize--;
            return true;
        }
        prev = cur;
        cur = cur->psNext;
    }
    return false;
}
 
/************************************************************************/
/*                         TIFFHashSetRemove()                          */
/************************************************************************/
 
bool TIFFHashSetRemove(TIFFHashSet *set, const void *elt)
{
    return TIFFHashSetRemoveInternal(set, elt, false);
}
 
#ifdef notused
/************************************************************************/
/*                     TIFFHashSetRemoveDeferRehash()                   */
/************************************************************************/
 
bool TIFFHashSetRemoveDeferRehash(TIFFHashSet *set, const void *elt)
{
    return TIFFHashSetRemoveInternal(set, elt, true);
}
#endif