[webkit-changes] cvs commit: JavaScriptCore/kjs identifier.cpp
identifier.h internal.cpp
Maciej
mjs at opensource.apple.com
Mon Dec 19 02:38:08 PST 2005
mjs 05/12/19 02:38:08
Modified: . ChangeLog
kjs identifier.cpp identifier.h internal.cpp
Log:
Reviewed by Geoff and Adele
- replaced custom Identifier hashtable with HashSet
* kjs/identifier.cpp:
(KXMLCore::):
(KJS::identifierTable):
(KJS::Identifier::equal):
(KJS::hash):
(KJS::equal):
(KJS::convert):
(KJS::Identifier::add):
(KJS::Identifier::remove):
* kjs/identifier.h:
* kjs/internal.cpp:
(KJS::InterpreterImp::initGlobalObject):
Revision Changes Path
1.911 +19 -0 JavaScriptCore/ChangeLog
Index: ChangeLog
===================================================================
RCS file: /cvs/root/JavaScriptCore/ChangeLog,v
retrieving revision 1.910
retrieving revision 1.911
diff -u -r1.910 -r1.911
--- ChangeLog 19 Dec 2005 00:27:26 -0000 1.910
+++ ChangeLog 19 Dec 2005 10:38:06 -0000 1.911
@@ -1,3 +1,22 @@
+2005-12-13 Maciej Stachowiak <mjs at apple.com>
+
+ Reviewed by Geoff and Adele
+
+ - replaced custom Identifier hashtable with HashSet
+
+ * kjs/identifier.cpp:
+ (KXMLCore::):
+ (KJS::identifierTable):
+ (KJS::Identifier::equal):
+ (KJS::hash):
+ (KJS::equal):
+ (KJS::convert):
+ (KJS::Identifier::add):
+ (KJS::Identifier::remove):
+ * kjs/identifier.h:
+ * kjs/internal.cpp:
+ (KJS::InterpreterImp::initGlobalObject):
+
2005-12-18 Justin Haygood <justin at xiondigital.net>
Reviewed, tweaked, and landed by Darin.
1.24 +76 -182 JavaScriptCore/kjs/identifier.cpp
Index: identifier.cpp
===================================================================
RCS file: /cvs/root/JavaScriptCore/kjs/identifier.cpp,v
retrieving revision 1.23
retrieving revision 1.24
diff -u -r1.23 -r1.24
--- identifier.cpp 6 Dec 2005 09:21:04 -0000 1.23
+++ identifier.cpp 19 Dec 2005 10:38:07 -0000 1.24
@@ -37,39 +37,34 @@
#include "identifier.h"
#include <kxmlcore/FastMalloc.h>
+#include <kxmlcore/HashSet.h>
#include <string.h> // for strlen
#include <new> // for placement new
-#define DUMP_STATISTICS 0
+namespace KXMLCore {
-namespace KJS {
-
-#if DUMP_STATISTICS
+ template<typename T> class DefaultHash;
-static int numProbes;
-static int numCollisions;
+ template<> struct DefaultHash<KJS::UString::Rep *> {
+ static unsigned hash(const KJS::UString::Rep *key) { return key->hash(); }
+ static bool equal(const KJS::UString::Rep *a, const KJS::UString::Rep *b) { return KJS::Identifier::equal(a, b); }
+ };
+}
-struct IdentifierStatisticsExitLogger { ~IdentifierStatisticsExitLogger(); };
+namespace KJS {
-static IdentifierStatisticsExitLogger logger;
+typedef HashSet<UString::Rep *> IdentifierTable;
+static IdentifierTable *table;
-IdentifierStatisticsExitLogger::~IdentifierStatisticsExitLogger()
+static inline IdentifierTable& identifierTable()
{
- printf("\nKJS::Identifier statistics\n\n");
- printf("%d probes\n", numProbes);
- printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
+ if (!table)
+ table = new IdentifierTable;
+ return *table;
}
-#endif
-
-const int _minTableSize = 64;
-UString::Rep **Identifier::_table;
-int Identifier::_tableSize;
-int Identifier::_tableSizeMask;
-int Identifier::_keyCount;
-
-bool Identifier::equal(UString::Rep *r, const char *s)
+bool Identifier::equal(const UString::Rep *r, const char *s)
{
int length = r->len;
const UChar *d = r->data();
@@ -79,7 +74,7 @@
return s[length] == 0;
}
-bool Identifier::equal(UString::Rep *r, const UChar *s, int length)
+bool Identifier::equal(const UString::Rep *r, const UChar *s, int length)
{
if (r->len != length)
return false;
@@ -90,7 +85,7 @@
return true;
}
-bool Identifier::equal(UString::Rep *r, UString::Rep *b)
+bool Identifier::equal(const UString::Rep *r, const UString::Rep *b)
{
int length = r->len;
if (length != b->len)
@@ -103,198 +98,97 @@
return true;
}
-UString::Rep *Identifier::add(const char *c)
+inline unsigned hash(const char* const& c)
{
- if (!c)
- return &UString::Rep::null;
- int length = strlen(c);
- if (length == 0)
- return &UString::Rep::empty;
-
- if (!_table)
- expand();
-
- unsigned hash = UString::Rep::computeHash(c);
-
- int i = hash & _tableSizeMask;
-#if DUMP_STATISTICS
- ++numProbes;
- numCollisions += _table[i] && !equal(_table[i], c);
-#endif
- while (UString::Rep *key = _table[i]) {
- if (equal(key, c))
- return key;
- i = (i + 1) & _tableSizeMask;
- }
-
- UChar *d = static_cast<UChar *>(fastMalloc(sizeof(UChar) * length));
- for (int j = 0; j != length; j++)
- d[j] = c[j];
-
- UString::Rep *r = UString::Rep::create(d, length).release();
- r->isIdentifier = 1;
- r->rc = 0;
- r->_hash = hash;
-
- _table[i] = r;
- ++_keyCount;
-
- if (_keyCount * 2 >= _tableSize)
- expand();
-
- return r;
+ return UString::Rep::computeHash(c);
}
-UString::Rep *Identifier::add(const UChar *s, int length)
+inline bool equal(UString::Rep* const& r, const char* const& s)
{
- if (length == 0)
- return &UString::Rep::empty;
-
- if (!_table)
- expand();
-
- unsigned hash = UString::Rep::computeHash(s, length);
-
- int i = hash & _tableSizeMask;
-#if DUMP_STATISTICS
- ++numProbes;
- numCollisions += _table[i] && !equal(_table[i], s, length);
-#endif
- while (UString::Rep *key = _table[i]) {
- if (equal(key, s, length))
- return key;
- i = (i + 1) & _tableSizeMask;
- }
-
+ 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 j = 0; j != length; j++)
- d[j] = s[j];
+ 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;
-
- _table[i] = r;
- ++_keyCount;
-
- if (_keyCount * 2 >= _tableSize)
- expand();
-
- return r;
+
+ return r;
}
-UString::Rep *Identifier::add(UString::Rep *r)
+UString::Rep *Identifier::add(const char *c)
{
- if (r->isIdentifier)
- return r;
- if (r->len == 0)
+ if (!c)
+ return &UString::Rep::null;
+ int length = strlen(c);
+ if (length == 0)
return &UString::Rep::empty;
- if (!_table)
- expand();
-
- unsigned hash = r->hash();
-
- int i = hash & _tableSizeMask;
-#if DUMP_STATISTICS
- ++numProbes;
- numCollisions += _table[i] && !equal(_table[i], r);
-#endif
- while (UString::Rep *key = _table[i]) {
- if (equal(key, r))
- return key;
- i = (i + 1) & _tableSizeMask;
- }
-
- r->isIdentifier = 1;
-
- _table[i] = r;
- ++_keyCount;
-
- if (_keyCount * 2 >= _tableSize)
- expand();
-
- return r;
+ return *identifierTable().insert<const char *, hash, KJS::equal, convert>(c).first;
}
-inline void Identifier::insert(UString::Rep *key)
+struct UCharBuffer {
+ const UChar *s;
+ uint length;
+};
+
+inline unsigned hash(const UCharBuffer& buf)
{
- unsigned hash = key->hash();
-
- int i = hash & _tableSizeMask;
-#if DUMP_STATISTICS
- ++numProbes;
- numCollisions += _table[i] != 0;
-#endif
- while (_table[i])
- i = (i + 1) & _tableSizeMask;
-
- _table[i] = key;
+ return UString::Rep::computeHash(buf.s, buf.length);
}
-void Identifier::remove(UString::Rep *r)
+inline bool equal(UString::Rep* const& str, const UCharBuffer& buf)
{
- unsigned hash = r->hash();
-
- UString::Rep *key;
-
- int i = hash & _tableSizeMask;
-#if DUMP_STATISTICS
- ++numProbes;
- numCollisions += _table[i] && equal(_table[i], r);
-#endif
- while ((key = _table[i])) {
- if (equal(key, r))
- break;
- 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;
- _table[i] = 0;
- insert(key);
- }
+ return Identifier::equal(str, buf.s, buf.length);
}
-void Identifier::expand()
+inline UString::Rep *convert(const UCharBuffer& buf, unsigned hash)
{
- rehash(_tableSize == 0 ? _minTableSize : _tableSize * 2);
+ 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;
+
+ return r;
}
-void Identifier::shrink()
+UString::Rep *Identifier::add(const UChar *s, int length)
{
- rehash(_tableSize / 2);
+ if (length == 0)
+ return &UString::Rep::empty;
+
+ UCharBuffer buf = {s, length};
+ return *identifierTable().insert<UCharBuffer, hash, KJS::equal, convert>(buf).first;
}
-void Identifier::rehash(int newTableSize)
+UString::Rep *Identifier::add(UString::Rep *r)
{
- int oldTableSize = _tableSize;
- UString::Rep **oldTable = _table;
+ if (r->isIdentifier)
+ return r;
- _tableSize = newTableSize;
- _tableSizeMask = newTableSize - 1;
- _table = (UString::Rep **)fastCalloc(newTableSize, sizeof(UString::Rep *));
+ if (r->len == 0)
+ return &UString::Rep::empty;
- for (int i = 0; i != oldTableSize; ++i)
- if (UString::Rep *key = oldTable[i])
- insert(key);
+ UString::Rep *result = *identifierTable().insert(r).first;
+ if (result == r)
+ r->isIdentifier = true;
+ return result;
+}
- fastFree(oldTable);
+void Identifier::remove(UString::Rep *r)
+{
+ identifierTable().remove(r);
}
// Global constants for property name strings.
1.21 +4 -15 JavaScriptCore/kjs/identifier.h
Index: identifier.h
===================================================================
RCS file: /cvs/root/JavaScriptCore/kjs/identifier.h,v
retrieving revision 1.20
retrieving revision 1.21
diff -u -r1.20 -r1.21
--- identifier.h 6 Dec 2005 09:21:04 -0000 1.20
+++ identifier.h 19 Dec 2005 10:38:07 -0000 1.21
@@ -65,13 +65,13 @@
static void remove(UString::Rep *);
+ static bool equal(const UString::Rep *, const char *);
+ static bool equal(const UString::Rep *, const UChar *, int length);
+ static bool equal(const UString::Rep *, const UString::Rep *);
+
private:
UString _ustring;
- static bool equal(UString::Rep *, const char *);
- static bool equal(UString::Rep *, const UChar *, int length);
- static bool equal(UString::Rep *, UString::Rep *);
-
static bool equal(const Identifier &a, const Identifier &b)
{ return a._ustring.rep() == b._ustring.rep(); }
static bool equal(const Identifier &a, const char *b)
@@ -80,17 +80,6 @@
static UString::Rep *add(const char *);
static UString::Rep *add(const UChar *, int length);
static UString::Rep *add(UString::Rep *);
-
- static void insert(UString::Rep *);
-
- static void rehash(int newTableSize);
- static void expand();
- static void shrink();
-
- static UString::Rep **_table;
- static int _tableSize;
- static int _tableSizeMask;
- static int _keyCount;
};
#if !KJS_IDENTIFIER_HIDE_GLOBALS
1.85 +1 -1 JavaScriptCore/kjs/internal.cpp
Index: internal.cpp
===================================================================
RCS file: /cvs/root/JavaScriptCore/kjs/internal.cpp,v
retrieving revision 1.84
retrieving revision 1.85
diff -u -r1.84 -r1.85
--- internal.cpp 16 Dec 2005 08:08:05 -0000 1.84
+++ internal.cpp 19 Dec 2005 10:38:07 -0000 1.85
@@ -472,7 +472,7 @@
recursion = 0;
}
- void InterpreterImp::initGlobalObject()
+void InterpreterImp::initGlobalObject()
{
Identifier::init();
More information about the webkit-changes
mailing list