tif_hash_set.c | Explore in Territory

/**********************************************************************
 *
 * 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 "tiffconf.h"

#include "tif_hash_set.h"

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

/** List element structure. */
TIFFList;

/** List element structure. */
struct _TIFFList
{ … };

struct _TIFFHashSet
{ … };

static const int anPrimes[] = …;

/************************************************************************/
/*                    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)
{ … }

/************************************************************************/
/*                   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)
{ … }

/************************************************************************/
/*                          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)
{ … }

/************************************************************************/
/*                          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)
{ … }

/************************************************************************/
/*                       TIFFHashSetGetNewListElt()                      */
/************************************************************************/

static TIFFList *TIFFHashSetGetNewListElt(TIFFHashSet *set)
{ … }

/************************************************************************/
/*                       TIFFHashSetReturnListElt()                      */
/************************************************************************/

static void TIFFHashSetReturnListElt(TIFFHashSet *set, TIFFList *psList)
{ … }

/************************************************************************/
/*                   TIFFHashSetClearInternal()                          */
/************************************************************************/

static void TIFFHashSetClearInternal(TIFFHashSet *set, bool bFinalize)
{ … }

/************************************************************************/
/*                         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)
{ … }

/************************************************************************/
/*                        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)
{ … }

#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)
{ … }

/************************************************************************/
/*                        TIFFHashSetFindPtr()                          */
/************************************************************************/

static void **TIFFHashSetFindPtr(TIFFHashSet *set, const void *elt)
{ … }

/************************************************************************/
/*                         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)
{ … }

/************************************************************************/
/*                        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)
{ … }

/************************************************************************/
/*                     TIFFHashSetRemoveInternal()                      */
/************************************************************************/

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

/************************************************************************/
/*                         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)
{ … }

#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
chromium/third_party/pdfium/third_party/libtiff/tif_hash_set.c
