identifier.cpp

00001 /*
00002  *  This file is part of the KDE libraries
00003  *  Copyright (C) 2003 Apple Computer, Inc
00004  *
00005  *  This library is free software; you can redistribute it and/or
00006  *  modify it under the terms of the GNU Library General Public
00007  *  License as published by the Free Software Foundation; either
00008  *  version 2 of the License, or (at your option) any later version.
00009  *
00010  *  This library is distributed in the hope that it will be useful,
00011  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00012  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013  *  Library General Public License for more details.
00014  *
00015  *  You should have received a copy of the GNU Library General Public License
00016  *  along with this library; see the file COPYING.LIB.  If not, write to
00017  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00018  *  Boston, MA 02110-1301, USA.
00019  *
00020  */
00021 
00022 #include "identifier.h"
00023 
00024 #include <stdio.h>
00025 #include <stdlib.h>
00026 #include <string.h>
00027 
00028 #define DUMP_STATISTICS 0
00029 
00030 namespace KJS {
00031 
00032 #if DUMP_STATISTICS
00033 
00034 static int numProbes;
00035 static int numCollisions;
00036 
00037 struct IdentifierStatisticsExitLogger { ~IdentifierStatisticsExitLogger(); };
00038 
00039 static IdentifierStatisticsExitLogger logger;
00040 
00041 IdentifierStatisticsExitLogger::~IdentifierStatisticsExitLogger()
00042 {
00043     printf("\nKJS::Identifier statistics\n\n");
00044     printf("%d probes\n", numProbes);
00045     printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
00046 }
00047 
00048 #endif
00049 
00050 extern const Identifier argumentsPropertyName("arguments");
00051 extern const Identifier calleePropertyName("callee");
00052 extern const Identifier callerPropertyName("caller");
00053 extern const Identifier constructorPropertyName("constructor");
00054 extern const Identifier lengthPropertyName("length");
00055 extern const Identifier messagePropertyName("message");
00056 extern const Identifier namePropertyName("name");
00057 extern const Identifier prototypePropertyName("prototype");
00058 extern const Identifier specialPrototypePropertyName("__proto__");
00059 extern const Identifier toLocaleStringPropertyName("toLocaleString");
00060 extern const Identifier toStringPropertyName("toString");
00061 extern const Identifier valueOfPropertyName("valueOf");
00062 
00063 static const int _minTableSize = 64;
00064 
00065 UString::Rep **Identifier::_table;
00066 int Identifier::_tableSize;
00067 int Identifier::_tableSizeMask;
00068 int Identifier::_keyCount;
00069 
00070 bool Identifier::equal(UString::Rep *r, const char *s)
00071 {
00072     int length = r->len;
00073     const UChar *d = r->data();
00074     for (int i = 0; i != length; ++i)
00075         if (d[i].uc != (unsigned char)s[i])
00076             return false;
00077     return s[length] == 0;
00078 }
00079 
00080 bool Identifier::equal(UString::Rep *r, const UChar *s, int length)
00081 {
00082     if (r->len != length)
00083         return false;
00084     const UChar *d = r->data();
00085     for (int i = 0; i != length; ++i)
00086         if (d[i].uc != s[i].uc)
00087             return false;
00088     return true;
00089 }
00090 
00091 bool Identifier::equal(UString::Rep *r, UString::Rep *b)
00092 {
00093     int length = r->len;
00094     if (length != b->len)
00095         return false;
00096     const UChar *d = r->data();
00097     const UChar *s = b->data();
00098     for (int i = 0; i != length; ++i)
00099         if (d[i].uc != s[i].uc)
00100             return false;
00101     return true;
00102 }
00103 
00104 UString::Rep *Identifier::add(const char *c)
00105 {
00106     if (!c)
00107         return &UString::Rep::null;
00108     int length = strlen(c);
00109     if (length == 0)
00110         return &UString::Rep::empty;
00111 
00112     if (!_table)
00113         expand();
00114 
00115     unsigned hash = UString::Rep::computeHash(c);
00116 
00117     int i = hash & _tableSizeMask;
00118 #if DUMP_STATISTICS
00119     ++numProbes;
00120     numCollisions += _table[i] && !equal(_table[i], c);
00121 #endif
00122     while (UString::Rep *key = _table[i]) {
00123         if (equal(key, c))
00124             return key;
00125         i = (i + 1) & _tableSizeMask;
00126     }
00127 
00128     UChar *d = new UChar[length];
00129     for (int j = 0; j != length; j++)
00130         d[j] = c[j];
00131 
00132     UString::Rep *r = new UString::Rep;
00133     r->dat = d;
00134     r->len = length;
00135     r->capacity = UString::Rep::capacityForIdentifier;
00136     r->rc = 0;
00137     r->_hash = hash;
00138 
00139     _table[i] = r;
00140     ++_keyCount;
00141 
00142     if (_keyCount * 2 >= _tableSize)
00143         expand();
00144 
00145     return r;
00146 }
00147 
00148 UString::Rep *Identifier::add(const UChar *s, int length)
00149 {
00150     if (length == 0)
00151         return &UString::Rep::empty;
00152 
00153     if (!_table)
00154         expand();
00155 
00156     unsigned hash = UString::Rep::computeHash(s, length);
00157 
00158     int i = hash & _tableSizeMask;
00159 #if DUMP_STATISTICS
00160     ++numProbes;
00161     numCollisions += _table[i] && !equal(_table[i], s, length);
00162 #endif
00163     while (UString::Rep *key = _table[i]) {
00164         if (equal(key, s, length))
00165             return key;
00166         i = (i + 1) & _tableSizeMask;
00167     }
00168 
00169     UChar *d = new UChar[length];
00170     for (int j = 0; j != length; j++)
00171         d[j] = s[j];
00172 
00173     UString::Rep *r = new UString::Rep;
00174     r->dat = d;
00175     r->len = length;
00176     r->capacity = UString::Rep::capacityForIdentifier;
00177     r->rc = 0;
00178     r->_hash = hash;
00179 
00180     _table[i] = r;
00181     ++_keyCount;
00182 
00183     if (_keyCount * 2 >= _tableSize)
00184         expand();
00185 
00186     return r;
00187 }
00188 
00189 UString::Rep *Identifier::add(UString::Rep *r)
00190 {
00191     if (r->capacity == UString::Rep::capacityForIdentifier)
00192         return r;
00193     if (r->len == 0)
00194         return &UString::Rep::empty;
00195 
00196     if (!_table)
00197         expand();
00198 
00199     unsigned hash = r->hash();
00200 
00201     int i = hash & _tableSizeMask;
00202 #if DUMP_STATISTICS
00203     ++numProbes;
00204     numCollisions += _table[i] && !equal(_table[i], r);
00205 #endif
00206     while (UString::Rep *key = _table[i]) {
00207         if (equal(key, r))
00208             return key;
00209         i = (i + 1) & _tableSizeMask;
00210     }
00211 
00212     r->capacity = UString::Rep::capacityForIdentifier;
00213 
00214     _table[i] = r;
00215     ++_keyCount;
00216 
00217     if (_keyCount * 2 >= _tableSize)
00218         expand();
00219 
00220     return r;
00221 }
00222 
00223 inline void Identifier::insert(UString::Rep *key)
00224 {
00225     unsigned hash = key->hash();
00226 
00227     int i = hash & _tableSizeMask;
00228 #if DUMP_STATISTICS
00229     ++numProbes;
00230     numCollisions += _table[i] != 0;
00231 #endif
00232     while (_table[i])
00233         i = (i + 1) & _tableSizeMask;
00234 
00235     _table[i] = key;
00236 }
00237 
00238 void Identifier::remove(UString::Rep *r)
00239 {
00240     unsigned hash = r->hash();
00241 
00242     UString::Rep *key;
00243 
00244     int i = hash & _tableSizeMask;
00245 #if DUMP_STATISTICS
00246     ++numProbes;
00247     numCollisions += _table[i] && equal(_table[i], r);
00248 #endif
00249     while ((key = _table[i])) {
00250         if (equal(key, r))
00251             break;
00252         i = (i + 1) & _tableSizeMask;
00253     }
00254     if (!key)
00255         return;
00256 
00257     _table[i] = 0;
00258     --_keyCount;
00259 
00260     if (_keyCount * 6 < _tableSize && _tableSize > _minTableSize) {
00261         shrink();
00262         return;
00263     }
00264 
00265     // Reinsert all the items to the right in the same cluster.
00266     while (1) {
00267         i = (i + 1) & _tableSizeMask;
00268         key = _table[i];
00269         if (!key)
00270             break;
00271         _table[i] = 0;
00272         insert(key);
00273     }
00274 }
00275 
00276 void Identifier::expand()
00277 {
00278     rehash(_tableSize == 0 ? _minTableSize : _tableSize * 2);
00279 }
00280 
00281 void Identifier::shrink()
00282 {
00283     rehash(_tableSize / 2);
00284 }
00285 
00286 void Identifier::rehash(int newTableSize)
00287 {
00288     int oldTableSize = _tableSize;
00289     UString::Rep **oldTable = _table;
00290 
00291     _tableSize = newTableSize;
00292     _tableSizeMask = newTableSize - 1;
00293     _table = (UString::Rep **)calloc(newTableSize, sizeof(UString::Rep *));
00294 
00295     for (int i = 0; i != oldTableSize; ++i)
00296         if (UString::Rep *key = oldTable[i])
00297             insert(key);
00298 
00299     free(oldTable);
00300 }
00301 
00302 const Identifier &Identifier::null()
00303 {
00304     static Identifier null;
00305     return null;
00306 }
00307 
00308 } // namespace KJS
KDE Home | KDE Accessibility Home | Description of Access Keys