xpcom/glue/nsBaseHashtable.h

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* ***** BEGIN LICENSE BLOCK *****
   3  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   4  *
   5  * The contents of this file are subject to the Mozilla Public License Version
   6  * 1.1 (the "License"); you may not use this file except in compliance with
   7  * the License. You may obtain a copy of the License at
   8  * http://www.mozilla.org/MPL/
   9  *
  10  * Software distributed under the License is distributed on an "AS IS" basis,
  11  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  12  * for the specific language governing rights and limitations under the
  13  * License.
  14  *
  15  * The Original Code is C++ hashtable templates.
  16  *
  17  * The Initial Developer of the Original Code is
  18  * Benjamin Smedberg.
  19  * Portions created by the Initial Developer are Copyright (C) 2002
  20  * the Initial Developer. All Rights Reserved.
  21  *
  22  * Contributor(s):
  23  *
  24  * Alternatively, the contents of this file may be used under the terms of
  25  * either the GNU General Public License Version 2 or later (the "GPL"), or
  26  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  27  * in which case the provisions of the GPL or the LGPL are applicable instead
  28  * of those above. If you wish to allow use of your version of this file only
  29  * under the terms of either the GPL or the LGPL, and not to allow others to
  30  * use your version of this file under the terms of the MPL, indicate your
  31  * decision by deleting the provisions above and replace them with the notice
  32  * and other provisions required by the GPL or the LGPL. If you do not delete
  33  * the provisions above, a recipient may use your version of this file under
  34  * the terms of any one of the MPL, the GPL or the LGPL.
  35  *
  36  * ***** END LICENSE BLOCK ***** */
  37
  38 #ifndef nsBaseHashtable_h__
  39 #define nsBaseHashtable_h__
  40
  41 #include "nsTHashtable.h"
  42 #include "prlock.h"
  43 #include "nsDebug.h"
  44
  45 template<class KeyClass,class DataType,class UserDataType>
  46 class nsBaseHashtable; // forward declaration
  47
  48 /**
  49  * the private nsTHashtable::EntryType class used by nsBaseHashtable
  50  * @see nsTHashtable for the specification of this class
  51  * @see nsBaseHashtable for template parameters
  52  */
  53 template<class KeyClass,class DataType>
  54 class nsBaseHashtableET : public KeyClass
  55 {
  56 public:
  57   DataType mData;
  58   friend class nsTHashtable< nsBaseHashtableET<KeyClass,DataType> >;
  59
  60 private:
  61   typedef typename KeyClass::KeyType KeyType;
  62   typedef typename KeyClass::KeyTypePointer KeyTypePointer;
  63
  64   nsBaseHashtableET(KeyTypePointer aKey);
  65   nsBaseHashtableET(nsBaseHashtableET<KeyClass,DataType>& toCopy);
  66   ~nsBaseHashtableET();
  67 };
  68
  69 /**
  70  * templated hashtable for simple data types
  71  * This class manages simple data types that do not need construction or
  72  * destruction.
  73  *
  74  * @param KeyClass a wrapper-class for the hashtable key, see nsHashKeys.h
  75  *   for a complete specification.
  76  * @param DataType the datatype stored in the hashtable,
  77  *   for example, PRUint32 or nsCOMPtr.  If UserDataType is not the same,
  78  *   DataType must implicitly cast to UserDataType
  79  * @param UserDataType the user sees, for example PRUint32 or nsISupports*
  80  */
  81 template<class KeyClass,class DataType,class UserDataType>
  82 class nsBaseHashtable :
  83   protected nsTHashtable< nsBaseHashtableET<KeyClass,DataType> >
  84 {
  85 public:
  86   typedef typename KeyClass::KeyType KeyType;
  87   typedef nsBaseHashtableET<KeyClass,DataType> EntryType;
  88
  89   // default constructor+destructor are fine
  90
  91   /**
  92    * Initialize the object.
  93    * @param initSize the initial number of buckets in the hashtable,
  94    *        default 16
  95    * locking on all class methods
  96    * @return    PR_TRUE if the object was initialized properly.
  97    */
  98   PRBool Init(PRUint32 initSize = PL_DHASH_MIN_SIZE)
  99   { return nsTHashtable<EntryType>::Init(initSize); }
 100
 101   /**
 102    * Check whether the table has been initialized.
 103    * This function is especially useful for static hashtables.
 104    * @return PR_TRUE if the table has been initialized.
 105    */
 106   PRBool IsInitialized() const { return !!this->mTable.entrySize; }
 107
 108   /**
 109    * Return the number of entries in the table.
 110    * @return    number of entries
 111    */
 112   PRUint32 Count() const
 113   { return nsTHashtable<EntryType>::Count(); }
 114
 115   /**
 116    * retrieve the value for a key.
 117    * @param aKey the key to retreive
 118    * @param pData data associated with this key will be placed at this
 119    *   pointer.  If you only need to check if the key exists, pData
 120    *   may be null.
 121    * @return PR_TRUE if the key exists. If key does not exist, pData is not
 122    *   modified.
 123    */
 124   PRBool Get(KeyType aKey, UserDataType* pData NS_OUTPARAM) const
 125   {
 126     EntryType* ent = this->GetEntry(aKey);
 127
 128     if (!ent)
 129       return PR_FALSE;
 130
 131     if (pData)
 132       *pData = ent->mData;
 133
 134     return PR_TRUE;
 135   }
 136
 137   /**
 138    * For pointer types, get the value, returning NULL if the entry is not
 139    * present in the table.
 140    *
 141    * @param aKey the key to retrieve
 142    * @return The found value, or NULL if no entry was found with the given key.
 143    * @note If NULL values are stored in the table, it is not possible to
 144    *       distinguish between a NULL value and a missing entry.
 145    */
 146   UserDataType Get(KeyType aKey) const
 147   {
 148     EntryType* ent = this->GetEntry(aKey);
 149     if (!ent)
 150       return NULL;
 151
 152     return ent->mData;
 153   }
 154
 155   /**
 156    * put a new value for the associated key
 157    * @param aKey the key to put
 158    * @param aData the new data
 159    * @return always PR_TRUE, unless memory allocation failed
 160    */
 161   PRBool Put(KeyType aKey, UserDataType aData)
 162   {
 163     EntryType* ent = this->PutEntry(aKey);
 164
 165     if (!ent)
 166       return PR_FALSE;
 167
 168     ent->mData = aData;
 169
 170     return PR_TRUE;
 171   }
 172
 173   /**
 174    * remove the data for the associated key
 175    * @param aKey the key to remove from the hashtable
 176    */
 177   void Remove(KeyType aKey) { this->RemoveEntry(aKey); }
 178
 179   /**
 180    * function type provided by the application for enumeration.
 181    * @param aKey the key being enumerated
 182    * @param aData data being enumerated
 183    * @parm userArg passed unchanged from Enumerate
 184    * @return either
 185    *   @link PLDHashOperator::PL_DHASH_NEXT PL_DHASH_NEXT @endlink or
 186    *   @link PLDHashOperator::PL_DHASH_STOP PL_DHASH_STOP @endlink
 187    */
 188   typedef PLDHashOperator
 189     (* EnumReadFunction)(KeyType      aKey,
 190                          UserDataType aData,
 191                          void*        userArg);
 192
 193   /**
 194    * enumerate entries in the hashtable, without allowing changes
 195    * @param enumFunc enumeration callback
 196    * @param userArg passed unchanged to the EnumReadFunction
 197    */
 198   PRUint32 EnumerateRead(EnumReadFunction enumFunc, void* userArg) const
 199   {
 200     NS_ASSERTION(this->mTable.entrySize,
 201                  "nsBaseHashtable was not initialized properly.");
 202
 203     s_EnumReadArgs enumData = { enumFunc, userArg };
 204     return PL_DHashTableEnumerate(const_cast<PLDHashTable*>(&this->mTable),
 205                                   s_EnumReadStub,
 206                                   &enumData);
 207   }
 208
 209   /**
 210    * function type provided by the application for enumeration.
 211    * @param aKey the key being enumerated
 212    * @param aData Reference to data being enumerated, may be altered. e.g. for
 213    *        nsInterfaceHashtable this is an nsCOMPtr reference...
 214    * @parm userArg passed unchanged from Enumerate
 215    * @return bitflag combination of
 216    *   @link PLDHashOperator::PL_DHASH_REMOVE @endlink,
 217    *   @link PLDHashOperator::PL_DHASH_NEXT PL_DHASH_NEXT @endlink, or
 218    *   @link PLDHashOperator::PL_DHASH_STOP PL_DHASH_STOP @endlink
 219    */
 220   typedef PLDHashOperator
 221     (* EnumFunction)(KeyType       aKey,
 222                      DataType&     aData,
 223                      void*         userArg);
 224
 225   /**
 226    * enumerate entries in the hashtable, allowing changes. This
 227    * functions write-locks the hashtable.
 228    * @param enumFunc enumeration callback
 229    * @param userArg passed unchanged to the EnumFunction
 230    */
 231   PRUint32 Enumerate(EnumFunction enumFunc, void* userArg)
 232   {
 233     NS_ASSERTION(this->mTable.entrySize,
 234                  "nsBaseHashtable was not initialized properly.");
 235
 236     s_EnumArgs enumData = { enumFunc, userArg };
 237     return PL_DHashTableEnumerate(&this->mTable,
 238                                   s_EnumStub,
 239                                   &enumData);
 240   }
 241
 242   /**
 243    * reset the hashtable, removing all entries
 244    */
 245   void Clear() { nsTHashtable<EntryType>::Clear(); }
 246
 247 protected:
 248   /**
 249    * used internally during EnumerateRead.  Allocated on the stack.
 250    * @param func the enumerator passed to EnumerateRead
 251    * @param userArg the userArg passed to EnumerateRead
 252    */
 253   struct s_EnumReadArgs
 254   {
 255     EnumReadFunction func;
 256     void* userArg;
 257   };
 258
 259   static PLDHashOperator s_EnumReadStub(PLDHashTable    *table,
 260                                         PLDHashEntryHdr *hdr,
 261                                         PRUint32         number,
 262                                         void            *arg);
 263
 264   struct s_EnumArgs
 265   {
 266     EnumFunction func;
 267     void* userArg;
 268   };
 269
 270   static PLDHashOperator s_EnumStub(PLDHashTable      *table,
 271                                     PLDHashEntryHdr   *hdr,
 272                                     PRUint32           number,
 273                                     void              *arg);
 274 };
 275
 276 /**
 277  * This class is a thread-safe version of nsBaseHashtable.
 278  */
 279 template<class KeyClass,class DataType,class UserDataType>
 280 class nsBaseHashtableMT :
 281   protected nsBaseHashtable<KeyClass,DataType,UserDataType>
 282 {
 283 public:
 284   typedef typename
 285     nsBaseHashtable<KeyClass,DataType,UserDataType>::EntryType EntryType;
 286   typedef typename
 287     nsBaseHashtable<KeyClass,DataType,UserDataType>::KeyType KeyType;
 288   typedef typename
 289     nsBaseHashtable<KeyClass,DataType,UserDataType>::EnumFunction EnumFunction;
 290   typedef typename
 291     nsBaseHashtable<KeyClass,DataType,UserDataType>::EnumReadFunction EnumReadFunction;
 292
 293   nsBaseHashtableMT() : mLock(nsnull) { }
 294   ~nsBaseHashtableMT();
 295
 296   PRBool Init(PRUint32 initSize = PL_DHASH_MIN_SIZE);
 297   PRBool IsInitialized() const { return mLock != nsnull; }
 298   PRUint32 Count() const;
 299   PRBool Get(KeyType aKey, UserDataType* pData) const;
 300   PRBool Put(KeyType aKey, UserDataType aData);
 301   void Remove(KeyType aKey);
 302
 303   PRUint32 EnumerateRead(EnumReadFunction enumFunc, void* userArg) const;
 304   PRUint32 Enumerate(EnumFunction enumFunc, void* userArg);
 305   void Clear();
 306
 307 protected:
 308   PRLock* mLock;
 309 };
 310
 311
 312 //
 313 // nsBaseHashtableET definitions
 314 //
 315
 316 template<class KeyClass,class DataType>
 317 nsBaseHashtableET<KeyClass,DataType>::nsBaseHashtableET(KeyTypePointer aKey) :
 318   KeyClass(aKey)
 319 { }
 320
 321 template<class KeyClass,class DataType>
 322 nsBaseHashtableET<KeyClass,DataType>::nsBaseHashtableET
 323   (nsBaseHashtableET<KeyClass,DataType>& toCopy) :
 324   KeyClass(toCopy),
 325   mData(toCopy.mData)
 326 { }
 327
 328 template<class KeyClass,class DataType>
 329 nsBaseHashtableET<KeyClass,DataType>::~nsBaseHashtableET()
 330 { }
 331
 332
 333 //
 334 // nsBaseHashtable definitions
 335 //
 336
 337 template<class KeyClass,class DataType,class UserDataType>
 338 PLDHashOperator
 339 nsBaseHashtable<KeyClass,DataType,UserDataType>::s_EnumReadStub
 340   (PLDHashTable *table, PLDHashEntryHdr *hdr, PRUint32 number, void* arg)
 341 {
 342   EntryType* ent = static_cast<EntryType*>(hdr);
 343   s_EnumReadArgs* eargs = (s_EnumReadArgs*) arg;
 344
 345   PLDHashOperator res = (eargs->func)(ent->GetKey(), ent->mData, eargs->userArg);
 346
 347   NS_ASSERTION( !(res & PL_DHASH_REMOVE ),
 348                 "PL_DHASH_REMOVE return during const enumeration; ignoring.");
 349
 350   if (res & PL_DHASH_STOP)
 351     return PL_DHASH_STOP;
 352
 353   return PL_DHASH_NEXT;
 354 }
 355
 356 template<class KeyClass,class DataType,class UserDataType>
 357 PLDHashOperator
 358 nsBaseHashtable<KeyClass,DataType,UserDataType>::s_EnumStub
 359   (PLDHashTable *table, PLDHashEntryHdr *hdr, PRUint32 number, void* arg)
 360 {
 361   EntryType* ent = static_cast<EntryType*>(hdr);
 362   s_EnumArgs* eargs = (s_EnumArgs*) arg;
 363
 364   return (eargs->func)(ent->GetKey(), ent->mData, eargs->userArg);
 365 }
 366
 367
 368 //
 369 // nsBaseHashtableMT  definitions
 370 //
 371
 372 template<class KeyClass,class DataType,class UserDataType>
 373 nsBaseHashtableMT<KeyClass,DataType,UserDataType>::~nsBaseHashtableMT()
 374 {
 375   if (this->mLock)
 376     PR_DestroyLock(this->mLock);
 377 }
 378
 379 template<class KeyClass,class DataType,class UserDataType>
 380 PRBool
 381 nsBaseHashtableMT<KeyClass,DataType,UserDataType>::Init(PRUint32 initSize)
 382 {
 383   if (!nsTHashtable<EntryType>::IsInitialized() && !nsTHashtable<EntryType>::Init(initSize))
 384     return PR_FALSE;
 385
 386   this->mLock = PR_NewLock();
 387   NS_ASSERTION(this->mLock, "Error creating lock during nsBaseHashtableL::Init()");
 388
 389   return (this->mLock != nsnull);
 390 }
 391
 392 template<class KeyClass,class DataType,class UserDataType>
 393 PRUint32
 394 nsBaseHashtableMT<KeyClass,DataType,UserDataType>::Count() const
 395 {
 396   PR_Lock(this->mLock);
 397   PRUint32 count = nsTHashtable<EntryType>::Count();
 398   PR_Unlock(this->mLock);
 399
 400   return count;
 401 }
 402
 403 template<class KeyClass,class DataType,class UserDataType>
 404 PRBool
 405 nsBaseHashtableMT<KeyClass,DataType,UserDataType>::Get(KeyType       aKey,
 406                                                            UserDataType* pData) const
 407 {
 408   PR_Lock(this->mLock);
 409   PRBool res =
 410     nsBaseHashtable<KeyClass,DataType,UserDataType>::Get(aKey, pData);
 411   PR_Unlock(this->mLock);
 412
 413   return res;
 414 }
 415
 416 template<class KeyClass,class DataType,class UserDataType>
 417 PRBool
 418 nsBaseHashtableMT<KeyClass,DataType,UserDataType>::Put(KeyType      aKey,
 419                                                            UserDataType aData)
 420 {
 421   PR_Lock(this->mLock);
 422   PRBool res =
 423     nsBaseHashtable<KeyClass,DataType,UserDataType>::Put(aKey, aData);
 424   PR_Unlock(this->mLock);
 425
 426   return res;
 427 }
 428
 429 template<class KeyClass,class DataType,class UserDataType>
 430 void
 431 nsBaseHashtableMT<KeyClass,DataType,UserDataType>::Remove(KeyType aKey)
 432 {
 433   PR_Lock(this->mLock);
 434   nsBaseHashtable<KeyClass,DataType,UserDataType>::Remove(aKey);
 435   PR_Unlock(this->mLock);
 436 }
 437
 438 template<class KeyClass,class DataType,class UserDataType>
 439 PRUint32
 440 nsBaseHashtableMT<KeyClass,DataType,UserDataType>::EnumerateRead
 441   (EnumReadFunction fEnumCall, void* userArg) const
 442 {
 443   PR_Lock(this->mLock);
 444   PRUint32 count =
 445     nsBaseHashtable<KeyClass,DataType,UserDataType>::EnumerateRead(fEnumCall, userArg);
 446   PR_Unlock(this->mLock);
 447
 448   return count;
 449 }
 450
 451 template<class KeyClass,class DataType,class UserDataType>
 452 PRUint32
 453 nsBaseHashtableMT<KeyClass,DataType,UserDataType>::Enumerate
 454   (EnumFunction fEnumCall, void* userArg)
 455 {
 456   PR_Lock(this->mLock);
 457   PRUint32 count =
 458     nsBaseHashtable<KeyClass,DataType,UserDataType>::Enumerate(fEnumCall, userArg);
 459   PR_Unlock(this->mLock);
 460
 461   return count;
 462 }
 463
 464 template<class KeyClass,class DataType,class UserDataType>
 465 void
 466 nsBaseHashtableMT<KeyClass,DataType,UserDataType>::Clear()
 467 {
 468   PR_Lock(this->mLock);
 469   nsBaseHashtable<KeyClass,DataType,UserDataType>::Clear();
 470   PR_Unlock(this->mLock);
 471 }
 472
 473 #endif // nsBaseHashtable_h__