summaryrefslogtreecommitdiffstats
path: root/kjs/identifier.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'kjs/identifier.cpp')
-rw-r--r--kjs/identifier.cpp308
1 files changed, 308 insertions, 0 deletions
diff --git a/kjs/identifier.cpp b/kjs/identifier.cpp
new file mode 100644
index 000000000..835ab1208
--- /dev/null
+++ b/kjs/identifier.cpp
@@ -0,0 +1,308 @@
+/*
+ * This file is part of the KDE libraries
+ * Copyright (C) 2003 Apple Computer, Inc
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Library General Public
+ * License as published by the Free Software Foundation; either
+ * version 2 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public License
+ * along with this library; see the file COPYING.LIB. If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ * Boston, MA 02110-1301, USA.
+ *
+ */
+
+#include "identifier.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define DUMP_STATISTICS 0
+
+namespace KJS {
+
+#if DUMP_STATISTICS
+
+static int numProbes;
+static int numCollisions;
+
+struct IdentifierStatisticsExitLogger { ~IdentifierStatisticsExitLogger(); };
+
+static IdentifierStatisticsExitLogger logger;
+
+IdentifierStatisticsExitLogger::~IdentifierStatisticsExitLogger()
+{
+ printf("\nKJS::Identifier statistics\n\n");
+ printf("%d probes\n", numProbes);
+ printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
+}
+
+#endif
+
+extern const Identifier argumentsPropertyName("arguments");
+extern const Identifier calleePropertyName("callee");
+extern const Identifier callerPropertyName("caller");
+extern const Identifier constructorPropertyName("constructor");
+extern const Identifier lengthPropertyName("length");
+extern const Identifier messagePropertyName("message");
+extern const Identifier namePropertyName("name");
+extern const Identifier prototypePropertyName("prototype");
+extern const Identifier specialPrototypePropertyName("__proto__");
+extern const Identifier toLocaleStringPropertyName("toLocaleString");
+extern const Identifier toStringPropertyName("toString");
+extern const Identifier valueOfPropertyName("valueOf");
+
+static 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)
+{
+ int length = r->len;
+ const UChar *d = r->data();
+ for (int i = 0; i != length; ++i)
+ if (d[i].uc != (unsigned char)s[i])
+ return false;
+ return s[length] == 0;
+}
+
+bool Identifier::equal(UString::Rep *r, const UChar *s, int length)
+{
+ if (r->len != length)
+ return false;
+ const UChar *d = r->data();
+ for (int i = 0; i != length; ++i)
+ if (d[i].uc != s[i].uc)
+ return false;
+ return true;
+}
+
+bool Identifier::equal(UString::Rep *r, UString::Rep *b)
+{
+ int length = r->len;
+ if (length != b->len)
+ return false;
+ const UChar *d = r->data();
+ const UChar *s = b->data();
+ for (int i = 0; i != length; ++i)
+ if (d[i].uc != s[i].uc)
+ return false;
+ return true;
+}
+
+UString::Rep *Identifier::add(const char *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 = new UChar[length];
+ for (int j = 0; j != length; j++)
+ d[j] = c[j];
+
+ UString::Rep *r = new UString::Rep;
+ r->dat = d;
+ r->len = length;
+ r->capacity = UString::Rep::capacityForIdentifier;
+ r->rc = 0;
+ r->_hash = hash;
+
+ _table[i] = r;
+ ++_keyCount;
+
+ if (_keyCount * 2 >= _tableSize)
+ expand();
+
+ return r;
+}
+
+UString::Rep *Identifier::add(const UChar *s, int length)
+{
+ 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;
+ }
+
+ UChar *d = new UChar[length];
+ for (int j = 0; j != length; j++)
+ d[j] = s[j];
+
+ UString::Rep *r = new UString::Rep;
+ r->dat = d;
+ r->len = length;
+ r->capacity = UString::Rep::capacityForIdentifier;
+ r->rc = 0;
+ r->_hash = hash;
+
+ _table[i] = r;
+ ++_keyCount;
+
+ if (_keyCount * 2 >= _tableSize)
+ expand();
+
+ return r;
+}
+
+UString::Rep *Identifier::add(UString::Rep *r)
+{
+ if (r->capacity == UString::Rep::capacityForIdentifier)
+ return r;
+ if (r->len == 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->capacity = UString::Rep::capacityForIdentifier;
+
+ _table[i] = r;
+ ++_keyCount;
+
+ if (_keyCount * 2 >= _tableSize)
+ expand();
+
+ return r;
+}
+
+inline void Identifier::insert(UString::Rep *key)
+{
+ 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;
+}
+
+void Identifier::remove(UString::Rep *r)
+{
+ 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);
+ }
+}
+
+void Identifier::expand()
+{
+ rehash(_tableSize == 0 ? _minTableSize : _tableSize * 2);
+}
+
+void Identifier::shrink()
+{
+ rehash(_tableSize / 2);
+}
+
+void Identifier::rehash(int newTableSize)
+{
+ int oldTableSize = _tableSize;
+ UString::Rep **oldTable = _table;
+
+ _tableSize = newTableSize;
+ _tableSizeMask = newTableSize - 1;
+ _table = (UString::Rep **)calloc(newTableSize, sizeof(UString::Rep *));
+
+ for (int i = 0; i != oldTableSize; ++i)
+ if (UString::Rep *key = oldTable[i])
+ insert(key);
+
+ free(oldTable);
+}
+
+const Identifier &Identifier::null()
+{
+ static Identifier null;
+ return null;
+}
+
+} // namespace KJS
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-03 11:38:30 +0000