interpreter_map.cpp [plain text]
#include "interpreter_map.h"
namespace KJS {
const int _minTableSize = 64;
InterpreterMap::KeyValue *InterpreterMap::_table;
int InterpreterMap::_tableSize;
int InterpreterMap::_tableSizeMask;
int InterpreterMap::_keyCount;
InterpreterImp * InterpreterMap::getInterpreterForGlobalObject(ObjectImp *global)
{
if (!_table)
expand();
unsigned hash = computeHash(global);
int i = hash & _tableSizeMask;
#if DUMP_STATISTICS
++numProbes;
numCollisions += _table[i].key && _table[i].key != global;
#endif
while (ObjectImp *key = _table[i].key) {
if (key == global) {
return _table[i].value;
}
i = (i + 1) & _tableSizeMask;
}
return 0;
}
void InterpreterMap::setInterpreterForGlobalObject(InterpreterImp *interpreter, ObjectImp *global)
{
if (!_table)
expand();
unsigned hash = computeHash(global);
int i = hash & _tableSizeMask;
#if DUMP_STATISTICS
++numProbes;
numCollisions += _table[i].key && _table[i].key != global;
#endif
while (ObjectImp *key = _table[i].key) {
if (key == global) {
_table[i].value = interpreter;
return;
}
i = (i + 1) & _tableSizeMask;
}
_table[i].key = global;
_table[i].value = interpreter;
++_keyCount;
if (_keyCount * 2 >= _tableSize)
expand();
}
inline void InterpreterMap::insert(InterpreterImp *interpreter, ObjectImp *global)
{
unsigned hash = computeHash(global);
int i = hash & _tableSizeMask;
#if DUMP_STATISTICS
++numProbes;
numCollisions += _table[i] != 0;
#endif
while (_table[i].key)
i = (i + 1) & _tableSizeMask;
_table[i].key = global;
_table[i].value = interpreter;
}
void InterpreterMap::removeInterpreterForGlobalObject(ObjectImp *global)
{
unsigned hash = computeHash(global);
ObjectImp *key;
int i = hash & _tableSizeMask;
#if DUMP_STATISTICS
++numProbes;
numCollisions += _table[i].key && _table[i].key == global;
#endif
while ((key = _table[i].key)) {
if (key == global)
break;
i = (i + 1) & _tableSizeMask;
}
if (!key)
return;
_table[i].key = 0;
_table[i].value = 0;
--_keyCount;
if (_keyCount * 6 < _tableSize && _tableSize > _minTableSize) {
shrink();
return;
}
while (1) {
i = (i + 1) & _tableSizeMask;
key = _table[i].key;
InterpreterImp *value = _table[i].value;
if (!key)
break;
_table[i].key = 0;
_table[i].value = 0;
insert(value,key);
}
}
void InterpreterMap::expand()
{
rehash(_tableSize == 0 ? _minTableSize : _tableSize * 2);
}
void InterpreterMap::shrink()
{
rehash(_tableSize / 2);
}
void InterpreterMap::rehash(int newTableSize)
{
int oldTableSize = _tableSize;
KeyValue *oldTable = _table;
_tableSize = newTableSize;
_tableSizeMask = newTableSize - 1;
_table = (KeyValue *)calloc(newTableSize, sizeof(KeyValue));
for (int i = 0; i != oldTableSize; ++i)
if (oldTable[i].key)
insert(oldTable[i].value, oldTable[i].key);
free(oldTable);
}
const unsigned PHI = 0x9e3779b9U;
unsigned InterpreterMap::computeHash(ObjectImp *pointer)
{
int length = sizeof(ObjectImp *);
char s[sizeof(ObjectImp *)];
memcpy((void *)s, (void *)&pointer, sizeof(ObjectImp *));
unsigned h = PHI;
h += length;
h += (h << 10);
h ^= (h << 6);
for (int i = 0; i < length; i++) {
h += (unsigned char)s[i];
h += (h << 10);
h ^= (h << 6);
}
h += (h << 3);
h ^= (h >> 11);
h += (h << 15);
if (h == 0)
h = 0x80000000;
return h;
}
};