Back to index

lightning-sunbird  0.9+nobinonly
hash.c
Go to the documentation of this file.
00001 /* ***** BEGIN LICENSE BLOCK *****
00002  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00003  *
00004  * The contents of this file are subject to the Mozilla Public License Version
00005  * 1.1 (the "License"); you may not use this file except in compliance with
00006  * the License. You may obtain a copy of the License at
00007  * http://www.mozilla.org/MPL/
00008  *
00009  * Software distributed under the License is distributed on an "AS IS" basis,
00010  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00011  * for the specific language governing rights and limitations under the
00012  * License.
00013  *
00014  * The Original Code is the Netscape security libraries.
00015  *
00016  * The Initial Developer of the Original Code is
00017  * Netscape Communications Corporation.
00018  * Portions created by the Initial Developer are Copyright (C) 1994-2000
00019  * the Initial Developer. All Rights Reserved.
00020  *
00021  * Contributor(s):
00022  *
00023  * Alternatively, the contents of this file may be used under the terms of
00024  * either the GNU General Public License Version 2 or later (the "GPL"), or
00025  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00026  * in which case the provisions of the GPL or the LGPL are applicable instead
00027  * of those above. If you wish to allow use of your version of this file only
00028  * under the terms of either the GPL or the LGPL, and not to allow others to
00029  * use your version of this file under the terms of the MPL, indicate your
00030  * decision by deleting the provisions above and replace them with the notice
00031  * and other provisions required by the GPL or the LGPL. If you do not delete
00032  * the provisions above, a recipient may use your version of this file under
00033  * the terms of any one of the MPL, the GPL or the LGPL.
00034  *
00035  * ***** END LICENSE BLOCK ***** */
00036 
00037 #ifdef DEBUG
00038 static const char CVS_ID[] = "@(#) $RCSfile: hash.c,v $ $Revision: 1.9 $ $Date: 2005/01/20 02:25:45 $";
00039 #endif /* DEBUG */
00040 
00041 /*
00042  * hash.c
00043  *
00044  * This is merely a couple wrappers around NSPR's PLHashTable, using
00045  * the identity hash and arena-aware allocators.
00046  * This is a copy of ckfw/hash.c, with modifications to use NSS types
00047  * (not Cryptoki types).  Would like for this to be a single implementation,
00048  * but doesn't seem like it will work.
00049  */
00050 
00051 #ifndef BASE_H
00052 #include "base.h"
00053 #endif /* BASE_H */
00054 
00055 /*
00056  * nssHash
00057  *
00058  *  nssHash_Create
00059  *  nssHash_Destroy
00060  *  nssHash_Add
00061  *  nssHash_Remove
00062  *  nssHash_Count
00063  *  nssHash_Exists
00064  *  nssHash_Lookup
00065  *  nssHash_Iterate
00066  */
00067 
00068 struct nssHashStr {
00069   NSSArena *arena;
00070   PRBool i_alloced_arena;
00071   PRLock *mutex;
00072 
00073   /*
00074    * The invariant that mutex protects is:
00075    *   The count accurately reflects the hashtable state.
00076    */
00077 
00078   PLHashTable *plHashTable;
00079   PRUint32 count;
00080 };
00081 
00082 static PLHashNumber
00083 nss_identity_hash
00084 (
00085   const void *key
00086 )
00087 {
00088   PRUint32 i = (PRUint32)key;
00089   PR_ASSERT(sizeof(PLHashNumber) == sizeof(PRUint32));
00090   return (PLHashNumber)i;
00091 }
00092 
00093 static PLHashNumber
00094 nss_item_hash
00095 (
00096   const void *key
00097 )
00098 {
00099   unsigned int i;
00100   PLHashNumber h;
00101   NSSItem *it = (NSSItem *)key;
00102   h = 0;
00103   for (i=0; i<it->size; i++)
00104     h = (h >> 28) ^ (h << 4) ^ ((unsigned char *)it->data)[i];
00105   return h;
00106 }
00107 
00108 static int
00109 nss_compare_items(const void *v1, const void *v2)
00110 {
00111   PRStatus ignore;
00112   return (int)nssItem_Equal((NSSItem *)v1, (NSSItem *)v2, &ignore);
00113 }
00114 
00115 /*
00116  * nssHash_create
00117  *
00118  */
00119 NSS_IMPLEMENT nssHash *
00120 nssHash_Create
00121 (
00122   NSSArena *arenaOpt,
00123   PRUint32 numBuckets,
00124   PLHashFunction keyHash,
00125   PLHashComparator keyCompare,
00126   PLHashComparator valueCompare
00127 )
00128 {
00129   nssHash *rv;
00130   NSSArena *arena;
00131   PRBool i_alloced;
00132 
00133 #ifdef NSSDEBUG
00134   if( arenaOpt && PR_SUCCESS != nssArena_verifyPointer(arenaOpt) ) {
00135     nss_SetError(NSS_ERROR_INVALID_POINTER);
00136     return (nssHash *)NULL;
00137   }
00138 #endif /* NSSDEBUG */
00139 
00140   if (arenaOpt) {
00141     arena = arenaOpt;
00142     i_alloced = PR_FALSE;
00143   } else {
00144     arena = nssArena_Create();
00145     i_alloced = PR_TRUE;
00146   }
00147 
00148   rv = nss_ZNEW(arena, nssHash);
00149   if( (nssHash *)NULL == rv ) {
00150     goto loser;
00151   }
00152 
00153   rv->mutex = PZ_NewLock(nssILockOther);
00154   if( (PZLock *)NULL == rv->mutex ) {
00155     goto loser;
00156   }
00157 
00158   rv->plHashTable = PL_NewHashTable(numBuckets, 
00159                                     keyHash, keyCompare, valueCompare,
00160                                     &nssArenaHashAllocOps, arena);
00161   if( (PLHashTable *)NULL == rv->plHashTable ) {
00162     (void)PZ_DestroyLock(rv->mutex);
00163     goto loser;
00164   }
00165 
00166   rv->count = 0;
00167   rv->arena = arena;
00168   rv->i_alloced_arena = i_alloced;
00169 
00170   return rv;
00171 loser:
00172   (void)nss_ZFreeIf(rv);
00173   return (nssHash *)NULL;
00174 }
00175 
00176 /*
00177  * nssHash_CreatePointer
00178  *
00179  */
00180 NSS_IMPLEMENT nssHash *
00181 nssHash_CreatePointer
00182 (
00183   NSSArena *arenaOpt,
00184   PRUint32 numBuckets
00185 )
00186 {
00187   return nssHash_Create(arenaOpt, numBuckets, 
00188                         nss_identity_hash, PL_CompareValues, PL_CompareValues);
00189 }
00190 
00191 /*
00192  * nssHash_CreateString
00193  *
00194  */
00195 NSS_IMPLEMENT nssHash *
00196 nssHash_CreateString
00197 (
00198   NSSArena *arenaOpt,
00199   PRUint32 numBuckets
00200 )
00201 {
00202   return nssHash_Create(arenaOpt, numBuckets, 
00203                         PL_HashString, PL_CompareStrings, PL_CompareStrings);
00204 }
00205 
00206 /*
00207  * nssHash_CreateItem
00208  *
00209  */
00210 NSS_IMPLEMENT nssHash *
00211 nssHash_CreateItem
00212 (
00213   NSSArena *arenaOpt,
00214   PRUint32 numBuckets
00215 )
00216 {
00217   return nssHash_Create(arenaOpt, numBuckets, 
00218                         nss_item_hash, nss_compare_items, PL_CompareValues);
00219 }
00220 
00221 /*
00222  * nssHash_Destroy
00223  *
00224  */
00225 NSS_IMPLEMENT void
00226 nssHash_Destroy
00227 (
00228   nssHash *hash
00229 )
00230 {
00231   (void)PZ_DestroyLock(hash->mutex);
00232   PL_HashTableDestroy(hash->plHashTable);
00233   if (hash->i_alloced_arena) {
00234     nssArena_Destroy(hash->arena);
00235   } else {
00236     nss_ZFreeIf(hash);
00237   }
00238 }
00239 
00240 /*
00241  * nssHash_Add
00242  *
00243  */
00244 NSS_IMPLEMENT PRStatus
00245 nssHash_Add
00246 (
00247   nssHash *hash,
00248   const void *key,
00249   const void *value
00250 )
00251 {
00252   PRStatus error = PR_FAILURE;
00253   PLHashEntry *he;
00254 
00255   PZ_Lock(hash->mutex);
00256   
00257   he = PL_HashTableAdd(hash->plHashTable, key, (void *)value);
00258   if( (PLHashEntry *)NULL == he ) {
00259     nss_SetError(NSS_ERROR_NO_MEMORY);
00260   } else if (he->value != value) {
00261     nss_SetError(NSS_ERROR_HASH_COLLISION);
00262   } else {
00263     hash->count++;
00264     error = PR_SUCCESS;
00265   }
00266 
00267   (void)PZ_Unlock(hash->mutex);
00268 
00269   return error;
00270 }
00271 
00272 /*
00273  * nssHash_Remove
00274  *
00275  */
00276 NSS_IMPLEMENT void
00277 nssHash_Remove
00278 (
00279   nssHash *hash,
00280   const void *it
00281 )
00282 {
00283   PRBool found;
00284 
00285   PZ_Lock(hash->mutex);
00286 
00287   found = PL_HashTableRemove(hash->plHashTable, it);
00288   if( found ) {
00289     hash->count--;
00290   }
00291 
00292   (void)PZ_Unlock(hash->mutex);
00293   return;
00294 }
00295 
00296 /*
00297  * nssHash_Count
00298  *
00299  */
00300 NSS_IMPLEMENT PRUint32
00301 nssHash_Count
00302 (
00303   nssHash *hash
00304 )
00305 {
00306   PRUint32 count;
00307 
00308   PZ_Lock(hash->mutex);
00309 
00310   count = hash->count;
00311 
00312   (void)PZ_Unlock(hash->mutex);
00313 
00314   return count;
00315 }
00316 
00317 /*
00318  * nssHash_Exists
00319  *
00320  */
00321 NSS_IMPLEMENT PRBool
00322 nssHash_Exists
00323 (
00324   nssHash *hash,
00325   const void *it
00326 )
00327 {
00328   void *value;
00329 
00330   PZ_Lock(hash->mutex);
00331 
00332   value = PL_HashTableLookup(hash->plHashTable, it);
00333 
00334   (void)PZ_Unlock(hash->mutex);
00335 
00336   if( (void *)NULL == value ) {
00337     return PR_FALSE;
00338   } else {
00339     return PR_TRUE;
00340   }
00341 }
00342 
00343 /*
00344  * nssHash_Lookup
00345  *
00346  */
00347 NSS_IMPLEMENT void *
00348 nssHash_Lookup
00349 (
00350   nssHash *hash,
00351   const void *it
00352 )
00353 {
00354   void *rv;
00355 
00356   PZ_Lock(hash->mutex);
00357 
00358   rv = PL_HashTableLookup(hash->plHashTable, it);
00359 
00360   (void)PZ_Unlock(hash->mutex);
00361 
00362   return rv;
00363 }
00364 
00365 struct arg_str {
00366   nssHashIterator fcn;
00367   void *closure;
00368 };
00369 
00370 static PRIntn
00371 nss_hash_enumerator
00372 (
00373   PLHashEntry *he,
00374   PRIntn index,
00375   void *arg
00376 )
00377 {
00378   struct arg_str *as = (struct arg_str *)arg;
00379   as->fcn(he->key, he->value, as->closure);
00380   return HT_ENUMERATE_NEXT;
00381 }
00382 
00383 /*
00384  * nssHash_Iterate
00385  *
00386  * NOTE that the iteration function will be called with the hashtable locked.
00387  */
00388 NSS_IMPLEMENT void
00389 nssHash_Iterate
00390 (
00391   nssHash *hash,
00392   nssHashIterator fcn,
00393   void *closure
00394 )
00395 {
00396   struct arg_str as;
00397   as.fcn = fcn;
00398   as.closure = closure;
00399 
00400   PZ_Lock(hash->mutex);
00401 
00402   PL_HashTableEnumerateEntries(hash->plHashTable, nss_hash_enumerator, &as);
00403 
00404   (void)PZ_Unlock(hash->mutex);
00405 
00406   return;
00407 }