security/nss/lib/base/hash.c

   1 /* ***** BEGIN LICENSE BLOCK *****
   2  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   3  *
   4  * The contents of this file are subject to the Mozilla Public License Version
   5  * 1.1 (the "License"); you may not use this file except in compliance with
   6  * the License. You may obtain a copy of the License at
   7  * http://www.mozilla.org/MPL/
   8  *
   9  * Software distributed under the License is distributed on an "AS IS" basis,
  10  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  11  * for the specific language governing rights and limitations under the
  12  * License.
  13  *
  14  * The Original Code is the Netscape security libraries.
  15  *
  16  * The Initial Developer of the Original Code is
  17  * Netscape Communications Corporation.
  18  * Portions created by the Initial Developer are Copyright (C) 1994-2000
  19  * the Initial Developer. All Rights Reserved.
  20  *
  21  * Contributor(s):
  22  *
  23  * Alternatively, the contents of this file may be used under the terms of
  24  * either the GNU General Public License Version 2 or later (the "GPL"), or
  25  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  26  * in which case the provisions of the GPL or the LGPL are applicable instead
  27  * of those above. If you wish to allow use of your version of this file only
  28  * under the terms of either the GPL or the LGPL, and not to allow others to
  29  * use your version of this file under the terms of the MPL, indicate your
  30  * decision by deleting the provisions above and replace them with the notice
  31  * and other provisions required by the GPL or the LGPL. If you do not delete
  32  * the provisions above, a recipient may use your version of this file under
  33  * the terms of any one of the MPL, the GPL or the LGPL.
  34  *
  35  * ***** END LICENSE BLOCK ***** */
  36
  37 #ifdef DEBUG
  38 static const char CVS_ID[] = "@(#) $RCSfile: hash.c,v $ $Revision: 1.9 $ $Date: 2005/01/20 02:25:45 $";
  39 #endif /* DEBUG */
  40
  41 /*
  42  * hash.c
  43  *
  44  * This is merely a couple wrappers around NSPR's PLHashTable, using
  45  * the identity hash and arena-aware allocators.
  46  * This is a copy of ckfw/hash.c, with modifications to use NSS types
  47  * (not Cryptoki types).  Would like for this to be a single implementation,
  48  * but doesn't seem like it will work.
  49  */
  50
  51 #ifndef BASE_H
  52 #include "base.h"
  53 #endif /* BASE_H */
  54
  55 /*
  56  * nssHash
  57  *
  58  *  nssHash_Create
  59  *  nssHash_Destroy
  60  *  nssHash_Add
  61  *  nssHash_Remove
  62  *  nssHash_Count
  63  *  nssHash_Exists
  64  *  nssHash_Lookup
  65  *  nssHash_Iterate
  66  */
  67
  68 struct nssHashStr {
  69   NSSArena *arena;
  70   PRBool i_alloced_arena;
  71   PRLock *mutex;
  72
  73   /*
  74    * The invariant that mutex protects is:
  75    *   The count accurately reflects the hashtable state.
  76    */
  77
  78   PLHashTable *plHashTable;
  79   PRUint32 count;
  80 };
  81
  82 static PLHashNumber
  83 nss_identity_hash
  84 (
  85   const void *key
  86 )
  87 {
  88   PRUint32 i = (PRUint32)key;
  89   PR_ASSERT(sizeof(PLHashNumber) == sizeof(PRUint32));
  90   return (PLHashNumber)i;
  91 }
  92
  93 static PLHashNumber
  94 nss_item_hash
  95 (
  96   const void *key
  97 )
  98 {
  99   unsigned int i;
 100   PLHashNumber h;
 101   NSSItem *it = (NSSItem *)key;
 102   h = 0;
 103   for (i=0; i<it->size; i++)
 104     h = (h >> 28) ^ (h << 4) ^ ((unsigned char *)it->data)[i];
 105   return h;
 106 }
 107
 108 static int
 109 nss_compare_items(const void *v1, const void *v2)
 110 {
 111   PRStatus ignore;
 112   return (int)nssItem_Equal((NSSItem *)v1, (NSSItem *)v2, &ignore);
 113 }
 114
 115 /*
 116  * nssHash_create
 117  *
 118  */
 119 NSS_IMPLEMENT nssHash *
 120 nssHash_Create
 121 (
 122   NSSArena *arenaOpt,
 123   PRUint32 numBuckets,
 124   PLHashFunction keyHash,
 125   PLHashComparator keyCompare,
 126   PLHashComparator valueCompare
 127 )
 128 {
 129   nssHash *rv;
 130   NSSArena *arena;
 131   PRBool i_alloced;
 132
 133 #ifdef NSSDEBUG
 134   if( arenaOpt && PR_SUCCESS != nssArena_verifyPointer(arenaOpt) ) {
 135     nss_SetError(NSS_ERROR_INVALID_POINTER);
 136     return (nssHash *)NULL;
 137   }
 138 #endif /* NSSDEBUG */
 139
 140   if (arenaOpt) {
 141     arena = arenaOpt;
 142     i_alloced = PR_FALSE;
 143   } else {
 144     arena = nssArena_Create();
 145     i_alloced = PR_TRUE;
 146   }
 147
 148   rv = nss_ZNEW(arena, nssHash);
 149   if( (nssHash *)NULL == rv ) {
 150     goto loser;
 151   }
 152
 153   rv->mutex = PZ_NewLock(nssILockOther);
 154   if( (PZLock *)NULL == rv->mutex ) {
 155     goto loser;
 156   }
 157
 158   rv->plHashTable = PL_NewHashTable(numBuckets,
 159                                     keyHash, keyCompare, valueCompare,
 160                                     &nssArenaHashAllocOps, arena);
 161   if( (PLHashTable *)NULL == rv->plHashTable ) {
 162     (void)PZ_DestroyLock(rv->mutex);
 163     goto loser;
 164   }
 165
 166   rv->count = 0;
 167   rv->arena = arena;
 168   rv->i_alloced_arena = i_alloced;
 169
 170   return rv;
 171 loser:
 172   (void)nss_ZFreeIf(rv);
 173   return (nssHash *)NULL;
 174 }
 175
 176 /*
 177  * nssHash_CreatePointer
 178  *
 179  */
 180 NSS_IMPLEMENT nssHash *
 181 nssHash_CreatePointer
 182 (
 183   NSSArena *arenaOpt,
 184   PRUint32 numBuckets
 185 )
 186 {
 187   return nssHash_Create(arenaOpt, numBuckets,
 188                         nss_identity_hash, PL_CompareValues, PL_CompareValues);
 189 }
 190
 191 /*
 192  * nssHash_CreateString
 193  *
 194  */
 195 NSS_IMPLEMENT nssHash *
 196 nssHash_CreateString
 197 (
 198   NSSArena *arenaOpt,
 199   PRUint32 numBuckets
 200 )
 201 {
 202   return nssHash_Create(arenaOpt, numBuckets,
 203                         PL_HashString, PL_CompareStrings, PL_CompareStrings);
 204 }
 205
 206 /*
 207  * nssHash_CreateItem
 208  *
 209  */
 210 NSS_IMPLEMENT nssHash *
 211 nssHash_CreateItem
 212 (
 213   NSSArena *arenaOpt,
 214   PRUint32 numBuckets
 215 )
 216 {
 217   return nssHash_Create(arenaOpt, numBuckets,
 218                         nss_item_hash, nss_compare_items, PL_CompareValues);
 219 }
 220
 221 /*
 222  * nssHash_Destroy
 223  *
 224  */
 225 NSS_IMPLEMENT void
 226 nssHash_Destroy
 227 (
 228   nssHash *hash
 229 )
 230 {
 231   (void)PZ_DestroyLock(hash->mutex);
 232   PL_HashTableDestroy(hash->plHashTable);
 233   if (hash->i_alloced_arena) {
 234     nssArena_Destroy(hash->arena);
 235   } else {
 236     nss_ZFreeIf(hash);
 237   }
 238 }
 239
 240 /*
 241  * nssHash_Add
 242  *
 243  */
 244 NSS_IMPLEMENT PRStatus
 245 nssHash_Add
 246 (
 247   nssHash *hash,
 248   const void *key,
 249   const void *value
 250 )
 251 {
 252   PRStatus error = PR_FAILURE;
 253   PLHashEntry *he;
 254
 255   PZ_Lock(hash->mutex);
 256
 257   he = PL_HashTableAdd(hash->plHashTable, key, (void *)value);
 258   if( (PLHashEntry *)NULL == he ) {
 259     nss_SetError(NSS_ERROR_NO_MEMORY);
 260   } else if (he->value != value) {
 261     nss_SetError(NSS_ERROR_HASH_COLLISION);
 262   } else {
 263     hash->count++;
 264     error = PR_SUCCESS;
 265   }
 266
 267   (void)PZ_Unlock(hash->mutex);
 268
 269   return error;
 270 }
 271
 272 /*
 273  * nssHash_Remove
 274  *
 275  */
 276 NSS_IMPLEMENT void
 277 nssHash_Remove
 278 (
 279   nssHash *hash,
 280   const void *it
 281 )
 282 {
 283   PRBool found;
 284
 285   PZ_Lock(hash->mutex);
 286
 287   found = PL_HashTableRemove(hash->plHashTable, it);
 288   if( found ) {
 289     hash->count--;
 290   }
 291
 292   (void)PZ_Unlock(hash->mutex);
 293   return;
 294 }
 295
 296 /*
 297  * nssHash_Count
 298  *
 299  */
 300 NSS_IMPLEMENT PRUint32
 301 nssHash_Count
 302 (
 303   nssHash *hash
 304 )
 305 {
 306   PRUint32 count;
 307
 308   PZ_Lock(hash->mutex);
 309
 310   count = hash->count;
 311
 312   (void)PZ_Unlock(hash->mutex);
 313
 314   return count;
 315 }
 316
 317 /*
 318  * nssHash_Exists
 319  *
 320  */
 321 NSS_IMPLEMENT PRBool
 322 nssHash_Exists
 323 (
 324   nssHash *hash,
 325   const void *it
 326 )
 327 {
 328   void *value;
 329
 330   PZ_Lock(hash->mutex);
 331
 332   value = PL_HashTableLookup(hash->plHashTable, it);
 333
 334   (void)PZ_Unlock(hash->mutex);
 335
 336   if( (void *)NULL == value ) {
 337     return PR_FALSE;
 338   } else {
 339     return PR_TRUE;
 340   }
 341 }
 342
 343 /*
 344  * nssHash_Lookup
 345  *
 346  */
 347 NSS_IMPLEMENT void *
 348 nssHash_Lookup
 349 (
 350   nssHash *hash,
 351   const void *it
 352 )
 353 {
 354   void *rv;
 355
 356   PZ_Lock(hash->mutex);
 357
 358   rv = PL_HashTableLookup(hash->plHashTable, it);
 359
 360   (void)PZ_Unlock(hash->mutex);
 361
 362   return rv;
 363 }
 364
 365 struct arg_str {
 366   nssHashIterator fcn;
 367   void *closure;
 368 };
 369
 370 static PRIntn
 371 nss_hash_enumerator
 372 (
 373   PLHashEntry *he,
 374   PRIntn index,
 375   void *arg
 376 )
 377 {
 378   struct arg_str *as = (struct arg_str *)arg;
 379   as->fcn(he->key, he->value, as->closure);
 380   return HT_ENUMERATE_NEXT;
 381 }
 382
 383 /*
 384  * nssHash_Iterate
 385  *
 386  * NOTE that the iteration function will be called with the hashtable locked.
 387  */
 388 NSS_IMPLEMENT void
 389 nssHash_Iterate
 390 (
 391   nssHash *hash,
 392   nssHashIterator fcn,
 393   void *closure
 394 )
 395 {
 396   struct arg_str as;
 397   as.fcn = fcn;
 398   as.closure = closure;
 399
 400   PZ_Lock(hash->mutex);
 401
 402   PL_HashTableEnumerateEntries(hash->plHashTable, nss_hash_enumerator, &as);
 403
 404   (void)PZ_Unlock(hash->mutex);
 405
 406   return;
 407 }