[webkit-changes] cvs commit: WebCore/khtml/xml dom_atomicstring.cpp
Maciej
mjs at opensource.apple.com
Tue Jun 28 14:18:18 PDT 2005
mjs 05/06/28 14:18:17
Modified: WebCore.pbproj project.pbxproj
khtml/xml dom_atomicstring.cpp
Added: khtml/misc hashset.h hashtable.cpp hashtable.h
Log:
Revision Changes Path
1.559 +48 -0 WebCore/WebCore.pbproj/project.pbxproj
Index: project.pbxproj
===================================================================
RCS file: /cvs/root/WebCore/WebCore.pbproj/project.pbxproj,v
retrieving revision 1.558
retrieving revision 1.559
diff -u -r1.558 -r1.559
--- project.pbxproj 28 Jun 2005 01:57:42 -0000 1.558
+++ project.pbxproj 28 Jun 2005 21:18:16 -0000 1.559
@@ -1279,6 +1279,48 @@
settings = {
};
};
+ 65F378260870D958000B2F94 = {
+ fileEncoding = 30;
+ isa = PBXFileReference;
+ lastKnownFileType = sourcecode.c.h;
+ path = hashset.h;
+ refType = 4;
+ sourceTree = "<group>";
+ };
+ 65F378270870D958000B2F94 = {
+ fileEncoding = 30;
+ isa = PBXFileReference;
+ lastKnownFileType = sourcecode.cpp.cpp;
+ path = hashtable.cpp;
+ refType = 4;
+ sourceTree = "<group>";
+ };
+ 65F378280870D958000B2F94 = {
+ fileEncoding = 30;
+ isa = PBXFileReference;
+ lastKnownFileType = sourcecode.c.h;
+ path = hashtable.h;
+ refType = 4;
+ sourceTree = "<group>";
+ };
+ 65F378290870D958000B2F94 = {
+ fileRef = 65F378260870D958000B2F94;
+ isa = PBXBuildFile;
+ settings = {
+ };
+ };
+ 65F3782A0870D958000B2F94 = {
+ fileRef = 65F378270870D958000B2F94;
+ isa = PBXBuildFile;
+ settings = {
+ };
+ };
+ 65F3782B0870D958000B2F94 = {
+ fileRef = 65F378280870D958000B2F94;
+ isa = PBXBuildFile;
+ settings = {
+ };
+ };
65F80697054D9F86008BF776 = {
fileEncoding = 30;
isa = PBXFileReference;
@@ -2724,6 +2766,8 @@
1A69D381085627410009880D,
550A0BCA085F6039007353D6,
550A0BCE085F604D007353D6,
+ 65F378290870D958000B2F94,
+ 65F3782B0870D958000B2F94,
);
isa = PBXHeadersBuildPhase;
runOnlyForDeploymentPostprocessing = 0;
@@ -5097,6 +5141,7 @@
1A69D382085627410009880D,
550A0BC9085F6039007353D6,
550A0BCD085F604D007353D6,
+ 65F3782A0870D958000B2F94,
);
isa = PBXSourcesBuildPhase;
runOnlyForDeploymentPostprocessing = 0;
@@ -8790,6 +8835,9 @@
};
F523D29C02DE43D9018635CA = {
children = (
+ 65F378260870D958000B2F94,
+ 65F378270870D958000B2F94,
+ 65F378280870D958000B2F94,
BC7294F703804B3C00A80166,
BC7294F803804B3C00A80166,
F523D27802DE43D7018635CA,
1.1 WebCore/khtml/misc/hashset.h
Index: hashset.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 HASHSET_H
#define HASHSET_H
#include "hashtable.h"
namespace khtml {
template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
class HashSet {
public:
typedef HashTable<Key, Hash, Equal> ImplType;
typedef typename ImplType::KeyType KeyType;
HashSet() {}
int size() const { return m_impl.count(); }
bool isEmpty() const { return size() == 0; }
KeyType insert(const KeyType &key)
{
return m_impl.insert(key);
}
// 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)> KeyType insert(const T& key)
{
return m_impl.insert<T, HashT, EqualT, ConvertT>(key);
}
#if 0
Iterator find(const KeyType& key)
{
return m_impl.find(key);
}
#endif
bool contains(const KeyType& key)
{
return find(key) != 0;
}
void remove(const KeyType& key)
{
m_impl.remove(key);
}
private:
ImplType m_impl;
};
} // namespace khtml
#endif /* HASHSET_H */
1.1 WebCore/khtml/misc/hashtable.cpp
Index: hashtable.cpp
===================================================================
/*
This file is part of the KDE libraries
Copyright (C) 2005 Apple Computer
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Library General Public
License as published by the Free Software Foundation; either
version 2 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Library General Public License for more details.
You should have received a copy of the GNU Library General Public License
along with this library; see the file COPYING.LIB. If not, write to
the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA.
*/
#include "hashtable.h"
namespace khtml {
#if DUMP_HASHTABLE_STATS
int HashTableStats::numAccesses;
int HashTableStats::numCollisions;
int HashTableStats::collisionGraph[4096];
int HashTableStats::maxCollisions;
int HashTableStats::numRehashes;
int HashTableStats::numRemoves;
int HashTableStats::numReinserts;
static HashTableStats logger;
HashTableStats::~HashTableStats()
{
printf("\nkhtml::HashTable statistics\n\n");
printf("%d accesses\n", numAccesses);
printf("%d total collisions, average %.2f probes per access\n", numCollisions, 1.0 * (numAccesses + numCollisions) / numAccesses);
printf("longest collision chain: %d\n", maxCollisions);
for (int i = 1; i <= maxCollisions; i++) {
printf(" %d lookups with exactly %d collisions (%.2f%% , %.2f%% with this many or more)\n", collisionGraph[i], i, 100.0 * (collisionGraph[i] - collisionGraph[i+1]) / numAccesses, 100.0 * collisionGraph[i] / numAccesses);
}
printf("%d rehashes\n", numRehashes);
printf("%d removes, %d reinserts\n", numRemoves, numReinserts);
}
void HashTableStats::recordCollisionAtCount(int count)
{
if (count > maxCollisions)
maxCollisions = count;
numCollisions++;
collisionGraph[count]++;
}
#endif
} // namespace khtml
1.1 WebCore/khtml/misc/hashtable.h
Index: hashtable.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 HASHTABLE_H
#define HASHTABLE_H
#include "main_thread_malloc.h"
namespace khtml {
#define DUMP_HASHTABLE_STATS 0
#if DUMP_HASHTABLE_STATS
struct HashTableStats {
~HashTableStats();
static int numAccesses;
static int numCollisions;
static int collisionGraph[4096];
static int maxCollisions;
static int numRehashes;
static int numRemoves;
static int numReinserts;
static void recordCollisionAtCount(int count);
};
#endif
// 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.
// FIXME: add Iterator type, along with begin() and end() methods, change insert and
// find to return Iterator
template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
class HashTable {
public:
typedef Key KeyType;
HashTable() : m_table(0), m_tableSize(0), m_tableSizeMask(0), m_keyCount(0) {}
~HashTable() { main_thread_free(m_table); }
HashTable(const HashTable& other);
void swap(const HashTable& other);
HashTable& operator=(const HashTable& other);
int size() const { return m_keyCount; }
KeyType insert(const KeyType& key);
// 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)> KeyType insert(const T& key);
#if 0
Iterator find(const KeyType& key)
{
if (!m_table)
return 0;
unsigned h = hash(key);
int i = h & m_tableSizeMask;
KeyType *item;
while (*(item = m_table +i)) {
if (equal(*item, key))
return item;
i = (i + 1) & m_tableSizeMask;
}
return 0;
}
#endif
void remove(const KeyType& key);
private:
unsigned hash(const KeyType& key) const { return Hash(key); }
bool equal(const KeyType& a, const KeyType& b) const { return Equal(a, b); }
void expand() { rehash(m_tableSize == 0 ? m_minTableSize : m_tableSize * 2); }
void shrink() { rehash(m_tableSize / 2); }
void rehash(int newTableSize);
void reinsert(const KeyType& key);
bool isEmptyBucket(const KeyType& key) { return key == 0; }
void clearBucket(KeyType& key) { key = 0;}
static const int m_minTableSize = 64;
KeyType *m_table;
int m_tableSize;
int m_tableSizeMask;
int m_keyCount;
};
template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
Key HashTable<Key, Hash, Equal>::insert(const Key& key)
{
if (!m_table)
expand();
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 entry;
#if DUMP_HASHTABLE_STATS
++collisionCount;
HashTableStats::recordCollisionAtCount(collisionCount);
#endif
i = (i + 1) & m_tableSizeMask;
}
m_table[i] = key;
++m_keyCount;
if (m_keyCount * 2 >= m_tableSize)
expand();
return key;
}
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)>
Key HashTable<Key, Hash, Equal>::insert(const T& key)
{
if (!m_table)
expand();
unsigned h = HashT(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 (EqualT(entry, key))
return entry;
#if DUMP_HASHTABLE_STATS
++collisionCount;
HashTableStats::recordCollisionAtCount(collisionCount);
#endif
i = (i + 1) & m_tableSizeMask;
}
KeyType convertedKey = ConvertT(key, h);
m_table[i] = convertedKey;
++m_keyCount;
if (m_keyCount * 2 >= m_tableSize)
expand();
return convertedKey;
}
template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
void HashTable<Key, Hash, Equal>::reinsert(const Key& key)
{
if (!m_table)
expand();
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 DUMP_HASHTABLE_STATS
++collisionCount;
HashTableStats::recordCollisionAtCount(collisionCount);
#endif
i = (i + 1) & m_tableSizeMask;
}
m_table[i] = key;
}
template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
void HashTable<Key, Hash, Equal>::remove(const Key& key)
{
unsigned h = hash(key);
int i = h & m_tableSizeMask;
#if DUMP_HASHTABLE_STATS
++HashTableStats::numAccesses;
++HashTableStats::numRemoves;
int collisionCount = 0;
#endif
KeyType entry;
while (!isEmptyBucket(entry = m_table[i])) {
if (equal(entry, key))
break;
#if DUMP_HASHTABLE_STATS
++collisionCount;
HashTableStats::recordCollisionAtCount(collisionCount);
#endif
i = (i + 1) & m_tableSizeMask;
}
if (!key)
return;
m_table[i] = 0;
--m_keyCount;
if (m_keyCount * 6 < m_tableSize && m_tableSize > m_minTableSize) {
shrink();
return;
}
// Reinsert all the items to the right in the same cluster.
while (1) {
i = (i + 1) & m_tableSizeMask;
entry = m_table[i];
if (isEmptyBucket(entry))
break;
#if DUMP_HASHTABLE_STATS
++HashTableStats::numReinserts;
#endif
clearBucket(m_table[i]);
reinsert(entry);
}
}
template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
void HashTable<Key, Hash, Equal>::rehash(int newTableSize)
{
int oldTableSize = m_tableSize;
KeyType *oldTable = m_table;
#if DUMP_HASHTABLE_STATS
if (oldTableSize != 0)
++HashTableStats::numRehashes;
#endif
m_tableSize = newTableSize;
m_tableSizeMask = newTableSize - 1;
m_table = (KeyType *)main_thread_calloc(newTableSize, sizeof(KeyType));
for (int i = 0; i != oldTableSize; ++i) {
KeyType key;
if (!isEmptyBucket(key = oldTable[i]))
reinsert(key);
}
main_thread_free(oldTable);
}
template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
HashTable<Key, Hash, Equal>::HashTable(const HashTable& other)
: m_table(0)
, m_tableSize(other.m_tableSize)
, m_tableSizeMask(other.m_tableSizeMask)
, m_keyCount(other.m_keyCount)
{
if (m_tableSize != 0) {
m_table = main_thread_malloc(m_tableSize);
memcpy(other.m_table, m_table, m_tableSize * sizeof(KeyType));
}
}
template<typename Key, unsigned Hash(const Key&), bool Equal(const Key&, const Key&)>
void HashTable<Key, Hash, Equal>::swap(const HashTable& other)
{
KeyType *tmp_table = m_table;
m_table = other.m_table;
other.m_table = tmp_table;
int tmp_tableSize = m_tableSize;
m_tableSize = other.m_tableSize;
other.m_tableSize = tmp_tableSize;
int tmp_tableSizeMask = m_tableSizeMask;
m_tableSizeMask = other.m_tableSizeMask;
other.m_tableSizeMask = tmp_tableSizeMask;
int tmp_keyCount = m_keyCount;
m_keyCount = other.m_keyCount;
other.m_keyCount = tmp_keyCount;
}
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)
{
HashTable tmp(other);
swap(tmp);
return *this;
}
} // namespace khtml
#endif // HASHTABLE_H
1.6 +68 -244 WebCore/khtml/xml/dom_atomicstring.cpp
Index: dom_atomicstring.cpp
===================================================================
RCS file: /cvs/root/WebCore/khtml/xml/dom_atomicstring.cpp,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -r1.5 -r1.6
--- dom_atomicstring.cpp 28 Jun 2005 05:47:26 -0000 1.5
+++ dom_atomicstring.cpp 28 Jun 2005 21:18:17 -0000 1.6
@@ -36,55 +36,40 @@
#include "dom_atomicstring.h"
#include "xml/dom_stringimpl.h"
+#include "hashset.h"
+
+using khtml::HashSet;
namespace DOM {
-#define DUMP_STATISTICS 0
-
-#if DUMP_STATISTICS
-
-static int numAccesses;
-static int numCollisions;
-static int collisionGraph[4096];
-static int maxCollisions;
-static int numRehashes;
-static int numRemoves;
-static int numReinserts;
-
-struct AtomicStringStatisticsExitLogger { ~AtomicStringStatisticsExitLogger(); };
-
-static AtomicStringStatisticsExitLogger logger;
-
-AtomicStringStatisticsExitLogger::~AtomicStringStatisticsExitLogger()
-{
- printf("\nkhtml::HashTable statistics\n\n");
- printf("%d accesses\n", numAccesses);
- printf("%d total collisions, average %.2f probes per access\n", numCollisions, 1.0 * (numAccesses + numCollisions) / numAccesses);
- printf("longest collision chain: %d\n", maxCollisions);
- for (int i = 1; i <= maxCollisions; i++) {
- printf(" %d lookups with exactly %d collisions (%.2f%% , %.2f%% with this many or more)\n", collisionGraph[i], i, 100.0 * (collisionGraph[i] - collisionGraph[i+1]) / numAccesses, 100.0 * collisionGraph[i] / numAccesses);
- }
- printf("%d rehashes\n", numRehashes);
- printf("%d removes, %d reinserts\n", numRemoves, numReinserts);
+inline unsigned hash(DOMStringImpl* const& s)
+{
+ return s->hash();
}
-static void recordCollisionAtCount(int count)
+bool equal(DOMStringImpl* const& r, DOMStringImpl* const& b)
{
- if (count > maxCollisions)
- maxCollisions = count;
- numCollisions++;
- collisionGraph[count]++;
+ 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;
}
-#endif
-const int _minTableSize = 64;
+static HashSet<DOMStringImpl *, hash, equal> stringTable;
-DOMStringImpl **AtomicString::_table;
-int AtomicString::_tableSize;
-int AtomicString::_tableSizeMask;
-int AtomicString::_keyCount;
+inline unsigned hash(const char* const& c)
+{
+ return DOMStringImpl::computeHash(c);
+}
-bool AtomicString::equal(DOMStringImpl *r, const char *s)
+inline bool equal(DOMStringImpl* const& r, const char* const& s)
{
if (!r && !s) return true;
if (!r || !s) return false;
@@ -99,36 +84,16 @@
bool AtomicString::equal(const AtomicString &a, const char *b)
{
- return equal(a.m_string.implementation(), b);
+ return DOM::equal(a.m_string.implementation(), b);
}
-bool AtomicString::equal(DOMStringImpl *r, const QChar *s, uint length)
+inline DOMStringImpl *convert(const char* const& c, unsigned hash)
{
- if (!r && !s) return true;
- if (!r || !s) return false;
-
- if (r->l != length)
- return false;
- const QChar *d = r->s;
- for (uint i = 0; i != length; ++i)
- if (d[i] != s[i])
- return false;
- return true;
-}
+ DOMStringImpl *r = new DOMStringImpl(c);
+ r->_hash = hash;
+ r->_inTable = true;
-bool AtomicString::equal(DOMStringImpl *r, DOMStringImpl *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;
+ return r;
}
DOMStringImpl *AtomicString::add(const char *c)
@@ -139,37 +104,41 @@
if (length == 0)
return DOMStringImpl::empty();
- if (!_table)
- expand();
-
- unsigned hash = DOMStringImpl::computeHash(c);
-
- int i = hash & _tableSizeMask;
-#if DUMP_STATISTICS
- ++numAccesses;
- int collisionCount = 0;
-#endif
- while (DOMStringImpl *key = _table[i]) {
- if (equal(key, c))
- return key;
-#if DUMP_STATISTICS
- ++collisionCount;
- recordCollisionAtCount(collisionCount);
-#endif
- i = (i + 1) & _tableSizeMask;
- }
+ return stringTable.insert<const char *, hash, DOM::equal, convert>(c);
+}
+
+
+struct QCharBuffer {
+ const QChar *s;
+ uint length;
+};
+
+inline unsigned hash(const QCharBuffer& buf)
+{
+ return DOMStringImpl::computeHash(buf.s, buf.length);
+}
+
+inline bool equal(DOMStringImpl* const&r, const QCharBuffer &buf)
+{
+ if (!r && !buf.s) return true;
+ if (!r || !buf.s) return false;
- DOMStringImpl *r = new DOMStringImpl(c, length);
+ if (r->l != buf.length)
+ return false;
+ const QChar *d = r->s;
+ for (uint i = 0; i != buf.length; ++i)
+ if (d[i] != buf.s[i])
+ 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;
- _table[i] = r;
- ++_keyCount;
-
- if (_keyCount * 2 >= _tableSize)
- expand();
-
- return r;
+ return r;
}
DOMStringImpl *AtomicString::add(const QChar *s, int length)
@@ -180,37 +149,8 @@
if (length == 0)
return DOMStringImpl::empty();
- if (!_table)
- expand();
-
- unsigned hash = DOMStringImpl::computeHash(s, length);
-
- int i = hash & _tableSizeMask;
-#if DUMP_STATISTICS
- ++numAccesses;
- int collisionCount = 0;
-#endif
- while (DOMStringImpl *key = _table[i]) {
- if (equal(key, s, length))
- return key;
-#if DUMP_STATISTICS
- ++collisionCount;
- recordCollisionAtCount(collisionCount);
-#endif
- i = (i + 1) & _tableSizeMask;
- }
-
- DOMStringImpl *r = new DOMStringImpl(s, length);
- r->_hash = hash;
- r->_inTable = true;
-
- _table[i] = r;
- ++_keyCount;
-
- if (_keyCount * 2 >= _tableSize)
- expand();
-
- return r;
+ QCharBuffer buf = {s, length};
+ return stringTable.insert<QCharBuffer, hash, DOM::equal, convert>(buf);
}
DOMStringImpl *AtomicString::add(DOMStringImpl *r)
@@ -221,131 +161,15 @@
if (r->l == 0)
return DOMStringImpl::empty();
- if (!_table)
- expand();
-
- unsigned hash = r->hash();
-
- int i = hash & _tableSizeMask;
-#if DUMP_STATISTICS
- ++numAccesses;
- int collisionCount = 0;
-#endif
- while (DOMStringImpl *key = _table[i]) {
- if (equal(key, r)) {
- return key;
- }
-#if DUMP_STATISTICS
- ++collisionCount;
- recordCollisionAtCount(collisionCount);
-#endif
- i = (i + 1) & _tableSizeMask;
- }
-
- r->_inTable = true;
- _table[i] = r;
- ++_keyCount;
-
- if (_keyCount * 2 >= _tableSize)
- expand();
-
- return r;
-}
-
-inline void AtomicString::insert(DOMStringImpl *key)
-{
- unsigned hash = key->hash();
-
- int i = hash & _tableSizeMask;
-#if DUMP_STATISTICS
- ++numAccesses;
- int collisionCount = 0;
-#endif
- while (_table[i] && !(key == _table[i])) {
-#if DUMP_STATISTICS
- ++collisionCount;
- recordCollisionAtCount(collisionCount);
-#endif
- i = (i + 1) & _tableSizeMask;
- }
- _table[i] = key;
+ DOMStringImpl *result = stringTable.insert(r);
+ if (result == r)
+ r->_inTable = true;
+ return result;
}
void AtomicString::remove(DOMStringImpl *r)
{
- unsigned hash = r->_hash;
-
- DOMStringImpl *key;
-
- int i = hash & _tableSizeMask;
-#if DUMP_STATISTICS
- ++numRemoves;
- ++numAccesses;
- int collisionCount = 0;
-#endif
- while ((key = _table[i])) {
- if (key == r)
- break;
-#if DUMP_STATISTICS
- ++collisionCount;
- recordCollisionAtCount(collisionCount);
-#endif
- i = (i + 1) & _tableSizeMask;
- }
- if (!key)
- return;
-
- _table[i] = 0;
- --_keyCount;
-
- if (_keyCount * 6 < _tableSize && _tableSize > _minTableSize) {
- shrink();
- return;
- }
-
- // Reinsert all the items to the right in the same cluster.
- while (1) {
- i = (i + 1) & _tableSizeMask;
- key = _table[i];
- if (!key)
- break;
-#if DUMP_STATISTICS
- ++numReinserts;
-#endif
- _table[i] = 0;
- insert(key);
- }
-}
-
-void AtomicString::expand()
-{
- rehash(_tableSize == 0 ? _minTableSize : _tableSize * 2);
-}
-
-void AtomicString::shrink()
-{
- rehash(_tableSize / 2);
-}
-
-void AtomicString::rehash(int newTableSize)
-{
- int oldTableSize = _tableSize;
- DOMStringImpl **oldTable = _table;
-
-#if DUMP_STATISTICS
- if (oldTableSize != 0)
- ++numRehashes;
-#endif
-
- _tableSize = newTableSize;
- _tableSizeMask = newTableSize - 1;
- _table = (DOMStringImpl **)calloc(newTableSize, sizeof(DOMStringImpl *));
-
- for (int i = 0; i != oldTableSize; ++i)
- if (DOMStringImpl *key = oldTable[i])
- insert(key);
-
- free(oldTable);
+ stringTable.remove(r);
}
// Global constants for property name strings.
More information about the webkit-changes
mailing list