00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
#include "property_map.h"
00023
00024
#include "object.h"
00025
#include "reference_list.h"
00026
00027
#include <assert.h>
00028
00029
#define DEBUG_PROPERTIES 0
00030
#define DO_CONSISTENCY_CHECK 0
00031
#define DUMP_STATISTICS 0
00032
#define USE_SINGLE_ENTRY 1
00033
00034
00035
00036
00037
#if !DO_CONSISTENCY_CHECK
00038
#define checkConsistency() ((void)0)
00039
#endif
00040
00041
namespace KJS {
00042
00043
#if DUMP_STATISTICS
00044
00045
static int numProbes;
00046
static int numCollisions;
00047
00048
struct PropertyMapStatisticsExitLogger { ~PropertyMapStatisticsExitLogger(); };
00049
00050
static PropertyMapStatisticsExitLogger logger;
00051
00052 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
00053 {
00054 printf(
"\nKJS::PropertyMap statistics\n\n");
00055 printf(
"%d probes\n", numProbes);
00056 printf(
"%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
00057 }
00058
00059
#endif
00060
00061
struct PropertyMapHashTable
00062 {
00063
int sizeMask;
00064
int size;
00065
int keyCount;
00066 PropertyMapHashTableEntry entries[1];
00067 };
00068
00069
class SavedProperty {
00070
public:
00071 Identifier
key;
00072
Value value;
00073
int attributes;
00074 };
00075
00076 SavedProperties::SavedProperties() : _count(0), _properties(0) { }
00077
00078 SavedProperties::~SavedProperties()
00079 {
00080
delete [] _properties;
00081 }
00082
00083
00084
00085 PropertyMap::PropertyMap() : _table(0)
00086 {
00087 }
00088
00089 PropertyMap::~PropertyMap()
00090 {
00091
if (!_table) {
00092
#if USE_SINGLE_ENTRY
00093
UString::Rep *
key = _singleEntry.key;
00094
if (
key)
00095
key->deref();
00096
#endif
00097
return;
00098 }
00099
00100
for (
int i = 0; i < _table->size; i++) {
00101 UString::Rep *
key = _table->entries[i].key;
00102
if (
key)
00103
key->deref();
00104 }
00105 free(_table);
00106 }
00107
00108
void PropertyMap::clear()
00109 {
00110
if (!_table) {
00111
#if USE_SINGLE_ENTRY
00112
UString::Rep *
key = _singleEntry.key;
00113
if (
key) {
00114
key->deref();
00115 _singleEntry.key = 0;
00116 }
00117
#endif
00118
return;
00119 }
00120
00121
for (
int i = 0; i < _table->size; i++) {
00122 UString::Rep *
key = _table->entries[i].key;
00123
if (
key) {
00124
key->deref();
00125 _table->entries[i].key = 0;
00126 }
00127 }
00128 _table->keyCount = 0;
00129 }
00130
00131
inline int PropertyMap::hash(
const UString::Rep *s)
const
00132
{
00133
return s->hash() & _table->sizeMask;
00134 }
00135
00136
ValueImp *PropertyMap::get(
const Identifier &name,
int &attributes)
const
00137
{
00138 assert(!
name.
isNull());
00139
00140 UString::Rep *rep =
name._ustring.rep;
00141
00142
if (!_table) {
00143
#if USE_SINGLE_ENTRY
00144
UString::Rep *
key = _singleEntry.key;
00145
if (rep ==
key) {
00146 attributes = _singleEntry.attributes;
00147
return _singleEntry.value;
00148 }
00149
#endif
00150
return 0;
00151 }
00152
00153
int i = hash(rep);
00154
#if DUMP_STATISTICS
00155
++numProbes;
00156 numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
00157
#endif
00158
while (UString::Rep *
key = _table->entries[i].key) {
00159
if (rep ==
key) {
00160 attributes = _table->entries[i].attributes;
00161
return _table->entries[i].value;
00162 }
00163 i = (i + 1) & _table->sizeMask;
00164 }
00165
return 0;
00166 }
00167
00168
ValueImp *PropertyMap::get(
const Identifier &name)
const
00169
{
00170 assert(!
name.
isNull());
00171
00172 UString::Rep *rep =
name._ustring.rep;
00173
00174
if (!_table) {
00175
#if USE_SINGLE_ENTRY
00176
UString::Rep *
key = _singleEntry.key;
00177
if (rep ==
key)
00178
return _singleEntry.value;
00179
#endif
00180
return 0;
00181 }
00182
00183
int i = hash(rep);
00184
#if DUMP_STATISTICS
00185
++numProbes;
00186 numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
00187
#endif
00188
while (UString::Rep *
key = _table->entries[i].key) {
00189
if (rep ==
key)
00190
return _table->entries[i].value;
00191 i = (i + 1) & _table->sizeMask;
00192 }
00193
return 0;
00194 }
00195
00196
#if DEBUG_PROPERTIES
00197
static void printAttributes(
int attributes)
00198 {
00199
if (attributes == 0)
00200 printf (
"None ");
00201
if (attributes & ReadOnly)
00202 printf (
"ReadOnly ");
00203
if (attributes & DontEnum)
00204 printf (
"DontEnum ");
00205
if (attributes & DontDelete)
00206 printf (
"DontDelete ");
00207
if (attributes & Internal)
00208 printf (
"Internal ");
00209
if (attributes & Function)
00210 printf (
"Function ");
00211 }
00212
#endif
00213
00214
void PropertyMap::put(
const Identifier &name,
ValueImp *value,
int attributes)
00215 {
00216 assert(!
name.
isNull());
00217 assert(value != 0);
00218
00219 checkConsistency();
00220
00221 UString::Rep *rep =
name._ustring.rep;
00222
00223
#if DEBUG_PROPERTIES
00224
printf(
"adding property %s, attributes = 0x%08x (",
name.
ascii(), attributes);
00225 printAttributes(attributes);
00226 printf(
")\n");
00227
#endif
00228
00229
#if USE_SINGLE_ENTRY
00230
if (!_table) {
00231 UString::Rep *
key = _singleEntry.key;
00232
if (
key) {
00233
if (rep ==
key) {
00234 _singleEntry.value = value;
00235
return;
00236 }
00237 }
else {
00238 rep->
ref();
00239 _singleEntry.key = rep;
00240 _singleEntry.value = value;
00241 _singleEntry.attributes = attributes;
00242 checkConsistency();
00243
return;
00244 }
00245 }
00246
#endif
00247
00248
if (!_table || _table->keyCount * 2 >= _table->size)
00249 expand();
00250
00251
int i = hash(rep);
00252
#if DUMP_STATISTICS
00253
++numProbes;
00254 numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
00255
#endif
00256
while (UString::Rep *
key = _table->entries[i].key) {
00257
if (rep ==
key) {
00258
00259 _table->entries[i].value = value;
00260
00261
return;
00262 }
00263 i = (i + 1) & _table->sizeMask;
00264 }
00265
00266
00267 rep->
ref();
00268 _table->entries[i].key = rep;
00269 _table->entries[i].value = value;
00270 _table->entries[i].attributes = attributes;
00271 ++_table->keyCount;
00272
00273 checkConsistency();
00274 }
00275
00276
inline void PropertyMap::insert(UString::Rep *key,
ValueImp *value,
int attributes)
00277 {
00278 assert(_table);
00279
00280
int i = hash(key);
00281
#if DUMP_STATISTICS
00282
++numProbes;
00283 numCollisions += _table->entries[i].key && _table->entries[i].key !=
key;
00284
#endif
00285
while (_table->entries[i].key)
00286 i = (i + 1) & _table->sizeMask;
00287
00288 _table->entries[i].key =
key;
00289 _table->entries[i].value = value;
00290 _table->entries[i].attributes = attributes;
00291 }
00292
00293
void PropertyMap::expand()
00294 {
00295 checkConsistency();
00296
00297 Table *oldTable = _table;
00298
int oldTableSize = oldTable ? oldTable->size : 0;
00299
00300
int newTableSize = oldTableSize ? oldTableSize * 2 : 16;
00301 _table = (Table *)calloc(1,
sizeof(Table) + (newTableSize - 1) *
sizeof(Entry) );
00302 _table->size = newTableSize;
00303 _table->sizeMask = newTableSize - 1;
00304 _table->keyCount = oldTable ? oldTable->keyCount : 0;
00305
00306
#if USE_SINGLE_ENTRY
00307
UString::Rep *
key = _singleEntry.key;
00308
if (
key) {
00309
insert(key, _singleEntry.value, _singleEntry.attributes);
00310 _table->keyCount++;
00311 _singleEntry.key = 0;
00312 }
00313
#endif
00314
00315
for (
int i = 0; i != oldTableSize; ++i) {
00316 UString::Rep *
key = oldTable->entries[i].key;
00317
if (
key)
00318
insert(key, oldTable->entries[i].value, oldTable->entries[i].attributes);
00319 }
00320
00321 free(oldTable);
00322
00323 checkConsistency();
00324 }
00325
00326
void PropertyMap::remove(
const Identifier &name)
00327 {
00328 assert(!
name.
isNull());
00329
00330 checkConsistency();
00331
00332 UString::Rep *rep =
name._ustring.rep;
00333
00334 UString::Rep *
key;
00335
00336
if (!_table) {
00337
#if USE_SINGLE_ENTRY
00338
key = _singleEntry.key;
00339
if (rep ==
key) {
00340
key->deref();
00341 _singleEntry.key = 0;
00342 checkConsistency();
00343 }
00344
#endif
00345
return;
00346 }
00347
00348
00349
int i = hash(rep);
00350
#if DUMP_STATISTICS
00351
++numProbes;
00352 numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
00353
#endif
00354
while ((
key = _table->entries[i].key)) {
00355
if (rep ==
key)
00356
break;
00357 i = (i + 1) & _table->sizeMask;
00358 }
00359
if (!
key)
00360
return;
00361
00362
00363
key->deref();
00364 _table->entries[i].key = 0;
00365 assert(_table->keyCount >= 1);
00366 --_table->keyCount;
00367
00368
00369
while (1) {
00370 i = (i + 1) & _table->sizeMask;
00371
key = _table->entries[i].key;
00372
if (!
key)
00373
break;
00374 _table->entries[i].key = 0;
00375
insert(key, _table->entries[i].value, _table->entries[i].attributes);
00376 }
00377
00378 checkConsistency();
00379 }
00380
00381
void PropertyMap::mark()
const
00382
{
00383
if (!_table) {
00384
#if USE_SINGLE_ENTRY
00385
if (_singleEntry.key) {
00386
ValueImp *v = _singleEntry.value;
00387
if (!v->
marked())
00388 v->
mark();
00389 }
00390
#endif
00391
return;
00392 }
00393
00394
for (
int i = 0; i != _table->size; ++i) {
00395
if (_table->entries[i].key) {
00396
ValueImp *v = _table->entries[i].value;
00397
if (!v->
marked())
00398 v->
mark();
00399 }
00400 }
00401 }
00402
00403
void PropertyMap::addEnumerablesToReferenceList(ReferenceList &list,
const Object &base)
const
00404
{
00405
if (!_table) {
00406
#if USE_SINGLE_ENTRY
00407
UString::Rep *
key = _singleEntry.key;
00408
if (
key && !(_singleEntry.attributes & DontEnum))
00409 list.append(Reference(base, Identifier(key)));
00410
#endif
00411
return;
00412 }
00413
00414
for (
int i = 0; i != _table->size; ++i) {
00415 UString::Rep *
key = _table->entries[i].key;
00416
if (
key && !(_table->entries[i].attributes & DontEnum))
00417 list.append(Reference(base, Identifier(key)));
00418 }
00419 }
00420
00421
void PropertyMap::addSparseArrayPropertiesToReferenceList(ReferenceList &list,
const Object &base)
const
00422
{
00423
if (!_table) {
00424
#if USE_SINGLE_ENTRY
00425
UString::Rep *
key = _singleEntry.key;
00426
if (
key) {
00427
UString k(key);
00428
bool fitsInULong;
00429
unsigned long i = k.toULong(&fitsInULong);
00430
if (fitsInULong && i <= 0xFFFFFFFFU)
00431 list.append(Reference(base, Identifier(key)));
00432 }
00433
#endif
00434
return;
00435 }
00436
00437
for (
int i = 0; i != _table->size; ++i) {
00438 UString::Rep *
key = _table->entries[i].key;
00439
if (
key) {
00440
UString k(key);
00441
bool fitsInULong;
00442
unsigned long i = k.toULong(&fitsInULong);
00443
if (fitsInULong && i <= 0xFFFFFFFFU)
00444 list.append(Reference(base, Identifier(key)));
00445 }
00446 }
00447 }
00448
00449
void PropertyMap::save(SavedProperties &p)
const
00450
{
00451
int count = 0;
00452
00453
if (!_table) {
00454
#if USE_SINGLE_ENTRY
00455
if (_singleEntry.key && !(_singleEntry.attributes & (ReadOnly | DontEnum | Function)))
00456 ++count;
00457
#endif
00458
}
else {
00459
for (
int i = 0; i != _table->size; ++i)
00460
if (_table->entries[i].key && !(_table->entries[i].attributes & (ReadOnly | DontEnum | Function)))
00461 ++count;
00462 }
00463
00464
delete [] p._properties;
00465
00466 p._count = count;
00467
00468
if (count == 0) {
00469 p._properties = 0;
00470
return;
00471 }
00472
00473 p._properties =
new SavedProperty [count];
00474
00475 SavedProperty *prop = p._properties;
00476
00477
if (!_table) {
00478
#if USE_SINGLE_ENTRY
00479
if (_singleEntry.key && !(_singleEntry.attributes & (ReadOnly | DontEnum | Function))) {
00480 prop->key = Identifier(_singleEntry.key);
00481 prop->value =
Value(_singleEntry.value);
00482 prop->attributes = _singleEntry.attributes;
00483 ++prop;
00484 }
00485
#endif
00486
}
else {
00487
for (
int i = 0; i != _table->size; ++i) {
00488
if (_table->entries[i].key && !(_table->entries[i].attributes & (ReadOnly | DontEnum | Function))) {
00489 prop->key = Identifier(_table->entries[i].key);
00490 prop->value =
Value(_table->entries[i].value);
00491 prop->attributes = _table->entries[i].attributes;
00492 ++prop;
00493 }
00494 }
00495 }
00496 }
00497
00498
void PropertyMap::restore(
const SavedProperties &p)
00499 {
00500
for (
int i = 0; i != p._count; ++i)
00501
put(p._properties[i].key, p._properties[i].value.imp(), p._properties[i].attributes);
00502 }
00503
00504
#if DO_CONSISTENCY_CHECK
00505
00506
void PropertyMap::checkConsistency()
00507 {
00508
if (!_table)
00509
return;
00510
00511
int count = 0;
00512
for (
int j = 0; j != _table->size; ++j) {
00513 UString::Rep *rep = _table->entries[j].key;
00514
if (!rep)
00515
continue;
00516
int i = hash(rep);
00517
while (UString::Rep *
key = _table->entries[i].key) {
00518
if (rep ==
key)
00519
break;
00520 i = (i + 1) & _table->sizeMask;
00521 }
00522 assert(i == j);
00523 count++;
00524 }
00525 assert(count == _table->keyCount);
00526 assert(_table->size >= 16);
00527 assert(_table->sizeMask);
00528 assert(_table->size == _table->sizeMask + 1);
00529 }
00530
00531
#endif // DO_CONSISTENCY_CHECK
00532
00533 }