tif_hash_set.h File Reference

#include <stdbool.h>

Include dependency graph for tif_hash_set.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs
typedef struct _TIFFHashSet	TIFFHashSet
typedef unsigned long(*	TIFFHashSetHashFunc) (const void *elt)
typedef bool(*	TIFFHashSetEqualFunc) (const void *elt1, const void *elt2)
typedef void(*	TIFFHashSetFreeEltFunc) (void *elt)

Functions
TIFFHashSet *	TIFFHashSetNew (TIFFHashSetHashFunc fnHashFunc, TIFFHashSetEqualFunc fnEqualFunc, TIFFHashSetFreeEltFunc fnFreeEltFunc)
void	TIFFHashSetDestroy (TIFFHashSet *set)
int	TIFFHashSetSize (const TIFFHashSet *set)
bool	TIFFHashSetInsert (TIFFHashSet *set, void *elt)
void *	TIFFHashSetLookup (TIFFHashSet *set, const void *elt)
bool	TIFFHashSetRemove (TIFFHashSet *set, const void *elt)

Detailed Description

Hash set implementation.

An hash set is a data structure that holds elements that are unique according to a comparison function. Operations on the hash set, such as insertion, removal or lookup, are supposed to be fast if an efficient "hash" function is provided.

Definition in file tif_hash_set.h.

Typedef Documentation

TIFFHashSet

typedef struct _TIFFHashSet TIFFHashSet

Opaque type for a hash set

Definition at line 55 of file tif_hash_set.h.

TIFFHashSetEqualFunc

typedef bool(* TIFFHashSetEqualFunc) (const void *elt1, const void *elt2)

TIFFHashSetEqualFunc

Definition at line 61 of file tif_hash_set.h.

TIFFHashSetFreeEltFunc

typedef void(* TIFFHashSetFreeEltFunc) (void *elt)

TIFFHashSetFreeEltFunc

Definition at line 64 of file tif_hash_set.h.

TIFFHashSetHashFunc

typedef unsigned long(* TIFFHashSetHashFunc) (const void *elt)

TIFFHashSetHashFunc

Definition at line 58 of file tif_hash_set.h.

Function Documentation

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().

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().

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().

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().