diff options
Diffstat (limited to 'sgx/services4/srvkm/common/hash.c')
| -rw-r--r-- | sgx/services4/srvkm/common/hash.c | 336 |
1 files changed, 285 insertions, 51 deletions
diff --git a/sgx/services4/srvkm/common/hash.c b/sgx/services4/srvkm/common/hash.c index 78eab44..a3791fa 100644 --- a/sgx/services4/srvkm/common/hash.c +++ b/sgx/services4/srvkm/common/hash.c @@ -1,28 +1,50 @@ -/********************************************************************** - * - * Copyright (C) Imagination Technologies Ltd. All rights reserved. - * - * This program is free software; you can redistribute it and/or modify it - * under the terms and conditions of the GNU General Public License, - * version 2, as published by the Free Software Foundation. - * - * This program is distributed in the hope it will be useful but, except - * as otherwise stated in writing, without any warranty; without even the - * implied warranty of merchantability or fitness for a particular purpose. - * See the GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License along with - * this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA. - * - * The full GNU General Public License is included in this distribution in - * the file called "COPYING". - * - * Contact Information: - * Imagination Technologies Ltd. <gpl-support@imgtec.com> - * Home Park Estate, Kings Langley, Herts, WD4 8LZ, UK - * - ******************************************************************************/ +/*************************************************************************/ /*! +@Title Self scaling hash tables. +@Copyright Copyright (c) Imagination Technologies Ltd. All Rights Reserved +@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. + +@Description + Implements simple self scaling hash tables. Hash collisions are + handled by chaining entries together. Hash tables are increased in + size when they become more than (50%?) full and decreased in size + when less than (25%?) full. Hash tables are never decreased below + their initial size. +*/ /**************************************************************************/ #include "pvr_debug.h" #include "img_defs.h" @@ -39,43 +61,57 @@ #define KEY_COMPARE(pHash, pKey1, pKey2) \ ((pHash)->pfnKeyComp((pHash)->uKeySize, (pKey1), (pKey2))) +/* Each entry in a hash table is placed into a bucket */ struct _BUCKET_ { - + /* the next bucket on the same chain */ struct _BUCKET_ *pNext; - + /* entry value */ IMG_UINTPTR_T v; - - IMG_UINTPTR_T k[]; + /* entry key */ + IMG_UINTPTR_T k[]; /* PRQA S 0642 */ /* override dynamic array declaration warning */ }; typedef struct _BUCKET_ BUCKET; struct _HASH_TABLE_ { - + /* the hash table array */ BUCKET **ppBucketTable; - + /* current size of the hash table */ IMG_UINT32 uSize; - + /* number of entries currently in the hash table */ IMG_UINT32 uCount; - + /* the minimum size that the hash table should be re-sized to */ IMG_UINT32 uMinimumSize; - + /* size of key in bytes */ IMG_UINT32 uKeySize; - + /* hash function */ HASH_FUNC *pfnHashFunc; - + /* key comparison function */ HASH_KEY_COMP *pfnKeyComp; }; +/*! +****************************************************************************** + @Function HASH_Func_Default + + @Description Hash function intended for hashing keys composed of + IMG_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 (IMG_SIZE_T uKeySize, IMG_VOID *pKey, IMG_UINT32 uHashTabLen) { @@ -107,6 +143,18 @@ HASH_Func_Default (IMG_SIZE_T uKeySize, IMG_VOID *pKey, IMG_UINT32 uHashTabLen) return uHashKey; } +/*! +****************************************************************************** + @Function HASH_Key_Comp_Default + + @Description Compares keys composed of IMG_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 (IMG_SIZE_T uKeySize, IMG_VOID *pKey1, IMG_VOID *pKey2) { @@ -126,6 +174,18 @@ HASH_Key_Comp_Default (IMG_SIZE_T uKeySize, IMG_VOID *pKey1, IMG_VOID *pKey2) return IMG_TRUE; } +/*! +****************************************************************************** + @Function _ChainInsert + + @Description Insert a bucket into the appropriate hash table chain. + + @Input pBucket - the bucket + @Input ppBucketTable - the hash table + @Input uSize - the size of the hash table + + @Return PVRSRV_ERROR +******************************************************************************/ static PVRSRV_ERROR _ChainInsert (HASH_TABLE *pHash, BUCKET *pBucket, BUCKET **ppBucketTable, IMG_UINT32 uSize) { @@ -141,13 +201,27 @@ _ChainInsert (HASH_TABLE *pHash, BUCKET *pBucket, BUCKET **ppBucketTable, IMG_UI return PVRSRV_ERROR_INVALID_PARAMS; } - uIndex = KEY_TO_INDEX(pHash, pBucket->k, uSize); + uIndex = KEY_TO_INDEX(pHash, pBucket->k, uSize); /* PRQA S 0432,0541 */ /* ignore dynamic array warning */ pBucket->pNext = ppBucketTable[uIndex]; ppBucketTable[uIndex] = pBucket; return PVRSRV_OK; } +/*! +****************************************************************************** + @Function _Rehash + + @Description Iterate over every entry in an old hash table and + rehash into the new table. + + @Input ppOldTable - the old hash table + @Input uOldSize - the size of the old hash table + @Input ppNewTable - the new hash table + @Input uNewSize - the size of the new hash table + + @Return None +******************************************************************************/ static PVRSRV_ERROR _Rehash (HASH_TABLE *pHash, BUCKET **ppOldTable, IMG_UINT32 uOldSize, @@ -174,6 +248,20 @@ _Rehash (HASH_TABLE *pHash, return PVRSRV_OK; } +/*! +****************************************************************************** + @Function _Resize + + @Description Attempt to resize a hash table, failure to allocate a + new larger hash table is not considered a hard failure. + We simply continue and allow the table to fill up, the + effect is to allow hash chains to become longer. + + @Input pHash - Hash table to resize. + @Input uNewSize - Required table size. + @Return IMG_TRUE Success + IMG_FALSE Failed +******************************************************************************/ static IMG_BOOL _Resize (HASH_TABLE *pHash, IMG_UINT32 uNewSize) { @@ -202,7 +290,7 @@ _Resize (HASH_TABLE *pHash, IMG_UINT32 uNewSize) } OSFreeMem (PVRSRV_PAGEABLE_SELECT, sizeof(BUCKET *)*pHash->uSize, pHash->ppBucketTable, IMG_NULL); - + /*not nulling pointer, being reassigned just below*/ pHash->ppBucketTable = ppNewTable; pHash->uSize = uNewSize; } @@ -210,6 +298,23 @@ _Resize (HASH_TABLE *pHash, IMG_UINT32 uNewSize) } +/*! +****************************************************************************** + @Function HASH_Create_Extended + + @Description Create a self scaling hash table, using the supplied + key size, and the supplied 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 IMG_NULL or hash table handle. +******************************************************************************/ HASH_TABLE * HASH_Create_Extended (IMG_UINT32 uInitialLen, IMG_SIZE_T uKeySize, HASH_FUNC *pfnHashFunc, HASH_KEY_COMP *pfnKeyComp) { HASH_TABLE *pHash; @@ -240,7 +345,7 @@ HASH_TABLE * HASH_Create_Extended (IMG_UINT32 uInitialLen, IMG_SIZE_T uKeySize, if (pHash->ppBucketTable == IMG_NULL) { OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(HASH_TABLE), pHash, IMG_NULL); - + /*not nulling pointer, out of scope*/ return IMG_NULL; } @@ -249,12 +354,38 @@ HASH_TABLE * HASH_Create_Extended (IMG_UINT32 uInitialLen, IMG_SIZE_T uKeySize, return pHash; } +/*! +****************************************************************************** + @Function HASH_Create + + @Description Create a self scaling hash table with a key + consisting of a single IMG_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 IMG_NULL or hash table handle. +******************************************************************************/ HASH_TABLE * HASH_Create (IMG_UINT32 uInitialLen) { return HASH_Create_Extended(uInitialLen, sizeof(IMG_UINTPTR_T), &HASH_Func_Default, &HASH_Key_Comp_Default); } +/*! +****************************************************************************** + @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 + + @Return None +******************************************************************************/ IMG_VOID HASH_Delete (HASH_TABLE *pHash) { @@ -271,10 +402,24 @@ HASH_Delete (HASH_TABLE *pHash) OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(BUCKET *)*pHash->uSize, pHash->ppBucketTable, IMG_NULL); pHash->ppBucketTable = IMG_NULL; OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(HASH_TABLE), pHash, IMG_NULL); - + /*not nulling pointer, copy on stack*/ } } +/*! +****************************************************************************** + @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, IMG_VOID *pKey, IMG_UINTPTR_T v) { @@ -301,7 +446,7 @@ HASH_Insert_Extended (HASH_TABLE *pHash, IMG_VOID *pKey, IMG_UINTPTR_T v) } pBucket->v = v; - + /* PRQA S 0432,0541 1 */ /* ignore warning about dynamic array k (linux)*/ OSMemCopy(pBucket->k, pKey, pHash->uKeySize); if (_ChainInsert (pHash, pBucket, pHash->ppBucketTable, pHash->uSize) != PVRSRV_OK) { @@ -313,11 +458,12 @@ HASH_Insert_Extended (HASH_TABLE *pHash, IMG_VOID *pKey, IMG_UINTPTR_T v) pHash->uCount++; - + /* check if we need to think about re-balencing */ if (pHash->uCount << 1 > pHash->uSize) { - - + /* Ignore the return code from _Resize because the hash table is + still in a valid state and although not ideally sized, it is still + functional */ _Resize (pHash, pHash->uSize << 1); } @@ -325,6 +471,20 @@ HASH_Insert_Extended (HASH_TABLE *pHash, IMG_VOID *pKey, IMG_UINTPTR_T v) return IMG_TRUE; } +/*! +****************************************************************************** + @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, IMG_UINTPTR_T k, IMG_UINTPTR_T v) { @@ -335,6 +495,19 @@ HASH_Insert (HASH_TABLE *pHash, IMG_UINTPTR_T k, IMG_UINTPTR_T v) return HASH_Insert_Extended(pHash, &k, 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. +******************************************************************************/ IMG_UINTPTR_T HASH_Remove_Extended(HASH_TABLE *pHash, IMG_VOID *pKey) { @@ -356,7 +529,7 @@ HASH_Remove_Extended(HASH_TABLE *pHash, IMG_VOID *pKey) for (ppBucket = &(pHash->ppBucketTable[uIndex]); *ppBucket != IMG_NULL; ppBucket = &((*ppBucket)->pNext)) { - + /* PRQA S 0432,0541 1 */ /* ignore warning about dynamic array k */ if (KEY_COMPARE(pHash, (*ppBucket)->k, pKey)) { BUCKET *pBucket = *ppBucket; @@ -364,16 +537,17 @@ HASH_Remove_Extended(HASH_TABLE *pHash, IMG_VOID *pKey) (*ppBucket) = pBucket->pNext; OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(BUCKET) + pHash->uKeySize, pBucket, IMG_NULL); - + /*not nulling original pointer, already overwritten*/ pHash->uCount--; - + /* check if we need to think about re-balencing */ if (pHash->uSize > (pHash->uCount << 2) && pHash->uSize > pHash->uMinimumSize) { - - + /* Ignore the return code from _Resize because the + hash table is still in a valid state and although + not ideally sized, it is still functional */ _Resize (pHash, PRIVATE_MAX (pHash->uSize >> 1, pHash->uMinimumSize)); @@ -391,6 +565,19 @@ HASH_Remove_Extended(HASH_TABLE *pHash, IMG_VOID *pKey) return 0; } +/*! +****************************************************************************** + @Function HASH_Remove + + @Description Remove a key value pair from a hash table created + with HASH_Create. + + @Input pHash - the hash table + @Input k - the key + + @Return 0 if the key is missing, or the value associated + with the key. +******************************************************************************/ IMG_UINTPTR_T HASH_Remove (HASH_TABLE *pHash, IMG_UINTPTR_T k) { @@ -400,6 +587,19 @@ HASH_Remove (HASH_TABLE *pHash, IMG_UINTPTR_T k) return HASH_Remove_Extended(pHash, &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 the key. + + @Return 0 if the key is missing, or the value associated with + the key. +******************************************************************************/ IMG_UINTPTR_T HASH_Retrieve_Extended (HASH_TABLE *pHash, IMG_VOID *pKey) { @@ -421,7 +621,7 @@ HASH_Retrieve_Extended (HASH_TABLE *pHash, IMG_VOID *pKey) for (ppBucket = &(pHash->ppBucketTable[uIndex]); *ppBucket != IMG_NULL; ppBucket = &((*ppBucket)->pNext)) { - + /* PRQA S 0432,0541 1 */ /* ignore warning about dynamic array k */ if (KEY_COMPARE(pHash, (*ppBucket)->k, pKey)) { BUCKET *pBucket = *ppBucket; @@ -439,6 +639,18 @@ HASH_Retrieve_Extended (HASH_TABLE *pHash, IMG_VOID *pKey) return 0; } +/*! +****************************************************************************** + @Function HASH_Retrieve + + @Description Retrieve a value from a hash table created with + HASH_Create. + + @Input pHash - the hash table + @Input k - the key + @Return 0 if the key is missing, or the value associated with + the key. +******************************************************************************/ IMG_UINTPTR_T HASH_Retrieve (HASH_TABLE *pHash, IMG_UINTPTR_T k) { @@ -447,6 +659,17 @@ HASH_Retrieve (HASH_TABLE *pHash, IMG_UINTPTR_T k) return HASH_Retrieve_Extended(pHash, &k); } +/*! +****************************************************************************** + @Function HASH_Iterate + + @Description Iterate over every entry in the hash table + + @Input pHash - the old hash table + @Input pfnCallback - the size of the old hash table + + @Return Callback error if any, otherwise PVRSRV_OK +******************************************************************************/ PVRSRV_ERROR HASH_Iterate(HASH_TABLE *pHash, HASH_pfnCallback pfnCallback) { @@ -462,7 +685,7 @@ HASH_Iterate(HASH_TABLE *pHash, HASH_pfnCallback pfnCallback) eError = pfnCallback((IMG_UINTPTR_T) ((IMG_VOID *) *(pBucket->k)), (IMG_UINTPTR_T) pBucket->v); - + /* The callback might want us to break out early */ if (eError != PVRSRV_OK) return eError; @@ -473,6 +696,17 @@ HASH_Iterate(HASH_TABLE *pHash, HASH_pfnCallback pfnCallback) } #ifdef HASH_TRACE +/*! +****************************************************************************** + @Function HASH_Dump + + @Description To dump the contents of a hash table in human readable + form. + + @Input pHash - the hash table + + @Return None +******************************************************************************/ IMG_VOID HASH_Dump (HASH_TABLE *pHash) { |