Changeset 11739 in webkit for trunk/JavaScriptCore/kxmlcore/HashSet.h

Timestamp:

Dec 22, 2005, 5:52:43 PM (19 years ago)

Author:

mjs

Message:

JavaScriptCore:

Reviewed by Darin.

• Make HashMap/HashSet support non-POD types ​http://bugzilla.opendarwin.org/show_bug.cgi?id=5332

The changes for support are relatively simple, but I also made extensive changes to
avoid copying, so that there isn't refcount thrash when you put RefPtrs into a HashMap.

• kxmlcore/HashTable.h: (KXMLCore::swap): specialize swap for pairs, to swap elements individually, so that excess copies can be avoided. (KXMLCore::Mover::move): Template function to either copy or swap, used when transferring elements from old table to new. (KXMLCore::IdentityHashTranslator::hash): The old "converting lookup" templates that took two or three function parameters now take a class parameter, this is the class used to do a normal lookup. (KXMLCore::IdentityHashTranslator::equal): Ditto. (KXMLCore::IdentityHashTranslator::translate): Ditto. Translate now takes a reference to write into instead of returning a value to avoid redundant copies. (KXMLCore::HashTable::~HashTable): Use deallocateTable instead of freeing directly. (KXMLCore::HashTable::insert): Based on HashTranslator now instead of separate functions. Added a FIXME about a remaining rare excess copy. (KXMLCore::HashTable::isEmptyBucket): Use KeyTraits directly instead of unwrapping the key from Traits, to avoid creating and destroying pair, which copies. (KXMLCore::HashTable::isDeletedBucket): ditto (KXMLCore::HashTable::lookup): Use HashTranslator now instead of separate functions. (KXMLCore::HashTable::initializeBucket): Renamed from emptyBucket. Use placement new to work right for non-POD types. (KXMLCore::HashTable::deleteBucket): Use assignDeleted to avoid excess copies. (KXMLCore::HashTable::reinsert): use Mover template to copy or swap as appropriate (KXMLCore::HashTable::allocateTable): Initialize every bucket if calloc won't do. (KXMLCore::HashTable::deallocateTable): Destruct every bucket if needed. (KXMLCore::HashTable::rehash): Avoid copy before reinserting, so that swap can do its magic. (KXMLCore::HashTable::clear): use deallocateTable instead of freeing directly. (KXMLCore::HashTable::HashTable): be more dumb when copying to ensure that non-POD types work right
• kxmlcore/HashFunctions.h: (KXMLCore::PointerHash): Specialize PointerHash for RefPtr
• kxmlcore/HashMap.h: (KXMLCore::extractFirst): Return a reference not a full object to avoid copies. (KXMLCore::HashMapTranslator::hash): Use a special translator for insertion to defer making the pair as long as possible, thus avoiding needless copies. (KXMLCore::HashMapTranslator::equal): ditto (KXMLCore::HashMapTranslator::translate): ditto (KXMLCore::::inlineAdd): Shared by set and add to insert using HashMapTranslator (KXMLCore::::set): Use inlineAdd (KXMLCore::::add): Use inlineAdd
• kxmlcore/HashMapPtrSpec.h: (KXMLCore::): Pass KeyTraits along
• kxmlcore/HashSet.h: (KXMLCore::identityExtract): Return a reference not a full object to avoid copies. (KXMLCore::HashSetTranslatorAdapter::hash): Redo adapter stuff to work with the new HashTranslator approach. (KXMLCore::HashSetTranslatorAdapter::equal): ditto (KXMLCore::HashSetTranslatorAdapter::translate): ditto (KXMLCore::::insert): ditto
• kxmlcore/HashTraits.h: (KXMLCore::GenericHashTraits): This is intended be used as a base class for customized traits: sensible defaults. (KXMLCore::): Use it a bunch (KXMLCore::assignDeleted): template function to allow pairs to be assigned the deleted value w/o excess copies. (KXMLCore::PairHashTraits::emptyValue): Updated (KXMLCore::PairHashTraits::deletedValue): Updated (KXMLCore::PairHashTraits::assignDeletedValue): part of assignDeleted hack (KXMLCore::DeletedValueAssigner::assignDeletedValue): Use template magic to either use use deletedValue or assignDeletedValue for the cases where we care.
• kxmlcore/RefPtr.h: (KXMLCore::RefPtr::swap): Added swap method. (KXMLCore::swap): Added swap free function.
• kjs/identifier.cpp: (KJS::CStringTranslator::hash): Use new HashTranslator class approach to alternate type based insertion. (KJS::CStringTranslator::equal): ditto (KJS::CStringTranslator::translate): ditto (KJS::Identifier::add): ditto (KJS::UCharBufferTranslator::hash): ditto (KJS::UCharBufferTranslator::equal): ditto (KJS::UCharBufferTranslator::translate): ditto

• irrelevant change:

• kjs/array_object.cpp: (ArrayProtoFunc::callAsFunction): Removed a stray space.

WebCore:

Reviewed by Darin.

• update for new HashTranslator stuff

• khtml/xml/dom_atomicstring.cpp: (DOM::CStringTranslator::hash): (DOM::CStringTranslator::equal): (DOM::CStringTranslator::translate): (DOM::AtomicString::equal): (DOM::AtomicString::add): (DOM::QCharBufferTranslator::hash): (DOM::QCharBufferTranslator::equal): (DOM::QCharBufferTranslator::translate):
• khtml/xml/dom_qname.cpp: (DOM::QNameComponentsTranslator::hash): (DOM::QNameComponentsTranslator::equal): (DOM::QNameComponentsTranslator::translate): (DOM::QualifiedName::QualifiedName):

File:

• trunk/JavaScriptCore/kxmlcore/HashSet.h (modified) (3 diffs)

trunk/JavaScriptCore/kxmlcore/HashSet.h

@@ -31 +31 @@
 
     template <typename T>
-    inline T identityExtract(const T& t) 
+    inline const T& identityExtract(const T& t) 
     { 
         return t; 
     }
 
-    template<typename Value, typename T, Value ConvertT(const T&, unsigned)> 
-    inline Value convertAdapter(const T& t, const T&, unsigned h)
-    { 
-        return ConvertT(t, h); 
-    }
 
+    template<typename Value, typename T, typename HashSetTranslator>
+    struct HashSetTranslatorAdapter 
+    {
+        static unsigned hash(const T& key)
+        {
+            return HashSetTranslator::hash(key);
+        }
+        
+        static bool equal(const Value& a, const T& b)
+        {
+            return HashSetTranslator::equal(a, b);
+        }
+        
+        static void translate(Value& location, const T& key, const T&, unsigned hashCode)
+        {
+            HashSetTranslator::translate(location, key, hashCode);
+        }
+    };
+    
     template<typename Value, typename HashFunctions = DefaultHash<Value>, typename Traits = HashTraits<Value> >
     class HashSet {
     private:
-        typedef HashTable<Value, Value, identityExtract<Value>, HashFunctions, Traits> ImplType;
+        typedef HashTable<Value, Value, identityExtract<Value>, HashFunctions, Traits, Traits> ImplType;
     public:
         typedef Value ValueType;
@@ -70 +84 @@
         // a special version of insert() that finds the object by hashing and comparing
         // with some other type, to avoid the cost of type conversion if the object is already
-        // in the table
-        template<typename T, unsigned HashT(const T&), bool EqualT(const ValueType&, const T&), ValueType ConvertT(const T&, unsigned)> 
+        // in the table. HashTranslator should have the following methods:
+        //   static unsigned hash(const T&);
+        //   static bool equal(const ValueType&, const T&);
+        //   static translate(ValueType&, const T&, unsigned hashCode);
+        template<typename T, typename HashTranslator> 
         std::pair<iterator, bool> insert(const T& value);
         
@@ -149 +166 @@
     
     template<typename Value, typename HashFunctions, typename Traits>
-    template<typename T, unsigned HashT(const T&), bool EqualT(const Value&, const T&), Value ConvertT(const T&, unsigned)> 
+    template<typename T, typename HashSetTranslator> 
     std::pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool> HashSet<Value, HashFunctions, Traits>::insert(const T& value)
     {
-        return m_impl.insert<T, T, HashT, EqualT, convertAdapter<Value, T, ConvertT> >(value, value); 
+        return m_impl.template insert<T, T, HashSetTranslatorAdapter<ValueType, T, HashSetTranslator> >(value, value); 
     }