tif_hash_set.c File Reference

#include "tif_config.h"
#include "tif_hash_set.h"
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

Include dependency graph for tif_hash_set.c:

Go to the source code of this file.

Classes
struct	_TIFFList
struct	_TIFFHashSet

Typedefs
typedef struct _TIFFList	TIFFList

Functions
static unsigned long	TIFFHashSetHashPointer (const void *elt)
static bool	TIFFHashSetEqualPointer (const void *elt1, const void *elt2)
TIFFHashSet *	TIFFHashSetNew (TIFFHashSetHashFunc fnHashFunc, TIFFHashSetEqualFunc fnEqualFunc, TIFFHashSetFreeEltFunc fnFreeEltFunc)
int	TIFFHashSetSize (const TIFFHashSet *set)
static TIFFList *	TIFFHashSetGetNewListElt (TIFFHashSet *set)
static void	TIFFHashSetReturnListElt (TIFFHashSet *set, TIFFList *psList)
static void	TIFFHashSetClearInternal (TIFFHashSet *set, bool bFinalize)
static void	TIFFListDestroy (TIFFList *psList)
void	TIFFHashSetDestroy (TIFFHashSet *set)
static bool	TIFFHashSetRehash (TIFFHashSet *set)
static void **	TIFFHashSetFindPtr (TIFFHashSet *set, const void *elt)
bool	TIFFHashSetInsert (TIFFHashSet *set, void *elt)
void *	TIFFHashSetLookup (TIFFHashSet *set, const void *elt)
static bool	TIFFHashSetRemoveInternal (TIFFHashSet *set, const void *elt, bool bDeferRehash)
bool	TIFFHashSetRemove (TIFFHashSet *set, const void *elt)

Variables
static const int	anPrimes []

Typedef Documentation

TIFFList

typedef struct _TIFFList TIFFList

List element structure.

Definition at line 40 of file tif_hash_set.c.

Function Documentation

TIFFHashSetClearInternal()

static void TIFFHashSetClearInternal ( TIFFHashSet *  set, bool  bFinalize  )

static

Definition at line 226 of file tif_hash_set.c.

{
    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;
}

Referenced by TIFFHashSetDestroy().

TIFFHashSetDestroy()

void TIFFHashSetDestroy

(

TIFFHashSet *

set

)

Destroys an allocated hash set.

This function also frees the elements if a free function was provided at the creation of the hash set.

Parameters

set	the hash set

Definition at line 285 of file tif_hash_set.c.

{
    if (set)
    {
        TIFFHashSetClearInternal(set, true);
        free(set->tabList);
        TIFFListDestroy(set->psRecyclingList);
        free(set);
    }
}

Referenced by _TIFFCleanupIFDOffsetAndNumberMaps().

TIFFHashSetEqualPointer()

static bool TIFFHashSetEqualPointer ( const void *  elt1, const void *  elt2  )

static

Equality function for arbitrary pointers

Parameters

elt1	the first arbitrary pointer to compare
elt2	the second arbitrary pointer to compare

Returns

true if the pointers are equal

Definition at line 108 of file tif_hash_set.c.

{
    return elt1 == elt2;
}

Referenced by TIFFHashSetNew().

TIFFHashSetFindPtr()

static void ** TIFFHashSetFindPtr ( TIFFHashSet *  set, const void *  elt  )

static

Definition at line 409 of file tif_hash_set.c.

{
    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;
}

Referenced by TIFFHashSetInsert(), and TIFFHashSetLookup().

TIFFHashSetGetNewListElt()

static TIFFList * TIFFHashSetGetNewListElt ( TIFFHashSet *  set )

static

Definition at line 190 of file tif_hash_set.c.

{
    if (set->psRecyclingList)
    {
        TIFFList *psRet = set->psRecyclingList;
        psRet->pData = NULL;
        set->nRecyclingListSize--;
        set->psRecyclingList = psRet->psNext;
        return psRet;
    }
 
    return (TIFFList *)malloc(sizeof(TIFFList));
}

Referenced by TIFFHashSetInsert().

TIFFHashSetHashPointer()

static unsigned long TIFFHashSetHashPointer ( const void *  elt )

static

Hash function for an arbitrary pointer

Parameters

elt	the arbitrary pointer to hash

Returns

the hash value of the pointer

Definition at line 90 of file tif_hash_set.c.

{
    return (unsigned long)(uintptr_t)((void *)(elt));
}

Referenced by TIFFHashSetNew().

TIFFHashSetInsert()

bool TIFFHashSetInsert	(	TIFFHashSet *	set,
		void *	elt
	)

Inserts an element into a hash set.

If the element was already inserted in the hash set, the previous element is replaced by the new element. If a free function was provided, it is used to free the previously inserted element

Parameters

set	the hash set
elt	the new element to insert in the hash set

Returns

true if success. If false is returned, elt has not been inserted, but TIFFHashSetInsert() will have run the free function if provided.

Definition at line 440 of file tif_hash_set.c.

{
    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;
}

Referenced by _TIFFCheckDirNumberAndOffset().

TIFFHashSetLookup()

void * TIFFHashSetLookup	(	TIFFHashSet *	set,
		const void *	elt
	)

Returns the element found in the hash set corresponding to the element to look up The element must not be modified.

Parameters

set	the hash set
elt	the element to look up in the hash set

Returns

the element found in the hash set or NULL

Definition at line 502 of file tif_hash_set.c.

{
    assert(set != NULL);
    void **pElt = TIFFHashSetFindPtr(set, elt);
    if (pElt)
        return *pElt;
 
    return NULL;
}

Referenced by _TIFFCheckDirNumberAndOffset(), _TIFFGetDirNumberFromOffset(), _TIFFGetOffsetFromDirNumber(), and _TIFFRemoveEntryFromDirectoryListByOffset().

TIFFHashSetNew()

TIFFHashSet * TIFFHashSetNew	(	TIFFHashSetHashFunc	fnHashFunc,
		TIFFHashSetEqualFunc	fnEqualFunc,
		TIFFHashSetFreeEltFunc	fnFreeEltFunc
	)

Creates a new hash set

The hash function must return a hash value for the elements to insert. If fnHashFunc is NULL, TIFFHashSetHashPointer will be used.

The equal function must return if two elements are equal. If fnEqualFunc is NULL, TIFFHashSetEqualPointer will be used.

The free function is used to free elements inserted in the hash set, when the hash set is destroyed, when elements are removed or replaced. If fnFreeEltFunc is NULL, elements inserted into the hash set will not be freed.

Parameters

fnHashFunc	hash function. May be NULL.
fnEqualFunc	equal function. May be NULL.
fnFreeEltFunc	element free function. May be NULL.

Returns

a new hash set

Definition at line 138 of file tif_hash_set.c.

{
    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;
}

Referenced by _TIFFCheckDirNumberAndOffset().

TIFFHashSetRehash()

static bool TIFFHashSetRehash ( TIFFHashSet *  set )

static

Definition at line 366 of file tif_hash_set.c.

{
    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;
}

Referenced by TIFFHashSetInsert(), and TIFFHashSetRemoveInternal().

TIFFHashSetRemove()

bool TIFFHashSetRemove	(	TIFFHashSet *	set,
		const void *	elt
	)

Removes an element from a hash set

Parameters

set	the hash set
elt	the new element to remove from the hash set

Returns

true if the element was in the hash set

Definition at line 577 of file tif_hash_set.c.

{
    return TIFFHashSetRemoveInternal(set, elt, false);
}

Referenced by _TIFFCheckDirNumberAndOffset(), and _TIFFRemoveEntryFromDirectoryListByOffset().

TIFFHashSetRemoveInternal()

static bool TIFFHashSetRemoveInternal ( TIFFHashSet *  set, const void *  elt, bool  bDeferRehash  )

static

Definition at line 516 of file tif_hash_set.c.

{
    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;
}

Referenced by TIFFHashSetRemove().

TIFFHashSetReturnListElt()

static void TIFFHashSetReturnListElt ( TIFFHashSet *  set, TIFFList *  psList  )

static

Definition at line 208 of file tif_hash_set.c.

{
    if (set->nRecyclingListSize < 128)
    {
        psList->psNext = set->psRecyclingList;
        set->psRecyclingList = psList;
        set->nRecyclingListSize++;
    }
    else
    {
        free(psList);
    }
}

Referenced by TIFFHashSetClearInternal(), and TIFFHashSetRemoveInternal().

TIFFHashSetSize()

int TIFFHashSetSize

(

const TIFFHashSet *

set

)

Returns the number of elements inserted in the hash set

Note: this is not the internal size of the hash set

Parameters

set	the hash set

Returns

the number of elements in the hash set

Definition at line 180 of file tif_hash_set.c.

{
    assert(set != NULL);
    return set->nSize;
}

Referenced by _TIFFCheckDirNumberAndOffset().

TIFFListDestroy()

static void TIFFListDestroy ( TIFFList *  psList )

static

Destroy a list. Caller responsible for freeing data objects contained in list elements.

Parameters

psList

pointer to list head.

Definition at line 260 of file tif_hash_set.c.

{
    TIFFList *psCurrent = psList;
 
    while (psCurrent)
    {
        TIFFList *const psNext = psCurrent->psNext;
        free(psCurrent);
        psCurrent = psNext;
    }
}

Referenced by TIFFHashSetDestroy().

Variable Documentation

anPrimes

const int anPrimes[]

static

Initial value:

= {
    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}

Definition at line 72 of file tif_hash_set.c.

Referenced by TIFFHashSetRehash().