security/nss/lib/base/hash.c

Thu, 22 Jan 2015 13:21:57 +0100

author
Michael Schloh von Bennewitz <michael@schloh.com>
date
Thu, 22 Jan 2015 13:21:57 +0100
branch
TOR_BUG_9701
changeset 15
b8a032363ba2
permissions
-rw-r--r--

Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6

     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/. */
     5 /*
     6  * hash.c
     7  *
     8  * This is merely a couple wrappers around NSPR's PLHashTable, using
     9  * the identity hash and arena-aware allocators.
    10  * This is a copy of ckfw/hash.c, with modifications to use NSS types
    11  * (not Cryptoki types).  Would like for this to be a single implementation,
    12  * but doesn't seem like it will work.
    13  */
    15 #ifndef BASE_H
    16 #include "base.h"
    17 #endif /* BASE_H */
    19 #include "prbit.h"
    21 /*
    22  * nssHash
    23  *
    24  *  nssHash_Create
    25  *  nssHash_Destroy
    26  *  nssHash_Add
    27  *  nssHash_Remove
    28  *  nssHash_Count
    29  *  nssHash_Exists
    30  *  nssHash_Lookup
    31  *  nssHash_Iterate
    32  */
    34 struct nssHashStr {
    35   NSSArena *arena;
    36   PRBool i_alloced_arena;
    37   PRLock *mutex;
    39   /*
    40    * The invariant that mutex protects is:
    41    *   The count accurately reflects the hashtable state.
    42    */
    44   PLHashTable *plHashTable;
    45   PRUint32 count;
    46 };
    48 static PLHashNumber
    49 nss_identity_hash
    50 (
    51   const void *key
    52 )
    53 {
    54   PRUint32 i = (PRUint32)key;
    55   PR_ASSERT(sizeof(PLHashNumber) == sizeof(PRUint32));
    56   return (PLHashNumber)i;
    57 }
    59 static PLHashNumber
    60 nss_item_hash
    61 (
    62   const void *key
    63 )
    64 {
    65   unsigned int i;
    66   PLHashNumber h;
    67   NSSItem *it = (NSSItem *)key;
    68   h = 0;
    69   for (i=0; i<it->size; i++)
    70     h = PR_ROTATE_LEFT32(h, 4) ^ ((unsigned char *)it->data)[i];
    71   return h;
    72 }
    74 static int
    75 nss_compare_items(const void *v1, const void *v2)
    76 {
    77   PRStatus ignore;
    78   return (int)nssItem_Equal((NSSItem *)v1, (NSSItem *)v2, &ignore);
    79 }
    81 /*
    82  * nssHash_create
    83  *
    84  */
    85 NSS_IMPLEMENT nssHash *
    86 nssHash_Create
    87 (
    88   NSSArena *arenaOpt,
    89   PRUint32 numBuckets,
    90   PLHashFunction keyHash,
    91   PLHashComparator keyCompare,
    92   PLHashComparator valueCompare
    93 )
    94 {
    95   nssHash *rv;
    96   NSSArena *arena;
    97   PRBool i_alloced;
    99 #ifdef NSSDEBUG
   100   if( arenaOpt && PR_SUCCESS != nssArena_verifyPointer(arenaOpt) ) {
   101     nss_SetError(NSS_ERROR_INVALID_POINTER);
   102     return (nssHash *)NULL;
   103   }
   104 #endif /* NSSDEBUG */
   106   if (arenaOpt) {
   107     arena = arenaOpt;
   108     i_alloced = PR_FALSE;
   109   } else {
   110     arena = nssArena_Create();
   111     i_alloced = PR_TRUE;
   112   }
   114   rv = nss_ZNEW(arena, nssHash);
   115   if( (nssHash *)NULL == rv ) {
   116     goto loser;
   117   }
   119   rv->mutex = PZ_NewLock(nssILockOther);
   120   if( (PZLock *)NULL == rv->mutex ) {
   121     goto loser;
   122   }
   124   rv->plHashTable = PL_NewHashTable(numBuckets, 
   125                                     keyHash, keyCompare, valueCompare,
   126                                     &nssArenaHashAllocOps, arena);
   127   if( (PLHashTable *)NULL == rv->plHashTable ) {
   128     (void)PZ_DestroyLock(rv->mutex);
   129     goto loser;
   130   }
   132   rv->count = 0;
   133   rv->arena = arena;
   134   rv->i_alloced_arena = i_alloced;
   136   return rv;
   137 loser:
   138   (void)nss_ZFreeIf(rv);
   139   return (nssHash *)NULL;
   140 }
   142 /*
   143  * nssHash_CreatePointer
   144  *
   145  */
   146 NSS_IMPLEMENT nssHash *
   147 nssHash_CreatePointer
   148 (
   149   NSSArena *arenaOpt,
   150   PRUint32 numBuckets
   151 )
   152 {
   153   return nssHash_Create(arenaOpt, numBuckets, 
   154                         nss_identity_hash, PL_CompareValues, PL_CompareValues);
   155 }
   157 /*
   158  * nssHash_CreateString
   159  *
   160  */
   161 NSS_IMPLEMENT nssHash *
   162 nssHash_CreateString
   163 (
   164   NSSArena *arenaOpt,
   165   PRUint32 numBuckets
   166 )
   167 {
   168   return nssHash_Create(arenaOpt, numBuckets, 
   169                         PL_HashString, PL_CompareStrings, PL_CompareStrings);
   170 }
   172 /*
   173  * nssHash_CreateItem
   174  *
   175  */
   176 NSS_IMPLEMENT nssHash *
   177 nssHash_CreateItem
   178 (
   179   NSSArena *arenaOpt,
   180   PRUint32 numBuckets
   181 )
   182 {
   183   return nssHash_Create(arenaOpt, numBuckets, 
   184                         nss_item_hash, nss_compare_items, PL_CompareValues);
   185 }
   187 /*
   188  * nssHash_Destroy
   189  *
   190  */
   191 NSS_IMPLEMENT void
   192 nssHash_Destroy
   193 (
   194   nssHash *hash
   195 )
   196 {
   197   (void)PZ_DestroyLock(hash->mutex);
   198   PL_HashTableDestroy(hash->plHashTable);
   199   if (hash->i_alloced_arena) {
   200     nssArena_Destroy(hash->arena);
   201   } else {
   202     nss_ZFreeIf(hash);
   203   }
   204 }
   206 /*
   207  * nssHash_Add
   208  *
   209  */
   210 NSS_IMPLEMENT PRStatus
   211 nssHash_Add
   212 (
   213   nssHash *hash,
   214   const void *key,
   215   const void *value
   216 )
   217 {
   218   PRStatus error = PR_FAILURE;
   219   PLHashEntry *he;
   221   PZ_Lock(hash->mutex);
   223   he = PL_HashTableAdd(hash->plHashTable, key, (void *)value);
   224   if( (PLHashEntry *)NULL == he ) {
   225     nss_SetError(NSS_ERROR_NO_MEMORY);
   226   } else if (he->value != value) {
   227     nss_SetError(NSS_ERROR_HASH_COLLISION);
   228   } else {
   229     hash->count++;
   230     error = PR_SUCCESS;
   231   }
   233   (void)PZ_Unlock(hash->mutex);
   235   return error;
   236 }
   238 /*
   239  * nssHash_Remove
   240  *
   241  */
   242 NSS_IMPLEMENT void
   243 nssHash_Remove
   244 (
   245   nssHash *hash,
   246   const void *it
   247 )
   248 {
   249   PRBool found;
   251   PZ_Lock(hash->mutex);
   253   found = PL_HashTableRemove(hash->plHashTable, it);
   254   if( found ) {
   255     hash->count--;
   256   }
   258   (void)PZ_Unlock(hash->mutex);
   259   return;
   260 }
   262 /*
   263  * nssHash_Count
   264  *
   265  */
   266 NSS_IMPLEMENT PRUint32
   267 nssHash_Count
   268 (
   269   nssHash *hash
   270 )
   271 {
   272   PRUint32 count;
   274   PZ_Lock(hash->mutex);
   276   count = hash->count;
   278   (void)PZ_Unlock(hash->mutex);
   280   return count;
   281 }
   283 /*
   284  * nssHash_Exists
   285  *
   286  */
   287 NSS_IMPLEMENT PRBool
   288 nssHash_Exists
   289 (
   290   nssHash *hash,
   291   const void *it
   292 )
   293 {
   294   void *value;
   296   PZ_Lock(hash->mutex);
   298   value = PL_HashTableLookup(hash->plHashTable, it);
   300   (void)PZ_Unlock(hash->mutex);
   302   if( (void *)NULL == value ) {
   303     return PR_FALSE;
   304   } else {
   305     return PR_TRUE;
   306   }
   307 }
   309 /*
   310  * nssHash_Lookup
   311  *
   312  */
   313 NSS_IMPLEMENT void *
   314 nssHash_Lookup
   315 (
   316   nssHash *hash,
   317   const void *it
   318 )
   319 {
   320   void *rv;
   322   PZ_Lock(hash->mutex);
   324   rv = PL_HashTableLookup(hash->plHashTable, it);
   326   (void)PZ_Unlock(hash->mutex);
   328   return rv;
   329 }
   331 struct arg_str {
   332   nssHashIterator fcn;
   333   void *closure;
   334 };
   336 static PRIntn
   337 nss_hash_enumerator
   338 (
   339   PLHashEntry *he,
   340   PRIntn index,
   341   void *arg
   342 )
   343 {
   344   struct arg_str *as = (struct arg_str *)arg;
   345   as->fcn(he->key, he->value, as->closure);
   346   return HT_ENUMERATE_NEXT;
   347 }
   349 /*
   350  * nssHash_Iterate
   351  *
   352  * NOTE that the iteration function will be called with the hashtable locked.
   353  */
   354 NSS_IMPLEMENT void
   355 nssHash_Iterate
   356 (
   357   nssHash *hash,
   358   nssHashIterator fcn,
   359   void *closure
   360 )
   361 {
   362   struct arg_str as;
   363   as.fcn = fcn;
   364   as.closure = closure;
   366   PZ_Lock(hash->mutex);
   368   PL_HashTableEnumerateEntries(hash->plHashTable, nss_hash_enumerator, &as);
   370   (void)PZ_Unlock(hash->mutex);
   372   return;
   373 }

mercurial