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