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                 size_t table_size;
 153
 154                 PVR_DPF(PVR_DBG_MESSAGE,
 155                          "HASH_Resize: oldsize=0x%x  newsize=0x%x  count=0x%x",
 156                          pHash->uSize, uNewSize, pHash->uCount);
 157
 158                 table_size = sizeof(struct BUCKET *) * uNewSize;
 159                 if (OSAllocMem(PVRSRV_PAGEABLE_SELECT, table_size,
 160                            (void **) &ppNewTable, NULL) != PVRSRV_OK)
 161                         return IMG_FALSE;
 162
 163                 memset(ppNewTable, 0, table_size);
 164
 165                 if (_Rehash(pHash, pHash->ppBucketTable, pHash->uSize,
 166                             ppNewTable, uNewSize) != PVRSRV_OK) {
 167                         OSFreeMem(PVRSRV_PAGEABLE_SELECT, table_size,
 168                                   ppNewTable, NULL);
 169                         return IMG_FALSE;
 170                 }
 171
 172                 OSFreeMem(PVRSRV_PAGEABLE_SELECT,
 173                           sizeof(struct BUCKET *) * pHash->uSize,
 174                           pHash->ppBucketTable, NULL);
 175                 pHash->ppBucketTable = ppNewTable;
 176                 pHash->uSize = uNewSize;
 177         }
 178         return IMG_TRUE;
 179 }
 180
 181 struct HASH_TABLE *HASH_Create_Extended(u32 uInitialLen, size_t uKeySize,
 182                                  u32 (*pfnHashFunc)(size_t uKeySize, void *pkey,
 183                                                     u32 uHashTabLen),
 184                                  IMG_BOOL (*pfnKeyComp)(size_t uKeySize,
 185                                                         void *pKey1,
 186                                                         void *pkey2))
 187 {
 188         struct HASH_TABLE *pHash;
 189         u32 uIndex;
 190
 191         PVR_DPF(PVR_DBG_MESSAGE, "HASH_Create_Extended: InitialSize=0x%x",
 192                  uInitialLen);
 193
 194         if (OSAllocMem(PVRSRV_PAGEABLE_SELECT,
 195                        sizeof(struct HASH_TABLE),
 196                        (void **) &pHash, NULL) != PVRSRV_OK)
 197                 return NULL;
 198
 199         pHash->uCount = 0;
 200         pHash->uSize = uInitialLen;
 201         pHash->uMinimumSize = uInitialLen;
 202         pHash->uKeySize = uKeySize;
 203         pHash->pfnHashFunc = pfnHashFunc;
 204         pHash->pfnKeyComp = pfnKeyComp;
 205
 206         if (OSAllocMem(PVRSRV_PAGEABLE_SELECT,
 207                    sizeof(struct BUCKET *) * pHash->uSize,
 208                    (void **) &pHash->ppBucketTable, NULL) != PVRSRV_OK) {
 209                 OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(struct HASH_TABLE),
 210                           pHash, NULL);
 211                 return NULL;
 212         }
 213
 214         for (uIndex = 0; uIndex < pHash->uSize; uIndex++)
 215                 pHash->ppBucketTable[uIndex] = NULL;
 216         return pHash;
 217 }
 218
 219 struct HASH_TABLE *HASH_Create(u32 uInitialLen)
 220 {
 221         return HASH_Create_Extended(uInitialLen, sizeof(u32),
 222                                     &HASH_Func_Default, &HASH_Key_Comp_Default);
 223 }
 224
 225 void HASH_Delete(struct HASH_TABLE *pHash)
 226 {
 227         if (pHash != NULL) {
 228                 PVR_DPF(PVR_DBG_MESSAGE, "HASH_Delete");
 229
 230                 PVR_ASSERT(pHash->uCount == 0);
 231                 OSFreeMem(PVRSRV_PAGEABLE_SELECT,
 232                           sizeof(struct BUCKET *) * pHash->uSize,
 233                           pHash->ppBucketTable, NULL);
 234                 OSFreeMem(PVRSRV_PAGEABLE_SELECT, sizeof(struct HASH_TABLE),
 235                           pHash, NULL);
 236         }
 237 }
 238
 239 IMG_BOOL HASH_Insert_Extended(struct HASH_TABLE *pHash, void *pKey, u32 v)
 240 {
 241         struct BUCKET *pBucket;
 242
 243         PVR_DPF(PVR_DBG_MESSAGE,
 244                  "HASH_Insert_Extended: Hash=%08X, pKey=%08X, v=0x%x", pHash,
 245                  pKey, v);
 246
 247         PVR_ASSERT(pHash != NULL);
 248
 249         if (pHash == NULL) {
 250                 PVR_DPF(PVR_DBG_ERROR,
 251                          "HASH_Insert_Extended: invalid parameter");
 252                 return IMG_FALSE;
 253         }
 254
 255         if (OSAllocMem(PVRSRV_PAGEABLE_SELECT,
 256                        sizeof(struct BUCKET) + pHash->uKeySize,
 257                        (void **) &pBucket, NULL) != PVRSRV_OK)
 258                 return IMG_FALSE;
 259
 260         pBucket->v = v;
 261         OSMemCopy(pBucket->k, pKey, pHash->uKeySize);
 262         if (_ChainInsert(pHash, pBucket, pHash->ppBucketTable, pHash->uSize) !=
 263             PVRSRV_OK) {
 264                 OSFreeMem(PVRSRV_PAGEABLE_SELECT,
 265                           sizeof(struct BUCKET) + pHash->uKeySize,
 266                           pBucket, NULL);
 267                 return IMG_FALSE;
 268         }
 269
 270         pHash->uCount++;
 271
 272         if (pHash->uCount << 1 > pHash->uSize)
 273                 _Resize(pHash, pHash->uSize << 1);
 274
 275         return IMG_TRUE;
 276 }
 277
 278 IMG_BOOL HASH_Insert(struct HASH_TABLE *pHash, u32 k, u32 v)
 279 {
 280         PVR_DPF(PVR_DBG_MESSAGE,
 281                  "HASH_Insert: Hash=%08X, k=0x%x, v=0x%x", pHash, k, v);
 282
 283         return HASH_Insert_Extended(pHash, &k, v);
 284 }
 285
 286 u32 HASH_Remove_Extended(struct HASH_TABLE *pHash, void *pKey)
 287 {
 288         struct BUCKET **ppBucket;
 289         u32 uIndex;
 290
 291         PVR_DPF(PVR_DBG_MESSAGE, "HASH_Remove: Hash=%08X, pKey=%08X", pHash,
 292                  pKey);
 293
 294         PVR_ASSERT(pHash != NULL);
 295
 296         if (pHash == NULL) {
 297                 PVR_DPF(PVR_DBG_ERROR,
 298                          "FreeResourceByPtr: invalid parameter");
 299                 return 0;
 300         }
 301
 302         uIndex = KEY_TO_INDEX(pHash, pKey, pHash->uSize);
 303
 304         for (ppBucket = &(pHash->ppBucketTable[uIndex]); *ppBucket != NULL;
 305              ppBucket = &((*ppBucket)->pNext))
 306                 if (KEY_COMPARE(pHash, (*ppBucket)->k, pKey)) {
 307                         struct BUCKET *pBucket = *ppBucket;
 308                         u32 v = pBucket->v;
 309                         (*ppBucket) = pBucket->pNext;
 310
 311                         OSFreeMem(PVRSRV_PAGEABLE_SELECT,
 312                                   sizeof(struct BUCKET) + pHash->uKeySize,
 313                                   pBucket, NULL);
 314
 315                         pHash->uCount--;
 316
 317                         if (pHash->uSize > (pHash->uCount << 2) &&
 318                             pHash->uSize > pHash->uMinimumSize)
 319
 320                                 _Resize(pHash,
 321                                         PRIVATE_MAX(pHash->uSize >> 1,
 322                                                     pHash->uMinimumSize));
 323
 324                         PVR_DPF(PVR_DBG_MESSAGE,
 325                         "HASH_Remove_Extended: Hash=%08X, pKey=%08X = 0x%x",
 326                                  pHash, pKey, v);
 327                         return v;
 328                 }
 329         PVR_DPF(PVR_DBG_MESSAGE,
 330                  "HASH_Remove_Extended: Hash=%08X, pKey=%08X = 0x0 !!!!", pHash,
 331                  pKey);
 332         return 0;
 333 }
 334
 335 u32 HASH_Remove(struct HASH_TABLE *pHash, u32 k)
 336 {
 337         PVR_DPF(PVR_DBG_MESSAGE, "HASH_Remove: Hash=%08X, k=0x%x", pHash, k);
 338
 339         return HASH_Remove_Extended(pHash, &k);
 340 }
 341
 342 u32 HASH_Retrieve_Extended(struct HASH_TABLE *pHash, void *pKey)
 343 {
 344         struct BUCKET **ppBucket;
 345         u32 uIndex;
 346
 347         PVR_DPF(PVR_DBG_MESSAGE, "HASH_Retrieve: Hash=%08X, pKey=%08X", pHash,
 348                  pKey);
 349
 350         PVR_ASSERT(pHash != NULL);
 351
 352         if (pHash == NULL) {
 353                 PVR_DPF(PVR_DBG_ERROR,
 354                          "HASH_Retrieve_Extended: invalid parameter");
 355                 return 0;
 356         }
 357
 358         uIndex = KEY_TO_INDEX(pHash, pKey, pHash->uSize);
 359
 360         for (ppBucket = &(pHash->ppBucketTable[uIndex]); *ppBucket != NULL;
 361              ppBucket = &((*ppBucket)->pNext))
 362                 if (KEY_COMPARE(pHash, (*ppBucket)->k, pKey)) {
 363                         struct BUCKET *pBucket = *ppBucket;
 364                         u32 v = pBucket->v;
 365
 366                         PVR_DPF(PVR_DBG_MESSAGE,
 367                                  "HASH_Retrieve: Hash=%08X, pKey=%08X = 0x%x",
 368                                  pHash, pKey, v);
 369                         return v;
 370                 }
 371         PVR_DPF(PVR_DBG_MESSAGE,
 372                  "HASH_Retrieve: Hash=%08X, pKey=%08X = 0x0 !!!!", pHash, pKey);
 373         return 0;
 374 }
 375
 376 u32 HASH_Retrieve(struct HASH_TABLE *pHash, u32 k)
 377 {
 378         PVR_DPF(PVR_DBG_MESSAGE, "HASH_Retrieve: Hash=%08X, k=0x%x", pHash, k);
 379         return HASH_Retrieve_Extended(pHash, &k);
 380 }
 381