+2006-04-05 Darin Adler <darin@apple.com>
+
+ Reviewed by Maciej.
+
+ - JavaScriptCore part of fix for http://bugzilla.opendarwin.org/show_bug.cgi?id=8049
+ StringImpl hash traits deleted value creates an init routine for WebCore
+ <rdar://problem/4442248> REGRESSION: WebCore has init routines (8049)
+
+ Change HashMap and HashSet implementation so they fold various types together.
+ This allows us to implement maps and sets that use RefPtr<WebCore::StringImpl>
+ and WebCore::String in terms of the underlying raw pointer type, and hence use
+ -1 for the deleted value.
+
+ * kxmlcore/HashTraits.h: Added a new type to HashTraits, StorageTraits, which is a
+ type to be used when storing a value that has the same layout as the type itself.
+ This is used only for non-key cases. In the case of keys, the hash function must also
+ be considered. Moved emptyValue out of GenericHashTraitsBase into GenericHashTraits.
+ Added a new bool to HashTraits, needsRef, which indicates whether the type needs
+ explicit reference counting. If the type itself has needsRef true, but the storage
+ type has needsRef false, then the HashSet or HashMap has to handle the reference
+ counting explicitly. Added hash trait specializations for all signed integer values
+ that give -1 as the deleted value. Gave all integers StorageTraits of the canonical
+ integer type of the same size so int and long will share code. Gave all pointers and
+ RefPtrs StorageTraits of the appropriately sized integer type. Removed redundant
+ TraitType and emptyValue definitions in the pointer specialization for HashTraits.
+ Added PairBaseHashTraits, which doesn't try to set up needsDestruction and deletedValue.
+ Useful for types where we don't want to force the existence of deletedValue, such as
+ the type of a pair in a HashMap which is not the actual storage type. Removed an
+ unneeded parameter from the DeletedValueAssigner template. Added HashKeyStorageTraits
+ template, which determines what type can be used to store a given hash key type with
+ a given hash function, and specialized it for pointers and RefPtr so that pointer
+ hash tables share an underlying HashTable that uses IntHash.
+
+ * kxmlcore/HashTable.h: Added HashTableConstIteratorAdapter, HashTableIteratorAdapter,
+ NeedsRef, RefCountManagerBase, RefCountManager, HashTableRefCountManagerBase, and
+ HashTableRefCountManager. All are used by both HashSet and HashMap to handle hash
+ tables where the type stored is not the same as the real value type.
+
+ * kxmlcore/HashFunctions.h: Added a new struct named IntTypes that finds an
+ integer type given a sizeof value. Renamed pointerHash to intHash and made it
+ use overloading and take integer parameters. Added an IntHash struct which is
+ a hash function that works for integers. Changed PtrHash to call IntHash with
+ an appropriately sized integer. Made IntHash the default hash function for
+ many integer types. Made PtrHash the default hash function for RefPtr as well
+ as for raw pointers.
+
+ * kxmlcore/HashSet.h: Changed implementation to use a separate "storage type"
+ derived from the new traits. The HashTable will use the storage type and all
+ necessary translation and ref/deref is done at the HashSet level. Also reorganized
+ the file so that the HashSet is at the top and has no inline implementation inside
+ it so it's easy to read the interface to HashSet.
+
+ * kxmlcore/HashMap.h: Changed implementation to use a separate "storage type"
+ derived from the new traits. The HashTable will use the storage type and all
+ necessary translation and ref/deref is done at the HashMap level. Also reorganized
+ the file so that the HashMap is at the top and has no inline implementation inside
+ it so it's easy to read the interface to HashMap.
+
+ * kxmlcore/HashMapPtrSpec.h: Removed. Superceded by optimizations in HashMap itself.
+
+ * JavaScriptCore.xcodeproj/project.pbxproj: Remove HashMapPtrSpec.h, resort files,
+ and also remove some unnecessary build settings from the aggregate target that
+ generates derived sources.
+ * JavaScriptCore.vcproj/JavaScriptCore/JavaScriptCore.vcproj: Ditto.
+
2006-04-04 Timothy Hatcher <timothy@apple.com>
Reviewed by Darin.
RelativePath="..\..\kxmlcore\HashMap.h"
>
</File>
- <File
- RelativePath="..\..\kxmlcore\HashMapPtrSpec.h"
- >
- </File>
<File
RelativePath="..\..\kxmlcore\HashSet.h"
>
buildPhases = (
65FB3F6509D11E9100F49DEB /* Generate Derived Sources */,
);
- buildSettings = {
- PRODUCT_NAME = "Generate Derived Sources";
- };
- dependencies = (
- );
name = "Derived Sources";
- productName = "Generate Derived Sources";
+ productName = "Derived Sources";
};
932F5BE30822A1C700736975 /* All */ = {
isa = PBXAggregateTarget;
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, ); }; };
657EEBC0094E445E008C9C7B /* HashCountedSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 657EEBBF094E445E008C9C7B /* HashCountedSet.h */; settings = {ATTRIBUTES = (Private, ); }; };
6541BD6F08E80A17002CBEE7 /* TCSpinLock.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = TCSpinLock.h; sourceTree = "<group>"; tabWidth = 8; };
6541BD7008E80A17002CBEE7 /* TCSystemAlloc.cpp */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.cpp.cpp; path = TCSystemAlloc.cpp; sourceTree = "<group>"; tabWidth = 8; };
6541BD7108E80A17002CBEE7 /* TCSystemAlloc.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = TCSystemAlloc.h; sourceTree = "<group>"; tabWidth = 8; };
- 6557E8F708EA5D4D0049CDFC /* HashMapPtrSpec.h */ = {isa = PBXFileReference; fileEncoding = 30; indentWidth = 4; lastKnownFileType = sourcecode.c.h; path = HashMapPtrSpec.h; sourceTree = "<group>"; tabWidth = 8; };
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; indentWidth = 4; lastKnownFileType = sourcecode.cpp.cpp; path = property_slot.cpp; sourceTree = "<group>"; tabWidth = 8; };
65162EF108E6A21C007556CD /* kxmlcore */ = {
isa = PBXGroup;
children = (
- 65D6D87E09B5A32E0002E4D7 /* Platform.h */,
93AA4F770957251F0084B3A7 /* AlwaysInline.h */,
- 65E217B708E7EECC0023E5F6 /* Assertions.h */,
65E217B808E7EECC0023E5F6 /* Assertions.cpp */,
+ 65E217B708E7EECC0023E5F6 /* Assertions.h */,
65E217B908E7EECC0023E5F6 /* FastMalloc.cpp */,
65E217BA08E7EECC0023E5F6 /* FastMalloc.h */,
65D7D19B08F10B5B0015ABD8 /* FastMallocInternal.h */,
657EEBBF094E445E008C9C7B /* HashCountedSet.h */,
65DFC92A08EA173A00F7300B /* HashFunctions.h */,
65DFC92B08EA173A00F7300B /* HashMap.h */,
- 6557E8F708EA5D4D0049CDFC /* HashMapPtrSpec.h */,
65DFC92C08EA173A00F7300B /* HashSet.h */,
65DFC92D08EA173A00F7300B /* HashTable.cpp */,
65DFC92E08EA173A00F7300B /* HashTable.h */,
9303F5A409911A5800AD71B8 /* OwnArrayPtr.h */,
9303F567099118FA00AD71B8 /* OwnPtr.h */,
6580F795094070560082C219 /* PassRefPtr.h */,
+ 65D6D87E09B5A32E0002E4D7 /* Platform.h */,
65C647B3093EF8D60022C380 /* RefPtr.h */,
6541BD6E08E80A17002CBEE7 /* TCPageMap.h */,
6541BD6F08E80A17002CBEE7 /* TCSpinLock.h */,
65DFC93208EA173A00F7300B /* HashSet.h in Headers */,
65DFC93408EA173A00F7300B /* HashTable.h in Headers */,
65DFC93508EA173A00F7300B /* HashTraits.h in Headers */,
- 6557E8F808EA5D4D0049CDFC /* HashMapPtrSpec.h in Headers */,
65D7D19C08F10B5B0015ABD8 /* FastMallocInternal.h in Headers */,
65EA4C9C092AF9E20093D800 /* JSLock.h in Headers */,
65C647B4093EF8D60022C380 /* RefPtr.h in Headers */,
65FB3F7809D11EBD00F49DEB /* Debug */ = {
isa = XCBuildConfiguration;
buildSettings = {
- COPY_PHASE_STRIP = NO;
- GCC_DYNAMIC_NO_PIC = NO;
- GCC_GENERATE_DEBUGGING_SYMBOLS = YES;
- GCC_OPTIMIZATION_LEVEL = 0;
PRODUCT_NAME = "Generate Derived Sources";
};
name = Debug;
65FB3F7909D11EBD00F49DEB /* Release */ = {
isa = XCBuildConfiguration;
buildSettings = {
- COPY_PHASE_STRIP = YES;
- GCC_ENABLE_FIX_AND_CONTINUE = NO;
- GCC_GENERATE_DEBUGGING_SYMBOLS = NO;
PRODUCT_NAME = "Generate Derived Sources";
- ZERO_LINK = NO;
};
name = Release;
};
// -*- mode: c++; c-basic-offset: 4 -*-
/*
* This file is part of the KDE libraries
- * Copyright (C) 2005 Apple Computer, Inc.
+ * Copyright (C) 2005, 2006 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
#ifndef KXMLCORE_HASH_FUNCTIONS_H
#define KXMLCORE_HASH_FUNCTIONS_H
-#include <stdint.h>
-
#include "RefPtr.h"
+#include <stdint.h>
namespace KXMLCore {
- template<typename T> class DefaultHash;
+ template<size_t size> struct IntTypes;
+ template<> struct IntTypes<1> { typedef int8_t SignedType; typedef uint8_t UnsignedType; };
+ template<> struct IntTypes<2> { typedef int16_t SignedType; typedef uint16_t UnsignedType; };
+ template<> struct IntTypes<4> { typedef int32_t SignedType; typedef uint32_t UnsignedType; };
+ template<> struct IntTypes<8> { typedef int64_t SignedType; typedef uint64_t UnsignedType; };
- template<int size> unsigned pointerHash(void *pointer);
+ // integer hash function
- // Thomas Wang's 32 bit mix
- // http://www.cris.com/~Ttwang/tech/inthash.htm
- template<> inline unsigned pointerHash<4>(void *pointer)
+ // Thomas Wang's 32 Bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
+ inline unsigned intHash(uint32_t key)
{
- uint32_t key = static_cast<uint32_t>(reinterpret_cast<uintptr_t>(pointer));
key += ~(key << 15);
key ^= (key >> 10);
key += (key << 3);
return key;
}
- // Thomas Wang's 64 bit mix
- // http://www.cris.com/~Ttwang/tech/inthash.htm
- template<> inline unsigned pointerHash<8>(void *pointer)
+ // Thomas Wang's 64 bit Mix Function: http://www.cris.com/~Ttwang/tech/inthash.htm
+ inline unsigned intHash(uint64_t key)
{
- uint64_t key = reinterpret_cast<uint64_t>(pointer);
key += ~(key << 32);
key ^= (key >> 22);
key += ~(key << 13);
return key;
}
- // pointer identity hash - default for pointer types that don't
- // explicitly specialize otherwise; also should work for integer
- // types
- template<typename T> struct PtrHash {
- static unsigned hash(T key) { return pointerHash<sizeof(void *)>((void *)key); }
+ template<typename T> struct IntHash {
+ static unsigned hash(T key) { return intHash(static_cast<typename IntTypes<sizeof(T)>::UnsignedType>(key)); }
static bool equal(T a, T b) { return a == b; }
};
+ // pointer identity hash function
+
+ template<typename T> struct PtrHash {
+ static unsigned hash(T key) { return IntHash<uintptr_t>::hash(reinterpret_cast<uintptr_t>(key)); }
+ static bool equal(T a, T b) { return a == b; }
+ };
template<typename P> struct PtrHash<RefPtr<P> > {
- static unsigned hash(const RefPtr<P>& key) { return pointerHash<sizeof(void *)>((void *)key.get()); }
+ static unsigned hash(const RefPtr<P>& key) { return PtrHash<P*>::hash(key.get()); }
static bool equal(const RefPtr<P>& a, const RefPtr<P>& b) { return a == b; }
};
- template<typename P> struct DefaultHash<P *> {
- typedef PtrHash<P *> Hash;
- };
+ // default hash function for each type
+
+ template<typename T> struct DefaultHash;
+
+ // make IntHash the default hash function for many integer types
+
+ template<> struct DefaultHash<int> { typedef IntHash<unsigned> Hash; };
+ template<> struct DefaultHash<unsigned> { typedef IntHash<unsigned> Hash; };
+ template<> struct DefaultHash<long> { typedef IntHash<unsigned long> Hash; };
+ template<> struct DefaultHash<unsigned long> { typedef IntHash<unsigned long> Hash; };
+ template<> struct DefaultHash<long long> { typedef IntHash<unsigned long long> Hash; };
+ template<> struct DefaultHash<unsigned long long> { typedef IntHash<unsigned long long> Hash; };
+
+ // make PtrHash the default hash function for pointer types that don't specialize
+
+ template<typename P> struct DefaultHash<P*> { typedef PtrHash<P*> Hash; };
+ template<typename P> struct DefaultHash<RefPtr<P> > { typedef PtrHash<RefPtr<P> > Hash; };
- template<> struct DefaultHash<int> {
- typedef PtrHash<int> Hash;
- };
-
} // namespace KXMLCore
using KXMLCore::DefaultHash;
+using KXMLCore::IntHash;
using KXMLCore::PtrHash;
#endif // KXLMCORE_HASH_FUNCTIONS_H
#define KXMLCORE_HASH_MAP_H
#include "HashTable.h"
-#include "HashTraits.h"
-#include "HashFunctions.h"
namespace KXMLCore {
-template<typename Key, typename Mapped>
-class PairFirstExtractor
-{
- typedef pair<Key, Mapped> ValueType;
-
-public:
- static const Key& extract(const ValueType& value)
+ template<typename PairType> struct PairFirstExtractor;
+
+ template<typename KeyArg, typename MappedArg, typename HashArg = typename DefaultHash<KeyArg>::Hash,
+ typename KeyTraitsArg = HashTraits<KeyArg>, typename MappedTraitsArg = HashTraits<MappedArg> > class HashMap {
+ private:
+ typedef KeyTraitsArg KeyTraits;
+ typedef MappedTraitsArg MappedTraits;
+ typedef PairBaseHashTraits<KeyTraits, MappedTraits> ValueTraits;
+
+ public:
+ typedef typename KeyTraits::TraitType KeyType;
+ typedef typename MappedTraits::TraitType MappedType;
+ typedef typename ValueTraits::TraitType ValueType;
+
+ private:
+ typedef HashArg HashFunctions;
+
+ typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Hash StorageHashFunctions;
+
+ typedef typename HashKeyStorageTraits<HashFunctions, KeyTraits>::Traits KeyStorageTraits;
+ typedef typename MappedTraits::StorageTraits MappedStorageTraits;
+ typedef PairHashTraits<KeyStorageTraits, MappedStorageTraits> ValueStorageTraits;
+
+ typedef typename KeyStorageTraits::TraitType KeyStorageType;
+ typedef typename MappedStorageTraits::TraitType MappedStorageType;
+ typedef typename ValueStorageTraits::TraitType ValueStorageType;
+
+ typedef HashTable<KeyStorageType, ValueStorageType, PairFirstExtractor<ValueStorageType>,
+ StorageHashFunctions, ValueStorageTraits, KeyStorageTraits> HashTableType;
+
+ public:
+ typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
+ typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
+
+ HashMap();
+ HashMap(const HashMap&);
+ HashMap& operator=(const HashMap&);
+ ~HashMap();
+
+ int size() const;
+ int capacity() const;
+ bool isEmpty() const;
+
+ // iterators iterate over pairs of keys and values
+ iterator begin();
+ iterator end();
+ const_iterator begin() const;
+ const_iterator end() const;
+
+ iterator find(const KeyType&);
+ const_iterator find(const KeyType&) const;
+ bool contains(const KeyType&) const;
+ MappedType get(const KeyType&) const;
+
+ // replaces value but not key if key is already present
+ // return value is a pair of the iterator to the key location,
+ // and a boolean that's true if a new value was actually added
+ pair<iterator, bool> set(const KeyType&, const MappedType&);
+
+ // does nothing if key is already present
+ // return value is a pair of the iterator to the key location,
+ // and a boolean that's true if a new value was actually added
+ pair<iterator, bool> add(const KeyType&, const MappedType&);
+
+ void remove(const KeyType&);
+ void remove(iterator it);
+ void clear();
+
+ private:
+ pair<iterator, bool> inlineAdd(const KeyType&, const MappedType&);
+ void refAll();
+ void derefAll();
+
+ HashTableType m_impl;
+ };
+
+ template<typename PairType> struct PairFirstExtractor {
+ static const typename PairType::first_type& extract(const PairType& p) { return p.first; }
+ };
+
+ template<bool canReplaceDeletedKey, typename ValueType, typename ValueStorageTraits, typename HashFunctions>
+ struct HashMapTranslator;
+
+ template<typename ValueType, typename ValueStorageTraits, typename HashFunctions>
+ struct HashMapTranslator<true, ValueType, ValueStorageTraits, HashFunctions> {
+ typedef typename ValueType::first_type KeyType;
+ typedef typename ValueType::second_type MappedType;
+ typedef typename ValueStorageTraits::TraitType ValueStorageType;
+ typedef typename ValueStorageTraits::FirstTraits KeyStorageTraits;
+ typedef typename KeyStorageTraits::TraitType KeyStorageType;
+
+ static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
+ static bool equal(const KeyStorageType& a, const KeyType& b) { return HashFunctions::equal(*(KeyType*)&a, b); }
+ static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped, unsigned)
+ {
+ *(KeyType*)&location.first = key;
+ *(MappedType*)&location.second = mapped;
+ }
+ };
+
+ template<typename ValueType, typename ValueStorageTraits, typename HashFunctions>
+ struct HashMapTranslator<false, ValueType, ValueStorageTraits, HashFunctions> {
+ typedef typename ValueType::first_type KeyType;
+ typedef typename ValueType::second_type MappedType;
+ typedef typename ValueStorageTraits::TraitType ValueStorageType;
+ typedef typename ValueStorageTraits::FirstTraits KeyStorageTraits;
+ typedef typename KeyStorageTraits::TraitType KeyStorageType;
+
+ static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
+ static bool equal(const KeyStorageType& a, const KeyType& b) { return HashFunctions::equal(*(KeyType*)&a, b); }
+ static void translate(ValueStorageType& location, const KeyType& key, const MappedType& mapped, unsigned)
+ {
+ if (location.first == KeyStorageTraits::deletedValue())
+ location.first = KeyStorageTraits::emptyValue();
+ *(KeyType*)&location.first = key;
+ *(MappedType*)&location.second = mapped;
+ }
+ };
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline void HashMap<T, U, V, W, X>::refAll()
+ {
+ HashTableRefCounter<HashTableType, ValueTraits>::refAll(m_impl);
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline void HashMap<T, U, V, W, X>::derefAll()
+ {
+ HashTableRefCounter<HashTableType, ValueTraits>::derefAll(m_impl);
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline HashMap<T, U, V, W, X>::HashMap()
+ {
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline HashMap<T, U, V, W, X>::HashMap(const HashMap& other)
+ : m_impl(other.m_impl)
+ {
+ refAll();
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline HashMap<T, U, V, W, X>& HashMap<T, U, V, W, X>::operator=(const HashMap& other)
+ {
+ HashMap tmp(other);
+ m_impl.swap(tmp.m_impl);
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline HashMap<T, U, V, W, X>::~HashMap()
+ {
+ derefAll();
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline int HashMap<T, U, V, W, X>::size() const
+ {
+ return m_impl.size();
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline int HashMap<T, U, V, W, X>::capacity() const
{
- return value.first;
- }
-};
-
-template<typename Key, typename Mapped, typename HashFunctions>
-class HashMapTranslator
-{
- typedef pair<Key, Mapped> ValueType;
-
-public:
- static unsigned hash(const Key& key)
- {
- return HashFunctions::hash(key);
- }
-
- static bool equal(const Key& a, const Key& b)
- {
- return HashFunctions::equal(a, b);
- }
-
- static void translate(ValueType& location, const Key& key, const Mapped& mapped, unsigned)
- {
- ValueType tmp(key, mapped);
- swap(tmp, location);
- }
-};
-
-
-template<typename Key, typename Mapped, typename HashFunctions = typename DefaultHash<Key>::Hash, typename KeyTraits = HashTraits<Key>, typename MappedTraits = HashTraits<Mapped> >
-class HashMap {
- public:
- typedef Key KeyType;
- typedef Mapped MappedType;
- typedef pair<Key, Mapped> ValueType;
- typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits;
- private:
- typedef HashTable<KeyType, ValueType, PairFirstExtractor<KeyType, MappedType>, HashFunctions, ValueTraits, KeyTraits> ImplType;
- typedef HashMapTranslator<Key, Mapped, HashFunctions> TranslatorType;
- public:
- typedef typename ImplType::iterator iterator;
- typedef typename ImplType::const_iterator const_iterator;
-
- HashMap() {}
-
- int size() const;
- int capacity() const;
- bool isEmpty() const;
-
- // iterators iterate over pairs of keys and values
- 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
- // return value is a pair of the iterator to the key location,
- // and a boolean that's true if a new value was actually added
- pair<iterator, bool> set(const KeyType &key, const MappedType &mapped);
-
- // does nothing if key is already present
- // return value is a pair of the iterator to the key location,
- // and a boolean that's true if a new value was actually added
- pair<iterator, bool> add(const KeyType &key, const MappedType &mapped);
-
- void remove(const KeyType& key);
- void remove(iterator it);
- void clear();
-
- private:
- pair<iterator, bool> inlineAdd(const KeyType &key, const MappedType &mapped);
-
- 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>
-pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::inlineAdd(const KeyType &key, const MappedType &mapped)
-{
- return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::set(const KeyType &key, const MappedType &mapped)
-{
- pair<iterator, bool> result = inlineAdd(key, mapped);
- // the add call above won't change anything if the key is
- // already there; in that case, make sure to set the value.
- if (!result.second)
- result.first->second = mapped;
- return result;
-}
-
-template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::add(const KeyType &key, const MappedType &mapped)
-{
- return inlineAdd(key, mapped);
-}
-
-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 Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-void deleteAllValues(HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>& collection)
-{
- typedef HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits> T;
- typename T::iterator end = collection.end();
- for (typename T::iterator it = collection.begin(); it != end; ++it)
- delete it->second;
-}
+ return m_impl.capacity();
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline bool HashMap<T, U, V, W, X>::isEmpty() const
+ {
+ return m_impl.isEmpty();
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::begin()
+ {
+ return m_impl.begin();
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::end()
+ {
+ return m_impl.end();
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::begin() const
+ {
+ return m_impl.begin();
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::end() const
+ {
+ return m_impl.end();
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline typename HashMap<T, U, V, W, X>::iterator HashMap<T, U, V, W, X>::find(const KeyType& key)
+ {
+ return m_impl.find(*(const KeyStorageType*)&key);
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline typename HashMap<T, U, V, W, X>::const_iterator HashMap<T, U, V, W, X>::find(const KeyType& key) const
+ {
+ return m_impl.find(*(const KeyStorageType*)&key);
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline bool HashMap<T, U, V, W, X>::contains(const KeyType& key) const
+ {
+ return m_impl.contains(*(const KeyStorageType*)&key);
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline pair<typename HashMap<T, U, V, W, X>::iterator, bool>
+ HashMap<T, U, V, W, X>::inlineAdd(const KeyType& key, const MappedType& mapped)
+ {
+ const bool canReplaceDeletedKey = !KeyTraits::needsDestruction || KeyStorageTraits::needsDestruction;
+ typedef HashMapTranslator<canReplaceDeletedKey, ValueType, ValueStorageTraits, HashFunctions> TranslatorType;
+ return m_impl.template add<KeyType, MappedType, TranslatorType>(key, mapped);
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ pair<typename HashMap<T, U, V, W, X>::iterator, bool>
+ HashMap<T, U, V, W, X>::set(const KeyType& key, const MappedType& mapped)
+ {
+ pair<iterator, bool> result = inlineAdd(key, mapped);
+ if (!result.second)
+ // add call above didn't change anything, so set the mapped value
+ result.first->second = mapped;
+ return result;
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ pair<typename HashMap<T, U, V, W, X>::iterator, bool>
+ HashMap<T, U, V, W, X>::add(const KeyType& key, const MappedType& mapped)
+ {
+ return inlineAdd(key, mapped);
+ }
+
+ template<typename T, typename U, typename V, typename W, typename MappedTraits>
+ inline typename HashMap<T, U, V, W, MappedTraits>::MappedType
+ HashMap<T, U, V, W, MappedTraits>::get(const KeyType& key) const
+ {
+ const_iterator it = find(key);
+ if (it == end())
+ return MappedTraits::emptyValue();
+ return it->second;
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline void HashMap<T, U, V, W, X>::remove(iterator it)
+ {
+ if (it.m_impl == m_impl.end())
+ return;
+ it->~ValueType();
+ m_impl.remove(it.m_impl);
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline void HashMap<T, U, V, W, X>::remove(const KeyType& key)
+ {
+ remove(find(key));
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline void HashMap<T, U, V, W, X>::clear()
+ {
+ derefAll();
+ m_impl.clear();
+ }
+
+ template<typename MappedType, typename HashTableType>
+ void deleteAllPairSeconds(HashTableType& collection)
+ {
+ typedef typename HashTableType::iterator iterator;
+ iterator end = collection.end();
+ for (iterator it = collection.begin(); it != end; ++it)
+ delete *(MappedType*)&it->second;
+ }
+
+ template<typename T, typename U, typename V, typename W, typename X>
+ inline void deleteAllValues(HashMap<T, U, V, W, X>& collection)
+ {
+ deleteAllPairSeconds<typename HashMap<T, U, V, W, X>::MappedType>(collection);
+ }
} // 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., 51 Franklin Street, Fifth Floor,
- * Boston, MA 02110-1301, 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 {
-
- struct VoidPtrHash : public PtrHash<void *>
- {
- };
-
- template<typename P, typename Mapped> class PtrHashConstIteratorAdapter;
-
- template<typename P, typename Mapped>
- class PtrHashIteratorAdapter {
- private:
- typedef HashMap<P *, Mapped, PtrHash<P *>, HashTraits<P *>, HashTraits<Mapped> > MapType;
- typedef typename MapType::ValueType ValueType;
- typedef typename MapType::ImplValueType ImplValueType;
- typedef typename HashMap<P *, Mapped, PtrHash<P *>, HashTraits<P *>, HashTraits<Mapped> >::ImplIterator ImplIterator;
- typedef PtrHashIteratorAdapter<P, Mapped> iterator;
- typedef ValueType& ReferenceType;
- typedef ValueType *PointerType;
-
- friend class HashMap<P *, Mapped, PtrHash<P *>, HashTraits<P *>, HashTraits<Mapped> >;
- friend class PtrHashConstIteratorAdapter<P, Mapped>;
-
- public:
- PtrHashIteratorAdapter() {}
- PtrHashIteratorAdapter(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 PtrHashConstIteratorAdapter {
- private:
- typedef HashMap<P *, Mapped, PtrHash<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 PtrHashIteratorAdapter<P, Mapped> iterator;
- typedef PtrHashConstIteratorAdapter<P, Mapped> const_iterator;
- typedef const ValueType& ReferenceType;
- typedef const ValueType *PointerType;
-
- friend class HashMap<P *, Mapped, PtrHash<P *>, HashTraits<P *>, HashTraits<Mapped> >;
-
- public:
- PtrHashConstIteratorAdapter() {}
- PtrHashConstIteratorAdapter(const ImplConstIterator &impl) : m_impl(impl) {}
- PtrHashConstIteratorAdapter(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*()); }
-
- const_iterator& operator++()
- {
- ++m_impl;
- return *this;
- }
-
- // postfix ++ intentionally omitted
-
- // Comparison.
- bool operator==(const const_iterator& other) const
- {
- return m_impl == other.m_impl;
- }
-
- bool operator!=(const const_iterator& other) const
- {
- return m_impl != other.m_impl;
- }
-
- private:
- ImplConstIterator m_impl;
- };
-
- template<typename P, typename Mapped>
- class HashMap<P *, Mapped, PtrHash<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, VoidPtrHash, HashTraits<void *>, HashTraits<Mapped> > ImplType;
- public:
- typedef typename ImplType::ValueType ImplValueType;
- typedef typename ImplType::iterator ImplIterator;
- typedef typename ImplType::const_iterator ImplConstIterator;
- typedef PtrHashIteratorAdapter<P, Mapped> iterator;
- typedef PtrHashConstIteratorAdapter<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((void *)(key)); }
- const_iterator find(const KeyType& key) const { return m_impl.find((void *)(key)); }
- bool contains(const KeyType& key) const { return m_impl.contains((void *)(key)); }
- MappedType get(const KeyType &key) const { return m_impl.get((void *)(key)); }
-
- std::pair<iterator, bool> set(const KeyType &key, const MappedType &mapped)
- { return m_impl.set((void *)(key), mapped); }
-
- std::pair<iterator, bool> add(const KeyType &key, const MappedType &mapped)
- { return m_impl.add((void *)(key), mapped); }
-
- void remove(const KeyType& key) { m_impl.remove((void *)(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 *, PtrHash<P *>, HashTraits<P *>, HashTraits<Q *> > {
- private:
- // important not to use PtrHash here or instantiation would recurse
- typedef HashMap<void *, void *, VoidPtrHash, 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, PairFirstExtractor<void *, void*>, VoidPtrHash, PairHashTraits<HashTraits<void *>, HashTraits<void *> >, HashTraits<void *> > ImplIterator;
- typedef HashTableConstIterator<void *, ImplValueType, PairFirstExtractor<void *, void*>, VoidPtrHash, PairHashTraits<HashTraits<void *>, HashTraits<void *> >, HashTraits<void *> > ImplConstIterator;
-
- typedef PtrHashIteratorAdapter<P, Q *> iterator;
- typedef PtrHashConstIteratorAdapter<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((void *)(key)); }
- const_iterator find(const KeyType& key) const { return m_impl.find((void *)(key)); }
- bool contains(const KeyType& key) const { return m_impl.contains((void *)(key)); }
- MappedType get(const KeyType &key) const { return reinterpret_cast<MappedType>(m_impl.get((void *)(key))); }
-
- std::pair<iterator, bool> set(const KeyType &key, const MappedType &mapped)
- { return m_impl.set((void *)(key), (void *)(mapped)); }
-
- std::pair<iterator, bool> add(const KeyType &key, const MappedType &mapped)
- { return m_impl.add((void *)(key), (void *)(mapped)); }
-
- void remove(const KeyType& key) { m_impl.remove((void *)(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
#define KXMLCORE_HASH_SET_H
#include "HashTable.h"
-#include "HashTraits.h"
-#include "HashFunctions.h"
namespace KXMLCore {
- template <typename T>
- struct IdentityExtractor
- {
- static const T& extract(const T& t)
- {
- return t;
- }
- };
+ template<typename T> struct IdentityExtractor;
- template<typename Value, typename T, typename HashSetTranslator>
- struct HashSetTranslatorAdapter
- {
- static unsigned hash(const T& key)
- {
- return HashSetTranslator::hash(key);
- }
-
- static bool equal(const Value& a, const T& b)
- {
- return HashSetTranslator::equal(a, b);
- }
-
- static void translate(Value& location, const T& key, const T&, unsigned hashCode)
- {
- HashSetTranslator::translate(location, key, hashCode);
- }
- };
-
- template<typename Value, typename HashFunctions = typename DefaultHash<Value>::Hash, typename Traits = HashTraits<Value> >
- class HashSet {
+ template<typename Value, typename HashFunctions, typename Traits> class HashSet;
+ template<typename Value, typename HashFunctions, typename Traits>
+ void deleteAllValues(HashSet<Value, HashFunctions, Traits>&);
+
+ template<typename ValueArg, typename HashArg = typename DefaultHash<ValueArg>::Hash,
+ typename TraitsArg = HashTraits<ValueArg> > class HashSet {
private:
- typedef HashTable<Value, Value, IdentityExtractor<Value>, HashFunctions, Traits, Traits> ImplType;
+ typedef HashArg HashFunctions;
+ typedef TraitsArg ValueTraits;
+
+ typedef typename HashKeyStorageTraits<HashFunctions, ValueTraits>::Hash StorageHashFunctions;
+
+ typedef typename HashKeyStorageTraits<HashFunctions, ValueTraits>::Traits StorageTraits;
+ typedef typename StorageTraits::TraitType StorageType;
+
+ typedef HashTable<StorageType, StorageType, IdentityExtractor<StorageType>,
+ StorageHashFunctions, StorageTraits, StorageTraits> HashTableType;
+
public:
- typedef Value ValueType;
- typedef typename ImplType::iterator iterator;
- typedef typename ImplType::const_iterator const_iterator;
-
- HashSet() {}
-
+ typedef typename ValueTraits::TraitType ValueType;
+ typedef HashTableIteratorAdapter<HashTableType, ValueType> iterator;
+ typedef HashTableConstIteratorAdapter<HashTableType, ValueType> const_iterator;
+
+ HashSet();
+ HashSet(const HashSet&);
+ HashSet& operator=(const HashSet&);
+ ~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;
-
+
+ iterator find(const ValueType&);
+ const_iterator find(const ValueType&) const;
+ bool contains(const ValueType&) const;
+
// the return value is a pair of an interator to the new value's location,
// and a bool that is true if an new entry was added
- std::pair<iterator, bool> add(const ValueType &value);
-
+ pair<iterator, bool> add(const ValueType&);
+
// a special version of add() 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. HashTranslator should have the following methods:
// static unsigned hash(const T&);
// static bool equal(const ValueType&, const T&);
// static translate(ValueType&, const T&, unsigned hashCode);
- template<typename T, typename HashTranslator>
- std::pair<iterator, bool> add(const T& value);
-
- void remove(const ValueType& value);
- void remove(iterator it);
+ template<typename T, typename HashTranslator> pair<iterator, bool> add(const T&);
+
+ void remove(const ValueType&);
+ void remove(iterator);
void clear();
-
+
private:
- ImplType m_impl;
+ void refAll();
+ void derefAll();
+
+ friend void deleteAllValues<>(HashSet&);
+
+ HashTableType m_impl;
};
-
- template<typename Value, typename HashFunctions, typename Traits>
- inline int HashSet<Value, HashFunctions, Traits>::size() const
+
+ template<typename T> struct IdentityExtractor {
+ static const T& extract(const T& t) { return t; }
+ };
+
+ template<bool canReplaceDeletedValue, typename ValueType, typename StorageTraits, typename HashFunctions>
+ struct HashSetTranslator;
+
+ template<typename ValueType, typename StorageTraits, typename HashFunctions>
+ struct HashSetTranslator<true, ValueType, StorageTraits, HashFunctions> {
+ typedef typename StorageTraits::TraitType StorageType;
+ static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
+ static bool equal(const StorageType& a, const ValueType& b) { return HashFunctions::equal(*(const ValueType*)&a, b); }
+ static void translate(StorageType& location, const ValueType& key, const ValueType&, unsigned)
+ {
+ *(ValueType*)&location = key;
+ }
+ };
+
+ template<typename ValueType, typename StorageTraits, typename HashFunctions>
+ struct HashSetTranslator<false, ValueType, StorageTraits, HashFunctions> {
+ typedef typename StorageTraits::TraitType StorageType;
+ static unsigned hash(const ValueType& key) { return HashFunctions::hash(key); }
+ static bool equal(const StorageType& a, const ValueType& b) { return HashFunctions::equal(*(const ValueType*)&a, b); }
+ static void translate(StorageType& location, const ValueType& key, const ValueType&, unsigned)
+ {
+ if (location == StorageTraits::deletedValue())
+ location = StorageTraits::emptyValue();
+ *(ValueType*)&location = key;
+ }
+ };
+
+ template<bool canReplaceDeletedValue, typename ValueType, typename StorageTraits, typename T, typename Translator>
+ struct HashSetTranslatorAdapter;
+
+ template<typename ValueType, typename StorageTraits, typename T, typename Translator>
+ struct HashSetTranslatorAdapter<true, ValueType, StorageTraits, T, Translator> {
+ typedef typename StorageTraits::TraitType StorageType;
+ static unsigned hash(const T& key) { return Translator::hash(key); }
+ static bool equal(const StorageType& a, const T& b) { return Translator::equal(*(const ValueType*)&a, b); }
+ static void translate(StorageType& location, const T& key, const T&, unsigned hashCode)
+ {
+ Translator::translate(*(ValueType*)&location, key, hashCode);
+ }
+ };
+
+ template<typename ValueType, typename StorageTraits, typename T, typename Translator>
+ struct HashSetTranslatorAdapter<false, ValueType, StorageTraits, T, Translator> {
+ typedef typename StorageTraits::TraitType StorageType;
+ static unsigned hash(const T& key) { return Translator::hash(key); }
+ static bool equal(const StorageType& a, const T& b) { return Translator::equal(*(const ValueType*)&a, b); }
+ static void translate(StorageType& location, const T& key, const T&, unsigned hashCode)
+ {
+ if (location == StorageTraits::deletedValue())
+ location = StorageTraits::emptyValue();
+ Translator::translate(*(ValueType*)&location, key, hashCode);
+ }
+ };
+
+ template<typename T, typename U, typename V>
+ inline void HashSet<T, U, V>::refAll()
+ {
+ HashTableRefCounter<HashTableType, ValueTraits>::refAll(m_impl);
+ }
+
+ template<typename T, typename U, typename V>
+ inline void HashSet<T, U, V>::derefAll()
+ {
+ HashTableRefCounter<HashTableType, ValueTraits>::derefAll(m_impl);
+ }
+
+ template<typename T, typename U, typename V>
+ inline HashSet<T, U, V>::HashSet()
+ {
+ }
+
+ template<typename T, typename U, typename V>
+ inline HashSet<T, U, V>::HashSet(const HashSet& other)
+ : m_impl(other.m_impl)
+ {
+ refAll();
+ }
+
+ template<typename T, typename U, typename V>
+ inline HashSet<T, U, V>& HashSet<T, U, V>::operator=(const HashSet& other)
+ {
+ HashSet tmp(other);
+ m_impl.swap(tmp.m_impl);
+ }
+
+ template<typename T, typename U, typename V>
+ inline HashSet<T, U, V>::~HashSet()
+ {
+ derefAll();
+ }
+
+ template<typename T, typename U, typename V>
+ inline int HashSet<T, U, V>::size() const
{
return m_impl.size();
}
-
- template<typename Value, typename HashFunctions, typename Traits>
- int HashSet<Value, HashFunctions, Traits>::capacity() const
+
+ template<typename T, typename U, typename V>
+ inline int HashSet<T, U, V>::capacity() const
{
return m_impl.capacity();
}
-
- template<typename Value, typename HashFunctions, typename Traits>
- inline bool HashSet<Value, HashFunctions, Traits>::isEmpty() const
+
+ template<typename T, typename U, typename V>
+ inline bool HashSet<T, U, V>::isEmpty() const
{
- return size() == 0;
+ return m_impl.isEmpty();
}
-
- template<typename Value, typename HashFunctions, typename Traits>
- inline typename HashSet<Value, HashFunctions, Traits>::iterator HashSet<Value, HashFunctions, Traits>::begin()
+
+ template<typename T, typename U, typename V>
+ inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::begin()
{
return m_impl.begin();
}
- template<typename Value, typename HashFunctions, typename Traits>
- inline typename HashSet<Value, HashFunctions, Traits>::iterator HashSet<Value, HashFunctions, Traits>::end()
+ template<typename T, typename U, typename V>
+ inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::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
+
+ template<typename T, typename U, typename V>
+ inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::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
+
+ template<typename T, typename U, typename V>
+ inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::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)
+
+ template<typename T, typename U, typename V>
+ inline typename HashSet<T, U, V>::iterator HashSet<T, U, V>::find(const ValueType& value)
{
- return m_impl.find(value);
+ return m_impl.find(*(const StorageType*)&value);
}
-
- template<typename Value, typename HashFunctions, typename Traits>
- typename HashSet<Value, HashFunctions, Traits>::const_iterator HashSet<Value, HashFunctions, Traits>::find(const ValueType& value) const
+
+ template<typename T, typename U, typename V>
+ inline typename HashSet<T, U, V>::const_iterator HashSet<T, U, V>::find(const ValueType& value) const
{
- return m_impl.find(value);
+ return m_impl.find(*(const StorageType*)&value);
}
-
- template<typename Value, typename HashFunctions, typename Traits>
- inline bool HashSet<Value, HashFunctions, Traits>::contains(const ValueType& value) const
+
+ template<typename T, typename U, typename V>
+ inline bool HashSet<T, U, V>::contains(const ValueType& value) const
{
- return m_impl.contains(value);
+ return m_impl.contains(*(const StorageType*)&value);
}
-
- template<typename Value, typename HashFunctions, typename Traits>
- std::pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool> HashSet<Value, HashFunctions, Traits>::add(const ValueType &value)
+
+ template<typename T, typename U, typename V>
+ pair<typename HashSet<T, U, V>::iterator, bool> HashSet<T, U, V>::add(const ValueType &value)
{
- return m_impl.add(value);
+ const bool canReplaceDeletedValue = !ValueTraits::needsDestruction || StorageTraits::needsDestruction;
+ typedef HashSetTranslator<canReplaceDeletedValue, ValueType, StorageTraits, HashFunctions> Translator;
+ return m_impl.template add<ValueType, ValueType, Translator>(value, value);
}
-
+
template<typename Value, typename HashFunctions, typename Traits>
- template<typename T, typename HashSetTranslator>
- std::pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool> HashSet<Value, HashFunctions, Traits>::add(const T& value)
+ template<typename T, typename Translator>
+ pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool>
+ HashSet<Value, HashFunctions, Traits>::add(const T& value)
{
- return m_impl.template add<T, T, HashSetTranslatorAdapter<ValueType, T, HashSetTranslator> >(value, value);
+ const bool canReplaceDeletedValue = !ValueTraits::needsDestruction || StorageTraits::needsDestruction;
+ typedef HashSetTranslatorAdapter<canReplaceDeletedValue, ValueType, StorageTraits, T, Translator> Adapter;
+ return m_impl.template add<T, T, Adapter>(value, value);
}
-
- template<typename Value, typename HashFunctions, typename Traits>
- void HashSet<Value, HashFunctions, Traits>::remove(const ValueType& value)
+
+ template<typename T, typename U, typename V>
+ inline void HashSet<T, U, V>::remove(iterator it)
{
- m_impl.remove(value);
+ if (it.m_impl == m_impl.end())
+ return;
+ it->~ValueType();
+ m_impl.remove(it.m_impl);
}
-
- template<typename Value, typename HashFunctions, typename Traits>
- void HashSet<Value, HashFunctions, Traits>::remove(iterator it)
+
+ template<typename T, typename U, typename V>
+ inline void HashSet<T, U, V>::remove(const ValueType& value)
{
- m_impl.remove(it);
+ remove(find(value));
}
-
- template<typename Value, typename HashFunctions, typename Traits>
- void HashSet<Value, HashFunctions, Traits>::clear()
+
+ template<typename T, typename U, typename V>
+ inline void HashSet<T, U, V>::clear()
{
+ derefAll();
m_impl.clear();
}
- template<typename Value, typename HashFunctions, typename Traits>
- void deleteAllValues(HashSet<Value, HashFunctions, Traits>& collection)
+ template<typename ValueType, typename HashTableType>
+ void deleteAllValues(HashTableType& collection)
+ {
+ typedef typename HashTableType::iterator iterator;
+ iterator end = collection.end();
+ for (iterator it = collection.begin(); it != end; ++it)
+ delete *(ValueType*)&*it;
+ }
+
+ template<typename T, typename U, typename V>
+ inline void deleteAllValues(HashSet<T, U, V>& collection)
{
- typedef HashSet<Value, HashFunctions, Traits> T;
- typename T::iterator end = collection.end();
- for (typename T::iterator it = collection.begin(); it != end; ++it)
- delete (*it);
+ deleteAllValues<typename HashSet<T, U, V>::ValueType>(collection.m_impl);
}
-} // namespace khtml
+} // namespace KXMLCore
using KXMLCore::HashSet;
#endif /* KXMLCORE_HASH_SET_H */
-
-
}
#endif
- ReferenceType operator*() const
+ PointerType get() const
{
checkValidity();
- return *m_position;
+ return m_position;
}
- PointerType operator->() const { return &**this; }
+ ReferenceType operator*() const { return *get(); }
+ PointerType operator->() const { return get(); }
const_iterator& operator++()
{
// default copy, assignment and destructor are OK
- ReferenceType operator*() const { return const_cast<ReferenceType>(*m_iterator); }
- PointerType operator->() const { return &**this; }
+ PointerType get() const { return const_cast<PointerType>(m_iterator.get()); }
+ ReferenceType operator*() const { return *get(); }
+ PointerType operator->() const { return get(); }
iterator& operator++() { ++m_iterator; return *this; }
public:
typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
+ typedef Traits ValueTraits;
typedef Key KeyType;
typedef Value ValueType;
typedef IdentityHashTranslator<Key, Value, HashFunctions> IdentityTranslatorType;
int size() const { return m_keyCount; }
int capacity() const { return m_tableSize; }
+ bool isEmpty() const { return !m_keyCount; }
pair<iterator, bool> add(const ValueType& value) { return add<KeyType, ValueType, IdentityTranslatorType>(Extractor::extract(value), value); }
}
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
- inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const Key& key)
+ typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const Key& key)
{
if (!m_table)
return end();
}
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
- inline typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const Key& key) const
+ typename HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::find(const Key& key) const
{
if (!m_table)
return end();
}
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
- inline bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const KeyType& key) const
+ bool HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::contains(const KeyType& key) const
{
if (!m_table)
return false;
}
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
- inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
+ void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(ValueType* pos)
{
invalidateIterators();
checkTableConsistency();
checkTableConsistency();
}
- template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
- inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
- {
- if (!m_table)
- return;
-
- remove(find(key));
- }
-
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(iterator it)
{
remove(const_cast<ValueType*>(it.m_iterator.m_position));
}
+ template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
+ inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
+ {
+ remove(find(key));
+ }
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
- inline Value *HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::allocateTable(int size)
+ Value *HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::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++) {
- initializeBucket(result[i]);
- }
- return result;
- }
+ return static_cast<ValueType *>(fastCalloc(size, sizeof(ValueType)));
+ ValueType* result = static_cast<ValueType*>(fastMalloc(size * sizeof(ValueType)));
+ for (int i = 0; i < size; i++)
+ initializeBucket(result[i]);
+ return result;
}
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
- inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType *table, int size)
+ void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType *table, int size)
{
- if (Traits::needsDestruction) {
- for (int i = 0; i < size; ++i) {
- (&table[i])->~ValueType();
- }
- }
-
+ if (Traits::needsDestruction)
+ for (int i = 0; i < size; ++i)
+ table[i].~ValueType();
fastFree(table);
}
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
- inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand()
+ void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::expand()
{
int newSize;
if (m_tableSize == 0)
m_tableSizeMask = newTableSize - 1;
m_table = allocateTable(newTableSize);
- for (int i = 0; i != oldTableSize; ++i) {
+ for (int i = 0; i != oldTableSize; ++i)
if (!isEmptyOrDeletedBucket(oldTable[i]))
reinsert(oldTable[i]);
- }
m_deletedCount = 0;
}
template<typename Key, typename Value, typename Extractor, typename HashFunctions, typename Traits, typename KeyTraits>
- inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
+ void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::clear()
{
invalidateIterators();
deallocateTable(m_table, m_tableSize);
#endif // CHECK_HASHTABLE_ITERATORS
+ // iterator adapters
+
+ template<typename HashTableType, typename ValueType> struct HashTableConstIteratorAdapter {
+ HashTableConstIteratorAdapter(const typename HashTableType::const_iterator& impl) : m_impl(impl) {}
+
+ const ValueType* get() const { return (const ValueType*)m_impl.get(); }
+ const ValueType& operator*() const { return *get(); }
+ const ValueType* operator->() const { return get(); }
+
+ HashTableConstIteratorAdapter& operator++() { ++m_impl; return *this; }
+ // postfix ++ intentionally omitted
+
+ typename HashTableType::const_iterator m_impl;
+ };
+
+ template<typename HashTableType, typename ValueType> struct HashTableIteratorAdapter {
+ HashTableIteratorAdapter(const typename HashTableType::iterator& impl) : m_impl(impl) {}
+
+ ValueType* get() const { return (ValueType*)m_impl.get(); }
+ ValueType& operator*() const { return *get(); }
+ ValueType* operator->() const { return get(); }
+
+ HashTableIteratorAdapter& operator++() { ++m_impl; return *this; }
+ // postfix ++ intentionally omitted
+
+ operator HashTableConstIteratorAdapter<HashTableType, ValueType>() {
+ typename HashTableType::const_iterator i = m_impl;
+ return i;
+ }
+
+ typename HashTableType::iterator m_impl;
+ };
+
+ template<typename T, typename U>
+ inline bool operator==(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
+ {
+ return a.m_impl == b.m_impl;
+ }
+
+ template<typename T, typename U>
+ inline bool operator!=(const HashTableConstIteratorAdapter<T, U>& a, const HashTableConstIteratorAdapter<T, U>& b)
+ {
+ return a.m_impl != b.m_impl;
+ }
+
+ template<typename T, typename U>
+ inline bool operator==(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
+ {
+ return a.m_impl == b.m_impl;
+ }
+
+ template<typename T, typename U>
+ inline bool operator!=(const HashTableIteratorAdapter<T, U>& a, const HashTableIteratorAdapter<T, U>& b)
+ {
+ return a.m_impl != b.m_impl;
+ }
+
+ // reference count manager
+
+ template<typename ValueTraits, typename ValueStorageTraits> struct NeedsRef {
+ static const bool value = ValueTraits::needsRef && !ValueStorageTraits::needsRef;
+ };
+
+ template<bool needsRef, typename ValueTraits> struct RefCounterBase;
+
+ template<typename ValueTraits>
+ struct RefCounterBase<false, ValueTraits> {
+ typedef typename ValueTraits::TraitType ValueType;
+ static void ref(const ValueType&) { }
+ static void deref(const ValueType&) { }
+ };
+
+ template<typename ValueTraits>
+ struct RefCounterBase<true, ValueTraits> {
+ typedef typename ValueTraits::TraitType ValueType;
+ static void ref(const ValueType& v) { ValueTraits::ref(*(const ValueType*)&v); }
+ static void deref(const ValueType& v) { ValueTraits::deref(*(const ValueType*)&v); }
+ };
+
+ template<typename ValueTraits, typename ValueStorageTraits> struct RefCounter {
+ typedef typename ValueTraits::TraitType ValueType;
+ typedef typename ValueStorageTraits::TraitType ValueStorageType;
+ static const bool needsRef = NeedsRef<ValueTraits, ValueStorageTraits>::value;
+ typedef RefCounterBase<needsRef, ValueTraits> Base;
+ static void ref(const ValueStorageType& v) { Base::ref(*(const ValueType*)&v); }
+ static void deref(const ValueStorageType& v) { Base::deref(*(const ValueType*)&v); }
+ };
+
+ template<typename FirstTraits, typename SecondTraits, typename ValueStorageTraits>
+ struct RefCounter<PairBaseHashTraits<FirstTraits, SecondTraits>, ValueStorageTraits> {
+ typedef typename FirstTraits::TraitType FirstType;
+ typedef typename SecondTraits::TraitType SecondType;
+ typedef typename ValueStorageTraits::FirstTraits FirstStorageTraits;
+ typedef typename ValueStorageTraits::SecondTraits SecondStorageTraits;
+ typedef typename ValueStorageTraits::TraitType ValueStorageType;
+ static const bool firstNeedsRef = NeedsRef<FirstTraits, FirstStorageTraits>::value;
+ static const bool secondNeedsRef = NeedsRef<SecondTraits, SecondStorageTraits>::value;
+ typedef RefCounterBase<firstNeedsRef, FirstTraits> FirstBase;
+ typedef RefCounterBase<secondNeedsRef, SecondTraits> SecondBase;
+ static void ref(const ValueStorageType& v) {
+ FirstBase::ref(*(const FirstType*)&v.first);
+ SecondBase::ref(*(const SecondType*)&v.second);
+ }
+ static void deref(const ValueStorageType& v) {
+ FirstBase::deref(*(const FirstType*)&v.first);
+ SecondBase::deref(*(const SecondType*)&v.second);
+ }
+ };
+
+ template<bool needsRef, typename HashTableType, typename ValueTraits> struct HashTableRefCounterBase;
+
+ template<typename HashTableType, typename ValueTraits>
+ struct HashTableRefCounterBase<false, HashTableType, ValueTraits>
+ {
+ static void refAll(HashTableType&) { }
+ static void derefAll(HashTableType&) { }
+ };
+
+ template<typename HashTableType, typename ValueTraits>
+ struct HashTableRefCounterBase<true, HashTableType, ValueTraits>
+ {
+ typedef typename HashTableType::iterator iterator;
+ typedef RefCounter<ValueTraits, typename HashTableType::ValueTraits> ValueRefCounter;
+ static void refAll(HashTableType&);
+ static void derefAll(HashTableType&);
+ };
+
+ template<typename HashTableType, typename ValueTraits>
+ void HashTableRefCounterBase<true, HashTableType, ValueTraits>::refAll(HashTableType& table)
+ {
+ iterator end = table.end();
+ for (iterator it = table.begin(); it != end; ++it)
+ ValueRefCounter::ref(*it);
+ }
+
+ template<typename HashTableType, typename ValueTraits>
+ void HashTableRefCounterBase<true, HashTableType, ValueTraits>::derefAll(HashTableType& table)
+ {
+ iterator end = table.end();
+ for (iterator it = table.begin(); it != end; ++it)
+ ValueRefCounter::deref(*it);
+ }
+
+ template<typename HashTableType, typename ValueTraits> struct HashTableRefCounter {
+ static const bool needsRef = NeedsRef<ValueTraits, typename HashTableType::ValueTraits>::value;
+ typedef HashTableRefCounterBase<needsRef, HashTableType, ValueTraits> Base;
+ static void refAll(HashTableType& table) { Base::refAll(table); }
+ static void derefAll(HashTableType& table) { Base::derefAll(table); }
+ };
+
} // namespace KXMLCore
#endif // KXMLCORE_HASH_TABLE_H
#ifndef KXMLCORE_HASH_TRAITS_H
#define KXMLCORE_HASH_TRAITS_H
-#include "RefPtr.h"
+#include "HashFunctions.h"
#include <utility>
namespace KXMLCore {
using std::pair;
-
- template <typename T> struct IsInteger { static const bool value = false; };
- template <> struct IsInteger<bool> { static const bool value = true; };
- template <> struct IsInteger<char> { static const bool value = true; };
- template <> struct IsInteger<signed char> { static const bool value = true; };
- template <> struct IsInteger<unsigned char> { static const bool value = true; };
- template <> struct IsInteger<short> { static const bool value = true; };
- template <> struct IsInteger<unsigned short> { static const bool value = true; };
- template <> struct IsInteger<int> { static const bool value = true; };
- template <> struct IsInteger<unsigned int> { static const bool value = true; };
- template <> struct IsInteger<long> { static const bool value = true; };
- template <> struct IsInteger<unsigned long> { static const bool value = true; };
- template <> struct IsInteger<long long> { static const bool value = true; };
- template <> struct IsInteger<unsigned long long> { static const bool value = true; };
+ using std::make_pair;
+
+ template<typename T> struct IsInteger { static const bool value = false; };
+ template<> struct IsInteger<bool> { static const bool value = true; };
+ template<> struct IsInteger<char> { static const bool value = true; };
+ template<> struct IsInteger<signed char> { static const bool value = true; };
+ template<> struct IsInteger<unsigned char> { static const bool value = true; };
+ template<> struct IsInteger<short> { static const bool value = true; };
+ template<> struct IsInteger<unsigned short> { static const bool value = true; };
+ template<> struct IsInteger<int> { static const bool value = true; };
+ template<> struct IsInteger<unsigned int> { static const bool value = true; };
+ template<> struct IsInteger<long> { static const bool value = true; };
+ template<> struct IsInteger<unsigned long> { static const bool value = true; };
+ template<> struct IsInteger<long long> { static const bool value = true; };
+ template<> struct IsInteger<unsigned long long> { static const bool value = true; };
+
+ template<typename T> struct HashTraits;
template<bool isInteger, typename T> struct GenericHashTraitsBase;
template<typename T> struct GenericHashTraitsBase<true, T> {
typedef T TraitType;
+ typedef HashTraits<typename IntTypes<sizeof(T)>::SignedType> StorageTraits;
static const bool emptyValueIsZero = true;
static const bool needsDestruction = false;
- static TraitType emptyValue() { return 0; }
};
template<typename T> struct GenericHashTraitsBase<false, T> {
typedef T TraitType;
+ typedef HashTraits<T> StorageTraits;
static const bool emptyValueIsZero = false;
static const bool needsDestruction = true;
- static TraitType emptyValue() { return TraitType(); }
};
- template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> { };
+ template<typename T> struct GenericHashTraits : GenericHashTraitsBase<IsInteger<T>::value, T> {
+ static T emptyValue() { return T(); }
+ static const bool needsRef = false;
+ };
template<typename T> struct HashTraits : GenericHashTraits<T> { };
- // may not be appropriate for all uses since it disallows 0 and -1 as keys
+ // signed integer traits may not be appropriate for all uses since they disallow 0 and -1 as keys
+ template<> struct HashTraits<signed char> : GenericHashTraits<int> {
+ static signed char deletedValue() { return -1; }
+ };
+ template<> struct HashTraits<short> : GenericHashTraits<int> {
+ static short deletedValue() { return -1; }
+ };
template<> struct HashTraits<int> : GenericHashTraits<int> {
- static TraitType deletedValue() { return -1; }
+ static int deletedValue() { return -1; }
+ };
+ template<> struct HashTraits<long> : GenericHashTraits<long> {
+ static long deletedValue() { return -1; }
+ };
+ template<> struct HashTraits<long long> : GenericHashTraits<long long> {
+ static long deletedValue() { return -1; }
};
template<typename P> struct HashTraits<P*> : GenericHashTraits<P*> {
- typedef P* TraitType;
+ typedef HashTraits<typename IntTypes<sizeof(P*)>::SignedType> StorageTraits;
static const bool emptyValueIsZero = true;
static const bool needsDestruction = false;
- static TraitType emptyValue() { return 0; }
- static TraitType deletedValue() { return reinterpret_cast<P*>(-1); }
+ static P* deletedValue() { return reinterpret_cast<P*>(-1); }
};
template<typename P> struct HashTraits<RefPtr<P> > : GenericHashTraits<RefPtr<P> > {
+ typedef HashTraits<typename IntTypes<sizeof(P*)>::SignedType> StorageTraits;
static const bool emptyValueIsZero = true;
+ static const bool needsRef = true;
+ static void ref(const RefPtr<P>& p) { if (p) p->ref(); }
+ static void deref(const RefPtr<P>& p) { if (p) p->deref(); }
};
- template<typename T, typename Traits> class DeletedValueAssigner;
+ // template to set deleted values
+
+ template<typename Traits> struct DeletedValueAssigner {
+ static void assignDeletedValue(typename Traits::TraitType& location) { location = Traits::deletedValue(); }
+ };
template<typename T, typename Traits> inline void assignDeleted(T& location)
{
- DeletedValueAssigner<T, Traits>::assignDeletedValue(location);
+ DeletedValueAssigner<Traits>::assignDeletedValue(location);
}
- template<typename FirstTraits, typename SecondTraits>
- struct PairHashTraits : GenericHashTraits<pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> > {
- private:
- typedef typename FirstTraits::TraitType FirstType;
- typedef typename SecondTraits::TraitType SecondType;
- public:
- typedef pair<FirstType, SecondType> TraitType;
+ // special traits for pairs, helpful for their use in HashMap implementation
+
+ template<typename FirstTraits, typename SecondTraits> struct PairHashTraits;
+
+ template<typename FirstTraitsArg, typename SecondTraitsArg>
+ struct PairBaseHashTraits : GenericHashTraits<pair<typename FirstTraitsArg::TraitType, typename SecondTraitsArg::TraitType> > {
+ typedef FirstTraitsArg FirstTraits;
+ typedef SecondTraitsArg SecondTraits;
+ typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
+
+ typedef PairHashTraits<typename FirstTraits::StorageTraits, typename SecondTraits::StorageTraits> StorageTraits;
static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
- static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
static TraitType emptyValue()
{
- return TraitType(FirstTraits::emptyValue(), SecondTraits::emptyValue());
+ return make_pair(FirstTraits::emptyValue(), SecondTraits::emptyValue());
}
+ };
+
+ template<typename FirstTraits, typename SecondTraits>
+ struct PairHashTraits : PairBaseHashTraits<FirstTraits, SecondTraits> {
+ typedef pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> TraitType;
+
+ static const bool needsDestruction = FirstTraits::needsDestruction || SecondTraits::needsDestruction;
static TraitType deletedValue()
{
static void assignDeletedValue(TraitType& location)
{
- assignDeleted<FirstType, FirstTraits>(location.first);
+ assignDeleted<typename FirstTraits::TraitType, FirstTraits>(location.first);
location.second = SecondTraits::emptyValue();
}
};
template<typename First, typename Second>
struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > { };
- template<typename T, typename Traits> struct DeletedValueAssigner {
- static void assignDeletedValue(T& location) { location = Traits::deletedValue(); }
- };
-
template<typename FirstTraits, typename SecondTraits>
- struct DeletedValueAssigner<pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType>, PairHashTraits<FirstTraits, SecondTraits> >
+ struct DeletedValueAssigner<PairHashTraits<FirstTraits, SecondTraits> >
{
static void assignDeletedValue(pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType>& location)
{
};
template<typename First, typename Second>
- struct DeletedValueAssigner<
pair<First, Second>, HashTraits<pair<First, Second> > >
+ struct DeletedValueAssigner<HashTraits<pair<First, Second> > >
{
static void assignDeletedValue(pair<First, Second>& location)
{
}
};
+ // hassh functions and traits that are equivalent (for code sharing)
+
+ template<typename HashArg, typename TraitsArg> struct HashKeyStorageTraits {
+ typedef HashArg Hash;
+ typedef TraitsArg Traits;
+ };
+ template<typename P> struct HashKeyStorageTraits<PtrHash<P*>, HashTraits<P*> > {
+ typedef typename IntTypes<sizeof(P*)>::SignedType IntType;
+ typedef IntHash<IntType> Hash;
+ typedef HashTraits<IntType> Traits;
+ };
+ template<typename P> struct HashKeyStorageTraits<PtrHash<RefPtr<P> >, HashTraits<RefPtr<P> > > {
+ typedef typename IntTypes<sizeof(P*)>::SignedType IntType;
+ typedef IntHash<IntType> Hash;
+ typedef HashTraits<IntType> Traits;
+ };
} // namespace KXMLCore
+2006-04-05 Darin Adler <darin@apple.com>
+
+ Reviewed by Maciej.
+
+ - fix for http://bugzilla.opendarwin.org/show_bug.cgi?id=8049
+ StringImpl hash traits deleted value creates an init routine for WebCore
+ <rdar://problem/4442248> REGRESSION: WebCore has init routines (8049)
+
+ * platform/StringHash.h: Added. Moved hash functions and such for
+ WebCore::String and friends into this file so we don't have to include
+ the hash traits header everywhere. Changed hashing for WebCore::StringImpl
+ and WebCore::String so that they use a raw pointer for the underlying
+ storage type, taking advantage of the new feature added in JavaScriptCore.
+
+ * platform/AtomicString.h: Moved StrHash specialization to StringHash.h.
+ * platform/PlatformString.h: Moved StrHash specialization to StringHash.h.
+ * platform/StringImpl.h: Moved StrHash, CaseInsensitiveHash, and HashTraits
+ to StringHash.h. Left DefaultHash behind so that you can't get the wrong
+ hash function by accident if you forget to include "StringHash.h".
+
+ * platform/StringImpl.cpp: Added include of StringHash.h and removed
+ RefPtr<StringImpl> HashTraits<RefPtr<StringImpl> >::_deleted, which is
+ the object with a global initializer causing all the trouble!
+
+ * kwq/AccessibilityObjectCache.h: Changed hash function to be IntHash
+ instead of PtrHash.
+
+ * dom/StyledElement.cpp: Changed MappedAttributeKeyTraits to inherit from
+ the generic traits in KXMLCore so we get a StorageType. Also cleaned up a
+ tiny bit by adding default values to the MappedAttributeKey constructor.
+
+ * platform/CharsetNames.cpp: Changed hash traits here to be a new
+ TextEncodingIDHashTraits struct rather than defining new default traits
+ for the integer type since more integer types have default traits in
+ HashTraits.h now. Also added a specialization so this class will share
+ the underlying implementation (since InvalidEncoding happens to be -1).
+
+ * bridge/mac/FrameMac.h:
+ * dom/Document.h:
+ * dom/xml_tokenizer.h:
+ * khtml/xsl/XSLTProcessor.h:
+ * kwq/JavaAppletWidget.h:
+ * page/FramePrivate.h:
+ * page/Page.cpp:
+ * platform/AtomicString.cpp:
+ * platform/TransferJob.h:
+ * rendering/render_applet.h:
+ Added include of StringHash.h.
+
+ * WebCore.xcodeproj/project.pbxproj: Added StringHash.h. Remove unneeded
+ CREATE_HASH_TABLE variable in build settings. Re-sorted some file lists.
+ Added quotes to the CREATE_HASH_TABLE initialization in the rule that
+ builds generated files. Removed various unneeded build settings for that
+ target as well.
+
+ * ForwardingHeaders/kxmlcore/HashTraits.h: Added.
+
+ - other minor cleanup
+
+ * bridge/mac/FrameMac.mm: Sorted includes.
+ * dom/Node.cpp: Removed bogus symbol after #endif.
+
+ * khtml/xsl/XSLTProcessor.cpp: Sorted includes. Removed redundant using
+ namespace WebCore.
+ * loader/Cache.cpp: Ditto.
+
2006-04-05 Beth Dakin <bdakin@apple.com>
Reviewed by Darin.
(WebCore::RenderTheme::paintBorderOnly):
* rendering/RenderTheme.h:
-2006-03-30 Darin Adler <darin@apple.com>
+2006-03-31 Darin Adler <darin@apple.com>
Reviewed by John Sullivan.
--- /dev/null
+#import <JavaScriptCore/HashTraits.h>
930705EB09E0C9F600B17FE4 /* JSCSSPrimitiveValue.h in Headers */ = {isa = PBXBuildFile; fileRef = 930705EA09E0C9F600B17FE4 /* JSCSSPrimitiveValue.h */; };
930CAD1509C4F3C300229C04 /* JSCanvasRenderingContext2DBase.h in Headers */ = {isa = PBXBuildFile; fileRef = 930CAD1409C4F3C300229C04 /* JSCanvasRenderingContext2DBase.h */; };
930CAD2609C4F49100229C04 /* JSCanvasRenderingContext2DBase.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 930CAD2509C4F49100229C04 /* JSCanvasRenderingContext2DBase.cpp */; };
+ 93126F6109D7A736008D9626 /* StringHash.h in Headers */ = {isa = PBXBuildFile; fileRef = 93126F6009D7A736008D9626 /* StringHash.h */; };
9326DC0B09DAD5BE00AFC847 /* CharsetData.h in Headers */ = {isa = PBXBuildFile; fileRef = 9326DC0A09DAD5BE00AFC847 /* CharsetData.h */; };
9326DC0C09DAD5D600AFC847 /* CharsetData.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 656581AC09D14EE6000E61D7 /* CharsetData.cpp */; };
9327A94209968D1A0068A546 /* HTMLOptionsCollection.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 9327A94109968D1A0068A546 /* HTMLOptionsCollection.cpp */; };
014CEA440018CDF011CA2923 /* Development */ = {
isa = PBXBuildStyle;
buildSettings = {
- CREATE_HASH_TABLE = "$(BUILT_PRODUCTS_DIR)/JavaScriptCore.framework/PrivateHeaders/create_hash_table";
DEBUG_DEFINES = "";
EXPORTED_SYMBOLS_FILE = "$(DERIVED_FILES_DIR)/WebCore-combined.exp";
GCC_GENERATE_DEBUGGING_SYMBOLS = YES;
014CEA450018CDF011CA2923 /* Deployment */ = {
isa = PBXBuildStyle;
buildSettings = {
- CREATE_HASH_TABLE = "$(BUILT_PRODUCTS_DIR)/JavaScriptCore.framework/PrivateHeaders/create_hash_table";
GCC_GENERATE_DEBUGGING_SYMBOLS = YES;
MACOSX_DEPLOYMENT_TARGET = 10.3;
PREBINDING = NO;
F58C8A07025BD3BC018635CA /* OptimizedWithSymbols */ = {
isa = PBXBuildStyle;
buildSettings = {
- CREATE_HASH_TABLE = "$(BUILT_PRODUCTS_DIR)/JavaScriptCore.framework/PrivateHeaders/create_hash_table";
GCC_GENERATE_DEBUGGING_SYMBOLS = YES;
MACOSX_DEPLOYMENT_TARGET = 10.3;
PREBINDING = NO;
930CAB9609C49FAA00229C04 /* CodeGeneratorJS.pm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text.script.perl; name = CodeGeneratorJS.pm; path = bindings/scripts/CodeGeneratorJS.pm; sourceTree = "<group>"; };
930CAD1409C4F3C300229C04 /* JSCanvasRenderingContext2DBase.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = JSCanvasRenderingContext2DBase.h; path = bindings/js/JSCanvasRenderingContext2DBase.h; sourceTree = "<group>"; };
930CAD2509C4F49100229C04 /* JSCanvasRenderingContext2DBase.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = JSCanvasRenderingContext2DBase.cpp; path = bindings/js/JSCanvasRenderingContext2DBase.cpp; sourceTree = "<group>"; };
+ 93126F6009D7A736008D9626 /* StringHash.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = StringHash.h; path = platform/StringHash.h; sourceTree = "<group>"; };
9326DC0A09DAD5BE00AFC847 /* CharsetData.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = CharsetData.h; path = platform/CharsetData.h; sourceTree = "<group>"; };
9327A94109968D1A0068A546 /* HTMLOptionsCollection.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = HTMLOptionsCollection.cpp; sourceTree = "<group>"; };
93309D87099E64910056E581 /* AppendNodeCommand.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = AppendNodeCommand.cpp; sourceTree = "<group>"; };
6582A14809999D6C00BEEB6D /* mac */,
BCFB2F74097A2E1A00BA703D /* Arena.cpp */,
BCFB2F75097A2E1A00BA703D /* Arena.h */,
- BCB16B880979B01400467741 /* DeprecatedArray.h */,
BCB16B890979B01400467741 /* ArrayImpl.cpp */,
BCB16B8A0979B01400467741 /* ArrayImpl.h */,
93CD4FD70995F9EA007ECC97 /* AtomicString.cpp */,
BCC8CFCA0986CD2400140BF2 /* ColorData.gperf */,
9352088109BD45E900F2038D /* CookieJar.h */,
F587868402DE3B8601EA4122 /* Cursor.h */,
+ BCB16B880979B01400467741 /* DeprecatedArray.h */,
+ 6582A13D09999CD600BEEB6D /* DeprecatedString.cpp */,
+ 6582A13E09999CD600BEEB6D /* DeprecatedString.h */,
+ 651B4D8309AC83370029F1EF /* DeprecatedStringList.cpp */,
+ 651B4D8409AC83370029F1EF /* DeprecatedStringList.h */,
BC73E3900978CED700EDFF8A /* FloatPoint.cpp */,
BC73E3910978CED700EDFF8A /* FloatPoint.h */,
BCB16AF50979A08500467741 /* FloatRect.cpp */,
BC73E25C0978682700EDFF8A /* FloatSize.h */,
BC6D6DD009AF906600F59759 /* Font.cpp */,
BC6D6DD109AF906600F59759 /* Font.h */,
+ BCEB377509B7BB0D00CB38B1 /* FontDataSet.h */,
BCC47E6A09A3FE4700ADB771 /* FontDescription.h */,
BCC47E2409A3D6F100ADB771 /* FontFamily.cpp */,
BCC47E2509A3D6F100ADB771 /* FontFamily.h */,
- BCEB377509B7BB0D00CB38B1 /* FontDataSet.h */,
A823A75B09B6E53900B60641 /* GraphicsContext.cpp */,
935367E409AF77DD00D35CD6 /* GraphicsContext.h */,
BC6B7BAE0993603C0052867B /* Image.cpp */,
BCB16AF70979A08500467741 /* IntRect.cpp */,
BCB16AF80979A08500467741 /* IntRect.h */,
BCF1A5EF097839600061A123 /* IntSize.h */,
- 935C476609AC4D4300A6AAB4 /* PlatformKeyboardEvent.h */,
6593923509AE4346002C531F /* KURL.cpp */,
6593923609AE4346002C531F /* KURL.h */,
935207BD09BD410A00F2038D /* LocalizedStrings.h */,
A8239DFE09B3CF8A00B60641 /* Logging.cpp */,
A8239DFF09B3CF8A00B60641 /* Logging.h */,
65F5382109B2B55700F3DC4A /* make-charset-table.pl */,
- 935C476709AC4D4300A6AAB4 /* PlatformMouseEvent.h */,
93032CC909AEC34B00F82A18 /* Path.h */,
BC6B7BBB0993611A0052867B /* PDFDocumentImage.h */,
BCC8D1710988301200140BF2 /* Pen.cpp */,
BCC8D1720988301200140BF2 /* Pen.h */,
+ 935C476609AC4D4300A6AAB4 /* PlatformKeyboardEvent.h */,
+ 935C476709AC4D4300A6AAB4 /* PlatformMouseEvent.h */,
93CD4FEB0995FD2A007ECC97 /* PlatformString.h */,
+ 935C476A09AC4D4F00A6AAB4 /* PlatformWheelEvent.h */,
A82398A509B3ACDB00B60641 /* PlugInInfoStore.h */,
- 6582A13D09999CD600BEEB6D /* DeprecatedString.cpp */,
- 6582A13E09999CD600BEEB6D /* DeprecatedString.h */,
- 651B4D8309AC83370029F1EF /* DeprecatedStringList.cpp */,
- 651B4D8409AC83370029F1EF /* DeprecatedStringList.h */,
9385F761098D9C3100D90D24 /* Screen.h */,
9353673E09AED79200D35CD6 /* ScrollBarMode.h */,
BC6D6E2509AF943500F59759 /* ScrollView.h */,
657BD74909AFDC54005A2056 /* StreamingTextDecoder.cpp */,
657BD74A09AFDC54005A2056 /* StreamingTextDecoder.h */,
93CD4FDA0995F9EA007ECC97 /* String.cpp */,
+ 93126F6009D7A736008D9626 /* StringHash.h */,
93CD4FDC0995F9EA007ECC97 /* StringImpl.cpp */,
93CD4FDD0995F9EA007ECC97 /* StringImpl.h */,
93E62D990985F41600E1B5E3 /* SystemTime.h */,
6545F66D09B82FED0013006F /* TransferJob.h */,
6545F66E09B82FED0013006F /* TransferJobClient.h */,
6545F66F09B82FED0013006F /* TransferJobInternal.h */,
- 935C476A09AC4D4F00A6AAB4 /* PlatformWheelEvent.h */,
9380F47109A11AB4001FDB34 /* Widget.cpp */,
9380F47209A11AB4001FDB34 /* Widget.h */,
93B780C909B3B7FE00690162 /* WidgetClient.h */,
65DF323A09D1DE65000BE325 /* JSCanvasGradient.h in Headers */,
65DF323C09D1DE65000BE325 /* JSCanvasPattern.h in Headers */,
65DF323E09D1DE65000BE325 /* JSCanvasRenderingContext2D.h in Headers */,
+ 93126F6109D7A736008D9626 /* StringHash.h in Headers */,
D086FE9809D53AAB005BC74D /* UnlinkCommand.h in Headers */,
A8C4A7FD09D563270003AC8D /* StyledElement.h in Headers */,
A8C4A7FF09D563270003AC8D /* Node.h in Headers */,
buildRules = (
);
buildSettings = {
- CREATE_HASH_TABLE = /System/Library/Frameworks/WebKit.framework/Versions/A/Frameworks/JavaScriptCore.framework/PrivateHeaders/create_hash_table;
DEBUG_DEFINES = NDEBUG;
DYLIB_COMPATIBILITY_VERSION = 1;
DYLIB_CURRENT_VERSION = 1;
);
runOnlyForDeploymentPostprocessing = 0;
shellPath = /bin/sh;
+<<<<<<< .mine
+ shellScript = "if [ \"${BUILD_STYLE}\" = \"Release\" -o \"${BUILD_STYLE}\" = \"Debug\" ] ; then\n export CREATE_HASH_TABLE=\"${BUILT_PRODUCTS_DIR}/JavaScriptCore.framework/PrivateHeaders/create_hash_table\"\nelse\n export CREATE_HASH_TABLE=\"${NEXT_ROOT}${SYSTEM_LIBRARY_DIR}/Frameworks/WebKit.framework/Versions/A/Frameworks/JavaScriptCore.framework/PrivateHeaders/create_hash_table\"\nfi\n./generate-derived-sources\n";
+=======
shellScript = "if [ \"${BUILD_STYLE}\" = \"Release\" -o \"${BUILD_STYLE}\" = \"Debug\" ] ; then\n export CREATE_HASH_TABLE=\"${BUILT_PRODUCTS_DIR}/JavaScriptCore.framework/PrivateHeaders/create_hash_table\"\nelse\n export CREATE_HASH_TABLE=\"${NEXT_ROOT}${SYSTEM_LIBRARY_DIR}/Frameworks/WebKit.framework/Versions/A/Frameworks/JavaScriptCore.framework/PrivateHeaders/create_hash_table\"\nfi\n\nmkdir -p \"${BUILT_PRODUCTS_DIR}/DerivedSources/WebCore\"\ncd \"${BUILT_PRODUCTS_DIR}/DerivedSources/WebCore\"\n\nexport WebCore=\"${SRCROOT}\"\n\nexport ENCODINGS_FILE=\"${WebCore}/platform/mac/mac-encodings.txt\"\nexport ENCODINGS_PREFIX=\"kCFStringEncoding\"\n\nmake -f \"$WebCore/DerivedSources.make\"\n";
+>>>>>>> .r13702
};
/* End PBXShellScriptBuildPhase section */
149C283A08902B11008A9EFC /* Debug */ = {
isa = XCBuildConfiguration;
buildSettings = {
- CREATE_HASH_TABLE = "$(BUILT_PRODUCTS_DIR)/JavaScriptCore.framework/PrivateHeaders/create_hash_table";
DEBUG_DEFINES = "";
DYLIB_COMPATIBILITY_VERSION = 1;
DYLIB_CURRENT_VERSION = 1;
149C283B08902B11008A9EFC /* Release */ = {
isa = XCBuildConfiguration;
buildSettings = {
- CREATE_HASH_TABLE = "$(BUILT_PRODUCTS_DIR)/JavaScriptCore.framework/PrivateHeaders/create_hash_table";
DEBUG_DEFINES = NDEBUG;
DYLIB_COMPATIBILITY_VERSION = 1;
DYLIB_CURRENT_VERSION = 1;
149C283D08902B11008A9EFC /* Production */ = {
isa = XCBuildConfiguration;
buildSettings = {
- CREATE_HASH_TABLE = "$(NEXT_ROOT)$(SYSTEM_LIBRARY_DIR)/Frameworks/WebKit.framework/Versions/A/Frameworks/JavaScriptCore.framework/PrivateHeaders/create_hash_table";
DEBUG_DEFINES = NDEBUG;
DYLIB_COMPATIBILITY_VERSION = 1;
DYLIB_CURRENT_VERSION = 1;
DD041FC209D9DDDC0010AF2A /* Debug */ = {
isa = XCBuildConfiguration;
buildSettings = {
- COPY_PHASE_STRIP = NO;
- GCC_DYNAMIC_NO_PIC = NO;
- GCC_GENERATE_DEBUGGING_SYMBOLS = YES;
- GCC_OPTIMIZATION_LEVEL = 0;
PRODUCT_NAME = "Derived Sources";
};
name = Debug;
DD041FC309D9DDDC0010AF2A /* Release */ = {
isa = XCBuildConfiguration;
buildSettings = {
- COPY_PHASE_STRIP = YES;
- GCC_ENABLE_FIX_AND_CONTINUE = NO;
- GCC_GENERATE_DEBUGGING_SYMBOLS = NO;
PRODUCT_NAME = "Derived Sources";
- ZERO_LINK = NO;
};
name = Release;
};
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
-#ifndef MacFrame_H
-#define MacFrame_H
-
-#include "Frame.h"
-#include "IntRect.h"
-#include "ClipboardMac.h"
-#include "KWQScrollBar.h"
-#include "PlatformMouseEvent.h"
-#include "Node.h"
-#include "WebCoreKeyboardAccess.h"
-#include "TextAffinity.h"
-#include <kxmlcore/HashSet.h>
-
+#ifndef FrameMac_h
+#define FrameMac_h
+
+#import "ClipboardMac.h"
+#import "Frame.h"
+#import "IntRect.h"
+#import "KWQScrollBar.h"
+#import "Node.h"
+#import "PlatformMouseEvent.h"
+#import "StringHash.h"
+#import "TextAffinity.h"
+#import "WebCoreKeyboardAccess.h"
#import <CoreFoundation/CoreFoundation.h>
+#import <kxmlcore/HashSet.h>
class NPObject;
#import "config.h"
#import "FrameMac.h"
+#import "AccessibilityObjectCache.h"
+#import "BlockExceptions.h"
#import "BrowserExtensionMac.h"
+#import "CSSComputedStyleDeclaration.h"
#import "Cache.h"
+#import "ClipboardMac.h"
#import "Cursor.h"
#import "DOMInternal.h"
#import "EventNames.h"
#import "FramePrivate.h"
#import "FrameView.h"
#import "GraphicsContext.h"
+#import "HTMLDocument.h"
#import "HTMLFormElement.h"
#import "HTMLGenericFormElement.h"
#import "InlineTextBox.h"
-#import "AccessibilityObjectCache.h"
-#import "ClipboardMac.h"
#import "KWQEditCommand.h"
-#import "BlockExceptions.h"
#import "KWQFormData.h"
-#import "TransferJob.h"
-#import "Logging.h"
#import "KWQPageState.h"
-#import "RegularExpression.h"
#import "KWQScrollBar.h"
-#import "TextEncoding.h"
+#import "Logging.h"
+#import "MouseEventWithHitTestResults.h"
#import "PlatformKeyboardEvent.h"
#import "PlatformMouseEvent.h"
-#import "MouseEventWithHitTestResults.h"
+#import "PlatformWheelEvent.h"
#import "Plugin.h"
+#import "Position.h"
+#import "Range.h"
+#import "RegularExpression.h"
+#import "RenderCanvas.h"
+#import "RenderImage.h"
#import "RenderTableCell.h"
+#import "RenderTheme.h"
#import "SelectionController.h"
+#import "TextEncoding.h"
+#import "TextIterator.h"
+#import "TransferJob.h"
#import "VisiblePosition.h"
#import "WebCoreFrameBridge.h"
#import "WebCoreGraphicsBridge.h"
#import "WebCoreViewFactory.h"
#import "WebDashboardRegion.h"
-#import "PlatformWheelEvent.h"
-#import "CSSComputedStyleDeclaration.h"
#import "csshelper.h"
#import "dom2_eventsimpl.h"
-#import "Range.h"
-#import "Position.h"
-#import "HTMLDocument.h"
#import "html_tableimpl.h"
#import "kjs_binding.h"
#import "kjs_window.h"
-#import "RenderCanvas.h"
#import "render_frames.h"
-#import "RenderImage.h"
#import "render_list.h"
#import "render_style.h"
-#import "RenderTheme.h"
-#import "TextIterator.h"
#import "visible_units.h"
#import <JavaScriptCore/NP_jsobject.h>
#import <JavaScriptCore/WebScriptObjectPrivate.h>
#include "ContainerNode.h"
#include "DocumentMarker.h"
#include "Shared.h"
+#include "StringHash.h"
#include "Timer.h"
#include "decoder.h"
#include "dom2_traversalimpl.h"
+#include <DeprecatedStringList.h>
#include <KURL.h>
#include <kxmlcore/HashCountedSet.h>
#include <kxmlcore/HashMap.h>
#include <qptrlist.h>
-#include <DeprecatedStringList.h>
class RenderArena;
static NodeImplCounter nodeImplCounter;
int gEventDispatchForbidden = 0;
-#endif NDEBUG
+#endif
Node::Node(Document *doc)
: m_document(doc),
* the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*/
+
#include "config.h"
#include "StyledElement.h"
-#include "css_stylesheetimpl.h"
-#include "css_valueimpl.h"
#include "CSSValueKeywords.h"
#include "Document.h"
#include "HTMLNames.h"
+#include "css_stylesheetimpl.h"
+#include "css_valueimpl.h"
+#include <kxmlcore/HashTraits.h>
namespace WebCore {
uint16_t type;
StringImpl* name;
StringImpl* value;
- MappedAttributeKey(MappedAttributeEntry t, StringImpl* n, StringImpl* v)
+ MappedAttributeKey(MappedAttributeEntry t = eNone, StringImpl* n = 0, StringImpl* v = 0)
: type(t), name(n), value(v) { }
};
static inline bool operator==(const MappedAttributeKey& a, const MappedAttributeKey& b)
{ return a.type == b.type && a.name == b.name && a.value == b.value; }
-struct MappedAttributeKeyTraits {
- typedef MappedAttributeKey TraitType;
+struct MappedAttributeKeyTraits : KXMLCore::GenericHashTraits<MappedAttributeKey> {
static const bool emptyValueIsZero = true;
static const bool needsDestruction = false;
- static MappedAttributeKey emptyValue() { return MappedAttributeKey(eNone, 0, 0); }
- static MappedAttributeKey deletedValue() { return MappedAttributeKey(eLastEntry, 0, 0); }
+ static MappedAttributeKey deletedValue() { return eLastEntry; }
};
struct MappedAttributeHash {
#ifndef XML_Tokenizer_h_
#define XML_Tokenizer_h_
-#include "PlatformString.h"
+#include "StringHash.h"
#include <kxmlcore/HashMap.h>
namespace WebCore {
#ifdef KHTML_XSLT
-#include "XSLTProcessor.h"
-#include "XSLStyleSheet.h"
-#include "xml_tokenizer.h"
-#include "Text.h"
-#include "HTMLTokenizer.h"
-#include "HTMLDocument.h"
-#include "DOMImplementation.h"
-#include "loader.h"
#include "Cache.h"
+#include "DOMImplementation.h"
#include "DocLoader.h"
-#include "markup.h"
-#include "FrameView.h"
#include "Frame.h"
+#include "FrameView.h"
+#include "HTMLDocument.h"
+#include "HTMLTokenizer.h"
#include "KWQLoader.h"
-
+#include "Text.h"
#include "TransferJob.h"
-
-#include <libxslt/xsltutils.h>
+#include "XSLStyleSheet.h"
+#include "XSLTProcessor.h"
+#include "loader.h"
+#include "markup.h"
+#include "xml_tokenizer.h"
+#include <kxmlcore/Assertions.h>
#include <libxslt/documents.h>
#include <libxslt/imports.h>
-
-#include <kxmlcore/Assertions.h>
-
-using namespace WebCore;
-using namespace WebCore;
+#include <libxslt/xsltutils.h>
namespace WebCore {
*
*/
-#ifndef _xslt_processorimpl_h_
-#define _xslt_processorimpl_h_
+#ifndef xslt_processorimpl_h_
+#define xslt_processorimpl_h_
#ifdef KHTML_XSLT
#include "Shared.h"
-#include "StringImpl.h"
+#include "StringHash.h"
#include "XSLStyleSheet.h"
+#include <DeprecatedString.h>
+#include <kxmlcore/HashMap.h>
#include <libxml/parser.h>
#include <libxml/parserInternals.h>
#include <libxslt/documents.h>
#include <libxslt/transform.h>
-#include <DeprecatedString.h>
-
-#include <kxmlcore/HashMap.h>
namespace WebCore {
AXID getAXID(WebCoreAXObject*);
HashMap<RenderObject*, WebCoreAXObject*> m_objects;
- HashSet<AXID,
PtrHash<AXID>, AXIDHashTraits> m_idsInUse;
+ HashSet<AXID,
IntHash<AXID>, AXIDHashTraits> m_idsInUse;
};
#ifndef __APPLE__
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
-#include "PlatformString.h"
+#include "StringHash.h"
#include "Widget.h"
#include <kxmlcore/HashMap.h>
#include "CachedXSLStyleSheet.h"
#include "DocLoader.h"
#include "Document.h"
-#include "loader.h"
-#include "TransferJob.h"
+#include "Image.h"
#include "TransferJob.h"
+#include "loader.h"
#include <kxmlcore/Assertions.h>
-#include "Image.h"
-
-using namespace WebCore;
namespace WebCore {
#include "Frame.h"
#include "FrameTree.h"
#include "SelectionController.h"
+#include "StringHash.h"
#include "Timer.h"
#include "css_valueimpl.h"
#include "kjs_proxy.h"
#include "Color.h"
#include "Frame.h"
#include "FrameTree.h"
+#include "StringHash.h"
#include <kjs/collector.h>
#include <kjs/JSLock.h>
#include <kxmlcore/HashMap.h>
#include "AtomicString.h"
#include "StaticConstructors.h"
+#include "StringHash.h"
#include <kjs/identifier.h>
#include <kxmlcore/HashSet.h>
}
-namespace KXMLCore {
-
- template<typename T> class StrHash;
-
- template<> struct StrHash<WebCore::AtomicStringImpl*> : public StrHash<WebCore::StringImpl*>
- {
- };
-
-}
-
#endif
#include <unicode/ucnv.h>
#include <unicode/utypes.h>
+using namespace KXMLCore;
+using namespace WebCore;
+
+namespace WebCore {
+
+struct TextEncodingIDHashTraits : GenericHashTraits<TextEncodingID> {
+ static TraitType deletedValue() { return InvalidEncoding; }
+};
+
+}
+
namespace KXMLCore {
- template<> struct DefaultHash<WebCore::TextEncodingID> {
- typedef PtrHash<WebCore::TextEncodingID> Hash;
- };
+template<> struct HashKeyStorageTraits<IntHash<TextEncodingID>, TextEncodingIDHashTraits> {
+ typedef IntTypes<sizeof(TextEncodingID)>::SignedType IntType;
+ typedef IntHash<IntType> Hash;
+ typedef HashTraits<IntType> Traits;
+};
- template<> struct HashTraits<WebCore::TextEncodingID> : GenericHashTraits<WebCore::TextEncodingID> {
- static TraitType deletedValue() { return WebCore::InvalidEncoding; }
- };
-
-} // namespace KXMLCore
+}
namespace WebCore {
}
};
-static HashMap<const char*, const CharsetEntry*, EncodingHash>* nameMap;
-static HashMap<TextEncodingID, const CharsetEntry*>* encodingMap;
+typedef HashMap<const char*, const CharsetEntry*, EncodingHash> NameMap;
+typedef HashMap<TextEncodingID, const CharsetEntry*, IntHash<TextEncodingID>, TextEncodingIDHashTraits> EncodingMap;
+
+static NameMap* nameMap;
+static EncodingMap* encodingMap;
static void buildDictionaries()
{
- nameMap = new HashMap<const char*, const CharsetEntry*, EncodingHash>();
- encodingMap = new HashMap<TextEncodingID, const CharsetEntry*>();
+ nameMap = new NameMap;
+ encodingMap = new EncodingMap;
for (int i = 0; CharsetTable[i].name; ++i) {
nameMap->add(CharsetTable[i].name, &CharsetTable[i]);
namespace KXMLCore {
- template<> struct StrHash<WebCore::String> {
- static unsigned hash(const WebCore::String& key) { return key.impl()->hash(); }
- static bool equal(const WebCore::String& a, const WebCore::String& b)
- { return StrHash<WebCore::StringImpl*>::equal(a.impl(), b.impl()); }
- };
-
+ // StrHash is the default hash for String
+ template<typename T> struct DefaultHash;
+ template<typename T> struct StrHash;
template<> struct DefaultHash<WebCore::String> {
typedef StrHash<WebCore::String> Hash;
};
- template<> struct HashTraits<WebCore::String> {
- typedef WebCore::String TraitType;
- static const bool emptyValueIsZero = true;
- static const bool needsDestruction = true;
- static TraitType emptyValue() { return TraitType(); }
- static TraitType deletedValue() { return HashTraits<RefPtr<WebCore::StringImpl> >::_deleted.get(); }
- };
}
#endif
--- /dev/null
+/*
+ * Copyright (C) 2006 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 StringHash_h
+#define StringHash_h
+
+#include "AtomicStringImpl.h"
+#include "PlatformString.h"
+#include <kxmlcore/HashTraits.h>
+
+namespace KXMLCore {
+
+ template<typename T> struct StrHash;
+
+ template<> struct StrHash<WebCore::StringImpl*> {
+ static unsigned hash(const WebCore::StringImpl* key) { return key->hash(); }
+ static bool equal(const WebCore::StringImpl* a, const WebCore::StringImpl* b)
+ {
+ if (a == b)
+ return true;
+ if (!a || !b)
+ return false;
+
+ unsigned aLength = a->length();
+ unsigned bLength = b->length();
+ if (aLength != bLength)
+ return false;
+
+ const uint32_t* aChars = reinterpret_cast<const uint32_t*>(a->unicode());
+ const uint32_t* bChars = reinterpret_cast<const uint32_t*>(b->unicode());
+
+ unsigned halfLength = aLength >> 1;
+ for (unsigned 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 WebCore::StringImpl* str)
+ {
+ unsigned l = str->length();
+ const QChar* s = str->unicode();
+ 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 unsigned hash(const char* str, unsigned length)
+ {
+ // This hash is designed to work on 16-bit chunks at a time. But since the normal case
+ // (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
+ // were 16-bit chunks, which will give matching results.
+
+ unsigned l = length;
+ const char* s = str;
+ uint32_t hash = PHI;
+ uint32_t tmp;
+
+ int rem = l & 1;
+ l >>= 1;
+
+ // Main loop
+ for (; l > 0; l--) {
+ hash += QChar(s[0]).lower().unicode();
+ tmp = (QChar(s[1]).lower().unicode() << 11) ^ hash;
+ hash = (hash << 16) ^ tmp;
+ s += 2;
+ hash += hash >> 11;
+ }
+
+ // Handle end case
+ if (rem) {
+ hash += QChar(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 WebCore::StringImpl* a, const WebCore::StringImpl* b)
+ {
+ if (a == b) return true;
+ if (!a || !b) return false;
+ unsigned length = a->length();
+ if (length != b->length())
+ return false;
+ const QChar* as = a->unicode();
+ const QChar* bs = b->unicode();
+ for (unsigned i = 0; i != length; ++i)
+ if (as[i].lower() != bs[i].lower())
+ return false;
+ return true;
+ }
+ };
+
+ template<> struct StrHash<WebCore::AtomicStringImpl*> : public StrHash<WebCore::StringImpl*> {
+ };
+
+ template<> struct StrHash<RefPtr<WebCore::StringImpl> > {
+ static unsigned hash(const RefPtr<WebCore::StringImpl>& key) { return key->hash(); }
+ static bool equal(const RefPtr<WebCore::StringImpl>& a, const RefPtr<WebCore::StringImpl>& b)
+ {
+ return StrHash<WebCore::StringImpl*>::equal(a.get(), b.get());
+ }
+ };
+
+ template<> struct StrHash<WebCore::String> {
+ static unsigned hash(const WebCore::String& key) { return key.impl()->hash(); }
+ static bool equal(const WebCore::String& a, const WebCore::String& b)
+ {
+ return StrHash<WebCore::StringImpl*>::equal(a.impl(), b.impl());
+ }
+ };
+
+ // store WebCore::String as StringImpl*
+
+ template<> struct HashTraits<WebCore::String> : GenericHashTraits<WebCore::String> {
+ typedef HashTraits<WebCore::StringImpl*>::StorageTraits StorageTraits;
+ static const bool emptyValueIsZero = true;
+ static const bool needsRef = true;
+ static void ref(const WebCore::String& s) { if (s.impl()) s.impl()->ref(); }
+ static void deref(const WebCore::String& s) { if (s.impl()) s.impl()->deref(); }
+ };
+
+ // share code between StringImpl*, RefPtr<StringImpl>, and String
+
+ template<> struct HashKeyStorageTraits<StrHash<RefPtr<WebCore::StringImpl> >, HashTraits<RefPtr<WebCore::StringImpl> > > {
+ typedef StrHash<WebCore::StringImpl*> Hash;
+ typedef HashTraits<WebCore::StringImpl*> Traits;
+ };
+ template<> struct HashKeyStorageTraits<StrHash<WebCore::String>, HashTraits<WebCore::String> > {
+ typedef StrHash<WebCore::StringImpl*> Hash;
+ typedef HashTraits<WebCore::StringImpl*> Traits;
+ };
+
+}
+
+using KXMLCore::CaseInsensitiveHash;
+
+#endif
#include "AtomicString.h"
#include "Length.h"
+#include "StringHash.h"
#include <kjs/identifier.h>
#include <kxmlcore/Assertions.h>
#include <string.h>
}
} // namespace WebCore
-
-namespace KXMLCore {
-
-const RefPtr<WebCore::StringImpl> HashTraits<RefPtr<WebCore::StringImpl> >::_deleted = new WebCore::StringImpl(static_cast<char*>(0), 0);
-
-}
struct CStringTranslator;
struct Length;
-class StringImpl : public Shared<StringImpl>
+class StringImpl : public Shared<StringImpl>, Noncopyable
{
private:
struct WithOneRef { };
// For debugging only, leaks memory.
const char* ascii() const;
+#if __APPLE__
+ StringImpl(CFStringRef);
+ CFStringRef createCFString() const;
+#endif
+#if __OBJC__
+ StringImpl(NSString*);
+ operator NSString*() const;
+#endif
+
private:
unsigned m_length;
QChar* m_data;
-private:
friend class AtomicString;
friend struct QCharBufferTranslator;
friend struct CStringTranslator;
mutable unsigned m_hash;
bool m_inTable;
-
-public:
-#if __APPLE__
- StringImpl(CFStringRef);
- CFStringRef createCFString() const;
-#endif
-#if __OBJC__
- StringImpl(NSString*);
- operator NSString*() const;
-#endif
};
bool equal(const StringImpl*, const StringImpl*);
namespace KXMLCore {
- template<typename T> class DefaultHash;
- template<typename T> class StrHash;
-
- template<> struct StrHash<WebCore::StringImpl*> {
- static unsigned hash(const WebCore::StringImpl* key) { return key->hash(); }
- static bool equal(const WebCore::StringImpl* a, const WebCore::StringImpl* b)
- {
- if (a == b) return true;
- if (!a || !b) return false;
-
- unsigned aLength = a->length();
- unsigned bLength = b->length();
- if (aLength != bLength)
- return false;
-
- const uint32_t* aChars = reinterpret_cast<const uint32_t*>(a->unicode());
- const uint32_t* bChars = reinterpret_cast<const uint32_t*>(b->unicode());
-
- unsigned halfLength = aLength >> 1;
- for (unsigned 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 WebCore::StringImpl* str)
- {
- unsigned m_length = str->length();
- const QChar* m_data = str->unicode();
- uint32_t hash = PHI;
- uint32_t tmp;
-
- int rem = m_length & 1;
- m_length >>= 1;
-
- // Main loop
- for (; m_length > 0; m_length--) {
- hash += m_data[0].lower().unicode();
- tmp = (m_data[1].lower().unicode() << 11) ^ hash;
- hash = (hash << 16) ^ tmp;
- m_data += 2;
- hash += hash >> 11;
- }
-
- // Handle end case
- if (rem) {
- hash += m_data[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 unsigned hash(const char* str, unsigned length)
- {
- // This hash is designed to work on 16-bit chunks at a time. But since the normal case
- // (above) is to hash UTF-16 characters, we just treat the 8-bit chars as if they
- // were 16-bit chunks, which will give matching results.
-
- unsigned m_length = length;
- const char* m_data = str;
- uint32_t hash = PHI;
- uint32_t tmp;
-
- int rem = m_length & 1;
- m_length >>= 1;
-
- // Main loop
- for (; m_length > 0; m_length--) {
- hash += QChar(m_data[0]).lower().unicode();
- tmp = (QChar(m_data[1]).lower().unicode() << 11) ^ hash;
- hash = (hash << 16) ^ tmp;
- m_data += 2;
- hash += hash >> 11;
- }
-
- // Handle end case
- if (rem) {
- hash += QChar(m_data[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 WebCore::StringImpl* a, const WebCore::StringImpl* b)
- {
- if (a == b) return true;
- if (!a || !b) return false;
- unsigned length = a->length();
- if (length != b->length())
- return false;
- const QChar* as = a->unicode();
- const QChar* bs = b->unicode();
- for (unsigned i = 0; i != length; ++i)
- if (as[i].lower() != bs[i].lower())
- return false;
- return true;
- }
- };
-
- template<> struct StrHash<RefPtr<WebCore::StringImpl> > {
- static unsigned hash(const RefPtr<WebCore::StringImpl>& key)
- {
- return StrHash<WebCore::StringImpl*>::hash(key.get());
- }
-
- static bool equal(const RefPtr<WebCore::StringImpl>& a, const RefPtr<WebCore::StringImpl>& b)
- {
- return StrHash<WebCore::StringImpl*>::equal(a.get(), b.get());
- }
- };
-
+ // StrHash is the default hash for StringImpl* and RefPtr<StringImpl>
+ template<typename T> struct DefaultHash;
+ template<typename T> struct StrHash;
template<> struct DefaultHash<WebCore::StringImpl*> {
typedef StrHash<WebCore::StringImpl*> Hash;
};
-
template<> struct DefaultHash<RefPtr<WebCore::StringImpl> > {
typedef StrHash<RefPtr<WebCore::StringImpl> > Hash;
};
-
- template <typename T> class HashTraits;
-
- template<> struct HashTraits<RefPtr<WebCore::StringImpl> > {
- typedef RefPtr<WebCore::StringImpl> TraitType;
-
- static const bool emptyValueIsZero = true;
- static const bool needsDestruction = true;
- static const TraitType emptyValue() { return TraitType(); }
-
- static const TraitType _deleted;
- static const TraitType& deletedValue() { return _deleted; }
- };
}
-using KXMLCore::CaseInsensitiveHash;
-
#endif
#ifndef TransferJob_H_
#define TransferJob_H_
-#include "PlatformString.h"
+#include "StringHash.h"
+#include "Timer.h"
#include "TransferJobClient.h" // for PlatformResponse
#include <kxmlcore/HashMap.h>
-#include "Timer.h"
#ifdef WIN32
typedef unsigned long DWORD;
#define render_applet_h
#include "HTMLElement.h"
+#include "StringHash.h"
#include "render_replaced.h"
namespace WebCore {
+2006-04-05 Darin Adler <darin@apple.com>
+
+ Reviewed by Maciej.
+
+ * Scripts/check-for-global-initializers: Remove StringImpl from the list of files that
+ are allowed to have global initializers.
+
2006-04-05 Geoffrey Garen <ggaren@apple.com>
Reviewed by OMG BETH
if ($target eq "JavaScriptCore") {
next if $shortName eq "FastMalloc.o";
}
- if ($target eq "WebCore") {
- next if $shortName eq "StringImpl.o";
- }
print "$shortName has a global initializer in it! ($file)\n";
$sawError = 1;
}
}
+ my $httpdPath = "/usr/sbin/httpd";
my $httpdConfig = "$testDirectory/http/conf/httpd.conf";
+ $httpdConfig = "$testDirectory/http/conf/apache2-httpd.conf" if `$httpdPath -v` =~ m|Apache/2|;
my $documentRoot = "$testDirectory/http/tests";
my $typesConfig = "$testDirectory/http/conf/mime.types";
my $listen = "127.0.0.1:$httpdPort";
mkpath $absTestResultsDirectory;
- my $httpdPath;
- if (-x "/usr/sbin/httpd-1.3") {
- $httpdPath = "/usr/sbin/httpd-1.3";
- open CONFIG, $httpdConfig or die;
- open CONFIGOUT, ">", "/tmp/WebKit/httpd.conf" or die;
- while (<CONFIG>) {
- s|/httpd/|/httpd-1.3/|g;
- print CONFIGOUT;
- }
- close CONFIG;
- close CONFIGOUT;
- $httpdConfig = "/tmp/WebKit/httpd.conf";
- } elsif (-x "/usr/sbin/httpd") {
- $httpdPath = "/usr/sbin/httpd";
- } else {
- die "Can't locate the httpd binary";
- }
-
open2(\*HTTPDIN, \*HTTPDOUT, $httpdPath,
"-f", "$httpdConfig",
"-C", "DocumentRoot \"$documentRoot\"",
git://git.webkit.org / WebKit-https.git / commitdiff