15734343726

Committed 18 Jun 2025 01:34PM UTC coverage: 71.06% (+0.01%) from 71.049%

Build # 15734343726

Build Type

Pull #12592

github

Committed by

web-flow

Commit Message

Merge 3d0ea274f into 29b0de830

Pull Request Pull Request #12592: VRTDerivedBand expressions: Add _CENTER_X_ and _CENTER_Y_ built-in variables

Run Details

44 of 47 new or added lines in 2 files covered. (93.62%)

39 existing lines in 24 files now uncovered.

574650 of 808682 relevant lines covered (71.06%)

250316.89 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

66.88

/frmts/gtiff/libtiff/tif_hash_set.c

/**********************************************************************
 *
 * 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>

/** List element structure. */
typedef struct _TIFFList TIFFList;

/** List element structure. */
struct _TIFFList
{
    /*! Pointer to the data object. Should be allocated and freed by the
     * caller.
     * */
    void *pData;
    /*! Pointer to the next element in list. NULL, if current element is the
     * last one.
     */
    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()                          */
/************************************************************************/

/**
 * Hash function for an arbitrary pointer
 *
 * @param elt the arbitrary pointer to hash
 *
 * @return the hash value of the pointer
 */

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

/************************************************************************/
/*                   TIFFHashSetEqualPointer()                          */
/************************************************************************/

/**
 * Equality function for arbitrary pointers
 *
 * @param elt1 the first arbitrary pointer to compare
 * @param elt2 the second arbitrary pointer to compare
 *
 * @return true if the pointers are equal
 */

static bool TIFFHashSetEqualPointer(const void *elt1, const void *elt2)
{
    return elt1 == elt2;
}

/************************************************************************/
/*                          TIFFHashSetNew()                             */
/************************************************************************/

/**
 * 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.
 *
 * @param fnHashFunc hash function. May be NULL.
 * @param fnEqualFunc equal function. May be NULL.
 * @param fnFreeEltFunc element free function. May be NULL.
 *
 * @return a new hash set
 */

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()                            */
/************************************************************************/

/**
 * Returns the number of elements inserted in the hash set
 *
 * Note: this is not the internal size of the hash set
 *
 * @param set the hash set
 *
 * @return the number of elements in the hash set
 */

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()                            */
/************************************************************************/

/**
 * Destroy a list. Caller responsible for freeing data objects contained in
 * list elements.
 *
 * @param psList pointer to list head.
 *
 */

static void TIFFListDestroy(TIFFList *psList)
{
    TIFFList *psCurrent = psList;

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

/************************************************************************/
/*                        TIFFHashSetDestroy()                          */
/************************************************************************/

/**
 * Destroys an allocated hash set.
 *
 * This function also frees the elements if a free function was
 * provided at the creation of the hash set.
 *
 * @param set the hash set
 */

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

#ifdef notused
/************************************************************************/
/*                        TIFFHashSetClear()                             */
/************************************************************************/

/**
 * Clear all elements from a hash set.
 *
 * This function also frees the elements if a free function was
 * provided at the creation of the hash set.
 *
 * @param set the hash set
 */

void TIFFHashSetClear(TIFFHashSet *set)
{
    TIFFHashSetClearInternal(set, false);
    set->nIndiceAllocatedSize = 0;
    set->nAllocatedSize = 53;
#ifdef HASH_DEBUG
    set->nCollisions = 0;
#endif
    set->nSize = 0;
}

/************************************************************************/
/*                       TIFFHashSetForeach()                           */
/************************************************************************/

/**
 * Walk through the hash set and runs the provided function on all the
 * elements
 *
 * This function is provided the user_data argument of TIFFHashSetForeach.
 * It must return true to go on the walk through the hash set, or FALSE to
 * make it stop.
 *
 * Note : the structure of the hash set must *NOT* be modified during the
 * walk.
 *
 * @param set the hash set.
 * @param fnIterFunc the function called on each element.
 * @param user_data the user data provided to the function.
 */

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()                          */
/************************************************************************/

/**
 * 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
 *
 * @param set the hash set
 * @param elt the new element to insert in the hash set
 *
 * @return true if success. If false is returned, elt has not been inserted,
 * but TIFFHashSetInsert() will have run the free function if provided.
 */

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()                           */
/************************************************************************/

/**
 * Returns the element found in the hash set corresponding to the element to
 * look up The element must not be modified.
 *
 * @param set the hash set
 * @param elt the element to look up in the hash set
 *
 * @return the element found in the hash set or NULL
 */

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()                          */
/************************************************************************/

/**
 * Removes an element from a hash set
 *
 * @param set the hash set
 * @param elt the new element to remove from the hash set
 *
 * @return true if the element was in the hash set
 */

bool TIFFHashSetRemove(TIFFHashSet *set, const void *elt)
{
    return TIFFHashSetRemoveInternal(set, elt, false);
}

#ifdef notused
/************************************************************************/
/*                     TIFFHashSetRemoveDeferRehash()                   */
/************************************************************************/

/**
 * Removes an element from a hash set.
 *
 * This will defer potential rehashing of the set to later calls to
 * TIFFHashSetInsert() or TIFFHashSetRemove().
 *
 * @param set the hash set
 * @param elt the new element to remove from the hash set
 *
 * @return true if the element was in the hash set
 */

bool TIFFHashSetRemoveDeferRehash(TIFFHashSet *set, const void *elt)
{
    return TIFFHashSetRemoveInternal(set, elt, true);
}
#endif

1	/**********************************************************************
2	*
3	* Name: tif_hash_set.c
4	* Purpose: Hash set functions.
5	* Author: Even Rouault, <even dot rouault at spatialys.com>
6	*
7	**********************************************************************
8	* Copyright (c) 2008-2009, Even Rouault <even dot rouault at spatialys.com>
9	*
10	* Permission is hereby granted, free of charge, to any person obtaining a
11	* copy of this software and associated documentation files (the "Software"),
12	* to deal in the Software without restriction, including without limitation
13	* the rights to use, copy, modify, merge, publish, distribute, sublicense,
14	* and/or sell copies of the Software, and to permit persons to whom the
15	* Software is furnished to do so, subject to the following conditions:
16	*
17	* The above copyright notice and this permission notice shall be included
18	* in all copies or substantial portions of the Software.
19	*
20	* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
21	* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22	* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
23	* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
24	* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
25	* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
26	* DEALINGS IN THE SOFTWARE.
27	****************************************************************************/
28
29	#include "tif_config.h"
30
31	#include "tif_hash_set.h"
32
33	#include <assert.h>
34	#include <stdbool.h>
35	#include <stdint.h>
36	#include <stdio.h>
37	#include <stdlib.h>
38
39	/** List element structure. */
40	typedef struct _TIFFList TIFFList;
41
42	/** List element structure. */
43	struct _TIFFList
44	{
45	/*! Pointer to the data object. Should be allocated and freed by the
46	* caller.
47	* */
48	void *pData;
49	/*! Pointer to the next element in list. NULL, if current element is the
50	* last one.
51	*/
52	struct _TIFFList *psNext;
53	};
54
55	struct _TIFFHashSet
56	{
57	TIFFHashSetHashFunc fnHashFunc;
58	TIFFHashSetEqualFunc fnEqualFunc;
59	TIFFHashSetFreeEltFunc fnFreeEltFunc;
60	TIFFList **tabList;
61	int nSize;
62	int nIndiceAllocatedSize;
63	int nAllocatedSize;
64	TIFFList *psRecyclingList;
65	int nRecyclingListSize;
66	bool bRehash;
67	#ifdef HASH_DEBUG
68	int nCollisions;
69	#endif
70	};
71
72	static const int anPrimes[] = {
73	53, 97, 193, 389, 769, 1543, 3079,
74	6151, 12289, 24593, 49157, 98317, 196613, 393241,
75	786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653,
76	100663319, 201326611, 402653189, 805306457, 1610612741};
77
78	/************************************************************************/
79	/* TIFFHashSetHashPointer() */
80	/************************************************************************/
81
82	/**
83	* Hash function for an arbitrary pointer
84	*
85	* @param elt the arbitrary pointer to hash
86	*
87	* @return the hash value of the pointer
88	*/
89
90	static unsigned long TIFFHashSetHashPointer(const void *elt)	×
91	{
92	return (unsigned long)(uintptr_t)((void *)(elt));	×
93	}
94
95	/************************************************************************/
96	/* TIFFHashSetEqualPointer() */
97	/************************************************************************/
98
99	/**
100	* Equality function for arbitrary pointers
101	*
102	* @param elt1 the first arbitrary pointer to compare
103	* @param elt2 the second arbitrary pointer to compare
104	*
105	* @return true if the pointers are equal
106	*/
107
108	static bool TIFFHashSetEqualPointer(const void elt1, const void elt2)	×
109	{
110	return elt1 == elt2;	×
111	}
112
113	/************************************************************************/
114	/* TIFFHashSetNew() */
115	/************************************************************************/
116
117	/**
118	* Creates a new hash set
119	*
120	* The hash function must return a hash value for the elements to insert.
121	* If fnHashFunc is NULL, TIFFHashSetHashPointer will be used.
122	*
123	* The equal function must return if two elements are equal.
124	* If fnEqualFunc is NULL, TIFFHashSetEqualPointer will be used.
125	*
126	* The free function is used to free elements inserted in the hash set,
127	* when the hash set is destroyed, when elements are removed or replaced.
128	* If fnFreeEltFunc is NULL, elements inserted into the hash set will not be
129	* freed.
130	*
131	* @param fnHashFunc hash function. May be NULL.
132	* @param fnEqualFunc equal function. May be NULL.
133	* @param fnFreeEltFunc element free function. May be NULL.
134	*
135	* @return a new hash set
136	*/
137
138	TIFFHashSet *TIFFHashSetNew(TIFFHashSetHashFunc fnHashFunc,	138,001✔
139	TIFFHashSetEqualFunc fnEqualFunc,
140	TIFFHashSetFreeEltFunc fnFreeEltFunc)
141	{
142	TIFFHashSet set = (TIFFHashSet )malloc(sizeof(TIFFHashSet));	138,001✔
143	if (set == NULL)	138,001✔
144	return NULL;	×
145	set->fnHashFunc = fnHashFunc ? fnHashFunc : TIFFHashSetHashPointer;	138,001✔
146	set->fnEqualFunc = fnEqualFunc ? fnEqualFunc : TIFFHashSetEqualPointer;	138,001✔
147	set->fnFreeEltFunc = fnFreeEltFunc;	138,001✔
148	set->nSize = 0;	138,001✔
149	set->tabList = (TIFFList *)(calloc(53, sizeof(TIFFList )));	138,001✔
150	if (set->tabList == NULL)	138,001✔
151	{
152	free(set);	×
153	return NULL;	×
154	}
155	set->nIndiceAllocatedSize = 0;	138,001✔
156	set->nAllocatedSize = 53;	138,001✔
157	set->psRecyclingList = NULL;	138,001✔
158	set->nRecyclingListSize = 0;	138,001✔
159	set->bRehash = false;	138,001✔
160	#ifdef HASH_DEBUG
161	set->nCollisions = 0;
162	#endif
163	return set;	138,001✔
164	}
165
166	/************************************************************************/
167	/* TIFFHashSetSize() */
168	/************************************************************************/
169
170	/**
171	* Returns the number of elements inserted in the hash set
172	*
173	* Note: this is not the internal size of the hash set
174	*
175	* @param set the hash set
176	*
177	* @return the number of elements in the hash set
178	*/
179
180	int TIFFHashSetSize(const TIFFHashSet *set)	76,795✔
181	{
182	assert(set != NULL);	76,795✔
183	return set->nSize;	76,795✔
184	}
185
186	/************************************************************************/
187	/* TIFFHashSetGetNewListElt() */
188	/************************************************************************/
189
190	static TIFFList TIFFHashSetGetNewListElt(TIFFHashSet set)	153,560✔
191	{
192	if (set->psRecyclingList)	153,560✔
193	{
194	TIFFList *psRet = set->psRecyclingList;	2,840✔
195	psRet->pData = NULL;	2,840✔
196	set->nRecyclingListSize--;	2,840✔
197	set->psRecyclingList = psRet->psNext;	2,840✔
198	return psRet;	2,840✔
199	}
200
201	return (TIFFList *)malloc(sizeof(TIFFList));	150,720✔
202	}
203
204	/************************************************************************/
205	/* TIFFHashSetReturnListElt() */
206	/************************************************************************/
207
208	static void TIFFHashSetReturnListElt(TIFFHashSet set, TIFFList psList)	2,862✔
209	{
210	if (set->nRecyclingListSize < 128)	2,862✔
211	{
212	psList->psNext = set->psRecyclingList;	2,862✔
213	set->psRecyclingList = psList;	2,862✔
214	set->nRecyclingListSize++;	2,862✔
215	}
216	else
217	{
218	free(psList);	×
219	}
220	}	2,862✔
221
222	/************************************************************************/
223	/* TIFFHashSetClearInternal() */
224	/************************************************************************/
225
226	static void TIFFHashSetClearInternal(TIFFHashSet *set, bool bFinalize)	138,114✔
227	{
228	assert(set != NULL);	138,114✔
229	for (int i = 0; i < set->nAllocatedSize; i++)	7,454,830✔
230	{
231	TIFFList *cur = set->tabList[i];	7,316,710✔
232	while (cur)	7,467,630✔
233	{
234	if (set->fnFreeEltFunc)	150,917✔
235	set->fnFreeEltFunc(cur->pData);	75,458✔
236	TIFFList *psNext = cur->psNext;	150,918✔
237	if (bFinalize)	150,918✔
238	free(cur);	150,918✔
239	else
240	TIFFHashSetReturnListElt(set, cur);	×
241	cur = psNext;	150,919✔
242	}
243	set->tabList[i] = NULL;	7,316,710✔
244	}
245	set->bRehash = false;	138,116✔
246	}	138,116✔
247
248	/************************************************************************/
249	/* TIFFListDestroy() */
250	/************************************************************************/
251
252	/**
253	* Destroy a list. Caller responsible for freeing data objects contained in
254	* list elements.
255	*
256	* @param psList pointer to list head.
257	*
258	*/
259
260	static void TIFFListDestroy(TIFFList *psList)	138,124✔
261	{
262	TIFFList *psCurrent = psList;	138,124✔
263
264	while (psCurrent)	138,146✔
265	{
266	TIFFList *const psNext = psCurrent->psNext;	22✔
267	free(psCurrent);	22✔
268	psCurrent = psNext;	22✔
269	}
270	}	138,124✔
271
272	/************************************************************************/
273	/* TIFFHashSetDestroy() */
274	/************************************************************************/
275
276	/**
277	* Destroys an allocated hash set.
278	*
279	* This function also frees the elements if a free function was
280	* provided at the creation of the hash set.
281	*
282	* @param set the hash set
283	*/
284
285	void TIFFHashSetDestroy(TIFFHashSet *set)	138,064✔
286	{
287	if (set)	138,064✔
288	{
289	TIFFHashSetClearInternal(set, true);	138,113✔
290	free(set->tabList);	138,123✔
291	TIFFListDestroy(set->psRecyclingList);	138,123✔
292	free(set);	138,123✔
293	}
294	}	138,074✔
295
296	#ifdef notused
297	/************************************************************************/
298	/* TIFFHashSetClear() */
299	/************************************************************************/
300
301	/**
302	* Clear all elements from a hash set.
303	*
304	* This function also frees the elements if a free function was
305	* provided at the creation of the hash set.
306	*
307	* @param set the hash set
308	*/
309
310	void TIFFHashSetClear(TIFFHashSet *set)
311	{
312	TIFFHashSetClearInternal(set, false);
313	set->nIndiceAllocatedSize = 0;
314	set->nAllocatedSize = 53;
315	#ifdef HASH_DEBUG
316	set->nCollisions = 0;
317	#endif
318	set->nSize = 0;
319	}
320
321	/************************************************************************/
322	/* TIFFHashSetForeach() */
323	/************************************************************************/
324
325	/**
326	* Walk through the hash set and runs the provided function on all the
327	* elements
328	*
329	* This function is provided the user_data argument of TIFFHashSetForeach.
330	* It must return true to go on the walk through the hash set, or FALSE to
331	* make it stop.
332	*
333	* Note : the structure of the hash set must NOT be modified during the
334	* walk.
335	*
336	* @param set the hash set.
337	* @param fnIterFunc the function called on each element.
338	* @param user_data the user data provided to the function.
339	*/
340
341	void TIFFHashSetForeach(TIFFHashSet *set, TIFFHashSetIterEltFunc fnIterFunc,
342	void *user_data)
343	{
344	assert(set != NULL);
345	if (!fnIterFunc)
346	return;
347
348	for (int i = 0; i < set->nAllocatedSize; i++)
349	{
350	TIFFList *cur = set->tabList[i];
351	while (cur)
352	{
353	if (!fnIterFunc(cur->pData, user_data))
354	return;
355
356	cur = cur->psNext;
357	}
358	}
359	}
360	#endif
361
362	/************************************************************************/
363	/* TIFFHashSetRehash() */
364	/************************************************************************/
365
366	static bool TIFFHashSetRehash(TIFFHashSet *set)	×
367	{
368	int nNewAllocatedSize = anPrimes[set->nIndiceAllocatedSize];	×
369	TIFFList **newTabList =
370	(TIFFList *)(calloc(nNewAllocatedSize, sizeof(TIFFList )));	×
371	if (newTabList == NULL)	×
372	return false;	×
373	#ifdef HASH_DEBUG
374	TIFFDebug("TIFFHASH",
375	"hashSet=%p, nSize=%d, nCollisions=%d, "
376	"fCollisionRate=%.02f",
377	set, set->nSize, set->nCollisions,
378	set->nCollisions * 100.0 / set->nSize);
379	set->nCollisions = 0;
380	#endif
381	for (int i = 0; i < set->nAllocatedSize; i++)	×
382	{
383	TIFFList *cur = set->tabList[i];	×
384	while (cur)	×
385	{
386	const unsigned long nNewHashVal =	×
387	set->fnHashFunc(cur->pData) % nNewAllocatedSize;	×
388	#ifdef HASH_DEBUG
389	if (newTabList[nNewHashVal])
390	set->nCollisions++;
391	#endif
392	TIFFList *psNext = cur->psNext;	×
393	cur->psNext = newTabList[nNewHashVal];	×
394	newTabList[nNewHashVal] = cur;	×
395	cur = psNext;	×
396	}
397	}
398	free(set->tabList);	×
399	set->tabList = newTabList;	×
400	set->nAllocatedSize = nNewAllocatedSize;	×
401	set->bRehash = false;	×
402	return true;	×
403	}
404
405	/************************************************************************/
406	/* TIFFHashSetFindPtr() */
407	/************************************************************************/
408
409	static void *TIFFHashSetFindPtr(TIFFHashSet set, const void *elt)	371,092✔
410	{
411	const unsigned long nHashVal = set->fnHashFunc(elt) % set->nAllocatedSize;	371,092✔
412	TIFFList *cur = set->tabList[nHashVal];	371,055✔
413	while (cur)	371,683✔
414	{
415	if (set->fnEqualFunc(cur->pData, elt))	62,731✔
416	return &cur->pData;	62,103✔
417	cur = cur->psNext;	628✔
418	}
419	return NULL;	308,952✔
420	}
421
422	/************************************************************************/
423	/* TIFFHashSetInsert() */
424	/************************************************************************/
425
426	/**
427	* Inserts an element into a hash set.
428	*
429	* If the element was already inserted in the hash set, the previous
430	* element is replaced by the new element. If a free function was provided,
431	* it is used to free the previously inserted element
432	*
433	* @param set the hash set
434	* @param elt the new element to insert in the hash set
435	*
436	* @return true if success. If false is returned, elt has not been inserted,
437	* but TIFFHashSetInsert() will have run the free function if provided.
438	*/
439
440	bool TIFFHashSetInsert(TIFFHashSet set, void elt)	153,487✔
441	{
442	assert(set != NULL);	153,487✔
443	void **pElt = TIFFHashSetFindPtr(set, elt);	153,487✔
444	if (pElt)	153,582✔
445	{
446	if (set->fnFreeEltFunc)	×
447	set->fnFreeEltFunc(*pElt);	×
448
449	*pElt = elt;	×
450	return true;	×
451	}
452
453	if (set->nSize >= 2 * set->nAllocatedSize / 3 \|\|	153,582✔
454	(set->bRehash && set->nIndiceAllocatedSize > 0 &&	153,613✔
455	set->nSize <= set->nAllocatedSize / 2))	×
456	{
UNCOV 457	set->nIndiceAllocatedSize++;	×
UNCOV 458	if (!TIFFHashSetRehash(set))	×
459	{
460	set->nIndiceAllocatedSize--;	×
461	if (set->fnFreeEltFunc)	×
462	set->fnFreeEltFunc(elt);	×
463	return false;	×
464	}
465	}
466
467	const unsigned long nHashVal = set->fnHashFunc(elt) % set->nAllocatedSize;	153,613✔
468	#ifdef HASH_DEBUG
469	if (set->tabList[nHashVal])
470	set->nCollisions++;
471	#endif
472
473	TIFFList *new_elt = TIFFHashSetGetNewListElt(set);	153,658✔
474	if (new_elt == NULL)	153,579✔
475	{
476	if (set->fnFreeEltFunc)	×
477	set->fnFreeEltFunc(elt);	×
478	return false;	×
479	}
480	new_elt->pData = elt;	153,579✔
481	new_elt->psNext = set->tabList[nHashVal];	153,579✔
482	set->tabList[nHashVal] = new_elt;	153,579✔
483	set->nSize++;	153,579✔
484
485	return true;	153,579✔
486	}
487
488	/************************************************************************/
489	/* TIFFHashSetLookup() */
490	/************************************************************************/
491
492	/**
493	* Returns the element found in the hash set corresponding to the element to
494	* look up The element must not be modified.
495	*
496	* @param set the hash set
497	* @param elt the element to look up in the hash set
498	*
499	* @return the element found in the hash set or NULL
500	*/
501
502	void TIFFHashSetLookup(TIFFHashSet set, const void *elt)	217,583✔
503	{
504	assert(set != NULL);	217,583✔
505	void **pElt = TIFFHashSetFindPtr(set, elt);	217,583✔
506	if (pElt)	217,497✔
507	return *pElt;	62,103✔
508
509	return NULL;	155,394✔
510	}
511
512	/************************************************************************/
513	/* TIFFHashSetRemoveInternal() */
514	/************************************************************************/
515
516	static bool TIFFHashSetRemoveInternal(TIFFHashSet set, const void elt,	2,862✔
517	bool bDeferRehash)
518	{
519	assert(set != NULL);	2,862✔
520	if (set->nIndiceAllocatedSize > 0 && set->nSize <= set->nAllocatedSize / 2)	2,862✔
521	{
522	set->nIndiceAllocatedSize--;	×
523	if (bDeferRehash)	×
524	set->bRehash = true;	×
525	else
526	{
527	if (!TIFFHashSetRehash(set))	×
528	{
529	set->nIndiceAllocatedSize++;	×
530	return false;	×
531	}
532	}
533	}
534
535	int nHashVal = (int)(set->fnHashFunc(elt) % set->nAllocatedSize);	2,862✔
536	TIFFList *cur = set->tabList[nHashVal];	2,862✔
537	TIFFList *prev = NULL;	2,862✔
538	while (cur)	2,862✔
539	{
540	if (set->fnEqualFunc(cur->pData, elt))	2,862✔
541	{
542	if (prev)	2,862✔
543	prev->psNext = cur->psNext;	×
544	else
545	set->tabList[nHashVal] = cur->psNext;	2,862✔
546
547	if (set->fnFreeEltFunc)	2,862✔
548	set->fnFreeEltFunc(cur->pData);	1,431✔
549
550	TIFFHashSetReturnListElt(set, cur);	2,862✔
551	#ifdef HASH_DEBUG
552	if (set->tabList[nHashVal])
553	set->nCollisions--;
554	#endif
555	set->nSize--;	2,862✔
556	return true;	2,862✔
557	}
558	prev = cur;	×
559	cur = cur->psNext;	×
560	}
561	return false;	×
562	}
563
564	/************************************************************************/
565	/* TIFFHashSetRemove() */
566	/************************************************************************/
567
568	/**
569	* Removes an element from a hash set
570	*
571	* @param set the hash set
572	* @param elt the new element to remove from the hash set
573	*
574	* @return true if the element was in the hash set
575	*/
576
577	bool TIFFHashSetRemove(TIFFHashSet set, const void elt)	2,862✔
578	{
579	return TIFFHashSetRemoveInternal(set, elt, false);	2,862✔
580	}
581
582	#ifdef notused
583	/************************************************************************/
584	/* TIFFHashSetRemoveDeferRehash() */
585	/************************************************************************/
586
587	/**
588	* Removes an element from a hash set.
589	*
590	* This will defer potential rehashing of the set to later calls to
591	* TIFFHashSetInsert() or TIFFHashSetRemove().
592	*
593	* @param set the hash set
594	* @param elt the new element to remove from the hash set
595	*
596	* @return true if the element was in the hash set
597	*/
598
599	bool TIFFHashSetRemoveDeferRehash(TIFFHashSet set, const void elt)
600	{
601	return TIFFHashSetRemoveInternal(set, elt, true);
602	}
603	#endif

OSGeo / gdal / 15734343726

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous