property_map.cpp
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 }
This file is part of the documentation for kjs Library Version 3.4.3.