michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef nsTHashtable_h__
michael@0: #define nsTHashtable_h__
michael@0: 
michael@0: #include "nscore.h"
michael@0: #include "pldhash.h"
michael@0: #include "nsDebug.h"
michael@0: #include "mozilla/MemoryChecking.h"
michael@0: #include "mozilla/MemoryReporting.h"
michael@0: #include "mozilla/Move.h"
michael@0: #include "mozilla/fallible.h"
michael@0: #include "mozilla/PodOperations.h"
michael@0: 
michael@0: #include <new>
michael@0: 
michael@0: // helper function for nsTHashtable::Clear()
michael@0: NS_COM_GLUE PLDHashOperator
michael@0: PL_DHashStubEnumRemove(PLDHashTable    *table,
michael@0:                        PLDHashEntryHdr *entry,
michael@0:                        uint32_t         ordinal,
michael@0:                        void            *userArg);
michael@0: 
michael@0: 
michael@0: /**
michael@0:  * a base class for templated hashtables.
michael@0:  *
michael@0:  * Clients will rarely need to use this class directly. Check the derived
michael@0:  * classes first, to see if they will meet your needs.
michael@0:  *
michael@0:  * @param EntryType  the templated entry-type class that is managed by the
michael@0:  *   hashtable. <code>EntryType</code> must extend the following declaration,
michael@0:  *   and <strong>must not declare any virtual functions or derive from classes
michael@0:  *   with virtual functions.</strong>  Any vtable pointer would break the
michael@0:  *   PLDHashTable code.
michael@0:  *<pre>   class EntryType : public PLDHashEntryHdr
michael@0:  *   {
michael@0:  *   public: or friend nsTHashtable<EntryType>;
michael@0:  *     // KeyType is what we use when Get()ing or Put()ing this entry
michael@0:  *     // this should either be a simple datatype (uint32_t, nsISupports*) or
michael@0:  *     // a const reference (const nsAString&)
michael@0:  *     typedef something KeyType;
michael@0:  *     // KeyTypePointer is the pointer-version of KeyType, because pldhash.h
michael@0:  *     // requires keys to cast to <code>const void*</code>
michael@0:  *     typedef const something* KeyTypePointer;
michael@0:  *
michael@0:  *     EntryType(KeyTypePointer aKey);
michael@0:  *
michael@0:  *     // A copy or C++11 Move constructor must be defined, even if
michael@0:  *     // AllowMemMove() == true, otherwise you will cause link errors.
michael@0:  *     EntryType(const EntryType& aEnt);  // Either this...
michael@0:  *     EntryType(EntryType&& aEnt);       // ...or this
michael@0:  *
michael@0:  *     // the destructor must be defined... or you will cause link errors!
michael@0:  *     ~EntryType();
michael@0:  *
michael@0:  *     // KeyEquals(): does this entry match this key?
michael@0:  *     bool KeyEquals(KeyTypePointer aKey) const;
michael@0:  *
michael@0:  *     // KeyToPointer(): Convert KeyType to KeyTypePointer
michael@0:  *     static KeyTypePointer KeyToPointer(KeyType aKey);
michael@0:  *
michael@0:  *     // HashKey(): calculate the hash number
michael@0:  *     static PLDHashNumber HashKey(KeyTypePointer aKey);
michael@0:  *
michael@0:  *     // ALLOW_MEMMOVE can we move this class with memmove(), or do we have
michael@0:  *     // to use the copy constructor?
michael@0:  *     enum { ALLOW_MEMMOVE = true/false };
michael@0:  *   }</pre>
michael@0:  *
michael@0:  * @see nsInterfaceHashtable
michael@0:  * @see nsDataHashtable
michael@0:  * @see nsClassHashtable
michael@0:  * @author "Benjamin Smedberg <bsmedberg@covad.net>"
michael@0:  */
michael@0: 
michael@0: template<class EntryType>
michael@0: class nsTHashtable
michael@0: {
michael@0:   typedef mozilla::fallible_t fallible_t;
michael@0: 
michael@0: public:
michael@0:   // Separate constructors instead of default aInitSize parameter since
michael@0:   // otherwise the default no-arg constructor isn't found.
michael@0:   nsTHashtable()
michael@0:   {
michael@0:     Init(PL_DHASH_MIN_SIZE);
michael@0:   }
michael@0:   explicit nsTHashtable(uint32_t aInitSize)
michael@0:   {
michael@0:     Init(aInitSize);
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * destructor, cleans up and deallocates
michael@0:    */
michael@0:   ~nsTHashtable();
michael@0: 
michael@0:   nsTHashtable(nsTHashtable<EntryType>&& aOther);
michael@0: 
michael@0:   /**
michael@0:    * Return the generation number for the table. This increments whenever
michael@0:    * the table data items are moved.
michael@0:    */
michael@0:   uint32_t GetGeneration() const { return mTable.generation; }
michael@0: 
michael@0:   /**
michael@0:    * KeyType is typedef'ed for ease of use.
michael@0:    */
michael@0:   typedef typename EntryType::KeyType KeyType;
michael@0: 
michael@0:   /**
michael@0:    * KeyTypePointer is typedef'ed for ease of use.
michael@0:    */
michael@0:   typedef typename EntryType::KeyTypePointer KeyTypePointer;
michael@0: 
michael@0:   /**
michael@0:    * Return the number of entries in the table.
michael@0:    * @return    number of entries
michael@0:    */
michael@0:   uint32_t Count() const { return mTable.entryCount; }
michael@0: 
michael@0:   /**
michael@0:    * Get the entry associated with a key.
michael@0:    * @param     aKey the key to retrieve
michael@0:    * @return    pointer to the entry class, if the key exists; nullptr if the
michael@0:    *            key doesn't exist
michael@0:    */
michael@0:   EntryType* GetEntry(KeyType aKey) const
michael@0:   {
michael@0:     NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
michael@0:   
michael@0:     EntryType* entry =
michael@0:       reinterpret_cast<EntryType*>
michael@0:                       (PL_DHashTableOperate(
michael@0:                             const_cast<PLDHashTable*>(&mTable),
michael@0:                             EntryType::KeyToPointer(aKey),
michael@0:                             PL_DHASH_LOOKUP));
michael@0:     return PL_DHASH_ENTRY_IS_BUSY(entry) ? entry : nullptr;
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Return true if an entry for the given key exists, false otherwise.
michael@0:    * @param     aKey the key to retrieve
michael@0:    * @return    true if the key exists, false if the key doesn't exist
michael@0:    */
michael@0:   bool Contains(KeyType aKey) const
michael@0:   {
michael@0:     return !!GetEntry(aKey);
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Get the entry associated with a key, or create a new entry,
michael@0:    * @param     aKey the key to retrieve
michael@0:    * @return    pointer to the entry class retreived; nullptr only if memory
michael@0:                 can't be allocated
michael@0:    */
michael@0:   EntryType* PutEntry(KeyType aKey)
michael@0:   {
michael@0:     EntryType* e = PutEntry(aKey, fallible_t());
michael@0:     if (!e)
michael@0:       NS_ABORT_OOM(mTable.entrySize * mTable.entryCount);
michael@0:     return e;
michael@0:   }
michael@0: 
michael@0:   EntryType* PutEntry(KeyType aKey, const fallible_t&) NS_WARN_UNUSED_RESULT
michael@0:   {
michael@0:     NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
michael@0: 
michael@0:     return static_cast<EntryType*>
michael@0:                       (PL_DHashTableOperate(
michael@0:                             &mTable,
michael@0:                             EntryType::KeyToPointer(aKey),
michael@0:                             PL_DHASH_ADD));
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Remove the entry associated with a key.
michael@0:    * @param     aKey of the entry to remove
michael@0:    */
michael@0:   void RemoveEntry(KeyType aKey)
michael@0:   {
michael@0:     NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
michael@0: 
michael@0:     PL_DHashTableOperate(&mTable,
michael@0:                          EntryType::KeyToPointer(aKey),
michael@0:                          PL_DHASH_REMOVE);
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Remove the entry associated with a key, but don't resize the hashtable.
michael@0:    * This is a low-level method, and is not recommended unless you know what
michael@0:    * you're doing and you need the extra performance. This method can be used
michael@0:    * during enumeration, while RemoveEntry() cannot.
michael@0:    * @param aEntry   the entry-pointer to remove (obtained from GetEntry or
michael@0:    *                 the enumerator
michael@0:    */
michael@0:   void RawRemoveEntry(EntryType* aEntry)
michael@0:   {
michael@0:     PL_DHashTableRawRemove(&mTable, aEntry);
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * client must provide an <code>Enumerator</code> function for
michael@0:    *   EnumerateEntries
michael@0:    * @param     aEntry the entry being enumerated
michael@0:    * @param     userArg passed unchanged from <code>EnumerateEntries</code>
michael@0:    * @return    combination of flags
michael@0:    *            @link PLDHashOperator::PL_DHASH_NEXT PL_DHASH_NEXT @endlink ,
michael@0:    *            @link PLDHashOperator::PL_DHASH_STOP PL_DHASH_STOP @endlink ,
michael@0:    *            @link PLDHashOperator::PL_DHASH_REMOVE PL_DHASH_REMOVE @endlink
michael@0:    */
michael@0:   typedef PLDHashOperator (* Enumerator)(EntryType* aEntry, void* userArg);
michael@0: 
michael@0:   /**
michael@0:    * Enumerate all the entries of the function.
michael@0:    * @param     enumFunc the <code>Enumerator</code> function to call
michael@0:    * @param     userArg a pointer to pass to the
michael@0:    *            <code>Enumerator</code> function
michael@0:    * @return    the number of entries actually enumerated
michael@0:    */
michael@0:   uint32_t EnumerateEntries(Enumerator enumFunc, void* userArg)
michael@0:   {
michael@0:     NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
michael@0:     
michael@0:     s_EnumArgs args = { enumFunc, userArg };
michael@0:     return PL_DHashTableEnumerate(&mTable, s_EnumStub, &args);
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * remove all entries, return hashtable to "pristine" state ;)
michael@0:    */
michael@0:   void Clear()
michael@0:   {
michael@0:     NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
michael@0: 
michael@0:     PL_DHashTableEnumerate(&mTable, PL_DHashStubEnumRemove, nullptr);
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * client must provide a <code>SizeOfEntryExcludingThisFun</code> function for
michael@0:    *   SizeOfExcludingThis.
michael@0:    * @param     aEntry the entry being enumerated
michael@0:    * @param     mallocSizeOf the function used to measure heap-allocated blocks
michael@0:    * @param     arg passed unchanged from <code>SizeOf{In,Ex}cludingThis</code>
michael@0:    * @return    summed size of the things pointed to by the entries
michael@0:    */
michael@0:   typedef size_t (* SizeOfEntryExcludingThisFun)(EntryType* aEntry,
michael@0:                                                  mozilla::MallocSizeOf mallocSizeOf,
michael@0:                                                  void *arg);
michael@0: 
michael@0:   /**
michael@0:    * Measure the size of the table's entry storage, and if
michael@0:    * |sizeOfEntryExcludingThis| is non-nullptr, measure the size of things
michael@0:    * pointed to by entries.
michael@0:    * 
michael@0:    * @param     sizeOfEntryExcludingThis the
michael@0:    *            <code>SizeOfEntryExcludingThisFun</code> function to call
michael@0:    * @param     mallocSizeOf the function used to measure heap-allocated blocks
michael@0:    * @param     userArg a pointer to pass to the
michael@0:    *            <code>SizeOfEntryExcludingThisFun</code> function
michael@0:    * @return    the summed size of all the entries
michael@0:    */
michael@0:   size_t SizeOfExcludingThis(SizeOfEntryExcludingThisFun sizeOfEntryExcludingThis,
michael@0:                              mozilla::MallocSizeOf mallocSizeOf,
michael@0:                              void *userArg = nullptr) const
michael@0:   {
michael@0:     if (sizeOfEntryExcludingThis) {
michael@0:       s_SizeOfArgs args = { sizeOfEntryExcludingThis, userArg };
michael@0:       return PL_DHashTableSizeOfExcludingThis(&mTable, s_SizeOfStub, mallocSizeOf, &args);
michael@0:     }
michael@0:     return PL_DHashTableSizeOfExcludingThis(&mTable, nullptr, mallocSizeOf);
michael@0:   }
michael@0: 
michael@0: #ifdef DEBUG
michael@0:   /**
michael@0:    * Mark the table as constant after initialization.
michael@0:    *
michael@0:    * This will prevent assertions when a read-only hash is accessed on multiple
michael@0:    * threads without synchronization.
michael@0:    */
michael@0:   void MarkImmutable()
michael@0:   {
michael@0:     NS_ASSERTION(mTable.entrySize, "nsTHashtable was not initialized properly.");
michael@0: 
michael@0:     PL_DHashMarkTableImmutable(&mTable);
michael@0:   }
michael@0: #endif
michael@0: 
michael@0: protected:
michael@0:   PLDHashTable mTable;
michael@0: 
michael@0:   static const void* s_GetKey(PLDHashTable    *table,
michael@0:                               PLDHashEntryHdr *entry);
michael@0: 
michael@0:   static PLDHashNumber s_HashKey(PLDHashTable *table,
michael@0:                                  const void   *key);
michael@0: 
michael@0:   static bool s_MatchEntry(PLDHashTable           *table,
michael@0:                              const PLDHashEntryHdr  *entry,
michael@0:                              const void             *key);
michael@0:   
michael@0:   static void s_CopyEntry(PLDHashTable          *table,
michael@0:                           const PLDHashEntryHdr *from,
michael@0:                           PLDHashEntryHdr       *to);
michael@0:   
michael@0:   static void s_ClearEntry(PLDHashTable *table,
michael@0:                            PLDHashEntryHdr *entry);
michael@0: 
michael@0:   static bool s_InitEntry(PLDHashTable     *table,
michael@0:                             PLDHashEntryHdr  *entry,
michael@0:                             const void       *key);
michael@0: 
michael@0:   /**
michael@0:    * passed internally during enumeration.  Allocated on the stack.
michael@0:    *
michael@0:    * @param userFunc the Enumerator function passed to
michael@0:    *   EnumerateEntries by the client
michael@0:    * @param userArg the userArg passed unaltered
michael@0:    */
michael@0:   struct s_EnumArgs
michael@0:   {
michael@0:     Enumerator userFunc;
michael@0:     void* userArg;
michael@0:   };
michael@0:   
michael@0:   static PLDHashOperator s_EnumStub(PLDHashTable    *table,
michael@0:                                     PLDHashEntryHdr *entry,
michael@0:                                     uint32_t         number,
michael@0:                                     void            *arg);
michael@0: 
michael@0:   /**
michael@0:    * passed internally during sizeOf counting.  Allocated on the stack.
michael@0:    *
michael@0:    * @param userFunc the SizeOfEntryExcludingThisFun passed to
michael@0:    *                 SizeOf{In,Ex}cludingThis by the client
michael@0:    * @param userArg the userArg passed unaltered
michael@0:    */
michael@0:   struct s_SizeOfArgs
michael@0:   {
michael@0:     SizeOfEntryExcludingThisFun userFunc;
michael@0:     void* userArg;
michael@0:   };
michael@0:   
michael@0:   static size_t s_SizeOfStub(PLDHashEntryHdr *entry,
michael@0:                              mozilla::MallocSizeOf mallocSizeOf,
michael@0:                              void *arg);
michael@0: 
michael@0: private:
michael@0:   // copy constructor, not implemented
michael@0:   nsTHashtable(nsTHashtable<EntryType>& toCopy) MOZ_DELETE;
michael@0: 
michael@0:   /**
michael@0:    * Initialize the table.
michael@0:    * @param initSize the initial number of buckets in the hashtable
michael@0:    */
michael@0:   void Init(uint32_t aInitSize);
michael@0: 
michael@0:   // assignment operator, not implemented
michael@0:   nsTHashtable<EntryType>& operator= (nsTHashtable<EntryType>& toEqual) MOZ_DELETE;
michael@0: };
michael@0: 
michael@0: //
michael@0: // template definitions
michael@0: //
michael@0: 
michael@0: template<class EntryType>
michael@0: nsTHashtable<EntryType>::nsTHashtable(
michael@0:   nsTHashtable<EntryType>&& aOther)
michael@0:   : mTable(mozilla::Move(aOther.mTable))
michael@0: {
michael@0:   // aOther shouldn't touch mTable after this, because we've stolen the table's
michael@0:   // pointers but not overwitten them.
michael@0:   MOZ_MAKE_MEM_UNDEFINED(&aOther.mTable, sizeof(aOther.mTable));
michael@0: 
michael@0:   // Indicate that aOther is not initialized.  This will make its destructor a
michael@0:   // nop, which is what we want.
michael@0:   aOther.mTable.entrySize = 0;
michael@0: }
michael@0: 
michael@0: template<class EntryType>
michael@0: nsTHashtable<EntryType>::~nsTHashtable()
michael@0: {
michael@0:   if (mTable.entrySize)
michael@0:     PL_DHashTableFinish(&mTable);
michael@0: }
michael@0: 
michael@0: template<class EntryType>
michael@0: void
michael@0: nsTHashtable<EntryType>::Init(uint32_t aInitSize)
michael@0: {
michael@0:   static const PLDHashTableOps sOps =
michael@0:   {
michael@0:     ::PL_DHashAllocTable,
michael@0:     ::PL_DHashFreeTable,
michael@0:     s_HashKey,
michael@0:     s_MatchEntry,
michael@0:     EntryType::ALLOW_MEMMOVE ? ::PL_DHashMoveEntryStub : s_CopyEntry,
michael@0:     s_ClearEntry,
michael@0:     ::PL_DHashFinalizeStub,
michael@0:     s_InitEntry
michael@0:   };
michael@0: 
michael@0:   PL_DHashTableInit(&mTable, &sOps, nullptr, sizeof(EntryType), aInitSize);
michael@0: }
michael@0: 
michael@0: // static definitions
michael@0: 
michael@0: template<class EntryType>
michael@0: PLDHashNumber
michael@0: nsTHashtable<EntryType>::s_HashKey(PLDHashTable  *table,
michael@0:                                    const void    *key)
michael@0: {
michael@0:   return EntryType::HashKey(reinterpret_cast<const KeyTypePointer>(key));
michael@0: }
michael@0: 
michael@0: template<class EntryType>
michael@0: bool
michael@0: nsTHashtable<EntryType>::s_MatchEntry(PLDHashTable          *table,
michael@0:                                       const PLDHashEntryHdr *entry,
michael@0:                                       const void            *key)
michael@0: {
michael@0:   return ((const EntryType*) entry)->KeyEquals(
michael@0:     reinterpret_cast<const KeyTypePointer>(key));
michael@0: }
michael@0: 
michael@0: template<class EntryType>
michael@0: void
michael@0: nsTHashtable<EntryType>::s_CopyEntry(PLDHashTable          *table,
michael@0:                                      const PLDHashEntryHdr *from,
michael@0:                                      PLDHashEntryHdr       *to)
michael@0: {
michael@0:   EntryType* fromEntry =
michael@0:     const_cast<EntryType*>(reinterpret_cast<const EntryType*>(from));
michael@0: 
michael@0:   new(to) EntryType(mozilla::Move(*fromEntry));
michael@0: 
michael@0:   fromEntry->~EntryType();
michael@0: }
michael@0: 
michael@0: template<class EntryType>
michael@0: void
michael@0: nsTHashtable<EntryType>::s_ClearEntry(PLDHashTable    *table,
michael@0:                                       PLDHashEntryHdr *entry)
michael@0: {
michael@0:   reinterpret_cast<EntryType*>(entry)->~EntryType();
michael@0: }
michael@0: 
michael@0: template<class EntryType>
michael@0: bool
michael@0: nsTHashtable<EntryType>::s_InitEntry(PLDHashTable    *table,
michael@0:                                      PLDHashEntryHdr *entry,
michael@0:                                      const void      *key)
michael@0: {
michael@0:   new(entry) EntryType(reinterpret_cast<KeyTypePointer>(key));
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: template<class EntryType>
michael@0: PLDHashOperator
michael@0: nsTHashtable<EntryType>::s_EnumStub(PLDHashTable    *table,
michael@0:                                     PLDHashEntryHdr *entry,
michael@0:                                     uint32_t         number,
michael@0:                                     void            *arg)
michael@0: {
michael@0:   // dereferences the function-pointer to the user's enumeration function
michael@0:   return (* reinterpret_cast<s_EnumArgs*>(arg)->userFunc)(
michael@0:     reinterpret_cast<EntryType*>(entry),
michael@0:     reinterpret_cast<s_EnumArgs*>(arg)->userArg);
michael@0: }
michael@0: 
michael@0: template<class EntryType>
michael@0: size_t
michael@0: nsTHashtable<EntryType>::s_SizeOfStub(PLDHashEntryHdr *entry,
michael@0:                                       mozilla::MallocSizeOf mallocSizeOf,
michael@0:                                       void *arg)
michael@0: {
michael@0:   // dereferences the function-pointer to the user's enumeration function
michael@0:   return (* reinterpret_cast<s_SizeOfArgs*>(arg)->userFunc)(
michael@0:     reinterpret_cast<EntryType*>(entry),
michael@0:     mallocSizeOf,
michael@0:     reinterpret_cast<s_SizeOfArgs*>(arg)->userArg);
michael@0: }
michael@0: 
michael@0: class nsCycleCollectionTraversalCallback;
michael@0: 
michael@0: struct MOZ_STACK_CLASS nsTHashtableCCTraversalData
michael@0: {
michael@0:   nsTHashtableCCTraversalData(nsCycleCollectionTraversalCallback& aCallback,
michael@0:                               const char* aName,
michael@0:                               uint32_t aFlags)
michael@0:   : mCallback(aCallback),
michael@0:     mName(aName),
michael@0:     mFlags(aFlags)
michael@0:   {
michael@0:   }
michael@0: 
michael@0:   nsCycleCollectionTraversalCallback& mCallback;
michael@0:   const char* mName;
michael@0:   uint32_t mFlags;
michael@0: };
michael@0: 
michael@0: template <class EntryType>
michael@0: PLDHashOperator
michael@0: ImplCycleCollectionTraverse_EnumFunc(EntryType *aEntry,
michael@0:                                      void* aUserData)
michael@0: {
michael@0:   auto userData = static_cast<nsTHashtableCCTraversalData*>(aUserData);
michael@0: 
michael@0:   ImplCycleCollectionTraverse(userData->mCallback,
michael@0:                               *aEntry,
michael@0:                               userData->mName,
michael@0:                               userData->mFlags);
michael@0:   return PL_DHASH_NEXT;
michael@0: }
michael@0: 
michael@0: template <class EntryType>
michael@0: inline void
michael@0: ImplCycleCollectionUnlink(nsTHashtable<EntryType>& aField)
michael@0: {
michael@0:   aField.Clear();
michael@0: }
michael@0: 
michael@0: template <class EntryType>
michael@0: inline void
michael@0: ImplCycleCollectionTraverse(nsCycleCollectionTraversalCallback& aCallback,
michael@0:                             nsTHashtable<EntryType>& aField,
michael@0:                             const char* aName,
michael@0:                             uint32_t aFlags = 0)
michael@0: {
michael@0:   nsTHashtableCCTraversalData userData(aCallback, aName, aFlags);
michael@0: 
michael@0:   aField.EnumerateEntries(ImplCycleCollectionTraverse_EnumFunc<EntryType>,
michael@0:                           &userData);
michael@0: }
michael@0: 
michael@0: #endif // nsTHashtable_h__