Changeset 11739 in webkit for trunk/JavaScriptCore/kxmlcore/HashMap.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/HashMap.h (modified) (6 diffs)

trunk/JavaScriptCore/kxmlcore/HashMap.h

@@ -31 +31 @@
 
 template<typename PairType> 
-inline typename PairType::first_type extractFirst(const PairType& value)
+inline typename PairType::first_type const& extractFirst(const PairType& value)
 {
     return value.first;
 }
+
+template<typename Key, typename Mapped, typename HashFunctions>
+class HashMapTranslator 
+{
+    typedef pair<Key, Mapped> ValueType;
+        
+public:
+    static unsigned hash(const Key& key)
+    {
+        return HashFunctions::hash(key);
+    }
+    
+    static bool equal(const Key& a, const Key& b)
+    {
+        return HashFunctions::equal(a, b);
+    }
+    
+    static void translate(ValueType& location, const Key& key, const Mapped& mapped, unsigned)
+    {
+        ValueType tmp(key, mapped);
+        swap(tmp, location);
+    }
+};
+
 
 template<typename Key, typename Mapped, typename HashFunctions = DefaultHash<Key>, typename KeyTraits = HashTraits<Key>, typename MappedTraits = HashTraits<Mapped> >
@@ -41 +65 @@
     typedef Key KeyType;
     typedef Mapped MappedType;
-    typedef std::pair<Key, Mapped> ValueType;
+    typedef pair<Key, Mapped> ValueType;
     typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits;
  private:
-    typedef HashTable<KeyType, ValueType, extractFirst<ValueType>, HashFunctions, ValueTraits> ImplType;
+    typedef HashTable<KeyType, ValueType, extractFirst<ValueType>, HashFunctions, ValueTraits, KeyTraits> ImplType;
+    typedef HashMapTranslator<Key, Mapped, HashFunctions> TranslatorType; 
  public:
     typedef typename ImplType::iterator iterator;
@@ -69 +94 @@
     // return value is a pair of the iterator to the key location, 
     // and a boolean that's true if a new value was actually added
-    std::pair<iterator, bool> set(const KeyType &key, const MappedType &mapped); 
+    pair<iterator, bool> set(const KeyType &key, const MappedType &mapped); 
 
     // does nothing if key is already present
     // return value is a pair of the iterator to the key location, 
     // and a boolean that's true if a new value was actually added
-    std::pair<iterator, bool> add(const KeyType &key, const MappedType &mapped); 
+    pair<iterator, bool> add(const KeyType &key, const MappedType &mapped); 
 
     void remove(const KeyType& key);
@@ -81 +106 @@
 
  private:
+    pair<iterator, bool> inlineAdd(const KeyType &key, const MappedType &mapped);
+
     ImplType m_impl;
 };
@@ -145 +172 @@
 
 template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-std::pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::set(const KeyType &key, const MappedType &mapped) 
-{
-    pair<iterator, bool> result = m_impl.insert(ValueType(key, mapped));
-    // the insert call above won't change anything if the key is
+pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::inlineAdd(const KeyType &key, const MappedType &mapped) 
+{
+    return m_impl.template insert<KeyType, MappedType, TranslatorType>(key, mapped); 
+}
+
+template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
+pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::set(const KeyType &key, const MappedType &mapped) 
+{
+    pair<iterator, bool> result = inlineAdd(key, mapped);
+    // the add call above won't change anything if the key is
     // already there; in that case, make sure to set the value.
     if (!result.second)
@@ -156 +189 @@
 
 template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-std::pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::add(const KeyType &key, const MappedType &mapped)
-{
-    return m_impl.insert(ValueType(key, mapped));
+pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::add(const KeyType &key, const MappedType &mapped)
+{
+    return inlineAdd(key, mapped);
 }