summaryrefslogtreecommitdiffstats
path: root/src/libs/xpcom18a4/xpcom/ds/nsDoubleHashtable.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/libs/xpcom18a4/xpcom/ds/nsDoubleHashtable.h505
1 files changed, 505 insertions, 0 deletions
diff --git a/src/libs/xpcom18a4/xpcom/ds/nsDoubleHashtable.h b/src/libs/xpcom18a4/xpcom/ds/nsDoubleHashtable.h
new file mode 100644
index 00000000..27bf4ce5
--- /dev/null
+++ b/src/libs/xpcom18a4/xpcom/ds/nsDoubleHashtable.h
@@ -0,0 +1,505 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is Mozilla Communicator client code.
+ *
+ * The Initial Developer of the Original Code is
+ * Netscape Communications Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 2002
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either of the GNU General Public License Version 2 or later (the "GPL"),
+ * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+/**
+ * nsDoubleHashtable.h is OBSOLETE. Use nsTHashtable or a derivative instead.
+ */
+
+#ifndef __nsDoubleHashtable_h__
+#define __nsDoubleHashtable_h__
+
+#include "pldhash.h"
+#include "nscore.h"
+#include "nsString.h"
+#include "nsReadableUtils.h"
+
+/*
+ * This file provides several major things to make PLDHashTable easier to use:
+ * - hash class macros for you to define a hashtable
+ * - default key classes to use as superclasses for your entries
+ * - empty maps for string, cstring, int and void
+ */
+
+/*
+ * USAGE
+ *
+ * To use nsDoubleHashtable macros
+ * (1) Define an entry class
+ * (2) Create the hash class
+ * (3) Use the hash class
+ *
+ * EXAMPLE
+ *
+ * As an example, let's create a dictionary, a mapping from a string (the word)
+ * to the pronunciation and definition of those words.
+ *
+ * (1) Define an entry class
+ *
+ * What we want here is an entry class that contains the word, the
+ * pronunciation string, and the definition string. Since we have a string key
+ * we can use the standard PLDHashStringEntry class as our base, it will handle
+ * the key stuff for us automatically.
+ *
+ * #include "nsDoubleHashtable.h"
+ *
+ * // Do NOT ADD VIRTUAL METHODS INTO YOUR ENTRY. Everything will break.
+ * // This is because of the 4-byte pointer C++ magically prepends onto your
+ * // entry class. It interacts very unhappily with PLDHashTable.
+ * class DictionaryEntry : public PLDHashStringEntry {
+ * public:
+ * DictionaryEntry(const void* aKey) : PLDHashStringEntry(aKey) { }
+ * ~DictionaryEntry() { }
+ * nsString mPronunciation;
+ * nsString mDefinition;
+ * }
+ *
+ * (2) Create the hash class
+ *
+ * The final hash class you will use in step 3 is defined by 2 macros.
+ *
+ * DECL_DHASH_WRAPPER(Dictionary, DictionaryEntry, const nsAString&)
+ * DHASH_WRAPPER(Dictionary, DictionaryEntry, const nsAString&)
+ *
+ * (3) Use the hash class
+ *
+ * Here is a simple main() that might look up a string:
+ *
+ * int main(void) {
+ * Dictionary d;
+ * nsresult rv = d.Init(10);
+ * if (NS_FAILED(rv)) return 1;
+ *
+ * // Put an entry
+ * DictionaryEntry* a = d.AddEntry(NS_LITERAL_STRING("doomed"));
+ * if (!a) return 1;
+ * a->mDefinition.AssignLiteral("The state you get in when a Mozilla release is pending");
+ * a->mPronunciation.AssignLiteral("doom-d");
+ *
+ * // Get the entry
+ * DictionaryEntry* b = d.GetEntry(NS_LITERAL_STRING("doomed"));
+ * printf("doomed: %s\n", NS_ConvertUCS2toUTF8(b->mDefinition).get());
+ *
+ * // Entries will be automagically cleaned up when the Dictionary object goes away
+ * return 0;
+ * }
+ *
+ *
+ * BONUS POINTS
+ *
+ * You may wish to extend this class and add helper functions like
+ * nsDependentString* GetDefinition(nsAString& aWord). For example:
+ *
+ * class MyDictionary : public Dictionary {
+ * public:
+ * MyDictionary() { }
+ * // Make SURE you have a virtual destructor
+ * virtual ~myDictionary() { }
+ * nsDependentString* GetDefinition(const nsAString& aWord) {
+ * DictionaryEntry* e = GetEntry(aWord);
+ * if (e) {
+ * // We're returning an nsDependentString here, callers need to delete it
+ * // and it doesn't last long, but at least it doesn't create a copy
+ * return new nsDependentString(e->mDefinition.get());
+ * } else {
+ * return nsnull;
+ * }
+ * }
+ * nsresult PutDefinition(const nsAString& aWord,
+ * const nsAString& aDefinition,
+ * const nsAString& aPronunciation) {
+ * DictionaryEntry* e = AddEntry(aWord);
+ * if (!e) {
+ * return NS_ERROR_OUT_OF_MEMORY;
+ * }
+ * e->mDefinition = aDefinition;
+ * e->mPronunciation = aPronunciation;
+ * return NS_OK;
+ * }
+ * }
+ */
+
+/*
+ * ENTRY CLASS DEFINITION
+ *
+ * The simplifications of PLDHashTable all hinge upon the idea of an entry
+ * class, which is a class you define, where you store the key and values that
+ * you will place in each hash entry. You must define six methods for an entry
+ * (the standard key classes, which you can extend from, define all of these
+ * for you except the constructor and destructor):
+ *
+ * CONSTRUCTOR(const void* aKey)
+ * When your entry is constructed it will only be given a pointer to the key.
+ *
+ * DESTRUCTOR
+ * Called when the entry is destroyed (of course).
+ *
+ * const void* GetKey()
+ * Must return a pointer to the key
+ *
+ * PRBool MatchEntry(const void* aKey) - return true or false depending on
+ * whether the key pointed to by aKey matches this entry
+ *
+ * static PLDHashNumber HashKey(const void* aKey) - get a hashcode based on the
+ * key (must be the same every time for the same key, but does not have
+ * to be unique)
+ *
+ * For a small hash that just does key->value, you will often just extend a
+ * standard key class and put a value member into it, and have a destructor and
+ * constructor--nothing else necessary.
+ *
+ * See the default key entry classes as example entry classes.
+ *
+ * NOTES:
+ * - Do NOT ADD VIRTUAL METHODS INTO YOUR ENTRY. Everything will break.
+ * This is because of the 4-byte pointer C++ magically prepends onto your
+ * entry class. It interacts very unhappily with PLDHashTable.
+ */
+
+/*
+ * PRIVATE HASHTABLE MACROS
+ *
+ * These internal macros can be used to declare the callbacks for an entry
+ * class, but the wrapper class macros call these for you so don't call them.
+ */
+
+//
+// DHASH_CALLBACKS
+//
+// Define the hashtable callback functions. Do this in one place only, as you
+// will have redundant symbols otherwise.
+//
+// ENTRY_CLASS: the classname of the entry
+//
+#define DHASH_CALLBACKS(ENTRY_CLASS) \
+PR_STATIC_CALLBACK(const void *) \
+ENTRY_CLASS##GetKey(PLDHashTable* table, PLDHashEntryHdr* entry) \
+{ \
+ ENTRY_CLASS* e = NS_STATIC_CAST(ENTRY_CLASS*, entry); \
+ return e->GetKey(); \
+} \
+PR_STATIC_CALLBACK(PLDHashNumber) \
+ENTRY_CLASS##HashKey(PLDHashTable* table, const void* key) \
+{ \
+ return ENTRY_CLASS::HashKey(key); \
+} \
+PR_STATIC_CALLBACK(PRBool) \
+ENTRY_CLASS##MatchEntry(PLDHashTable *table, const PLDHashEntryHdr *entry, \
+ const void *key) \
+{ \
+ const ENTRY_CLASS* e = NS_STATIC_CAST(const ENTRY_CLASS*, entry); \
+ return e->MatchEntry(key); \
+} \
+PR_STATIC_CALLBACK(void) \
+ENTRY_CLASS##ClearEntry(PLDHashTable *table, PLDHashEntryHdr *entry) \
+{ \
+ ENTRY_CLASS* e = NS_STATIC_CAST(ENTRY_CLASS *, entry); \
+ e->~ENTRY_CLASS(); \
+} \
+PR_STATIC_CALLBACK(PRBool) \
+ENTRY_CLASS##InitEntry(PLDHashTable *table, PLDHashEntryHdr *entry, \
+ const void *key) \
+{ \
+ new (entry) ENTRY_CLASS(key); \
+ return PR_TRUE; \
+}
+
+//
+// DHASH_INIT
+//
+// Initialize hashtable to a certain class.
+//
+// HASHTABLE: the name of the PLDHashTable variable
+// ENTRY_CLASS: the classname of the entry
+// NUM_INITIAL_ENTRIES: the number of entry slots the hashtable should start
+// with
+// RV: an nsresult variable to hold the outcome of the initialization.
+// Will be NS_ERROR_OUT_OF_MEMORY if failed, NS_OK otherwise.
+//
+#define DHASH_INIT(HASHTABLE,ENTRY_CLASS,NUM_INITIAL_ENTRIES,RV) \
+PR_BEGIN_MACRO \
+ static PLDHashTableOps hash_table_ops = \
+ { \
+ PL_DHashAllocTable, \
+ PL_DHashFreeTable, \
+ ENTRY_CLASS##GetKey, \
+ ENTRY_CLASS##HashKey, \
+ ENTRY_CLASS##MatchEntry, \
+ PL_DHashMoveEntryStub, \
+ ENTRY_CLASS##ClearEntry, \
+ PL_DHashFinalizeStub, \
+ ENTRY_CLASS##InitEntry \
+ }; \
+ PRBool isLive = PL_DHashTableInit(&(HASHTABLE), \
+ &hash_table_ops, nsnull, \
+ sizeof(ENTRY_CLASS), \
+ (NUM_INITIAL_ENTRIES)); \
+ if (!isLive) { \
+ (HASHTABLE).ops = nsnull; \
+ RV = NS_ERROR_OUT_OF_MEMORY; \
+ } else { \
+ RV = NS_OK; \
+ } \
+PR_END_MACRO
+
+
+/*
+ * WRAPPER CLASS
+ *
+ * This class handles initialization and destruction of the hashtable
+ * (you must call Init() yourself). It defines these functions:
+ *
+ * Init(aNumInitialEntries)
+ * Initialize the hashtable. This must be called once, it is only separate
+ * from the constructor so that you can get the return value. You should pass
+ * in the number of entries you think the hashtable will typically hold (this
+ * will be the amount of space allocated initially so that it will not have to
+ * grow).
+ *
+ * ENTRY_CLASS* GetEntry(aKey):
+ * Get the entry referenced by aKey and return a pointer to it. THIS IS A
+ * TEMPORARY POINTER and is only guaranteed to exist until the next time you do
+ * an operation on the hashtable. But you can safely use it until then.
+ *
+ * Returns nsnull if the entry is not found.
+ *
+ * ENTRY_CLASS* AddEntry(aKey):
+ * Create a new, empty entry and return a pointer to it for you to fill values
+ * into. THIS IS A TEMPORARY POINTER and is only guaranteed to exist until the
+ * next time you do an operation on the hashtable. But you can safely fill it
+ * in.
+ *
+ * Returns nsnull if the entry cannot be created (usually a low memory
+ * constraint).
+ *
+ * void Remove(aKey)
+ * Remove the entry referenced by aKey. If the entry does not exist, nothing
+ * will happen.
+ *
+ *
+ * DECL_DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE)
+ *
+ * Declare the hash class but do not define the functions.
+ *
+ * CLASSNAME: the name of the class to declare.
+ * ENTRY_CLASS: the class of the entry struct.
+ * KEY_TYPE: the name of the key type for GetEntry and AddEntry.
+ *
+ *
+ * DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE)
+ *
+ * Define the functions for the hash class.
+ *
+ * CLASSNAME: the name of the class to declare.
+ * ENTRY_CLASS: the class of the entry struct.
+ * KEY_TYPE: the name of the key type for GetEntry and AddEntry.
+ *
+ *
+ * CAVEATS:
+ * - You may have only *one* wrapper class per entry class.
+ */
+
+#define DECL_DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE) \
+class DHASH_EXPORT CLASSNAME { \
+public: \
+ CLASSNAME(); \
+ ~CLASSNAME(); \
+ nsresult Init(PRUint32 aNumInitialEntries); \
+ ENTRY_CLASS* GetEntry(const KEY_TYPE aKey); \
+ ENTRY_CLASS* AddEntry(const KEY_TYPE aKey); \
+ void Remove(const KEY_TYPE aKey); \
+ PLDHashTable mHashTable; \
+};
+
+#define DHASH_WRAPPER(CLASSNAME,ENTRY_CLASS,KEY_TYPE) \
+DHASH_CALLBACKS(ENTRY_CLASS) \
+CLASSNAME::CLASSNAME() { \
+ mHashTable.ops = nsnull; \
+} \
+CLASSNAME::~CLASSNAME() { \
+ if (mHashTable.ops) { \
+ PL_DHashTableFinish(&mHashTable); \
+ } \
+} \
+nsresult CLASSNAME::Init(PRUint32 aNumInitialEntries) { \
+ if (!mHashTable.ops) { \
+ nsresult rv; \
+ DHASH_INIT(mHashTable,ENTRY_CLASS,aNumInitialEntries,rv); \
+ return rv; \
+ } \
+ return NS_OK; \
+} \
+ENTRY_CLASS* CLASSNAME::GetEntry(const KEY_TYPE aKey) { \
+ ENTRY_CLASS* e = NS_STATIC_CAST(ENTRY_CLASS*, \
+ PL_DHashTableOperate(&mHashTable, &aKey, \
+ PL_DHASH_LOOKUP)); \
+ return PL_DHASH_ENTRY_IS_BUSY(e) ? e : nsnull; \
+} \
+ENTRY_CLASS* CLASSNAME::AddEntry(const KEY_TYPE aKey) { \
+ return NS_STATIC_CAST(ENTRY_CLASS*, \
+ PL_DHashTableOperate(&mHashTable, &aKey, \
+ PL_DHASH_ADD)); \
+} \
+void CLASSNAME::Remove(const KEY_TYPE aKey) { \
+ PL_DHashTableOperate(&mHashTable, &aKey, PL_DHASH_REMOVE); \
+}
+
+/*
+ * STANDARD KEY ENTRY CLASSES
+ *
+ * We have declared some standard key classes for you to make life a little
+ * easier. These include string, int and void* keys. You can extend these
+ * and add value data members to make a working hash entry class with your
+ * values.
+ *
+ * PLDHashStringEntry: nsAString
+ * PLDHashCStringEntry: nsACString
+ * PLDHashInt32Entry: PRInt32
+ * PLDHashVoidEntry: void*
+ *
+ * As a short example, if you want to make a class that maps int to string,
+ * you could do:
+ *
+ * class MyIntStringEntry : public PLDHashInt32Entry
+ * {
+ * public:
+ * MyIntStringEntry(const void* aKey) : PLDHashInt32Entry(aKey) { }
+ * ~MyIntStringEntry() { };
+ * nsString mMyStr;
+ * };
+ *
+ * XXX It could be advisable (unless COW strings ever happens) to have a
+ * PLDHashDependentStringEntry
+ */
+
+//
+// String-key entry
+//
+class NS_COM PLDHashStringEntry : public PLDHashEntryHdr
+{
+public:
+ PLDHashStringEntry(const void* aKey) :
+ mKey(*NS_STATIC_CAST(const nsAString*, aKey)) { }
+ ~PLDHashStringEntry() { }
+
+ const void* GetKey() const {
+ return NS_STATIC_CAST(const nsAString*, &mKey);
+ }
+ static PLDHashNumber HashKey(const void* key) {
+ return HashString(*NS_STATIC_CAST(const nsAString*, key));
+ }
+ PRBool MatchEntry(const void* key) const {
+ return NS_STATIC_CAST(const nsAString*, key)->Equals(mKey);
+ }
+
+ const nsString mKey;
+};
+
+//
+// CString-key entry
+//
+class NS_COM PLDHashCStringEntry : public PLDHashEntryHdr
+{
+public:
+ PLDHashCStringEntry(const void* aKey) :
+ mKey(*NS_STATIC_CAST(const nsACString*, aKey)) { }
+ ~PLDHashCStringEntry() { }
+
+ const void* GetKey() const {
+ return NS_STATIC_CAST(const nsACString*, &mKey);
+ }
+ static PLDHashNumber HashKey(const void* key) {
+ return HashString(*NS_STATIC_CAST(const nsACString*, key));
+ }
+ PRBool MatchEntry(const void* key) const {
+ return NS_STATIC_CAST(const nsACString*, key)->Equals(mKey);
+ }
+
+ const nsCString mKey;
+};
+
+//
+// Int-key entry
+//
+class NS_COM PLDHashInt32Entry : public PLDHashEntryHdr
+{
+public:
+ PLDHashInt32Entry(const void* aKey) :
+ mKey(*(NS_STATIC_CAST(const PRInt32*, aKey))) { }
+ ~PLDHashInt32Entry() { }
+
+ const void* GetKey() const {
+ return NS_STATIC_CAST(const PRInt32*, &mKey);
+ }
+ static PLDHashNumber HashKey(const void* key) {
+ return *NS_STATIC_CAST(const PRInt32*, key);
+ }
+ PRBool MatchEntry(const void* key) const {
+ return *(NS_STATIC_CAST(const PRInt32*, key)) == mKey;
+ }
+
+ const PRInt32 mKey;
+};
+
+
+//
+// Void-key entry
+//
+class NS_COM PLDHashVoidEntry : public PLDHashEntryHdr
+{
+public:
+ PLDHashVoidEntry(const void* aKey) :
+ mKey(*(const void**)aKey) { }
+ ~PLDHashVoidEntry() { }
+
+ const void* GetKey() const {
+ return (const void**)&mKey;
+ }
+ static PLDHashNumber HashKey(const void* key) {
+ return PLDHashNumber(NS_PTR_TO_INT32(*(const void**)key)) >> 2;
+ }
+ PRBool MatchEntry(const void* key) const {
+ return *(const void**)key == mKey;
+ }
+
+ const void* mKey;
+};
+
+
+#define DHASH_EXPORT
+
+
+#endif