Back to index

lightning-sunbird  0.9+nobinonly
nsDoubleHashtable.h
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is Mozilla Communicator client code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 2002
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *
00024  * Alternatively, the contents of this file may be used under the terms of
00025  * either of the GNU General Public License Version 2 or later (the "GPL"),
00026  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00027  * in which case the provisions of the GPL or the LGPL are applicable instead
00028  * of those above. If you wish to allow use of your version of this file only
00029  * under the terms of either the GPL or the LGPL, and not to allow others to
00030  * use your version of this file under the terms of the MPL, indicate your
00031  * decision by deleting the provisions above and replace them with the notice
00032  * and other provisions required by the GPL or the LGPL. If you do not delete
00033  * the provisions above, a recipient may use your version of this file under
00034  * the terms of any one of the MPL, the GPL or the LGPL.
00035  *
00036  * ***** END LICENSE BLOCK ***** */
00037 
00042 #ifndef __nsDoubleHashtable_h__
00043 #define __nsDoubleHashtable_h__
00044 
00045 #include "pldhash.h"
00046 #include "nscore.h"
00047 #include "nsString.h"
00048 #include "nsHashKeys.h"
00049 
00050 /*
00051  * This file provides several major things to make PLDHashTable easier to use:
00052  * - hash class macros for you to define a hashtable
00053  * - default key classes to use as superclasses for your entries
00054  * - empty maps for string, cstring, int and void
00055  */
00056 
00057 /*
00058  * USAGE
00059  *
00060  * To use nsDoubleHashtable macros
00061  * (1) Define an entry class
00062  * (2) Create the hash class
00063  * (3) Use the hash class
00064  *
00065  * EXAMPLE
00066  *
00067  * As an example, let's create a dictionary, a mapping from a string (the word)
00068  * to the pronunciation and definition of those words.
00069  *
00070  * (1) Define an entry class
00071  *
00072  * What we want here is an entry class that contains the word, the
00073  * pronunciation string, and the definition string.  Since we have a string key
00074  * we can use the standard PLDHashStringEntry class as our base, it will handle
00075  * the key stuff for us automatically.
00076  *
00077  * #include "nsDoubleHashtable.h"
00078  *
00079  * // Do NOT ADD VIRTUAL METHODS INTO YOUR ENTRY.  Everything will break.
00080  * // This is because of the 4-byte pointer C++ magically prepends onto your
00081  * // entry class.  It interacts very unhappily with PLDHashTable.
00082  * class DictionaryEntry : public PLDHashStringEntry {
00083  * public:
00084  *   DictionaryEntry(const void* aKey) : PLDHashStringEntry(aKey) { }
00085  *   ~DictionaryEntry() { }
00086  *   nsString mPronunciation;
00087  *   nsString mDefinition;
00088  * }
00089  *
00090  * (2) Create the hash class
00091  *
00092  * The final hash class you will use in step 3 is defined by 2 macros.
00093  *
00094  * DECL_DHASH_WRAPPER(Dictionary, DictionaryEntry, const nsAString&)
00095  * DHASH_WRAPPER(Dictionary, DictionaryEntry, const nsAString&)
00096  * 
00097  * (3) Use the hash class
00098  *
00099  * Here is a simple main() that might look up a string:
00100  *
00101  * int main(void) {
00102  *   Dictionary d;
00103  *   nsresult rv = d.Init(10);
00104  *   if (NS_FAILED(rv)) return 1;
00105  *
00106  *   // Put an entry
00107  *   DictionaryEntry* a = d.AddEntry(NS_LITERAL_STRING("doomed"));
00108  *   if (!a) return 1;
00109  *   a->mDefinition.AssignLiteral("The state you get in when a Mozilla release is pending");
00110  *   a->mPronunciation.AssignLiteral("doom-d");
00111  *
00112  *   // Get the entry
00113  *   DictionaryEntry* b = d.GetEntry(NS_LITERAL_STRING("doomed"));
00114  *   printf("doomed: %s\n", NS_ConvertUCS2toUTF8(b->mDefinition).get());
00115  *
00116  *   // Entries will be automagically cleaned up when the Dictionary object goes away
00117  *   return 0;
00118  * }
00119  *
00120  *
00121  * BONUS POINTS
00122  *
00123  * You may wish to extend this class and add helper functions like
00124  * nsDependentString* GetDefinition(nsAString& aWord).  For example:
00125  *
00126  * class MyDictionary : public Dictionary {
00127  * public:
00128  *   MyDictionary() { }
00129  *   // Make SURE you have a virtual destructor
00130  *   virtual ~myDictionary() { }
00131  *   nsDependentString* GetDefinition(const nsAString& aWord) {
00132  *     DictionaryEntry* e = GetEntry(aWord);
00133  *     if (e) {
00134  *       // We're returning an nsDependentString here, callers need to delete it
00135  *       // and it doesn't last long, but at least it doesn't create a copy
00136  *       return new nsDependentString(e->mDefinition.get());
00137  *     } else {
00138  *       return nsnull;
00139  *     }
00140  *   }
00141  *   nsresult PutDefinition(const nsAString& aWord,
00142  *                          const nsAString& aDefinition,
00143  *                          const nsAString& aPronunciation) {
00144  *     DictionaryEntry* e = AddEntry(aWord);
00145  *     if (!e) {
00146  *       return NS_ERROR_OUT_OF_MEMORY;
00147  *     }
00148  *     e->mDefinition = aDefinition;
00149  *     e->mPronunciation = aPronunciation;
00150  *     return NS_OK;
00151  *   }
00152  * }
00153  */
00154 
00155 /*
00156  * ENTRY CLASS DEFINITION
00157  *
00158  * The simplifications of PLDHashTable all hinge upon the idea of an entry
00159  * class, which is a class you define, where you store the key and values that
00160  * you will place in each hash entry.  You must define six methods for an entry
00161  * (the standard key classes, which you can extend from, define all of these
00162  * for you except the constructor and destructor):
00163  *
00164  * CONSTRUCTOR(const void* aKey)
00165  * When your entry is constructed it will only be given a pointer to the key.
00166  *
00167  * DESTRUCTOR
00168  * Called when the entry is destroyed (of course).
00169  *
00170  * const void* GetKey()
00171  * Must return a pointer to the key
00172  *
00173  * PRBool MatchEntry(const void* aKey) - return true or false depending on
00174  *        whether the key pointed to by aKey matches this entry
00175  *
00176  * static PLDHashNumber HashKey(const void* aKey) - get a hashcode based on the
00177  *        key (must be the same every time for the same key, but does not have
00178  *        to be unique)
00179  *
00180  * For a small hash that just does key->value, you will often just extend a
00181  * standard key class and put a value member into it, and have a destructor and
00182  * constructor--nothing else necessary.
00183  *
00184  * See the default key entry classes as example entry classes.
00185  *
00186  * NOTES:
00187  * - Do NOT ADD VIRTUAL METHODS INTO YOUR ENTRY.  Everything will break.
00188  *   This is because of the 4-byte pointer C++ magically prepends onto your
00189  *   entry class.  It interacts very unhappily with PLDHashTable.
00190  */
00191 
00192 /*
00193  * PRIVATE HASHTABLE MACROS
00194  *
00195  * These internal macros can be used to declare the callbacks for an entry
00196  * class, but the wrapper class macros call these for you so don't call them.
00197  */
00198 
00199 //
00200 // DHASH_CALLBACKS
00201 //
00202 // Define the hashtable callback functions.  Do this in one place only, as you
00203 // will have redundant symbols otherwise.
00204 //
00205 // ENTRY_CLASS: the classname of the entry
00206 //
00207 #define DHASH_CALLBACKS(ENTRY_CLASS)                                          \
00208 PR_STATIC_CALLBACK(const void *)                                              \
00209 ENTRY_CLASS##GetKey(PLDHashTable* table, PLDHashEntryHdr* entry)              \
00210 {                                                                             \
00211   ENTRY_CLASS* e = NS_STATIC_CAST(ENTRY_CLASS*, entry);                       \
00212   return e->GetKey();                                                         \
00213 }                                                                             \
00214 PR_STATIC_CALLBACK(PLDHashNumber)                                             \
00215 ENTRY_CLASS##HashKey(PLDHashTable* table, const void* key)                    \
00216 {                                                                             \
00217   return ENTRY_CLASS::HashKey(key);                                           \
00218 }                                                                             \
00219 PR_STATIC_CALLBACK(PRBool)                                                    \
00220 ENTRY_CLASS##MatchEntry(PLDHashTable *table, const PLDHashEntryHdr *entry,    \
00221                         const void *key)                                      \
00222 {                                                                             \
00223   const ENTRY_CLASS* e = NS_STATIC_CAST(const ENTRY_CLASS*, entry);           \
00224   return e->MatchEntry(key);                                                  \
00225 }                                                                             \
00226 PR_STATIC_CALLBACK(void)                                                      \
00227 ENTRY_CLASS##ClearEntry(PLDHashTable *table, PLDHashEntryHdr *entry)          \
00228 {                                                                             \
00229   ENTRY_CLASS* e = NS_STATIC_CAST(ENTRY_CLASS *, entry);                      \
00230   e->~ENTRY_CLASS();                                                          \
00231 }                                                                             \
00232 PR_STATIC_CALLBACK(PRBool)                                                    \
00233 ENTRY_CLASS##InitEntry(PLDHashTable *table, PLDHashEntryHdr *entry,           \
00234                        const void *key)                                       \
00235 {                                                                             \
00236   new (entry) ENTRY_CLASS(key);                                               \
00237   return PR_TRUE;                                                             \
00238 }
00239 
00240 //
00241 // DHASH_INIT
00242 //
00243 // Initialize hashtable to a certain class.
00244 //
00245 // HASHTABLE: the name of the PLDHashTable variable
00246 // ENTRY_CLASS: the classname of the entry
00247 // NUM_INITIAL_ENTRIES: the number of entry slots the hashtable should start
00248 //                      with
00249 // RV: an nsresult variable to hold the outcome of the initialization.
00250 //     Will be NS_ERROR_OUT_OF_MEMORY if failed, NS_OK otherwise.
00251 //
00252 #define DHASH_INIT(HASHTABLE,ENTRY_CLASS,NUM_INITIAL_ENTRIES,RV)              \
00253 PR_BEGIN_MACRO                                                                \
00254   static PLDHashTableOps hash_table_ops =                                     \
00255   {                                                                           \
00256     PL_DHashAllocTable,                                                       \
00257     PL_DHashFreeTable,                                                        \
00258     ENTRY_CLASS##GetKey,                                                      \
00259     ENTRY_CLASS##HashKey,                                                     \
00260     ENTRY_CLASS##MatchEntry,                                                  \
00261     PL_DHashMoveEntryStub,                                                    \
00262     ENTRY_CLASS##ClearEntry,                                                  \
00263     PL_DHashFinalizeStub,                                                     \
00264     ENTRY_CLASS##InitEntry                                                    \
00265   };                                                                          \
00266   PRBool isLive = PL_DHashTableInit(&(HASHTABLE),                             \
00267                                     &hash_table_ops, nsnull,                  \
00268                                     sizeof(ENTRY_CLASS),                      \
00269                                     (NUM_INITIAL_ENTRIES));                   \
00270   if (!isLive) {                                                              \
00271     (HASHTABLE).ops = nsnull;                                                 \
00272     RV = NS_ERROR_OUT_OF_MEMORY;                                              \
00273   } else {                                                                    \
00274     RV = NS_OK;                                                               \
00275   }                                                                           \
00276 PR_END_MACRO
00277 
00278 
00279 /*
00280  * WRAPPER CLASS
00281  *
00282  * This class handles initialization and destruction of the hashtable
00283  * (you must call Init() yourself).  It defines these functions:
00284  *
00285  * Init(aNumInitialEntries)
00286  * Initialize the hashtable.  This must be called once, it is only separate
00287  * from the constructor so that you can get the return value.  You should pass
00288  * in the number of entries you think the hashtable will typically hold (this
00289  * will be the amount of space allocated initially so that it will not have to
00290  * grow).
00291  *
00292  * ENTRY_CLASS* GetEntry(aKey):
00293  * Get the entry referenced by aKey and return a pointer to it.  THIS IS A
00294  * TEMPORARY POINTER and is only guaranteed to exist until the next time you do
00295  * an operation on the hashtable.  But you can safely use it until then.
00296  *
00297  * Returns nsnull if the entry is not found.
00298  *
00299  * ENTRY_CLASS* AddEntry(aKey):
00300  * Create a new, empty entry and return a pointer to it for you to fill values
00301  * into.  THIS IS A TEMPORARY POINTER and is only guaranteed to exist until the
00302  * next time you do an operation on the hashtable.  But you can safely fill it
00303  * in.
00304  *
00305  * Returns nsnull if the entry cannot be created (usually a low memory
00306  * constraint).
00307  *
00308  * void Remove(aKey)
00309  * Remove the entry referenced by aKey.  If the entry does not exist, nothing
00310  * will happen.
00311  *
00312  *
00313  * DECL_DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE)
00314  *
00315  * Declare the hash class but do not define the functions.
00316  *
00317  * CLASSNAME: the name of the class to declare.
00318  * ENTRY_CLASS: the class of the entry struct.
00319  * KEY_TYPE: the name of the key type for GetEntry and AddEntry.
00320  *
00321  *
00322  * DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE)
00323  *
00324  * Define the functions for the hash class.
00325  *
00326  * CLASSNAME: the name of the class to declare.
00327  * ENTRY_CLASS: the class of the entry struct.
00328  * KEY_TYPE: the name of the key type for GetEntry and AddEntry.
00329  *
00330  *
00331  * CAVEATS:
00332  * - You may have only *one* wrapper class per entry class.
00333  */
00334 
00335 #define DECL_DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE)                    \
00336 class DHASH_EXPORT CLASSNAME {                                                \
00337 public:                                                                       \
00338   CLASSNAME();                                                                \
00339   ~CLASSNAME();                                                               \
00340   nsresult Init(PRUint32 aNumInitialEntries);                                 \
00341   ENTRY_CLASS* GetEntry(const KEY_TYPE aKey);                                 \
00342   ENTRY_CLASS* AddEntry(const KEY_TYPE aKey);                                 \
00343   void Remove(const KEY_TYPE aKey);                                           \
00344   PLDHashTable mHashTable;                                                    \
00345 };
00346 
00347 #define DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE)                         \
00348 DHASH_CALLBACKS(ENTRY_CLASS)                                                  \
00349 CLASSNAME::CLASSNAME() {                                                      \
00350   mHashTable.ops = nsnull;                                                    \
00351 }                                                                             \
00352 CLASSNAME::~CLASSNAME() {                                                     \
00353   if (mHashTable.ops) {                                                       \
00354     PL_DHashTableFinish(&mHashTable);                                         \
00355   }                                                                           \
00356 }                                                                             \
00357 nsresult CLASSNAME::Init(PRUint32 aNumInitialEntries) {                       \
00358   if (!mHashTable.ops) {                                                      \
00359     nsresult rv;                                                              \
00360     DHASH_INIT(mHashTable,ENTRY_CLASS,aNumInitialEntries,rv);                 \
00361     return rv;                                                                \
00362   }                                                                           \
00363   return NS_OK;                                                               \
00364 }                                                                             \
00365 ENTRY_CLASS* CLASSNAME::GetEntry(const KEY_TYPE aKey) {                       \
00366   ENTRY_CLASS* e = NS_STATIC_CAST(ENTRY_CLASS*,                               \
00367                                   PL_DHashTableOperate(&mHashTable, &aKey,    \
00368                                                        PL_DHASH_LOOKUP));     \
00369   return PL_DHASH_ENTRY_IS_BUSY(e) ? e : nsnull;                              \
00370 }                                                                             \
00371 ENTRY_CLASS* CLASSNAME::AddEntry(const KEY_TYPE aKey) {                       \
00372   return NS_STATIC_CAST(ENTRY_CLASS*,                                         \
00373                         PL_DHashTableOperate(&mHashTable, &aKey,              \
00374                                              PL_DHASH_ADD));                  \
00375 }                                                                             \
00376 void CLASSNAME::Remove(const KEY_TYPE aKey) {                                 \
00377   PL_DHashTableOperate(&mHashTable, &aKey, PL_DHASH_REMOVE);                  \
00378 }
00379 
00380 /*
00381  * STANDARD KEY ENTRY CLASSES
00382  *
00383  * We have declared some standard key classes for you to make life a little
00384  * easier.  These include string, int and void* keys.  You can extend these
00385  * and add value data members to make a working hash entry class with your
00386  * values.
00387  *
00388  * PLDHashStringEntry:  nsAString
00389  * PLDHashCStringEntry: nsACString
00390  * PLDHashInt32Entry:   PRInt32
00391  * PLDHashVoidEntry:    void*
00392  *
00393  * As a short example, if you want to make a class that maps int to string,
00394  * you could do:
00395  *
00396  * class MyIntStringEntry : public PLDHashInt32Entry
00397  * {
00398  * public:
00399  *   MyIntStringEntry(const void* aKey) : PLDHashInt32Entry(aKey) { }
00400  *   ~MyIntStringEntry() { };
00401  *   nsString mMyStr;
00402  * };
00403  *
00404  * XXX It could be advisable (unless COW strings ever happens) to have a
00405  * PLDHashDependentStringEntry
00406  */
00407 
00408 //
00409 // String-key entry
00410 //
00411 class NS_COM PLDHashStringEntry : public PLDHashEntryHdr
00412 {
00413 public:
00414   PLDHashStringEntry(const void* aKey) :
00415     mKey(*NS_STATIC_CAST(const nsAString*, aKey)) { }
00416   ~PLDHashStringEntry() { }
00417 
00418   const void* GetKey() const {
00419     return NS_STATIC_CAST(const nsAString*, &mKey);
00420   }
00421   static PLDHashNumber HashKey(const void* key) {
00422     return HashString(*NS_STATIC_CAST(const nsAString*, key));
00423   }
00424   PRBool MatchEntry(const void* key) const {
00425     return NS_STATIC_CAST(const nsAString*, key)->Equals(mKey);
00426   }
00427 
00428   const nsString mKey;
00429 };
00430 
00431 //
00432 // CString-key entry
00433 //
00434 class NS_COM PLDHashCStringEntry : public PLDHashEntryHdr
00435 {
00436 public:
00437   PLDHashCStringEntry(const void* aKey) :
00438     mKey(*NS_STATIC_CAST(const nsACString*, aKey)) { }
00439   ~PLDHashCStringEntry() { }
00440 
00441   const void* GetKey() const {
00442     return NS_STATIC_CAST(const nsACString*, &mKey);
00443   }
00444   static PLDHashNumber HashKey(const void* key) {
00445     return HashString(*NS_STATIC_CAST(const nsACString*, key));
00446   }
00447   PRBool MatchEntry(const void* key) const {
00448     return NS_STATIC_CAST(const nsACString*, key)->Equals(mKey);
00449   }
00450 
00451   const nsCString mKey;
00452 };
00453 
00454 //
00455 // Int-key entry
00456 //
00457 class NS_COM PLDHashInt32Entry : public PLDHashEntryHdr
00458 {
00459 public:
00460   PLDHashInt32Entry(const void* aKey) :
00461     mKey(*(NS_STATIC_CAST(const PRInt32*, aKey))) { }
00462   ~PLDHashInt32Entry() { }
00463 
00464   const void* GetKey() const {
00465     return NS_STATIC_CAST(const PRInt32*, &mKey);
00466   }
00467   static PLDHashNumber HashKey(const void* key) {
00468     return *NS_STATIC_CAST(const PRInt32*, key);
00469   }
00470   PRBool MatchEntry(const void* key) const {
00471     return *(NS_STATIC_CAST(const PRInt32*, key)) == mKey;
00472   }
00473 
00474   const PRInt32 mKey;
00475 };
00476 
00477 
00478 //
00479 // Void-key entry
00480 //
00481 class NS_COM PLDHashVoidEntry : public PLDHashEntryHdr
00482 {
00483 public:
00484   PLDHashVoidEntry(const void* aKey) :
00485     mKey(*(const void**)aKey) { }
00486   ~PLDHashVoidEntry() { }
00487 
00488   const void* GetKey() const {
00489     return (const void**)&mKey;
00490   }
00491   static PLDHashNumber HashKey(const void* key) {
00492     return PLDHashNumber(NS_PTR_TO_INT32(*(const void**)key)) >> 2;
00493   }
00494   PRBool MatchEntry(const void* key) const {
00495     return *(const void**)key == mKey;
00496   }
00497 
00498   const void* mKey;
00499 };
00500 
00501 
00502 #define DHASH_EXPORT
00503 
00504 
00505 #endif