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