xpcom/ds/nsTHashtable.h

	nsTHashtable.h revision 677833bc953b6cb418c701facbdcf4aa18d6c44e
0N/A/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2362N/A/* ***** BEGIN LICENSE BLOCK *****
0N/A * Version: MPL 1.1/GPL 2.0/LGPL 2.1
0N/A *
0N/A * The contents of this file are subject to the Mozilla Public License Version
0N/A * 1.1 (the "License"); you may not use this file except in compliance with
2362N/A * the License. You may obtain a copy of the License at
0N/A * http://www.mozilla.org/MPL/
2362N/A *
0N/A * Software distributed under the License is distributed on an "AS IS" basis,
0N/A * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
0N/A * for the specific language governing rights and limitations under the
0N/A * License.
0N/A *
0N/A * The Original Code is C++ hashtable templates.
0N/A *
0N/A * The Initial Developer of the Original Code is
0N/A * Benjamin Smedberg.
0N/A * Portions created by the Initial Developer are Copyright (C) 2002
0N/A * the Initial Developer. All Rights Reserved.
2362N/A *
2362N/A * Contributor(s):
2362N/A *
0N/A * Alternatively, the contents of this file may be used under the terms of
0N/A * either the GNU General Public License Version 2 or later (the "GPL"), or
0N/A * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
0N/A * in which case the provisions of the GPL or the LGPL are applicable instead
0N/A * of those above. If you wish to allow use of your version of this file only
0N/A * under the terms of either the GPL or the LGPL, and not to allow others to
0N/A * use your version of this file under the terms of the MPL, indicate your
0N/A * decision by deleting the provisions above and replace them with the notice
0N/A * and other provisions required by the GPL or the LGPL. If you do not delete
0N/A * the provisions above, a recipient may use your version of this file under
0N/A * the terms of any one of the MPL, the GPL or the LGPL.
0N/A *
0N/A * ***** END LICENSE BLOCK ***** */
0N/A
0N/A#ifndef nsTHashtable_h__
0N/A#define nsTHashtable_h__
0N/A
0N/A#include "nscore.h"
0N/A#include "pldhash.h"
0N/A#include "nsDebug.h"
0N/A#include NEW_H
0N/A
0N/A// helper function for nsTHashtable::Clear()
0N/APR_EXTERN(PLDHashOperator) PR_CALLBACK
0N/APL_DHashStubEnumRemove(PLDHashTable    *table,
0N/A                       PLDHashEntryHdr *entry,
0N/A                       PRUint32         ordinal,
0N/A                       void            *userArg);
0N/A
0N/A
0N/A/**
0N/A * a base class for templated hashtables.
0N/A *
0N/A * Clients will rarely need to use this class directly. Check the derived
0N/A * classes first, to see if they will meet your needs.
0N/A *
0N/A * @param EntryType  the templated entry-type class that is managed by the
0N/A *   hashtable. <code>EntryType</code> must extend the following declaration,
0N/A *   and <strong>must not declare any virtual functions or derive from classes
0N/A *   with virtual functions.</strong>  Any vtable pointer would break the
0N/A *   PLDHashTable code.
0N/A *<pre>   class EntryType : public PLDHashEntryHdr
0N/A *   {
0N/A *   public: or friend nsTHashtable<EntryType>;
0N/A *     // KeyType is what we use when Get()ing or Put()ing this entry
0N/A *     // this should either be a simple datatype (PRUint32, nsISupports*) or
0N/A *     // a const reference (const nsAString&)
0N/A *     typedef something KeyType;
0N/A *     // KeyTypePointer is the pointer-version of KeyType, because pldhash.h
0N/A *     // requires keys to cast to <code>const void*</code>
0N/A *     typedef const something* KeyTypePointer;
0N/A *
0N/A *     EntryType(KeyTypePointer aKey);
0N/A *
0N/A *     // the copy constructor must be defined, even if AllowMemMove() == true
0N/A *     // or you will cause link errors!
0N/A *     EntryType(const EntryType& aEnt);
0N/A *
0N/A *     // the destructor must be defined... or you will cause link errors!
0N/A *     ~EntryType();
0N/A *
0N/A *     // return the key of this entry
0N/A *     const KeyTypePointer GetKeyPointer() const;
0N/A *
0N/A *     // KeyEquals(): does this entry match this key?
0N/A *     PRBool KeyEquals(KeyTypePointer aKey) const;
0N/A *
0N/A *     // KeyToPointer(): Convert KeyType to KeyTypePointer
0N/A *     static KeyTypePointer KeyToPointer(KeyType aKey);
0N/A *
0N/A *     // HashKey(): calculate the hash number
0N/A *     static PLDHashNumber HashKey(KeyTypePointer aKey);
0N/A *
0N/A *     // ALLOW_MEMMOVE can we move this class with memmove(), or do we have
0N/A *     // to use the copy constructor?
0N/A *     enum { ALLOW_MEMMOVE = PR_(TRUE or FALSE) };
0N/A *   }</pre>
0N/A *
0N/A * @see nsInterfaceHashtable
0N/A * @see nsDataHashtable
0N/A * @see nsClassHashtable
0N/A * @author "Benjamin Smedberg <bsmedberg@covad.net>"
0N/A */
0N/A
0N/Atemplate<class EntryType>
0N/Aclass nsTHashtable
0N/A{
0N/Apublic:
0N/A  /**
0N/A   * A dummy constructor; you must call Init() before using this class.
0N/A   */
0N/A  nsTHashtable();
0N/A
0N/A  /**
0N/A   * destructor, cleans up and deallocates
0N/A   */
0N/A  ~nsTHashtable();
0N/A
0N/A  /**
0N/A   * Initialize the table.  This function must be called before any other
0N/A   * class operations.  This can fail due to OOM conditions.
0N/A   * @param initSize the initial number of buckets in the hashtable, default 16
0N/A   * @return PR_TRUE if the class was initialized properly.
0N/A   */
0N/A  PRBool Init(PRUint32 initSize = PL_DHASH_MIN_SIZE);
0N/A
0N/A  /**
0N/A   * Check whether the table has been initialized. This can be useful for static hashtables.
0N/A   * @return the initialization state of the class.
0N/A   */
0N/A  PRBool IsInitialized() const { return mTable.entrySize; }
0N/A
0N/A  /**
0N/A   * KeyType is typedef'ed for ease of use.
0N/A   */
0N/A  typedef typename EntryType::KeyType KeyType;
0N/A
0N/A  /**
0N/A   * KeyTypePointer is typedef'ed for ease of use.
0N/A   */
0N/A  typedef typename EntryType::KeyTypePointer KeyTypePointer;
0N/A
0N/A  /**
0N/A   * Return the number of entries in the table.
0N/A   * @return    number of entries
0N/A   */
0N/A  PRUint32 Count() const { return mTable.entryCount; }
0N/A
0N/A  /**
0N/A   * Get the entry associated with a key.
0N/A   * @param     aKey the key to retrieve
0N/A   * @return    pointer to the entry class, if the key exists; nsnull if the
0N/A   *            key doesn't exist
0N/A   */
0N/A  EntryType* GetEntry(KeyType aKey) const
0N/A  {
0N/A    NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
0N/A
0N/A    EntryType* entry =
0N/A      NS_REINTERPRET_CAST(EntryType*,
0N/A                          PL_DHashTableOperate(
0N/A                            NS_CONST_CAST(PLDHashTable*,&mTable),
0N/A                            EntryType::KeyToPointer(aKey),
0N/A                            PL_DHASH_LOOKUP));
0N/A    return PL_DHASH_ENTRY_IS_BUSY(entry) ? entry : nsnull;
0N/A  }
0N/A
0N/A  /**
0N/A   * Get the entry associated with a key, or create a new entry,
0N/A   * @param     aKey the key to retrieve
0N/A   * @return    pointer to the entry class retreived; nsnull only if memory
0N/A                can't be allocated
0N/A   */
0N/A  EntryType* PutEntry(KeyType aKey)
0N/A  {
0N/A    NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
0N/A
0N/A    return NS_STATIC_CAST(EntryType*,
0N/A                          PL_DHashTableOperate(
0N/A                            &mTable,
0N/A                            EntryType::KeyToPointer(aKey),
0N/A                            PL_DHASH_ADD));
0N/A  }
0N/A
0N/A  /**
0N/A   * Remove the entry associated with a key.
0N/A   * @param     aKey of the entry to remove
0N/A   */
0N/A  void RemoveEntry(KeyType aKey)
0N/A  {
0N/A    NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
0N/A
0N/A    PL_DHashTableOperate(&mTable,
0N/A                         EntryType::KeyToPointer(aKey),
0N/A                         PL_DHASH_REMOVE);
0N/A  }
0N/A
0N/A  /**
0N/A   * Remove the entry associated with a key, but don't resize the hashtable.
0N/A   * This is a low-level method, and is not recommended unless you know what
0N/A   * you're doing and you need the extra performance. This method can be used
   * during enumeration, while RemoveEntry() cannot.
   * @param aEntry   the entry-pointer to remove (obtained from GetEntry or
   *                 the enumerator
   */
  void RawRemoveEntry(EntryType* aEntry)
  {
    PL_DHashTableRawRemove(&mTable, aEntry);
  }

  /**
   * client must provide an <code>Enumerator</code> function for
   *   EnumerateEntries
   * @param     aEntry the entry being enumerated
   * @param     userArg passed unchanged from <code>EnumerateEntries</code>
   * @return    combination of flags
   *            @link PLDHashOperator::PL_DHASH_NEXT PL_DHASH_NEXT @endlink ,
   *            @link PLDHashOperator::PL_DHASH_STOP PL_DHASH_STOP @endlink ,
   *            @link PLDHashOperator::PL_DHASH_REMOVE PL_DHASH_REMOVE @endlink
   */
  typedef PLDHashOperator (*PR_CALLBACK Enumerator)(EntryType* aEntry, void* userArg);

  /**
   * Enumerate all the entries of the function.
   * @param     enumFunc the <code>Enumerator</code> function to call
   * @param     userArg a pointer to pass to the
   *            <code>Enumerator</code> function
   * @return    the number of entries actually enumerated
   */
  PRUint32 EnumerateEntries(Enumerator enumFunc, void* userArg)
  {
    NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");

    s_EnumArgs args = { enumFunc, userArg };
    return PL_DHashTableEnumerate(&mTable, s_EnumStub, &args);
  }

  /**
   * remove all entries, return hashtable to "pristine" state ;)
   */
  void Clear()
  {
    NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");

    PL_DHashTableEnumerate(&mTable, PL_DHashStubEnumRemove, nsnull);
  }

protected:
  PLDHashTable mTable;

  static const void* PR_CALLBACK s_GetKey(PLDHashTable    *table,
                                          PLDHashEntryHdr *entry);

  static PLDHashNumber PR_CALLBACK s_HashKey(PLDHashTable *table,
                                             const void   *key);

  static PRBool PR_CALLBACK s_MatchEntry(PLDHashTable           *table,
                                         const PLDHashEntryHdr  *entry,
                                         const void             *key);

  static void PR_CALLBACK s_CopyEntry(PLDHashTable          *table,
                                      const PLDHashEntryHdr *from,
                                      PLDHashEntryHdr       *to);

  static void PR_CALLBACK s_ClearEntry(PLDHashTable *table,
                                       PLDHashEntryHdr *entry);

  static PRBool PR_CALLBACK s_InitEntry(PLDHashTable     *table,
                                        PLDHashEntryHdr  *entry,
                                        const void       *key);

  /**
   * passed internally during enumeration.  Allocated on the stack.
   *
   * @param userFunc the Enumerator function passed to
   *   EnumerateEntries by the client
   * @param userArg the userArg passed unaltered
   */
  struct s_EnumArgs
  {
    Enumerator userFunc;
    void* userArg;
  };

  static PLDHashOperator PR_CALLBACK s_EnumStub(PLDHashTable    *table,
                                                PLDHashEntryHdr *entry,
                                                PRUint32         number,
                                                void            *arg);
private:
  // copy constructor, not implemented
  nsTHashtable(nsTHashtable<EntryType>& toCopy);

  // assignment operator, not implemented
  nsTHashtable<EntryType>& operator= (nsTHashtable<EntryType>& toEqual);
};

//
// template definitions
//

template<class EntryType>
nsTHashtable<EntryType>::nsTHashtable()
{
  // entrySize is our "I'm initialized" indicator
  mTable.entrySize = 0;
}

template<class EntryType>
nsTHashtable<EntryType>::~nsTHashtable()
{
  if (mTable.entrySize)
    PL_DHashTableFinish(&mTable);
}

template<class EntryType>
PRBool
nsTHashtable<EntryType>::Init(PRUint32 initSize)
{
  if (mTable.entrySize)
  {
    NS_ERROR("nsTHashtable::Init() should not be called twice.");
    return PR_TRUE;
  }

  static PLDHashTableOps sOps =
  {
    ::PL_DHashAllocTable,
    ::PL_DHashFreeTable,
    s_GetKey,
    s_HashKey,
    s_MatchEntry,
    ::PL_DHashMoveEntryStub,
    s_ClearEntry,
    ::PL_DHashFinalizeStub,
    s_InitEntry
  };

  if (!EntryType::ALLOW_MEMMOVE)
  {
    sOps.moveEntry = s_CopyEntry;
  }

  if (!PL_DHashTableInit(&mTable, &sOps, nsnull, sizeof(EntryType), initSize))
  {
    // if failed, reset "flag"
    mTable.entrySize = 0;
    return PR_FALSE;
  }

  return PR_TRUE;
}

// static definitions

template<class EntryType>
const void*
nsTHashtable<EntryType>::s_GetKey(PLDHashTable    *table,
                                  PLDHashEntryHdr *entry)
{
  return ((EntryType*) entry)->GetKeyPointer();
}

template<class EntryType>
PLDHashNumber
nsTHashtable<EntryType>::s_HashKey(PLDHashTable  *table,
                                   const void    *key)
{
  return EntryType::HashKey(NS_REINTERPRET_CAST(const KeyTypePointer, key));
}

template<class EntryType>
PRBool
nsTHashtable<EntryType>::s_MatchEntry(PLDHashTable          *table,
                                      const PLDHashEntryHdr *entry,
                                      const void            *key)
{
  return ((const EntryType*) entry)->KeyEquals(
    NS_REINTERPRET_CAST(const KeyTypePointer, key));
}

template<class EntryType>
void
nsTHashtable<EntryType>::s_CopyEntry(PLDHashTable          *table,
                                     const PLDHashEntryHdr *from,
                                     PLDHashEntryHdr       *to)
{
  EntryType* fromEntry =
    NS_CONST_CAST(EntryType*, NS_REINTERPRET_CAST(const EntryType*, from));

  new(to) EntryType(*fromEntry);

  fromEntry->~EntryType();
}

template<class EntryType>
void
nsTHashtable<EntryType>::s_ClearEntry(PLDHashTable    *table,
                                      PLDHashEntryHdr *entry)
{
  NS_REINTERPRET_CAST(EntryType*,entry)->~EntryType();
}

template<class EntryType>
PRBool
nsTHashtable<EntryType>::s_InitEntry(PLDHashTable    *table,
                                     PLDHashEntryHdr *entry,
                                     const void      *key)
{
  new(entry) EntryType(NS_REINTERPRET_CAST(KeyTypePointer,key));
  return PR_TRUE;
}

template<class EntryType>
PLDHashOperator
nsTHashtable<EntryType>::s_EnumStub(PLDHashTable    *table,
                                    PLDHashEntryHdr *entry,
                                    PRUint32         number,
                                    void            *arg)
{
  // dereferences the function-pointer to the user's enumeration function
  return (* NS_REINTERPRET_CAST(s_EnumArgs*,arg)->userFunc)(
    NS_REINTERPRET_CAST(EntryType*,entry),
    NS_REINTERPRET_CAST(s_EnumArgs*,arg)->userArg);
}

#endif // nsTHashtable_h__