dom_atomicstring.cpp [plain text]
#if APPLE_CHANGES
#define AVOID_STATIC_CONSTRUCTORS 1
#endif
#if AVOID_STATIC_CONSTRUCTORS
#define KHTML_ATOMICSTRING_HIDE_GLOBALS 1
#endif
#include "dom_atomicstring.h"
#include "xml/dom_stringimpl.h"
namespace DOM {
#define DUMP_STATISTICS 0
#if DUMP_STATISTICS
static int numProbes;
static int numCollisions;
struct AtomicStringStatisticsExitLogger { ~AtomicStringStatisticsExitLogger(); };
static AtomicStringStatisticsExitLogger logger;
AtomicStringStatisticsExitLogger::~AtomicStringStatisticsExitLogger()
{
printf("\nDOM::AtomicString statistics\n\n");
printf("%d probes\n", numProbes);
printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
}
#endif
const int _minTableSize = 64;
DOMStringImpl **AtomicString::_table;
int AtomicString::_tableSize;
int AtomicString::_tableSizeMask;
int AtomicString::_keyCount;
bool AtomicString::equal(DOMStringImpl *r, const char *s)
{
if (!r && !s) return true;
if (!r || !s) return false;
int length = r->l;
const QChar *d = r->s;
for (int i = 0; i != length; ++i)
if (d[i] != s[i])
return false;
return s[length] == 0;
}
bool AtomicString::equal(DOMStringImpl *r, const QChar *s, uint length)
{
if (!r && !s) return true;
if (!r || !s) return false;
if (r->l != length)
return false;
const QChar *d = r->s;
for (uint i = 0; i != length; ++i)
if (d[i] != s[i])
return false;
return true;
}
bool AtomicString::equal(DOMStringImpl *r, DOMStringImpl *b)
{
if (r == b) return true;
if (!r || !b) return false;
uint length = r->l;
if (length != b->l)
return false;
const QChar *d = r->s;
const QChar *s = b->s;
for (uint i = 0; i != length; ++i)
if (d[i] != s[i])
return false;
return true;
}
DOMStringImpl *AtomicString::add(const char *c)
{
if (!c)
return 0;
int length = strlen(c);
if (length == 0)
return DOMStringImpl::empty();
if (!_table)
expand();
unsigned hash = DOMStringImpl::computeHash(c);
int i = hash & _tableSizeMask;
#if DUMP_STATISTICS
++numProbes;
numCollisions += _table[i] && !equal(_table[i], c);
#endif
while (DOMStringImpl *key = _table[i]) {
if (equal(key, c))
return key;
i = (i + 1) & _tableSizeMask;
}
DOMStringImpl *r = new DOMStringImpl(c, length);
r->_hash = hash;
r->_inTable = true;
_table[i] = r;
++_keyCount;
if (_keyCount * 2 >= _tableSize)
expand();
return r;
}
DOMStringImpl *AtomicString::add(const QChar *s, int length)
{
if (!s)
return 0;
if (length == 0)
return DOMStringImpl::empty();
if (!_table)
expand();
unsigned hash = DOMStringImpl::computeHash(s, length);
int i = hash & _tableSizeMask;
#if DUMP_STATISTICS
++numProbes;
numCollisions += _table[i] && !equal(_table[i], s, length);
#endif
while (DOMStringImpl *key = _table[i]) {
if (equal(key, s, length))
return key;
i = (i + 1) & _tableSizeMask;
}
DOMStringImpl *r = new DOMStringImpl(s, length);
r->_hash = hash;
r->_inTable = true;
_table[i] = r;
++_keyCount;
if (_keyCount * 2 >= _tableSize)
expand();
return r;
}
DOMStringImpl *AtomicString::add(DOMStringImpl *r)
{
if (!r || r->_inTable)
return r;
if (r->l == 0)
return DOMStringImpl::empty();
if (!_table)
expand();
unsigned hash = r->hash();
int i = hash & _tableSizeMask;
#if DUMP_STATISTICS
++numProbes;
numCollisions += _table[i] && !equal(_table[i], r);
#endif
while (DOMStringImpl *key = _table[i]) {
if (equal(key, r)) {
return key;
}
i = (i + 1) & _tableSizeMask;
}
r->_inTable = true;
_table[i] = r;
++_keyCount;
if (_keyCount * 2 >= _tableSize)
expand();
return r;
}
inline void AtomicString::insert(DOMStringImpl *key)
{
unsigned hash = key->hash();
int i = hash & _tableSizeMask;
#if DUMP_STATISTICS
++numProbes;
numCollisions += _table[i] != 0;
#endif
while (_table[i])
i = (i + 1) & _tableSizeMask;
_table[i] = key;
}
void AtomicString::remove(DOMStringImpl *r)
{
unsigned hash = r->_hash;
DOMStringImpl *key;
int i = hash & _tableSizeMask;
#if DUMP_STATISTICS
++numProbes;
numCollisions += _table[i] && equal(_table[i], r);
#endif
while ((key = _table[i])) {
if (key == r)
break;
i = (i + 1) & _tableSizeMask;
}
if (!key)
return;
_table[i] = 0;
--_keyCount;
if (_keyCount * 6 < _tableSize && _tableSize > _minTableSize) {
shrink();
return;
}
while (1) {
i = (i + 1) & _tableSizeMask;
key = _table[i];
if (!key)
break;
_table[i] = 0;
insert(key);
}
}
void AtomicString::expand()
{
rehash(_tableSize == 0 ? _minTableSize : _tableSize * 2);
}
void AtomicString::shrink()
{
rehash(_tableSize / 2);
}
void AtomicString::rehash(int newTableSize)
{
int oldTableSize = _tableSize;
DOMStringImpl **oldTable = _table;
_tableSize = newTableSize;
_tableSizeMask = newTableSize - 1;
_table = (DOMStringImpl **)calloc(newTableSize, sizeof(DOMStringImpl *));
for (int i = 0; i != oldTableSize; ++i)
if (DOMStringImpl *key = oldTable[i])
insert(key);
free(oldTable);
}
#if !AVOID_STATIC_CONSTRUCTORS
#define DEFINE_GLOBAL(name, string) extern const AtomicString name ## Atom(string);
extern const AtomicString nullAtom;
extern const AtomicString emptyAtom;
#else
#define DEFINE_GLOBAL(name, string) \
void * name ## Atom[(sizeof(AtomicString) + sizeof(void *) - 1) / sizeof(void *)];
DEFINE_GLOBAL(null, ignored)
DEFINE_GLOBAL(empty, ignored)
#endif
#define CALL_DEFINE_GLOBAL(name) DEFINE_GLOBAL(name, #name)
KHTML_ATOMICSTRING_EACH_GLOBAL(CALL_DEFINE_GLOBAL)
void AtomicString::init()
{
#if AVOID_STATIC_CONSTRUCTORS
static bool initialized;
if (!initialized) {
new (&nullAtom) AtomicString;
new (&emptyAtom) AtomicString("");
#define PLACEMENT_NEW_GLOBAL(name, string) new (&name ## PropertyName) AtomicString(string);
#define CALL_PLACEMENT_NEW_GLOBAL(name) PLACEMENT_NEW_GLOBAL(name, #name)
KHTML_ATOMICSTRING_EACH_GLOBAL(CALL_PLACEMENT_NEW_GLOBAL)
initialized = true;
}
#endif
}
bool operator==(const AtomicString &a, const DOMString &b)
{
return a.domString() == b;
}
bool equalsIgnoreCase(const AtomicString &as, const DOMString &bs)
{
return !strcasecmp(as.domString(), bs);
}
bool equalsIgnoreCase(const AtomicString &as, const AtomicString &bs)
{
if (as == bs)
return true;
return !strcasecmp(as.domString(), bs.domString());
}
}