drivers/staging/imgtec/rogue/hash.h

   1 /*************************************************************************/ /*!
   2 @File
   3 @Title          Self scaling hash tables
   4 @Copyright      Copyright (c) Imagination Technologies Ltd. All Rights Reserved
   5 @Description    Implements simple self scaling hash tables.
   6 @License        Dual MIT/GPLv2
   7
   8 The contents of this file are subject to the MIT license as set out below.
   9
  10 Permission is hereby granted, free of charge, to any person obtaining a copy
  11 of this software and associated documentation files (the "Software"), to deal
  12 in the Software without restriction, including without limitation the rights
  13 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  14 copies of the Software, and to permit persons to whom the Software is
  15 furnished to do so, subject to the following conditions:
  16
  17 The above copyright notice and this permission notice shall be included in
  18 all copies or substantial portions of the Software.
  19
  20 Alternatively, the contents of this file may be used under the terms of
  21 the GNU General Public License Version 2 ("GPL") in which case the provisions
  22 of GPL are applicable instead of those above.
  23
  24 If you wish to allow use of your version of this file only under the terms of
  25 GPL, and not to allow others to use your version of this file under the terms
  26 of the MIT license, indicate your decision by deleting the provisions above
  27 and replace them with the notice and other provisions required by GPL as set
  28 out in the file called "GPL-COPYING" included in this distribution. If you do
  29 not delete the provisions above, a recipient may use your version of this file
  30 under the terms of either the MIT license or GPL.
  31
  32 This License is also included in this distribution in the file called
  33 "MIT-COPYING".
  34
  35 EXCEPT AS OTHERWISE STATED IN A NEGOTIATED AGREEMENT: (A) THE SOFTWARE IS
  36 PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING
  37 BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  38 PURPOSE AND NONINFRINGEMENT; AND (B) IN NO EVENT SHALL THE AUTHORS OR
  39 COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
  40 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  41 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  42 */ /**************************************************************************/
  43
  44 #ifndef _HASH_H_
  45 #define _HASH_H_
  46
  47 /* include5/ */
  48 #include "img_types.h"
  49
  50 /* services/client/include/ or services/server/include/ */
  51 #include "osfunc.h"
  52
  53 #if defined (__cplusplus)
  54 extern "C" {
  55 #endif
  56
  57 /*
  58  * Keys passed to the comparsion function are only guaranteed to
  59  * be aligned on an uintptr_t boundary.
  60  */
  61 typedef IMG_UINT32 HASH_FUNC(size_t uKeySize, void *pKey, IMG_UINT32 uHashTabLen);
  62 typedef IMG_BOOL HASH_KEY_COMP(size_t uKeySize, void *pKey1, void *pKey2);
  63
  64 typedef struct _HASH_TABLE_ HASH_TABLE;
  65
  66 typedef PVRSRV_ERROR (*HASH_pfnCallback) (
  67         uintptr_t k,
  68         uintptr_t v
  69 );
  70
  71 /*************************************************************************/ /*!
  72 @Function       HASH_Func_Default
  73 @Description    Hash function intended for hashing keys composed of
  74                 uintptr_t arrays.
  75 @Input          uKeySize     The size of the hash key, in bytes.
  76 @Input          pKey         A pointer to the key to hash.
  77 @Input          uHashTabLen  The length of the hash table.
  78 @Return         The hash value.
  79 */ /**************************************************************************/
  80 IMG_UINT32 HASH_Func_Default (size_t uKeySize, void *pKey, IMG_UINT32 uHashTabLen);
  81
  82 /*************************************************************************/ /*!
  83 @Function       HASH_Key_Comp_Default
  84 @Description    Compares keys composed of uintptr_t arrays.
  85 @Input          uKeySize     The size of the hash key, in bytes.
  86 @Input          pKey1        Pointer to first hash key to compare.
  87 @Input          pKey2        Pointer to second hash key to compare.
  88 @Return         IMG_TRUE  - the keys match.
  89                 IMG_FALSE - the keys don't match.
  90 */ /**************************************************************************/
  91 IMG_BOOL HASH_Key_Comp_Default (size_t uKeySize, void *pKey1, void *pKey2);
  92
  93 /*************************************************************************/ /*!
  94 @Function       HASH_Create_Extended
  95 @Description    Create a self scaling hash table, using the supplied
  96                 key size, and the supllied hash and key comparsion
  97                 functions.
  98 @Input          uInitialLen   Initial and minimum length of the
  99                               hash table, where the length refers to the number
 100                               of entries in the hash table, not its size in
 101                               bytes.
 102 @Input          uKeySize      The size of the key, in bytes.
 103 @Input          pfnHashFunc   Pointer to hash function.
 104 @Input          pfnKeyComp    Pointer to key comparsion function.
 105 @Return         NULL or hash table handle.
 106 */ /**************************************************************************/
 107 HASH_TABLE * HASH_Create_Extended (IMG_UINT32 uInitialLen, size_t uKeySize, HASH_FUNC *pfnHashFunc, HASH_KEY_COMP *pfnKeyComp);
 108
 109 /*************************************************************************/ /*!
 110 @Function       HASH_Create
 111 @Description    Create a self scaling hash table with a key
 112                 consisting of a single uintptr_t, and using
 113                 the default hash and key comparison functions.
 114 @Input          uInitialLen   Initial and minimum length of the
 115                               hash table, where the length refers to the
 116                               number of entries in the hash table, not its size
 117                               in bytes.
 118 @Return         NULL or hash table handle.
 119 */ /**************************************************************************/
 120 HASH_TABLE * HASH_Create (IMG_UINT32 uInitialLen);
 121
 122 /*************************************************************************/ /*!
 123 @Function       HASH_Delete
 124 @Description    Delete a hash table created by HASH_Create_Extended or
 125                 HASH_Create.  All entries in the table must have been
 126                 removed before calling this function.
 127 @Input          pHash         Hash table
 128 */ /**************************************************************************/
 129 void HASH_Delete (HASH_TABLE *pHash);
 130
 131 /*************************************************************************/ /*!
 132 @Function       HASH_Insert_Extended
 133 @Description    Insert a key value pair into a hash table created
 134                 with HASH_Create_Extended.
 135 @Input          pHash         The hash table.
 136 @Input          pKey          Pointer to the key.
 137 @Input          v             The value associated with the key.
 138 @Return         IMG_TRUE  - success
 139                 IMG_FALSE  - failure
 140 */ /**************************************************************************/
 141 IMG_BOOL HASH_Insert_Extended (HASH_TABLE *pHash, void *pKey, uintptr_t v);
 142
 143 /*************************************************************************/ /*!
 144 @Function       HASH_Insert
 145
 146 @Description    Insert a key value pair into a hash table created with
 147                 HASH_Create.
 148 @Input          pHash         The hash table.
 149 @Input          k             The key value.
 150 @Input          v             The value associated with the key.
 151 @Return         IMG_TRUE - success.
 152                 IMG_FALSE - failure.
 153 */ /**************************************************************************/
 154 IMG_BOOL HASH_Insert (HASH_TABLE *pHash, uintptr_t k, uintptr_t v);
 155
 156 /*************************************************************************/ /*!
 157 @Function       HASH_Remove_Extended
 158 @Description    Remove a key from a hash table created with
 159                 HASH_Create_Extended.
 160 @Input          pHash         The hash table.
 161 @Input          pKey          Pointer to key.
 162 @Return         0 if the key is missing, or the value associated
 163                 with the key.
 164 */ /**************************************************************************/
 165 uintptr_t HASH_Remove_Extended(HASH_TABLE *pHash, void *pKey);
 166
 167 /*************************************************************************/ /*!
 168 @Function       HASH_Remove
 169 @Description    Remove a key value pair from a hash table created
 170                 with HASH_Create.
 171 @Input          pHash         The hash table.
 172 @Input          pKey          Pointer to key.
 173 @Return         0 if the key is missing, or the value associated
 174                 with the key.
 175 */ /**************************************************************************/
 176 uintptr_t HASH_Remove (HASH_TABLE *pHash, uintptr_t k);
 177
 178 /*************************************************************************/ /*!
 179 @Function       HASH_Retrieve_Extended
 180 @Description    Retrieve a value from a hash table created with
 181                 HASH_Create_Extended.
 182 @Input          pHash         The hash table.
 183 @Input          pKey          Pointer to key.
 184 @Return         0 if the key is missing, or the value associated with
 185                 the key.
 186 */ /**************************************************************************/
 187 uintptr_t HASH_Retrieve_Extended (HASH_TABLE *pHash, void *pKey);
 188
 189 /*************************************************************************/ /*!
 190 @Function       HASH_Retrieve
 191 @Description    Retrieve a value from a hash table created with
 192                 HASH_Create.
 193 @Input          pHash         The hash table.
 194 @Input          pKey          Pointer to key.
 195 @Return         0 if the key is missing, or the value associated with
 196                 the key.
 197 */ /**************************************************************************/
 198 uintptr_t HASH_Retrieve (HASH_TABLE *pHash, uintptr_t k);
 199
 200 /*************************************************************************/ /*!
 201 @Function       HASH_Iterate
 202 @Description    Iterate over every entry in the hash table
 203 @Input          pHash                   Hash table to iterate
 204 @Input          pfnCallback             Callback to call with the key and data for
 205                                                                 each entry in the hash table
 206 @Return         Callback error if any, otherwise PVRSRV_OK
 207 */ /**************************************************************************/
 208 PVRSRV_ERROR HASH_Iterate(HASH_TABLE *pHash, HASH_pfnCallback pfnCallback);
 209
 210 #ifdef HASH_TRACE
 211 /*************************************************************************/ /*!
 212 @Function       HASH_Dump
 213 @Description    Dump out some information about a hash table.
 214 @Input          pHash         The hash table.
 215 */ /**************************************************************************/
 216 void HASH_Dump (HASH_TABLE *pHash);
 217 #endif
 218
 219 #if defined (__cplusplus)
 220 }
 221 #endif
 222
 223 #endif /* _HASH_H_ */
 224
 225 /******************************************************************************
 226  End of file (hash.h)
 227 ******************************************************************************/
 228
 229