property_map.cpp00001
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
00067
00068 int *hashToIndex;
00069
00070
00071 int indexCount;
00072
00073 PropertyMapHashTableEntry entries[1];
00074 };
00075
00076 class SavedProperty {
00077 public:
00078 Identifier key;
00079 Value value;
00080 int attributes;
00081 };
00082
00083 SavedProperties::SavedProperties() : _count(0), _properties(0) { }
00084
00085 SavedProperties::~SavedProperties()
00086 {
00087 delete [] _properties;
00088 }
00089
00090
00091
00092 PropertyMap::PropertyMap() : _table(0)
00093 {
00094 }
00095
00096 PropertyMap::~PropertyMap()
00097 {
00098 if (!_table) {
00099 #if USE_SINGLE_ENTRY
00100 UString::Rep *key = _singleEntry.key;
00101 if (key)
00102 key->deref();
00103 #endif
00104 return;
00105 }
00106
00107 for (int i = 0; i < _table->size; i++) {
00108 UString::Rep *key = _table->entries[i].key;
00109 if (key)
00110 key->deref();
00111 }
00112
00113 if (_table)
00114 delete [] _table->hashToIndex;
00115
00116 free(_table);
00117 }
00118
00119 void PropertyMap::clear()
00120 {
00121 if (!_table) {
00122 #if USE_SINGLE_ENTRY
00123 UString::Rep *key = _singleEntry.key;
00124 if (key) {
00125 key->deref();
00126 _singleEntry.key = 0;
00127 }
00128 #endif
00129 return;
00130 }
00131
00132 for (int i = 0; i < _table->size; i++) {
00133 UString::Rep *key = _table->entries[i].key;
00134 if (key) {
00135 key->deref();
00136 _table->entries[i].key = 0;
00137 }
00138 }
00139 _table->keyCount = 0;
00140 }
00141
00142 inline int PropertyMap::hash(const UString::Rep *s) const
00143 {
00144 return s->hash() & _table->sizeMask;
00145 }
00146
00147 ValueImp *PropertyMap::get(const Identifier &name, int &attributes) const
00148 {
00149 assert(!name.isNull());
00150
00151 UString::Rep *rep = name._ustring.rep;
00152
00153 if (!_table) {
00154 #if USE_SINGLE_ENTRY
00155 UString::Rep *key = _singleEntry.key;
00156 if (rep == key) {
00157 attributes = _singleEntry.attributes;
00158 return _singleEntry.value;
00159 }
00160 #endif
00161 return 0;
00162 }
00163
00164 int i = hash(rep);
00165 #if DUMP_STATISTICS
00166 ++numProbes;
00167 numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
00168 #endif
00169 while (UString::Rep *key = _table->entries[i].key) {
00170 if (rep == key) {
00171 attributes = _table->entries[i].attributes;
00172 return _table->entries[i].value;
00173 }
00174 i = (i + 1) & _table->sizeMask;
00175 }
00176 return 0;
00177 }
00178
00179 ValueImp *PropertyMap::get(const Identifier &name) const
00180 {
00181 assert(!name.isNull());
00182
00183 UString::Rep *rep = name._ustring.rep;
00184
00185 if (!_table) {
00186 #if USE_SINGLE_ENTRY
00187 UString::Rep *key = _singleEntry.key;
00188 if (rep == key)
00189 return _singleEntry.value;
00190 #endif
00191 return 0;
00192 }
00193
00194 int i = hash(rep);
00195 #if DUMP_STATISTICS
00196 ++numProbes;
00197 numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
00198 #endif
00199 while (UString::Rep *key = _table->entries[i].key) {
00200 if (rep == key)
00201 return _table->entries[i].value;
00202 i = (i + 1) & _table->sizeMask;
00203 }
00204 return 0;
00205 }
00206
00207 #if DEBUG_PROPERTIES
00208 static void printAttributes(int attributes)
00209 {
00210 if (attributes == 0)
00211 printf ("None ");
00212 if (attributes & ReadOnly)
00213 printf ("ReadOnly ");
00214 if (attributes & DontEnum)
00215 printf ("DontEnum ");
00216 if (attributes & DontDelete)
00217 printf ("DontDelete ");
00218 if (attributes & Internal)
00219 printf ("Internal ");
00220 if (attributes & Function)
00221 printf ("Function ");
00222 }
00223 #endif
00224
00225 void PropertyMap::put(const Identifier &name, ValueImp *value, int attributes)
00226 {
00227 assert(!name.isNull());
00228 assert(value != 0);
00229
00230 #if DO_CONSISTENCY_CHECK // speed, why call a stub if we dont need to??
00231 checkConsistency();
00232 #endif
00233
00234 UString::Rep *rep = name._ustring.rep;
00235
00236 #if DEBUG_PROPERTIES
00237 printf("adding property %s, attributes = 0x%08x (", name.ascii(), attributes);
00238 printAttributes(attributes);
00239 printf(")\n");
00240 #endif
00241
00242 #if USE_SINGLE_ENTRY
00243 if (!_table) {
00244 UString::Rep *key = _singleEntry.key;
00245 if (key) {
00246 if (rep == key) {
00247 _singleEntry.value = value;
00248 return;
00249 }
00250 } else {
00251 rep->ref();
00252 _singleEntry.key = rep;
00253 _singleEntry.value = value;
00254 _singleEntry.attributes = attributes;
00255 checkConsistency();
00256 return;
00257 }
00258 }
00259 #endif
00260 if (!_table || _table->keyCount * 2 >= _table->size)
00261 expand();
00262 int i = hash(rep);
00263 #if DUMP_STATISTICS
00264 ++numProbes;
00265 numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
00266 #endif
00267 while (UString::Rep *key = _table->entries[i].key) {
00268 if (rep == key) {
00269
00270 _table->entries[i].value = value;
00271
00272 return;
00273 }
00274 i = (i + 1) & _table->sizeMask;
00275 }
00276
00277
00278 rep->ref();
00279 _table->entries[i].key = rep;
00280 _table->entries[i].value = value;
00281 _table->entries[i].attributes = attributes;
00282 ++_table->keyCount;
00283
00284
00285 _table->indexCount++;
00286 _table->hashToIndex[i] = _table->indexCount;
00287
00288 #if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to??
00289 checkConsistency();
00290 #endif
00291 }
00292
00293 inline void PropertyMap::insert(UString::Rep *key, ValueImp *value, int attributes)
00294 {
00295 assert(_table);
00296
00297 int i = hash(key);
00298 #if DUMP_STATISTICS
00299 ++numProbes;
00300 numCollisions += _table->entries[i].key && _table->entries[i].key != key;
00301 #endif
00302 while (_table->entries[i].key)
00303 i = (i + 1) & _table->sizeMask;
00304
00305 _table->entries[i].key = key;
00306 _table->entries[i].value = value;
00307 _table->entries[i].attributes = attributes;
00308 }
00309
00310 void PropertyMap::expand()
00311 {
00312 #if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to??
00313 checkConsistency();
00314 #endif
00315 Table *oldTable = _table;
00316
00317 int oldTableSize = oldTable ? oldTable->size : 0;
00318
00319 int newTableSize = oldTableSize ? oldTableSize * 2 : 16;
00320
00321
00322
00323
00324 _table = (Table *)calloc(1, sizeof(Table) + ((newTableSize - 1) * sizeof(Entry)) );
00325
00326 int *p = new int[newTableSize];
00327 for (int i = 0; i < newTableSize; i++)
00328 p[i] = 0;
00329
00330 _table->hashToIndex = p;
00331
00332 _table->size = newTableSize;
00333
00334 _table->sizeMask = newTableSize - 1;
00335
00336 _table->keyCount = oldTable ? oldTable->keyCount : 0;
00337
00338 _table->indexCount = oldTable ? oldTable->indexCount : 0;
00339
00340 #if USE_SINGLE_ENTRY
00341 UString::Rep *key = _singleEntry.key;
00342 if (key) {
00343 insert(key, _singleEntry.value, _singleEntry.attributes);
00344 _table->keyCount++;
00345 _singleEntry.key = 0;
00346
00347
00348
00349 int k = hash(key);
00350 #if DUMP_STATISTICS
00351 ++numProbes;
00352 numCollisions += _table->entries[k].key && _table->entries[k].key != key;
00353 #endif
00354 while (UString::Rep *newKey = _table->entries[k].key) {
00355 if (key == newKey)
00356 break;
00357 k = (k + 1) & _table->sizeMask;
00358 }
00359 _table->indexCount++;
00360 _table->hashToIndex[k] = _table->indexCount;
00361 }
00362 #endif
00363
00364 for (int i = 0; i != oldTableSize; ++i) {
00365 UString::Rep *key = oldTable->entries[i].key;
00366 if (key) {
00367 insert(key, oldTable->entries[i].value, oldTable->entries[i].attributes);
00368
00369
00370
00371 int k = hash(key);
00372 #if DUMP_STATISTICS
00373 ++numProbes;
00374 numCollisions += _table->entries[k].key && _table->entries[k].key != key;
00375 #endif
00376 while (UString::Rep *newKey = _table->entries[k].key) {
00377 if (key == newKey)
00378 break;
00379 k = (k + 1) & _table->sizeMask;
00380 }
00381
00382 _table->hashToIndex[k] = oldTable->hashToIndex[i];
00383 }
00384 }
00385
00386 if (oldTable){
00387 delete [] oldTable->hashToIndex;
00388 }
00389 free(oldTable);
00390
00391 #if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to??
00392 checkConsistency();
00393 #endif
00394 }
00395
00396 void PropertyMap::remove(const Identifier &name)
00397 {
00398 assert(!name.isNull());
00399
00400 #if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to??
00401 checkConsistency();
00402 #endif
00403
00404 UString::Rep *rep = name._ustring.rep;
00405
00406 UString::Rep *key;
00407
00408 if (!_table) {
00409 #if USE_SINGLE_ENTRY
00410 key = _singleEntry.key;
00411 if (rep == key) {
00412 key->deref();
00413 _singleEntry.key = 0;
00414 checkConsistency();
00415 }
00416 #endif
00417 return;
00418 }
00419
00420
00421 int i = hash(rep);
00422 #if DUMP_STATISTICS
00423 ++numProbes;
00424 numCollisions += _table->entries[i].key && _table->entries[i].key != rep;
00425 #endif
00426 while ((key = _table->entries[i].key)) {
00427 if (rep == key)
00428 break;
00429 i = (i + 1) & _table->sizeMask;
00430 }
00431
00432 if (!key)
00433 return;
00434
00435
00436 key->deref();
00437 _table->entries[i].key = 0;
00438 assert(_table->keyCount >= 1);
00439 --_table->keyCount;
00440
00441
00442 while (1) {
00443 i = (i + 1) & _table->sizeMask;
00444 key = _table->entries[i].key;
00445 if (!key)
00446 break;
00447
00448 _table->entries[i].key = 0;
00449
00450 insert(key, _table->entries[i].value, _table->entries[i].attributes);
00451
00452
00453 int k = hash(key);
00454 #if DUMP_STATISTICS
00455 ++numProbes;
00456 numCollisions += _table->entries[k].key && _table->entries[k].key != key;
00457 #endif
00458 while (UString::Rep *newKey = _table->entries[k].key) {
00459 if (key == newKey)
00460 break;
00461 k = (k + 1) & _table->sizeMask;
00462 }
00463
00464
00465 _table->hashToIndex[k] = _table->hashToIndex[i];
00466 }
00467
00468 #if DO_CONSISTENCY_CHECK// speed, why call a stub if we dont need to??
00469 checkConsistency();
00470 #endif
00471 }
00472
00473 void PropertyMap::mark() const
00474 {
00475 if (!_table) {
00476 #if USE_SINGLE_ENTRY
00477 if (_singleEntry.key) {
00478 ValueImp *v = _singleEntry.value;
00479 if (!v->marked())
00480 v->mark();
00481 }
00482 #endif
00483 return;
00484 }
00485
00486 for (int i = 0; i != _table->size; ++i) {
00487 if (_table->entries[i].key) {
00488 ValueImp *v = _table->entries[i].value;
00489 if (!v->marked())
00490 v->mark();
00491 }
00492 }
00493 }
00494
00495 void PropertyMap::addEnumerablesToReferenceList(ReferenceList &list, const Object &base) const
00496 {
00497 if (!_table) {
00498 #if USE_SINGLE_ENTRY
00499 UString::Rep *key = _singleEntry.key;
00500 if (key && !(_singleEntry.attributes & DontEnum))
00501 list.append(Reference(base, Identifier(key)));
00502 #endif
00503 return;
00504 }
00505
00506
00507 int indexSize = _table->indexCount + 1;
00508 UString::Rep **allKeys = new UString::Rep*[indexSize];
00509
00510 for (int i = 0; i < indexSize; i++)
00511 allKeys[i] = NULL;
00512
00513
00514
00515
00516 int size = _table->size;
00517 Entry *entries = _table->entries;
00518 for (int i = 0; i != size; ++i) {
00519 if (entries[i].key && !(entries[i].attributes & DontEnum)) {
00520 int idx = _table->hashToIndex[i];
00521 if (idx) {
00522 allKeys[idx] = entries[i].key;
00523 } else {
00524
00525 assert(0==1);
00526 }
00527 }
00528 }
00529
00530 for (int i = 0; i < indexSize; ++i) {
00531 if (allKeys[i] != NULL){
00532 list.append(Reference(base, Identifier(allKeys[i])));
00533 }
00534 allKeys[i] = NULL;
00535 }
00536
00537
00538 delete [] allKeys;
00539 }
00540
00541 void PropertyMap::addSparseArrayPropertiesToReferenceList(ReferenceList &list, const Object &base) const
00542 {
00543
00544
00545 if (!_table) {
00546 #if USE_SINGLE_ENTRY
00547 UString::Rep *key = _singleEntry.key;
00548 if (key) {
00549 UString k(key);
00550 bool fitsInULong;
00551 unsigned long i = k.toULong(&fitsInULong);
00552 if (fitsInULong && i <= 0xFFFFFFFFU)
00553 list.append(Reference(base, Identifier(key)));
00554 }
00555 #endif
00556 return;
00557 }
00558
00559 for (int i = 0; i != _table->size; ++i) {
00560 UString::Rep *key = _table->entries[i].key;
00561 if (key) {
00562 UString k(key);
00563 bool fitsInULong;
00564 unsigned long i = k.toULong(&fitsInULong);
00565 if (fitsInULong && i <= 0xFFFFFFFFU)
00566 list.append(Reference(base, Identifier(key)));
00567 }
00568 }
00569 }
00570
00571 void PropertyMap::save(SavedProperties &p) const
00572 {
00573 int count = 0;
00574
00575 if (!_table) {
00576 #if USE_SINGLE_ENTRY
00577 if (_singleEntry.key && !(_singleEntry.attributes & (ReadOnly | DontEnum | Function)))
00578 ++count;
00579 #endif
00580 } else {
00581 for (int i = 0; i != _table->size; ++i)
00582 if (_table->entries[i].key && !(_table->entries[i].attributes & (ReadOnly | DontEnum | Function)))
00583 ++count;
00584 }
00585
00586 delete [] p._properties;
00587
00588 p._count = count;
00589
00590 if (count == 0) {
00591 p._properties = 0;
00592 return;
00593 }
00594
00595 p._properties = new SavedProperty [count];
00596
00597 SavedProperty *prop = p._properties;
00598
00599 if (!_table) {
00600 #if USE_SINGLE_ENTRY
00601 if (_singleEntry.key && !(_singleEntry.attributes & (ReadOnly | DontEnum | Function))) {
00602 prop->key = Identifier(_singleEntry.key);
00603 prop->value = Value(_singleEntry.value);
00604 prop->attributes = _singleEntry.attributes;
00605 ++prop;
00606 }
00607 #endif
00608 } else {
00609 for (int i = 0; i != _table->size; ++i) {
00610 if (_table->entries[i].key && !(_table->entries[i].attributes & (ReadOnly | DontEnum | Function))) {
00611 prop->key = Identifier(_table->entries[i].key);
00612 prop->value = Value(_table->entries[i].value);
00613 prop->attributes = _table->entries[i].attributes;
00614 ++prop;
00615 }
00616 }
00617 }
00618 }
00619
00620 void PropertyMap::restore(const SavedProperties &p)
00621 {
00622 for (int i = 0; i != p._count; ++i)
00623 put(p._properties[i].key, p._properties[i].value.imp(), p._properties[i].attributes);
00624 }
00625
00626 #if DO_CONSISTENCY_CHECK
00627
00628 void PropertyMap::checkConsistency()
00629 {
00630 if (!_table)
00631 return;
00632
00633 int count = 0;
00634 for (int j = 0; j != _table->size; ++j) {
00635 UString::Rep *rep = _table->entries[j].key;
00636 if (!rep)
00637 continue;
00638 int i = hash(rep);
00639 while (UString::Rep *key = _table->entries[i].key) {
00640 if (rep == key)
00641 break;
00642 i = (i + 1) & _table->sizeMask;
00643 }
00644 assert(i == j);
00645 assert(_table->hashToIndex[i] > 0);
00646 count++;
00647 }
00648 assert(count == _table->keyCount);
00649 assert(_table->size >= 16);
00650 assert(_table->sizeMask);
00651 assert(_table->size == _table->sizeMask + 1);
00652 }
00653
00654 #endif // DO_CONSISTENCY_CHECK
00655
00656 }
|