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 constructorPropertyName("constructor");
00053 extern const Identifier lengthPropertyName("length");
00054 extern const Identifier messagePropertyName("message");
00055 extern const Identifier namePropertyName("name");
00056 extern const Identifier prototypePropertyName("prototype");
00057 extern const Identifier specialPrototypePropertyName("__proto__");
00058 extern const Identifier toLocaleStringPropertyName("toLocaleString");
00059 extern const Identifier toStringPropertyName("toString");
00060 extern const Identifier valueOfPropertyName("valueOf");
00061 
00062 static const int _minTableSize = 64;
00063 
00064 UString::Rep **Identifier::_table;
00065 int Identifier::_tableSize;
00066 int Identifier::_tableSizeMask;
00067 int Identifier::_keyCount;
00068 
00069 bool Identifier::equal(UString::Rep *r, const char *s)
00070 {
00071     int length = r->len;
00072     const UChar *d = r->data();
00073     for (int i = 0; i != length; ++i)
00074         if (d[i].uc != (unsigned char)s[i])
00075             return false;
00076     return s[length] == 0;
00077 }
00078 
00079 bool Identifier::equal(UString::Rep *r, const UChar *s, int length)
00080 {
00081     if (r->len != length)
00082         return false;
00083     const UChar *d = r->data();
00084     for (int i = 0; i != length; ++i)
00085         if (d[i].uc != s[i].uc)
00086             return false;
00087     return true;
00088 }
00089 
00090 bool Identifier::equal(UString::Rep *r, UString::Rep *b)
00091 {
00092     int length = r->len;
00093     if (length != b->len)
00094         return false;
00095     const UChar *d = r->data();
00096     const UChar *s = b->data();
00097     for (int i = 0; i != length; ++i)
00098         if (d[i].uc != s[i].uc)
00099             return false;
00100     return true;
00101 }
00102 
00103 UString::Rep *Identifier::add(const char *c)
00104 {
00105     if (!c)
00106         return &UString::Rep::null;
00107     int length = strlen(c);
00108     if (length == 0)
00109         return &UString::Rep::empty;
00110 
00111     if (!_table)
00112         expand();
00113 
00114     unsigned hash = UString::Rep::computeHash(c);
00115 
00116     int i = hash & _tableSizeMask;
00117 #if DUMP_STATISTICS
00118     ++numProbes;
00119     numCollisions += _table[i] && !equal(_table[i], c);
00120 #endif
00121     while (UString::Rep *key = _table[i]) {
00122         if (equal(key, c))
00123             return key;
00124         i = (i + 1) & _tableSizeMask;
00125     }
00126 
00127     UChar *d = new UChar[length];
00128     for (int j = 0; j != length; j++)
00129         d[j] = c[j];
00130 
00131     UString::Rep *r = new UString::Rep;
00132     r->dat = d;
00133     r->len = length;
00134     r->capacity = UString::Rep::capacityForIdentifier;
00135     r->rc = 0;
00136     r->_hash = hash;
00137 
00138     _table[i] = r;
00139     ++_keyCount;
00140 
00141     if (_keyCount * 2 >= _tableSize)
00142         expand();
00143 
00144     return r;
00145 }
00146 
00147 UString::Rep *Identifier::add(const UChar *s, int length)
00148 {
00149     if (length == 0)
00150         return &UString::Rep::empty;
00151 
00152     if (!_table)
00153         expand();
00154 
00155     unsigned hash = UString::Rep::computeHash(s, length);
00156 
00157     int i = hash & _tableSizeMask;
00158 #if DUMP_STATISTICS
00159     ++numProbes;
00160     numCollisions += _table[i] && !equal(_table[i], s, length);
00161 #endif
00162     while (UString::Rep *key = _table[i]) {
00163         if (equal(key, s, length))
00164             return key;
00165         i = (i + 1) & _tableSizeMask;
00166     }
00167 
00168     UChar *d = new UChar[length];
00169     for (int j = 0; j != length; j++)
00170         d[j] = s[j];
00171 
00172     UString::Rep *r = new UString::Rep;
00173     r->dat = d;
00174     r->len = length;
00175     r->capacity = UString::Rep::capacityForIdentifier;
00176     r->rc = 0;
00177     r->_hash = hash;
00178 
00179     _table[i] = r;
00180     ++_keyCount;
00181 
00182     if (_keyCount * 2 >= _tableSize)
00183         expand();
00184 
00185     return r;
00186 }
00187 
00188 UString::Rep *Identifier::add(UString::Rep *r)
00189 {
00190     if (r->capacity == UString::Rep::capacityForIdentifier)
00191         return r;
00192     if (r->len == 0)
00193         return &UString::Rep::empty;
00194 
00195     if (!_table)
00196         expand();
00197 
00198     unsigned hash = r->hash();
00199 
00200     int i = hash & _tableSizeMask;
00201 #if DUMP_STATISTICS
00202     ++numProbes;
00203     numCollisions += _table[i] && !equal(_table[i], r);
00204 #endif
00205     while (UString::Rep *key = _table[i]) {
00206         if (equal(key, r))
00207             return key;
00208         i = (i + 1) & _tableSizeMask;
00209     }
00210 
00211     r->capacity = UString::Rep::capacityForIdentifier;
00212 
00213     _table[i] = r;
00214     ++_keyCount;
00215 
00216     if (_keyCount * 2 >= _tableSize)
00217         expand();
00218 
00219     return r;
00220 }
00221 
00222 inline void Identifier::insert(UString::Rep *key)
00223 {
00224     unsigned hash = key->hash();
00225 
00226     int i = hash & _tableSizeMask;
00227 #if DUMP_STATISTICS
00228     ++numProbes;
00229     numCollisions += _table[i] != 0;
00230 #endif
00231     while (_table[i])
00232         i = (i + 1) & _tableSizeMask;
00233 
00234     _table[i] = key;
00235 }
00236 
00237 void Identifier::remove(UString::Rep *r)
00238 {
00239     unsigned hash = r->hash();
00240 
00241     UString::Rep *key;
00242 
00243     int i = hash & _tableSizeMask;
00244 #if DUMP_STATISTICS
00245     ++numProbes;
00246     numCollisions += _table[i] && equal(_table[i], r);
00247 #endif
00248     while ((key = _table[i])) {
00249         if (equal(key, r))
00250             break;
00251         i = (i + 1) & _tableSizeMask;
00252     }
00253     if (!key)
00254         return;
00255 
00256     _table[i] = 0;
00257     --_keyCount;
00258 
00259     if (_keyCount * 6 < _tableSize && _tableSize > _minTableSize) {
00260         shrink();
00261         return;
00262     }
00263 
00264     // Reinsert all the items to the right in the same cluster.
00265     while (1) {
00266         i = (i + 1) & _tableSizeMask;
00267         key = _table[i];
00268         if (!key)
00269             break;
00270         _table[i] = 0;
00271         insert(key);
00272     }
00273 }
00274 
00275 void Identifier::expand()
00276 {
00277     rehash(_tableSize == 0 ? _minTableSize : _tableSize * 2);
00278 }
00279 
00280 void Identifier::shrink()
00281 {
00282     rehash(_tableSize / 2);
00283 }
00284 
00285 void Identifier::rehash(int newTableSize)
00286 {
00287     int oldTableSize = _tableSize;
00288     UString::Rep **oldTable = _table;
00289 
00290     _tableSize = newTableSize;
00291     _tableSizeMask = newTableSize - 1;
00292     _table = (UString::Rep **)calloc(newTableSize, sizeof(UString::Rep *));
00293 
00294     for (int i = 0; i != oldTableSize; ++i)
00295         if (UString::Rep *key = oldTable[i])
00296             insert(key);
00297 
00298     free(oldTable);
00299 }
00300 
00301 const Identifier &Identifier::null()
00302 {
00303     static Identifier null;
00304     return null;
00305 }
00306 
00307 } // namespace KJS
KDE Home | KDE Accessibility Home | Description of Access Keys