pvr/hash.c

   1 /**********************************************************************
   2  *
   3  * Copyright(c) 2008 Imagination Technologies Ltd. All rights reserved.
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms and conditions of the GNU General Public License,
   7  * version 2, as published by the Free Software Foundation.
   8  *
   9  * This program is distributed in the hope it will be useful but, except
  10  * as otherwise stated in writing, without any warranty; without even the
  11  * implied warranty of merchantability or fitness for a particular purpose.
  12  * See the GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License along with
  15  * this program; if not, write to the Free Software Foundation, Inc.,
  16  * 51 Franklin St - Fifth Floor, Boston, MA 02110-1301 USA.
  17  *
  18  * The full GNU General Public License is included in this distribution in
  19  * the file called "COPYING".
  20  *
  21  * Contact Information:
  22  * Imagination Technologies Ltd. <gpl-support@imgtec.com>
  23  * Home Park Estate, Kings Langley, Herts, WD4 8LZ, UK
  24  *
  25  ******************************************************************************/
  26
  27 #include "pvr_debug.h"
  28 #include "img_defs.h"
  29 #include "services.h"
  30 #include "servicesint.h"
  31 #include "hash.h"
  32 #include "osfunc.h"
  33
  34 #define PRIVATE_MAX(a, b) ((a) > (b) ? (a) : (b))
  35
  36 #define KEY_TO_INDEX(pHash, key, uSize) \
  37         ((pHash)->pfnHashFunc((pHash)->uKeySize, key, uSize) % uSize)
  38
  39 #define KEY_COMPARE(pHash, pKey1, pKey2) \
  40         ((pHash)->pfnKeyComp((pHash)->uKeySize, pKey1, pKey2))
  41
  42 struct BUCKET {
  43         struct BUCKET *pNext;
  44         u32 v;
  45         u32 k[];
  46 };
  47 struct BUCKET;
  48
  49 struct HASH_TABLE {
  50         struct BUCKET **ppBucketTable;
  51         u32 uSize;
  52         u32 uCount;
  53         u32 uMinimumSize;
  54         u32 uKeySize;
  55         u32 (*pfnHashFunc)(size_t uKeySize, void *pkey, u32 uHashTabLen);
  56         IMG_BOOL (*pfnKeyComp)(size_t uKeySize, void *pKey1, void *pkey2);
  57 };
  58
  59 u32 HASH_Func_Default(size_t uKeySize, void *pKey, u32 uHashTabLen)
  60 {
  61         u32 *p = (u32 *) pKey;
  62         u32 uKeyLen = uKeySize / sizeof(u32);
  63         u32 ui;
  64         u32 uHashKey = 0;
  65
  66         PVR_UNREFERENCED_PARAMETER(uHashTabLen);
  67
  68         PVR_ASSERT((uKeySize % sizeof(u32)) == 0);
  69
  70         for (ui = 0; ui < uKeyLen; ui++) {
  71                 u32 uHashPart = (u32) *p++;
  72
  73                 uHashPart += (uHashPart << 12);
  74                 uHashPart ^= (uHashPart >> 22);
  75                 uHashPart += (uHashPart << 4);
  76                 uHashPart ^= (uHashPart >> 9);
  77                 uHashPart += (uHashPart << 10);
  78                 uHashPart ^= (uHashPart >> 2);
  79                 uHashPart += (uHashPart << 7);
  80                 uHashPart ^= (uHashPart >> 12);
  81
  82                 uHashKey += uHashPart;
  83         }
  84
  85         return uHashKey;
  86 }
  87
  88 IMG_BOOL HASH_Key_Comp_Default(size_t uKeySize, void *pKey1, void *pKey2)
  89 {
  90         u32 *p1 = (u32 *) pKey1;
  91         u32 *p2 = (u32 *) pKey2;
  92         u32 uKeyLen = uKeySize / sizeof(u32);
  93         u32 ui;
  94
  95         PVR_ASSERT((uKeySize % sizeof(u32)) == 0);
  96
  97         for (ui = 0; ui < uKeyLen; ui++)
  98                 if (*p1++ != *p2++)
  99                         return IMG_FALSE;
 100
 101         return IMG_TRUE;
 102 }
 103
 104 static enum PVRSRV_ERROR _ChainInsert(struct HASH_TABLE *pHash,
 105                                       struct BUCKET *pBucket,
 106                          struct BUCKET **ppBucketTable, u32 uSize)
 107 {
 108         u32 uIndex;
 109
 110         PVR_ASSERT(pBucket != NULL);
 111         PVR_ASSERT(ppBucketTable != NULL);
 112         PVR_ASSERT(uSize != 0);
 113
 114         if ((pBucket == NULL) || (ppBucketTable == NULL) || (uSize == 0)) {
 115                 PVR_DPF(PVR_DBG_ERROR, "_ChainInsert: invalid parameter");
 116                 return PVRSRV_ERROR_INVALID_PARAMS;
 117         }
 118
 119         uIndex = KEY_TO_INDEX(pHash, pBucket->k, uSize);
 120         pBucket->pNext = ppBucketTable[uIndex];
 121         ppBucketTable[uIndex] = pBucket;
 122
 123         return PVRSRV_OK;
 124 }
 125
 126 static enum PVRSRV_ERROR _Rehash(struct HASH_TABLE *pHash,
 127                                  struct BUCKET **ppOldTable, u32 uOldSize,
 128                                  struct BUCKET **ppNewTable, u32 uNewSize)
 129 {
 130         u32 uIndex;
 131         for (uIndex = 0; uIndex < uOldSize; uIndex++) {
 132                 struct BUCKET *pBucket;
 133                 pBucket = ppOldTable[uIndex];
 134                 while (pBucket != NULL) {
 135                         struct BUCKET *pNextBucket = pBucket->pNext;
 136                         if (_ChainInsert(pHash, pBucket, ppNewTable, uNewSize)
 137                             != PVRSRV_OK) {
 138                                 PVR_DPF(PVR_DBG_ERROR,
 139                                         "_Rehash: call to _ChainInsert failed");
 140                                 return PVRSRV_ERROR_GENERIC;
 141                         }
 142                         pBucket = pNextBucket;
 143                 }
 144         }
 145         return PVRSRV_OK;
 146 }
 147
 148 static IMG_BOOL _Resize(struct HASH_TABLE *pHash, u32 uNewSize)
 149 {
 150         if (uNewSize != pHash->uSize) {
 151                 struct BUCKET **ppNewTable;
 152                 u32 uIndex;
 153                 size_t table_size;
 154
 155                 PVR_DPF(PVR_DBG_MESSAGE,
 156                          "HASH_Resize: oldsize=0x%x  newsize=0x%x  count=0x%x",
 157                          pHash->uSize, uNewSize, pHash->uCount);
 158
 159                 table_size = sizeof(struct BUCKET *) * uNewSize;
 160                 if (OSAllocMem(PVRSRV_PAGEABLE_SELECT, table_size,
 161                            (void **) &ppNewTable, NULL) != PVRSRV_OK)
 162                         return IMG_FALSE;
 163
 164                 for (uIndex = 0; uIndex < uNewSize; uIndex++)
 165                         ppNewTable[uIndex] = NULL;
 166
 167                 if (_Rehash(pHash, pHash->ppBucketTable, pHash->uSize,
 168                             ppNewTable, uNewSize) != PVRSRV_OK) {
 169                         OSFreeMem(PVRSRV_PAGEABLE_SELECT, table_size,
 170                                   ppNewTable, NULL);
 171                         return IMG_FALSE;
 172                 }
 173
 174                 OSFreeMem(PVRSRV_PAGEABLE_SELECT,
 175                           sizeof(struct BUCKET *) * pHash->uSize,
 176                           pHash->ppBucketTable, NULL);
 177                 pHash->ppBucketTable = ppNewTable;
 178                 pHash->uSize = uNewSize;
 179         }
 180         return IMG_TRUE;
 181 }
 182
 183 struct HASH_TABLE *HASH_Create_Extended(u32 uInitialLen, size_t uKeySize,
 184                                  u32 (*pfnHashFunc)(size_t uKeySize, void *pkey,
 185                                                     u32 uHashTabLen),
 186                                  IMG_BOOL (*pfnKeyComp)(size_t uKeySize,
 187                                                         void *pKey1,
 188                                                         void *pkey2))
 189 {
 190         struct HASH_TABLE *pHash;
 191         u32 uIndex;
 192
 193         PVR_DPF(PVR_DBG_MESSAGE, "HASH_Create_Extended: InitialSize=0x%x",
 194                  uInitialLen);
 195
 196         if (OSAllocMem(PVRSRV_PAGEABLE_SELECT,
 197                        sizeof(struct HASH_TABLE),
 198                        (void **) &pHash, NULL) != PVRSRV_OK)
 199                 return NULL;
 200
 201         pHash->uCount = 0;
 202         pHash->uSize = uInitialLen;
 203         pHash->uMinimumSize = uInitialLen;
 204         pHash->uKeySize = uKeySize;
 205         pHash->pfnHashFunc = pfnHashFunc;
 206         pHash->pfnKeyComp = pfnKeyComp;
 207
 208         if (OSAllocMem(PVRSRV_PAGEABLE_SELECT,
 209                    sizeof(struct BUCKET *) * pHash->uSize,
 210                    (void **) &pHash->ppBucketTable, NULL) != PVRSRV_OK) {
 211                 OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(struct HASH_TABLE),
 212                           pHash, NULL);
 213                 return NULL;
 214         }
 215
 216         for (uIndex = 0; uIndex < pHash->uSize; uIndex++)
 217                 pHash->ppBucketTable[uIndex] = NULL;
 218         return pHash;
 219 }
 220
 221 struct HASH_TABLE *HASH_Create(u32 uInitialLen)
 222 {
 223         return HASH_Create_Extended(uInitialLen, sizeof(u32),
 224                                     &HASH_Func_Default, &HASH_Key_Comp_Default);
 225 }
 226
 227 void HASH_Delete(struct HASH_TABLE *pHash)
 228 {
 229         if (pHash != NULL) {
 230                 PVR_DPF(PVR_DBG_MESSAGE, "HASH_Delete");
 231
 232                 PVR_ASSERT(pHash->uCount == 0);
 233                 OSFreeMem(PVRSRV_PAGEABLE_SELECT,
 234                           sizeof(struct BUCKET *) * pHash->uSize,
 235                           pHash->ppBucketTable, NULL);
 236                 OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(struct HASH_TABLE),
 237                           pHash, NULL);
 238         }
 239 }
 240
 241 IMG_BOOL HASH_Insert_Extended(struct HASH_TABLE *pHash, void *pKey, u32 v)
 242 {
 243         struct BUCKET *pBucket;
 244
 245         PVR_DPF(PVR_DBG_MESSAGE,
 246                  "HASH_Insert_Extended: Hash=%08X, pKey=%08X, v=0x%x", pHash,
 247                  pKey, v);
 248
 249         PVR_ASSERT(pHash != NULL);
 250
 251         if (pHash == NULL) {
 252                 PVR_DPF(PVR_DBG_ERROR,
 253                          "HASH_Insert_Extended: invalid parameter");
 254                 return IMG_FALSE;
 255         }
 256
 257         if (OSAllocMem(PVRSRV_PAGEABLE_SELECT,
 258                        sizeof(struct BUCKET) + pHash->uKeySize,
 259                        (void **) &pBucket, NULL) != PVRSRV_OK)
 260                 return IMG_FALSE;
 261
 262         pBucket->v = v;
 263         OSMemCopy(pBucket->k, pKey, pHash->uKeySize);
 264         if (_ChainInsert(pHash, pBucket, pHash->ppBucketTable, pHash->uSize) !=
 265             PVRSRV_OK) {
 266                 OSFreeMem(PVRSRV_PAGEABLE_SELECT,
 267                           sizeof(struct BUCKET) + pHash->uKeySize,
 268                           pBucket, NULL);
 269                 return IMG_FALSE;
 270         }
 271
 272         pHash->uCount++;
 273
 274         if (pHash->uCount << 1 > pHash->uSize)
 275                 _Resize(pHash, pHash->uSize << 1);
 276
 277         return IMG_TRUE;
 278 }
 279
 280 IMG_BOOL HASH_Insert(struct HASH_TABLE *pHash, u32 k, u32 v)
 281 {
 282         PVR_DPF(PVR_DBG_MESSAGE,
 283                  "HASH_Insert: Hash=%08X, k=0x%x, v=0x%x", pHash, k, v);
 284
 285         return HASH_Insert_Extended(pHash, &k, v);
 286 }
 287
 288 u32 HASH_Remove_Extended(struct HASH_TABLE *pHash, void *pKey)
 289 {
 290         struct BUCKET **ppBucket;
 291         u32 uIndex;
 292
 293         PVR_DPF(PVR_DBG_MESSAGE, "HASH_Remove: Hash=%08X, pKey=%08X", pHash,
 294                  pKey);
 295
 296         PVR_ASSERT(pHash != NULL);
 297
 298         if (pHash == NULL) {
 299                 PVR_DPF(PVR_DBG_ERROR,
 300                          "FreeResourceByPtr: invalid parameter");
 301                 return 0;
 302         }
 303
 304         uIndex = KEY_TO_INDEX(pHash, pKey, pHash->uSize);
 305
 306         for (ppBucket = &(pHash->ppBucketTable[uIndex]); *ppBucket != NULL;
 307              ppBucket = &((*ppBucket)->pNext))
 308                 if (KEY_COMPARE(pHash, (*ppBucket)->k, pKey)) {
 309                         struct BUCKET *pBucket = *ppBucket;
 310                         u32 v = pBucket->v;
 311                         (*ppBucket) = pBucket->pNext;
 312
 313                         OSFreeMem(PVRSRV_PAGEABLE_SELECT,
 314                                   sizeof(struct BUCKET) + pHash->uKeySize,
 315                                   pBucket, NULL);
 316
 317                         pHash->uCount--;
 318
 319                         if (pHash->uSize > (pHash->uCount << 2) &&
 320                             pHash->uSize > pHash->uMinimumSize)
 321
 322                                 _Resize(pHash,
 323                                         PRIVATE_MAX(pHash->uSize >> 1,
 324                                                     pHash->uMinimumSize));
 325
 326                         PVR_DPF(PVR_DBG_MESSAGE,
 327                         "HASH_Remove_Extended: Hash=%08X, pKey=%08X = 0x%x",
 328                                  pHash, pKey, v);
 329                         return v;
 330                 }
 331         PVR_DPF(PVR_DBG_MESSAGE,
 332                  "HASH_Remove_Extended: Hash=%08X, pKey=%08X = 0x0 !!!!", pHash,
 333                  pKey);
 334         return 0;
 335 }
 336
 337 u32 HASH_Remove(struct HASH_TABLE *pHash, u32 k)
 338 {
 339         PVR_DPF(PVR_DBG_MESSAGE, "HASH_Remove: Hash=%08X, k=0x%x", pHash, k);
 340
 341         return HASH_Remove_Extended(pHash, &k);
 342 }
 343
 344 u32 HASH_Retrieve_Extended(struct HASH_TABLE *pHash, void *pKey)
 345 {
 346         struct BUCKET **ppBucket;
 347         u32 uIndex;
 348
 349         PVR_DPF(PVR_DBG_MESSAGE, "HASH_Retrieve: Hash=%08X, pKey=%08X", pHash,
 350                  pKey);
 351
 352         PVR_ASSERT(pHash != NULL);
 353
 354         if (pHash == NULL) {
 355                 PVR_DPF(PVR_DBG_ERROR,
 356                          "HASH_Retrieve_Extended: invalid parameter");
 357                 return 0;
 358         }
 359
 360         uIndex = KEY_TO_INDEX(pHash, pKey, pHash->uSize);
 361
 362         for (ppBucket = &(pHash->ppBucketTable[uIndex]); *ppBucket != NULL;
 363              ppBucket = &((*ppBucket)->pNext))
 364                 if (KEY_COMPARE(pHash, (*ppBucket)->k, pKey)) {
 365                         struct BUCKET *pBucket = *ppBucket;
 366                         u32 v = pBucket->v;
 367
 368                         PVR_DPF(PVR_DBG_MESSAGE,
 369                                  "HASH_Retrieve: Hash=%08X, pKey=%08X = 0x%x",
 370                                  pHash, pKey, v);
 371                         return v;
 372                 }
 373         PVR_DPF(PVR_DBG_MESSAGE,
 374                  "HASH_Retrieve: Hash=%08X, pKey=%08X = 0x0 !!!!", pHash, pKey);
 375         return 0;
 376 }
 377
 378 u32 HASH_Retrieve(struct HASH_TABLE *pHash, u32 k)
 379 {
 380         PVR_DPF(PVR_DBG_MESSAGE, "HASH_Retrieve: Hash=%08X, k=0x%x", pHash, k);
 381         return HASH_Retrieve_Extended(pHash, &k);
 382 }
 383