+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.
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 */,
#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"
#include "regexp_object.h"
#include "string_object.h"
+#include <kxmlcore/HashMap.h>
+
#if WIN32
#include <float.h>
#define copysign(a, b) _copysign(a, b)
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)
globalInit();
}
- InterpreterMap::setInterpreterForGlobalObject(this, glob);
+ interpreterMap().set(glob, this);
global = glob;
dbg = 0;
s_hook = 0L;
globalClear();
}
- InterpreterMap::removeInterpreterForGlobalObject(global);
+ interpreterMap().remove(global);
}
void InterpreterImp::mark()
InterpreterImp *InterpreterImp::interpreterWithGlobalObject(ObjectImp *global)
{
- return InterpreterMap::getInterpreterForGlobalObject(global);
+ return interpreterMap().get(global);
}
+++ /dev/null
-/*
- * 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
+++ /dev/null
-// -*- 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_
--- /dev/null
+// -*- 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
--- /dev/null
+// -*- 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 */
--- /dev/null
+// -*- 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
--- /dev/null
+// -*- 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 */
+
+
--- /dev/null
+/*
+ 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
--- /dev/null
+// -*- 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
--- /dev/null
+// -*- 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
+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
--- /dev/null
+#import <JavaScriptCore/HashMap.h>
--- /dev/null
+#import <JavaScriptCore/HashSet.h>
+++ /dev/null
-#import <hashmap.h>
+++ /dev/null
-#import <hashset.h>
+++ /dev/null
-#import <pointerhash.h>
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 */,
#include <qintcache.h>
#include <stdlib.h>
+#include <kxmlcore/HashMap.h>
+
using namespace DOM;
using namespace HTMLNames;
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;
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);
}
#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>
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
#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;
using DOM::NodeImpl;
using DOM::RangeException;
-using khtml::HashMap;
-using khtml::PointerHash;
-
namespace KJS {
UString DOMObject::toString(ExecState *) const
#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 {
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;
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);
}
#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;
virtual DocumentTypeImpl *doctype() const;
- typedef khtml::HashMap<DOMStringImpl *, int> NameCountMap;
+ typedef HashMap<DOMStringImpl *, int> NameCountMap;
protected:
HTMLElementImpl *bodyElement;
#include "html/htmltokenizer.h"
#include "htmlfactory.h"
-#include "misc/hashset.h"
+#include <kxmlcore/HashSet.h>
#include "editing/visible_text.h"
#include "khtmlview.h"
// 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)
#include <qptrvector.h>
#include <qmemarray.h>
-#include "hashtable.h"
-#include "pointerhash.h"
+#include <kxmlcore/HashMap.h>
class KHTMLView;
class QTextCodec;
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 &);
#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
{
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*)¶graphConstructor);
- 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*)¶mConstructor);
- 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*)"eConstructor);
- 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*)¶graphConstructor);
+ 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*)¶mConstructor);
+ 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*)"eConstructor);
+ gFunctionMap->set(marqueeTag.localName().impl(), (void*)&marqueeConstructor);
}
void* result = gFunctionMap->get(tagName.impl());
#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"
#include "rendering/render_object.h"
-#include "misc/pointerhash.h"
+#include <kxmlcore/HashMap.h>
#include <kdebug.h>
#include <klocale.h>
// 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;
#include "dom_atomicstring.h"
#include "xml/dom_stringimpl.h"
-#include "misc/hashset.h"
-
-using khtml::HashSet;
+#include <kxmlcore/HashSet.h>
namespace DOM {
#define KHTML_QNAME_HIDE_GLOBALS 1
#include "dom_qname.h"
-#include "misc/hashset.h"
-
-using khtml::HashSet;
+#include <kxmlcore/HashSet.h>
namespace DOM {
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
#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"
#import "dom_textimpl.h"
#import "dom_xmlimpl.h"
#import "html_elementimpl.h"
-#import "hashmap.h"
+#import <kxmlcore/HashMap.h>
#import "khtml_part.h"
using DOM::TextImpl;
using DOM::TreeWalkerImpl;
-using khtml::HashMap;
-using khtml::PointerHash;
using khtml::RenderObject;
@interface DOMAttr (WebCoreInternal)
map = new ListenerMap;
listenerMap = map;
}
- map->insert(listener, this);
+ map->set(listener, this);
}
ObjCEventListener::~ObjCEventListener()
git://git.webkit.org / WebKit-https.git / commitdiff