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 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
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 }
|