1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/base/hash.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,373 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +/*
1.9 + * hash.c
1.10 + *
1.11 + * This is merely a couple wrappers around NSPR's PLHashTable, using
1.12 + * the identity hash and arena-aware allocators.
1.13 + * This is a copy of ckfw/hash.c, with modifications to use NSS types
1.14 + * (not Cryptoki types). Would like for this to be a single implementation,
1.15 + * but doesn't seem like it will work.
1.16 + */
1.17 +
1.18 +#ifndef BASE_H
1.19 +#include "base.h"
1.20 +#endif /* BASE_H */
1.21 +
1.22 +#include "prbit.h"
1.23 +
1.24 +/*
1.25 + * nssHash
1.26 + *
1.27 + * nssHash_Create
1.28 + * nssHash_Destroy
1.29 + * nssHash_Add
1.30 + * nssHash_Remove
1.31 + * nssHash_Count
1.32 + * nssHash_Exists
1.33 + * nssHash_Lookup
1.34 + * nssHash_Iterate
1.35 + */
1.36 +
1.37 +struct nssHashStr {
1.38 + NSSArena *arena;
1.39 + PRBool i_alloced_arena;
1.40 + PRLock *mutex;
1.41 +
1.42 + /*
1.43 + * The invariant that mutex protects is:
1.44 + * The count accurately reflects the hashtable state.
1.45 + */
1.46 +
1.47 + PLHashTable *plHashTable;
1.48 + PRUint32 count;
1.49 +};
1.50 +
1.51 +static PLHashNumber
1.52 +nss_identity_hash
1.53 +(
1.54 + const void *key
1.55 +)
1.56 +{
1.57 + PRUint32 i = (PRUint32)key;
1.58 + PR_ASSERT(sizeof(PLHashNumber) == sizeof(PRUint32));
1.59 + return (PLHashNumber)i;
1.60 +}
1.61 +
1.62 +static PLHashNumber
1.63 +nss_item_hash
1.64 +(
1.65 + const void *key
1.66 +)
1.67 +{
1.68 + unsigned int i;
1.69 + PLHashNumber h;
1.70 + NSSItem *it = (NSSItem *)key;
1.71 + h = 0;
1.72 + for (i=0; i<it->size; i++)
1.73 + h = PR_ROTATE_LEFT32(h, 4) ^ ((unsigned char *)it->data)[i];
1.74 + return h;
1.75 +}
1.76 +
1.77 +static int
1.78 +nss_compare_items(const void *v1, const void *v2)
1.79 +{
1.80 + PRStatus ignore;
1.81 + return (int)nssItem_Equal((NSSItem *)v1, (NSSItem *)v2, &ignore);
1.82 +}
1.83 +
1.84 +/*
1.85 + * nssHash_create
1.86 + *
1.87 + */
1.88 +NSS_IMPLEMENT nssHash *
1.89 +nssHash_Create
1.90 +(
1.91 + NSSArena *arenaOpt,
1.92 + PRUint32 numBuckets,
1.93 + PLHashFunction keyHash,
1.94 + PLHashComparator keyCompare,
1.95 + PLHashComparator valueCompare
1.96 +)
1.97 +{
1.98 + nssHash *rv;
1.99 + NSSArena *arena;
1.100 + PRBool i_alloced;
1.101 +
1.102 +#ifdef NSSDEBUG
1.103 + if( arenaOpt && PR_SUCCESS != nssArena_verifyPointer(arenaOpt) ) {
1.104 + nss_SetError(NSS_ERROR_INVALID_POINTER);
1.105 + return (nssHash *)NULL;
1.106 + }
1.107 +#endif /* NSSDEBUG */
1.108 +
1.109 + if (arenaOpt) {
1.110 + arena = arenaOpt;
1.111 + i_alloced = PR_FALSE;
1.112 + } else {
1.113 + arena = nssArena_Create();
1.114 + i_alloced = PR_TRUE;
1.115 + }
1.116 +
1.117 + rv = nss_ZNEW(arena, nssHash);
1.118 + if( (nssHash *)NULL == rv ) {
1.119 + goto loser;
1.120 + }
1.121 +
1.122 + rv->mutex = PZ_NewLock(nssILockOther);
1.123 + if( (PZLock *)NULL == rv->mutex ) {
1.124 + goto loser;
1.125 + }
1.126 +
1.127 + rv->plHashTable = PL_NewHashTable(numBuckets,
1.128 + keyHash, keyCompare, valueCompare,
1.129 + &nssArenaHashAllocOps, arena);
1.130 + if( (PLHashTable *)NULL == rv->plHashTable ) {
1.131 + (void)PZ_DestroyLock(rv->mutex);
1.132 + goto loser;
1.133 + }
1.134 +
1.135 + rv->count = 0;
1.136 + rv->arena = arena;
1.137 + rv->i_alloced_arena = i_alloced;
1.138 +
1.139 + return rv;
1.140 +loser:
1.141 + (void)nss_ZFreeIf(rv);
1.142 + return (nssHash *)NULL;
1.143 +}
1.144 +
1.145 +/*
1.146 + * nssHash_CreatePointer
1.147 + *
1.148 + */
1.149 +NSS_IMPLEMENT nssHash *
1.150 +nssHash_CreatePointer
1.151 +(
1.152 + NSSArena *arenaOpt,
1.153 + PRUint32 numBuckets
1.154 +)
1.155 +{
1.156 + return nssHash_Create(arenaOpt, numBuckets,
1.157 + nss_identity_hash, PL_CompareValues, PL_CompareValues);
1.158 +}
1.159 +
1.160 +/*
1.161 + * nssHash_CreateString
1.162 + *
1.163 + */
1.164 +NSS_IMPLEMENT nssHash *
1.165 +nssHash_CreateString
1.166 +(
1.167 + NSSArena *arenaOpt,
1.168 + PRUint32 numBuckets
1.169 +)
1.170 +{
1.171 + return nssHash_Create(arenaOpt, numBuckets,
1.172 + PL_HashString, PL_CompareStrings, PL_CompareStrings);
1.173 +}
1.174 +
1.175 +/*
1.176 + * nssHash_CreateItem
1.177 + *
1.178 + */
1.179 +NSS_IMPLEMENT nssHash *
1.180 +nssHash_CreateItem
1.181 +(
1.182 + NSSArena *arenaOpt,
1.183 + PRUint32 numBuckets
1.184 +)
1.185 +{
1.186 + return nssHash_Create(arenaOpt, numBuckets,
1.187 + nss_item_hash, nss_compare_items, PL_CompareValues);
1.188 +}
1.189 +
1.190 +/*
1.191 + * nssHash_Destroy
1.192 + *
1.193 + */
1.194 +NSS_IMPLEMENT void
1.195 +nssHash_Destroy
1.196 +(
1.197 + nssHash *hash
1.198 +)
1.199 +{
1.200 + (void)PZ_DestroyLock(hash->mutex);
1.201 + PL_HashTableDestroy(hash->plHashTable);
1.202 + if (hash->i_alloced_arena) {
1.203 + nssArena_Destroy(hash->arena);
1.204 + } else {
1.205 + nss_ZFreeIf(hash);
1.206 + }
1.207 +}
1.208 +
1.209 +/*
1.210 + * nssHash_Add
1.211 + *
1.212 + */
1.213 +NSS_IMPLEMENT PRStatus
1.214 +nssHash_Add
1.215 +(
1.216 + nssHash *hash,
1.217 + const void *key,
1.218 + const void *value
1.219 +)
1.220 +{
1.221 + PRStatus error = PR_FAILURE;
1.222 + PLHashEntry *he;
1.223 +
1.224 + PZ_Lock(hash->mutex);
1.225 +
1.226 + he = PL_HashTableAdd(hash->plHashTable, key, (void *)value);
1.227 + if( (PLHashEntry *)NULL == he ) {
1.228 + nss_SetError(NSS_ERROR_NO_MEMORY);
1.229 + } else if (he->value != value) {
1.230 + nss_SetError(NSS_ERROR_HASH_COLLISION);
1.231 + } else {
1.232 + hash->count++;
1.233 + error = PR_SUCCESS;
1.234 + }
1.235 +
1.236 + (void)PZ_Unlock(hash->mutex);
1.237 +
1.238 + return error;
1.239 +}
1.240 +
1.241 +/*
1.242 + * nssHash_Remove
1.243 + *
1.244 + */
1.245 +NSS_IMPLEMENT void
1.246 +nssHash_Remove
1.247 +(
1.248 + nssHash *hash,
1.249 + const void *it
1.250 +)
1.251 +{
1.252 + PRBool found;
1.253 +
1.254 + PZ_Lock(hash->mutex);
1.255 +
1.256 + found = PL_HashTableRemove(hash->plHashTable, it);
1.257 + if( found ) {
1.258 + hash->count--;
1.259 + }
1.260 +
1.261 + (void)PZ_Unlock(hash->mutex);
1.262 + return;
1.263 +}
1.264 +
1.265 +/*
1.266 + * nssHash_Count
1.267 + *
1.268 + */
1.269 +NSS_IMPLEMENT PRUint32
1.270 +nssHash_Count
1.271 +(
1.272 + nssHash *hash
1.273 +)
1.274 +{
1.275 + PRUint32 count;
1.276 +
1.277 + PZ_Lock(hash->mutex);
1.278 +
1.279 + count = hash->count;
1.280 +
1.281 + (void)PZ_Unlock(hash->mutex);
1.282 +
1.283 + return count;
1.284 +}
1.285 +
1.286 +/*
1.287 + * nssHash_Exists
1.288 + *
1.289 + */
1.290 +NSS_IMPLEMENT PRBool
1.291 +nssHash_Exists
1.292 +(
1.293 + nssHash *hash,
1.294 + const void *it
1.295 +)
1.296 +{
1.297 + void *value;
1.298 +
1.299 + PZ_Lock(hash->mutex);
1.300 +
1.301 + value = PL_HashTableLookup(hash->plHashTable, it);
1.302 +
1.303 + (void)PZ_Unlock(hash->mutex);
1.304 +
1.305 + if( (void *)NULL == value ) {
1.306 + return PR_FALSE;
1.307 + } else {
1.308 + return PR_TRUE;
1.309 + }
1.310 +}
1.311 +
1.312 +/*
1.313 + * nssHash_Lookup
1.314 + *
1.315 + */
1.316 +NSS_IMPLEMENT void *
1.317 +nssHash_Lookup
1.318 +(
1.319 + nssHash *hash,
1.320 + const void *it
1.321 +)
1.322 +{
1.323 + void *rv;
1.324 +
1.325 + PZ_Lock(hash->mutex);
1.326 +
1.327 + rv = PL_HashTableLookup(hash->plHashTable, it);
1.328 +
1.329 + (void)PZ_Unlock(hash->mutex);
1.330 +
1.331 + return rv;
1.332 +}
1.333 +
1.334 +struct arg_str {
1.335 + nssHashIterator fcn;
1.336 + void *closure;
1.337 +};
1.338 +
1.339 +static PRIntn
1.340 +nss_hash_enumerator
1.341 +(
1.342 + PLHashEntry *he,
1.343 + PRIntn index,
1.344 + void *arg
1.345 +)
1.346 +{
1.347 + struct arg_str *as = (struct arg_str *)arg;
1.348 + as->fcn(he->key, he->value, as->closure);
1.349 + return HT_ENUMERATE_NEXT;
1.350 +}
1.351 +
1.352 +/*
1.353 + * nssHash_Iterate
1.354 + *
1.355 + * NOTE that the iteration function will be called with the hashtable locked.
1.356 + */
1.357 +NSS_IMPLEMENT void
1.358 +nssHash_Iterate
1.359 +(
1.360 + nssHash *hash,
1.361 + nssHashIterator fcn,
1.362 + void *closure
1.363 +)
1.364 +{
1.365 + struct arg_str as;
1.366 + as.fcn = fcn;
1.367 + as.closure = closure;
1.368 +
1.369 + PZ_Lock(hash->mutex);
1.370 +
1.371 + PL_HashTableEnumerateEntries(hash->plHashTable, nss_hash_enumerator, &as);
1.372 +
1.373 + (void)PZ_Unlock(hash->mutex);
1.374 +
1.375 + return;
1.376 +}
