diff options
Diffstat (limited to 'security/nss/lib/base/hash.c')
| -rw-r--r-- | security/nss/lib/base/hash.c | 314 |
1 files changed, 314 insertions, 0 deletions
diff --git a/security/nss/lib/base/hash.c b/security/nss/lib/base/hash.c new file mode 100644 index 000000000..f9ee75803 --- /dev/null +++ b/security/nss/lib/base/hash.c @@ -0,0 +1,314 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +/* + * hash.c + * + * This is merely a couple wrappers around NSPR's PLHashTable, using + * the identity hash and arena-aware allocators. + * This is a copy of ckfw/hash.c, with modifications to use NSS types + * (not Cryptoki types). Would like for this to be a single implementation, + * but doesn't seem like it will work. + */ + +#ifndef BASE_H +#include "base.h" +#endif /* BASE_H */ + +#include "prbit.h" + +/* + * nssHash + * + * nssHash_Create + * nssHash_Destroy + * nssHash_Add + * nssHash_Remove + * nssHash_Count + * nssHash_Exists + * nssHash_Lookup + * nssHash_Iterate + */ + +struct nssHashStr { + NSSArena *arena; + PRBool i_alloced_arena; + PRLock *mutex; + + /* + * The invariant that mutex protects is: + * The count accurately reflects the hashtable state. + */ + + PLHashTable *plHashTable; + PRUint32 count; +}; + +static PLHashNumber +nss_identity_hash(const void *key) +{ + return (PLHashNumber)((char *)key - (char *)NULL); +} + +static PLHashNumber +nss_item_hash(const void *key) +{ + unsigned int i; + PLHashNumber h; + NSSItem *it = (NSSItem *)key; + h = 0; + for (i = 0; i < it->size; i++) + h = PR_ROTATE_LEFT32(h, 4) ^ ((unsigned char *)it->data)[i]; + return h; +} + +static int +nss_compare_items(const void *v1, const void *v2) +{ + PRStatus ignore; + return (int)nssItem_Equal((NSSItem *)v1, (NSSItem *)v2, &ignore); +} + +/* + * nssHash_create + * + */ +NSS_IMPLEMENT nssHash * +nssHash_Create(NSSArena *arenaOpt, PRUint32 numBuckets, PLHashFunction keyHash, + PLHashComparator keyCompare, PLHashComparator valueCompare) +{ + nssHash *rv; + NSSArena *arena; + PRBool i_alloced; + +#ifdef NSSDEBUG + if (arenaOpt && PR_SUCCESS != nssArena_verifyPointer(arenaOpt)) { + nss_SetError(NSS_ERROR_INVALID_POINTER); + return (nssHash *)NULL; + } +#endif /* NSSDEBUG */ + + if (arenaOpt) { + arena = arenaOpt; + i_alloced = PR_FALSE; + } else { + arena = nssArena_Create(); + i_alloced = PR_TRUE; + } + + rv = nss_ZNEW(arena, nssHash); + if ((nssHash *)NULL == rv) { + goto loser; + } + + rv->mutex = PZ_NewLock(nssILockOther); + if ((PZLock *)NULL == rv->mutex) { + goto loser; + } + + rv->plHashTable = + PL_NewHashTable(numBuckets, keyHash, keyCompare, valueCompare, + &nssArenaHashAllocOps, arena); + if ((PLHashTable *)NULL == rv->plHashTable) { + (void)PZ_DestroyLock(rv->mutex); + goto loser; + } + + rv->count = 0; + rv->arena = arena; + rv->i_alloced_arena = i_alloced; + + return rv; +loser: + (void)nss_ZFreeIf(rv); + return (nssHash *)NULL; +} + +/* + * nssHash_CreatePointer + * + */ +NSS_IMPLEMENT nssHash * +nssHash_CreatePointer(NSSArena *arenaOpt, PRUint32 numBuckets) +{ + return nssHash_Create(arenaOpt, numBuckets, nss_identity_hash, + PL_CompareValues, PL_CompareValues); +} + +/* + * nssHash_CreateString + * + */ +NSS_IMPLEMENT nssHash * +nssHash_CreateString(NSSArena *arenaOpt, PRUint32 numBuckets) +{ + return nssHash_Create(arenaOpt, numBuckets, PL_HashString, + PL_CompareStrings, PL_CompareStrings); +} + +/* + * nssHash_CreateItem + * + */ +NSS_IMPLEMENT nssHash * +nssHash_CreateItem(NSSArena *arenaOpt, PRUint32 numBuckets) +{ + return nssHash_Create(arenaOpt, numBuckets, nss_item_hash, + nss_compare_items, PL_CompareValues); +} + +/* + * nssHash_Destroy + * + */ +NSS_IMPLEMENT void +nssHash_Destroy(nssHash *hash) +{ + (void)PZ_DestroyLock(hash->mutex); + PL_HashTableDestroy(hash->plHashTable); + if (hash->i_alloced_arena) { + nssArena_Destroy(hash->arena); + } else { + nss_ZFreeIf(hash); + } +} + +/* + * nssHash_Add + * + */ +NSS_IMPLEMENT PRStatus +nssHash_Add(nssHash *hash, const void *key, const void *value) +{ + PRStatus error = PR_FAILURE; + PLHashEntry *he; + + PZ_Lock(hash->mutex); + + he = PL_HashTableAdd(hash->plHashTable, key, (void *)value); + if ((PLHashEntry *)NULL == he) { + nss_SetError(NSS_ERROR_NO_MEMORY); + } else if (he->value != value) { + nss_SetError(NSS_ERROR_HASH_COLLISION); + } else { + hash->count++; + error = PR_SUCCESS; + } + + (void)PZ_Unlock(hash->mutex); + + return error; +} + +/* + * nssHash_Remove + * + */ +NSS_IMPLEMENT void +nssHash_Remove(nssHash *hash, const void *it) +{ + PRBool found; + + PZ_Lock(hash->mutex); + + found = PL_HashTableRemove(hash->plHashTable, it); + if (found) { + hash->count--; + } + + (void)PZ_Unlock(hash->mutex); + return; +} + +/* + * nssHash_Count + * + */ +NSS_IMPLEMENT PRUint32 +nssHash_Count(nssHash *hash) +{ + PRUint32 count; + + PZ_Lock(hash->mutex); + + count = hash->count; + + (void)PZ_Unlock(hash->mutex); + + return count; +} + +/* + * nssHash_Exists + * + */ +NSS_IMPLEMENT PRBool +nssHash_Exists(nssHash *hash, const void *it) +{ + void *value; + + PZ_Lock(hash->mutex); + + value = PL_HashTableLookup(hash->plHashTable, it); + + (void)PZ_Unlock(hash->mutex); + + if ((void *)NULL == value) { + return PR_FALSE; + } else { + return PR_TRUE; + } +} + +/* + * nssHash_Lookup + * + */ +NSS_IMPLEMENT void * +nssHash_Lookup(nssHash *hash, const void *it) +{ + void *rv; + + PZ_Lock(hash->mutex); + + rv = PL_HashTableLookup(hash->plHashTable, it); + + (void)PZ_Unlock(hash->mutex); + + return rv; +} + +struct arg_str { + nssHashIterator fcn; + void *closure; +}; + +static PRIntn +nss_hash_enumerator(PLHashEntry *he, PRIntn index, void *arg) +{ + struct arg_str *as = (struct arg_str *)arg; + as->fcn(he->key, he->value, as->closure); + return HT_ENUMERATE_NEXT; +} + +/* + * nssHash_Iterate + * + * NOTE that the iteration function will be called with the hashtable locked. + */ +NSS_IMPLEMENT void +nssHash_Iterate(nssHash *hash, nssHashIterator fcn, void *closure) +{ + struct arg_str as; + as.fcn = fcn; + as.closure = closure; + + PZ_Lock(hash->mutex); + + PL_HashTableEnumerateEntries(hash->plHashTable, nss_hash_enumerator, &as); + + (void)PZ_Unlock(hash->mutex); + + return; +} |