identifier.cpp00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
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
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 }
|