VirtualBox

source: vbox/trunk/src/libs/xpcom18a4/xpcom/ds/nsDoubleHashtable.h@ 78394

Last change on this file since 78394 was 1, checked in by vboxsync, 55 years ago

import
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 19.9 KB
Line 
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 Mozilla Communicator client code.
16 *
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.
21 *
22 * Contributor(s):
23 *
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.
35 *
36 * ***** END LICENSE BLOCK ***** */
37
38/**
39 * nsDoubleHashtable.h is OBSOLETE. Use nsTHashtable or a derivative instead.
40 */
41
42#ifndef __nsDoubleHashtable_h__
43#define __nsDoubleHashtable_h__
44
45#include "pldhash.h"
46#include "nscore.h"
47#include "nsString.h"
48#include "nsReadableUtils.h"
49
50/*
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
55 */
56
57/*
58 * USAGE
59 *
60 * To use nsDoubleHashtable macros
61 * (1) Define an entry class
62 * (2) Create the hash class
63 * (3) Use the hash class
64 *
65 * EXAMPLE
66 *
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.
69 *
70 * (1) Define an entry class
71 *
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.
76 *
77 * #include "nsDoubleHashtable.h"
78 *
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 {
83 * public:
84 * DictionaryEntry(const void* aKey) : PLDHashStringEntry(aKey) { }
85 * ~DictionaryEntry() { }
86 * nsString mPronunciation;
87 * nsString mDefinition;
88 * }
89 *
90 * (2) Create the hash class
91 *
92 * The final hash class you will use in step 3 is defined by 2 macros.
93 *
94 * DECL_DHASH_WRAPPER(Dictionary, DictionaryEntry, const nsAString&)
95 * DHASH_WRAPPER(Dictionary, DictionaryEntry, const nsAString&)
96 *
97 * (3) Use the hash class
98 *
99 * Here is a simple main() that might look up a string:
100 *
101 * int main(void) {
102 * Dictionary d;
103 * nsresult rv = d.Init(10);
104 * if (NS_FAILED(rv)) return 1;
105 *
106 * // Put an entry
107 * DictionaryEntry* a = d.AddEntry(NS_LITERAL_STRING("doomed"));
108 * if (!a) return 1;
109 * a->mDefinition.AssignLiteral("The state you get in when a Mozilla release is pending");
110 * a->mPronunciation.AssignLiteral("doom-d");
111 *
112 * // Get the entry
113 * DictionaryEntry* b = d.GetEntry(NS_LITERAL_STRING("doomed"));
114 * printf("doomed: %s\n", NS_ConvertUCS2toUTF8(b->mDefinition).get());
115 *
116 * // Entries will be automagically cleaned up when the Dictionary object goes away
117 * return 0;
118 * }
119 *
120 *
121 * BONUS POINTS
122 *
123 * You may wish to extend this class and add helper functions like
124 * nsDependentString* GetDefinition(nsAString& aWord). For example:
125 *
126 * class MyDictionary : public Dictionary {
127 * public:
128 * MyDictionary() { }
129 * // Make SURE you have a virtual destructor
130 * virtual ~myDictionary() { }
131 * nsDependentString* GetDefinition(const nsAString& aWord) {
132 * DictionaryEntry* e = GetEntry(aWord);
133 * if (e) {
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());
137 * } else {
138 * return nsnull;
139 * }
140 * }
141 * nsresult PutDefinition(const nsAString& aWord,
142 * const nsAString& aDefinition,
143 * const nsAString& aPronunciation) {
144 * DictionaryEntry* e = AddEntry(aWord);
145 * if (!e) {
146 * return NS_ERROR_OUT_OF_MEMORY;
147 * }
148 * e->mDefinition = aDefinition;
149 * e->mPronunciation = aPronunciation;
150 * return NS_OK;
151 * }
152 * }
153 */
154
155/*
156 * ENTRY CLASS DEFINITION
157 *
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):
163 *
164 * CONSTRUCTOR(const void* aKey)
165 * When your entry is constructed it will only be given a pointer to the key.
166 *
167 * DESTRUCTOR
168 * Called when the entry is destroyed (of course).
169 *
170 * const void* GetKey()
171 * Must return a pointer to the key
172 *
173 * PRBool MatchEntry(const void* aKey) - return true or false depending on
174 * whether the key pointed to by aKey matches this entry
175 *
176 * static PLDHashNumber HashKey(const void* aKey) - get a hashcode based on the
177 * key (must be the same every time for the same key, but does not have
178 * to be unique)
179 *
180 * For a small hash that just does key->value, you will often just extend a
181 * standard key class and put a value member into it, and have a destructor and
182 * constructor--nothing else necessary.
183 *
184 * See the default key entry classes as example entry classes.
185 *
186 * NOTES:
187 * - Do NOT ADD VIRTUAL METHODS INTO YOUR ENTRY. Everything will break.
188 * This is because of the 4-byte pointer C++ magically prepends onto your
189 * entry class. It interacts very unhappily with PLDHashTable.
190 */
191
192/*
193 * PRIVATE HASHTABLE MACROS
194 *
195 * These internal macros can be used to declare the callbacks for an entry
196 * class, but the wrapper class macros call these for you so don't call them.
197 */
198
199//
200// DHASH_CALLBACKS
201//
202// Define the hashtable callback functions. Do this in one place only, as you
203// will have redundant symbols otherwise.
204//
205// ENTRY_CLASS: the classname of the entry
206//
207#define DHASH_CALLBACKS(ENTRY_CLASS) \
208PR_STATIC_CALLBACK(const void *) \
209ENTRY_CLASS##GetKey(PLDHashTable* table, PLDHashEntryHdr* entry) \
210{ \
211 ENTRY_CLASS* e = NS_STATIC_CAST(ENTRY_CLASS*, entry); \
212 return e->GetKey(); \
213} \
214PR_STATIC_CALLBACK(PLDHashNumber) \
215ENTRY_CLASS##HashKey(PLDHashTable* table, const void* key) \
216{ \
217 return ENTRY_CLASS::HashKey(key); \
218} \
219PR_STATIC_CALLBACK(PRBool) \
220ENTRY_CLASS##MatchEntry(PLDHashTable *table, const PLDHashEntryHdr *entry, \
221 const void *key) \
222{ \
223 const ENTRY_CLASS* e = NS_STATIC_CAST(const ENTRY_CLASS*, entry); \
224 return e->MatchEntry(key); \
225} \
226PR_STATIC_CALLBACK(void) \
227ENTRY_CLASS##ClearEntry(PLDHashTable *table, PLDHashEntryHdr *entry) \
228{ \
229 ENTRY_CLASS* e = NS_STATIC_CAST(ENTRY_CLASS *, entry); \
230 e->~ENTRY_CLASS(); \
231} \
232PR_STATIC_CALLBACK(PRBool) \
233ENTRY_CLASS##InitEntry(PLDHashTable *table, PLDHashEntryHdr *entry, \
234 const void *key) \
235{ \
236 new (entry) ENTRY_CLASS(key); \
237 return PR_TRUE; \
238}
239
240//
241// DHASH_INIT
242//
243// Initialize hashtable to a certain class.
244//
245// HASHTABLE: the name of the PLDHashTable variable
246// ENTRY_CLASS: the classname of the entry
247// NUM_INITIAL_ENTRIES: the number of entry slots the hashtable should start
248// with
249// RV: an nsresult variable to hold the outcome of the initialization.
250// Will be NS_ERROR_OUT_OF_MEMORY if failed, NS_OK otherwise.
251//
252#define DHASH_INIT(HASHTABLE,ENTRY_CLASS,NUM_INITIAL_ENTRIES,RV) \
253PR_BEGIN_MACRO \
254 static PLDHashTableOps hash_table_ops = \
255 { \
256 PL_DHashAllocTable, \
257 PL_DHashFreeTable, \
258 ENTRY_CLASS##GetKey, \
259 ENTRY_CLASS##HashKey, \
260 ENTRY_CLASS##MatchEntry, \
261 PL_DHashMoveEntryStub, \
262 ENTRY_CLASS##ClearEntry, \
263 PL_DHashFinalizeStub, \
264 ENTRY_CLASS##InitEntry \
265 }; \
266 PRBool isLive = PL_DHashTableInit(&(HASHTABLE), \
267 &hash_table_ops, nsnull, \
268 sizeof(ENTRY_CLASS), \
269 (NUM_INITIAL_ENTRIES)); \
270 if (!isLive) { \
271 (HASHTABLE).ops = nsnull; \
272 RV = NS_ERROR_OUT_OF_MEMORY; \
273 } else { \
274 RV = NS_OK; \
275 } \
276PR_END_MACRO
277
278
279/*
280 * WRAPPER CLASS
281 *
282 * This class handles initialization and destruction of the hashtable
283 * (you must call Init() yourself). It defines these functions:
284 *
285 * Init(aNumInitialEntries)
286 * Initialize the hashtable. This must be called once, it is only separate
287 * from the constructor so that you can get the return value. You should pass
288 * in the number of entries you think the hashtable will typically hold (this
289 * will be the amount of space allocated initially so that it will not have to
290 * grow).
291 *
292 * ENTRY_CLASS* GetEntry(aKey):
293 * Get the entry referenced by aKey and return a pointer to it. THIS IS A
294 * TEMPORARY POINTER and is only guaranteed to exist until the next time you do
295 * an operation on the hashtable. But you can safely use it until then.
296 *
297 * Returns nsnull if the entry is not found.
298 *
299 * ENTRY_CLASS* AddEntry(aKey):
300 * Create a new, empty entry and return a pointer to it for you to fill values
301 * into. THIS IS A TEMPORARY POINTER and is only guaranteed to exist until the
302 * next time you do an operation on the hashtable. But you can safely fill it
303 * in.
304 *
305 * Returns nsnull if the entry cannot be created (usually a low memory
306 * constraint).
307 *
308 * void Remove(aKey)
309 * Remove the entry referenced by aKey. If the entry does not exist, nothing
310 * will happen.
311 *
312 *
313 * DECL_DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE)
314 *
315 * Declare the hash class but do not define the functions.
316 *
317 * CLASSNAME: the name of the class to declare.
318 * ENTRY_CLASS: the class of the entry struct.
319 * KEY_TYPE: the name of the key type for GetEntry and AddEntry.
320 *
321 *
322 * DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE)
323 *
324 * Define the functions for the hash class.
325 *
326 * CLASSNAME: the name of the class to declare.
327 * ENTRY_CLASS: the class of the entry struct.
328 * KEY_TYPE: the name of the key type for GetEntry and AddEntry.
329 *
330 *
331 * CAVEATS:
332 * - You may have only *one* wrapper class per entry class.
333 */
334
335#define DECL_DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE) \
336class DHASH_EXPORT CLASSNAME { \
337public: \
338 CLASSNAME(); \
339 ~CLASSNAME(); \
340 nsresult Init(PRUint32 aNumInitialEntries); \
341 ENTRY_CLASS* GetEntry(const KEY_TYPE aKey); \
342 ENTRY_CLASS* AddEntry(const KEY_TYPE aKey); \
343 void Remove(const KEY_TYPE aKey); \
344 PLDHashTable mHashTable; \
345};
346
347#define DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE) \
348DHASH_CALLBACKS(ENTRY_CLASS) \
349CLASSNAME::CLASSNAME() { \
350 mHashTable.ops = nsnull; \
351} \
352CLASSNAME::~CLASSNAME() { \
353 if (mHashTable.ops) { \
354 PL_DHashTableFinish(&mHashTable); \
355 } \
356} \
357nsresult CLASSNAME::Init(PRUint32 aNumInitialEntries) { \
358 if (!mHashTable.ops) { \
359 nsresult rv; \
360 DHASH_INIT(mHashTable,ENTRY_CLASS,aNumInitialEntries,rv); \
361 return rv; \
362 } \
363 return NS_OK; \
364} \
365ENTRY_CLASS* CLASSNAME::GetEntry(const KEY_TYPE aKey) { \
366 ENTRY_CLASS* e = NS_STATIC_CAST(ENTRY_CLASS*, \
367 PL_DHashTableOperate(&mHashTable, &aKey, \
368 PL_DHASH_LOOKUP)); \
369 return PL_DHASH_ENTRY_IS_BUSY(e) ? e : nsnull; \
370} \
371ENTRY_CLASS* CLASSNAME::AddEntry(const KEY_TYPE aKey) { \
372 return NS_STATIC_CAST(ENTRY_CLASS*, \
373 PL_DHashTableOperate(&mHashTable, &aKey, \
374 PL_DHASH_ADD)); \
375} \
376void CLASSNAME::Remove(const KEY_TYPE aKey) { \
377 PL_DHashTableOperate(&mHashTable, &aKey, PL_DHASH_REMOVE); \
378}
379
380/*
381 * STANDARD KEY ENTRY CLASSES
382 *
383 * We have declared some standard key classes for you to make life a little
384 * easier. These include string, int and void* keys. You can extend these
385 * and add value data members to make a working hash entry class with your
386 * values.
387 *
388 * PLDHashStringEntry: nsAString
389 * PLDHashCStringEntry: nsACString
390 * PLDHashInt32Entry: PRInt32
391 * PLDHashVoidEntry: void*
392 *
393 * As a short example, if you want to make a class that maps int to string,
394 * you could do:
395 *
396 * class MyIntStringEntry : public PLDHashInt32Entry
397 * {
398 * public:
399 * MyIntStringEntry(const void* aKey) : PLDHashInt32Entry(aKey) { }
400 * ~MyIntStringEntry() { };
401 * nsString mMyStr;
402 * };
403 *
404 * XXX It could be advisable (unless COW strings ever happens) to have a
405 * PLDHashDependentStringEntry
406 */
407
408//
409// String-key entry
410//
411class NS_COM PLDHashStringEntry : public PLDHashEntryHdr
412{
413public:
414 PLDHashStringEntry(const void* aKey) :
415 mKey(*NS_STATIC_CAST(const nsAString*, aKey)) { }
416 ~PLDHashStringEntry() { }
417
418 const void* GetKey() const {
419 return NS_STATIC_CAST(const nsAString*, &mKey);
420 }
421 static PLDHashNumber HashKey(const void* key) {
422 return HashString(*NS_STATIC_CAST(const nsAString*, key));
423 }
424 PRBool MatchEntry(const void* key) const {
425 return NS_STATIC_CAST(const nsAString*, key)->Equals(mKey);
426 }
427
428 const nsString mKey;
429};
430
431//
432// CString-key entry
433//
434class NS_COM PLDHashCStringEntry : public PLDHashEntryHdr
435{
436public:
437 PLDHashCStringEntry(const void* aKey) :
438 mKey(*NS_STATIC_CAST(const nsACString*, aKey)) { }
439 ~PLDHashCStringEntry() { }
440
441 const void* GetKey() const {
442 return NS_STATIC_CAST(const nsACString*, &mKey);
443 }
444 static PLDHashNumber HashKey(const void* key) {
445 return HashString(*NS_STATIC_CAST(const nsACString*, key));
446 }
447 PRBool MatchEntry(const void* key) const {
448 return NS_STATIC_CAST(const nsACString*, key)->Equals(mKey);
449 }
450
451 const nsCString mKey;
452};
453
454//
455// Int-key entry
456//
457class NS_COM PLDHashInt32Entry : public PLDHashEntryHdr
458{
459public:
460 PLDHashInt32Entry(const void* aKey) :
461 mKey(*(NS_STATIC_CAST(const PRInt32*, aKey))) { }
462 ~PLDHashInt32Entry() { }
463
464 const void* GetKey() const {
465 return NS_STATIC_CAST(const PRInt32*, &mKey);
466 }
467 static PLDHashNumber HashKey(const void* key) {
468 return *NS_STATIC_CAST(const PRInt32*, key);
469 }
470 PRBool MatchEntry(const void* key) const {
471 return *(NS_STATIC_CAST(const PRInt32*, key)) == mKey;
472 }
473
474 const PRInt32 mKey;
475};
476
477
478//
479// Void-key entry
480//
481class NS_COM PLDHashVoidEntry : public PLDHashEntryHdr
482{
483public:
484 PLDHashVoidEntry(const void* aKey) :
485 mKey(*(const void**)aKey) { }
486 ~PLDHashVoidEntry() { }
487
488 const void* GetKey() const {
489 return (const void**)&mKey;
490 }
491 static PLDHashNumber HashKey(const void* key) {
492 return PLDHashNumber(NS_PTR_TO_INT32(*(const void**)key)) >> 2;
493 }
494 PRBool MatchEntry(const void* key) const {
495 return *(const void**)key == mKey;
496 }
497
498 const void* mKey;
499};
500
501
502#define DHASH_EXPORT
503
504
505#endif
Note: See TracBrowser for help on using the repository browser.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette