[webkit-changes] cvs commit: JavaScriptCore/kxmlcore
HashFunctions.h HashMap.h HashMapPtrSpec.h HashSet.h
HashTable.h HashTraits.h RefPtr.h
Maciej
mjs at opensource.apple.com
Thu Dec 22 17:52:45 PST 2005
mjs 05/12/22 17:52:44
Modified: . ChangeLog
khtml/xml dom_atomicstring.cpp dom_qname.cpp
. ChangeLog
kjs array_object.cpp identifier.cpp
kxmlcore HashFunctions.h HashMap.h HashMapPtrSpec.h
HashSet.h HashTable.h HashTraits.h RefPtr.h
Log:
JavaScriptCore:
Reviewed by Darin.
- Make HashMap/HashSet support non-POD types
http://bugzilla.opendarwin.org/show_bug.cgi?id=5332
The changes for support are relatively simple, but I also made extensive changes to
avoid copying, so that there isn't refcount thrash when you put RefPtrs into a HashMap.
* kxmlcore/HashTable.h:
(KXMLCore::swap): specialize swap for pairs, to swap elements individually,
so that excess copies can be avoided.
(KXMLCore::Mover::move): Template function to either copy or swap, used
when transferring elements from old table to new.
(KXMLCore::IdentityHashTranslator::hash): The old "converting lookup" templates
that took two or three function parameters now take a class parameter, this is
the class used to do a normal lookup.
(KXMLCore::IdentityHashTranslator::equal): Ditto.
(KXMLCore::IdentityHashTranslator::translate): Ditto. Translate now takes a reference
to write into instead of returning a value to avoid redundant copies.
(KXMLCore::HashTable::~HashTable): Use deallocateTable instead of freeing directly.
(KXMLCore::HashTable::insert): Based on HashTranslator now instead of separate
functions. Added a FIXME about a remaining rare excess copy.
(KXMLCore::HashTable::isEmptyBucket): Use KeyTraits directly instead of unwrapping
the key from Traits, to avoid creating and destroying pair, which copies.
(KXMLCore::HashTable::isDeletedBucket): ditto
(KXMLCore::HashTable::lookup): Use HashTranslator now instead of separate functions.
(KXMLCore::HashTable::initializeBucket): Renamed from emptyBucket. Use placement new to
work right for non-POD types.
(KXMLCore::HashTable::deleteBucket): Use assignDeleted to avoid excess copies.
(KXMLCore::HashTable::reinsert): use Mover template to copy or swap as appropriate
(KXMLCore::HashTable::allocateTable): Initialize every bucket if calloc won't do.
(KXMLCore::HashTable::deallocateTable): Destruct every bucket if needed.
(KXMLCore::HashTable::rehash): Avoid copy before reinserting, so that swap can do its magic.
(KXMLCore::HashTable::clear): use deallocateTable instead of freeing directly.
(KXMLCore::HashTable::HashTable): be more dumb when copying to ensure that non-POD types
work right
* kxmlcore/HashFunctions.h:
(KXMLCore::PointerHash): Specialize PointerHash for RefPtr
* kxmlcore/HashMap.h:
(KXMLCore::extractFirst): Return a reference not a full object to avoid
copies.
(KXMLCore::HashMapTranslator::hash): Use a special translator for insertion
to defer making the pair as long as possible, thus avoiding needless copies.
(KXMLCore::HashMapTranslator::equal): ditto
(KXMLCore::HashMapTranslator::translate): ditto
(KXMLCore::::inlineAdd): Shared by set and add to insert using HashMapTranslator
(KXMLCore::::set): Use inlineAdd
(KXMLCore::::add): Use inlineAdd
* kxmlcore/HashMapPtrSpec.h:
(KXMLCore::): Pass KeyTraits along
* kxmlcore/HashSet.h:
(KXMLCore::identityExtract): Return a reference not a full object to avoid copies.
(KXMLCore::HashSetTranslatorAdapter::hash): Redo adapter stuff to work with
the new HashTranslator approach.
(KXMLCore::HashSetTranslatorAdapter::equal): ditto
(KXMLCore::HashSetTranslatorAdapter::translate): ditto
(KXMLCore::::insert): ditto
* kxmlcore/HashTraits.h:
(KXMLCore::GenericHashTraits): This is intended be used as a base class for
customized traits: sensible defaults.
(KXMLCore::): Use it a bunch
(KXMLCore::assignDeleted): template function to allow pairs to be assigned the
deleted value w/o excess copies.
(KXMLCore::PairHashTraits::emptyValue): Updated
(KXMLCore::PairHashTraits::deletedValue): Updated
(KXMLCore::PairHashTraits::assignDeletedValue): part of assignDeleted hack
(KXMLCore::DeletedValueAssigner::assignDeletedValue): Use template magic
to either use use deletedValue or assignDeletedValue for the cases where we care.
* kxmlcore/RefPtr.h:
(KXMLCore::RefPtr::swap): Added swap method.
(KXMLCore::swap): Added swap free function.
* kjs/identifier.cpp:
(KJS::CStringTranslator::hash): Use new HashTranslator class approach to
alternate type based insertion.
(KJS::CStringTranslator::equal): ditto
(KJS::CStringTranslator::translate): ditto
(KJS::Identifier::add): ditto
(KJS::UCharBufferTranslator::hash): ditto
(KJS::UCharBufferTranslator::equal): ditto
(KJS::UCharBufferTranslator::translate): ditto
- irrelevant change:
* kjs/array_object.cpp:
(ArrayProtoFunc::callAsFunction): Removed a stray space.
WebCore:
Reviewed by Darin.
- update for new HashTranslator stuff
* khtml/xml/dom_atomicstring.cpp:
(DOM::CStringTranslator::hash):
(DOM::CStringTranslator::equal):
(DOM::CStringTranslator::translate):
(DOM::AtomicString::equal):
(DOM::AtomicString::add):
(DOM::QCharBufferTranslator::hash):
(DOM::QCharBufferTranslator::equal):
(DOM::QCharBufferTranslator::translate):
* khtml/xml/dom_qname.cpp:
(DOM::QNameComponentsTranslator::hash):
(DOM::QNameComponentsTranslator::equal):
(DOM::QNameComponentsTranslator::translate):
(DOM::QualifiedName::QualifiedName):
Revision Changes Path
1.30 +21 -0 WebCore/ChangeLog
Index: ChangeLog
===================================================================
RCS file: /cvs/root/WebCore/ChangeLog,v
retrieving revision 1.29
retrieving revision 1.30
diff -u -r1.29 -r1.30
--- ChangeLog 23 Dec 2005 01:13:49 -0000 1.29
+++ ChangeLog 23 Dec 2005 01:52:39 -0000 1.30
@@ -1,3 +1,24 @@
+2005-12-21 Maciej Stachowiak <mjs at apple.com>
+
+ Reviewed by Darin.
+
+ - update for new HashTranslator stuff
+
+ * khtml/xml/dom_atomicstring.cpp:
+ (DOM::CStringTranslator::hash):
+ (DOM::CStringTranslator::equal):
+ (DOM::CStringTranslator::translate):
+ (DOM::AtomicString::equal):
+ (DOM::AtomicString::add):
+ (DOM::QCharBufferTranslator::hash):
+ (DOM::QCharBufferTranslator::equal):
+ (DOM::QCharBufferTranslator::translate):
+ * khtml/xml/dom_qname.cpp:
+ (DOM::QNameComponentsTranslator::hash):
+ (DOM::QNameComponentsTranslator::equal):
+ (DOM::QNameComponentsTranslator::translate):
+ (DOM::QualifiedName::QualifiedName):
+
2005-12-22 Adele Peterson <adele at apple.com>
Reviewed by Darin.
1.15 +61 -56 WebCore/khtml/xml/dom_atomicstring.cpp
Index: dom_atomicstring.cpp
===================================================================
RCS file: /cvs/root/WebCore/khtml/xml/dom_atomicstring.cpp,v
retrieving revision 1.14
retrieving revision 1.15
diff -u -r1.14 -r1.15
--- dom_atomicstring.cpp 3 Oct 2005 21:12:51 -0000 1.14
+++ dom_atomicstring.cpp 23 Dec 2005 01:52:40 -0000 1.15
@@ -37,20 +37,32 @@
static HashSet<DOMStringImpl *> stringTable;
-inline unsigned hash(const char* const& c)
+struct CStringTranslator
{
- return DOMStringImpl::computeHash(c);
-}
+ static unsigned hash(const char* c)
+ {
+ return DOMStringImpl::computeHash(c);
+ }
-inline bool equal(DOMStringImpl* const& r, const char* const& s)
-{
- int length = r->l;
- const QChar *d = r->s;
- for (int i = 0; i != length; ++i)
- if (d[i] != s[i])
- return false;
- return s[length] == 0;
-}
+ static bool equal(DOMStringImpl *r, const char *s)
+ {
+ int length = r->l;
+ const QChar *d = r->s;
+ for (int i = 0; i != length; ++i)
+ if (d[i] != s[i])
+ return false;
+ return s[length] == 0;
+ }
+
+ static void translate(DOMStringImpl *& location, const char* const& c, unsigned hash)
+ {
+ DOMStringImpl *r = new DOMStringImpl(c);
+ r->_hash = hash;
+ r->_inTable = true;
+
+ location = r;
+ }
+};
bool AtomicString::equal(const AtomicString &a, const char *b)
{
@@ -59,16 +71,7 @@
return true;
if ((!impl || !impl->s) || !b)
return false;
- return DOM::equal(impl, b);
-}
-
-inline DOMStringImpl *convert(const char* const& c, unsigned hash)
-{
- DOMStringImpl *r = new DOMStringImpl(c);
- r->_hash = hash;
- r->_inTable = true;
-
- return r;
+ return CStringTranslator::equal(impl, b);
}
DOMStringImpl *AtomicString::add(const char *c)
@@ -79,51 +82,53 @@
if (length == 0)
return DOMStringImpl::empty();
- return *stringTable.insert<const char *, hash, DOM::equal, convert>(c).first;
+ return *stringTable.insert<const char *, CStringTranslator>(c).first;
}
-
struct QCharBuffer {
const QChar *s;
uint length;
};
-inline unsigned hash(const QCharBuffer& buf)
+struct QCharBufferTranslator
{
- return DOMStringImpl::computeHash(buf.s, buf.length);
-}
-
-inline bool equal(DOMStringImpl* const& str, const QCharBuffer &buf)
-{
- uint strLength = str->l;
- uint bufLength = buf.length;
- if (strLength != bufLength)
- return false;
+ static unsigned hash(const QCharBuffer& buf)
+ {
+ return DOMStringImpl::computeHash(buf.s, buf.length);
+ }
- const uint32_t *strChars = reinterpret_cast<const uint32_t *>(str->s);
- const uint32_t *bufChars = reinterpret_cast<const uint32_t *>(buf.s);
-
- uint halfLength = strLength >> 1;
- for (uint i = 0; i != halfLength; ++i) {
- if (*strChars++ != *bufChars++)
+ static bool equal(DOMStringImpl* const& str, const QCharBuffer &buf)
+ {
+ uint strLength = str->l;
+ uint bufLength = buf.length;
+ if (strLength != bufLength)
return false;
+
+ const uint32_t *strChars = reinterpret_cast<const uint32_t *>(str->s);
+ const uint32_t *bufChars = reinterpret_cast<const uint32_t *>(buf.s);
+
+ uint halfLength = strLength >> 1;
+ for (uint i = 0; i != halfLength; ++i) {
+ if (*strChars++ != *bufChars++)
+ return false;
+ }
+
+ if (strLength & 1 &&
+ *reinterpret_cast<const uint16_t *>(strChars) != *reinterpret_cast<const uint16_t *>(bufChars))
+ return false;
+
+ return true;
}
- if (strLength & 1 &&
- *reinterpret_cast<const uint16_t *>(strChars) != *reinterpret_cast<const uint16_t *>(bufChars))
- return false;
-
- return true;
-}
-
-inline DOMStringImpl *convert(const QCharBuffer& buf, unsigned hash)
-{
- DOMStringImpl *r = new DOMStringImpl(buf.s, buf.length);
- r->_hash = hash;
- r->_inTable = true;
-
- return r;
-}
+ static void translate(DOMStringImpl*& location, const QCharBuffer& buf, unsigned hash)
+ {
+ DOMStringImpl *r = new DOMStringImpl(buf.s, buf.length);
+ r->_hash = hash;
+ r->_inTable = true;
+
+ location = r;
+ }
+};
DOMStringImpl *AtomicString::add(const QChar *s, int length)
{
@@ -134,7 +139,7 @@
return DOMStringImpl::empty();
QCharBuffer buf = {s, length};
- return *stringTable.insert<QCharBuffer, hash, DOM::equal, convert>(buf).first;
+ return *stringTable.insert<QCharBuffer, QCharBufferTranslator>(buf).first;
}
DOMStringImpl *AtomicString::add(DOMStringImpl *r)
1.8 +19 -13 WebCore/khtml/xml/dom_qname.cpp
Index: dom_qname.cpp
===================================================================
RCS file: /cvs/root/WebCore/khtml/xml/dom_qname.cpp,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -r1.7 -r1.8
--- dom_qname.cpp 3 Oct 2005 21:12:53 -0000 1.7
+++ dom_qname.cpp 23 Dec 2005 01:52:40 -0000 1.8
@@ -92,18 +92,24 @@
static QNameSet *gNameCache;
-inline bool equalComponents(QualifiedName::QualifiedNameImpl* const& name, const QualifiedNameComponents &components)
-{
- return components.m_localName == name->m_localName.impl() &&
- components.m_namespace == name->m_namespace.impl() &&
- components.m_prefix == name->m_prefix.impl();
-}
-
-inline QualifiedName::QualifiedNameImpl *convertComponents(const QualifiedNameComponents& components, unsigned hash)
-{
- return new QualifiedName::QualifiedNameImpl(components.m_prefix, components.m_localName, components.m_namespace);
-}
-
+struct QNameComponentsTranslator {
+ static unsigned hash(const QualifiedNameComponents& components)
+ {
+ return hashComponents(components);
+ }
+
+ static bool equal(QualifiedName::QualifiedNameImpl *name, const QualifiedNameComponents& components)
+ {
+ return components.m_localName == name->m_localName.impl() &&
+ components.m_namespace == name->m_namespace.impl() &&
+ components.m_prefix == name->m_prefix.impl();
+ }
+
+ static void translate(QualifiedName::QualifiedNameImpl*& location, const QualifiedNameComponents& components, unsigned hash)
+ {
+ location = new QualifiedName::QualifiedNameImpl(components.m_prefix, components.m_localName, components.m_namespace);
+ }
+};
QualifiedName::QualifiedName(const AtomicString& p, const AtomicString& l, const AtomicString& n)
: m_impl(0)
@@ -111,7 +117,7 @@
if (!gNameCache)
gNameCache = new QNameSet;
QualifiedNameComponents components = { p.impl(), l.impl(), n.impl() };
- m_impl = *gNameCache->insert<QualifiedNameComponents, hashComponents, equalComponents, convertComponents>(components).first;
+ m_impl = *gNameCache->insert<QualifiedNameComponents, QNameComponentsTranslator>(components).first;
ref();
}
1.923 +88 -0 JavaScriptCore/ChangeLog
Index: ChangeLog
===================================================================
RCS file: /cvs/root/JavaScriptCore/ChangeLog,v
retrieving revision 1.922
retrieving revision 1.923
diff -u -r1.922 -r1.923
--- ChangeLog 22 Dec 2005 21:08:59 -0000 1.922
+++ ChangeLog 23 Dec 2005 01:52:40 -0000 1.923
@@ -1,3 +1,91 @@
+2005-12-21 Maciej Stachowiak <mjs at apple.com>
+
+ Reviewed by Darin.
+
+ - Make HashMap/HashSet support non-POD types
+ http://bugzilla.opendarwin.org/show_bug.cgi?id=5332
+
+ The changes for support are relatively simple, but I also made extensive changes to
+ avoid copying, so that there isn't refcount thrash when you put RefPtrs into a HashMap.
+
+ * kxmlcore/HashTable.h:
+ (KXMLCore::swap): specialize swap for pairs, to swap elements individually,
+ so that excess copies can be avoided.
+ (KXMLCore::Mover::move): Template function to either copy or swap, used
+ when transferring elements from old table to new.
+ (KXMLCore::IdentityHashTranslator::hash): The old "converting lookup" templates
+ that took two or three function parameters now take a class parameter, this is
+ the class used to do a normal lookup.
+ (KXMLCore::IdentityHashTranslator::equal): Ditto.
+ (KXMLCore::IdentityHashTranslator::translate): Ditto. Translate now takes a reference
+ to write into instead of returning a value to avoid redundant copies.
+ (KXMLCore::HashTable::~HashTable): Use deallocateTable instead of freeing directly.
+ (KXMLCore::HashTable::insert): Based on HashTranslator now instead of separate
+ functions. Added a FIXME about a remaining rare excess copy.
+ (KXMLCore::HashTable::isEmptyBucket): Use KeyTraits directly instead of unwrapping
+ the key from Traits, to avoid creating and destroying pair, which copies.
+ (KXMLCore::HashTable::isDeletedBucket): ditto
+ (KXMLCore::HashTable::lookup): Use HashTranslator now instead of separate functions.
+ (KXMLCore::HashTable::initializeBucket): Renamed from emptyBucket. Use placement new to
+ work right for non-POD types.
+ (KXMLCore::HashTable::deleteBucket): Use assignDeleted to avoid excess copies.
+ (KXMLCore::HashTable::reinsert): use Mover template to copy or swap as appropriate
+ (KXMLCore::HashTable::allocateTable): Initialize every bucket if calloc won't do.
+ (KXMLCore::HashTable::deallocateTable): Destruct every bucket if needed.
+ (KXMLCore::HashTable::rehash): Avoid copy before reinserting, so that swap can do its magic.
+ (KXMLCore::HashTable::clear): use deallocateTable instead of freeing directly.
+ (KXMLCore::HashTable::HashTable): be more dumb when copying to ensure that non-POD types
+ work right
+ * kxmlcore/HashFunctions.h:
+ (KXMLCore::PointerHash): Specialize PointerHash for RefPtr
+ * kxmlcore/HashMap.h:
+ (KXMLCore::extractFirst): Return a reference not a full object to avoid
+ copies.
+ (KXMLCore::HashMapTranslator::hash): Use a special translator for insertion
+ to defer making the pair as long as possible, thus avoiding needless copies.
+ (KXMLCore::HashMapTranslator::equal): ditto
+ (KXMLCore::HashMapTranslator::translate): ditto
+ (KXMLCore::::inlineAdd): Shared by set and add to insert using HashMapTranslator
+ (KXMLCore::::set): Use inlineAdd
+ (KXMLCore::::add): Use inlineAdd
+ * kxmlcore/HashMapPtrSpec.h:
+ (KXMLCore::): Pass KeyTraits along
+ * kxmlcore/HashSet.h:
+ (KXMLCore::identityExtract): Return a reference not a full object to avoid copies.
+ (KXMLCore::HashSetTranslatorAdapter::hash): Redo adapter stuff to work with
+ the new HashTranslator approach.
+ (KXMLCore::HashSetTranslatorAdapter::equal): ditto
+ (KXMLCore::HashSetTranslatorAdapter::translate): ditto
+ (KXMLCore::::insert): ditto
+ * kxmlcore/HashTraits.h:
+ (KXMLCore::GenericHashTraits): This is intended be used as a base class for
+ customized traits: sensible defaults.
+ (KXMLCore::): Use it a bunch
+ (KXMLCore::assignDeleted): template function to allow pairs to be assigned the
+ deleted value w/o excess copies.
+ (KXMLCore::PairHashTraits::emptyValue): Updated
+ (KXMLCore::PairHashTraits::deletedValue): Updated
+ (KXMLCore::PairHashTraits::assignDeletedValue): part of assignDeleted hack
+ (KXMLCore::DeletedValueAssigner::assignDeletedValue): Use template magic
+ to either use use deletedValue or assignDeletedValue for the cases where we care.
+ * kxmlcore/RefPtr.h:
+ (KXMLCore::RefPtr::swap): Added swap method.
+ (KXMLCore::swap): Added swap free function.
+ * kjs/identifier.cpp:
+ (KJS::CStringTranslator::hash): Use new HashTranslator class approach to
+ alternate type based insertion.
+ (KJS::CStringTranslator::equal): ditto
+ (KJS::CStringTranslator::translate): ditto
+ (KJS::Identifier::add): ditto
+ (KJS::UCharBufferTranslator::hash): ditto
+ (KJS::UCharBufferTranslator::equal): ditto
+ (KJS::UCharBufferTranslator::translate): ditto
+
+ - irrelevant change:
+
+ * kjs/array_object.cpp:
+ (ArrayProtoFunc::callAsFunction): Removed a stray space.
+
2005-12-22 Anders Carlsson <andersca at mac.com>
Reviewed by Eric and Darin.
1.60 +1 -1 JavaScriptCore/kjs/array_object.cpp
Index: array_object.cpp
===================================================================
RCS file: /cvs/root/JavaScriptCore/kjs/array_object.cpp,v
retrieving revision 1.59
retrieving revision 1.60
diff -u -r1.59 -r1.60
--- array_object.cpp 19 Dec 2005 00:27:28 -0000 1.59
+++ array_object.cpp 23 Dec 2005 01:52:42 -0000 1.60
@@ -448,7 +448,7 @@
// fall through
case Join: {
- static HashSet< JSObject*, PointerHash<JSObject*> > visitedElems;
+ static HashSet<JSObject*, PointerHash<JSObject*> > visitedElems;
if (visitedElems.contains(thisObj))
return jsString("");
UString separator = ",";
1.26 +48 -42 JavaScriptCore/kjs/identifier.cpp
Index: identifier.cpp
===================================================================
RCS file: /cvs/root/JavaScriptCore/kjs/identifier.cpp,v
retrieving revision 1.25
retrieving revision 1.26
diff -u -r1.25 -r1.26
--- identifier.cpp 20 Dec 2005 20:12:47 -0000 1.25
+++ identifier.cpp 23 Dec 2005 01:52:42 -0000 1.26
@@ -98,30 +98,33 @@
return true;
}
-inline unsigned hash(const char* const& c)
+struct CStringTranslator
{
- return UString::Rep::computeHash(c);
-}
+ static unsigned hash(const char *c)
+ {
+ return UString::Rep::computeHash(c);
+ }
-inline bool equal(UString::Rep* const& r, const char* const& s)
-{
- return Identifier::equal(r, s);
-}
+ static bool equal(UString::Rep *r, const char *s)
+ {
+ return Identifier::equal(r, s);
+ }
-inline UString::Rep *convert(const char* const& c, unsigned hash)
-{
- int length = strlen(c);
- UChar *d = static_cast<UChar *>(fastMalloc(sizeof(UChar) * length));
- for (int i = 0; i != length; i++)
- d[i] = c[i];
-
- UString::Rep *r = UString::Rep::create(d, length).release();
- r->isIdentifier = 1;
- r->rc = 0;
- r->_hash = hash;
+ static void translate(UString::Rep*& location, const char *c, unsigned hash)
+ {
+ int length = strlen(c);
+ UChar *d = static_cast<UChar *>(fastMalloc(sizeof(UChar) * length));
+ for (int i = 0; i != length; i++)
+ d[i] = c[i];
+
+ UString::Rep *r = UString::Rep::create(d, length).release();
+ r->isIdentifier = 1;
+ r->rc = 0;
+ r->_hash = hash;
- return r;
-}
+ location = r;
+ }
+};
PassRefPtr<UString::Rep> Identifier::add(const char *c)
{
@@ -131,7 +134,7 @@
if (length == 0)
return pass(&UString::Rep::empty);
- return pass(*identifierTable().insert<const char *, hash, KJS::equal, convert>(c).first);
+ return pass(*identifierTable().insert<const char *, CStringTranslator>(c).first);
}
struct UCharBuffer {
@@ -139,29 +142,32 @@
uint length;
};
-inline unsigned hash(const UCharBuffer& buf)
+struct UCharBufferTranslator
{
- return UString::Rep::computeHash(buf.s, buf.length);
-}
-
-inline bool equal(UString::Rep* const& str, const UCharBuffer& buf)
-{
- return Identifier::equal(str, buf.s, buf.length);
-}
+ static unsigned hash(const UCharBuffer& buf)
+ {
+ return UString::Rep::computeHash(buf.s, buf.length);
+ }
-inline UString::Rep *convert(const UCharBuffer& buf, unsigned hash)
-{
- UChar *d = static_cast<UChar *>(fastMalloc(sizeof(UChar) * buf.length));
- for (unsigned i = 0; i != buf.length; i++)
- d[i] = buf.s[i];
-
- UString::Rep *r = UString::Rep::create(d, buf.length).release();
- r->isIdentifier = 1;
- r->rc = 0;
- r->_hash = hash;
+ static bool equal(UString::Rep *str, const UCharBuffer& buf)
+ {
+ return Identifier::equal(str, buf.s, buf.length);
+ }
- return r;
-}
+ static void translate(UString::Rep *& location, const UCharBuffer& buf, unsigned hash)
+ {
+ UChar *d = static_cast<UChar *>(fastMalloc(sizeof(UChar) * buf.length));
+ for (unsigned i = 0; i != buf.length; i++)
+ d[i] = buf.s[i];
+
+ UString::Rep *r = UString::Rep::create(d, buf.length).release();
+ r->isIdentifier = 1;
+ r->rc = 0;
+ r->_hash = hash;
+
+ location = r;
+ }
+};
PassRefPtr<UString::Rep> Identifier::add(const UChar *s, int length)
{
@@ -169,7 +175,7 @@
return pass(&UString::Rep::empty);
UCharBuffer buf = {s, length};
- return pass(*identifierTable().insert<UCharBuffer, hash, KJS::equal, convert>(buf).first);
+ return pass(*identifierTable().insert<UCharBuffer, UCharBufferTranslator>(buf).first);
}
PassRefPtr<UString::Rep> Identifier::add(UString::Rep *r)
1.3 +7 -0 JavaScriptCore/kxmlcore/HashFunctions.h
Index: HashFunctions.h
===================================================================
RCS file: /cvs/root/JavaScriptCore/kxmlcore/HashFunctions.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- HashFunctions.h 13 Dec 2005 11:06:05 -0000 1.2
+++ HashFunctions.h 23 Dec 2005 01:52:43 -0000 1.3
@@ -25,6 +25,8 @@
#include <stdint.h>
+#include "RefPtr.h"
+
namespace KXMLCore {
template<typename T> class DefaultHash;
@@ -72,6 +74,11 @@
static unsigned hash(T key) { return pointerHash<sizeof(void *)>((void *)key); }
static bool equal(T a, T b) { return a == b; }
};
+
+ template<typename P> struct PointerHash<RefPtr<P> > {
+ static unsigned hash(const RefPtr<P>& key) { return pointerHash<sizeof(void *)>((void *)key.get()); }
+ static bool equal(const RefPtr<P>& a, const RefPtr<P>& b) { return a == b; }
+ };
} // namespace KXMLCore
1.3 +43 -10 JavaScriptCore/kxmlcore/HashMap.h
Index: HashMap.h
===================================================================
RCS file: /cvs/root/JavaScriptCore/kxmlcore/HashMap.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- HashMap.h 13 Dec 2005 11:06:05 -0000 1.2
+++ HashMap.h 23 Dec 2005 01:52:43 -0000 1.3
@@ -30,20 +30,45 @@
namespace KXMLCore {
template<typename PairType>
-inline typename PairType::first_type extractFirst(const PairType& value)
+inline typename PairType::first_type const& extractFirst(const PairType& value)
{
return value.first;
}
+template<typename Key, typename Mapped, typename HashFunctions>
+class HashMapTranslator
+{
+ typedef pair<Key, Mapped> ValueType;
+
+public:
+ static unsigned hash(const Key& key)
+ {
+ return HashFunctions::hash(key);
+ }
+
+ static bool equal(const Key& a, const Key& b)
+ {
+ return HashFunctions::equal(a, b);
+ }
+
+ static void translate(ValueType& location, const Key& key, const Mapped& mapped, unsigned)
+ {
+ ValueType tmp(key, mapped);
+ swap(tmp, location);
+ }
+};
+
+
template<typename Key, typename Mapped, typename HashFunctions = DefaultHash<Key>, typename KeyTraits = HashTraits<Key>, typename MappedTraits = HashTraits<Mapped> >
class HashMap {
public:
typedef Key KeyType;
typedef Mapped MappedType;
- typedef std::pair<Key, Mapped> ValueType;
+ typedef pair<Key, Mapped> ValueType;
typedef PairHashTraits<KeyTraits, MappedTraits> ValueTraits;
private:
- typedef HashTable<KeyType, ValueType, extractFirst<ValueType>, HashFunctions, ValueTraits> ImplType;
+ typedef HashTable<KeyType, ValueType, extractFirst<ValueType>, HashFunctions, ValueTraits, KeyTraits> ImplType;
+ typedef HashMapTranslator<Key, Mapped, HashFunctions> TranslatorType;
public:
typedef typename ImplType::iterator iterator;
typedef typename ImplType::const_iterator const_iterator;
@@ -68,18 +93,20 @@
// 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
- std::pair<iterator, bool> set(const KeyType &key, const MappedType &mapped);
+ pair<iterator, bool> set(const KeyType &key, const MappedType &mapped);
// does nothing if key is already present
// return value is a pair of the iterator to the key location,
// and a boolean that's true if a new value was actually added
- std::pair<iterator, bool> add(const KeyType &key, const MappedType &mapped);
+ pair<iterator, bool> add(const KeyType &key, const MappedType &mapped);
void remove(const KeyType& key);
void remove(iterator it);
void clear();
private:
+ pair<iterator, bool> inlineAdd(const KeyType &key, const MappedType &mapped);
+
ImplType m_impl;
};
@@ -144,10 +171,16 @@
}
template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-std::pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::set(const KeyType &key, const MappedType &mapped)
+pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::inlineAdd(const KeyType &key, const MappedType &mapped)
+{
+ return m_impl.template insert<KeyType, MappedType, TranslatorType>(key, mapped);
+}
+
+template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
+pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::set(const KeyType &key, const MappedType &mapped)
{
- pair<iterator, bool> result = m_impl.insert(ValueType(key, mapped));
- // the insert call above won't change anything if the key is
+ 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;
@@ -155,9 +188,9 @@
}
template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
-std::pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::add(const KeyType &key, const MappedType &mapped)
+pair<typename HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::iterator, bool> HashMap<Key, Mapped, HashFunctions, KeyTraits, MappedTraits>::add(const KeyType &key, const MappedType &mapped)
{
- return m_impl.insert(ValueType(key, mapped));
+ return inlineAdd(key, mapped);
}
template<typename Key, typename Mapped, typename HashFunctions, typename KeyTraits, typename MappedTraits>
1.3 +2 -2 JavaScriptCore/kxmlcore/HashMapPtrSpec.h
Index: HashMapPtrSpec.h
===================================================================
RCS file: /cvs/root/JavaScriptCore/kxmlcore/HashMapPtrSpec.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -r1.2 -r1.3
--- HashMapPtrSpec.h 13 Dec 2005 11:06:05 -0000 1.2
+++ HashMapPtrSpec.h 23 Dec 2005 01:52:43 -0000 1.3
@@ -180,8 +180,8 @@
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 HashTableIterator<void *, ImplValueType, extractFirst<ImplValueType>, DefaultHash<void *>, PairHashTraits<HashTraits<void *>, HashTraits<void *> >, HashTraits<void *> > ImplIterator;
+ typedef HashTableConstIterator<void *, ImplValueType, extractFirst<ImplValueType>, DefaultHash<void *>, PairHashTraits<HashTraits<void *>, HashTraits<void *> >, HashTraits<void *> > ImplConstIterator;
typedef PointerHashIteratorAdapter<P, Q *> iterator;
typedef PointerHashConstIteratorAdapter<P, Q *> const_iterator;
1.5 +28 -11 JavaScriptCore/kxmlcore/HashSet.h
Index: HashSet.h
===================================================================
RCS file: /cvs/root/JavaScriptCore/kxmlcore/HashSet.h,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- HashSet.h 4 Nov 2005 17:30:27 -0000 1.4
+++ HashSet.h 23 Dec 2005 01:52:43 -0000 1.5
@@ -30,21 +30,35 @@
namespace KXMLCore {
template <typename T>
- inline T identityExtract(const T& t)
+ inline const T& identityExtract(const T& t)
{
return t;
}
- template<typename Value, typename T, Value ConvertT(const T&, unsigned)>
- inline Value convertAdapter(const T& t, const T&, unsigned h)
- {
- return ConvertT(t, h);
- }
+ template<typename Value, typename 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 = DefaultHash<Value>, typename Traits = HashTraits<Value> >
class HashSet {
private:
- typedef HashTable<Value, Value, identityExtract<Value>, HashFunctions, Traits> ImplType;
+ typedef HashTable<Value, Value, identityExtract<Value>, HashFunctions, Traits, Traits> ImplType;
public:
typedef Value ValueType;
typedef typename ImplType::iterator iterator;
@@ -69,8 +83,11 @@
// a special version of insert() that finds the object by hashing and comparing
// with some other type, to avoid the cost of type conversion if the object is already
- // in the table
- template<typename T, unsigned HashT(const T&), bool EqualT(const ValueType&, const T&), ValueType ConvertT(const T&, unsigned)>
+ // 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> insert(const T& value);
void remove(const ValueType& value);
@@ -148,10 +165,10 @@
}
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)>
+ template<typename T, typename HashSetTranslator>
std::pair<typename HashSet<Value, HashFunctions, Traits>::iterator, bool> HashSet<Value, HashFunctions, Traits>::insert(const T& value)
{
- return m_impl.insert<T, T, HashT, EqualT, convertAdapter<Value, T, ConvertT> >(value, value);
+ return m_impl.template insert<T, T, HashSetTranslatorAdapter<ValueType, T, HashSetTranslator> >(value, value);
}
template<typename Value, typename HashFunctions, typename Traits>
1.2 +156 -93 JavaScriptCore/kxmlcore/HashTable.h
Index: HashTable.h
===================================================================
RCS file: /cvs/root/JavaScriptCore/kxmlcore/HashTable.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -r1.1 -r1.2
--- HashTable.h 28 Sep 2005 22:01:17 -0000 1.1
+++ HashTable.h 23 Dec 2005 01:52:43 -0000 1.2
@@ -24,7 +24,9 @@
#define KXMLCORE_HASH_TABLE_H
#include "FastMalloc.h"
+#include "HashTraits.h"
#include <utility>
+#include <algorithm>
namespace KXMLCore {
@@ -52,19 +54,19 @@
#define checkTableConsistencyExceptSize() ((void)0)
#endif
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
class HashTable;
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
class HashTableIterator {
private:
- typedef HashTable<Key, Value, ExtractKey, HashFunctions, Traits> HashTableType;
- typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits> iterator;
+ typedef HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> HashTableType;
+ typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> iterator;
typedef Value ValueType;
typedef ValueType& ReferenceType;
typedef ValueType *PointerType;
- friend class HashTable<Key, Value, ExtractKey, HashFunctions, Traits>;
+ friend class HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>;
void skipEmptyBuckets()
{
@@ -111,17 +113,17 @@
PointerType m_endPosition;
};
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
class HashTableConstIterator {
private:
- typedef HashTable<Key, Value, ExtractKey, HashFunctions, Traits> HashTableType;
- typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits> iterator;
- typedef HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits> const_iterator;
+ typedef HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> HashTableType;
+ typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> iterator;
+ typedef HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> const_iterator;
typedef Value ValueType;
typedef const ValueType& ReferenceType;
typedef const ValueType *PointerType;
- friend class HashTable<Key, Value, ExtractKey, HashFunctions, Traits>;
+ friend class HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>;
HashTableConstIterator(PointerType position, PointerType endPosition)
: m_position(position), m_endPosition(endPosition)
@@ -170,16 +172,66 @@
PointerType m_endPosition;
};
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
+ using std::swap;
+
+ // swap pairs by component, in case of pair members that specialize swap
+ template<typename T, typename U>
+ inline void swap(pair<T, U>& a, pair<T, U>& b)
+ {
+ swap(a.first, b.first);
+ swap(a.second, b.second);
+ }
+
+ template<typename T, bool useSwap>
+ class Mover;
+
+ template<typename T>
+ struct Mover<T, true> {
+ static void move(T& from, T& to)
+ {
+ swap(from, to);
+ }
+ };
+
+ template<typename T>
+ struct Mover<T, false> {
+ static void move(T& from, T& to)
+ {
+ to = from;
+ }
+ };
+
+ template<typename Key, typename Value, typename HashFunctions>
+ class IdentityHashTranslator {
+
+ 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(Value& location, const Key& key, const Value& value, unsigned)
+ {
+ location = value;
+ }
+ };
+
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
class HashTable {
public:
- typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits> iterator;
- typedef HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits> const_iterator;
+ typedef HashTableIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> iterator;
+ typedef HashTableConstIterator<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits> const_iterator;
typedef Key KeyType;
typedef Value ValueType;
+ typedef IdentityHashTranslator<Key, Value, HashFunctions> IdentityTranslatorType;
HashTable() : m_table(0), m_tableSize(0), m_tableSizeMask(0), m_keyCount(0), m_deletedCount(0) {}
- ~HashTable() { fastFree(m_table); }
+ ~HashTable() { deallocateTable(m_table, m_tableSize); }
HashTable(const HashTable& other);
void swap(const HashTable& other);
@@ -193,13 +245,13 @@
int size() const { return m_keyCount; }
int capacity() const { return m_tableSize; }
- std::pair<iterator, bool> insert(const ValueType& value) { return insert<KeyType, ValueType, hash, equal, identityConvert>(extractKey(value), value); }
+ pair<iterator, bool> insert(const ValueType& value) { return insert<KeyType, ValueType, IdentityTranslatorType>(ExtractKey(value), value); }
// a special version of insert() that finds the object by hashing and comparing
// with some other type, to avoid the cost of type conversion if the object is already
// in the table
- template<typename T, typename Extra, unsigned HashT(const T&), bool EqualT(const Key&, const T&), ValueType ConvertT(const T&, const Extra &, unsigned)>
- std::pair<iterator, bool> insert(const T& key, const Extra& extra);
+ template<typename T, typename Extra, typename HashTranslator>
+ pair<iterator, bool> insert(const T& key, const Extra& extra);
iterator find(const KeyType& key);
const_iterator find(const KeyType& key) const;
@@ -209,24 +261,19 @@
void remove(iterator it);
void clear();
- static bool isEmptyBucket(const ValueType& value) { return extractKey(value) == extractKey(Traits::emptyValue()); }
- static bool isDeletedBucket(const ValueType& value) { return extractKey(value) == extractKey(Traits::deletedValue()); }
+ static bool isEmptyBucket(const ValueType& value) { return ExtractKey(value) == KeyTraits::emptyValue(); }
+ static bool isDeletedBucket(const ValueType& value) { return ExtractKey(value) == KeyTraits::deletedValue(); }
static bool isEmptyOrDeletedBucket(const ValueType& value) { return isEmptyBucket(value) || isDeletedBucket(value); }
private:
- static unsigned hash(const KeyType& key) { return HashFunctions::hash(key); }
- static bool equal(const KeyType& a, const KeyType& b) { return HashFunctions::equal(a, b); }
- // FIXME: assumes key == value; special lookup needs adjusting
- static ValueType identityConvert(const KeyType& key, const ValueType& value, unsigned) { return value; }
- static KeyType extractKey(const ValueType& value) { return ExtractKey(value); }
-
static ValueType *allocateTable(int size);
+ static void deallocateTable(ValueType *table, int size);
+
+ typedef pair<ValueType *, bool> LookupType;
+ typedef pair<LookupType, unsigned> FullLookupType;
- typedef std::pair<ValueType *, bool> LookupType;
- typedef std::pair<LookupType, unsigned> FullLookupType;
-
- LookupType lookup(const Key& key) { return lookup<Key, hash, equal>(key).first; }
- template<typename T, unsigned HashT(const T&), bool EqualT(const Key&, const T&)>
+ LookupType lookup(const Key& key) { return lookup<Key, IdentityTranslatorType>(key).first; }
+ template<typename T, typename HashTranslator>
FullLookupType lookup(const T&);
void remove(ValueType *);
@@ -238,10 +285,10 @@
void shrink() { rehash(m_tableSize / 2); }
void rehash(int newTableSize);
- void reinsert(const ValueType&);
+ void reinsert(ValueType&);
- static void clearBucket(ValueType& key) { key = Traits::emptyValue();}
- static void deleteBucket(ValueType& key) { key = Traits::deletedValue();}
+ static void initializeBucket(ValueType& bucket) { new (&bucket) ValueType(Traits::emptyValue()); }
+ static void deleteBucket(ValueType& bucket) { assignDeleted<ValueType, Traits>(bucket); }
FullLookupType makeLookupResult(ValueType *position, bool found, unsigned hash)
{
@@ -267,13 +314,13 @@
int m_deletedCount;
};
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
- template<typename T, unsigned HashT(const T&), bool EqualT(const Key&, const T&)>
- inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::FullLookupType HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::lookup(const T& key)
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ template<typename T, typename HashTranslator>
+ inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::FullLookupType HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::lookup(const T& key)
{
assert(m_table);
- unsigned h = HashT(key);
+ unsigned h = HashTranslator::hash(key);
int sizeMask = m_tableSizeMask;
int i = h & sizeMask;
int k = 0;
@@ -289,7 +336,7 @@
while (!isEmptyBucket(*(entry = table + i))) {
if (isDeletedBucket(*entry))
deletedEntry = entry;
- else if (EqualT(extractKey(*entry), key))
+ else if (HashTranslator::equal(ExtractKey(*entry), key))
return makeLookupResult(entry, true, h);
#if DUMP_HASHTABLE_STATS
++probeCount;
@@ -304,16 +351,16 @@
}
- 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)
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ template<typename T, typename Extra, typename HashTranslator>
+ inline pair<typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::iterator, bool> HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::insert(const T& key, const Extra &extra)
{
if (!m_table)
expand();
checkTableConsistency();
- FullLookupType lookupResult = lookup<T, HashT, EqualT>(key);
+ FullLookupType lookupResult = lookup<T, HashTranslator>(key);
ValueType *entry = lookupResult.first.first;
bool found = lookupResult.first.second;
@@ -326,11 +373,14 @@
if (isDeletedBucket(*entry))
--m_deletedCount;
- *entry = ConvertT(key, extra, h);
+ HashTranslator::translate(*entry, key, extra, h);
++m_keyCount;
if (shouldExpand()) {
- KeyType enteredKey = extractKey(*entry);
+ // FIXME: this makes an extra copy on expand. Probably not that bad since
+ // expand is rare, but would be better to have a version of expand that can
+ // follow a pivot entry and return the new position
+ KeyType enteredKey = ExtractKey(*entry);
expand();
return std::make_pair(find(enteredKey), true);
}
@@ -340,21 +390,21 @@
return std::make_pair(makeIterator(entry), true);
}
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
- inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::reinsert(const ValueType& entry)
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::reinsert(ValueType& entry)
{
assert(m_table);
- assert(!lookup(extractKey(entry)).second);
- assert(!isDeletedBucket(*(lookup(extractKey(entry)).first)));
+ assert(!lookup(ExtractKey(entry)).second);
+ assert(!isDeletedBucket(*(lookup(ExtractKey(entry)).first)));
#if DUMP_HASHTABLE_STATS
++HashTableStats::numReinserts;
#endif
- *(lookup(extractKey(entry)).first) = entry;
+ Mover<ValueType, Traits::needsDestruction>::move(entry, *(lookup(ExtractKey(entry)).first));
}
- 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)
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::iterator HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::find(const Key& key)
{
if (!m_table)
return end();
@@ -365,8 +415,8 @@
return makeIterator(result.first);
}
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
- inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::const_iterator HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::find(const Key& key) const
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ inline typename HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::const_iterator HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::find(const Key& key) const
{
if (!m_table)
return end();
@@ -377,8 +427,8 @@
return makeConstIterator(result.first);
}
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
- inline bool HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::contains(const KeyType& key) const
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ inline bool HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::contains(const KeyType& key) const
{
if (!m_table)
return false;
@@ -386,8 +436,8 @@
return const_cast<HashTable *>(this)->lookup(key).second;
}
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
- inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::remove(ValueType *pos)
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::remove(ValueType *pos)
{
checkTableConsistency();
@@ -405,8 +455,8 @@
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)
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::remove(const KeyType& key)
{
if (!m_table)
return;
@@ -414,8 +464,8 @@
remove(find(key));
}
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
- inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::remove(iterator it)
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::remove(iterator it)
{
if (it == end())
return;
@@ -424,8 +474,8 @@
}
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
- inline Value *HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::allocateTable(int size)
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ inline Value *HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::allocateTable(int size)
{
// would use a template member function with explicit specializations here, but
// gcc doesn't appear to support that
@@ -434,14 +484,26 @@
else {
ValueType *result = reinterpret_cast<ValueType *>(fastMalloc(size * sizeof(ValueType)));
for (int i = 0; i < size; i++) {
- clearBucket(result[i]);
+ initializeBucket(result[i]);
}
return result;
}
}
+
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::deallocateTable(ValueType *table, int size)
+ {
+ if (Traits::needsDestruction) {
+ for (int i = 0; i < size; ++i) {
+ (&table[i])->~ValueType();
+ }
+ }
+
+ fastFree(table);
+ }
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
- inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::expand()
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::expand()
{
int newSize;
if (m_tableSize == 0)
@@ -454,8 +516,8 @@
rehash(newSize);
}
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
- void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::rehash(int newTableSize)
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::rehash(int newTableSize)
{
checkTableConsistencyExceptSize();
@@ -472,44 +534,45 @@
m_table = allocateTable(newTableSize);
for (int i = 0; i != oldTableSize; ++i) {
- ValueType entry = oldTable[i];
- if (!isEmptyOrDeletedBucket(entry))
- reinsert(entry);
+ if (!isEmptyOrDeletedBucket(oldTable[i]))
+ reinsert(oldTable[i]);
}
m_deletedCount = 0;
- fastFree(oldTable);
+ deallocateTable(oldTable, oldTableSize);
checkTableConsistency();
}
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
- inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::clear()
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ inline void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::clear()
{
- fastFree(m_table);
+ deallocateTable(m_table, m_tableSize);
m_table = 0;
m_tableSize = 0;
m_tableSizeMask = 0;
m_keyCount = 0;
}
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
- HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::HashTable(const HashTable& other)
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::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)
+ , m_tableSize(0)
+ , m_tableSizeMask(0)
+ , m_keyCount(0)
+ , m_deletedCount(0)
{
- if (m_tableSize != 0) {
- m_table = fastMalloc(m_tableSize);
- memcpy(other.m_table, m_table, m_tableSize * sizeof(ValueType));
+ // doesn't matter if copying a hashtable is efficient so just
+ // do it the dumb way, by copying each element.
+ iterator end = other.end();
+ for (iterator it = other.begin(); it != end; ++it) {
+ insert(*it);
}
}
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
- void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::swap(const HashTable& other)
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::swap(const HashTable& other)
{
ValueType *tmp_table = m_table;
m_table = other.m_table;
@@ -532,8 +595,8 @@
other.m_deletedCount = tmp_deletedCount;
}
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
- HashTable<Key, Value, ExtractKey, HashFunctions, Traits>& HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::operator=(const HashTable& other)
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>& HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::operator=(const HashTable& other)
{
HashTable tmp(other);
swap(tmp);
@@ -542,16 +605,16 @@
#if CHECK_HASHTABLE_CONSISTENCY
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
- void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::checkTableConsistency() const
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::checkTableConsistency() const
{
checkTableConsistencyExceptSize();
assert(!shouldExpand());
assert(!shouldShrink());
}
- template<typename Key, typename Value, Key ExtractKey(const Value &), typename HashFunctions, typename Traits>
- void HashTable<Key, Value, ExtractKey, HashFunctions, Traits>::checkTableConsistencyExceptSize() const
+ template<typename Key, typename Value, const Key& ExtractKey(const Value &), typename HashFunctions, typename Traits, typename KeyTraits>
+ void HashTable<Key, Value, ExtractKey, HashFunctions, Traits, KeyTraits>::checkTableConsistencyExceptSize() const
{
if (!m_table)
return;
@@ -568,7 +631,7 @@
continue;
}
- const_iterator it = find(extractKey(*entry));
+ const_iterator it = find(ExtractKey(*entry));
assert(entry == it.m_position);
++count;
}
1.4 +77 -34 JavaScriptCore/kxmlcore/HashTraits.h
Index: HashTraits.h
===================================================================
RCS file: /cvs/root/JavaScriptCore/kxmlcore/HashTraits.h,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- HashTraits.h 22 Dec 2005 00:55:34 -0000 1.3
+++ HashTraits.h 23 Dec 2005 01:52:43 -0000 1.4
@@ -23,6 +23,7 @@
#ifndef KXMLCORE_HASH_TRAITS_H
#define KXMLCORE_HASH_TRAITS_H
+#include "RefPtr.h"
#include <utility>
namespace KXMLCore {
@@ -44,64 +45,106 @@
template <> struct IsInteger<unsigned long long> { static const bool value = true; };
template<typename T>
- struct HashTraits {
- typedef T traitType;
+ struct GenericHashTraits {
+ typedef T TraitType;
static const bool emptyValueIsZero = IsInteger<T>::value;
-
- static traitType emptyValue() {
- return traitType();
- }
+ static const bool needsDestruction = !IsInteger<T>::value;
+ static TraitType emptyValue() { return IsInteger<T>::value ? 0 : TraitType(); }
+ };
+
+ template<typename T>
+ struct HashTraits : GenericHashTraits<T> {
};
// may not be appropriate for all uses since it would disallow 0 and -1 as keys
template<>
- struct HashTraits<int> {
- typedef int traitType;
+ struct HashTraits<int> : GenericHashTraits<int> {
+ static TraitType deletedValue() { return -1; }
+ };
+
+ template<typename P>
+ struct HashTraits<P *> : GenericHashTraits<P *> {
+ typedef P *TraitType;
static const bool emptyValueIsZero = true;
-
- static traitType emptyValue() {
- return 0;
- }
- static traitType deletedValue() {
- return -1;
- }
+ static const bool needsDestruction = false;
+ static TraitType emptyValue() { return reinterpret_cast<P *>(0); }
+ static TraitType deletedValue() { return reinterpret_cast<P *>(-1); }
};
template<typename P>
- struct HashTraits<P *> {
- typedef P *traitType;
+ struct HashTraits<RefPtr<P> > : GenericHashTraits<RefPtr<P> > {
static const bool emptyValueIsZero = true;
-
- static traitType emptyValue() {
- return reinterpret_cast<P *>(0);
- }
- static traitType deletedValue() {
- return reinterpret_cast<P *>(-1);
- }
};
+ template<typename T, typename Traits>
+ class DeletedValueAssigner;
+
+ template<typename T, typename Traits>
+ inline void assignDeleted(T& location)
+ {
+ DeletedValueAssigner<T, Traits>::assignDeletedValue(location);
+ }
+
template<typename FirstTraits, typename SecondTraits>
- struct PairHashTraits {
+ struct PairHashTraits : GenericHashTraits<pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType> > {
private:
- typedef typename FirstTraits::traitType FirstType;
- typedef typename SecondTraits::traitType SecondType;
+ typedef typename FirstTraits::TraitType FirstType;
+ typedef typename SecondTraits::TraitType SecondType;
public:
- typedef pair<FirstType, SecondType> traitType;
-
+ typedef pair<FirstType, SecondType> TraitType;
+
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());
+ static TraitType emptyValue()
+ {
+ return TraitType(FirstTraits::emptyValue(), SecondTraits::emptyValue());
}
- static traitType deletedValue() {
- return traitType(FirstTraits::deletedValue(), SecondTraits::emptyValue());
+
+ static TraitType deletedValue()
+ {
+ return TraitType(FirstTraits::deletedValue(), SecondTraits::emptyValue());
+ }
+
+ static void assignDeletedValue(TraitType& location)
+ {
+ assignDeleted<FirstType, 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> >
+ {
+ static void assignDeletedValue(pair<typename FirstTraits::TraitType, typename SecondTraits::TraitType>& location)
+ {
+ PairHashTraits<FirstTraits, SecondTraits>::assignDeletedValue(location);
+ }
+ };
+
+ template<typename First, typename Second>
+ struct DeletedValueAssigner<pair<First, Second>, HashTraits<pair<First, Second> > >
+ {
+ static void assignDeletedValue(pair<First, Second>& location)
+ {
+ HashTraits<pair<First, Second> >::assignDeletedValue(location);
+ }
+ };
+
+
} // namespace KXMLCore
using KXMLCore::HashTraits;
1.9 +12 -0 JavaScriptCore/kxmlcore/RefPtr.h
Index: RefPtr.h
===================================================================
RCS file: /cvs/root/JavaScriptCore/kxmlcore/RefPtr.h,v
retrieving revision 1.8
retrieving revision 1.9
diff -u -r1.8 -r1.9
--- RefPtr.h 22 Dec 2005 16:48:08 -0000 1.8
+++ RefPtr.h 23 Dec 2005 01:52:43 -0000 1.9
@@ -60,6 +60,8 @@
template <typename U> RefPtr& operator=(PassRefPtr<U>&);
template <typename U> RefPtr& operator=(PassRefPtr_Ref<U>);
+ void swap(RefPtr&);
+
private:
T *m_ptr;
};
@@ -138,6 +140,16 @@
return *this;
}
+ template <class T> inline void RefPtr<T>::swap(RefPtr<T>& o)
+ {
+ stap(m_ptr, o.m_ptr);
+ }
+
+ template <class T> inline void swap(RefPtr<T>& a, RefPtr<T>& b)
+ {
+ a.swap(b);
+ }
+
template <typename T, typename U> inline bool operator==(const RefPtr<T>& a, const RefPtr<U>& b)
{
return a.get() == b.get();
More information about the webkit-changes
mailing list