kjs Library API Documentation

identifier.cpp

00001 /* 00002 * This file is part of the KDE libraries 00003 * Copyright (C) 2002 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., 59 Temple Place - Suite 330, 00018 * Boston, MA 02111-1307, 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->dat; 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->dat; 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->dat; 00096 const UChar *s = b->dat; 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 Logo
This file is part of the documentation for kjs Library Version 3.2.3.
Documentation copyright © 1996-2004 the KDE developers.
Generated on Fri Oct 8 11:14:42 2004 by doxygen 1.3.7 written by Dimitri van Heesch, © 1997-2003