[webkit-changes] cvs commit: WebCore/khtml/xml dom_atomicstring.cpp
Maciej
mjs at opensource.apple.com
Tue Jul 5 18:28:44 PDT 2005
mjs 05/07/05 18:28:44
Modified: . ChangeLog
WebCore.pbproj project.pbxproj
khtml/css cssstyleselector.cpp cssstyleselector.h
khtml/editing jsediting.cpp
khtml/misc hashset.h hashtable.cpp hashtable.h
khtml/xml dom_atomicstring.cpp
Added: ForwardingHeaders/misc hashmap.h hashset.h
khtml/misc hashfunctions.h hashmap.h hashtraits.h
pointerhash.h
Log:
Reviewed by hyatt.
Numerous hash code improvements:
- added HashMap and the required support for it in HashTable
- convert to using deleted sentinels and double hashing instead of linear
probing and reinsert on delete
- add support for traits so that empty and deleted values can be customized
per type
- make insert return a pair of an iterator and a bool even at the API level
- converted some code to use HashMap
- added standard hash and equal functions for some types, plus case insensitive ones
- lots of assorted code cleanup
- pass hash functions as classes with two static functions instead of as functions
* khtml/css/cssstyleselector.cpp:
(khtml::CSSRuleSet::CSSRuleSet): Use HashMap instead of QPtrDict.
(khtml::CSSRuleSet::~CSSRuleSet): ditto
(khtml::CSSRuleSet::addToRuleSet): ditto
(khtml::CSSRuleSet::addRule): ditto
* khtml/css/cssstyleselector.h:
(khtml::CSSRuleSet::getIDRules): ditto
(khtml::CSSRuleSet::getClassRules): ditto
(khtml::CSSRuleSet::getTagRules): ditto
* khtml/editing/jsediting.cpp:
(DOM::DocumentImpl::commandImp): ditto
* khtml/misc/hashfunctions.h: Added. Standard hash functions.
(khtml::defaultEqual):
(khtml::pointerHash<4>):
(khtml::pointerHash<8>):
(khtml::defaultHash<void *>):
(khtml::defaultHash<DOM::DOMStringImpl *>):
(khtml::caseInsensitiveHash):
(khtml::caseInsensitiveEqual):
* WebCore.pbproj/project.pbxproj:
* khtml/misc/hashmap.h: Added.
(khtml::HashMap::HashMap):
(khtml::HashMap::size):
(khtml::HashMap::capacity):
(khtml::HashMap::isEmpty):
(khtml::HashMap::begin):
(khtml::HashMap::end):
(khtml::HashMap::find):
(khtml::HashMap::contains):
(khtml::HashMap::insert):
(khtml::HashMap::get):
(khtml::HashMap::remove):
(khtml::HashMap::clear):
(khtml::HashMap::extractKey):
* khtml/misc/hashset.h:
(khtml::identityExtract):
(khtml::::size):
(khtml::::capacity):
(khtml::::isEmpty):
(khtml::::begin):
(khtml::::end):
(khtml::::find):
(khtml::::contains):
(khtml::::insert):
(khtml::::remove):
(khtml::::clear):
(khtml::::convertAdapter):
* khtml/misc/hashtable.cpp:
(khtml::HashTableStats::~HashTableStats):
* khtml/misc/hashtable.h:
(khtml::HashTableIterator::HashTableIterator):
(khtml::HashTableIterator::skipEmptyBuckets):
(khtml::HashTableConstIterator::HashTableConstIterator):
(khtml::HashTableConstIterator::skipEmptyBuckets):
(khtml::HashTable::HashTable):
(khtml::HashTable::insert):
(khtml::HashTable::isEmptyBucket):
(khtml::HashTable::isDeletedBucket):
(khtml::HashTable::isEmptyOrDeletedBucket):
(khtml::HashTable::identityConvert):
(khtml::HashTable::extractKey):
(khtml::HashTable::lookup):
(khtml::HashTable::shouldExpand):
(khtml::HashTable::mustRehashInPlace):
(khtml::HashTable::clearBucket):
(khtml::HashTable::deleteBucket):
(khtml::HashTable::makeLookupResult):
(khtml::HashTable::makeIterator):
(khtml::HashTable::makeConstIterator):
(khtml::::lookup):
(khtml::::insert):
(khtml::::reinsert):
(khtml::::find):
(khtml::::contains):
(khtml::::remove):
(khtml::::allocateTable):
(khtml::::expand):
(khtml::::rehash):
(khtml::::clear):
(khtml::::HashTable):
(khtml::::swap):
(khtml::::operator):
(khtml::::checkConsistency):
(khtml::::checkConsistencyExceptSize):
* khtml/misc/hashtraits.h: Added.
(khtml::HashTraits::emptyValue):
(khtml::):
(khtml::PairHashTraits::emptyValue):
(khtml::PairHashTraits::deletedValue):
* ForwardingHeaders/misc/hashmap.h: Added.
* ForwardingHeaders/misc/hashset.h: Added.
* WebCore.pbproj/project.pbxproj: Added new files.
* khtml/misc/pointerhash.h: Added.
(khtml::PointerHashIteratorAdapter::PointerHashIteratorAdapter):
(khtml::PointerHashIteratorAdapter::operator*):
(khtml::PointerHashIteratorAdapter::operator->):
(khtml::PointerHashIteratorAdapter::operator++):
(khtml::PointerHashIteratorAdapter::operator==):
(khtml::PointerHashIteratorAdapter::operator!=):
(khtml::PointerHashConstIteratorAdapter::PointerHashConstIteratorAdapter):
(khtml::PointerHashConstIteratorAdapter::operator*):
(khtml::PointerHashConstIteratorAdapter::operator->):
(khtml::PointerHashConstIteratorAdapter::operator++):
(khtml::PointerHashConstIteratorAdapter::operator==):
(khtml::PointerHashConstIteratorAdapter::operator!=):
(khtml::):
Revision Changes Path
1.4372 +124 -0 WebCore/ChangeLog
Index: ChangeLog
===================================================================
RCS file: /cvs/root/WebCore/ChangeLog,v
retrieving revision 1.4371
retrieving revision 1.4372
diff -u -r1.4371 -r1.4372
--- ChangeLog 6 Jul 2005 00:21:44 -0000 1.4371
+++ ChangeLog 6 Jul 2005 01:28:35 -0000 1.4372
@@ -1,3 +1,127 @@
+2005-07-04 Maciej Stachowiak <mjs at apple.com>
+
+ Reviewed by hyatt.
+
+ Numerous hash code improvements:
+
+ - added HashMap and the required support for it in HashTable
+ - convert to using deleted sentinels and double hashing instead of linear
+ probing and reinsert on delete
+ - add support for traits so that empty and deleted values can be customized
+ per type
+ - make insert return a pair of an iterator and a bool even at the API level
+ - converted some code to use HashMap
+ - added standard hash and equal functions for some types, plus case insensitive ones
+ - lots of assorted code cleanup
+ - pass hash functions as classes with two static functions instead of as functions
+
+ * khtml/css/cssstyleselector.cpp:
+ (khtml::CSSRuleSet::CSSRuleSet): Use HashMap instead of QPtrDict.
+ (khtml::CSSRuleSet::~CSSRuleSet): ditto
+ (khtml::CSSRuleSet::addToRuleSet): ditto
+ (khtml::CSSRuleSet::addRule): ditto
+ * khtml/css/cssstyleselector.h:
+ (khtml::CSSRuleSet::getIDRules): ditto
+ (khtml::CSSRuleSet::getClassRules): ditto
+ (khtml::CSSRuleSet::getTagRules): ditto
+ * khtml/editing/jsediting.cpp:
+ (DOM::DocumentImpl::commandImp): ditto
+ * khtml/misc/hashfunctions.h: Added. Standard hash functions.
+ (khtml::defaultEqual):
+ (khtml::pointerHash<4>):
+ (khtml::pointerHash<8>):
+ (khtml::defaultHash<void *>):
+ (khtml::defaultHash<DOM::DOMStringImpl *>):
+ (khtml::caseInsensitiveHash):
+ (khtml::caseInsensitiveEqual):
+ * WebCore.pbproj/project.pbxproj:
+ * khtml/misc/hashmap.h: Added.
+ (khtml::HashMap::HashMap):
+ (khtml::HashMap::size):
+ (khtml::HashMap::capacity):
+ (khtml::HashMap::isEmpty):
+ (khtml::HashMap::begin):
+ (khtml::HashMap::end):
+ (khtml::HashMap::find):
+ (khtml::HashMap::contains):
+ (khtml::HashMap::insert):
+ (khtml::HashMap::get):
+ (khtml::HashMap::remove):
+ (khtml::HashMap::clear):
+ (khtml::HashMap::extractKey):
+ * khtml/misc/hashset.h:
+ (khtml::identityExtract):
+ (khtml::::size):
+ (khtml::::capacity):
+ (khtml::::isEmpty):
+ (khtml::::begin):
+ (khtml::::end):
+ (khtml::::find):
+ (khtml::::contains):
+ (khtml::::insert):
+ (khtml::::remove):
+ (khtml::::clear):
+ (khtml::::convertAdapter):
+ * khtml/misc/hashtable.cpp:
+ (khtml::HashTableStats::~HashTableStats):
+ * khtml/misc/hashtable.h:
+ (khtml::HashTableIterator::HashTableIterator):
+ (khtml::HashTableIterator::skipEmptyBuckets):
+ (khtml::HashTableConstIterator::HashTableConstIterator):
+ (khtml::HashTableConstIterator::skipEmptyBuckets):
+ (khtml::HashTable::HashTable):
+ (khtml::HashTable::insert):
+ (khtml::HashTable::isEmptyBucket):
+ (khtml::HashTable::isDeletedBucket):
+ (khtml::HashTable::isEmptyOrDeletedBucket):
+ (khtml::HashTable::identityConvert):
+ (khtml::HashTable::extractKey):
+ (khtml::HashTable::lookup):
+ (khtml::HashTable::shouldExpand):
+ (khtml::HashTable::mustRehashInPlace):
+ (khtml::HashTable::clearBucket):
+ (khtml::HashTable::deleteBucket):
+ (khtml::HashTable::makeLookupResult):
+ (khtml::HashTable::makeIterator):
+ (khtml::HashTable::makeConstIterator):
+ (khtml::::lookup):
+ (khtml::::insert):
+ (khtml::::reinsert):
+ (khtml::::find):
+ (khtml::::contains):
+ (khtml::::remove):
+ (khtml::::allocateTable):
+ (khtml::::expand):
+ (khtml::::rehash):
+ (khtml::::clear):
+ (khtml::::HashTable):
+ (khtml::::swap):
+ (khtml::::operator):
+ (khtml::::checkConsistency):
+ (khtml::::checkConsistencyExceptSize):
+ * khtml/misc/hashtraits.h: Added.
+ (khtml::HashTraits::emptyValue):
+ (khtml::):
+ (khtml::PairHashTraits::emptyValue):
+ (khtml::PairHashTraits::deletedValue):
+ * ForwardingHeaders/misc/hashmap.h: Added.
+ * ForwardingHeaders/misc/hashset.h: Added.
+ * WebCore.pbproj/project.pbxproj: Added new files.
+ * khtml/misc/pointerhash.h: Added.
+ (khtml::PointerHashIteratorAdapter::PointerHashIteratorAdapter):
+ (khtml::PointerHashIteratorAdapter::operator*):
+ (khtml::PointerHashIteratorAdapter::operator->):
+ (khtml::PointerHashIteratorAdapter::operator++):
+ (khtml::PointerHashIteratorAdapter::operator==):
+ (khtml::PointerHashIteratorAdapter::operator!=):
+ (khtml::PointerHashConstIteratorAdapter::PointerHashConstIteratorAdapter):
+ (khtml::PointerHashConstIteratorAdapter::operator*):
+ (khtml::PointerHashConstIteratorAdapter::operator->):
+ (khtml::PointerHashConstIteratorAdapter::operator++):
+ (khtml::PointerHashConstIteratorAdapter::operator==):
+ (khtml::PointerHashConstIteratorAdapter::operator!=):
+ (khtml::):
+
2005-07-05 Geoffrey Garen <ggaren at apple.com>
Rolled in patch by opendarwin.org at mitzpettel.com
1.1 WebCore/ForwardingHeaders/misc/hashmap.h
Index: hashmap.h
===================================================================
#import <hashmap.h>
1.1 WebCore/ForwardingHeaders/misc/hashset.h
Index: hashset.h
===================================================================
#import <hashset.h>
1.561 +35 -3 WebCore/WebCore.pbproj/project.pbxproj
Index: project.pbxproj
===================================================================
RCS file: /cvs/root/WebCore/WebCore.pbproj/project.pbxproj,v
retrieving revision 1.560
retrieving revision 1.561
diff -u -r1.560 -r1.561
--- project.pbxproj 5 Jul 2005 07:57:47 -0000 1.560
+++ project.pbxproj 6 Jul 2005 01:28:41 -0000 1.561
@@ -1279,6 +1279,34 @@
settings = {
};
};
+ 65DE852708765FC30011428A = {
+ fileEncoding = 30;
+ isa = PBXFileReference;
+ lastKnownFileType = sourcecode.c.h;
+ path = hashmap.h;
+ refType = 4;
+ sourceTree = "<group>";
+ };
+ 65DE852808765FC30011428A = {
+ fileEncoding = 30;
+ isa = PBXFileReference;
+ lastKnownFileType = sourcecode.c.h;
+ path = hashtraits.h;
+ refType = 4;
+ sourceTree = "<group>";
+ };
+ 65DE852908765FC30011428A = {
+ fileRef = 65DE852708765FC30011428A;
+ isa = PBXBuildFile;
+ settings = {
+ };
+ };
+ 65DE852A08765FC30011428A = {
+ fileRef = 65DE852808765FC30011428A;
+ isa = PBXBuildFile;
+ settings = {
+ };
+ };
65F378260870D958000B2F94 = {
fileEncoding = 30;
isa = PBXFileReference;
@@ -2768,6 +2796,8 @@
550A0BCE085F604D007353D6,
65F378290870D958000B2F94,
65F3782B0870D958000B2F94,
+ 65DE852908765FC30011428A,
+ 65DE852A08765FC30011428A,
A85D7C19087A6ED9006A9172,
);
isa = PBXHeadersBuildPhase;
@@ -8875,9 +8905,6 @@
};
F523D29C02DE43D9018635CA = {
children = (
- 65F378260870D958000B2F94,
- 65F378270870D958000B2F94,
- 65F378280870D958000B2F94,
BC7294F703804B3C00A80166,
BC7294F803804B3C00A80166,
F523D27802DE43D7018635CA,
@@ -8886,6 +8913,11 @@
93ABCE5E06E1A42E0085925B,
F523D27A02DE43D7018635CA,
F523D27B02DE43D7018635CA,
+ 65F378260870D958000B2F94,
+ 65F378270870D958000B2F94,
+ 65F378280870D958000B2F94,
+ 65DE852708765FC30011428A,
+ 65DE852808765FC30011428A,
F523D27E02DE43D7018635CA,
F523D27F02DE43D7018635CA,
F523D28202DE43D7018635CA,
1.188 +31 -11 WebCore/khtml/css/cssstyleselector.cpp
Index: cssstyleselector.cpp
===================================================================
RCS file: /cvs/root/WebCore/khtml/css/cssstyleselector.cpp,v
retrieving revision 1.187
retrieving revision 1.188
diff -u -r1.187 -r1.188
--- cssstyleselector.cpp 12 Jun 2005 04:07:30 -0000 1.187
+++ cssstyleselector.cpp 6 Jul 2005 01:28:41 -0000 1.188
@@ -339,7 +339,7 @@
matchRulesForList(rules->getClassRules(singleClass->string().implementation()),
firstRuleIndex, lastRuleIndex);
}
- matchRulesForList(rules->getTagRules((void*)(int)localNamePart(element->id())),
+ matchRulesForList(rules->getTagRules(localNamePart(element->id())),
firstRuleIndex, lastRuleIndex);
matchRulesForList(rules->getUniversalRules(), firstRuleIndex, lastRuleIndex);
@@ -1394,23 +1394,42 @@
CSSRuleSet::CSSRuleSet()
{
- m_idRules.setAutoDelete(true);
- m_classRules.setAutoDelete(true);
- m_tagRules.setAutoDelete(true);
m_universalRules = 0;
m_ruleCount = 0;
}
-void CSSRuleSet::addToRuleSet(void* hash, QPtrDict<CSSRuleDataList>& dict,
+CSSRuleSet::~CSSRuleSet()
+{
+ deleteAllValues(m_idRules);
+ deleteAllValues(m_classRules);
+ deleteAllValues(m_tagRules);
+
+ delete m_universalRules;
+}
+
+
+void CSSRuleSet::addToRuleSet(DOM::DOMStringImpl* key, AtomRuleMap& map,
CSSStyleRuleImpl* rule, CSSSelector* sel)
{
- if (!hash) return;
- CSSRuleDataList* rules = dict.find(hash);
+ if (!key) return;
+ CSSRuleDataList* rules = map.get(key);
if (!rules) {
rules = new CSSRuleDataList(m_ruleCount++, rule, sel);
- dict.insert(hash, rules);
- }
- else
+ map.insert(key, rules);
+ } else
+ rules->append(m_ruleCount++, rule, sel);
+}
+
+void CSSRuleSet::addToRuleSet(int key, IntRuleMap& map,
+ CSSStyleRuleImpl* rule, CSSSelector* sel)
+{
+ assert(key);
+ assert(key != -1);
+ CSSRuleDataList* rules = map.get(key);
+ if (!rules) {
+ rules = new CSSRuleDataList(m_ruleCount++, rule, sel);
+ map.insert(key, rules);
+ } else
rules->append(m_ruleCount++, rule, sel);
}
@@ -1427,7 +1446,8 @@
Q_UINT16 localName = localNamePart(sel->tag);
if (localName != anyLocalName) {
- addToRuleSet((void*)(int)localName, m_tagRules, rule, sel);
+ // FIXME: maybe it would be better to just use an int-keyed HashMap here
+ addToRuleSet(localName, m_tagRules, rule, sel);
return;
}
1.34 +15 -9 WebCore/khtml/css/cssstyleselector.h
Index: cssstyleselector.h
===================================================================
RCS file: /cvs/root/WebCore/khtml/css/cssstyleselector.h,v
retrieving revision 1.33
retrieving revision 1.34
diff -u -r1.33 -r1.34
--- cssstyleselector.h 11 May 2005 05:49:34 -0000 1.33
+++ cssstyleselector.h 6 Jul 2005 01:28:42 -0000 1.34
@@ -25,6 +25,7 @@
#include <qptrvector.h>
#include <qptrdict.h>
+#include "misc/pointerhash.h"
#include "rendering/render_style.h"
#include "dom/dom_string.h"
@@ -268,26 +269,31 @@
{
public:
CSSRuleSet();
- ~CSSRuleSet() { delete m_universalRules; }
+ ~CSSRuleSet();
MAIN_THREAD_ALLOCATED;
+ typedef HashMap<DOM::DOMStringImpl *, CSSRuleDataList *, PointerHash<DOM::DOMStringImpl *> > AtomRuleMap;
+ typedef HashMap<int, CSSRuleDataList *, PointerHash<int> > IntRuleMap;
+
void addRulesFromSheet(DOM::CSSStyleSheetImpl* sheet, const DOM::DOMString &medium = "screen");
void addRule(DOM::CSSStyleRuleImpl* rule, DOM::CSSSelector* sel);
- void addToRuleSet(void* hash, QPtrDict<CSSRuleDataList>& dict,
+ void addToRuleSet(DOM::DOMStringImpl* key, AtomRuleMap& map,
+ DOM::CSSStyleRuleImpl* rule, DOM::CSSSelector* sel);
+ void addToRuleSet(int key, IntRuleMap& map,
DOM::CSSStyleRuleImpl* rule, DOM::CSSSelector* sel);
- CSSRuleDataList* getIDRules(void* hash) { return m_idRules.find(hash); }
- CSSRuleDataList* getClassRules(void* hash) { return m_classRules.find(hash); }
- CSSRuleDataList* getTagRules(void* hash) { return m_tagRules.find(hash); }
+ CSSRuleDataList* getIDRules(DOM::DOMStringImpl* key) { return m_idRules.get(key); }
+ CSSRuleDataList* getClassRules(DOM::DOMStringImpl* key) { return m_classRules.get(key); }
+ CSSRuleDataList* getTagRules(int key) { return m_tagRules.get(key); }
CSSRuleDataList* getUniversalRules() { return m_universalRules; }
public:
- QPtrDict<CSSRuleDataList> m_idRules;
- QPtrDict<CSSRuleDataList> m_classRules;
- QPtrDict<CSSRuleDataList> m_tagRules;
- CSSRuleDataList* m_universalRules;
+ AtomRuleMap m_idRules;
+ AtomRuleMap m_classRules;
+ IntRuleMap m_tagRules;
+ CSSRuleDataList* m_universalRules;
uint m_ruleCount;
};
1.28 +15 -8 WebCore/khtml/editing/jsediting.cpp
Index: jsediting.cpp
===================================================================
RCS file: /cvs/root/WebCore/khtml/editing/jsediting.cpp,v
retrieving revision 1.27
retrieving revision 1.28
diff -u -r1.27 -r1.28
--- jsediting.cpp 26 May 2005 20:30:12 -0000 1.27
+++ jsediting.cpp 6 Jul 2005 01:28:42 -0000 1.28
@@ -30,14 +30,16 @@
#include "htmlediting.h"
#include "khtml_part.h"
-#include <qstring.h>
#include "selection.h"
+#include "misc/hashmap.h"
#if APPLE_CHANGES
#include "KWQKHTMLPart.h"
#endif
using khtml::TypingCommand;
+using khtml::HashMap;
+using khtml::CaseInsensitiveHash;
namespace DOM {
@@ -54,12 +56,14 @@
DOMString (*valueFn)(KHTMLPart *part);
};
-QDict<CommandImp> createCommandDictionary();
+typedef HashMap<DOMStringImpl *, const CommandImp *, CaseInsensitiveHash> CommandMap;
+
+CommandMap *createCommandDictionary();
const CommandImp *commandImp(const DOMString &command)
{
- static QDict<CommandImp> commandDictionary = createCommandDictionary();
- return commandDictionary.find(command.string());
+ static CommandMap *commandDictionary = createCommandDictionary();
+ return commandDictionary->get(command.implementation());
}
} // anonymous namespace
@@ -491,7 +495,7 @@
// =============================================================================================
-QDict<CommandImp> createCommandDictionary()
+CommandMap *createCommandDictionary()
{
struct EditorCommand { const char *name; CommandImp imp; };
@@ -589,15 +593,18 @@
// Unlink (not supported)
};
+ CommandMap *commandMap = new CommandMap;
+
const int numCommands = sizeof(commands) / sizeof(commands[0]);
- QDict<CommandImp> commandDictionary(numCommands, false); // case-insensitive dictionary
for (int i = 0; i < numCommands; ++i) {
- commandDictionary.insert(commands[i].name, &commands[i].imp);
+ DOMStringImpl *name = new DOMStringImpl(commands[i].name);
+ name->ref();
+ commandMap->insert(name, &commands[i].imp);
}
#ifndef NDEBUG
supportsPasteCommand = true;
#endif
- return commandDictionary;
+ return commandMap;
}
} // anonymous namespace
1.3 +134 -45 WebCore/khtml/misc/hashset.h
Index: hashset.h
===================================================================
RCS file: /cvs/root/WebCore/khtml/misc/hashset.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- hashset.h 29 Jun 2005 21:04:31 -0000 1.2
+++ hashset.h 6 Jul 2005 01:28:42 -0000 1.3
@@ -24,71 +24,160 @@
#define HASHSET_H
#include "hashtable.h"
+#include "hashtraits.h"
+#include "hashfunctions.h"
namespace khtml {
-template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
+template <typename T>
+inline T identityExtract(const T& t)
+{
+ return t;
+}
+
+template<typename Value, typename HashFunctions = DefaultHash<Value>, typename Traits = HashTraits<Value> >
class HashSet {
private:
- typedef HashTable<Key, Hash, Equal> ImplType;
- typedef typename ImplType::KeyType KeyType;
+ typedef HashTable<Value, Value, identityExtract<Value>, HashFunctions, Traits> ImplType;
public:
+ typedef Value ValueType;
typedef typename ImplType::iterator iterator;
typedef typename ImplType::const_iterator const_iterator;
HashSet() {}
- int size() const { return m_impl.count(); }
- int capacity() const { return m_impl.capacity(); }
- bool isEmpty() const { return size() == 0; }
-
- iterator begin() { m_impl.begin(); }
- iterator end() { return m_impl.end(); }
- const_iterator begin() const { m_impl.begin(); }
- const_iterator end() const { m_impl.end(); }
-
- iterator insert(const KeyType &key)
- {
- return m_impl.insert(key);
- }
+ int size() const;
+ int capacity() const;
+ bool isEmpty() const;
+
+ iterator begin();
+ iterator end();
+ const_iterator begin() const;
+ const_iterator end() const;
+
+ iterator find(const ValueType& value);
+ const_iterator find(const ValueType& value) const;
+ bool contains(const ValueType& value) const;
+
+ std::pair<iterator, bool> insert(const ValueType &value);
// a special version of insert() that finds the object by hashing and comparing
// with some other type, to avoid the cost of type conversion if the object is already
// in the table
- template<typename T, unsigned HashT(const T&), bool EqualT(const KeyType&, const T&), KeyType ConvertT(const T&, unsigned)> iterator insert(const T& key)
- {
- return m_impl.insert<T, HashT, EqualT, ConvertT>(key);
- }
-
- iterator find(const KeyType& key)
- {
- return m_impl.find(key);
- }
-
- bool contains(const KeyType& key)
- {
- return m_impl.contains(key);
- }
-
- void remove(const KeyType& key)
- {
- m_impl.remove(key);
- }
-
- void remove(iterator it)
- {
- m_impl.remove(it);
- }
-
- void clear()
- {
- m_impl.clear();
- }
+ template<typename T, unsigned HashT(const T&), bool EqualT(const ValueType&, const T&), ValueType ConvertT(const T&, unsigned)>
+ std::pair<iterator, bool> insert(const T& value);
+
+ void remove(const ValueType& value);
+ void remove(iterator it);
+ void clear();
private:
+ template<typename T, ValueType ConvertT(const T&, unsigned)>
+ static ValueType convertAdapter(const T& t, const T&, unsigned h);
+
ImplType m_impl;
};
+template<typename Value, typename HashFunctions, typename Traits>
+int HashSet<Value, HashFunctions, Traits>::size() const
+{
+ return m_impl.count();
+}
+
+template<typename Value, typename HashFunctions, typename Traits>
+int HashSet<Value, HashFunctions, Traits>::capacity() const
+{
+ return m_impl.capacity();
+}
+
+template<typename Value, typename HashFunctions, typename Traits>
+bool HashSet<Value, HashFunctions, Traits>::isEmpty() const
+{
+ return size() == 0;
+}
+
+template<typename Value, typename HashFunctions, typename Traits>
+typename HashSet<Value, HashFunctions, Traits>::iterator HashSet<Value, HashFunctions, Traits>::begin()
+{
+ return m_impl.begin();
+}
+
+template<typename Value, typename HashFunctions, typename Traits>
+typename HashSet<Value, HashFunctions, Traits>::iterator HashSet<Value, HashFunctions, Traits>::end()
+{
+ return m_impl.end();
+}
+
+template<typename Value, typename HashFunctions, typename Traits>
+typename HashSet<Value, HashFunctions, Traits>::const_iterator HashSet<Value, HashFunctions, Traits>::begin() const
+{
+ return m_impl.begin();
+}
+
+template<typename Value, typename HashFunctions, typename Traits>
+typename HashSet<Value, HashFunctions, Traits>::const_iterator HashSet<Value, HashFunctions, Traits>::end() const
+{
+ return m_impl.end();
+}
+
+template<typename Value, typename HashFunctions, typename Traits>
+typename HashSet<Value, HashFunctions, Traits>::iterator HashSet<Value, HashFunctions, Traits>::find(const ValueType& value)
+{
+ return m_impl.find(value);
+}
+
+template<typename Value, typename HashFunctions, typename Traits>
+typename HashSet<Value, HashFunctions, Traits>::const_iterator HashSet<Value, HashFunctions, Traits>::find(const ValueType& value) const
+{
+ return m_impl.find(value);
+}
+
+template<typename Value, typename HashFunctions, typename Traits>
+bool HashSet<Value, HashFunctions, Traits>::contains(const ValueType& value) const
+{
+ return m_impl.contains(value);
+}
+
+template<typename Value, typename HashFunctions, typename Traits>
+std::pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool> HashSet<Value, HashFunctions, Traits>::insert(const ValueType &value)
+{
+ return m_impl.insert(value);
+}
+
+template<typename Value, typename HashFunctions, typename Traits>
+template<typename T, unsigned HashT(const T&), bool EqualT(const Value&, const T&), Value ConvertT(const T&, unsigned)>
+std::pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool> HashSet<Value, HashFunctions, Traits>::insert(const T& value)
+{
+ return m_impl.insert<T, T, HashT, EqualT, HashSet::convertAdapter<T, ConvertT> >(value, value);
+}
+
+template<typename Value, typename HashFunctions, typename Traits>
+void HashSet<Value, HashFunctions, Traits>::remove(const ValueType& value)
+{
+ m_impl.remove(value);
+}
+
+template<typename Value, typename HashFunctions, typename Traits>
+void HashSet<Value, HashFunctions, Traits>::remove(iterator it)
+{
+ m_impl.remove(it);
+}
+
+template<typename Value, typename HashFunctions, typename Traits>
+void HashSet<Value, HashFunctions, Traits>::clear()
+{
+ m_impl.clear();
+}
+
+template<typename Value, typename HashFunctions, typename Traits>
+template<typename T, Value ConvertT(const T&, unsigned)>
+inline Value HashSet<Value, HashFunctions, Traits>::convertAdapter(const T& t, const T&, unsigned h)
+{
+ return ConvertT(t, h);
+}
+
} // namespace khtml
#endif /* HASHSET_H */
+
+
1.2 +1 -1 WebCore/khtml/misc/hashtable.cpp
Index: hashtable.cpp
===================================================================
RCS file: /cvs/root/WebCore/khtml/misc/hashtable.cpp,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- hashtable.cpp 28 Jun 2005 21:18:17 -0000 1.1
+++ hashtable.cpp 6 Jul 2005 01:28:43 -0000 1.2
@@ -45,7 +45,7 @@
printf(" %d lookups with exactly %d collisions (%.2f%% , %.2f%% with this many or more)\n", collisionGraph[i], i, 100.0 * (collisionGraph[i] - collisionGraph[i+1]) / numAccesses, 100.0 * collisionGraph[i] / numAccesses);
}
printf("%d rehashes\n", numRehashes);
- printf("%d removes, %d reinserts\n", numRemoves, numReinserts);
+ printf("%d reinserts\n", numReinserts);
}
void HashTableStats::recordCollisionAtCount(int count)
1.4 +250 -190 WebCore/khtml/misc/hashtable.h
Index: hashtable.h
===================================================================
RCS file: /cvs/root/WebCore/khtml/misc/hashtable.h,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- hashtable.h 30 Jun 2005 03:19:13 -0000 1.3
+++ hashtable.h 6 Jul 2005 01:28:43 -0000 1.4
@@ -24,10 +24,11 @@
#define HASHTABLE_H
#include "main_thread_malloc.h"
+#include <utility>
namespace khtml {
-#define DUMP_HASHTABLE_STATS 0
+#define DUMP_HASHTABLE_STATS 1
#define CHECK_HASHTABLE_CONSISTENCY 0
#if DUMP_HASHTABLE_STATS
@@ -47,30 +48,26 @@
#endif
#if !CHECK_HASHTABLE_CONSISTENCY
-#define checkConsistency() ((void)0)
-#define checkConsistencyExceptSize() ((void)0)
+#define checkTableConsistency() ((void)0)
+#define checkTableConsistencyExceptSize() ((void)0)
#endif
-// FIXME: this template actually depends on Key being a pointer type in two ways:
-// it compares to 0 to check for empty slots, and assigns to 0 when deleting.
-
-template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
class HashTable;
-template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
class HashTableIterator {
private:
- typedef HashTable<Key, Hash, Equal> HashTableType;
- typedef HashTableType *HashTablePointerType;
- typedef HashTableIterator<Key, Hash, Equal> iterator;
- typedef Key KeyType;
- typedef KeyType& ReferenceType;
- typedef KeyType *PointerType;
+ typedef HashTable<Key, Value, ExtractKey, HashFunctions, Traits> HashTableType;
+ typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits> iterator;
+ typedef Value ValueType;
+ typedef ValueType& ReferenceType;
+ typedef ValueType *PointerType;
- friend class HashTable<Key, Hash, Equal>;
+ friend class HashTable<Key, Value, ExtractKey, HashFunctions, Traits>;
- HashTableIterator(HashTablePointerType table, PointerType position, PointerType endPosition)
- : m_table(table), m_position(position), m_endPosition(endPosition)
+ HashTableIterator(PointerType position, PointerType endPosition)
+ : m_position(position), m_endPosition(endPosition)
{
skipEmptyBuckets();
}
@@ -82,13 +79,6 @@
ReferenceType operator*() const { return *m_position; }
PointerType operator->() const { return &(operator*()); }
- void skipEmptyBuckets()
- {
- while (m_position != m_endPosition && (m_table->isEmptyBucket(*m_position))) {
- ++m_position;
- }
- }
-
iterator& operator++()
{
++m_position;
@@ -106,37 +96,42 @@
bool operator!=(const iterator& other) const
{
- return m_position != other.m_posisiton;
+ return m_position != other.m_position;
}
private:
- HashTablePointerType m_table;
+ void skipEmptyBuckets()
+ {
+ while (m_position != m_endPosition && (HashTableType::isEmptyOrDeletedBucket(*m_position))) {
+ ++m_position;
+ }
+ }
+
PointerType m_position;
PointerType m_endPosition;
};
-template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
class HashTableConstIterator {
private:
- typedef HashTable<Key, Hash, Equal> HashTableType;
- typedef const HashTableType *HashTablePointerType;
- typedef HashTableIterator<Key, Hash, Equal> iterator;
- typedef HashTableConstIterator<Key, Hash, Equal> const_iterator;
- typedef Key KeyType;
- typedef const KeyType& ReferenceType;
- typedef const KeyType *PointerType;
+ typedef HashTable<Key, Value, ExtractKey, HashFunctions, Traits> HashTableType;
+ typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits> iterator;
+ typedef HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits> const_iterator;
+ typedef Value ValueType;
+ typedef const ValueType& ReferenceType;
+ typedef const ValueType *PointerType;
- friend class HashTable<Key, Hash, Equal>;
+ friend class HashTable<Key, Value, ExtractKey, HashFunctions, Traits>;
- HashTableConstIterator(HashTablePointerType table, PointerType position, PointerType endPosition)
- : m_table(table), m_position(position), m_endPosition(endPosition)
+ HashTableConstIterator(PointerType position, PointerType endPosition)
+ : m_position(position), m_endPosition(endPosition)
{
skipEmptyBuckets();
}
public:
HashTableConstIterator() {}
HashTableConstIterator(const iterator &other)
- : m_table(other.ht), m_position(other.m_position), m_endPosition(other.m_endPosition) { }
+ : m_position(other.m_position), m_endPosition(other.m_endPosition) { }
// default copy, assignment and destructor are ok
@@ -145,7 +140,7 @@
void skipEmptyBuckets()
{
- while (m_position != m_endPosition && (m_table->isEmptyBucket(*m_position))) {
+ while (m_position != m_endPosition && (HashTableType::isEmptyOrDeletedBucket(*m_position))) {
++m_position;
}
}
@@ -160,32 +155,30 @@
// postfix ++ intentionally omitted
// Comparison.
- bool operator==(const iterator& other) const
+ bool operator==(const const_iterator& other) const
{
return m_position == other.m_position;
}
- bool operator!=(const iterator& other) const
+ bool operator!=(const const_iterator& other) const
{
- return m_position != other.m_posisiton;
+ return m_position != other.m_position;
}
private:
- HashTablePointerType m_table;
PointerType m_position;
PointerType m_endPosition;
};
-template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
class HashTable {
public:
- typedef HashTableIterator<Key, Hash, Equal> iterator;
- typedef HashTableConstIterator<Key, Hash, Equal> const_iterator;
+ typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits> iterator;
+ typedef HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits> const_iterator;
typedef Key KeyType;
- typedef const Key& ReferenceType;
- typedef const Key *PointerType;
+ typedef Value ValueType;
- HashTable() : m_table(0), m_tableSize(0), m_tableSizeMask(0), m_keyCount(0) {}
+ HashTable() : m_table(0), m_tableSize(0), m_tableSizeMask(0), m_keyCount(0), m_deletedCount(0) {}
~HashTable() { main_thread_free(m_table); }
HashTable(const HashTable& other);
@@ -200,205 +193,258 @@
int size() const { return m_keyCount; }
int capacity() const { return m_tableSize; }
- iterator insert(const KeyType& key) { return insert<KeyType, hash, equal, identityConvert>(key); }
+ std::pair<iterator, bool> insert(const ValueType& value) { return insert<KeyType, ValueType, hash, equal, identityConvert>(extractKey(value), value); }
// a special version of insert() that finds the object by hashing and comparing
// with some other type, to avoid the cost of type conversion if the object is already
// in the table
- template<typename T, unsigned HashT(const T&), bool EqualT(const Key&, const T&), KeyType ConvertT(const T&, unsigned)> iterator insert(const T& key);
+ template<typename T, typename Extra, unsigned HashT(const T&), bool EqualT(const Key&, const T&), ValueType ConvertT(const T&, const Extra &, unsigned)>
+ std::pair<iterator, bool> insert(const T& key, const Extra& extra);
iterator find(const KeyType& key);
+ const_iterator find(const KeyType& key) const;
+ bool contains(const KeyType& key) const;
- const_iterator find(const KeyType& key) const
- {
- return makeConstIterator(const_cast<HashTable *>(this)->find(key).m_position);
- }
-
- bool contains(const KeyType& key) const
- {
- return find(key) != end();
- }
-
- void remove(const KeyType& key)
- {
- remove(find(key));
- }
+ void remove(const KeyType& key);
void remove(iterator it);
void clear();
- bool isEmptyBucket(const KeyType& key) const { return key == 0; }
+ static bool isEmptyBucket(const ValueType& value) { return extractKey(value) == extractKey(Traits::emptyValue()); }
+ static bool isDeletedBucket(const ValueType& value) { return extractKey(value) == extractKey(Traits::deletedValue()); }
+ static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
private:
- static unsigned hash(const KeyType& key) { return Hash(key); }
- static bool equal(const KeyType& a, const KeyType& b) { return Equal(a, b); }
- static KeyType identityConvert(const KeyType& key, unsigned) { return key; }
+ static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
+ static bool equal(const KeyType& a, const KeyType& b) { return HashFunctions::equal(a, b); }
+ // FIXME: assumes key == value; special lookup needs adjusting
+ static ValueType identityConvert(const KeyType& key, const ValueType& value, unsigned) { return value; }
+ static KeyType extractKey(const ValueType& value) { return ExtractKey(value); }
+
+ static ValueType *allocateTable(int size);
- bool shouldExpand() const { return m_keyCount * m_maxLoad >= m_tableSize; }
- void expand() { rehash(m_tableSize == 0 ? m_minTableSize : m_tableSize * 2); }
+ typedef std::pair<ValueType *, bool> LookupType;
+ typedef std::pair<LookupType, unsigned> FullLookupType;
+
+ LookupType lookup(const KeyType& key) { return lookup<KeyType, hash, equal>(key).first; }
+ template<typename T, unsigned HashT(const T&), bool EqualT(const Key&, const T&)>
+ FullLookupType lookup(const T&);
+
+ void remove(ValueType *);
+
+ bool shouldExpand() const { return (m_keyCount + m_deletedCount) * m_maxLoad >= m_tableSize; }
+ bool mustRehashInPlace() const { return m_keyCount * m_minLoad < m_tableSize * 2; }
bool shouldShrink() const { return m_keyCount * m_minLoad < m_tableSize && m_tableSize > m_minTableSize; }
+ void expand();
void shrink() { rehash(m_tableSize / 2); }
+
void rehash(int newTableSize);
- void reinsert(const KeyType& key);
+ void reinsert(const ValueType&);
- void clearBucket(KeyType& key) { key = 0;}
+ static void clearBucket(ValueType& key) { key = Traits::emptyValue();}
+ static void deleteBucket(ValueType& key) { key = Traits::deletedValue();}
+
+ FullLookupType makeLookupResult(ValueType *position, bool found, unsigned hash)
+ {
+ return FullLookupType(LookupType(position, found), hash);
+ }
- iterator makeIterator(KeyType *pos) { return iterator(this, pos, m_table + m_tableSize); }
- const_iterator makeConstIterator(KeyType *pos) const { return const_iterator(this, pos, m_table + m_tableSize); }
+ iterator makeIterator(ValueType *pos) { return iterator(pos, m_table + m_tableSize); }
+ const_iterator makeConstIterator(ValueType *pos) const { return const_iterator(pos, m_table + m_tableSize); }
#if CHECK_HASHTABLE_CONSISTENCY
- void checkConsistency() const;
- void checkConsistencyExceptSize() const;
+ void checkTableConsistency() const;
+ void checkTableConsistencyExceptSize() const;
#endif
static const int m_minTableSize = 64;
static const int m_maxLoad = 2;
static const int m_minLoad = 6;
- KeyType *m_table;
+ ValueType *m_table;
int m_tableSize;
int m_tableSizeMask;
int m_keyCount;
+ int m_deletedCount;
};
-template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
-template<typename T, unsigned HashT(const T&), bool EqualT(const Key&, const T&), Key ConvertT(const T&, unsigned)>
-typename HashTable<Key, Hash, Equal>::iterator HashTable<Key, Hash, Equal>::insert(const T& key)
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+template<typename T, unsigned HashT(const T&), bool EqualT(const Key&, const T&)>
+inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::FullLookupType HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::lookup(const T& key)
{
if (!m_table)
- expand();
-
- checkConsistency();
+ return makeLookupResult(0, false, 0);
unsigned h = HashT(key);
int i = h & m_tableSizeMask;
+ int k = 0;
+
#if DUMP_HASHTABLE_STATS
++HashTableStats::numAccesses;
- int collisionCount = 0;
+ int probeCount = 0;
#endif
- KeyType *entry;
+ ValueType *entry;
+ ValueType *deletedEntry = 0;
while (!isEmptyBucket(*(entry = m_table + i))) {
- if (EqualT(*entry, key)) {
- return makeIterator(entry);
- }
+ if (isDeletedBucket(*entry))
+ deletedEntry = entry;
+ else if (EqualT(extractKey(*entry), key))
+ return makeLookupResult(entry, true, h);
#if DUMP_HASHTABLE_STATS
- ++collisionCount;
- HashTableStats::recordCollisionAtCount(collisionCount);
+ HashTableStats::recordCollisionAtCount(probeCount);
+ ++probeCount;
#endif
- i = (i + 1) & m_tableSizeMask;
+ if (k == 0)
+ k = 1 | (h % m_tableSizeMask);
+ i = (i + k) & m_tableSizeMask;
}
-
- *entry = ConvertT(key, h);
+
+ return makeLookupResult(deletedEntry ? deletedEntry : entry, false, h);
+}
+
+
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+template<typename T, typename Extra, unsigned HashT(const T&), bool EqualT(const Key&, const T&), Value ConvertT(const T&, const Extra &, unsigned)>
+inline std::pair<typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::iterator, bool> HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::insert(const T& key, const Extra &extra)
+{
+ if (!m_table)
+ expand();
+
+ checkTableConsistency();
+
+ FullLookupType lookupResult = lookup<T, HashT, EqualT>(key);
+
+ ValueType *entry = lookupResult.first.first;
+ bool found = lookupResult.first.second;
+ unsigned h = lookupResult.second;
+
+ if (found) {
+ return std::make_pair(makeIterator(entry), false);
+ }
+
+ if (isDeletedBucket(*entry))
+ --m_deletedCount;
+
+ *entry = ConvertT(key, extra, h);
++m_keyCount;
if (shouldExpand()) {
- KeyType enteredKey = *entry;
+ KeyType enteredKey = extractKey(*entry);
expand();
- return find(enteredKey);
+ return std::make_pair(find(enteredKey), true);
}
- checkConsistency();
+ checkTableConsistency();
- return makeIterator(entry);
+ return std::make_pair(makeIterator(entry), true);
}
-template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
-void HashTable<Key, Hash, Equal>::reinsert(const KeyType& key)
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::reinsert(const ValueType& entry)
{
- if (!m_table)
- expand();
-
- unsigned h = hash(key);
- int i = h & m_tableSizeMask;
+ assert(m_table);
+ assert(!lookup(extractKey(entry)).second);
+ assert(!isDeletedBucket(*(lookup(extractKey(entry)).first)));
#if DUMP_HASHTABLE_STATS
- ++HashTableStats::numAccesses;
- int collisionCount = 0;
+ ++HashTableStats::numReinserts;
#endif
-
- KeyType *entry;
- while (!isEmptyBucket(*(entry = m_table + i))) {
-#if DUMP_HASHTABLE_STATS
- ++collisionCount;
- HashTableStats::recordCollisionAtCount(collisionCount);
-#endif
- i = (i + 1) & m_tableSizeMask;
- }
-
- *entry = key;
+
+ *(lookup(extractKey(entry)).first) = entry;
}
-template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
-typename HashTable<Key, Hash, Equal>::iterator HashTable<Key, Hash, Equal>::find(const Key& key)
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::iterator HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::find(const Key& key)
{
- if (!m_table)
+ LookupType result = lookup(key);
+ if (!result.second)
return end();
-
- unsigned h = hash(key);
- int i = h & m_tableSizeMask;
-#if DUMP_HASHTABLE_STATS
- ++HashTableStats::numAccesses;
- int collisionCount = 0;
-#endif
-
- KeyType *entry;
- while (!isEmptyBucket(*(entry = m_table + i))) {
- if (equal(*entry, key))
- return makeIterator(entry);
-#if DUMP_HASHTABLE_STATS
- ++collisionCount;
- HashTableStats::recordCollisionAtCount(collisionCount);
-#endif
- i = (i + 1) & m_tableSizeMask;
- }
+ return makeIterator(result.first);
+}
- return end();
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::const_iterator HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::find(const Key& key) const
+{
+ LookupType result = const_cast<HashTable *>(this)->lookup(key);
+ if (!result.second)
+ return end();
+ return makeConstIterator(result.first);
}
-template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
-void HashTable<Key, Hash, Equal>::remove(iterator it)
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+inline bool HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::contains(const KeyType& key) const
{
- checkConsistency();
+ return lookup(key).second;
+}
- if (it == end())
- return;
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::remove(ValueType *pos)
+{
+ checkTableConsistency();
#if DUMP_HASHTABLE_STATS
++HashTableStats::numRemoves;
#endif
- *it = 0;
+ deleteBucket(*pos);
+ ++m_deletedCount;
--m_keyCount;
-
- if (shouldShrink()) {
+
+ if (shouldShrink())
shrink();
- return;
- }
- int i = it.operator->() - m_table;
-
- // Reinsert all the items to the right in the same cluster.
- while (1) {
- i = (i + 1) & m_tableSizeMask;
- KeyType entry = m_table[i];
- if (isEmptyBucket(entry))
- break;
-#if DUMP_HASHTABLE_STATS
- ++HashTableStats::numReinserts;
-#endif
- clearBucket(m_table[i]);
- reinsert(entry);
+ checkTableConsistency();
+}
+
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::remove(const KeyType& key)
+{
+ remove(lookup(key).first);
+}
+
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::remove(iterator it)
+{
+ remove(it.m_position);
+}
+
+
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+inline Value *HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::allocateTable(int size)
+{
+ // would use a template member function with explicit specializations here, but
+ // gcc doesn't appear to support that
+ if (Traits::emptyValueIsZero)
+ return reinterpret_cast<ValueType *>(main_thread_calloc(size, sizeof(ValueType)));
+ else {
+ ValueType *result = reinterpret_cast<ValueType *>(main_thread_malloc(size * sizeof(ValueType)));
+ for (int i = 0; i < size; i++) {
+ clearBucket(result[i]);
+ }
+ return result;
}
+}
- checkConsistency();
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::expand()
+{
+ int newSize;
+ if (m_tableSize == 0)
+ newSize = m_minTableSize;
+ else if (mustRehashInPlace())
+ newSize = m_tableSize;
+ else
+ newSize = m_tableSize * 2;
+
+ rehash(newSize);
}
-template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
-void HashTable<Key, Hash, Equal>::rehash(int newTableSize)
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::rehash(int newTableSize)
{
- checkConsistencyExceptSize();
+ checkTableConsistencyExceptSize();
int oldTableSize = m_tableSize;
- KeyType *oldTable = m_table;
+ ValueType *oldTable = m_table;
#if DUMP_HASHTABLE_STATS
if (oldTableSize != 0)
@@ -407,21 +453,23 @@
m_tableSize = newTableSize;
m_tableSizeMask = newTableSize - 1;
- m_table = (KeyType *)main_thread_calloc(newTableSize, sizeof(KeyType));
+ m_table = allocateTable(newTableSize);
for (int i = 0; i != oldTableSize; ++i) {
- KeyType key = oldTable[i];
- if (!isEmptyBucket(key))
- reinsert(key);
+ ValueType entry = oldTable[i];
+ if (!isEmptyOrDeletedBucket(entry))
+ reinsert(entry);
}
+
+ m_deletedCount = 0;
main_thread_free(oldTable);
- checkConsistency();
+ checkTableConsistency();
}
-template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
-void HashTable<Key, Hash, Equal>::clear()
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::clear()
{
main_thread_free(m_table);
m_table = 0;
@@ -430,23 +478,24 @@
m_keyCount = 0;
}
-template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
-HashTable<Key, Hash, Equal>::HashTable(const HashTable& other)
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::HashTable(const HashTable& other)
: m_table(0)
, m_tableSize(other.m_tableSize)
, m_tableSizeMask(other.m_tableSizeMask)
, m_keyCount(other.m_keyCount)
+ , m_deletedCount(other.m_deletedCount)
{
if (m_tableSize != 0) {
m_table = main_thread_malloc(m_tableSize);
- memcpy(other.m_table, m_table, m_tableSize * sizeof(KeyType));
+ memcpy(other.m_table, m_table, m_tableSize * sizeof(ValueType));
}
}
-template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
-void HashTable<Key, Hash, Equal>::swap(const HashTable& other)
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::swap(const HashTable& other)
{
- KeyType *tmp_table = m_table;
+ ValueType *tmp_table = m_table;
m_table = other.m_table;
other.m_table = tmp_table;
@@ -461,10 +510,14 @@
int tmp_keyCount = m_keyCount;
m_keyCount = other.m_keyCount;
other.m_keyCount = tmp_keyCount;
+
+ int tmp_deletedCount = m_deletedCount;
+ m_deletedCount = other.m_deletedCount;
+ other.m_deletedCount = tmp_deletedCount;
}
-template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
-HashTable<Key, Hash, Equal>& HashTable<Key, Hash, Equal>::operator=(const HashTable& other)
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+HashTable<Key, Value, ExtractKey, HashFunctions, Traits>& HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::operator=(const HashTable& other)
{
HashTable tmp(other);
swap(tmp);
@@ -473,32 +526,39 @@
#if CHECK_HASHTABLE_CONSISTENCY
-template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
-void HashTable<Key, Hash, Equal>::checkConsistency() const
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::checkTableConsistency() const
{
- checkConsistencyExceptSize();
+ checkTableConsistencyExceptSize();
assert(!shouldExpand());
assert(!shouldShrink());
}
-template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
-void HashTable<Key, Hash, Equal>::checkConsistencyExceptSize() const
+template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::checkTableConsistencyExceptSize() const
{
if (!m_table)
return;
int count = 0;
+ int deletedCount = 0;
for (int j = 0; j < m_tableSize; ++j) {
- KeyType *entry = m_table + j;
+ ValueType *entry = m_table + j;
if (isEmptyBucket(*entry))
continue;
+
+ if (isDeletedBucket(*entry)) {
+ ++deletedCount;
+ continue;
+ }
- const_iterator it = find(*entry);
+ const_iterator it = find(extractKey(*entry));
assert(entry == it.m_position);
++count;
}
assert(count == m_keyCount);
+ assert(deletedCount == m_deletedCount);
assert(m_tableSize >= m_minTableSize);
assert(m_tableSizeMask);
assert(m_tableSize == m_tableSizeMask + 1);
1.1 WebCore/khtml/misc/hashfunctions.h
Index: hashfunctions.h
===================================================================
/*
* This file is part of the KDE libraries
*
* Copyright (C) 2005 Apple Computer, Inc.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public License
* along with this library; see the file COPYING.LIB. If not, write to
* the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*
*/
#ifndef HASHFUNCTIONS_H
#define HASHFUNCTIONS_H
#include "xml/dom_stringimpl.h"
namespace khtml {
template<typename T> class DefaultHash;
template<int size> unsigned pointerHash(void *pointer);
// Thomas Wang's 32 bit mix
// http://www.cris.com/~Ttwang/tech/inthash.htm
template<> inline unsigned pointerHash<4>(void *pointer)
{
uint32_t key = reinterpret_cast<uint32_t>(pointer);
key += ~(key << 15);
key ^= (key >> 10);
key += (key << 3);
key ^= (key >> 6);
key += ~(key << 11);
key ^= (key >> 16);
return key;
}
// Thomas Wang's 64 bit mix
// http://www.cris.com/~Ttwang/tech/inthash.htm
template<> inline unsigned pointerHash<8>(void *pointer)
{
uint64_t key = reinterpret_cast<uint64_t>(pointer);
key += ~(key << 32);
key ^= (key >> 22);
key += ~(key << 13);
key ^= (key >> 8);
key += (key << 3);
key ^= (key >> 15);
key += ~(key << 27);
key ^= (key >> 31);
return key;
}
template<> struct DefaultHash<void *> {
static unsigned hash(void *key) { return pointerHash<sizeof(void *)>(key); }
static bool equal(void *a, void *b) { return a == b; }
};
// pointer identity hash - default for void *, must be requested explicitly for other
// pointer types; also should work for integer types
template<typename T> struct PointerHash {
static unsigned hash(T key) { return pointerHash<sizeof(void *)>((void *)key); }
static bool equal(T a, T b) { return a == b; }
};
template<> struct DefaultHash<DOM::DOMStringImpl *> {
static unsigned hash(const DOM::DOMStringImpl *key) { return key->hash(); }
static bool equal(const DOM::DOMStringImpl *a, const DOM::DOMStringImpl *b)
{
if (a == b) return true;
if (!a || !b) return false;
uint length = a->l;
if (length != b->l)
return false;
const QChar *as = a->s;
const QChar *bs = b->s;
for (uint i = 0; i != length; ++i)
if (as[i] != bs[i])
return false;
return true;
}
};
class CaseInsensitiveHash {
private:
// Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
static const unsigned PHI = 0x9e3779b9U;
public:
// Paul Hsieh's SuperFastHash
// http://www.azillionmonkeys.com/qed/hash.html
static unsigned hash(const DOM::DOMStringImpl *str)
{
unsigned l = str->l;
QChar *s = str->s;
uint32_t hash = PHI;
uint32_t tmp;
int rem = l & 1;
l >>= 1;
// Main loop
for (; l > 0; l--) {
hash += s[0].lower().unicode();
tmp = (s[1].lower().unicode() << 11) ^ hash;
hash = (hash << 16) ^ tmp;
s += 2;
hash += hash >> 11;
}
// Handle end case
if (rem) {
hash += s[0].lower().unicode();
hash ^= hash << 11;
hash += hash >> 17;
}
// Force "avalanching" of final 127 bits
hash ^= hash << 3;
hash += hash >> 5;
hash ^= hash << 2;
hash += hash >> 15;
hash ^= hash << 10;
// this avoids ever returning a hash code of 0, since that is used to
// signal "hash not computed yet", using a value that is likely to be
// effectively the same as 0 when the low bits are masked
if (hash == 0)
hash = 0x80000000;
return hash;
}
static bool equal(const DOM::DOMStringImpl *a, const DOM::DOMStringImpl *b)
{
if (a == b) return true;
if (!a || !b) return false;
uint length = a->l;
if (length != b->l)
return false;
const QChar *as = a->s;
const QChar *bs = b->s;
for (uint i = 0; i != length; ++i)
if (as[i].lower() != bs[i].lower())
return false;
return true;
}
};
} // namespace khtml
#endif // HASHFUNCTIONS_H
1.1 WebCore/khtml/misc/hashmap.h
Index: hashmap.h
===================================================================
/*
* This file is part of the KDE libraries
*
* Copyright (C) 2005 Apple Computer, Inc.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public License
* along with this library; see the file COPYING.LIB. If not, write to
* the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*
*/
#ifndef HASHMAP_H
#define HASHMAP_H
#include "hashtable.h"
#include "hashtraits.h"
#include "hashfunctions.h"
namespace khtml {
template<typename PairType>
inline typename PairType::first_type extractFirst(const PairType& value)
{
return value.first;
}
template<typename Key, typename Mapped, typename HashFunctions = DefaultHash<Key>, typename KeyTraits = HashTraits<Key>, typename MappedTraits = HashTraits<Mapped> >
class HashMap {
public:
typedef Key KeyType;
typedef Mapped MappedType;
typedef std::pair<Key, Mapped> ValueType;
typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits;
private:
typedef HashTable<KeyType, ValueType, extractFirst<ValueType>, HashFunctions, ValueTraits> ImplType;
public:
typedef typename ImplType::iterator iterator;
typedef typename ImplType::const_iterator const_iterator;
HashMap() {}
int size() const;
int capacity() const;
bool isEmpty() const;
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
iterator find(const KeyType& key);
const_iterator find(const KeyType& key) const;
bool contains(const KeyType& key) const;
MappedType get(const KeyType &key) const;
std::pair<iterator, bool> insert(const KeyType &key, const MappedType &mapped);
void remove(const KeyType& key);
void remove(iterator it);
void clear();
private:
ImplType m_impl;
};
template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
int HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::size() const
{
return m_impl.count();
}
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>
bool HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::isEmpty() const
{
return size() == 0;
}
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>::begin()
{
return m_impl.begin();
}
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>::end()
{
return m_impl.end();
}
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>::begin() const
{
return m_impl.begin();
}
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>::end() const
{
return m_impl.end();
}
template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::find(const KeyType& key)
{
return m_impl.find(key);
}
template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::const_iterator HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::find(const KeyType& key) const
{
return m_impl.find(key);
}
template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
bool HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::contains(const KeyType& key) const
{
return m_impl.contains(key);
}
template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
std::pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::insert(const KeyType &key, const MappedType &mapped)
{
pair<iterator, bool> result = m_impl.insert(ValueType(key, mapped));
iterator it = result.first;
// insert won't change anything if the key is already there
if (!result.second)
it->second = mapped;
return result;
}
template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
Mapped HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::get(const KeyType &key) const
{
const_iterator it = find(key);
if (it == end())
return MappedTraits::emptyValue();
return it->second;
}
template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
void HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::remove(const KeyType& key)
{
m_impl.remove(key);
}
template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
void HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::remove(iterator it)
{
m_impl.remove(it);
}
template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
void HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::clear()
{
m_impl.clear();
}
template<typename T>
void deleteAllValues(T& collection)
{
for (typename T::iterator it = collection.begin(); it != collection.end(); ++it) {
delete it->second;
}
}
} // namespace khtml
#endif /* HASHMAP_H */
1.1 WebCore/khtml/misc/hashtraits.h
Index: hashtraits.h
===================================================================
/*
* This file is part of the KDE libraries
*
* Copyright (C) 2005 Apple Computer, Inc.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public License
* along with this library; see the file COPYING.LIB. If not, write to
* the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*
*/
#ifndef HASHTRAITS_H
#define HASHTRAITS_H
#include <utility>
#include <bits/cpp_type_traits.h>
namespace khtml {
using std::pair;
template <typename T>
struct HashTraits {
typedef T traitType;
static const bool emptyValueIsZero = std::__is_integer<T>::_M_type;
static traitType emptyValue() {
return traitType();
}
};
// may not be appropriate for all uses since it would disallow 0 and -1 as keys
struct HashTraits<int> {
typedef int traitType;
static const bool emptyValueIsZero = true;
static traitType emptyValue() {
return 0;
}
static traitType deletedValue() {
return -1;
}
};
template <typename P>
struct HashTraits<P *> {
typedef P *traitType;
static const bool emptyValueIsZero = true;
static traitType emptyValue() {
return reinterpret_cast<P *>(0);
}
static traitType deletedValue() {
return reinterpret_cast<P *>(-1);
}
};
template <typename FirstTraits, typename SecondTraits>
struct PairHashTraits {
private:
typedef typename FirstTraits::traitType FirstType;
typedef typename SecondTraits::traitType SecondType;
public:
typedef pair<FirstType, SecondType> traitType;
static const bool emptyValueIsZero = FirstTraits::emptyValueIsZero && SecondTraits::emptyValueIsZero;
static traitType emptyValue() {
return traitType(FirstTraits::emptyValue(), SecondTraits::emptyValue());
}
static traitType deletedValue() {
return traitType(FirstTraits::deletedValue(), SecondTraits::emptyValue());
}
};
template <typename First, typename Second>
struct HashTraits<pair<First, Second> > : public PairHashTraits<HashTraits<First>, HashTraits<Second> > {
};
} // namespace khtml
#endif // HASHTRAITS_H
1.1 WebCore/khtml/misc/pointerhash.h
Index: pointerhash.h
===================================================================
/*
* This file is part of the KDE libraries
*
* Copyright (C) 2005 Apple Computer, Inc.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public License
* along with this library; see the file COPYING.LIB. If not, write to
* the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*
*/
#ifndef PTRHASHMAP_H
#define PTRHASHMAP_H
#include "hashmap.h"
// 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 khtml {
template<typename P, typename Mapped>
class PointerHashIteratorAdapter {
private:
typedef HashMap<P *, Mapped, PointerHash<P *>, HashTraits<P *>, HashTraits<Mapped> > MapType;
typedef typename MapType::ValueType ValueType;
typedef typename MapType::ImplValueType ImplValueType;
typedef typename HashMap<P *, Mapped, PointerHash<P *>, HashTraits<P *>, HashTraits<Mapped> >::ImplIterator ImplIterator;
typedef PointerHashIteratorAdapter<P, Mapped> iterator;
typedef ValueType& ReferenceType;
typedef ValueType *PointerType;
friend class HashMap<P *, Mapped, PointerHash<P *>, HashTraits<P *>, HashTraits<Mapped> >;
public:
PointerHashIteratorAdapter() {}
PointerHashIteratorAdapter(const ImplIterator &impl) : m_impl(impl) {}
// default copy, assignment and destructor are ok
ReferenceType operator*() const { return *reinterpret_cast<PointerType>(m_impl.operator->()); }
PointerType operator->() const { return &(operator*()); }
iterator& operator++()
{
++m_impl;
return *this;
}
// postfix ++ intentionally omitted
// Comparison.
bool operator==(const iterator& other) const
{
return m_impl == other.m_impl;
}
bool operator!=(const iterator& other) const
{
return m_impl != other.m_impl;
}
private:
ImplIterator m_impl;
};
template<typename P, typename Mapped>
class PointerHashConstIteratorAdapter {
private:
typedef HashMap<P *, Mapped, PointerHash<P *>, HashTraits<P *>, HashTraits<Mapped> > MapType;
typedef typename MapType::ValueType ValueType;
typedef typename MapType::ImplValueType ImplValueType;
typedef typename MapType::ImplIterator ImplIterator;
typedef typename MapType::ImplConstIterator ImplConstIterator;
typedef PointerHashIteratorAdapter<P, Mapped> iterator;
typedef PointerHashConstIteratorAdapter<P, Mapped> const_iterator;
typedef const ValueType& ReferenceType;
typedef const ValueType *PointerType;
friend class HashMap<P *, Mapped, PointerHash<P *>, HashTraits<P *>, HashTraits<Mapped> >;
public:
PointerHashConstIteratorAdapter() {}
PointerHashConstIteratorAdapter(const ImplConstIterator &impl) : m_impl(impl) {}
PointerHashConstIteratorAdapter(const iterator &other) : m_impl(other.m_impl) { }
// default copy, assignment and destructor are ok
ReferenceType operator*() const { return *reinterpret_cast<PointerType>(m_position); }
PointerType operator->() const { return &(operator*()); }
iterator& operator++()
{
++m_impl;
return *this;
}
// postfix ++ intentionally omitted
// Comparison.
bool operator==(const iterator& other) const
{
return m_impl == other.m_impl;
}
bool operator!=(const iterator& other) const
{
return m_impl != other.m_impl;
}
private:
ImplConstIterator m_impl;
};
template<typename P, typename Mapped>
class HashMap<P *, Mapped, PointerHash<P *>, HashTraits<P *>, HashTraits<Mapped> > {
public:
typedef P *KeyType;
typedef Mapped MappedType;
typedef std::pair<KeyType, Mapped> ValueType;
private:
// important not to use pointerHash/pointerEqual here or instantiation would recurse
typedef HashMap<void *, MappedType, DefaultHash<void *>, HashTraits<void *>, HashTraits<Mapped> > ImplType;
public:
typedef typename ImplType::ValueType ImplValueType;
typedef typename ImplType::iterator ImplIterator;
typedef typename ImplType::const_iterator ImplConstIterator;
typedef PointerHashIteratorAdapter<P, Mapped> iterator;
typedef PointerHashConstIteratorAdapter<P, Mapped> const_iterator;
HashMap() {}
int size() const { return m_impl.size(); }
int capacity() const { return m_impl.capacity(); }
bool isEmpty() const { return m_impl.isEmpty(); }
iterator begin() { return m_impl.begin(); }
iterator end() { return m_impl.end(); }
const_iterator begin() const { return m_impl.begin(); }
const_iterator end() const { return m_impl.end(); }
iterator find(const KeyType& key) { return m_impl.find(key); }
const_iterator find(const KeyType& key) const { return m_impl.find(key); }
bool contains(const KeyType& key) const { return m_impl.contains(key); }
MappedType get(const KeyType &key) const { return m_impl.get(key); }
std::pair<iterator, bool> insert(const KeyType &key, const MappedType &mapped)
{ return m_impl.insert(key, mapped); }
void remove(const KeyType& key) { m_impl.remove(key); }
void remove(iterator it) { m_impl.remove(it.m_impl); }
void clear() { m_impl.clear(); }
private:
ImplType m_impl;
};
template<typename P, typename Q>
class HashMap<P *, Q *, PointerHash<P *>, HashTraits<P *>, HashTraits<Q *> > {
private:
// important not to use pointerHash/pointerEqual here or instantiation would recurse
typedef HashMap<void *, void *, DefaultHash<void *>, HashTraits<void *>, HashTraits<void *> > ImplMapType;
public:
typedef P *KeyType;
typedef Q *MappedType;
typedef std::pair<KeyType, MappedType> ValueType;
typedef typename std::pair<void *, void *> ImplValueType;
typedef HashTableIterator<void *, ImplValueType, extractFirst<ImplValueType>, DefaultHash<void *>, PairHashTraits<HashTraits<void *>, HashTraits<void *> > > ImplIterator;
typedef HashTableConstIterator<void *, ImplValueType, extractFirst<ImplValueType>, DefaultHash<void *>, PairHashTraits<HashTraits<void *>, HashTraits<void *> > > ImplConstIterator;
typedef PointerHashIteratorAdapter<P, Q *> iterator;
typedef PointerHashConstIteratorAdapter<P, Q *> const_iterator;
HashMap() {}
int size() const { return m_impl.size(); }
int capacity() const { return m_impl.capacity(); }
bool isEmpty() const { return m_impl.isEmpty(); }
iterator begin() { return m_impl.begin(); }
iterator end() { return m_impl.end(); }
const_iterator begin() const { return m_impl.begin(); }
const_iterator end() const { return m_impl.end(); }
iterator find(const KeyType& key) { return m_impl.find(key); }
const_iterator find(const KeyType& key) const { return m_impl.find(key); }
bool contains(const KeyType& key) const { return m_impl.contains(key); }
MappedType get(const KeyType &key) const { return (MappedType)m_impl.get(key); }
std::pair<iterator, bool> insert(const KeyType &key, const MappedType &mapped)
{ return m_impl.insert(key, mapped); }
void remove(const KeyType& key) { m_impl.remove(key); }
void remove(iterator it) { m_impl.remove(it.m_impl); }
void clear() { m_impl.clear(); }
private:
ImplMapType m_impl;
};
} // namespace khtml
#endif // PTRHASHMAP_H
1.8 +5 -25 WebCore/khtml/xml/dom_atomicstring.cpp
Index: dom_atomicstring.cpp
===================================================================
RCS file: /cvs/root/WebCore/khtml/xml/dom_atomicstring.cpp,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -r1.7 -r1.8
--- dom_atomicstring.cpp 29 Jun 2005 21:04:32 -0000 1.7
+++ dom_atomicstring.cpp 6 Jul 2005 01:28:44 -0000 1.8
@@ -36,33 +36,13 @@
#include "dom_atomicstring.h"
#include "xml/dom_stringimpl.h"
-#include "hashset.h"
+#include "misc/hashset.h"
using khtml::HashSet;
namespace DOM {
-inline unsigned hash(DOMStringImpl* const& s)
-{
- return s->hash();
-}
-
-bool equal(DOMStringImpl* const& r, DOMStringImpl* const& b)
-{
- if (r == b) return true;
- if (!r || !b) return false;
- uint length = r->l;
- if (length != b->l)
- return false;
- const QChar *d = r->s;
- const QChar *s = b->s;
- for (uint i = 0; i != length; ++i)
- if (d[i] != s[i])
- return false;
- return true;
-}
-
-static HashSet<DOMStringImpl *, hash, equal> stringTable;
+static HashSet<DOMStringImpl *> stringTable;
inline unsigned hash(const char* const& c)
{
@@ -104,7 +84,7 @@
if (length == 0)
return DOMStringImpl::empty();
- return *stringTable.insert<const char *, hash, DOM::equal, convert>(c);
+ return *stringTable.insert<const char *, hash, DOM::equal, convert>(c).first;
}
@@ -150,7 +130,7 @@
return DOMStringImpl::empty();
QCharBuffer buf = {s, length};
- return *stringTable.insert<QCharBuffer, hash, DOM::equal, convert>(buf);
+ return *stringTable.insert<QCharBuffer, hash, DOM::equal, convert>(buf).first;
}
DOMStringImpl *AtomicString::add(DOMStringImpl *r)
@@ -161,7 +141,7 @@
if (r->l == 0)
return DOMStringImpl::empty();
- DOMStringImpl *result = *stringTable.insert(r);
+ DOMStringImpl *result = *stringTable.insert(r).first;
if (result == r)
r->_inTable = true;
return result;
More information about the webkit-changes
mailing list