xpcom/glue/nsTHashtable.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 nsTHashtable_h__
  39 #define nsTHashtable_h__
  40
  41 #include "nscore.h"
  42 #include "pldhash.h"
  43 #include "nsDebug.h"
  44 #include NEW_H
  45
  46 // helper function for nsTHashtable::Clear()
  47 NS_COM_GLUE PLDHashOperator
  48 PL_DHashStubEnumRemove(PLDHashTable    *table,
  49                        PLDHashEntryHdr *entry,
  50                        PRUint32         ordinal,
  51                        void            *userArg);
  52
  53
  54 /**
  55  * a base class for templated hashtables.
  56  *
  57  * Clients will rarely need to use this class directly. Check the derived
  58  * classes first, to see if they will meet your needs.
  59  *
  60  * @param EntryType  the templated entry-type class that is managed by the
  61  *   hashtable. <code>EntryType</code> must extend the following declaration,
  62  *   and <strong>must not declare any virtual functions or derive from classes
  63  *   with virtual functions.</strong>  Any vtable pointer would break the
  64  *   PLDHashTable code.
  65  *<pre>   class EntryType : public PLDHashEntryHdr
  66  *   {
  67  *   public: or friend nsTHashtable<EntryType>;
  68  *     // KeyType is what we use when Get()ing or Put()ing this entry
  69  *     // this should either be a simple datatype (PRUint32, nsISupports*) or
  70  *     // a const reference (const nsAString&)
  71  *     typedef something KeyType;
  72  *     // KeyTypePointer is the pointer-version of KeyType, because pldhash.h
  73  *     // requires keys to cast to <code>const void*</code>
  74  *     typedef const something* KeyTypePointer;
  75  *
  76  *     EntryType(KeyTypePointer aKey);
  77  *
  78  *     // the copy constructor must be defined, even if AllowMemMove() == true
  79  *     // or you will cause link errors!
  80  *     EntryType(const EntryType& aEnt);
  81  *
  82  *     // the destructor must be defined... or you will cause link errors!
  83  *     ~EntryType();
  84  *
  85  *     // KeyEquals(): does this entry match this key?
  86  *     PRBool KeyEquals(KeyTypePointer aKey) const;
  87  *
  88  *     // KeyToPointer(): Convert KeyType to KeyTypePointer
  89  *     static KeyTypePointer KeyToPointer(KeyType aKey);
  90  *
  91  *     // HashKey(): calculate the hash number
  92  *     static PLDHashNumber HashKey(KeyTypePointer aKey);
  93  *
  94  *     // ALLOW_MEMMOVE can we move this class with memmove(), or do we have
  95  *     // to use the copy constructor?
  96  *     enum { ALLOW_MEMMOVE = PR_(TRUE or FALSE) };
  97  *   }</pre>
  98  *
  99  * @see nsInterfaceHashtable
 100  * @see nsDataHashtable
 101  * @see nsClassHashtable
 102  * @author "Benjamin Smedberg <bsmedberg@covad.net>"
 103  */
 104
 105 template<class EntryType>
 106 class nsTHashtable
 107 {
 108 public:
 109   /**
 110    * A dummy constructor; you must call Init() before using this class.
 111    */
 112   nsTHashtable();
 113
 114   /**
 115    * destructor, cleans up and deallocates
 116    */
 117   ~nsTHashtable();
 118
 119   /**
 120    * Initialize the table.  This function must be called before any other
 121    * class operations.  This can fail due to OOM conditions.
 122    * @param initSize the initial number of buckets in the hashtable, default 16
 123    * @return PR_TRUE if the class was initialized properly.
 124    */
 125   PRBool Init(PRUint32 initSize = PL_DHASH_MIN_SIZE);
 126
 127   /**
 128    * Check whether the table has been initialized. This can be useful for static hashtables.
 129    * @return the initialization state of the class.
 130    */
 131   PRBool IsInitialized() const { return !!mTable.entrySize; }
 132
 133   /**
 134    * Return the generation number for the table. This increments whenever
 135    * the table data items are moved.
 136    */
 137   PRUint32 GetGeneration() const { return mTable.generation; }
 138
 139   /**
 140    * KeyType is typedef'ed for ease of use.
 141    */
 142   typedef typename EntryType::KeyType KeyType;
 143
 144   /**
 145    * KeyTypePointer is typedef'ed for ease of use.
 146    */
 147   typedef typename EntryType::KeyTypePointer KeyTypePointer;
 148
 149   /**
 150    * Return the number of entries in the table.
 151    * @return    number of entries
 152    */
 153   PRUint32 Count() const { return mTable.entryCount; }
 154
 155   /**
 156    * Get the entry associated with a key.
 157    * @param     aKey the key to retrieve
 158    * @return    pointer to the entry class, if the key exists; nsnull if the
 159    *            key doesn't exist
 160    */
 161   EntryType* GetEntry(KeyType aKey) const
 162   {
 163     NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
 164
 165     EntryType* entry =
 166       reinterpret_cast<EntryType*>
 167                       (PL_DHashTableOperate(
 168                             const_cast<PLDHashTable*>(&mTable),
 169                             EntryType::KeyToPointer(aKey),
 170                             PL_DHASH_LOOKUP));
 171     return PL_DHASH_ENTRY_IS_BUSY(entry) ? entry : nsnull;
 172   }
 173
 174   /**
 175    * Get the entry associated with a key, or create a new entry,
 176    * @param     aKey the key to retrieve
 177    * @return    pointer to the entry class retreived; nsnull only if memory
 178                 can't be allocated
 179    */
 180   EntryType* PutEntry(KeyType aKey)
 181   {
 182     NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
 183
 184     return static_cast<EntryType*>
 185                       (PL_DHashTableOperate(
 186                             &mTable,
 187                             EntryType::KeyToPointer(aKey),
 188                             PL_DHASH_ADD));
 189   }
 190
 191   /**
 192    * Remove the entry associated with a key.
 193    * @param     aKey of the entry to remove
 194    */
 195   void RemoveEntry(KeyType aKey)
 196   {
 197     NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
 198
 199     PL_DHashTableOperate(&mTable,
 200                          EntryType::KeyToPointer(aKey),
 201                          PL_DHASH_REMOVE);
 202   }
 203
 204   /**
 205    * Remove the entry associated with a key, but don't resize the hashtable.
 206    * This is a low-level method, and is not recommended unless you know what
 207    * you're doing and you need the extra performance. This method can be used
 208    * during enumeration, while RemoveEntry() cannot.
 209    * @param aEntry   the entry-pointer to remove (obtained from GetEntry or
 210    *                 the enumerator
 211    */
 212   void RawRemoveEntry(EntryType* aEntry)
 213   {
 214     PL_DHashTableRawRemove(&mTable, aEntry);
 215   }
 216
 217   /**
 218    * client must provide an <code>Enumerator</code> function for
 219    *   EnumerateEntries
 220    * @param     aEntry the entry being enumerated
 221    * @param     userArg passed unchanged from <code>EnumerateEntries</code>
 222    * @return    combination of flags
 223    *            @link PLDHashOperator::PL_DHASH_NEXT PL_DHASH_NEXT @endlink ,
 224    *            @link PLDHashOperator::PL_DHASH_STOP PL_DHASH_STOP @endlink ,
 225    *            @link PLDHashOperator::PL_DHASH_REMOVE PL_DHASH_REMOVE @endlink
 226    */
 227   typedef PLDHashOperator (* Enumerator)(EntryType* aEntry, void* userArg);
 228
 229   /**
 230    * Enumerate all the entries of the function.
 231    * @param     enumFunc the <code>Enumerator</code> function to call
 232    * @param     userArg a pointer to pass to the
 233    *            <code>Enumerator</code> function
 234    * @return    the number of entries actually enumerated
 235    */
 236   PRUint32 EnumerateEntries(Enumerator enumFunc, void* userArg)
 237   {
 238     NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
 239
 240     s_EnumArgs args = { enumFunc, userArg };
 241     return PL_DHashTableEnumerate(&mTable, s_EnumStub, &args);
 242   }
 243
 244   /**
 245    * remove all entries, return hashtable to "pristine" state ;)
 246    */
 247   void Clear()
 248   {
 249     NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
 250
 251     PL_DHashTableEnumerate(&mTable, PL_DHashStubEnumRemove, nsnull);
 252   }
 253
 254 protected:
 255   PLDHashTable mTable;
 256
 257   static const void* s_GetKey(PLDHashTable    *table,
 258                               PLDHashEntryHdr *entry);
 259
 260   static PLDHashNumber s_HashKey(PLDHashTable *table,
 261                                  const void   *key);
 262
 263   static PRBool s_MatchEntry(PLDHashTable           *table,
 264                              const PLDHashEntryHdr  *entry,
 265                              const void             *key);
 266
 267   static void s_CopyEntry(PLDHashTable          *table,
 268                           const PLDHashEntryHdr *from,
 269                           PLDHashEntryHdr       *to);
 270
 271   static void s_ClearEntry(PLDHashTable *table,
 272                            PLDHashEntryHdr *entry);
 273
 274   static PRBool s_InitEntry(PLDHashTable     *table,
 275                             PLDHashEntryHdr  *entry,
 276                             const void       *key);
 277
 278   /**
 279    * passed internally during enumeration.  Allocated on the stack.
 280    *
 281    * @param userFunc the Enumerator function passed to
 282    *   EnumerateEntries by the client
 283    * @param userArg the userArg passed unaltered
 284    */
 285   struct s_EnumArgs
 286   {
 287     Enumerator userFunc;
 288     void* userArg;
 289   };
 290
 291   static PLDHashOperator s_EnumStub(PLDHashTable    *table,
 292                                     PLDHashEntryHdr *entry,
 293                                     PRUint32         number,
 294                                     void            *arg);
 295 private:
 296   // copy constructor, not implemented
 297   nsTHashtable(nsTHashtable<EntryType>& toCopy);
 298
 299   // assignment operator, not implemented
 300   nsTHashtable<EntryType>& operator= (nsTHashtable<EntryType>& toEqual);
 301 };
 302
 303 //
 304 // template definitions
 305 //
 306
 307 template<class EntryType>
 308 nsTHashtable<EntryType>::nsTHashtable()
 309 {
 310   // entrySize is our "I'm initialized" indicator
 311   mTable.entrySize = 0;
 312 }
 313
 314 template<class EntryType>
 315 nsTHashtable<EntryType>::~nsTHashtable()
 316 {
 317   if (mTable.entrySize)
 318     PL_DHashTableFinish(&mTable);
 319 }
 320
 321 template<class EntryType>
 322 PRBool
 323 nsTHashtable<EntryType>::Init(PRUint32 initSize)
 324 {
 325   if (mTable.entrySize)
 326   {
 327     NS_ERROR("nsTHashtable::Init() should not be called twice.");
 328     return PR_TRUE;
 329   }
 330
 331   static PLDHashTableOps sOps =
 332   {
 333     ::PL_DHashAllocTable,
 334     ::PL_DHashFreeTable,
 335     s_HashKey,
 336     s_MatchEntry,
 337     ::PL_DHashMoveEntryStub,
 338     s_ClearEntry,
 339     ::PL_DHashFinalizeStub,
 340     s_InitEntry
 341   };
 342
 343   if (!EntryType::ALLOW_MEMMOVE)
 344   {
 345     sOps.moveEntry = s_CopyEntry;
 346   }
 347
 348   if (!PL_DHashTableInit(&mTable, &sOps, nsnull, sizeof(EntryType), initSize))
 349   {
 350     // if failed, reset "flag"
 351     mTable.entrySize = 0;
 352     return PR_FALSE;
 353   }
 354
 355   return PR_TRUE;
 356 }
 357
 358 // static definitions
 359
 360 template<class EntryType>
 361 PLDHashNumber
 362 nsTHashtable<EntryType>::s_HashKey(PLDHashTable  *table,
 363                                    const void    *key)
 364 {
 365   return EntryType::HashKey(reinterpret_cast<const KeyTypePointer>(key));
 366 }
 367
 368 template<class EntryType>
 369 PRBool
 370 nsTHashtable<EntryType>::s_MatchEntry(PLDHashTable          *table,
 371                                       const PLDHashEntryHdr *entry,
 372                                       const void            *key)
 373 {
 374   return ((const EntryType*) entry)->KeyEquals(
 375     reinterpret_cast<const KeyTypePointer>(key));
 376 }
 377
 378 template<class EntryType>
 379 void
 380 nsTHashtable<EntryType>::s_CopyEntry(PLDHashTable          *table,
 381                                      const PLDHashEntryHdr *from,
 382                                      PLDHashEntryHdr       *to)
 383 {
 384   EntryType* fromEntry =
 385     const_cast<EntryType*>(reinterpret_cast<const EntryType*>(from));
 386
 387   new(to) EntryType(*fromEntry);
 388
 389   fromEntry->~EntryType();
 390 }
 391
 392 template<class EntryType>
 393 void
 394 nsTHashtable<EntryType>::s_ClearEntry(PLDHashTable    *table,
 395                                       PLDHashEntryHdr *entry)
 396 {
 397   reinterpret_cast<EntryType*>(entry)->~EntryType();
 398 }
 399
 400 template<class EntryType>
 401 PRBool
 402 nsTHashtable<EntryType>::s_InitEntry(PLDHashTable    *table,
 403                                      PLDHashEntryHdr *entry,
 404                                      const void      *key)
 405 {
 406   new(entry) EntryType(reinterpret_cast<KeyTypePointer>(key));
 407   return PR_TRUE;
 408 }
 409
 410 template<class EntryType>
 411 PLDHashOperator
 412 nsTHashtable<EntryType>::s_EnumStub(PLDHashTable    *table,
 413                                     PLDHashEntryHdr *entry,
 414                                     PRUint32         number,
 415                                     void            *arg)
 416 {
 417   // dereferences the function-pointer to the user's enumeration function
 418   return (* reinterpret_cast<s_EnumArgs*>(arg)->userFunc)(
 419     reinterpret_cast<EntryType*>(entry),
 420     reinterpret_cast<s_EnumArgs*>(arg)->userArg);
 421 }
 422
 423 #endif // nsTHashtable_h__