JavaScriptCore:
authormjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 28 Sep 2005 22:01:41 +0000 (22:01 +0000)
committermjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 28 Sep 2005 22:01:41 +0000 (22:01 +0000)
        Reviewed by Eric.

- move HashMap/HashSet code down to JavaScriptCore
http://bugzilla.opendarwin.org/show_bug.cgi?id=5161

        * JavaScriptCore.xcodeproj/project.pbxproj:
        * kjs/internal.cpp:
        (KJS::interpreterMap): Function that fetches the interpreter map on demand.
        (KJS::InterpreterImp::InterpreterImp): Replace use of InterpreterMap
class with an appropriate HashMap.
        (KJS::InterpreterImp::clear): ditto
        (KJS::InterpreterImp::interpreterWithGlobalObject): ditto
        * kjs/interpreter_map.cpp: Removed.
        * kjs/interpreter_map.h: Removed.

The HashMap/HashSet code (copied and slightly tweaked from WebCore)

* kxmlcore/HashFunctions.h: Added.
        (KXMLCore::4):
        (KXMLCore::8):
        (KXMLCore::):
        (KXMLCore::PointerHash::hash):
        (KXMLCore::PointerHash::equal):
        * kxmlcore/HashMap.h: Added.
        (KXMLCore::extractFirst):
        (KXMLCore::HashMap::HashMap):
        (KXMLCore::::size):
        (KXMLCore::::capacity):
        (KXMLCore::::isEmpty):
        (KXMLCore::::begin):
        (KXMLCore::::end):
        (KXMLCore::::find):
        (KXMLCore::::contains):
        (KXMLCore::::set):
        (KXMLCore::::get):
        (KXMLCore::::remove):
        (KXMLCore::::clear):
        (KXMLCore::deleteAllValues):
        * kxmlcore/HashMapPtrSpec.h: Added.
        (KXMLCore::PointerHashIteratorAdapter::PointerHashIteratorAdapter):
        (KXMLCore::PointerHashIteratorAdapter::operator*):
        (KXMLCore::PointerHashIteratorAdapter::operator->):
        (KXMLCore::PointerHashIteratorAdapter::operator++):
        (KXMLCore::PointerHashIteratorAdapter::operator==):
        (KXMLCore::PointerHashIteratorAdapter::operator!=):
        (KXMLCore::PointerHashConstIteratorAdapter::PointerHashConstIteratorAdapter):
        (KXMLCore::PointerHashConstIteratorAdapter::operator*):
        (KXMLCore::PointerHashConstIteratorAdapter::operator->):
        (KXMLCore::PointerHashConstIteratorAdapter::operator++):
        (KXMLCore::PointerHashConstIteratorAdapter::operator==):
        (KXMLCore::PointerHashConstIteratorAdapter::operator!=):
        (KXMLCore::):
        * kxmlcore/HashSet.h: Added.
        (KXMLCore::identityExtract):
        (KXMLCore::convertAdapter):
        (KXMLCore::HashSet::HashSet):
        (KXMLCore::::size):
        (KXMLCore::::capacity):
        (KXMLCore::::isEmpty):
        (KXMLCore::::begin):
        (KXMLCore::::end):
        (KXMLCore::::find):
        (KXMLCore::::contains):
        (KXMLCore::::insert):
        (KXMLCore::::remove):
        (KXMLCore::::clear):
        * kxmlcore/HashTable.cpp: Added.
        (KXMLCore::HashTableStats::~HashTableStats):
        (KXMLCore::HashTableStats::recordCollisionAtCount):
        * kxmlcore/HashTable.h: Added.
        (KXMLCore::HashTableIterator::skipEmptyBuckets):
        (KXMLCore::HashTableIterator::HashTableIterator):
        (KXMLCore::HashTableIterator::operator*):
        (KXMLCore::HashTableIterator::operator->):
        (KXMLCore::HashTableIterator::operator++):
        (KXMLCore::HashTableIterator::operator==):
        (KXMLCore::HashTableIterator::operator!=):
        (KXMLCore::HashTableConstIterator::HashTableConstIterator):
        (KXMLCore::HashTableConstIterator::operator*):
        (KXMLCore::HashTableConstIterator::operator->):
        (KXMLCore::HashTableConstIterator::skipEmptyBuckets):
        (KXMLCore::HashTableConstIterator::operator++):
        (KXMLCore::HashTableConstIterator::operator==):
        (KXMLCore::HashTableConstIterator::operator!=):
        (KXMLCore::HashTable::HashTable):
        (KXMLCore::HashTable::~HashTable):
        (KXMLCore::HashTable::begin):
        (KXMLCore::HashTable::end):
        (KXMLCore::HashTable::size):
        (KXMLCore::HashTable::capacity):
        (KXMLCore::HashTable::insert):
        (KXMLCore::HashTable::isEmptyBucket):
        (KXMLCore::HashTable::isDeletedBucket):
        (KXMLCore::HashTable::isEmptyOrDeletedBucket):
        (KXMLCore::HashTable::hash):
        (KXMLCore::HashTable::equal):
        (KXMLCore::HashTable::identityConvert):
        (KXMLCore::HashTable::extractKey):
        (KXMLCore::HashTable::lookup):
        (KXMLCore::HashTable::shouldExpand):
        (KXMLCore::HashTable::mustRehashInPlace):
        (KXMLCore::HashTable::shouldShrink):
        (KXMLCore::HashTable::shrink):
        (KXMLCore::HashTable::clearBucket):
        (KXMLCore::HashTable::deleteBucket):
        (KXMLCore::HashTable::makeLookupResult):
        (KXMLCore::HashTable::makeIterator):
        (KXMLCore::HashTable::makeConstIterator):
        (KXMLCore::::lookup):
        (KXMLCore::::insert):
        (KXMLCore::::reinsert):
        (KXMLCore::::find):
        (KXMLCore::::contains):
        (KXMLCore::::remove):
        (KXMLCore::::allocateTable):
        (KXMLCore::::expand):
        (KXMLCore::::rehash):
        (KXMLCore::::clear):
        (KXMLCore::::HashTable):
        (KXMLCore::::swap):
        (KXMLCore::::operator):
        (KXMLCore::::checkTableConsistency):
        (KXMLCore::::checkTableConsistencyExceptSize):
        * kxmlcore/HashTraits.h: Added.
        (KXMLCore::HashTraits::emptyValue):
        (KXMLCore::):
        (KXMLCore::PairHashTraits::emptyValue):
        (KXMLCore::PairHashTraits::deletedValue):

WebCore:

        Reviewed by Eric.

- move HashMap/HashSet code down to JavaScriptCore; adapt usage to the new header location
http://bugzilla.opendarwin.org/show_bug.cgi?id=5161

        * ForwardingHeaders/kxmlcore/HashMap.h: Added.
        * ForwardingHeaders/kxmlcore/HashSet.h: Added.
        * ForwardingHeaders/misc/hashmap.h: Removed.
        * ForwardingHeaders/misc/hashset.h: Removed.
        * ForwardingHeaders/misc/pointerhash.h: Removed.
        * WebCore.xcodeproj/project.pbxproj:
        * khtml/css/cssstyleselector.cpp:
        (khtml::CSSRuleSet::getIDRules):
        (khtml::CSSRuleSet::getClassRules):
        (khtml::CSSRuleSet::getTagRules):
        (khtml::CSSRuleSet::getUniversalRules):
        (khtml::CSSRuleSet::addToRuleSet):
        * khtml/css/cssstyleselector.h:
        * khtml/ecma/kjs_binding.cpp:
        * khtml/editing/jsediting.cpp:
        * khtml/html/html_documentimpl.cpp:
        (DOM::addItemToMap):
        * khtml/html/html_documentimpl.h:
        * khtml/html/html_elementimpl.cpp:
        * khtml/html/html_formimpl.cpp:
        (DOM::HTMLFormElementImpl::radioButtonChecked):
        * khtml/html/html_formimpl.h:
        * khtml/html/htmlfactory.cpp:
        (DOM::HTMLElementFactory::createHTMLElement):
        * khtml/html/htmlparser.cpp:
        (HTMLParser::getNode):
        * khtml/xml/dom_atomicstring.cpp:
        * khtml/xml/dom_qname.cpp:
        * khtml/xml/dom_stringimpl.h:
        (KXMLCore::):
        (KXMLCore::CaseInsensitiveHash::hash):
        (KXMLCore::CaseInsensitiveHash::equal):
        * khtml/xml/xml_tokenizer.cpp:
        * kwq/DOM.mm:
        (ObjCEventListener::ObjCEventListener):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@10653 268f45cc-cd09-0410-ab3c-d52691b4dbfc

35 files changed:
JavaScriptCore/ChangeLog
JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj
JavaScriptCore/kjs/internal.cpp
JavaScriptCore/kjs/interpreter_map.cpp [deleted file]
JavaScriptCore/kjs/interpreter_map.h [deleted file]
JavaScriptCore/kxmlcore/HashFunctions.h [new file with mode: 0644]
JavaScriptCore/kxmlcore/HashMap.h [new file with mode: 0644]
JavaScriptCore/kxmlcore/HashMapPtrSpec.h [new file with mode: 0644]
JavaScriptCore/kxmlcore/HashSet.h [new file with mode: 0644]
JavaScriptCore/kxmlcore/HashTable.cpp [new file with mode: 0644]
JavaScriptCore/kxmlcore/HashTable.h [new file with mode: 0644]
JavaScriptCore/kxmlcore/HashTraits.h [new file with mode: 0644]
WebCore/ChangeLog-2005-12-19
WebCore/ForwardingHeaders/kxmlcore/HashMap.h [new file with mode: 0644]
WebCore/ForwardingHeaders/kxmlcore/HashSet.h [new file with mode: 0644]
WebCore/ForwardingHeaders/misc/hashmap.h [deleted file]
WebCore/ForwardingHeaders/misc/hashset.h [deleted file]
WebCore/ForwardingHeaders/misc/pointerhash.h [deleted file]
WebCore/WebCore.xcodeproj/project.pbxproj
WebCore/khtml/css/cssstyleselector.cpp
WebCore/khtml/css/cssstyleselector.h
WebCore/khtml/ecma/kjs_binding.cpp
WebCore/khtml/editing/jsediting.cpp
WebCore/khtml/html/html_documentimpl.cpp
WebCore/khtml/html/html_documentimpl.h
WebCore/khtml/html/html_elementimpl.cpp
WebCore/khtml/html/html_formimpl.cpp
WebCore/khtml/html/html_formimpl.h
WebCore/khtml/html/htmlfactory.cpp
WebCore/khtml/html/htmlparser.cpp
WebCore/khtml/xml/dom_atomicstring.cpp
WebCore/khtml/xml/dom_qname.cpp
WebCore/khtml/xml/dom_stringimpl.h
WebCore/khtml/xml/xml_tokenizer.cpp
WebCore/kwq/DOM.mm

index 6080e84486e83537559a5fb74e5ce41ecf6b6661..d0f09c6d95c1277f033f64041207ca8b7e8efc24 100644 (file)
@@ -1,3 +1,134 @@
+2005-09-27  Maciej Stachowiak  <mjs@apple.com>
+
+        Reviewed by Eric.
+
+       - move HashMap/HashSet code down to JavaScriptCore
+       http://bugzilla.opendarwin.org/show_bug.cgi?id=5161
+       
+        * JavaScriptCore.xcodeproj/project.pbxproj:
+        * kjs/internal.cpp:
+        (KJS::interpreterMap): Function that fetches the interpreter map on demand. 
+        (KJS::InterpreterImp::InterpreterImp): Replace use of InterpreterMap
+       class with an appropriate HashMap.
+        (KJS::InterpreterImp::clear): ditto
+        (KJS::InterpreterImp::interpreterWithGlobalObject): ditto
+        * kjs/interpreter_map.cpp: Removed.
+        * kjs/interpreter_map.h: Removed.
+
+       The HashMap/HashSet code (copied and slightly tweaked from WebCore)
+        
+       * kxmlcore/HashFunctions.h: Added.
+        (KXMLCore::4):
+        (KXMLCore::8):
+        (KXMLCore::):
+        (KXMLCore::PointerHash::hash):
+        (KXMLCore::PointerHash::equal):
+        * kxmlcore/HashMap.h: Added.
+        (KXMLCore::extractFirst):
+        (KXMLCore::HashMap::HashMap):
+        (KXMLCore::::size):
+        (KXMLCore::::capacity):
+        (KXMLCore::::isEmpty):
+        (KXMLCore::::begin):
+        (KXMLCore::::end):
+        (KXMLCore::::find):
+        (KXMLCore::::contains):
+        (KXMLCore::::set):
+        (KXMLCore::::get):
+        (KXMLCore::::remove):
+        (KXMLCore::::clear):
+        (KXMLCore::deleteAllValues):
+        * kxmlcore/HashMapPtrSpec.h: Added.
+        (KXMLCore::PointerHashIteratorAdapter::PointerHashIteratorAdapter):
+        (KXMLCore::PointerHashIteratorAdapter::operator*):
+        (KXMLCore::PointerHashIteratorAdapter::operator->):
+        (KXMLCore::PointerHashIteratorAdapter::operator++):
+        (KXMLCore::PointerHashIteratorAdapter::operator==):
+        (KXMLCore::PointerHashIteratorAdapter::operator!=):
+        (KXMLCore::PointerHashConstIteratorAdapter::PointerHashConstIteratorAdapter):
+        (KXMLCore::PointerHashConstIteratorAdapter::operator*):
+        (KXMLCore::PointerHashConstIteratorAdapter::operator->):
+        (KXMLCore::PointerHashConstIteratorAdapter::operator++):
+        (KXMLCore::PointerHashConstIteratorAdapter::operator==):
+        (KXMLCore::PointerHashConstIteratorAdapter::operator!=):
+        (KXMLCore::):
+        * kxmlcore/HashSet.h: Added.
+        (KXMLCore::identityExtract):
+        (KXMLCore::convertAdapter):
+        (KXMLCore::HashSet::HashSet):
+        (KXMLCore::::size):
+        (KXMLCore::::capacity):
+        (KXMLCore::::isEmpty):
+        (KXMLCore::::begin):
+        (KXMLCore::::end):
+        (KXMLCore::::find):
+        (KXMLCore::::contains):
+        (KXMLCore::::insert):
+        (KXMLCore::::remove):
+        (KXMLCore::::clear):
+        * kxmlcore/HashTable.cpp: Added.
+        (KXMLCore::HashTableStats::~HashTableStats):
+        (KXMLCore::HashTableStats::recordCollisionAtCount):
+        * kxmlcore/HashTable.h: Added.
+        (KXMLCore::HashTableIterator::skipEmptyBuckets):
+        (KXMLCore::HashTableIterator::HashTableIterator):
+        (KXMLCore::HashTableIterator::operator*):
+        (KXMLCore::HashTableIterator::operator->):
+        (KXMLCore::HashTableIterator::operator++):
+        (KXMLCore::HashTableIterator::operator==):
+        (KXMLCore::HashTableIterator::operator!=):
+        (KXMLCore::HashTableConstIterator::HashTableConstIterator):
+        (KXMLCore::HashTableConstIterator::operator*):
+        (KXMLCore::HashTableConstIterator::operator->):
+        (KXMLCore::HashTableConstIterator::skipEmptyBuckets):
+        (KXMLCore::HashTableConstIterator::operator++):
+        (KXMLCore::HashTableConstIterator::operator==):
+        (KXMLCore::HashTableConstIterator::operator!=):
+        (KXMLCore::HashTable::HashTable):
+        (KXMLCore::HashTable::~HashTable):
+        (KXMLCore::HashTable::begin):
+        (KXMLCore::HashTable::end):
+        (KXMLCore::HashTable::size):
+        (KXMLCore::HashTable::capacity):
+        (KXMLCore::HashTable::insert):
+        (KXMLCore::HashTable::isEmptyBucket):
+        (KXMLCore::HashTable::isDeletedBucket):
+        (KXMLCore::HashTable::isEmptyOrDeletedBucket):
+        (KXMLCore::HashTable::hash):
+        (KXMLCore::HashTable::equal):
+        (KXMLCore::HashTable::identityConvert):
+        (KXMLCore::HashTable::extractKey):
+        (KXMLCore::HashTable::lookup):
+        (KXMLCore::HashTable::shouldExpand):
+        (KXMLCore::HashTable::mustRehashInPlace):
+        (KXMLCore::HashTable::shouldShrink):
+        (KXMLCore::HashTable::shrink):
+        (KXMLCore::HashTable::clearBucket):
+        (KXMLCore::HashTable::deleteBucket):
+        (KXMLCore::HashTable::makeLookupResult):
+        (KXMLCore::HashTable::makeIterator):
+        (KXMLCore::HashTable::makeConstIterator):
+        (KXMLCore::::lookup):
+        (KXMLCore::::insert):
+        (KXMLCore::::reinsert):
+        (KXMLCore::::find):
+        (KXMLCore::::contains):
+        (KXMLCore::::remove):
+        (KXMLCore::::allocateTable):
+        (KXMLCore::::expand):
+        (KXMLCore::::rehash):
+        (KXMLCore::::clear):
+        (KXMLCore::::HashTable):
+        (KXMLCore::::swap):
+        (KXMLCore::::operator):
+        (KXMLCore::::checkTableConsistency):
+        (KXMLCore::::checkTableConsistencyExceptSize):
+        * kxmlcore/HashTraits.h: Added.
+        (KXMLCore::HashTraits::emptyValue):
+        (KXMLCore::):
+        (KXMLCore::PairHashTraits::emptyValue):
+        (KXMLCore::PairHashTraits::deletedValue):
+
 2005-09-27  Darin Adler  <darin@apple.com>
 
         Reviewed by Maciej.
index 6c3f73c41983597513d67458dc7f2e4b7af01e60..9bffee23bc397c71f67fd56950662e6e262d401a 100644 (file)
                6541BD7308E80A17002CBEE7 /* TCSpinLock.h in Headers */ = {isa = PBXBuildFile; fileRef = 6541BD6F08E80A17002CBEE7 /* TCSpinLock.h */; };
                6541BD7408E80A17002CBEE7 /* TCSystemAlloc.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 6541BD7008E80A17002CBEE7 /* TCSystemAlloc.cpp */; };
                6541BD7508E80A17002CBEE7 /* TCSystemAlloc.h in Headers */ = {isa = PBXBuildFile; fileRef = 6541BD7108E80A17002CBEE7 /* TCSystemAlloc.h */; };
+               6557E8F808EA5D4D0049CDFC /* HashMapPtrSpec.h in Headers */ = {isa = PBXBuildFile; fileRef = 6557E8F708EA5D4D0049CDFC /* HashMapPtrSpec.h */; settings = {ATTRIBUTES = (Private, ); }; };
                65621E6D089E859700760F35 /* property_slot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 65621E6B089E859700760F35 /* property_slot.cpp */; };
                65621E6E089E859700760F35 /* property_slot.h in Headers */ = {isa = PBXBuildFile; fileRef = 65621E6C089E859700760F35 /* property_slot.h */; settings = {ATTRIBUTES = (Private, ); }; };
                65621E6F089E85D300760F35 /* property_slot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 65621E6B089E859700760F35 /* property_slot.cpp */; };
                65621E70089E85D300760F35 /* property_slot.h in Headers */ = {isa = PBXBuildFile; fileRef = 65621E6C089E859700760F35 /* property_slot.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               65DFC93008EA173A00F7300B /* HashFunctions.h in Headers */ = {isa = PBXBuildFile; fileRef = 65DFC92A08EA173A00F7300B /* HashFunctions.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               65DFC93108EA173A00F7300B /* HashMap.h in Headers */ = {isa = PBXBuildFile; fileRef = 65DFC92B08EA173A00F7300B /* HashMap.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               65DFC93208EA173A00F7300B /* HashSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 65DFC92C08EA173A00F7300B /* HashSet.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               65DFC93308EA173A00F7300B /* HashTable.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 65DFC92D08EA173A00F7300B /* HashTable.cpp */; };
+               65DFC93408EA173A00F7300B /* HashTable.h in Headers */ = {isa = PBXBuildFile; fileRef = 65DFC92E08EA173A00F7300B /* HashTable.h */; settings = {ATTRIBUTES = (Private, ); }; };
+               65DFC93508EA173A00F7300B /* HashTraits.h in Headers */ = {isa = PBXBuildFile; fileRef = 65DFC92F08EA173A00F7300B /* HashTraits.h */; settings = {ATTRIBUTES = (Private, ); }; };
                65E217BD08E7EECC0023E5F6 /* Assertions.h in Headers */ = {isa = PBXBuildFile; fileRef = 65E217B708E7EECC0023E5F6 /* Assertions.h */; settings = {ATTRIBUTES = (Private, ); }; };
                65E217BE08E7EECC0023E5F6 /* Assertions.mm in Sources */ = {isa = PBXBuildFile; fileRef = 65E217B808E7EECC0023E5F6 /* Assertions.mm */; };
                65E217BF08E7EECC0023E5F6 /* FastMalloc.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 65E217B908E7EECC0023E5F6 /* FastMalloc.cpp */; };
                932F5B830822A1C700736975 /* c_class.h in Headers */ = {isa = PBXBuildFile; fileRef = 5182A53B06012C3000CBD2F2 /* c_class.h */; };
                932F5B840822A1C700736975 /* NP_jsobject.h in Headers */ = {isa = PBXBuildFile; fileRef = 517BE7F40610E39600221947 /* NP_jsobject.h */; settings = {ATTRIBUTES = (Private, ); }; };
                932F5B850822A1C700736975 /* npruntime.h in Headers */ = {isa = PBXBuildFile; fileRef = 5199B1BE061B65BC0070C006 /* npruntime.h */; settings = {ATTRIBUTES = (Private, ); }; };
-               932F5B870822A1C700736975 /* interpreter_map.h in Headers */ = {isa = PBXBuildFile; fileRef = 65AB004906261CBA0076DE63 /* interpreter_map.h */; };
                932F5B880822A1C700736975 /* protect.h in Headers */ = {isa = PBXBuildFile; fileRef = 65C02FBB0637462A003E7EE6 /* protect.h */; settings = {ATTRIBUTES = (Private, ); }; };
                932F5B890822A1C700736975 /* protected_values.h in Headers */ = {isa = PBXBuildFile; fileRef = 650B68D90639033F009D42DE /* protected_values.h */; settings = {ATTRIBUTES = (Private, ); }; };
                932F5B8A0822A1C700736975 /* WebScriptObject.h in Headers */ = {isa = PBXBuildFile; fileRef = 51863F6F065420E800E9E8DD /* WebScriptObject.h */; settings = {ATTRIBUTES = (Private, ); }; };
                932F5BC90822A1C700736975 /* c_utility.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 5182A4FB06010F8200CBD2F2 /* c_utility.cpp */; };
                932F5BCA0822A1C700736975 /* c_class.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 5182A53A06012C3000CBD2F2 /* c_class.cpp */; };
                932F5BCB0822A1C700736975 /* npruntime.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 5199B1BD061B65BC0070C006 /* npruntime.cpp */; };
-               932F5BCC0822A1C700736975 /* interpreter_map.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 65AB004806261CBA0076DE63 /* interpreter_map.cpp */; };
                932F5BCD0822A1C700736975 /* protected_values.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 650B68D80639033F009D42DE /* protected_values.cpp */; };
                932F5BCE0822A1C700736975 /* WebScriptObject.mm in Sources */ = {isa = PBXBuildFile; fileRef = 51863FC406542D3100E9E8DD /* WebScriptObject.mm */; };
                932F5BCF0822A1C700736975 /* jni_objc.mm in Sources */ = {isa = PBXBuildFile; fileRef = 517EF37306D695930007C1BA /* jni_objc.mm */; };
                A85D8233087B2822006A9172 /* c_class.h in Headers */ = {isa = PBXBuildFile; fileRef = 5182A53B06012C3000CBD2F2 /* c_class.h */; };
                A85D8234087B2822006A9172 /* NP_jsobject.h in Headers */ = {isa = PBXBuildFile; fileRef = 517BE7F40610E39600221947 /* NP_jsobject.h */; settings = {ATTRIBUTES = (Private, ); }; };
                A85D8235087B2822006A9172 /* npruntime.h in Headers */ = {isa = PBXBuildFile; fileRef = 5199B1BE061B65BC0070C006 /* npruntime.h */; settings = {ATTRIBUTES = (Private, ); }; };
-               A85D8236087B2822006A9172 /* interpreter_map.h in Headers */ = {isa = PBXBuildFile; fileRef = 65AB004906261CBA0076DE63 /* interpreter_map.h */; };
                A85D8237087B2822006A9172 /* protect.h in Headers */ = {isa = PBXBuildFile; fileRef = 65C02FBB0637462A003E7EE6 /* protect.h */; settings = {ATTRIBUTES = (Private, ); }; };
                A85D8238087B2822006A9172 /* protected_values.h in Headers */ = {isa = PBXBuildFile; fileRef = 650B68D90639033F009D42DE /* protected_values.h */; settings = {ATTRIBUTES = (Private, ); }; };
                A85D8239087B2822006A9172 /* WebScriptObject.h in Headers */ = {isa = PBXBuildFile; fileRef = 51863F6F065420E800E9E8DD /* WebScriptObject.h */; settings = {ATTRIBUTES = (Private, ); }; };
                A85D8278087B2822006A9172 /* c_utility.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 5182A4FB06010F8200CBD2F2 /* c_utility.cpp */; };
                A85D8279087B2822006A9172 /* c_class.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 5182A53A06012C3000CBD2F2 /* c_class.cpp */; };
                A85D827A087B2822006A9172 /* npruntime.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 5199B1BD061B65BC0070C006 /* npruntime.cpp */; };
-               A85D827B087B2822006A9172 /* interpreter_map.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 65AB004806261CBA0076DE63 /* interpreter_map.cpp */; };
                A85D827C087B2822006A9172 /* protected_values.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 650B68D80639033F009D42DE /* protected_values.cpp */; };
                A85D827D087B2822006A9172 /* WebScriptObject.mm in Sources */ = {isa = PBXBuildFile; fileRef = 51863FC406542D3100E9E8DD /* WebScriptObject.mm */; };
                A85D827E087B2822006A9172 /* jni_objc.mm in Sources */ = {isa = PBXBuildFile; fileRef = 517EF37306D695930007C1BA /* jni_objc.mm */; };
                6541BD6F08E80A17002CBEE7 /* TCSpinLock.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = TCSpinLock.h; sourceTree = "<group>"; };
                6541BD7008E80A17002CBEE7 /* TCSystemAlloc.cpp */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = TCSystemAlloc.cpp; sourceTree = "<group>"; };
                6541BD7108E80A17002CBEE7 /* TCSystemAlloc.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = TCSystemAlloc.h; sourceTree = "<group>"; };
+               6557E8F708EA5D4D0049CDFC /* HashMapPtrSpec.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = HashMapPtrSpec.h; sourceTree = "<group>"; };
                6560A4CF04B3B3E7008AE952 /* CoreFoundation.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = CoreFoundation.framework; path = /System/Library/Frameworks/CoreFoundation.framework; sourceTree = "<absolute>"; };
                6560A63D04B3B69F008AE952 /* CoreServices.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = CoreServices.framework; path = /System/Library/Frameworks/CoreServices.framework; sourceTree = "<absolute>"; };
                65621E6B089E859700760F35 /* property_slot.cpp */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = property_slot.cpp; sourceTree = "<group>"; };
                65621E6C089E859700760F35 /* property_slot.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = property_slot.h; sourceTree = "<group>"; };
-               65AB004806261CBA0076DE63 /* interpreter_map.cpp */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = interpreter_map.cpp; sourceTree = "<group>"; };
-               65AB004906261CBA0076DE63 /* interpreter_map.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = interpreter_map.h; sourceTree = "<group>"; };
                65C02FBB0637462A003E7EE6 /* protect.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = protect.h; sourceTree = "<group>"; };
+               65DFC92A08EA173A00F7300B /* HashFunctions.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = HashFunctions.h; sourceTree = "<group>"; };
+               65DFC92B08EA173A00F7300B /* HashMap.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = HashMap.h; sourceTree = "<group>"; };
+               65DFC92C08EA173A00F7300B /* HashSet.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = HashSet.h; sourceTree = "<group>"; };
+               65DFC92D08EA173A00F7300B /* HashTable.cpp */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = HashTable.cpp; sourceTree = "<group>"; };
+               65DFC92E08EA173A00F7300B /* HashTable.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = HashTable.h; sourceTree = "<group>"; };
+               65DFC92F08EA173A00F7300B /* HashTraits.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = HashTraits.h; sourceTree = "<group>"; };
                65E217B708E7EECC0023E5F6 /* Assertions.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = Assertions.h; sourceTree = "<group>"; };
                65E217B808E7EECC0023E5F6 /* Assertions.mm */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.objcpp; path = Assertions.mm; sourceTree = "<group>"; };
                65E217B908E7EECC0023E5F6 /* FastMalloc.cpp */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = FastMalloc.cpp; sourceTree = "<group>"; };
                                650B68D80639033F009D42DE /* protected_values.cpp */,
                                652C107E08DA7B1E0020887D /* protected_reference.h */,
                                650B68D90639033F009D42DE /* protected_values.h */,
-                               65AB004806261CBA0076DE63 /* interpreter_map.cpp */,
-                               65AB004906261CBA0076DE63 /* interpreter_map.h */,
                                F692A84E0255597D01FF60F7 /* array_object.h */,
                                F692A84D0255597D01FF60F7 /* array_object.cpp */,
                                F692A8500255597D01FF60F7 /* bool_object.cpp */,
                65162EF108E6A21C007556CD /* kxmlcore */ = {
                        isa = PBXGroup;
                        children = (
+                               6557E8F708EA5D4D0049CDFC /* HashMapPtrSpec.h */,
+                               65DFC92A08EA173A00F7300B /* HashFunctions.h */,
+                               65DFC92B08EA173A00F7300B /* HashMap.h */,
+                               65DFC92C08EA173A00F7300B /* HashSet.h */,
+                               65DFC92D08EA173A00F7300B /* HashTable.cpp */,
+                               65DFC92E08EA173A00F7300B /* HashTable.h */,
+                               65DFC92F08EA173A00F7300B /* HashTraits.h */,
                                6541BD6E08E80A17002CBEE7 /* TCPageMap.h */,
                                6541BD6F08E80A17002CBEE7 /* TCSpinLock.h */,
                                6541BD7008E80A17002CBEE7 /* TCSystemAlloc.cpp */,
                                932F5B830822A1C700736975 /* c_class.h in Headers */,
                                932F5B840822A1C700736975 /* NP_jsobject.h in Headers */,
                                932F5B850822A1C700736975 /* npruntime.h in Headers */,
-                               932F5B870822A1C700736975 /* interpreter_map.h in Headers */,
                                932F5B880822A1C700736975 /* protect.h in Headers */,
                                932F5B890822A1C700736975 /* protected_values.h in Headers */,
                                932F5B8A0822A1C700736975 /* WebScriptObject.h in Headers */,
                                6541BD7208E80A17002CBEE7 /* TCPageMap.h in Headers */,
                                6541BD7308E80A17002CBEE7 /* TCSpinLock.h in Headers */,
                                6541BD7508E80A17002CBEE7 /* TCSystemAlloc.h in Headers */,
+                               65DFC93008EA173A00F7300B /* HashFunctions.h in Headers */,
+                               65DFC93108EA173A00F7300B /* HashMap.h in Headers */,
+                               65DFC93208EA173A00F7300B /* HashSet.h in Headers */,
+                               65DFC93408EA173A00F7300B /* HashTable.h in Headers */,
+                               65DFC93508EA173A00F7300B /* HashTraits.h in Headers */,
+                               6557E8F808EA5D4D0049CDFC /* HashMapPtrSpec.h in Headers */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
                                A85D8233087B2822006A9172 /* c_class.h in Headers */,
                                A85D8234087B2822006A9172 /* NP_jsobject.h in Headers */,
                                A85D8235087B2822006A9172 /* npruntime.h in Headers */,
-                               A85D8236087B2822006A9172 /* interpreter_map.h in Headers */,
                                A85D8237087B2822006A9172 /* protect.h in Headers */,
                                A85D8238087B2822006A9172 /* protected_values.h in Headers */,
                                A85D8239087B2822006A9172 /* WebScriptObject.h in Headers */,
                                932F5BC90822A1C700736975 /* c_utility.cpp in Sources */,
                                932F5BCA0822A1C700736975 /* c_class.cpp in Sources */,
                                932F5BCB0822A1C700736975 /* npruntime.cpp in Sources */,
-                               932F5BCC0822A1C700736975 /* interpreter_map.cpp in Sources */,
                                932F5BCD0822A1C700736975 /* protected_values.cpp in Sources */,
                                932F5BCE0822A1C700736975 /* WebScriptObject.mm in Sources */,
                                932F5BCF0822A1C700736975 /* jni_objc.mm in Sources */,
                                65E217BE08E7EECC0023E5F6 /* Assertions.mm in Sources */,
                                65E217BF08E7EECC0023E5F6 /* FastMalloc.cpp in Sources */,
                                6541BD7408E80A17002CBEE7 /* TCSystemAlloc.cpp in Sources */,
+                               65DFC93308EA173A00F7300B /* HashTable.cpp in Sources */,
                        );
                        runOnlyForDeploymentPostprocessing = 0;
                };
                                A85D8278087B2822006A9172 /* c_utility.cpp in Sources */,
                                A85D8279087B2822006A9172 /* c_class.cpp in Sources */,
                                A85D827A087B2822006A9172 /* npruntime.cpp in Sources */,
-                               A85D827B087B2822006A9172 /* interpreter_map.cpp in Sources */,
                                A85D827C087B2822006A9172 /* protected_values.cpp in Sources */,
                                A85D827D087B2822006A9172 /* WebScriptObject.mm in Sources */,
                                A85D827E087B2822006A9172 /* jni_objc.mm in Sources */,
index 08455bd9b93f423212c042d9e4d67dd34f4e5e72..1036c3c4916d107cda6b764b9e3605e35318dbb1 100644 (file)
@@ -34,7 +34,6 @@
 #include "error_object.h"
 #include "function_object.h"
 #include "internal.h"
-#include "interpreter_map.h"
 #include "lexer.h"
 #include "math_object.h"
 #include "nodes.h"
@@ -45,6 +44,8 @@
 #include "regexp_object.h"
 #include "string_object.h"
 
+#include <kxmlcore/HashMap.h>
+
 #if WIN32
 #include <float.h>
 #define copysign(a, b) _copysign(a, b)
@@ -442,6 +443,14 @@ void InterpreterImp::globalClear()
     ConstantValues::clear();
 }
 
+typedef HashMap<ObjectImp *, InterpreterImp *, PointerHash<ObjectImp *> > InterpreterMap;
+
+static inline InterpreterMap &interpreterMap()
+{
+    static InterpreterMap *map = new InterpreterMap;
+    return *map;
+}
+
 InterpreterImp::InterpreterImp(Interpreter *interp, ObjectImp *glob)
     : globExec(interp, 0)
     , _context(0)
@@ -462,7 +471,7 @@ InterpreterImp::InterpreterImp(Interpreter *interp, ObjectImp *glob)
     globalInit();
   }
 
-  InterpreterMap::setInterpreterForGlobalObject(this, glob);
+  interpreterMap().set(glob, this);
 
   global = glob;
   dbg = 0;
@@ -630,7 +639,7 @@ void InterpreterImp::clear()
     s_hook = 0L;
     globalClear();
   }
-  InterpreterMap::removeInterpreterForGlobalObject(global);
+  interpreterMap().remove(global);
 }
 
 void InterpreterImp::mark()
@@ -807,7 +816,7 @@ void InterpreterImp::restoreBuiltins (const SavedBuiltins &builtins)
 
 InterpreterImp *InterpreterImp::interpreterWithGlobalObject(ObjectImp *global)
 {
-  return InterpreterMap::getInterpreterForGlobalObject(global);
+    return interpreterMap().get(global);
 }
 
 
diff --git a/JavaScriptCore/kjs/interpreter_map.cpp b/JavaScriptCore/kjs/interpreter_map.cpp
deleted file mode 100644 (file)
index 96d103b..0000000
+++ /dev/null
@@ -1,173 +0,0 @@
-/*
- *  This file is part of the KDE libraries
- *  Copyright (C) 2004 Apple Computer, Inc.
- *
- *  This library is free software; you can redistribute it and/or
- *  modify it under the terms of the GNU Library General Public
- *  License as published by the Free Software Foundation; either
- *  version 2 of the License, or (at your option) any later version.
- *
- *  This library is distributed in the hope that it will be useful,
- *  but WITHOUT ANY WARRANTY; without even the implied warranty of
- *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- *  Library General Public License for more details.
- *
- *  You should have received a copy of the GNU Library General Public License
- *  along with this library; see the file COPYING.LIB.  If not, write to
- *  the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- *  Boston, MA 02111-1307, USA.
- *
- */
-
-#include "interpreter_map.h"
-#include "pointer_hash.h"
-#include <stdlib.h>
-
-namespace KJS {
-
-const int _minTableSize = 64;
-
-InterpreterMap::KeyValue *InterpreterMap::_table;
-int InterpreterMap::_tableSize;
-int InterpreterMap::_tableSizeMask;
-int InterpreterMap::_keyCount;
-
-InterpreterImp * InterpreterMap::getInterpreterForGlobalObject(ObjectImp *global)
-{
-    if (!_table)
-        expand();
-    
-    unsigned hash = computeHash(global);
-    
-    int i = hash & _tableSizeMask;
-#if DUMP_STATISTICS
-    ++numProbes;
-    numCollisions += _table[i].key && _table[i].key != global;
-#endif
-    while (ObjectImp *key = _table[i].key) {
-        if (key == global) {
-           return _table[i].value;
-       }
-        i = (i + 1) & _tableSizeMask;
-    }
-    
-    return 0;
-}
-
-void InterpreterMap::setInterpreterForGlobalObject(InterpreterImp *interpreter, ObjectImp *global)
-{
-    if (!_table)
-        expand();
-    
-    unsigned hash = computeHash(global);
-    
-    int i = hash & _tableSizeMask;
-#if DUMP_STATISTICS
-    ++numProbes;
-    numCollisions += _table[i].key && _table[i].key != global;
-#endif
-    while (ObjectImp *key = _table[i].key) {
-        if (key == global) {
-           _table[i].value = interpreter;
-           return;
-       }
-        i = (i + 1) & _tableSizeMask;
-    }
-    
-    _table[i].key = global;
-    _table[i].value = interpreter;
-    ++_keyCount;
-    
-    if (_keyCount * 2 >= _tableSize)
-        expand();
-}
-
-inline void InterpreterMap::insert(InterpreterImp *interpreter, ObjectImp *global)
-{
-    unsigned hash = computeHash(global);
-    
-    int i = hash & _tableSizeMask;
-#if DUMP_STATISTICS
-    ++numProbes;
-    numCollisions += _table[i] != 0;
-#endif
-    while (_table[i].key)
-        i = (i + 1) & _tableSizeMask;
-    
-    _table[i].key = global;
-    _table[i].value = interpreter;
-}
-
-void InterpreterMap::removeInterpreterForGlobalObject(ObjectImp *global)
-{
-    unsigned hash = computeHash(global);
-    
-    ObjectImp *key;
-    
-    int i = hash & _tableSizeMask;
-#if DUMP_STATISTICS
-    ++numProbes;
-    numCollisions += _table[i].key && _table[i].key == global;
-#endif
-    while ((key = _table[i].key)) {
-        if (key == global)
-            break;
-        i = (i + 1) & _tableSizeMask;
-    }
-    if (!key)
-        return;
-    
-    _table[i].key = 0;
-    _table[i].value = 0;
-    --_keyCount;
-    
-    if (_keyCount * 6 < _tableSize && _tableSize > _minTableSize) {
-        shrink();
-        return;
-    }
-    
-    // Reinsert all the items to the right in the same cluster.
-    while (1) {
-        i = (i + 1) & _tableSizeMask;
-        key = _table[i].key;
-       InterpreterImp *value = _table[i].value;
-        if (!key)
-            break;
-        _table[i].key = 0;
-        _table[i].value = 0;
-        insert(value,key);
-    }
-}
-
-void InterpreterMap::expand()
-{
-    rehash(_tableSize == 0 ? _minTableSize : _tableSize * 2);
-}
-
-void InterpreterMap::shrink()
-{
-    rehash(_tableSize / 2);
-}
-
-void InterpreterMap::rehash(int newTableSize)
-{
-    int oldTableSize = _tableSize;
-    KeyValue *oldTable = _table;
-
-    _tableSize = newTableSize;
-    _tableSizeMask = newTableSize - 1;
-    _table = (KeyValue *)calloc(newTableSize, sizeof(KeyValue));
-
-    for (int i = 0; i != oldTableSize; ++i)
-        if (oldTable[i].key)
-            insert(oldTable[i].value, oldTable[i].key);
-
-    free(oldTable);
-}
-
-unsigned InterpreterMap::computeHash(ObjectImp *pointer)
-{
-    return pointerHash(pointer);
-}
-
-} // namespace
diff --git a/JavaScriptCore/kjs/interpreter_map.h b/JavaScriptCore/kjs/interpreter_map.h
deleted file mode 100644 (file)
index 0876547..0000000
+++ /dev/null
@@ -1,58 +0,0 @@
-// -*- c-basic-offset: 2 -*-
-/*
- *  This file is part of the KDE libraries
- *  Copyright (C) 2004 Apple Computer, Inc.
- *
- *  This library is free software; you can redistribute it and/or
- *  modify it under the terms of the GNU Library General Public
- *  License as published by the Free Software Foundation; either
- *  version 2 of the License, or (at your option) any later version.
- *
- *  This library is distributed in the hope that it will be useful,
- *  but WITHOUT ANY WARRANTY; without even the implied warranty of
- *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
- *  Library General Public License for more details.
- *
- *  You should have received a copy of the GNU Library General Public License
- *  along with this library; see the file COPYING.LIB.  If not, write to
- *  the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- *  Boston, MA 02111-1307, USA.
- *
- */
-
-#ifndef _KJS_INTERPRETER_MAP_H_
-#define _KJS_INTERPRETER_MAP_H_
-
-namespace KJS {
-    class ObjectImp;
-    class InterpreterImp;
-
-    class InterpreterMap {
-       struct KeyValue {
-           ObjectImp *key;
-           InterpreterImp *value;
-       };
-
-    public:
-       static InterpreterImp * getInterpreterForGlobalObject(ObjectImp *global);
-       static void setInterpreterForGlobalObject(InterpreterImp *interpreter, ObjectImp *global);
-       static void removeInterpreterForGlobalObject(ObjectImp *global);
-
-    private:
-       static void insert(InterpreterImp *interpreter, ObjectImp *global);
-       static void expand();
-       static void shrink();
-       static void rehash(int newTableSize);
-       static unsigned computeHash(ObjectImp *pointer);
-
-
-       static KeyValue * InterpreterMap::_table;
-       static int InterpreterMap::_tableSize;
-       static int InterpreterMap::_tableSizeMask;
-       static int InterpreterMap::_keyCount;
-    };
-
-} // namespace
-
-
-#endif // _KJS_INTERPRETER_MAP_H_
diff --git a/JavaScriptCore/kxmlcore/HashFunctions.h b/JavaScriptCore/kxmlcore/HashFunctions.h
new file mode 100644 (file)
index 0000000..5f27333
--- /dev/null
@@ -0,0 +1,79 @@
+// -*- mode: c++; c-basic-offset: 4 -*-
+/*
+ * This file is part of the KDE libraries
+ * Copyright (C) 2005 Apple Computer, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public License
+ * along with this library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ *
+ */
+
+#ifndef KXMLCORE_HASH_FUNCTIONS_H
+#define KXMLCORE_HASH_FUNCTIONS_H
+
+namespace KXMLCore {
+
+    template<typename T> class DefaultHash;
+
+    template<int size> unsigned pointerHash(void *pointer);
+
+    // Thomas Wang's 32 bit mix
+    // http://www.cris.com/~Ttwang/tech/inthash.htm
+    template<> inline unsigned pointerHash<4>(void *pointer) 
+    {
+        uint32_t key = reinterpret_cast<uint32_t>(pointer);
+        key += ~(key << 15);
+        key ^= (key >> 10);
+        key += (key << 3);
+        key ^= (key >> 6);
+        key += ~(key << 11);
+        key ^= (key >> 16);
+        return key;
+    }
+    
+    // Thomas Wang's 64 bit mix
+    // http://www.cris.com/~Ttwang/tech/inthash.htm
+    template<> inline unsigned pointerHash<8>(void *pointer)
+    {
+        uint64_t key = reinterpret_cast<uint64_t>(pointer);
+        key += ~(key << 32);
+        key ^= (key >> 22);
+        key += ~(key << 13);
+        key ^= (key >> 8);
+        key += (key << 3);
+        key ^= (key >> 15);
+        key += ~(key << 27);
+        key ^= (key >> 31);
+        return key;
+    }
+    
+    template<> struct DefaultHash<void *> {
+        static unsigned hash(void *key) { return pointerHash<sizeof(void *)>(key); }
+        static bool equal(void *a, void *b) { return a == b; }
+    };
+    
+    // pointer identity hash - default for void *, must be requested explicitly for other 
+    // pointer types; also should work for integer types
+    template<typename T> struct PointerHash {
+        static unsigned hash(T key) { return pointerHash<sizeof(void *)>((void *)key); }
+        static bool equal(T a, T b) { return a == b; }
+    };
+    
+} // namespace KXMLCore
+
+using KXMLCore::DefaultHash;
+using KXMLCore::PointerHash;
+
+#endif // KXLMCORE_HASH_FUNCTIONS_H
diff --git a/JavaScriptCore/kxmlcore/HashMap.h b/JavaScriptCore/kxmlcore/HashMap.h
new file mode 100644 (file)
index 0000000..99a4c35
--- /dev/null
@@ -0,0 +1,192 @@
+// -*- mode: c++; c-basic-offset: 4 -*-
+/*
+ * This file is part of the KDE libraries
+ *
+ * Copyright (C) 2005 Apple Computer, Inc.
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public License
+ * along with this library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ *
+ */
+
+#ifndef KXMLCORE_HASH_MAP_H
+#define KXMLCORE_HASH_MAP_H
+
+#include "HashTable.h"
+#include "HashTraits.h"
+#include "HashFunctions.h"
+
+namespace KXMLCore {
+
+template<typename PairType> 
+inline typename PairType::first_type extractFirst(const PairType& value)
+{
+    return value.first;
+}
+
+template<typename Key, typename Mapped, typename HashFunctions = DefaultHash<Key>, typename KeyTraits = HashTraits<Key>, typename MappedTraits = HashTraits<Mapped> >
+class HashMap {
+ public:
+    typedef Key KeyType;
+    typedef Mapped MappedType;
+    typedef std::pair<Key, Mapped> ValueType;
+    typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits;
+ private:
+    typedef HashTable<KeyType, ValueType, extractFirst<ValueType>, HashFunctions, ValueTraits> ImplType;
+ public:
+    typedef typename ImplType::iterator iterator;
+    typedef typename ImplType::const_iterator const_iterator;
+
+    HashMap() {}
+
+    int size() const;
+    int capacity() const;
+    bool isEmpty() const;
+
+    iterator begin();
+    iterator end();
+    const_iterator begin() const;
+    const_iterator end() const;
+
+    iterator find(const KeyType& key);
+    const_iterator find(const KeyType& key) const;
+    bool contains(const KeyType& key) const;
+    MappedType get(const KeyType &key) const;
+
+    // replaces value but not key if key is already present
+    std::pair<iterator, bool> set(const KeyType &key, const MappedType &mapped); 
+
+    void remove(const KeyType& key);
+    void remove(iterator it);
+    void clear();
+
+ private:
+    ImplType m_impl;
+};
+
+template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
+inline int HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::size() const
+{
+    return m_impl.size(); 
+}
+
+template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
+int HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::capacity() const
+{ 
+    return m_impl.capacity(); 
+}
+
+template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
+inline bool HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::isEmpty() const
+{
+    return size() == 0;
+}
+
+template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
+inline typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::begin()
+{
+    return m_impl.begin();
+}
+
+template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
+inline typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::end()
+{
+    return m_impl.end();
+}
+
+template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
+inline typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::const_iterator HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::begin() const
+{
+    return m_impl.begin();
+}
+
+template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
+inline typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::const_iterator HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::end() const
+{
+    return m_impl.end();
+}
+
+template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
+typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::find(const KeyType& key)
+{
+    return m_impl.find(key);
+}
+
+template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
+typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::const_iterator HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::find(const KeyType& key) const
+{
+    return m_impl.find(key);
+}
+
+template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
+bool HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::contains(const KeyType& key) const
+{
+    return m_impl.contains(key);
+}
+
+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 aboveinsert won't change anything if the key is
+    // already there; in that case, make sure to set the value.
+    if (!result.second)
+        result.first->second = mapped;    
+    return result;
+}
+
+template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
+inline Mapped HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::get(const KeyType &key) const
+{
+    const_iterator it = find(key);
+    if (it == end())
+        return MappedTraits::emptyValue();
+    return it->second;
+}
+
+template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
+void HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::remove(const KeyType& key)
+{
+    m_impl.remove(key);
+}
+
+template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
+void HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::remove(iterator it)
+{
+    m_impl.remove(it);
+}
+
+template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
+void HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::clear()
+{
+    m_impl.clear();
+}
+
+template<typename T>
+void deleteAllValues(T& collection)
+{
+    for (typename T::iterator it = collection.begin(); it != collection.end(); ++it) {
+        delete it->second;
+    }
+}
+
+} // namespace KXMLCore
+
+using KXMLCore::HashMap;
+
+#ifndef HASH_MAP_PTR_SPEC_WORKAROUND
+#include "HashMapPtrSpec.h"
+#endif
+
+#endif /* KXMLCORE_HASH_MAP_H */
diff --git a/JavaScriptCore/kxmlcore/HashMapPtrSpec.h b/JavaScriptCore/kxmlcore/HashMapPtrSpec.h
new file mode 100644 (file)
index 0000000..2ebddd5
--- /dev/null
@@ -0,0 +1,215 @@
+// -*- mode: c++; c-basic-offset: 4 -*-
+/*
+ * This file is part of the KDE libraries
+ * Copyright (C) 2005 Apple Computer, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public License
+ * along with this library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ *
+ */
+
+#ifndef KXMLCORE_HASH_MAP_PTR_SPEC_H
+#define KXMLCORE_HASH_MAP_PTR_SPEC_H
+
+#include "HashMap.h"
+
+// This file includes specializations of HashMap for pointer types using raw pointer hashing
+// try to share implementation by making them use the void * version of the code
+// and casting at interfaces
+
+namespace KXMLCore {
+
+    template<typename P, typename Mapped>
+    class PointerHashIteratorAdapter {
+    private:
+        typedef HashMap<P *, Mapped, PointerHash<P *>, HashTraits<P *>, HashTraits<Mapped> > MapType;
+        typedef typename MapType::ValueType ValueType;
+        typedef typename MapType::ImplValueType ImplValueType;
+        typedef typename HashMap<P *, Mapped, PointerHash<P *>, HashTraits<P *>, HashTraits<Mapped> >::ImplIterator ImplIterator;
+        typedef PointerHashIteratorAdapter<P, Mapped> iterator;
+        typedef ValueType& ReferenceType;
+        typedef ValueType *PointerType;
+        
+        friend class HashMap<P *, Mapped, PointerHash<P *>, HashTraits<P *>, HashTraits<Mapped> >;
+        
+    public:
+        PointerHashIteratorAdapter() {}
+        PointerHashIteratorAdapter(const ImplIterator &impl) : m_impl(impl) {}
+        
+        // default copy, assignment and destructor are ok
+        
+        ReferenceType operator*() const { return *reinterpret_cast<PointerType>(m_impl.operator->()); }
+        PointerType operator->() const { return &(operator*()); }
+        
+        iterator& operator++()
+        {
+            ++m_impl;
+            return *this;
+        }
+        
+        // postfix ++ intentionally omitted
+        
+        // Comparison.
+        bool operator==(const iterator& other) const
+        { 
+            return m_impl == other.m_impl; 
+        }
+        
+        bool operator!=(const iterator& other) const 
+        { 
+            return m_impl != other.m_impl; 
+        }
+        
+    private:
+        ImplIterator m_impl;
+    };
+
+    template<typename P, typename Mapped>
+    class PointerHashConstIteratorAdapter {
+    private:
+        typedef HashMap<P *, Mapped, PointerHash<P *>, HashTraits<P *>, HashTraits<Mapped> > MapType;
+        typedef typename MapType::ValueType ValueType;
+        typedef typename MapType::ImplValueType ImplValueType;
+        typedef typename MapType::ImplIterator ImplIterator;
+        typedef typename MapType::ImplConstIterator ImplConstIterator;
+        typedef PointerHashIteratorAdapter<P, Mapped> iterator;
+        typedef PointerHashConstIteratorAdapter<P, Mapped> const_iterator;
+        typedef const ValueType& ReferenceType;
+        typedef const ValueType *PointerType;
+        
+        friend class HashMap<P *, Mapped, PointerHash<P *>, HashTraits<P *>, HashTraits<Mapped> >;
+        
+    public:
+        PointerHashConstIteratorAdapter() {}
+        PointerHashConstIteratorAdapter(const ImplConstIterator &impl) : m_impl(impl) {}
+        PointerHashConstIteratorAdapter(const iterator &other) : m_impl(other.m_impl) { }
+        
+        // default copy, assignment and destructor are ok
+        
+        ReferenceType operator*() const { return *reinterpret_cast<PointerType>(m_impl.operator->()); }
+        PointerType operator->() const { return &(operator*()); }
+        
+        iterator& operator++()
+        {
+            ++m_impl;
+            return *this;
+        }
+        
+        // postfix ++ intentionally omitted
+        
+        // Comparison.
+        bool operator==(const iterator& other) const
+        { 
+            return m_impl == other.m_impl; 
+        }
+        
+        bool operator!=(const iterator& other) const 
+        { 
+            return m_impl != other.m_impl; 
+        }
+        
+    private:
+        ImplConstIterator m_impl;
+    };
+
+    template<typename P, typename Mapped>
+    class HashMap<P *, Mapped, PointerHash<P *>, HashTraits<P *>, HashTraits<Mapped> > {
+    public:
+        typedef P *KeyType;
+        typedef Mapped MappedType;
+        typedef std::pair<KeyType, Mapped> ValueType;
+    private:
+        // important not to use pointerHash/pointerEqual here or instantiation would recurse
+        typedef HashMap<void *, MappedType, DefaultHash<void *>, HashTraits<void *>, HashTraits<Mapped> > ImplType;
+    public:
+        typedef typename ImplType::ValueType ImplValueType;
+        typedef typename ImplType::iterator ImplIterator;
+        typedef typename ImplType::const_iterator ImplConstIterator;
+        typedef PointerHashIteratorAdapter<P, Mapped> iterator;
+        typedef PointerHashConstIteratorAdapter<P, Mapped> const_iterator;
+        
+        HashMap() {}
+        
+        int size() const { return m_impl.size(); }
+        int capacity() const { return m_impl.capacity(); }
+        bool isEmpty() const { return m_impl.isEmpty(); }
+        
+        iterator begin() { return m_impl.begin(); }
+        iterator end() { return m_impl.end(); }
+        const_iterator begin() const { return m_impl.begin(); }
+        const_iterator end() const { return m_impl.end(); }
+        
+        iterator find(const KeyType& key) { return m_impl.find(key); }
+        const_iterator find(const KeyType& key) const { return m_impl.find(key); }
+        bool contains(const KeyType& key) const { return m_impl.contains(key); }
+        MappedType get(const KeyType &key) const { return m_impl.get(key); }
+        
+        std::pair<iterator, bool> set(const KeyType &key, const MappedType &mapped) 
+        { return m_impl.set(key, mapped); }
+        
+        void remove(const KeyType& key) { m_impl.remove(key); }
+        void remove(iterator it) { m_impl.remove(it.m_impl); }
+        void clear() { m_impl.clear(); }
+        
+    private:
+        ImplType m_impl;
+    };
+    
+    template<typename P, typename Q>
+    class HashMap<P *, Q *, PointerHash<P *>, HashTraits<P *>, HashTraits<Q *> > {
+    private:
+        // important not to use PointerHash here or instantiation would recurse
+        typedef HashMap<void *, void *, DefaultHash<void *>, HashTraits<void *>, HashTraits<void *> > ImplMapType;
+    public:
+        typedef P *KeyType;
+        typedef Q *MappedType;
+        typedef std::pair<KeyType, MappedType> ValueType;
+        typedef typename std::pair<void *, void *> ImplValueType;
+        typedef HashTableIterator<void *, ImplValueType, extractFirst<ImplValueType>, DefaultHash<void *>, PairHashTraits<HashTraits<void *>, HashTraits<void *> > > ImplIterator;
+        typedef HashTableConstIterator<void *, ImplValueType, extractFirst<ImplValueType>, DefaultHash<void *>, PairHashTraits<HashTraits<void *>, HashTraits<void *> > > ImplConstIterator;
+        
+        typedef PointerHashIteratorAdapter<P, Q *> iterator;
+        typedef PointerHashConstIteratorAdapter<P, Q *> const_iterator;
+        
+        HashMap() {}
+        
+        int size() const { return m_impl.size(); }
+        int capacity() const { return m_impl.capacity(); }
+        bool isEmpty() const { return m_impl.isEmpty(); }
+        
+        iterator begin() { return m_impl.begin(); }
+        iterator end() { return m_impl.end(); }
+        const_iterator begin() const { return m_impl.begin(); }
+        const_iterator end() const { return m_impl.end(); }
+        
+        iterator find(const KeyType& key) { return m_impl.find(key); }
+        const_iterator find(const KeyType& key) const { return m_impl.find(key); }
+        bool contains(const KeyType& key) const { return m_impl.contains(key); }
+        MappedType get(const KeyType &key) const { return (MappedType)m_impl.get(key); }
+        
+        std::pair<iterator, bool> set(const KeyType &key, const MappedType &mapped) 
+        { return m_impl.set(key, mapped); }
+        
+        void remove(const KeyType& key) { m_impl.remove(key); }
+        void remove(iterator it) { m_impl.remove(it.m_impl); }
+        void clear() { m_impl.clear(); }
+        
+    private:
+        ImplMapType m_impl;
+    };
+
+} // namespace KXMLCore
+
+#endif // KXMLCORE_HASH_MAP_PTR_SPEC_H
diff --git a/JavaScriptCore/kxmlcore/HashSet.h b/JavaScriptCore/kxmlcore/HashSet.h
new file mode 100644 (file)
index 0000000..b6d32ad
--- /dev/null
@@ -0,0 +1,181 @@
+// -*- mode: c++; c-basic-offset: 4 -*-
+/*
+ * This file is part of the KDE libraries
+ * Copyright (C) 2005 Apple Computer, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public License
+ * along with this library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ *
+ */
+
+#ifndef KXMLCORE_HASH_SET_H
+#define KXMLCORE_HASH_SET_H
+
+#include "HashTable.h"
+#include "HashTraits.h"
+#include "hashfunctions.h"
+
+namespace KXMLCore {
+
+    template <typename T>
+    inline 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 HashFunctions = DefaultHash<Value>, typename Traits = HashTraits<Value> >
+    class HashSet {
+    private:
+        typedef HashTable<Value, Value, identityExtract<Value>, HashFunctions, Traits> ImplType;
+    public:
+        typedef Value ValueType;
+        typedef typename ImplType::iterator iterator;
+        typedef typename ImplType::const_iterator const_iterator;
+        
+        HashSet() {}
+        
+        int size() const;
+        int capacity() const;
+        bool isEmpty() const;
+        
+        iterator begin();
+        iterator end();
+        const_iterator begin() const;
+        const_iterator end() const;
+        
+        iterator find(const ValueType& value);
+        const_iterator find(const ValueType& value) const;
+        bool contains(const ValueType& value) const;
+        
+        std::pair<iterator, bool> insert(const ValueType &value);
+        
+        // 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)> 
+        std::pair<iterator, bool> insert(const T& value);
+        
+        void remove(const ValueType& value);
+        void remove(iterator it);
+        void clear();
+        
+    private:
+        ImplType m_impl;
+    };
+    
+    template<typename Value, typename HashFunctions, typename Traits>
+    inline int HashSet<Value, HashFunctions, Traits>::size() const
+    {
+        return m_impl.size(); 
+    }
+    
+    template<typename Value, typename HashFunctions, typename Traits>
+    int HashSet<Value, HashFunctions, Traits>::capacity() const
+    {
+        return m_impl.capacity(); 
+    }
+    
+    template<typename Value, typename HashFunctions, typename Traits>
+    inline bool HashSet<Value, HashFunctions, Traits>::isEmpty() const
+    {
+        return size() == 0; 
+    }
+    
+    template<typename Value, typename HashFunctions, typename Traits>
+    inline typename HashSet<Value, HashFunctions, Traits>::iterator HashSet<Value, HashFunctions, Traits>::begin()
+    {
+        return m_impl.begin(); 
+    }
+
+    template<typename Value, typename HashFunctions, typename Traits>
+    inline typename HashSet<Value, HashFunctions, Traits>::iterator HashSet<Value, HashFunctions, Traits>::end()
+    {
+        return m_impl.end(); 
+    }
+    
+    template<typename Value, typename HashFunctions, typename Traits>
+    inline typename HashSet<Value, HashFunctions, Traits>::const_iterator HashSet<Value, HashFunctions, Traits>::begin() const
+    {
+        return m_impl.begin(); 
+    }
+    
+    template<typename Value, typename HashFunctions, typename Traits>
+    inline typename HashSet<Value, HashFunctions, Traits>::const_iterator HashSet<Value, HashFunctions, Traits>::end() const
+    {
+        return m_impl.end(); 
+    }
+    
+    template<typename Value, typename HashFunctions, typename Traits>
+    typename HashSet<Value, HashFunctions, Traits>::iterator HashSet<Value, HashFunctions, Traits>::find(const ValueType& value)
+    {
+        return m_impl.find(value); 
+    }
+    
+    template<typename Value, typename HashFunctions, typename Traits>
+    typename HashSet<Value, HashFunctions, Traits>::const_iterator HashSet<Value, HashFunctions, Traits>::find(const ValueType& value) const
+    {
+        return m_impl.find(value); 
+    }
+    
+    template<typename Value, typename HashFunctions, typename Traits>
+    inline bool HashSet<Value, HashFunctions, Traits>::contains(const ValueType& value) const
+    {
+        return m_impl.contains(value); 
+    }
+    
+    template<typename Value, typename HashFunctions, typename Traits>
+    std::pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool> HashSet<Value, HashFunctions, Traits>::insert(const ValueType &value)
+    {
+        return m_impl.insert(value); 
+    }
+    
+    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)> 
+    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); 
+    }
+    
+    template<typename Value, typename HashFunctions, typename Traits>
+    void HashSet<Value, HashFunctions, Traits>::remove(const ValueType& value)
+    {
+        m_impl.remove(value); 
+    }
+    
+    template<typename Value, typename HashFunctions, typename Traits>
+    void HashSet<Value, HashFunctions, Traits>::remove(iterator it)
+    {
+        m_impl.remove(it); 
+    }
+    
+    template<typename Value, typename HashFunctions, typename Traits>
+    void HashSet<Value, HashFunctions, Traits>::clear()
+    {
+        m_impl.clear(); 
+    }
+
+} // namespace khtml
+
+using KXMLCore::HashSet;
+
+#endif /* KXMLCORE_HASH_SET_H */
+
+
diff --git a/JavaScriptCore/kxmlcore/HashTable.cpp b/JavaScriptCore/kxmlcore/HashTable.cpp
new file mode 100644 (file)
index 0000000..b9712e6
--- /dev/null
@@ -0,0 +1,61 @@
+/*
+    This file is part of the KDE libraries
+
+    Copyright (C) 2005 Apple Computer
+
+    This library is free software; you can redistribute it and/or
+    modify it under the terms of the GNU Library General Public
+    License as published by the Free Software Foundation; either
+    version 2 of the License, or (at your option) any later version.
+
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Library General Public License for more details.
+
+    You should have received a copy of the GNU Library General Public License
+    along with this library; see the file COPYING.LIB.  If not, write to
+    the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+    Boston, MA 02111-1307, USA.
+*/
+
+#include "hashtable.h"
+
+namespace KXMLCore {
+
+#if DUMP_HASHTABLE_STATS
+
+int HashTableStats::numAccesses;
+int HashTableStats::numCollisions;
+int HashTableStats::collisionGraph[4096];
+int HashTableStats::maxCollisions;
+int HashTableStats::numRehashes;
+int HashTableStats::numRemoves;
+int HashTableStats::numReinserts;
+
+static HashTableStats logger;
+
+HashTableStats::~HashTableStats()
+{
+    printf("\nkhtml::HashTable statistics\n\n");
+    printf("%d accesses\n", numAccesses);
+    printf("%d total collisions, average %.2f probes per access\n", numCollisions, 1.0 * (numAccesses + numCollisions) / numAccesses);
+    printf("longest collision chain: %d\n", maxCollisions);
+    for (int i = 1; i <= maxCollisions; i++) {
+        printf("  %d lookups with exactly %d collisions (%.2f%% , %.2f%% with this many or more)\n", collisionGraph[i], i, 100.0 * (collisionGraph[i] - collisionGraph[i+1]) / numAccesses, 100.0 * collisionGraph[i] / numAccesses);
+    }
+    printf("%d rehashes\n", numRehashes);
+    printf("%d reinserts\n", numReinserts);
+}
+
+void HashTableStats::recordCollisionAtCount(int count)
+{
+    if (count > maxCollisions)
+        maxCollisions = count;
+    numCollisions++;
+    collisionGraph[count]++;
+}
+
+#endif
+
+} // namespace KXMLCore
diff --git a/JavaScriptCore/kxmlcore/HashTable.h b/JavaScriptCore/kxmlcore/HashTable.h
new file mode 100644 (file)
index 0000000..332beda
--- /dev/null
@@ -0,0 +1,587 @@
+// -*- mode: c++; c-basic-offset: 4 -*-
+/*
+ * This file is part of the KDE libraries
+ * Copyright (C) 2005 Apple Computer, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public License
+ * along with this library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ *
+ */
+
+#ifndef KXMLCORE_HASH_TABLE_H
+#define KXMLCORE_HASH_TABLE_H
+
+#include "FastMalloc.h"
+#include <utility>
+
+namespace KXMLCore {
+
+#define DUMP_HASHTABLE_STATS 0
+#define CHECK_HASHTABLE_CONSISTENCY 0
+    
+#if DUMP_HASHTABLE_STATS
+    
+    struct HashTableStats {
+        ~HashTableStats(); 
+        static int numAccesses;
+        static int numCollisions;
+        static int collisionGraph[4096];
+        static int maxCollisions;
+        static int numRehashes;
+        static int numRemoves;
+        static int numReinserts;
+        static void recordCollisionAtCount(int count);
+    };
+    
+#endif
+    
+#if !CHECK_HASHTABLE_CONSISTENCY
+#define checkTableConsistency() ((void)0)
+#define checkTableConsistencyExceptSize() ((void)0)
+#endif
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    class HashTable;
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    class HashTableIterator {
+    private:
+        typedef HashTable<Key, Value, ExtractKey, HashFunctions, Traits> HashTableType;
+        typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits> iterator;
+        typedef Value ValueType;
+        typedef ValueType& ReferenceType;
+        typedef ValueType *PointerType;
+        
+        friend class HashTable<Key, Value, ExtractKey, HashFunctions, Traits>;
+        
+        void skipEmptyBuckets() 
+        {
+            while (m_position != m_endPosition && (HashTableType::isEmptyOrDeletedBucket(*m_position))) {
+                ++m_position;
+            }
+        }
+        
+        HashTableIterator(PointerType position, PointerType endPosition) 
+            : m_position(position), m_endPosition(endPosition) 
+        { 
+            skipEmptyBuckets();
+        }
+    public:
+        HashTableIterator() {}
+        
+        // default copy, assignment and destructor are ok
+        
+        ReferenceType operator*() const { return *m_position; }
+        PointerType operator->() const { return &(operator*()); }
+        
+        iterator& operator++()
+        {
+            ++m_position;
+            skipEmptyBuckets();
+            return *this;
+        }
+        
+        // postfix ++ intentionally omitted
+        
+        // Comparison.
+        bool operator==(const iterator& other) const
+        { 
+            return m_position == other.m_position; 
+        }
+        
+        bool operator!=(const iterator& other) const 
+        { 
+            return m_position != other.m_position; 
+        }
+        
+    private:
+        PointerType m_position;
+        PointerType m_endPosition;
+    };
+
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    class HashTableConstIterator {
+    private:
+        typedef HashTable<Key, Value, ExtractKey, HashFunctions, Traits> HashTableType;
+        typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits> iterator;
+        typedef HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits> const_iterator;
+        typedef Value ValueType;
+        typedef const ValueType& ReferenceType;
+        typedef const ValueType *PointerType;
+        
+        friend class HashTable<Key, Value, ExtractKey, HashFunctions, Traits>;
+        
+        HashTableConstIterator(PointerType position, PointerType endPosition) 
+            : m_position(position), m_endPosition(endPosition) 
+        { 
+            skipEmptyBuckets();
+        }
+    public:
+        HashTableConstIterator() {}
+        HashTableConstIterator(const iterator &other)
+            : m_position(other.m_position), m_endPosition(other.m_endPosition) { }
+        
+        // default copy, assignment and destructor are ok
+        
+        ReferenceType operator*() const { return *m_position; }
+        PointerType operator->() const { return &(operator*()); }
+        
+        void skipEmptyBuckets() 
+        {
+            while (m_position != m_endPosition && (HashTableType::isEmptyOrDeletedBucket(*m_position))) {
+                ++m_position;
+            }
+        }
+        
+        iterator& operator++()
+        {
+            ++m_position;
+            skipEmptyBuckets();
+            return *this;
+        }
+        
+        // postfix ++ intentionally omitted
+        
+        // Comparison.
+        bool operator==(const const_iterator& other) const
+        { 
+            return m_position == other.m_position; 
+        }
+        
+        bool operator!=(const const_iterator& other) const 
+        { 
+            return m_position != other.m_position; 
+        }
+        
+    private:
+        PointerType m_position;
+        PointerType m_endPosition;
+    };
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    class HashTable {
+    public:
+        typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits> iterator;
+        typedef HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits> const_iterator;
+        typedef Key KeyType;
+        typedef Value ValueType;
+        
+        HashTable() : m_table(0), m_tableSize(0), m_tableSizeMask(0), m_keyCount(0), m_deletedCount(0) {}
+        ~HashTable() { fastFree(m_table); }
+        
+        HashTable(const HashTable& other);
+        void swap(const HashTable& other);
+        HashTable& operator=(const HashTable& other);
+        
+        iterator begin() { return makeIterator(m_table); }
+        iterator end() { return makeIterator(m_table + m_tableSize); }
+        const_iterator begin() const { return makeConstIterator(m_table); }
+        const_iterator end() const { return makeConstIterator(m_table + m_tableSize); }
+        
+        int size() const { return m_keyCount; }
+        int capacity() const { return m_tableSize; }
+        
+        std::pair<iterator, bool> insert(const ValueType& value) { return insert<KeyType, ValueType, hash, equal, identityConvert>(extractKey(value), value); }
+        
+        // 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, typename Extra, unsigned HashT(const T&), bool EqualT(const Key&, const T&), ValueType ConvertT(const T&, const Extra &, unsigned)> 
+        std::pair<iterator, bool> insert(const T& key, const Extra& extra);
+        
+        iterator find(const KeyType& key);
+        const_iterator find(const KeyType& key) const;
+        bool contains(const KeyType& key) const;
+        
+        void remove(const KeyType& key);
+        void remove(iterator it);
+        void clear();
+        
+        static bool isEmptyBucket(const ValueType& value) { return extractKey(value) == extractKey(Traits::emptyValue()); }
+        static bool isDeletedBucket(const ValueType& value) { return extractKey(value) == extractKey(Traits::deletedValue()); }
+        static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
+        
+    private:
+        static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
+        static bool equal(const KeyType& a, const KeyType& b) { return HashFunctions::equal(a, b); }                    
+        // FIXME: assumes key == value; special lookup needs adjusting
+        static ValueType identityConvert(const KeyType& key, const ValueType& value, unsigned) { return value; }
+        static KeyType extractKey(const ValueType& value) { return ExtractKey(value); }
+        
+        static ValueType *allocateTable(int size);
+        
+        typedef std::pair<ValueType *, bool> LookupType;
+        typedef std::pair<LookupType, unsigned> FullLookupType;
+        
+        LookupType lookup(const Key& key) { return lookup<Key, hash, equal>(key).first; }
+        template<typename T, unsigned HashT(const T&), bool EqualT(const Key&, const T&)>
+        FullLookupType lookup(const T&);
+        
+        void remove(ValueType *);
+        
+        bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
+        bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
+        bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > m_minTableSize; }
+        void expand();
+        void shrink() { rehash(m_tableSize / 2); }
+        
+        void rehash(int newTableSize);
+        void reinsert(const ValueType&);
+        
+        static void clearBucket(ValueType& key) { key = Traits::emptyValue();}
+        static void deleteBucket(ValueType& key) { key = Traits::deletedValue();}
+        
+        FullLookupType makeLookupResult(ValueType *position, bool found, unsigned hash)
+        {
+            return FullLookupType(LookupType(position, found), hash);
+        }
+        
+        iterator makeIterator(ValueType *pos) { return iterator(pos, m_table + m_tableSize); }
+        const_iterator makeConstIterator(ValueType *pos) const { return const_iterator(pos, m_table + m_tableSize); }
+        
+#if CHECK_HASHTABLE_CONSISTENCY
+        void checkTableConsistency() const;
+        void checkTableConsistencyExceptSize() const;
+#endif
+        
+        static const int m_minTableSize = 64;
+        static const int m_maxLoad = 2;
+        static const int m_minLoad = 6;
+        
+        ValueType *m_table;
+        int m_tableSize;
+        int m_tableSizeMask;
+        int m_keyCount;
+        int m_deletedCount;
+    };
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    template<typename T, unsigned HashT(const T&), bool EqualT(const Key&, const T&)>
+    inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::FullLookupType HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::lookup(const T& key)
+    {
+        assert(m_table);
+        
+        unsigned h = HashT(key);
+        int sizeMask = m_tableSizeMask;
+        int i = h & sizeMask;
+        int k = 0;
+        
+#if DUMP_HASHTABLE_STATS
+        ++HashTableStats::numAccesses;
+        int probeCount = 0;
+#endif
+        
+        ValueType *table = m_table;
+        ValueType *entry;
+        ValueType *deletedEntry = 0;
+        while (!isEmptyBucket(*(entry = table + i))) {
+            if (isDeletedBucket(*entry))
+                deletedEntry = entry;
+            else if (EqualT(extractKey(*entry), key))
+                return makeLookupResult(entry, true, h);
+#if DUMP_HASHTABLE_STATS
+            ++probeCount;
+            HashTableStats::recordCollisionAtCount(probeCount);
+#endif
+            if (k == 0)
+                k = 1 | (h % sizeMask);
+            i = (i + k) & sizeMask;
+        }
+        
+        return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
+    }
+    
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    template<typename T, typename Extra, unsigned HashT(const T&), bool EqualT(const Key&, const T&), Value ConvertT(const T&, const Extra &, unsigned)> 
+    inline std::pair<typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::iterator, bool> HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::insert(const T& key, const Extra &extra)
+    {
+        if (!m_table)
+            expand();
+        
+        checkTableConsistency();
+        
+        FullLookupType lookupResult = lookup<T, HashT, EqualT>(key);
+        
+        ValueType *entry = lookupResult.first.first;
+        bool found = lookupResult.first.second;
+        unsigned h = lookupResult.second;
+        
+        if (found) {
+            return std::make_pair(makeIterator(entry), false);
+        }
+        
+        if (isDeletedBucket(*entry))
+            --m_deletedCount;
+        
+        *entry = ConvertT(key, extra, h);
+        ++m_keyCount;
+        
+        if (shouldExpand()) {
+            KeyType enteredKey = extractKey(*entry);
+            expand();
+            return std::make_pair(find(enteredKey), true);
+        }
+        
+        checkTableConsistency();
+        
+        return std::make_pair(makeIterator(entry), true);
+    }
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::reinsert(const ValueType& entry)
+    {
+        assert(m_table);
+        assert(!lookup(extractKey(entry)).second);
+        assert(!isDeletedBucket(*(lookup(extractKey(entry)).first)));
+#if DUMP_HASHTABLE_STATS
+        ++HashTableStats::numReinserts;
+#endif
+        
+        *(lookup(extractKey(entry)).first) = entry;
+    }
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::iterator HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::find(const Key& key)
+    {
+        if (!m_table)
+            return end();
+        
+        LookupType result = lookup(key);
+        if (!result.second)
+            return end();
+        return makeIterator(result.first);
+    }
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::const_iterator HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::find(const Key& key) const
+    {
+        if (!m_table)
+            return end();
+        
+        LookupType result = const_cast<HashTable *>(this)->lookup(key);
+        if (!result.second)
+            return end();
+        return makeConstIterator(result.first);
+    }
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    inline bool HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::contains(const KeyType& key) const 
+    {
+        if (!m_table)
+            return false;
+        
+        return const_cast<HashTable *>(this)->lookup(key).second;
+    }
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::remove(ValueType *pos)
+    {
+        checkTableConsistency();
+        
+#if DUMP_HASHTABLE_STATS
+        ++HashTableStats::numRemoves;
+#endif
+        
+        deleteBucket(*pos);
+        ++m_deletedCount;
+        --m_keyCount;
+        
+        if (shouldShrink())
+            shrink();
+        
+        checkTableConsistency();
+    }
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::remove(const KeyType& key)
+    { 
+        if (!m_table)
+            return;
+        
+        remove(find(key)); 
+    }
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::remove(iterator it)
+    { 
+        if (it == end())
+            return;
+        
+        remove(it.m_position); 
+    }
+    
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    inline Value *HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::allocateTable(int size)
+    {
+        // would use a template member function with explicit specializations here, but
+        // gcc doesn't appear to support that
+        if (Traits::emptyValueIsZero)
+            return reinterpret_cast<ValueType *>(fastCalloc(size, sizeof(ValueType))); 
+        else {
+            ValueType *result = reinterpret_cast<ValueType *>(fastMalloc(size * sizeof(ValueType))); 
+            for (int i = 0; i < size; i++) {
+                clearBucket(result[i]);
+            }
+            return result;
+        }
+    }
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::expand()
+    { 
+        int newSize;
+        if (m_tableSize == 0)
+            newSize = m_minTableSize;
+        else if (mustRehashInPlace())
+            newSize = m_tableSize;
+        else
+            newSize = m_tableSize * 2;
+        
+        rehash(newSize); 
+    }
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::rehash(int newTableSize)
+    {
+        checkTableConsistencyExceptSize();
+        
+        int oldTableSize = m_tableSize;
+        ValueType *oldTable = m_table;
+        
+#if DUMP_HASHTABLE_STATS
+        if (oldTableSize != 0)
+            ++HashTableStats::numRehashes;
+#endif
+        
+        m_tableSize = newTableSize;
+        m_tableSizeMask = newTableSize - 1;
+        m_table = allocateTable(newTableSize);
+        
+        for (int i = 0; i != oldTableSize; ++i) {
+            ValueType entry = oldTable[i];
+            if (!isEmptyOrDeletedBucket(entry))
+                reinsert(entry);
+        }
+        
+        m_deletedCount = 0;
+        
+        fastFree(oldTable);
+        
+        checkTableConsistency();
+    }
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::clear()
+    {
+        fastFree(m_table);
+        m_table = 0;
+        m_tableSize = 0;
+        m_tableSizeMask = 0;
+        m_keyCount = 0;
+    }
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::HashTable(const HashTable& other)
+        : m_table(0)
+          , m_tableSize(other.m_tableSize)
+          , m_tableSizeMask(other.m_tableSizeMask)
+          , m_keyCount(other.m_keyCount)
+          , m_deletedCount(other.m_deletedCount)
+    {
+        if (m_tableSize != 0) {
+            m_table = fastMalloc(m_tableSize);
+            memcpy(other.m_table, m_table, m_tableSize * sizeof(ValueType));
+        }
+    }
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::swap(const HashTable& other)
+    {
+        ValueType *tmp_table = m_table;
+        m_table = other.m_table;
+        other.m_table = tmp_table;
+        
+        int tmp_tableSize = m_tableSize;
+        m_tableSize = other.m_tableSize;
+        other.m_tableSize = tmp_tableSize;
+        
+        int tmp_tableSizeMask = m_tableSizeMask;
+        m_tableSizeMask = other.m_tableSizeMask;
+        other.m_tableSizeMask = tmp_tableSizeMask;
+        
+        int tmp_keyCount = m_keyCount;
+        m_keyCount = other.m_keyCount;
+        other.m_keyCount = tmp_keyCount;
+        
+        int tmp_deletedCount = m_deletedCount;
+        m_deletedCount = other.m_deletedCount;
+        other.m_deletedCount = tmp_deletedCount;
+    }
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    HashTable<Key, Value, ExtractKey, HashFunctions, Traits>& HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::operator=(const HashTable& other)
+    {
+        HashTable tmp(other);
+        swap(tmp);
+        return *this;
+    }
+    
+#if CHECK_HASHTABLE_CONSISTENCY
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::checkTableConsistency() const
+    {
+        checkTableConsistencyExceptSize();
+        assert(!shouldExpand());
+        assert(!shouldShrink());
+    }
+    
+    template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+    void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::checkTableConsistencyExceptSize() const
+    {
+        if (!m_table)
+            return;
+        
+        int count = 0;
+        int deletedCount = 0;
+        for (int j = 0; j < m_tableSize; ++j) {
+            ValueType *entry = m_table + j;
+            if (isEmptyBucket(*entry))
+                continue;
+            
+            if (isDeletedBucket(*entry)) {
+                ++deletedCount;
+                continue;
+            }
+            
+            const_iterator it = find(extractKey(*entry));
+            assert(entry == it.m_position);
+            ++count;
+        }
+        
+        assert(count == m_keyCount);
+        assert(deletedCount == m_deletedCount);
+        assert(m_tableSize >= m_minTableSize);
+        assert(m_tableSizeMask);
+        assert(m_tableSize == m_tableSizeMask + 1);
+    }
+    
+#endif // CHECK_HASHTABLE_CONSISTENCY
+    
+} // namespace KXMLCore
+
+#endif // KXMLCORE_HASH_TABLE_H
diff --git a/JavaScriptCore/kxmlcore/HashTraits.h b/JavaScriptCore/kxmlcore/HashTraits.h
new file mode 100644 (file)
index 0000000..7137ac9
--- /dev/null
@@ -0,0 +1,103 @@
+// -*- mode: c++; c-basic-offset: 4 -*-
+/*
+ * This file is part of the KDE libraries
+ * Copyright (C) 2005 Apple Computer, Inc.
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public License
+ * along with this library; see the file COPYING.LIB.  If not, write to
+ * the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ *
+ */
+
+#ifndef KXMLCORE_HASH_TRAITS_H
+#define KXMLCORE_HASH_TRAITS_H
+
+#include <utility>
+#include <bits/cpp_type_traits.h>
+
+namespace KXMLCore {
+
+    using std::pair;
+    // FIXME: stop using this evil hack, use something supported or else specialize
+    // for all numerit cypes by hand
+    template<typename T>
+    struct HashTraits {
+        typedef T traitType;
+#ifdef __GLIBCXX__ // gcc 3.4 and greater:
+        static const bool emptyValueIsZero = std::__is_integer<T>::__value;
+#else
+        static const bool emptyValueIsZero = std::__is_integer<T>::_M_type;
+#endif
+        
+        static traitType emptyValue() {
+            return traitType();
+        }
+    };
+
+    // may not be appropriate for all uses since it would disallow 0 and -1 as keys
+    template<>
+    struct HashTraits<int> {
+        typedef int traitType;
+        static const bool emptyValueIsZero = true;
+        
+        static traitType emptyValue() {
+            return 0;
+        }
+        static traitType deletedValue() {
+            return -1;
+        }
+    };
+
+    template<typename P>
+    struct HashTraits<P *> {
+        typedef P *traitType;
+        static const bool emptyValueIsZero = true;
+        
+        static traitType emptyValue() {
+            return reinterpret_cast<P *>(0);
+        }
+        static traitType deletedValue() {
+            return reinterpret_cast<P *>(-1);
+        }
+    };
+
+    template<typename FirstTraits, typename SecondTraits>
+    struct PairHashTraits {
+    private:
+        typedef typename FirstTraits::traitType FirstType;
+        typedef typename SecondTraits::traitType SecondType;
+    public:
+        typedef pair<FirstType, SecondType> traitType;
+        
+        static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
+        
+        static traitType emptyValue() {
+            return traitType(FirstTraits::emptyValue(), SecondTraits::emptyValue());
+        }
+        static traitType deletedValue() {
+            return traitType(FirstTraits::deletedValue(), SecondTraits::emptyValue());
+        }
+    };
+    
+    template<typename First, typename Second>
+    struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > {
+    };
+
+} // namespace KXMLCore
+
+using KXMLCore::HashTraits;
+using KXMLCore::PairHashTraits;
+
+#endif // KXMLCORE_HASH_TRAITS_H
index c8992b8153132b5d278e001f2663dadfa8c76073..a4eb0610ec8cbab1b57de1716fcaf570bf63bf53 100644 (file)
@@ -1,3 +1,46 @@
+2005-09-27  Maciej Stachowiak  <mjs@apple.com>
+
+        Reviewed by Eric.
+
+       - move HashMap/HashSet code down to JavaScriptCore; adapt usage to the new header location
+       http://bugzilla.opendarwin.org/show_bug.cgi?id=5161
+
+        * ForwardingHeaders/kxmlcore/HashMap.h: Added.
+        * ForwardingHeaders/kxmlcore/HashSet.h: Added.
+        * ForwardingHeaders/misc/hashmap.h: Removed.
+        * ForwardingHeaders/misc/hashset.h: Removed.
+        * ForwardingHeaders/misc/pointerhash.h: Removed.
+        * WebCore.xcodeproj/project.pbxproj:
+        * khtml/css/cssstyleselector.cpp:
+        (khtml::CSSRuleSet::getIDRules):
+        (khtml::CSSRuleSet::getClassRules):
+        (khtml::CSSRuleSet::getTagRules):
+        (khtml::CSSRuleSet::getUniversalRules):
+        (khtml::CSSRuleSet::addToRuleSet):
+        * khtml/css/cssstyleselector.h:
+        * khtml/ecma/kjs_binding.cpp:
+        * khtml/editing/jsediting.cpp:
+        * khtml/html/html_documentimpl.cpp:
+        (DOM::addItemToMap):
+        * khtml/html/html_documentimpl.h:
+        * khtml/html/html_elementimpl.cpp:
+        * khtml/html/html_formimpl.cpp:
+        (DOM::HTMLFormElementImpl::radioButtonChecked):
+        * khtml/html/html_formimpl.h:
+        * khtml/html/htmlfactory.cpp:
+        (DOM::HTMLElementFactory::createHTMLElement):
+        * khtml/html/htmlparser.cpp:
+        (HTMLParser::getNode):
+        * khtml/xml/dom_atomicstring.cpp:
+        * khtml/xml/dom_qname.cpp:
+        * khtml/xml/dom_stringimpl.h:
+        (KXMLCore::):
+        (KXMLCore::CaseInsensitiveHash::hash):
+        (KXMLCore::CaseInsensitiveHash::equal):
+        * khtml/xml/xml_tokenizer.cpp:
+        * kwq/DOM.mm:
+        (ObjCEventListener::ObjCEventListener):
+
 2005-09-26  Darin Adler  <darin@apple.com>
 
         * layout-tests/fast/js/array-every.html: Fixed test case; one of the tests was using
diff --git a/WebCore/ForwardingHeaders/kxmlcore/HashMap.h b/WebCore/ForwardingHeaders/kxmlcore/HashMap.h
new file mode 100644 (file)
index 0000000..4d7d60f
--- /dev/null
@@ -0,0 +1 @@
+#import <JavaScriptCore/HashMap.h>
diff --git a/WebCore/ForwardingHeaders/kxmlcore/HashSet.h b/WebCore/ForwardingHeaders/kxmlcore/HashSet.h
new file mode 100644 (file)
index 0000000..03b7a70
--- /dev/null
@@ -0,0 +1 @@
+#import <JavaScriptCore/HashSet.h>
diff --git a/WebCore/ForwardingHeaders/misc/hashmap.h b/WebCore/ForwardingHeaders/misc/hashmap.h
deleted file mode 100644 (file)
index 99c001f..0000000
+++ /dev/null
@@ -1 +0,0 @@
-#import <hashmap.h>
diff --git a/WebCore/ForwardingHeaders/misc/hashset.h b/WebCore/ForwardingHeaders/misc/hashset.h
deleted file mode 100644 (file)
index 6ee9b7e..0000000
+++ /dev/null
@@ -1 +0,0 @@
-#import <hashset.h>
diff --git a/WebCore/ForwardingHeaders/misc/pointerhash.h b/WebCore/ForwardingHeaders/misc/pointerhash.h
deleted file mode 100644 (file)
index 38203c6..0000000
+++ /dev/null
@@ -1 +0,0 @@
-#import <pointerhash.h>
index 770b626b0701e60d36c05b5072a1defb3c35d873..15fc1ea3143ff2481cc6637157f4fcffa485f80d 100644 (file)
                65AC79AA0831F006009385CE /* apply_style_command.h in Headers */ = {isa = PBXBuildFile; fileRef = 65AC79A80831F006009385CE /* apply_style_command.h */; };
                65DC16C40831DD6F0022744E /* composite_edit_command.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 65DC16C20831DD6F0022744E /* composite_edit_command.cpp */; };
                65DC16C50831DD6F0022744E /* composite_edit_command.h in Headers */ = {isa = PBXBuildFile; fileRef = 65DC16C30831DD6F0022744E /* composite_edit_command.h */; };
-               65DE852908765FC30011428A /* hashmap.h in Headers */ = {isa = PBXBuildFile; fileRef = 65DE852708765FC30011428A /* hashmap.h */; };
-               65DE852A08765FC30011428A /* hashtraits.h in Headers */ = {isa = PBXBuildFile; fileRef = 65DE852808765FC30011428A /* hashtraits.h */; };
-               65F378290870D958000B2F94 /* hashset.h in Headers */ = {isa = PBXBuildFile; fileRef = 65F378260870D958000B2F94 /* hashset.h */; };
-               65F3782A0870D958000B2F94 /* hashtable.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 65F378270870D958000B2F94 /* hashtable.cpp */; };
-               65F3782B0870D958000B2F94 /* hashtable.h in Headers */ = {isa = PBXBuildFile; fileRef = 65F378280870D958000B2F94 /* hashtable.h */; };
                7E6FEED80898582300C44C3F /* WebCoreScriptDebugger.h in Headers */ = {isa = PBXBuildFile; fileRef = 7E6FEED60898582300C44C3F /* WebCoreScriptDebugger.h */; settings = {ATTRIBUTES = (Private, ); }; };
                7E6FEED90898582300C44C3F /* WebCoreScriptDebugger.mm in Sources */ = {isa = PBXBuildFile; fileRef = 7E6FEED70898582300C44C3F /* WebCoreScriptDebugger.mm */; };
                7E6FEEDA0898582300C44C3F /* WebCoreScriptDebugger.h in Headers */ = {isa = PBXBuildFile; fileRef = 7E6FEED60898582300C44C3F /* WebCoreScriptDebugger.h */; settings = {ATTRIBUTES = (Private, ); }; };
                A8212BDE08794A2300677359 /* domparser.h in Headers */ = {isa = PBXBuildFile; fileRef = 1A69D37F085627410009880D /* domparser.h */; };
                A8212BDF08794A2300677359 /* dom_qname.h in Headers */ = {isa = PBXBuildFile; fileRef = 550A0BC8085F6039007353D6 /* dom_qname.h */; };
                A8212BE008794A2300677359 /* htmlnames.h in Headers */ = {isa = PBXBuildFile; fileRef = 550A0BCC085F604D007353D6 /* htmlnames.h */; };
-               A8212BE108794A2300677359 /* hashset.h in Headers */ = {isa = PBXBuildFile; fileRef = 65F378260870D958000B2F94 /* hashset.h */; };
-               A8212BE208794A2300677359 /* hashtable.h in Headers */ = {isa = PBXBuildFile; fileRef = 65F378280870D958000B2F94 /* hashtable.h */; };
                A8212BE408794A2300677359 /* linkCursor.tiff in Resources */ = {isa = PBXBuildFile; fileRef = F5A1B04902DE8ABA018635CA /* linkCursor.tiff */; };
                A8212BE508794A2300677359 /* html4.css in Resources */ = {isa = PBXBuildFile; fileRef = F5A1B05302DE8B46018635CA /* html4.css */; };
                A8212BE608794A2300677359 /* quirks.css in Resources */ = {isa = PBXBuildFile; fileRef = BC8F62990405F45600A80004 /* quirks.css */; };
                A8212CFB08794A2300677359 /* domparser.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 1A69D380085627410009880D /* domparser.cpp */; };
                A8212CFC08794A2300677359 /* dom_qname.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 550A0BC7085F6039007353D6 /* dom_qname.cpp */; };
                A8212CFD08794A2300677359 /* htmlnames.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 550A0BCB085F604D007353D6 /* htmlnames.cpp */; };
-               A8212CFE08794A2300677359 /* hashtable.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 65F378270870D958000B2F94 /* hashtable.cpp */; };
                A8212D0008794A2300677359 /* ApplicationServices.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = F5C2869302846DCD018635CA /* ApplicationServices.framework */; };
                A8212D0108794A2300677359 /* Carbon.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = F5C2869402846DCD018635CA /* Carbon.framework */; };
                A8212D0208794A2300677359 /* Cocoa.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = F5C2869502846DCD018635CA /* Cocoa.framework */; };
                65AC79A80831F006009385CE /* apply_style_command.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; name = apply_style_command.h; path = editing/apply_style_command.h; sourceTree = "<group>"; };
                65DC16C20831DD6F0022744E /* composite_edit_command.cpp */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; name = composite_edit_command.cpp; path = editing/composite_edit_command.cpp; sourceTree = "<group>"; };
                65DC16C30831DD6F0022744E /* composite_edit_command.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; name = composite_edit_command.h; path = editing/composite_edit_command.h; sourceTree = "<group>"; };
-               65DE852708765FC30011428A /* hashmap.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = hashmap.h; sourceTree = "<group>"; };
-               65DE852808765FC30011428A /* hashtraits.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = hashtraits.h; sourceTree = "<group>"; };
-               65F378260870D958000B2F94 /* hashset.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = hashset.h; sourceTree = "<group>"; };
-               65F378270870D958000B2F94 /* hashtable.cpp */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.cpp; path = hashtable.cpp; sourceTree = "<group>"; };
-               65F378280870D958000B2F94 /* hashtable.h */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.c.h; path = hashtable.h; sourceTree = "<group>"; };
                65F80697054D9F86008BF776 /* KWQExceptions.mm */ = {isa = PBXFileReference; fileEncoding = 30; lastKnownFileType = sourcecode.cpp.objcpp; path = KWQExceptions.mm; sourceTree = "<group>"; };
                7E6FEED60898582300C44C3F /* WebCoreScriptDebugger.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WebCoreScriptDebugger.h; sourceTree = "<group>"; };
                7E6FEED70898582300C44C3F /* WebCoreScriptDebugger.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = WebCoreScriptDebugger.mm; sourceTree = "<group>"; };
                                93ABCE5E06E1A42E0085925B /* formdata.h */,
                                F523D27A02DE43D7018635CA /* helper.cpp */,
                                F523D27B02DE43D7018635CA /* helper.h */,
-                               65F378260870D958000B2F94 /* hashset.h */,
-                               65F378270870D958000B2F94 /* hashtable.cpp */,
-                               65F378280870D958000B2F94 /* hashtable.h */,
-                               65DE852708765FC30011428A /* hashmap.h */,
-                               65DE852808765FC30011428A /* hashtraits.h */,
                                F523D28202DE43D7018635CA /* khtmldata.h */,
                                F523D28302DE43D7018635CA /* khtmllayout.h */,
                                F523D28402DE43D7018635CA /* loader_client.h */,
                                1A69D381085627410009880D /* domparser.h in Headers */,
                                550A0BCA085F6039007353D6 /* dom_qname.h in Headers */,
                                550A0BCE085F604D007353D6 /* htmlnames.h in Headers */,
-                               65F378290870D958000B2F94 /* hashset.h in Headers */,
-                               65F3782B0870D958000B2F94 /* hashtable.h in Headers */,
-                               65DE852908765FC30011428A /* hashmap.h in Headers */,
-                               65DE852A08765FC30011428A /* hashtraits.h in Headers */,
                                BCEF3435087B563E00BBF833 /* htmlfactory.h in Headers */,
                                A8FD8B87087CB45700DC3707 /* KWQWMatrix.h in Headers */,
                                BC179894088D975F006068A5 /* render_theme.h in Headers */,
                                A8212BDE08794A2300677359 /* domparser.h in Headers */,
                                A8212BDF08794A2300677359 /* dom_qname.h in Headers */,
                                A8212BE008794A2300677359 /* htmlnames.h in Headers */,
-                               A8212BE108794A2300677359 /* hashset.h in Headers */,
-                               A8212BE208794A2300677359 /* hashtable.h in Headers */,
                                A85D7A8F0879EC64006A9172 /* KWQWMatrix.h in Headers */,
                                A898F147088121E90075EFB2 /* htmlfactory.h in Headers */,
                                A8C0FB90089701F900BA5114 /* DrawCanvasItem.h in Headers */,
                                1A69D382085627410009880D /* domparser.cpp in Sources */,
                                550A0BC9085F6039007353D6 /* dom_qname.cpp in Sources */,
                                550A0BCD085F604D007353D6 /* htmlnames.cpp in Sources */,
-                               65F3782A0870D958000B2F94 /* hashtable.cpp in Sources */,
                                BCEF3434087B563E00BBF833 /* htmlfactory.cpp in Sources */,
                                A8FD8B86087CB44C00DC3707 /* KWQWMatrix.mm in Sources */,
                                BC179892088D975F006068A5 /* render_theme_mac.mm in Sources */,
                                A8212CFB08794A2300677359 /* domparser.cpp in Sources */,
                                A8212CFC08794A2300677359 /* dom_qname.cpp in Sources */,
                                A8212CFD08794A2300677359 /* htmlnames.cpp in Sources */,
-                               A8212CFE08794A2300677359 /* hashtable.cpp in Sources */,
                                A85D7A8E0879EC64006A9172 /* KWQWMatrix.mm in Sources */,
                                A898F148088121ED0075EFB2 /* htmlfactory.cpp in Sources */,
                                A8C0FB97089701F900BA5114 /* DrawView.mm in Sources */,
index 550d1724da3b0202685e6b14c6004b92578b9c6f..9cc6d2e1d3b688aa23a9102b9806f548cce6cba4 100644 (file)
@@ -65,6 +65,8 @@
 #include <qintcache.h>
 #include <stdlib.h>
 
+#include <kxmlcore/HashMap.h>
+
 using namespace DOM;
 using namespace HTMLNames;
 
@@ -178,6 +180,34 @@ if (id == propID) \
 
 namespace khtml {
 
+class CSSRuleSet : public FastAllocated
+{
+public:
+    CSSRuleSet();
+    ~CSSRuleSet();
+    
+    typedef HashMap<DOM::DOMStringImpl *, CSSRuleDataList *, PointerHash<DOM::DOMStringImpl *> > AtomRuleMap;
+    
+    void addRulesFromSheet(DOM::CSSStyleSheetImpl* sheet, const DOM::DOMString &medium = "screen");
+    
+    void addRule(DOM::CSSStyleRuleImpl* rule, DOM::CSSSelector* sel);
+    void addToRuleSet(DOM::DOMStringImpl* key, AtomRuleMap& map,
+                      DOM::CSSStyleRuleImpl* rule, DOM::CSSSelector* sel);
+    
+    CSSRuleDataList* getIDRules(DOM::DOMStringImpl* key) { return m_idRules.get(key); }
+    CSSRuleDataList* getClassRules(DOM::DOMStringImpl* key) { return m_classRules.get(key); }
+    CSSRuleDataList* getTagRules(DOM::DOMStringImpl* key) { return m_tagRules.get(key); }
+    CSSRuleDataList* getUniversalRules() { return m_universalRules; }
+    
+public:
+    AtomRuleMap m_idRules;
+    AtomRuleMap m_classRules;
+    AtomRuleMap m_tagRules;
+    CSSRuleDataList* m_universalRules;
+    
+    uint m_ruleCount;
+};
+
 CSSRuleSet *CSSStyleSelector::defaultStyle = 0;
 CSSRuleSet *CSSStyleSelector::defaultQuirksStyle = 0;
 CSSRuleSet *CSSStyleSelector::defaultPrintStyle = 0;
@@ -1428,7 +1458,7 @@ void CSSRuleSet::addToRuleSet(DOMStringImpl* key, AtomRuleMap& map,
     CSSRuleDataList* rules = map.get(key);
     if (!rules) {
         rules = new CSSRuleDataList(m_ruleCount++, rule, sel);
-        map.insert(key, rules);
+        map.set(key, rules);
     } else
         rules->append(m_ruleCount++, rule, sel);
 }
index 5f83adf8491e0cffb899aa212a3d30faceecc988..3680a11dc7db5ebc5adbb5f5efe318bd14066eed 100644 (file)
 #define _CSS_cssstyleselector_h_
 
 #include <qptrvector.h>
-#include "misc/pointerhash.h"
 
 #include "rendering/render_style.h"
 #include "dom/dom_string.h"
+#include "xml/dom_stringimpl.h"
 #include "css/css_ruleimpl.h"
 #include <kxmlcore/FastMalloc.h>
 
@@ -260,32 +260,5 @@ public:
         CSSRuleData* m_last;
     };
     
-    class CSSRuleSet : public FastAllocated
-    {
-    public:
-        CSSRuleSet();
-        ~CSSRuleSet();
-
-        typedef HashMap<DOM::DOMStringImpl *, CSSRuleDataList *, PointerHash<DOM::DOMStringImpl *> > AtomRuleMap;
-
-        void addRulesFromSheet(DOM::CSSStyleSheetImpl* sheet, const DOM::DOMString &medium = "screen");
-
-        void addRule(DOM::CSSStyleRuleImpl* rule, DOM::CSSSelector* sel);
-        void addToRuleSet(DOM::DOMStringImpl* key, AtomRuleMap& map,
-                          DOM::CSSStyleRuleImpl* rule, DOM::CSSSelector* sel);
-
-        CSSRuleDataList* getIDRules(DOM::DOMStringImpl* key) { return m_idRules.get(key); }
-        CSSRuleDataList* getClassRules(DOM::DOMStringImpl* key) { return m_classRules.get(key); }
-        CSSRuleDataList* getTagRules(DOM::DOMStringImpl* key) { return m_tagRules.get(key); }
-        CSSRuleDataList* getUniversalRules() { return m_universalRules; }
-
-    public:
-        AtomRuleMap m_idRules;
-        AtomRuleMap m_classRules;
-        AtomRuleMap m_tagRules;
-        CSSRuleDataList* m_universalRules;
-        
-        uint m_ruleCount;
-    };
-};
+}
 #endif
index d3778f11e4e6d61aa35b447ac83541fe46277941..54a8e83463832124727ba33fd13803615086e5d8 100644 (file)
 #include "dom/dom_exception.h"
 #include "dom/dom2_events.h"
 #include "dom/dom2_range.h"
-#include "misc/hashmap.h"
 #include "xml/dom_nodeimpl.h"
 #include "xml/dom2_eventsimpl.h"
 #include "xml/EventNames.h"
 #include "dom/css_stylesheet.h"
 
+// gcc 3.x can't handle including the HashMap pointer specialization in this file
+#ifndef __GLIBCXX__ // less than gcc 3.4
+#define HASH_MAP_PTR_SPEC_WORKAROUND 1
+#endif
+#include <kxmlcore/HashMap.h>
+
 #include <kdebug.h>
 
 using namespace DOM::EventNames;
@@ -46,9 +51,6 @@ using DOM::EventException;
 using DOM::NodeImpl;
 using DOM::RangeException;
 
-using khtml::HashMap;
-using khtml::PointerHash;
-
 namespace KJS {
 
 UString DOMObject::toString(ExecState *) const
index 3230bdfed383a843579e3276fae84f5845ff3a8c..90af62b8a829b861151fb8f2e6ef5deaed4fa982 100644 (file)
 #include "htmlediting.h"
 #include "khtml_part.h"
 #include "SelectionController.h"
-#include "misc/hashmap.h"
+#include <kxmlcore/HashMap.h>
 
 #if APPLE_CHANGES
 #include "KWQKHTMLPart.h"
 #endif
 
 using khtml::TypingCommand;
-using khtml::HashMap;
-using khtml::CaseInsensitiveHash;
 
 namespace DOM {
 
@@ -599,7 +597,7 @@ CommandMap *createCommandDictionary()
     for (int i = 0; i < numCommands; ++i) {
         DOMStringImpl *name = new DOMStringImpl(commands[i].name);
         name->ref();
-        commandMap->insert(name, &commands[i].imp);
+        commandMap->set(name, &commands[i].imp);
     }
 #ifndef NDEBUG
     supportsPasteCommand = true;
index f5873e0f58d42084024fd1ebf0f8b4340c36d3e0..c2133e8eeb5931fc5550217cc36cf49e3786cf36 100644 (file)
@@ -273,7 +273,7 @@ static void addItemToMap(HTMLDocumentImpl::NameCountMap& map, const DOMString& n
  
     HTMLDocumentImpl::NameCountMap::iterator it = map.find(name.impl()); 
     if (it == map.end())
-        map.insert(name.impl(), 1);
+        map.set(name.impl(), 1);
     else
         ++(it->second);
 }
index 085b9227606fe4e8497ae3d3f3c60b4b29253dd6..822d2488cec4626020888d22aaca45e736750e77 100644 (file)
@@ -28,7 +28,7 @@
 #include "xml/dom_docimpl.h"
 #include "misc/loader_client.h"
 #include "html/html_miscimpl.h"
-#include "misc/hashmap.h"
+#include <kxmlcore/HashMap.h>
 
 class KHTMLView;
 class QString;
@@ -79,7 +79,7 @@ public:
 
     virtual DocumentTypeImpl *doctype() const;
 
-    typedef khtml::HashMap<DOMStringImpl *, int> NameCountMap;
+    typedef HashMap<DOMStringImpl *, int> NameCountMap;
 
 protected:
     HTMLElementImpl *bodyElement;
index afb155cdbc229ab83e6c488b66855b33c9d2cb2d..8f059bdb20ea39787015ab0176e8e6c31df788d6 100644 (file)
@@ -33,7 +33,7 @@
 #include "html/htmltokenizer.h"
 #include "htmlfactory.h"
 
-#include "misc/hashset.h"
+#include <kxmlcore/HashSet.h>
 #include "editing/visible_text.h"
 
 #include "khtmlview.h"
index f15e106beff2156842676cde3a13fa88d88c6cab..6d355d146f58efc5d58e931c22e012015502c9cb 100644 (file)
@@ -690,16 +690,13 @@ void HTMLFormElementImpl::radioButtonChecked(HTMLInputElementImpl *caller)
 
     // Uncheck the currently selected item
     if (!m_selectedRadioButtons)
-        m_selectedRadioButtons = new HashMap<DOMStringImpl*, HTMLInputElementImpl*, PointerHash<DOMStringImpl*> >;
+        m_selectedRadioButtons = new NameToInputMap;
 
     HTMLInputElementImpl* currentCheckedRadio = m_selectedRadioButtons->get(caller->name().impl());
     if (currentCheckedRadio && currentCheckedRadio != caller)
         currentCheckedRadio->setChecked(false);
         
-    // Now insert ourselves into the hash. There should really be a replace method
-    // in HashMap...
-    m_selectedRadioButtons->remove(caller->name().impl());
-    m_selectedRadioButtons->insert(caller->name().impl(), caller);
+    m_selectedRadioButtons->set(caller->name().impl(), caller);
 }
 
 HTMLInputElementImpl* HTMLFormElementImpl::checkedRadioButtonForGroup(DOMStringImpl* name)
index 058acf6e5c192a360347c89acd4b58f3d8567547..bc3bd712d8c97a3ef5c19717a4af9e75eebe8e26 100644 (file)
@@ -30,8 +30,7 @@
 
 #include <qptrvector.h>
 #include <qmemarray.h>
-#include "hashtable.h"
-#include "pointerhash.h"
+#include <kxmlcore/HashMap.h>
 
 class KHTMLView;
 class QTextCodec;
@@ -147,7 +146,8 @@ public:
     bool m_inreset : 1;
     bool m_malformed : 1;
 
-    khtml::HashMap<DOMStringImpl*, HTMLInputElementImpl*, khtml::PointerHash<DOMStringImpl*> >* m_selectedRadioButtons;
+    typedef HashMap<DOMStringImpl*, HTMLInputElementImpl*, PointerHash<DOMStringImpl*> > NameToInputMap;
+    NameToInputMap* m_selectedRadioButtons;
     
 private:
     void parseEnctype(const DOMString &);
index 3ec75bd7b72c2ca096790cdd6db336724fa2ef02..261e5bb0014544b58baa8cb04e4072529a802bae 100644 (file)
 #include "html/html_tableimpl.h"
 #include "html/html_objectimpl.h"
 
-#include "misc/pointerhash.h"
-
-using khtml::PointerHash;
-using khtml::HashMap;
+#include <kxmlcore/HashMap.h>
 
 namespace DOM
 {
@@ -342,74 +339,74 @@ HTMLElementImpl* HTMLElementFactory::createHTMLElement(const AtomicString& tagNa
         gFunctionMap = new FunctionMap;
         
         // Populate it with constructor functions.
-        gFunctionMap->insert(htmlTag.localName().impl(), (void*)&htmlConstructor);
-        gFunctionMap->insert(headTag.localName().impl(), (void*)&headConstructor);
-        gFunctionMap->insert(bodyTag.localName().impl(), (void*)&bodyConstructor);
-        gFunctionMap->insert(baseTag.localName().impl(), (void*)&baseConstructor);
-        gFunctionMap->insert(linkTag.localName().impl(), (void*)&linkConstructor);
-        gFunctionMap->insert(metaTag.localName().impl(), (void*)&metaConstructor);
-        gFunctionMap->insert(styleTag.localName().impl(), (void*)&styleConstructor);
-        gFunctionMap->insert(titleTag.localName().impl(), (void*)&titleConstructor);
-        gFunctionMap->insert(frameTag.localName().impl(), (void*)&frameConstructor);
-        gFunctionMap->insert(framesetTag.localName().impl(), (void*)&framesetConstructor);
-        gFunctionMap->insert(iframeTag.localName().impl(), (void*)&iframeConstructor);
-        gFunctionMap->insert(formTag.localName().impl(), (void*)&formConstructor);
-        gFunctionMap->insert(buttonTag.localName().impl(), (void*)&buttonConstructor);
-        gFunctionMap->insert(inputTag.localName().impl(), (void*)&inputConstructor);
-        gFunctionMap->insert(isindexTag.localName().impl(), (void*)&isindexConstructor);
-        gFunctionMap->insert(fieldsetTag.localName().impl(), (void*)&fieldsetConstructor);
-        gFunctionMap->insert(labelTag.localName().impl(), (void*)&labelConstructor);
-        gFunctionMap->insert(legendTag.localName().impl(), (void*)&legendConstructor);
-        gFunctionMap->insert(optgroupTag.localName().impl(), (void*)&optgroupConstructor);
-        gFunctionMap->insert(optionTag.localName().impl(), (void*)&optionConstructor);
-        gFunctionMap->insert(selectTag.localName().impl(), (void*)&selectConstructor);
-        gFunctionMap->insert(textareaTag.localName().impl(), (void*)&textareaConstructor);
-        gFunctionMap->insert(dlTag.localName().impl(), (void*)&dlConstructor);
-        gFunctionMap->insert(olTag.localName().impl(), (void*)&olConstructor);
-        gFunctionMap->insert(ulTag.localName().impl(), (void*)&ulConstructor);
-        gFunctionMap->insert(dirTag.localName().impl(), (void*)&dirConstructor);
-        gFunctionMap->insert(menuTag.localName().impl(), (void*)&menuConstructor);
-        gFunctionMap->insert(liTag.localName().impl(), (void*)&liConstructor);
-        gFunctionMap->insert(blockquoteTag.localName().impl(), (void*)&blockquoteConstructor);
-        gFunctionMap->insert(divTag.localName().impl(), (void*)&divConstructor);
-        gFunctionMap->insert(h1Tag.localName().impl(), (void*)&headingConstructor);
-        gFunctionMap->insert(h2Tag.localName().impl(), (void*)&headingConstructor);
-        gFunctionMap->insert(h3Tag.localName().impl(), (void*)&headingConstructor);
-        gFunctionMap->insert(h4Tag.localName().impl(), (void*)&headingConstructor);
-        gFunctionMap->insert(h5Tag.localName().impl(), (void*)&headingConstructor);
-        gFunctionMap->insert(h6Tag.localName().impl(), (void*)&headingConstructor);
-        gFunctionMap->insert(hrTag.localName().impl(), (void*)&hrConstructor);
-        gFunctionMap->insert(pTag.localName().impl(), (void*)&paragraphConstructor);
-        gFunctionMap->insert(preTag.localName().impl(), (void*)&preConstructor);
-        gFunctionMap->insert(xmpTag.localName().impl(), (void*)&preConstructor);
-        gFunctionMap->insert(basefontTag.localName().impl(), (void*)&basefontConstructor);
-        gFunctionMap->insert(fontTag.localName().impl(), (void*)&fontConstructor);
-        gFunctionMap->insert(delTag.localName().impl(), (void*)&modConstructor);
-        gFunctionMap->insert(insTag.localName().impl(), (void*)&modConstructor);
-        gFunctionMap->insert(aTag.localName().impl(), (void*)&anchorConstructor);
-        gFunctionMap->insert(imageTag.localName().impl(), (void*)&imageConstructor);
-        gFunctionMap->insert(imgTag.localName().impl(), (void*)&imageConstructor);
-        gFunctionMap->insert(mapTag.localName().impl(), (void*)&mapConstructor);
-        gFunctionMap->insert(areaTag.localName().impl(), (void*)&areaConstructor);
-        gFunctionMap->insert(canvasTag.localName().impl(), (void*)&canvasConstructor);
-        gFunctionMap->insert(appletTag.localName().impl(), (void*)&appletConstructor);
-        gFunctionMap->insert(embedTag.localName().impl(), (void*)&embedConstructor);
-        gFunctionMap->insert(objectTag.localName().impl(), (void*)&objectConstructor);
-        gFunctionMap->insert(paramTag.localName().impl(), (void*)&paramConstructor);
-        gFunctionMap->insert(scriptTag.localName().impl(), (void*)&scriptConstructor);
-        gFunctionMap->insert(tableTag.localName().impl(), (void*)&tableConstructor);
-        gFunctionMap->insert(captionTag.localName().impl(), (void*)&tableCaptionConstructor);
-        gFunctionMap->insert(colgroupTag.localName().impl(), (void*)&tableColConstructor);
-        gFunctionMap->insert(colTag.localName().impl(), (void*)&tableColConstructor);
-        gFunctionMap->insert(trTag.localName().impl(), (void*)&tableRowConstructor);
-        gFunctionMap->insert(tdTag.localName().impl(), (void*)&tableCellConstructor);
-        gFunctionMap->insert(thTag.localName().impl(), (void*)&tableCellConstructor);
-        gFunctionMap->insert(theadTag.localName().impl(), (void*)&tableSectionConstructor);
-        gFunctionMap->insert(tbodyTag.localName().impl(), (void*)&tableSectionConstructor);
-        gFunctionMap->insert(tfootTag.localName().impl(), (void*)&tableSectionConstructor);
-        gFunctionMap->insert(brTag.localName().impl(), (void*)&brConstructor);
-        gFunctionMap->insert(qTag.localName().impl(), (void*)&quoteConstructor);
-        gFunctionMap->insert(marqueeTag.localName().impl(), (void*)&marqueeConstructor);
+        gFunctionMap->set(htmlTag.localName().impl(), (void*)&htmlConstructor);
+        gFunctionMap->set(headTag.localName().impl(), (void*)&headConstructor);
+        gFunctionMap->set(bodyTag.localName().impl(), (void*)&bodyConstructor);
+        gFunctionMap->set(baseTag.localName().impl(), (void*)&baseConstructor);
+        gFunctionMap->set(linkTag.localName().impl(), (void*)&linkConstructor);
+        gFunctionMap->set(metaTag.localName().impl(), (void*)&metaConstructor);
+        gFunctionMap->set(styleTag.localName().impl(), (void*)&styleConstructor);
+        gFunctionMap->set(titleTag.localName().impl(), (void*)&titleConstructor);
+        gFunctionMap->set(frameTag.localName().impl(), (void*)&frameConstructor);
+        gFunctionMap->set(framesetTag.localName().impl(), (void*)&framesetConstructor);
+        gFunctionMap->set(iframeTag.localName().impl(), (void*)&iframeConstructor);
+        gFunctionMap->set(formTag.localName().impl(), (void*)&formConstructor);
+        gFunctionMap->set(buttonTag.localName().impl(), (void*)&buttonConstructor);
+        gFunctionMap->set(inputTag.localName().impl(), (void*)&inputConstructor);
+        gFunctionMap->set(isindexTag.localName().impl(), (void*)&isindexConstructor);
+        gFunctionMap->set(fieldsetTag.localName().impl(), (void*)&fieldsetConstructor);
+        gFunctionMap->set(labelTag.localName().impl(), (void*)&labelConstructor);
+        gFunctionMap->set(legendTag.localName().impl(), (void*)&legendConstructor);
+        gFunctionMap->set(optgroupTag.localName().impl(), (void*)&optgroupConstructor);
+        gFunctionMap->set(optionTag.localName().impl(), (void*)&optionConstructor);
+        gFunctionMap->set(selectTag.localName().impl(), (void*)&selectConstructor);
+        gFunctionMap->set(textareaTag.localName().impl(), (void*)&textareaConstructor);
+        gFunctionMap->set(dlTag.localName().impl(), (void*)&dlConstructor);
+        gFunctionMap->set(olTag.localName().impl(), (void*)&olConstructor);
+        gFunctionMap->set(ulTag.localName().impl(), (void*)&ulConstructor);
+        gFunctionMap->set(dirTag.localName().impl(), (void*)&dirConstructor);
+        gFunctionMap->set(menuTag.localName().impl(), (void*)&menuConstructor);
+        gFunctionMap->set(liTag.localName().impl(), (void*)&liConstructor);
+        gFunctionMap->set(blockquoteTag.localName().impl(), (void*)&blockquoteConstructor);
+        gFunctionMap->set(divTag.localName().impl(), (void*)&divConstructor);
+        gFunctionMap->set(h1Tag.localName().impl(), (void*)&headingConstructor);
+        gFunctionMap->set(h2Tag.localName().impl(), (void*)&headingConstructor);
+        gFunctionMap->set(h3Tag.localName().impl(), (void*)&headingConstructor);
+        gFunctionMap->set(h4Tag.localName().impl(), (void*)&headingConstructor);
+        gFunctionMap->set(h5Tag.localName().impl(), (void*)&headingConstructor);
+        gFunctionMap->set(h6Tag.localName().impl(), (void*)&headingConstructor);
+        gFunctionMap->set(hrTag.localName().impl(), (void*)&hrConstructor);
+        gFunctionMap->set(pTag.localName().impl(), (void*)&paragraphConstructor);
+        gFunctionMap->set(preTag.localName().impl(), (void*)&preConstructor);
+        gFunctionMap->set(xmpTag.localName().impl(), (void*)&preConstructor);
+        gFunctionMap->set(basefontTag.localName().impl(), (void*)&basefontConstructor);
+        gFunctionMap->set(fontTag.localName().impl(), (void*)&fontConstructor);
+        gFunctionMap->set(delTag.localName().impl(), (void*)&modConstructor);
+        gFunctionMap->set(insTag.localName().impl(), (void*)&modConstructor);
+        gFunctionMap->set(aTag.localName().impl(), (void*)&anchorConstructor);
+        gFunctionMap->set(imageTag.localName().impl(), (void*)&imageConstructor);
+        gFunctionMap->set(imgTag.localName().impl(), (void*)&imageConstructor);
+        gFunctionMap->set(mapTag.localName().impl(), (void*)&mapConstructor);
+        gFunctionMap->set(areaTag.localName().impl(), (void*)&areaConstructor);
+        gFunctionMap->set(canvasTag.localName().impl(), (void*)&canvasConstructor);
+        gFunctionMap->set(appletTag.localName().impl(), (void*)&appletConstructor);
+        gFunctionMap->set(embedTag.localName().impl(), (void*)&embedConstructor);
+        gFunctionMap->set(objectTag.localName().impl(), (void*)&objectConstructor);
+        gFunctionMap->set(paramTag.localName().impl(), (void*)&paramConstructor);
+        gFunctionMap->set(scriptTag.localName().impl(), (void*)&scriptConstructor);
+        gFunctionMap->set(tableTag.localName().impl(), (void*)&tableConstructor);
+        gFunctionMap->set(captionTag.localName().impl(), (void*)&tableCaptionConstructor);
+        gFunctionMap->set(colgroupTag.localName().impl(), (void*)&tableColConstructor);
+        gFunctionMap->set(colTag.localName().impl(), (void*)&tableColConstructor);
+        gFunctionMap->set(trTag.localName().impl(), (void*)&tableRowConstructor);
+        gFunctionMap->set(tdTag.localName().impl(), (void*)&tableCellConstructor);
+        gFunctionMap->set(thTag.localName().impl(), (void*)&tableCellConstructor);
+        gFunctionMap->set(theadTag.localName().impl(), (void*)&tableSectionConstructor);
+        gFunctionMap->set(tbodyTag.localName().impl(), (void*)&tableSectionConstructor);
+        gFunctionMap->set(tfootTag.localName().impl(), (void*)&tableSectionConstructor);
+        gFunctionMap->set(brTag.localName().impl(), (void*)&brConstructor);
+        gFunctionMap->set(qTag.localName().impl(), (void*)&quoteConstructor);
+        gFunctionMap->set(marqueeTag.localName().impl(), (void*)&marqueeConstructor);
     }
     
     void* result = gFunctionMap->get(tagName.impl());
index 8925414cf0f9aa0f09fab4139a4816d8924a7c32..bb3b7b74e5c316721b530f169a3a58fe465878cb 100644 (file)
@@ -48,7 +48,7 @@
 #include "xml/dom_textimpl.h"
 #include "xml/dom_nodeimpl.h"
 #include <kxmlcore/FastMalloc.h>
-#include "misc/hashset.h"
+#include <kxmlcore/HashSet.h>
 #include "html/htmltokenizer.h"
 #include "khtmlview.h"
 #include "khtml_part.h"
@@ -57,7 +57,7 @@
 
 #include "rendering/render_object.h"
 
-#include "misc/pointerhash.h"
+#include <kxmlcore/HashMap.h>
 
 #include <kdebug.h>
 #include <klocale.h>
@@ -768,39 +768,39 @@ NodeImpl *HTMLParser::getNode(Token* t)
     // Init our error handling table.
     static FunctionMap gFunctionMap;
     if (gFunctionMap.isEmpty()) {
-        gFunctionMap.insert(textAtom.impl(), &HTMLParser::textCreateErrorCheck);
-        gFunctionMap.insert(commentAtom.impl(), &HTMLParser::commentCreateErrorCheck);
-        gFunctionMap.insert(headTag.localName().impl(), &HTMLParser::headCreateErrorCheck);
-        gFunctionMap.insert(bodyTag.localName().impl(), &HTMLParser::bodyCreateErrorCheck);
-        gFunctionMap.insert(framesetTag.localName().impl(), &HTMLParser::framesetCreateErrorCheck);
-        gFunctionMap.insert(iframeTag.localName().impl(), &HTMLParser::iframeCreateErrorCheck);
-        gFunctionMap.insert(formTag.localName().impl(), &HTMLParser::formCreateErrorCheck);
-        gFunctionMap.insert(isindexTag.localName().impl(), &HTMLParser::isindexCreateErrorCheck);
-        gFunctionMap.insert(selectTag.localName().impl(), &HTMLParser::selectCreateErrorCheck);
-        gFunctionMap.insert(ddTag.localName().impl(), &HTMLParser::ddCreateErrorCheck);
-        gFunctionMap.insert(dtTag.localName().impl(), &HTMLParser::dtCreateErrorCheck);
-        gFunctionMap.insert(liTag.localName().impl(), &HTMLParser::nestedCreateErrorCheck);
-        gFunctionMap.insert(aTag.localName().impl(), &HTMLParser::nestedCreateErrorCheck);
-        gFunctionMap.insert(nobrTag.localName().impl(), &HTMLParser::nestedCreateErrorCheck);
-        gFunctionMap.insert(wbrTag.localName().impl(), &HTMLParser::nestedCreateErrorCheck);
-        gFunctionMap.insert(trTag.localName().impl(), &HTMLParser::nestedCreateErrorCheck);
-        gFunctionMap.insert(tdTag.localName().impl(), &HTMLParser::tableCellCreateErrorCheck);
-        gFunctionMap.insert(thTag.localName().impl(), &HTMLParser::tableCellCreateErrorCheck);
-        gFunctionMap.insert(tbodyTag.localName().impl(), &HTMLParser::tableSectionCreateErrorCheck);
-        gFunctionMap.insert(theadTag.localName().impl(), &HTMLParser::tableSectionCreateErrorCheck);
-        gFunctionMap.insert(tfootTag.localName().impl(), &HTMLParser::tableSectionCreateErrorCheck);
-        gFunctionMap.insert(ttTag.localName().impl(), &HTMLParser::nestedStyleCreateErrorCheck);
-        gFunctionMap.insert(uTag.localName().impl(), &HTMLParser::nestedStyleCreateErrorCheck);
-        gFunctionMap.insert(bTag.localName().impl(), &HTMLParser::nestedStyleCreateErrorCheck);
-        gFunctionMap.insert(iTag.localName().impl(), &HTMLParser::nestedStyleCreateErrorCheck);
-        gFunctionMap.insert(sTag.localName().impl(), &HTMLParser::nestedStyleCreateErrorCheck);
-        gFunctionMap.insert(strikeTag.localName().impl(), &HTMLParser::nestedStyleCreateErrorCheck);
-        gFunctionMap.insert(bigTag.localName().impl(), &HTMLParser::nestedStyleCreateErrorCheck);
-        gFunctionMap.insert(smallTag.localName().impl(), &HTMLParser::nestedStyleCreateErrorCheck);
-        gFunctionMap.insert(noembedTag.localName().impl(), &HTMLParser::noembedCreateErrorCheck);
-        gFunctionMap.insert(noframesTag.localName().impl(), &HTMLParser::noframesCreateErrorCheck);
-        gFunctionMap.insert(noscriptTag.localName().impl(), &HTMLParser::noscriptCreateErrorCheck);
-        gFunctionMap.insert(mapTag.localName().impl(), &HTMLParser::mapCreateErrorCheck);
+        gFunctionMap.set(textAtom.impl(), &HTMLParser::textCreateErrorCheck);
+        gFunctionMap.set(commentAtom.impl(), &HTMLParser::commentCreateErrorCheck);
+        gFunctionMap.set(headTag.localName().impl(), &HTMLParser::headCreateErrorCheck);
+        gFunctionMap.set(bodyTag.localName().impl(), &HTMLParser::bodyCreateErrorCheck);
+        gFunctionMap.set(framesetTag.localName().impl(), &HTMLParser::framesetCreateErrorCheck);
+        gFunctionMap.set(iframeTag.localName().impl(), &HTMLParser::iframeCreateErrorCheck);
+        gFunctionMap.set(formTag.localName().impl(), &HTMLParser::formCreateErrorCheck);
+        gFunctionMap.set(isindexTag.localName().impl(), &HTMLParser::isindexCreateErrorCheck);
+        gFunctionMap.set(selectTag.localName().impl(), &HTMLParser::selectCreateErrorCheck);
+        gFunctionMap.set(ddTag.localName().impl(), &HTMLParser::ddCreateErrorCheck);
+        gFunctionMap.set(dtTag.localName().impl(), &HTMLParser::dtCreateErrorCheck);
+        gFunctionMap.set(liTag.localName().impl(), &HTMLParser::nestedCreateErrorCheck);
+        gFunctionMap.set(aTag.localName().impl(), &HTMLParser::nestedCreateErrorCheck);
+        gFunctionMap.set(nobrTag.localName().impl(), &HTMLParser::nestedCreateErrorCheck);
+        gFunctionMap.set(wbrTag.localName().impl(), &HTMLParser::nestedCreateErrorCheck);
+        gFunctionMap.set(trTag.localName().impl(), &HTMLParser::nestedCreateErrorCheck);
+        gFunctionMap.set(tdTag.localName().impl(), &HTMLParser::tableCellCreateErrorCheck);
+        gFunctionMap.set(thTag.localName().impl(), &HTMLParser::tableCellCreateErrorCheck);
+        gFunctionMap.set(tbodyTag.localName().impl(), &HTMLParser::tableSectionCreateErrorCheck);
+        gFunctionMap.set(theadTag.localName().impl(), &HTMLParser::tableSectionCreateErrorCheck);
+        gFunctionMap.set(tfootTag.localName().impl(), &HTMLParser::tableSectionCreateErrorCheck);
+        gFunctionMap.set(ttTag.localName().impl(), &HTMLParser::nestedStyleCreateErrorCheck);
+        gFunctionMap.set(uTag.localName().impl(), &HTMLParser::nestedStyleCreateErrorCheck);
+        gFunctionMap.set(bTag.localName().impl(), &HTMLParser::nestedStyleCreateErrorCheck);
+        gFunctionMap.set(iTag.localName().impl(), &HTMLParser::nestedStyleCreateErrorCheck);
+        gFunctionMap.set(sTag.localName().impl(), &HTMLParser::nestedStyleCreateErrorCheck);
+        gFunctionMap.set(strikeTag.localName().impl(), &HTMLParser::nestedStyleCreateErrorCheck);
+        gFunctionMap.set(bigTag.localName().impl(), &HTMLParser::nestedStyleCreateErrorCheck);
+        gFunctionMap.set(smallTag.localName().impl(), &HTMLParser::nestedStyleCreateErrorCheck);
+        gFunctionMap.set(noembedTag.localName().impl(), &HTMLParser::noembedCreateErrorCheck);
+        gFunctionMap.set(noframesTag.localName().impl(), &HTMLParser::noframesCreateErrorCheck);
+        gFunctionMap.set(noscriptTag.localName().impl(), &HTMLParser::noscriptCreateErrorCheck);
+        gFunctionMap.set(mapTag.localName().impl(), &HTMLParser::mapCreateErrorCheck);
     }
 
     bool proceed = true;
index c2781a7e7bb649d26da298678b7d0b6300105040..fd5ed756703bb2b4566993bd81c6a89dd9853d11 100644 (file)
@@ -30,9 +30,7 @@
 
 #include "dom_atomicstring.h"
 #include "xml/dom_stringimpl.h"
-#include "misc/hashset.h"
-
-using khtml::HashSet;
+#include <kxmlcore/HashSet.h>
 
 namespace DOM {
    
index ec31e7b368c1a24b2c2fdcd23b0bd0d7ce329173..73cdfd28121fd6179cd69a5b5cecc1cd62af264c 100644 (file)
@@ -22,9 +22,7 @@
 #define KHTML_QNAME_HIDE_GLOBALS 1
 
 #include "dom_qname.h"
-#include "misc/hashset.h"
-
-using khtml::HashSet;
+#include <kxmlcore/HashSet.h>
 
 namespace DOM {
 
index 693594a05957b8205450aacde5716b5120978d53..f1fc77e8c9d7987095bb583e34a7d55612840252 100644 (file)
@@ -95,5 +95,107 @@ public:
     bool _inTable;
 };
 
-};
+}
+
+namespace KXMLCore {
+
+    template<typename T> class DefaultHash;
+
+    template<> struct DefaultHash<DOM::DOMStringImpl *> {
+        static unsigned hash(const DOM::DOMStringImpl *key) { return key->hash(); }
+        static bool equal(const DOM::DOMStringImpl *a, const DOM::DOMStringImpl *b)
+        {
+            if (a == b) return true;
+            if (!a || !b) return false;
+            
+            uint aLength = a->l;
+            uint bLength = b->l;
+            if (aLength != bLength)
+                return false;
+            
+            const uint32_t *aChars = reinterpret_cast<const uint32_t *>(a->s);
+            const uint32_t *bChars = reinterpret_cast<const uint32_t *>(b->s);
+            
+            uint halfLength = aLength >> 1;
+            for (uint i = 0; i != halfLength; ++i) {
+                if (*aChars++ != *bChars++)
+                    return false;
+            }
+            
+            if (aLength & 1 && *reinterpret_cast<const uint16_t *>(aChars) != *reinterpret_cast<const uint16_t *>(bChars))
+                return false;
+            
+            return true;
+        }
+    };
+    
+    class CaseInsensitiveHash {
+    private:
+        // Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
+        static const unsigned PHI = 0x9e3779b9U;
+    public:
+        // Paul Hsieh's SuperFastHash
+        // http://www.azillionmonkeys.com/qed/hash.html
+        static unsigned hash(const DOM::DOMStringImpl *str)
+        {
+            unsigned l = str->l;
+            QChar *s = str->s;
+            uint32_t hash = PHI;
+            uint32_t tmp;
+            
+            int rem = l & 1;
+            l >>= 1;
+            
+            // Main loop
+            for (; l > 0; l--) {
+                hash += s[0].lower().unicode();
+                tmp = (s[1].lower().unicode() << 11) ^ hash;
+                hash = (hash << 16) ^ tmp;
+                s += 2;
+                hash += hash >> 11;
+            }
+            
+            // Handle end case
+            if (rem) {
+                hash += s[0].lower().unicode();
+                hash ^= hash << 11;
+                hash += hash >> 17;
+            }
+            
+            // Force "avalanching" of final 127 bits
+            hash ^= hash << 3;
+            hash += hash >> 5;
+            hash ^= hash << 2;
+            hash += hash >> 15;
+            hash ^= hash << 10;
+            
+            // this avoids ever returning a hash code of 0, since that is used to
+            // signal "hash not computed yet", using a value that is likely to be
+            // effectively the same as 0 when the low bits are masked
+            if (hash == 0)
+                hash = 0x80000000;
+            
+            return hash;
+        }
+        
+        static bool equal(const DOM::DOMStringImpl *a, const DOM::DOMStringImpl *b)
+        {
+            if (a == b) return true;
+            if (!a || !b) return false;
+            uint length = a->l;
+            if (length != b->l)
+                return false;
+            const QChar *as = a->s;
+            const QChar *bs = b->s;
+            for (uint i = 0; i != length; ++i)
+                if (as[i].lower() != bs[i].lower())
+                    return false;
+            return true;
+        }
+    };
+
+}
+
+using KXMLCore::CaseInsensitiveHash;
+
 #endif
index 1964080ee2c7f895d10fe25b035032d8dacdb235..ca635d2ecee687d40db4afd60bb2b31412bc5d9e 100644 (file)
@@ -29,7 +29,7 @@
 #include "html/html_tableimpl.h"
 #include "htmlnames.h"
 #include "misc/loader.h"
-#include "misc/hashmap.h"
+#include <kxmlcore/HashMap.h>
 
 #include "khtmlview.h"
 #include "khtml_part.h"
index e7a42d4015f414ad20a890a8d41170d54245c4f1..4e539b6889268e899caa6f50051836f6b78f5c79 100644 (file)
@@ -45,7 +45,7 @@
 #import "dom_textimpl.h"
 #import "dom_xmlimpl.h"
 #import "html_elementimpl.h"
-#import "hashmap.h"
+#import <kxmlcore/HashMap.h>
 
 #import "khtml_part.h"
 
@@ -93,8 +93,6 @@ using DOM::RangeImpl;
 using DOM::TextImpl;
 using DOM::TreeWalkerImpl;
 
-using khtml::HashMap;
-using khtml::PointerHash;
 using khtml::RenderObject;
 
 @interface DOMAttr (WebCoreInternal)
@@ -2255,7 +2253,7 @@ ObjCEventListener::ObjCEventListener(id <DOMEventListener> listener)
         map = new ListenerMap;
         listenerMap = map;
     }
-    map->insert(listener, this);
+    map->set(listener, this);
 }
 
 ObjCEventListener::~ObjCEventListener()