pkix_pl_hashtable.c (10883B)
1 /* This Source Code Form is subject to the terms of the Mozilla Public 2 * License, v. 2.0. If a copy of the MPL was not distributed with this 3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 4 /* 5 * pkix_pl_hashtable.c 6 * 7 * Hashtable Object Functions 8 * 9 */ 10 11 #include "pkix_pl_hashtable.h" 12 13 /* --Private-Structure-------------------------------------------- */ 14 15 struct PKIX_PL_HashTableStruct { 16 pkix_pl_PrimHashTable *primHash; 17 PKIX_PL_Mutex *tableLock; 18 PKIX_UInt32 maxEntriesPerBucket; 19 }; 20 21 /* --Private-Functions-------------------------------------------- */ 22 23 #define PKIX_MUTEX_UNLOCK(mutex) \ 24 do { \ 25 if (mutex && lockedMutex == (PKIX_PL_Mutex *)(mutex)) { \ 26 pkixTempResult = \ 27 PKIX_PL_Mutex_Unlock((mutex), plContext); \ 28 PORT_Assert(pkixTempResult == NULL); \ 29 if (pkixTempResult) { \ 30 PKIX_DoAddError(&stdVars, pkixTempResult, plContext); \ 31 pkixTempResult = NULL; \ 32 } \ 33 lockedMutex = NULL; \ 34 } else { \ 35 PORT_Assert(lockedMutex == NULL); \ 36 }\ 37 } while (0) 38 39 40 #define PKIX_MUTEX_LOCK(mutex) \ 41 do { \ 42 if (mutex){ \ 43 PORT_Assert(lockedMutex == NULL); \ 44 PKIX_CHECK(PKIX_PL_Mutex_Lock((mutex), plContext), \ 45 PKIX_MUTEXLOCKFAILED); \ 46 lockedMutex = (mutex); \ 47 } \ 48 } while (0) 49 50 /* 51 * FUNCTION: pkix_pl_HashTable_Destroy 52 * (see comments for PKIX_PL_DestructorCallback in pkix_pl_system.h) 53 */ 54 static PKIX_Error * 55 pkix_pl_HashTable_Destroy( 56 PKIX_PL_Object *object, 57 void *plContext) 58 { 59 PKIX_PL_HashTable *ht = NULL; 60 pkix_pl_HT_Elem *item = NULL; 61 PKIX_UInt32 i; 62 63 PKIX_ENTER(HASHTABLE, "pkix_pl_HashTable_Destroy"); 64 PKIX_NULLCHECK_ONE(object); 65 66 PKIX_CHECK(pkix_CheckType(object, PKIX_HASHTABLE_TYPE, plContext), 67 PKIX_OBJECTNOTHASHTABLE); 68 69 ht = (PKIX_PL_HashTable*) object; 70 71 /* DecRef every object in the primitive hash table */ 72 for (i = 0; i < ht->primHash->size; i++) { 73 for (item = ht->primHash->buckets[i]; 74 item != NULL; 75 item = item->next) { 76 PKIX_DECREF(item->key); 77 PKIX_DECREF(item->value); 78 } 79 } 80 81 PKIX_CHECK(pkix_pl_PrimHashTable_Destroy(ht->primHash, plContext), 82 PKIX_PRIMHASHTABLEDESTROYFAILED); 83 84 PKIX_DECREF(ht->tableLock); 85 86 cleanup: 87 88 PKIX_RETURN(HASHTABLE); 89 } 90 91 /* 92 * FUNCTION: pkix_pl_HashTable_RegisterSelf 93 * DESCRIPTION: 94 * Registers PKIX_HASHTABLE_TYPE and its related functions with systemClasses[] 95 * THREAD SAFETY: 96 * Not Thread Safe - for performance and complexity reasons 97 * 98 * Since this function is only called by PKIX_PL_Initialize, which should 99 * only be called once, it is acceptable that this function is not 100 * thread-safe. 101 */ 102 PKIX_Error * 103 pkix_pl_HashTable_RegisterSelf( 104 void *plContext) 105 { 106 107 extern pkix_ClassTable_Entry systemClasses[PKIX_NUMTYPES]; 108 pkix_ClassTable_Entry entry; 109 110 PKIX_ENTER(HASHTABLE, "pkix_pl_HashTable_RegisterSelf"); 111 112 entry.description = "HashTable"; 113 entry.objCounter = 0; 114 entry.typeObjectSize = sizeof(PKIX_PL_HashTable); 115 entry.destructor = pkix_pl_HashTable_Destroy; 116 entry.equalsFunction = NULL; 117 entry.hashcodeFunction = NULL; 118 entry.toStringFunction = NULL; 119 entry.comparator = NULL; 120 entry.duplicateFunction = NULL; 121 122 systemClasses[PKIX_HASHTABLE_TYPE] = entry; 123 124 PKIX_RETURN(HASHTABLE); 125 } 126 127 /* --Public-Functions------------------------------------------------------- */ 128 129 /* 130 * FUNCTION: PKIX_PL_HashTable_Create (see comments in pkix_pl_system.h) 131 */ 132 PKIX_Error * 133 PKIX_PL_HashTable_Create( 134 PKIX_UInt32 numBuckets, 135 PKIX_UInt32 maxEntriesPerBucket, 136 PKIX_PL_HashTable **pResult, 137 void *plContext) 138 { 139 PKIX_PL_HashTable *hashTable = NULL; 140 141 PKIX_ENTER(HASHTABLE, "PKIX_PL_HashTable_Create"); 142 PKIX_NULLCHECK_ONE(pResult); 143 144 if (numBuckets == 0) { 145 PKIX_ERROR(PKIX_NUMBUCKETSEQUALSZERO); 146 } 147 148 /* Allocate a new hashtable */ 149 PKIX_CHECK(PKIX_PL_Object_Alloc 150 (PKIX_HASHTABLE_TYPE, 151 sizeof (PKIX_PL_HashTable), 152 (PKIX_PL_Object **)&hashTable, 153 plContext), 154 PKIX_COULDNOTCREATEHASHTABLEOBJECT); 155 156 /* Create the underlying primitive hash table type */ 157 PKIX_CHECK(pkix_pl_PrimHashTable_Create 158 (numBuckets, &hashTable->primHash, plContext), 159 PKIX_PRIMHASHTABLECREATEFAILED); 160 161 /* Create a lock for this table */ 162 PKIX_CHECK(PKIX_PL_Mutex_Create(&hashTable->tableLock, plContext), 163 PKIX_ERRORCREATINGTABLELOCK); 164 165 hashTable->maxEntriesPerBucket = maxEntriesPerBucket; 166 167 *pResult = hashTable; 168 169 cleanup: 170 171 if (PKIX_ERROR_RECEIVED){ 172 PKIX_DECREF(hashTable); 173 } 174 175 PKIX_RETURN(HASHTABLE); 176 } 177 178 /* 179 * FUNCTION: PKIX_PL_HashTable_Add (see comments in pkix_pl_system.h) 180 */ 181 PKIX_Error * 182 PKIX_PL_HashTable_Add( 183 PKIX_PL_HashTable *ht, 184 PKIX_PL_Object *key, 185 PKIX_PL_Object *value, 186 void *plContext) 187 { 188 PKIX_PL_Mutex *lockedMutex = NULL; 189 PKIX_PL_Object *deletedKey = NULL; 190 PKIX_PL_Object *deletedValue = NULL; 191 PKIX_UInt32 hashCode; 192 PKIX_PL_EqualsCallback keyComp; 193 PKIX_UInt32 bucketSize = 0; 194 195 PKIX_ENTER(HASHTABLE, "PKIX_PL_HashTable_Add"); 196 197 #if !defined(PKIX_OBJECT_LEAK_TEST) 198 PKIX_NULLCHECK_THREE(ht, key, value); 199 #else 200 PKIX_NULLCHECK_TWO(key, value); 201 202 if (ht == NULL) { 203 PKIX_RETURN(HASHTABLE); 204 } 205 #endif 206 /* Insert into primitive hashtable */ 207 208 PKIX_CHECK(PKIX_PL_Object_Hashcode(key, &hashCode, plContext), 209 PKIX_OBJECTHASHCODEFAILED); 210 211 PKIX_CHECK(pkix_pl_Object_RetrieveEqualsCallback 212 (key, &keyComp, plContext), 213 PKIX_OBJECTRETRIEVEEQUALSCALLBACKFAILED); 214 215 PKIX_MUTEX_LOCK(ht->tableLock); 216 217 PKIX_CHECK(pkix_pl_PrimHashTable_GetBucketSize 218 (ht->primHash, 219 hashCode, 220 &bucketSize, 221 plContext), 222 PKIX_PRIMHASHTABLEGETBUCKETSIZEFAILED); 223 224 if (ht->maxEntriesPerBucket != 0 && 225 bucketSize >= ht->maxEntriesPerBucket) { 226 /* drop the last one in the bucket */ 227 PKIX_CHECK(pkix_pl_PrimHashTable_RemoveFIFO 228 (ht->primHash, 229 hashCode, 230 (void **) &deletedKey, 231 (void **) &deletedValue, 232 plContext), 233 PKIX_PRIMHASHTABLEGETBUCKETSIZEFAILED); 234 PKIX_DECREF(deletedKey); 235 PKIX_DECREF(deletedValue); 236 } 237 238 PKIX_CHECK(pkix_pl_PrimHashTable_Add 239 (ht->primHash, 240 (void *)key, 241 (void *)value, 242 hashCode, 243 keyComp, 244 plContext), 245 PKIX_PRIMHASHTABLEADDFAILED); 246 247 PKIX_INCREF(key); 248 PKIX_INCREF(value); 249 PKIX_MUTEX_UNLOCK(ht->tableLock); 250 251 /* 252 * we don't call PKIX_PL_InvalidateCache here b/c we have 253 * not implemented toString or hashcode for this Object 254 */ 255 256 cleanup: 257 258 PKIX_MUTEX_UNLOCK(ht->tableLock); 259 260 PKIX_RETURN(HASHTABLE); 261 } 262 263 /* 264 * FUNCTION: PKIX_PL_HashTable_Remove (see comments in pkix_pl_system.h) 265 */ 266 PKIX_Error * 267 PKIX_PL_HashTable_Remove( 268 PKIX_PL_HashTable *ht, 269 PKIX_PL_Object *key, 270 void *plContext) 271 { 272 PKIX_PL_Mutex *lockedMutex = NULL; 273 PKIX_PL_Object *origKey = NULL; 274 PKIX_PL_Object *value = NULL; 275 PKIX_UInt32 hashCode; 276 PKIX_PL_EqualsCallback keyComp; 277 278 PKIX_ENTER(HASHTABLE, "PKIX_PL_HashTable_Remove"); 279 280 #if !defined(PKIX_OBJECT_LEAK_TEST) 281 PKIX_NULLCHECK_TWO(ht, key); 282 #else 283 PKIX_NULLCHECK_ONE(key); 284 285 if (ht == NULL) { 286 PKIX_RETURN(HASHTABLE); 287 } 288 #endif 289 290 PKIX_CHECK(PKIX_PL_Object_Hashcode(key, &hashCode, plContext), 291 PKIX_OBJECTHASHCODEFAILED); 292 293 PKIX_CHECK(pkix_pl_Object_RetrieveEqualsCallback 294 (key, &keyComp, plContext), 295 PKIX_OBJECTRETRIEVEEQUALSCALLBACKFAILED); 296 297 PKIX_MUTEX_LOCK(ht->tableLock); 298 299 /* Remove from primitive hashtable */ 300 PKIX_CHECK(pkix_pl_PrimHashTable_Remove 301 (ht->primHash, 302 (void *)key, 303 hashCode, 304 keyComp, 305 (void **)&origKey, 306 (void **)&value, 307 plContext), 308 PKIX_PRIMHASHTABLEREMOVEFAILED); 309 310 PKIX_MUTEX_UNLOCK(ht->tableLock); 311 312 PKIX_DECREF(origKey); 313 PKIX_DECREF(value); 314 315 /* 316 * we don't call PKIX_PL_InvalidateCache here b/c we have 317 * not implemented toString or hashcode for this Object 318 */ 319 320 cleanup: 321 322 PKIX_MUTEX_UNLOCK(ht->tableLock); 323 324 PKIX_RETURN(HASHTABLE); 325 } 326 327 /* 328 * FUNCTION: PKIX_PL_HashTable_Lookup (see comments in pkix_pl_system.h) 329 */ 330 PKIX_Error * 331 PKIX_PL_HashTable_Lookup( 332 PKIX_PL_HashTable *ht, 333 PKIX_PL_Object *key, 334 PKIX_PL_Object **pResult, 335 void *plContext) 336 { 337 PKIX_PL_Mutex *lockedMutex = NULL; 338 PKIX_UInt32 hashCode; 339 PKIX_PL_EqualsCallback keyComp; 340 PKIX_PL_Object *result = NULL; 341 342 PKIX_ENTER(HASHTABLE, "PKIX_PL_HashTable_Lookup"); 343 344 #if !defined(PKIX_OBJECT_LEAK_TEST) 345 PKIX_NULLCHECK_THREE(ht, key, pResult); 346 #else 347 PKIX_NULLCHECK_TWO(key, pResult); 348 349 if (ht == NULL) { 350 PKIX_RETURN(HASHTABLE); 351 } 352 #endif 353 354 PKIX_CHECK(PKIX_PL_Object_Hashcode(key, &hashCode, plContext), 355 PKIX_OBJECTHASHCODEFAILED); 356 357 PKIX_CHECK(pkix_pl_Object_RetrieveEqualsCallback 358 (key, &keyComp, plContext), 359 PKIX_OBJECTRETRIEVEEQUALSCALLBACKFAILED); 360 361 PKIX_MUTEX_LOCK(ht->tableLock); 362 363 /* Lookup in primitive hashtable */ 364 PKIX_CHECK(pkix_pl_PrimHashTable_Lookup 365 (ht->primHash, 366 (void *)key, 367 hashCode, 368 keyComp, 369 (void **)&result, 370 plContext), 371 PKIX_PRIMHASHTABLELOOKUPFAILED); 372 373 PKIX_INCREF(result); 374 PKIX_MUTEX_UNLOCK(ht->tableLock); 375 376 *pResult = result; 377 378 cleanup: 379 380 PKIX_MUTEX_UNLOCK(ht->tableLock); 381 382 PKIX_RETURN(HASHTABLE); 383 }