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
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/
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
15 * The Original Code is Mozilla Communicator client code.
17 * The Initial Developer of the Original Code is
18 * Netscape Communications Corporation.
19 * Portions created by the Initial Developer are Copyright (C) 2002
20 * the Initial Developer. All Rights Reserved.
24 * Alternatively, the contents of this file may be used under the terms of
25 * either of the GNU General Public License Version 2 or later (the "GPL"),
26 * or 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.
36 * ***** END LICENSE BLOCK ***** */
39 * nsDoubleHashtable.h is OBSOLETE. Use nsTHashtable or a derivative instead.
42 #ifndef __nsDoubleHashtable_h__
43 #define __nsDoubleHashtable_h__
48 #include "nsHashKeys.h"
51 * This file provides several major things to make PLDHashTable easier to use:
52 * - hash class macros for you to define a hashtable
53 * - default key classes to use as superclasses for your entries
54 * - empty maps for string, cstring, int and void
60 * To use nsDoubleHashtable macros
61 * (1) Define an entry class
62 * (2) Create the hash class
63 * (3) Use the hash class
67 * As an example, let's create a dictionary, a mapping from a string (the word)
68 * to the pronunciation and definition of those words.
70 * (1) Define an entry class
72 * What we want here is an entry class that contains the word, the
73 * pronunciation string, and the definition string. Since we have a string key
74 * we can use the standard PLDHashStringEntry class as our base, it will handle
75 * the key stuff for us automatically.
77 * #include "nsDoubleHashtable.h"
79 * // Do NOT ADD VIRTUAL METHODS INTO YOUR ENTRY. Everything will break.
80 * // This is because of the 4-byte pointer C++ magically prepends onto your
81 * // entry class. It interacts very unhappily with PLDHashTable.
82 * class DictionaryEntry : public PLDHashStringEntry {
84 * DictionaryEntry(const void* aKey) : PLDHashStringEntry(aKey) { }
85 * ~DictionaryEntry() { }
86 * nsString mPronunciation;
87 * nsString mDefinition;
90 * (2) Create the hash class
92 * The final hash class you will use in step 3 is defined by 2 macros.
94 * DECL_DHASH_WRAPPER(Dictionary, DictionaryEntry, const nsAString&)
95 * DHASH_WRAPPER(Dictionary, DictionaryEntry, const nsAString&)
97 * (3) Use the hash class
99 * Here is a simple main() that might look up a string:
103 * nsresult rv = d.Init(10);
104 * if (NS_FAILED(rv)) return 1;
107 * DictionaryEntry* a = d.AddEntry(NS_LITERAL_STRING("doomed"));
109 * a->mDefinition.AssignLiteral("The state you get in when a Mozilla release is pending");
110 * a->mPronunciation.AssignLiteral("doom-d");
113 * DictionaryEntry* b = d.GetEntry(NS_LITERAL_STRING("doomed"));
114 * printf("doomed: %s\n", NS_ConvertUTF16toUTF8(b->mDefinition).get());
116 * // Entries will be automagically cleaned up when the Dictionary object goes away
123 * You may wish to extend this class and add helper functions like
124 * nsDependentString* GetDefinition(nsAString& aWord). For example:
126 * class MyDictionary : public Dictionary {
129 * // Make SURE you have a virtual destructor
130 * virtual ~myDictionary() { }
131 * nsDependentString* GetDefinition(const nsAString& aWord) {
132 * DictionaryEntry* e = GetEntry(aWord);
134 * // We're returning an nsDependentString here, callers need to delete it
135 * // and it doesn't last long, but at least it doesn't create a copy
136 * return new nsDependentString(e->mDefinition.get());
141 * nsresult PutDefinition(const nsAString& aWord,
142 * const nsAString& aDefinition,
143 * const nsAString& aPronunciation) {
144 * DictionaryEntry* e = AddEntry(aWord);
146 * return NS_ERROR_OUT_OF_MEMORY;
148 * e->mDefinition = aDefinition;
149 * e->mPronunciation = aPronunciation;
156 * ENTRY CLASS DEFINITION
158 * The simplifications of PLDHashTable all hinge upon the idea of an entry
159 * class, which is a class you define, where you store the key and values that
160 * you will place in each hash entry. You must define six methods for an entry
161 * (the standard key classes, which you can extend from, define all of these
162 * for you except the constructor and destructor):
164 * CONSTRUCTOR(const void* aKey)
165 * When your entry is constructed it will only be given a pointer to the key.
168 * Called when the entry is destroyed (of course).
170 * PRBool MatchEntry(const void* aKey) - return true or false depending on
171 * whether the key pointed to by aKey matches this entry
173 * static PLDHashNumber HashKey(const void* aKey) - get a hashcode based on the
174 * key (must be the same every time for the same key, but does not have
177 * For a small hash that just does key->value, you will often just extend a
178 * standard key class and put a value member into it, and have a destructor and
179 * constructor--nothing else necessary.
181 * See the default key entry classes as example entry classes.
184 * - Do NOT ADD VIRTUAL METHODS INTO YOUR ENTRY. Everything will break.
185 * This is because of the 4-byte pointer C++ magically prepends onto your
186 * entry class. It interacts very unhappily with PLDHashTable.
190 * PRIVATE HASHTABLE MACROS
192 * These internal macros can be used to declare the callbacks for an entry
193 * class, but the wrapper class macros call these for you so don't call them.
199 // Define the hashtable callback functions. Do this in one place only, as you
200 // will have redundant symbols otherwise.
202 // ENTRY_CLASS: the classname of the entry
204 #define DHASH_CALLBACKS(ENTRY_CLASS) \
205 static PLDHashNumber \
206 ENTRY_CLASS##HashKey(PLDHashTable* table, const void* key) \
208 return ENTRY_CLASS::HashKey(key); \
211 ENTRY_CLASS##MatchEntry(PLDHashTable *table, const PLDHashEntryHdr *entry, \
214 const ENTRY_CLASS* e = static_cast<const ENTRY_CLASS*>(entry); \
215 return e->MatchEntry(key); \
218 ENTRY_CLASS##ClearEntry(PLDHashTable *table, PLDHashEntryHdr *entry) \
220 ENTRY_CLASS* e = static_cast<ENTRY_CLASS *>(entry); \
224 ENTRY_CLASS##InitEntry(PLDHashTable *table, PLDHashEntryHdr *entry, \
227 new (entry) ENTRY_CLASS(key); \
234 // Initialize hashtable to a certain class.
236 // HASHTABLE: the name of the PLDHashTable variable
237 // ENTRY_CLASS: the classname of the entry
238 // NUM_INITIAL_ENTRIES: the number of entry slots the hashtable should start
240 // RV: an nsresult variable to hold the outcome of the initialization.
241 // Will be NS_ERROR_OUT_OF_MEMORY if failed, NS_OK otherwise.
243 #define DHASH_INIT(HASHTABLE,ENTRY_CLASS,NUM_INITIAL_ENTRIES,RV) \
245 static PLDHashTableOps hash_table_ops = \
247 PL_DHashAllocTable, \
249 ENTRY_CLASS##HashKey, \
250 ENTRY_CLASS##MatchEntry, \
251 PL_DHashMoveEntryStub, \
252 ENTRY_CLASS##ClearEntry, \
253 PL_DHashFinalizeStub, \
254 ENTRY_CLASS##InitEntry \
256 PRBool isLive = PL_DHashTableInit(&(HASHTABLE), \
257 &hash_table_ops, nsnull, \
258 sizeof(ENTRY_CLASS), \
259 (NUM_INITIAL_ENTRIES)); \
261 (HASHTABLE).ops = nsnull; \
262 RV = NS_ERROR_OUT_OF_MEMORY; \
272 * This class handles initialization and destruction of the hashtable
273 * (you must call Init() yourself). It defines these functions:
275 * Init(aNumInitialEntries)
276 * Initialize the hashtable. This must be called once, it is only separate
277 * from the constructor so that you can get the return value. You should pass
278 * in the number of entries you think the hashtable will typically hold (this
279 * will be the amount of space allocated initially so that it will not have to
282 * ENTRY_CLASS* GetEntry(aKey):
283 * Get the entry referenced by aKey and return a pointer to it. THIS IS A
284 * TEMPORARY POINTER and is only guaranteed to exist until the next time you do
285 * an operation on the hashtable. But you can safely use it until then.
287 * Returns nsnull if the entry is not found.
289 * ENTRY_CLASS* AddEntry(aKey):
290 * Create a new, empty entry and return a pointer to it for you to fill values
291 * into. THIS IS A TEMPORARY POINTER and is only guaranteed to exist until the
292 * next time you do an operation on the hashtable. But you can safely fill it
295 * Returns nsnull if the entry cannot be created (usually a low memory
299 * Remove the entry referenced by aKey. If the entry does not exist, nothing
303 * DECL_DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE)
305 * Declare the hash class but do not define the functions.
307 * CLASSNAME: the name of the class to declare.
308 * ENTRY_CLASS: the class of the entry struct.
309 * KEY_TYPE: the name of the key type for GetEntry and AddEntry.
312 * DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE)
314 * Define the functions for the hash class.
316 * CLASSNAME: the name of the class to declare.
317 * ENTRY_CLASS: the class of the entry struct.
318 * KEY_TYPE: the name of the key type for GetEntry and AddEntry.
322 * - You may have only *one* wrapper class per entry class.
325 #define DECL_DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE) \
326 class DHASH_EXPORT CLASSNAME { \
330 nsresult Init(PRUint32 aNumInitialEntries); \
331 ENTRY_CLASS* GetEntry(const KEY_TYPE aKey); \
332 ENTRY_CLASS* AddEntry(const KEY_TYPE aKey); \
333 void Remove(const KEY_TYPE aKey); \
334 PLDHashTable mHashTable; \
337 #define DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE) \
338 DHASH_CALLBACKS(ENTRY_CLASS) \
339 CLASSNAME::CLASSNAME() { \
340 mHashTable.ops = nsnull; \
342 CLASSNAME::~CLASSNAME() { \
343 if (mHashTable.ops) { \
344 PL_DHashTableFinish(&mHashTable); \
347 nsresult CLASSNAME::Init(PRUint32 aNumInitialEntries) { \
348 if (!mHashTable.ops) { \
350 DHASH_INIT(mHashTable,ENTRY_CLASS,aNumInitialEntries,rv); \
355 ENTRY_CLASS* CLASSNAME::GetEntry(const KEY_TYPE aKey) { \
356 ENTRY_CLASS* e = static_cast<ENTRY_CLASS*>( \
357 PL_DHashTableOperate(&mHashTable, &aKey, \
359 return PL_DHASH_ENTRY_IS_BUSY(e) ? e : nsnull; \
361 ENTRY_CLASS* CLASSNAME::AddEntry(const KEY_TYPE aKey) { \
362 return static_cast<ENTRY_CLASS*>( \
363 PL_DHashTableOperate(&mHashTable, &aKey, \
366 void CLASSNAME::Remove(const KEY_TYPE aKey) { \
367 PL_DHashTableOperate(&mHashTable, &aKey, PL_DHASH_REMOVE); \
371 * STANDARD KEY ENTRY CLASSES
373 * We have declared some standard key classes for you to make life a little
374 * easier. These include string, int and void* keys. You can extend these
375 * and add value data members to make a working hash entry class with your
378 * PLDHashStringEntry: nsAString
379 * PLDHashCStringEntry: nsACString
380 * PLDHashInt32Entry: PRInt32
381 * PLDHashVoidEntry: void*
383 * As a short example, if you want to make a class that maps int to string,
386 * class MyIntStringEntry : public PLDHashInt32Entry
389 * MyIntStringEntry(const void* aKey) : PLDHashInt32Entry(aKey) { }
390 * ~MyIntStringEntry() { };
394 * XXX It could be advisable (unless COW strings ever happens) to have a
395 * PLDHashDependentStringEntry
401 class NS_COM PLDHashStringEntry
: public PLDHashEntryHdr
404 PLDHashStringEntry(const void* aKey
) :
405 mKey(*static_cast<const nsAString
*>(aKey
)) { }
406 ~PLDHashStringEntry() { }
408 static PLDHashNumber
HashKey(const void* key
) {
409 return HashString(*static_cast<const nsAString
*>(key
));
411 PRBool
MatchEntry(const void* key
) const {
412 return static_cast<const nsAString
*>(key
)->Equals(mKey
);
421 class NS_COM PLDHashCStringEntry
: public PLDHashEntryHdr
424 PLDHashCStringEntry(const void* aKey
) :
425 mKey(*static_cast<const nsACString
*>(aKey
)) { }
426 ~PLDHashCStringEntry() { }
428 static PLDHashNumber
HashKey(const void* key
) {
429 return HashString(*static_cast<const nsACString
*>(key
));
431 PRBool
MatchEntry(const void* key
) const {
432 return static_cast<const nsACString
*>(key
)->Equals(mKey
);
435 const nsCString mKey
;
441 class NS_COM PLDHashInt32Entry
: public PLDHashEntryHdr
444 PLDHashInt32Entry(const void* aKey
) :
445 mKey(*(static_cast<const PRInt32
*>(aKey
))) { }
446 ~PLDHashInt32Entry() { }
448 static PLDHashNumber
HashKey(const void* key
) {
449 return *static_cast<const PRInt32
*>(key
);
451 PRBool
MatchEntry(const void* key
) const {
452 return *(static_cast<const PRInt32
*>(key
)) == mKey
;
462 class NS_COM PLDHashVoidEntry
: public PLDHashEntryHdr
465 PLDHashVoidEntry(const void* aKey
) :
466 mKey(*(const void**)aKey
) { }
467 ~PLDHashVoidEntry() { }
469 static PLDHashNumber
HashKey(const void* key
) {
470 return PLDHashNumber(NS_PTR_TO_INT32(*(const void**)key
)) >> 2;
472 PRBool
MatchEntry(const void* key
) const {
473 return *(const void**)key
== mKey
;