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