Copy the KDE 3.5 branch to branches/trinity for new KDE 3.5 features.

BUG:215923


git-svn-id: svn://anonsvn.kde.org/home/kde/branches/trinity/kdelibs@1054174 283d02a7-25f6-0310-bc7c-ecb5cbfe19da

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