/*************************************************************************/ /*!
@File
@Title          Self scaling hash tables
@Copyright      Copyright (c) Imagination Technologies Ltd. All Rights Reserved
@Description    Implements simple self scaling hash tables.
@License        Dual MIT/GPLv2

The contents of this file are subject to the MIT license as set out below.

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.

Alternatively, the contents of this file may be used under the terms of
the GNU General Public License Version 2 ("GPL") in which case the provisions
of GPL are applicable instead of those above.

If you wish to allow use of your version of this file only under the terms of
GPL, and not to allow others to use your version of this file under the terms
of the MIT license, indicate your decision by deleting the provisions above
and replace them with the notice and other provisions required by GPL as set
out in the file called "GPL-COPYING" included in this distribution. If you do
not delete the provisions above, a recipient may use your version of this file
under the terms of either the MIT license or GPL.

This License is also included in this distribution in the file called
"MIT-COPYING".

EXCEPT AS OTHERWISE STATED IN A NEGOTIATED AGREEMENT: (A) 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; AND (B) 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.
*/ /**************************************************************************/

#ifndef _HASH_H_
#define _HASH_H_

/* include5/ */
#include "img_types.h"

#include "pvrsrv_error.h"

#if defined (__cplusplus)
extern "C" {
#endif

/*
 * Keys passed to the comparsion function are only guaranteed to
 * be aligned on an uintptr_t boundary.
 */
typedef IMG_UINT32 HASH_FUNC(size_t uKeySize, void *pKey, IMG_UINT32 uHashTabLen);
typedef IMG_BOOL HASH_KEY_COMP(size_t uKeySize, void *pKey1, void *pKey2);

typedef struct _HASH_TABLE_ HASH_TABLE;

typedef PVRSRV_ERROR (*HASH_pfnCallback) (
	uintptr_t k,
	uintptr_t v
);

/*************************************************************************/ /*!
@Function       HASH_Func_Default
@Description    Hash function intended for hashing keys composed of
                uintptr_t arrays.
@Input          uKeySize     The size of the hash key, in bytes.
@Input          pKey         A pointer to the key to hash.
@Input          uHashTabLen  The length of the hash table.
@Return         The hash value.
*/ /**************************************************************************/
IMG_UINT32 HASH_Func_Default (size_t uKeySize, void *pKey, IMG_UINT32 uHashTabLen);

/*************************************************************************/ /*!
@Function       HASH_Key_Comp_Default
@Description    Compares keys composed of uintptr_t arrays.
@Input          uKeySize     The size of the hash key, in bytes.
@Input          pKey1        Pointer to first hash key to compare.
@Input          pKey2        Pointer to second hash key to compare.
@Return         IMG_TRUE  - the keys match.
                IMG_FALSE - the keys don't match.
*/ /**************************************************************************/
IMG_BOOL HASH_Key_Comp_Default (size_t uKeySize, void *pKey1, void *pKey2);

/*************************************************************************/ /*!
@Function       HASH_Create_Extended
@Description    Create a self scaling hash table, using the supplied
                key size, and the supllied hash and key comparsion
                functions.
@Input          uInitialLen   Initial and minimum length of the
                              hash table, where the length refers to the number
                              of entries in the hash table, not its size in
                              bytes.
@Input          uKeySize      The size of the key, in bytes.
@Input          pfnHashFunc   Pointer to hash function.
@Input          pfnKeyComp    Pointer to key comparsion function.
@Return         NULL or hash table handle.
*/ /**************************************************************************/
HASH_TABLE * HASH_Create_Extended (IMG_UINT32 uInitialLen, size_t uKeySize, HASH_FUNC *pfnHashFunc, HASH_KEY_COMP *pfnKeyComp);

/*************************************************************************/ /*!
@Function       HASH_Create
@Description    Create a self scaling hash table with a key
                consisting of a single uintptr_t, and using
                the default hash and key comparison functions.
@Input          uInitialLen   Initial and minimum length of the
                              hash table, where the length refers to the
                              number of entries in the hash table, not its size
                              in bytes.
@Return         NULL or hash table handle.
*/ /**************************************************************************/
HASH_TABLE * HASH_Create (IMG_UINT32 uInitialLen);

/*************************************************************************/ /*!
@Function       HASH_Delete
@Description    Delete a hash table created by HASH_Create_Extended or
                HASH_Create.  All entries in the table must have been
                removed before calling this function.
@Input          pHash         Hash table
*/ /**************************************************************************/
void HASH_Delete (HASH_TABLE *pHash);

/*************************************************************************/ /*!
@Function       HASH_Insert_Extended
@Description    Insert a key value pair into a hash table created
                with HASH_Create_Extended.
@Input          pHash         The hash table.
@Input          pKey          Pointer to the key.
@Input          v             The value associated with the key.
@Return         IMG_TRUE  - success
                IMG_FALSE  - failure
*/ /**************************************************************************/
IMG_BOOL HASH_Insert_Extended (HASH_TABLE *pHash, void *pKey, uintptr_t v);

/*************************************************************************/ /*!
@Function       HASH_Insert

@Description    Insert a key value pair into a hash table created with
                HASH_Create.
@Input          pHash         The hash table.
@Input          k             The key value.
@Input          v             The value associated with the key.
@Return         IMG_TRUE - success.
                IMG_FALSE - failure.
*/ /**************************************************************************/
IMG_BOOL HASH_Insert (HASH_TABLE *pHash, uintptr_t k, uintptr_t v);

/*************************************************************************/ /*!
@Function       HASH_Remove_Extended
@Description    Remove a key from a hash table created with
                HASH_Create_Extended.
@Input          pHash         The hash table.
@Input          pKey          Pointer to key.
@Return         0 if the key is missing, or the value associated
                with the key.
*/ /**************************************************************************/
uintptr_t HASH_Remove_Extended(HASH_TABLE *pHash, void *pKey);

/*************************************************************************/ /*!
@Function       HASH_Remove
@Description    Remove a key value pair from a hash table created
                with HASH_Create.
@Input          pHash         The hash table.
@Input          pKey          Pointer to key.
@Return         0 if the key is missing, or the value associated
                with the key.
*/ /**************************************************************************/
uintptr_t HASH_Remove (HASH_TABLE *pHash, uintptr_t k);

/*************************************************************************/ /*!
@Function       HASH_Retrieve_Extended
@Description    Retrieve a value from a hash table created with
                HASH_Create_Extended.
@Input          pHash         The hash table.
@Input          pKey          Pointer to key.
@Return         0 if the key is missing, or the value associated with
                the key.
*/ /**************************************************************************/
uintptr_t HASH_Retrieve_Extended (HASH_TABLE *pHash, void *pKey);

/*************************************************************************/ /*!
@Function       HASH_Retrieve
@Description    Retrieve a value from a hash table created with
                HASH_Create.
@Input          pHash         The hash table.
@Input          pKey          Pointer to key.
@Return         0 if the key is missing, or the value associated with
                the key.
*/ /**************************************************************************/
uintptr_t HASH_Retrieve (HASH_TABLE *pHash, uintptr_t k);

/*************************************************************************/ /*!
@Function       HASH_Iterate
@Description    Iterate over every entry in the hash table
@Input          pHash			Hash table to iterate
@Input          pfnCallback		Callback to call with the key and data for
								each entry in the hash table
@Return         Callback error if any, otherwise PVRSRV_OK
*/ /**************************************************************************/
PVRSRV_ERROR HASH_Iterate(HASH_TABLE *pHash, HASH_pfnCallback pfnCallback);

#ifdef HASH_TRACE
/*************************************************************************/ /*!
@Function       HASH_Dump
@Description    Dump out some information about a hash table.
@Input          pHash         The hash table.
*/ /**************************************************************************/
void HASH_Dump (HASH_TABLE *pHash);
#endif

#if defined (__cplusplus)
}
#endif

#endif /* _HASH_H_ */

/******************************************************************************
 End of file (hash.h)
******************************************************************************/