From de7d66ba0295eba73d509e671fdda69a9bef39a6 Mon Sep 17 00:00:00 2001 From: Lars Knoll Date: Thu, 27 Jun 2013 19:57:46 +0200 Subject: [PATCH] Convert IdentifierHash to be template based Make it a template based class, so we can store more then just integers here and replace more StringHash'es with it. Change-Id: I21442d13c6260f184bc7b63a8a58e826699f0c83 Reviewed-by: Simon Hausmann --- src/qml/qml/qqmlcompiler.cpp | 2 +- src/qml/qml/qqmlcompiler_p.h | 2 +- src/qml/qml/qqmlcontext.cpp | 6 +- src/qml/qml/qqmlcontext_p.h | 4 +- src/qml/qml/v4/qv4identifier.cpp | 69 +++++-------- src/qml/qml/v4/qv4identifier_p.h | 195 +++++++++++++++++++++++++----------- src/qml/qml/v4/qv4internalclass.cpp | 8 +- 7 files changed, 173 insertions(+), 113 deletions(-) diff --git a/src/qml/qml/qqmlcompiler.cpp b/src/qml/qml/qqmlcompiler.cpp index 55212e5..841ad7a 100644 --- a/src/qml/qml/qqmlcompiler.cpp +++ b/src/qml/qml/qqmlcompiler.cpp @@ -3554,7 +3554,7 @@ int QQmlCompiler::genContextCache() if (compileState->ids.count() == 0) return -1; - QV4::IdentifierIntHash cache(QV8Engine::getV4(engine->handle())); + QV4::IdentifierHash cache(QV8Engine::getV4(engine->handle())); cache.reserve(compileState->ids.count()); for (Object *o = compileState->ids.first(); o; o = compileState->ids.next(o)) cache.add(o->id, o->idIndex); diff --git a/src/qml/qml/qqmlcompiler_p.h b/src/qml/qml/qqmlcompiler_p.h index 55e055e..6158ec3 100644 --- a/src/qml/qml/qqmlcompiler_p.h +++ b/src/qml/qml/qqmlcompiler_p.h @@ -121,7 +121,7 @@ public: QList datas; QByteArray bytecode; QList propertyCaches; - QList contextCaches; + QList > contextCaches; QList scripts; QList urls; diff --git a/src/qml/qml/qqmlcontext.cpp b/src/qml/qml/qqmlcontext.cpp index 684ac9e..55cfbc0 100644 --- a/src/qml/qml/qqmlcontext.cpp +++ b/src/qml/qml/qqmlcontext.cpp @@ -313,7 +313,7 @@ void QQmlContext::setContextProperty(const QString &name, const QVariant &value) } if (data->propertyNames.isEmpty()) - data->propertyNames = QV4::IdentifierIntHash(QV8Engine::getV4(engine()->handle())); + data->propertyNames = QV4::IdentifierHash(QV8Engine::getV4(engine()->handle())); int idx = data->propertyNames.value(name); if (idx == -1) { @@ -351,7 +351,7 @@ void QQmlContext::setContextProperty(const QString &name, QObject *value) } if (data->propertyNames.isEmpty()) - data->propertyNames = QV4::IdentifierIntHash(QV8Engine::getV4(engine()->handle())); + data->propertyNames = QV4::IdentifierHash(QV8Engine::getV4(engine()->handle())); int idx = data->propertyNames.value(name); if (idx == -1) { @@ -770,7 +770,7 @@ void QQmlContextData::setIdProperty(int idx, QObject *obj) idValues[idx].context = this; } -void QQmlContextData::setIdPropertyData(const QV4::IdentifierIntHash &data) +void QQmlContextData::setIdPropertyData(const QV4::IdentifierHash &data) { Q_ASSERT(propertyNames.isEmpty()); propertyNames = data; diff --git a/src/qml/qml/qqmlcontext_p.h b/src/qml/qml/qqmlcontext_p.h index 9fd9a10..3d31e47 100644 --- a/src/qml/qml/qqmlcontext_p.h +++ b/src/qml/qml/qqmlcontext_p.h @@ -152,7 +152,7 @@ public: void *activeVMEData; // Property name cache - QV4::IdentifierIntHash propertyNames; + QV4::IdentifierHash propertyNames; // Context object QObject *contextObject; @@ -198,7 +198,7 @@ public: ContextGuard *idValues; int idValueCount; void setIdProperty(int, QObject *); - void setIdPropertyData(const QV4::IdentifierIntHash &); + void setIdPropertyData(const QV4::IdentifierHash &); // Linked contexts. this owns linkedContext. QQmlContextData *linkedContext; diff --git a/src/qml/qml/v4/qv4identifier.cpp b/src/qml/qml/v4/qv4identifier.cpp index af11d2d..e2b9658 100644 --- a/src/qml/qml/v4/qv4identifier.cpp +++ b/src/qml/qml/v4/qv4identifier.cpp @@ -55,51 +55,24 @@ static inline int primeForNumBits(int numBits) } -IdentifierIntHashData::IdentifierIntHashData(int numBits) +IdentifierHashData::IdentifierHashData(int numBits) : refCount(Q_BASIC_ATOMIC_INITIALIZER(1)) , numBits(numBits) , size(0) { alloc = primeForNumBits(numBits); - entries = (IdentifierIntHash::Entry *)malloc(alloc*sizeof(IdentifierIntHash::Entry)); - memset(entries, 0, alloc*sizeof(IdentifierIntHash::Entry)); + entries = (IdentifierHashEntry *)malloc(alloc*sizeof(IdentifierHashEntry)); + memset(entries, 0, alloc*sizeof(IdentifierHashEntry)); } -IdentifierIntHash::IdentifierIntHash(ExecutionEngine *engine) +IdentifierHashBase::IdentifierHashBase(ExecutionEngine *engine) { - d = new IdentifierIntHashData(3); + d = new IdentifierHashData(3); d->identifierTable = engine->identifierTable; } -void IdentifierIntHash::add(const QString &str, int value) -{ - Identifier *i = d->identifierTable->identifier(str); - addEntry(i, value); -} - -int IdentifierIntHash::value(const QString &str) -{ - return lookup(d->identifierTable->identifier(str)); -} -int IdentifierIntHash::value(String *str) -{ - return lookup(d->identifierTable->identifier(str)); -} - -QString IdentifierIntHash::findId(int value) const -{ - Entry *e = d->entries; - Entry *end = e + d->alloc; - while (e < end) { - if (e->value == value) - return e->identifier->string; - } - return QString(); -} - - -void IdentifierIntHash::addEntry(const Identifier *identifier, uint value) +IdentifierHashEntry *IdentifierHashBase::addEntry(const Identifier *identifier) { // fill up to max 50% bool grow = (d->alloc <= d->size*2); @@ -107,13 +80,13 @@ void IdentifierIntHash::addEntry(const Identifier *identifier, uint value) if (grow) { ++d->numBits; int newAlloc = primeForNumBits(d->numBits); - Entry *newEntries = (Entry *)malloc(newAlloc * sizeof(Entry)); - memset(newEntries, 0, newAlloc*sizeof(Entry)); + IdentifierHashEntry *newEntries = (IdentifierHashEntry *)malloc(newAlloc * sizeof(IdentifierHashEntry)); + memset(newEntries, 0, newAlloc*sizeof(IdentifierHashEntry)); for (uint i = 0; i < d->alloc; ++i) { - const Entry &e = d->entries[i]; + const IdentifierHashEntry &e = d->entries[i]; if (!e.identifier) continue; - uint idx = hash(e.identifier) % newAlloc; + uint idx = Identifier::hash(e.identifier) % newAlloc; while (newEntries[idx].identifier) { ++idx; idx %= newAlloc; @@ -125,32 +98,42 @@ void IdentifierIntHash::addEntry(const Identifier *identifier, uint value) d->alloc = newAlloc; } - uint idx = hash(identifier) % d->alloc; + uint idx = Identifier::hash(identifier) % d->alloc; while (d->entries[idx].identifier) { Q_ASSERT(d->entries[idx].identifier != identifier); ++idx; idx %= d->alloc; } d->entries[idx].identifier = identifier; - d->entries[idx].value = value; ++d->size; + return d->entries + idx; } -int IdentifierIntHash::lookup(const Identifier *identifier) const +const IdentifierHashEntry *IdentifierHashBase::lookup(const Identifier *identifier) const { assert(d->entries); - uint idx = hash(identifier) % d->alloc; + uint idx = Identifier::hash(identifier) % d->alloc; while (1) { if (d->entries[idx].identifier == identifier) - return d->entries[idx].value; + return d->entries + idx; if (!d->entries[idx].identifier) - return -1; + return 0; ++idx; idx %= d->alloc; } } +const IdentifierHashEntry *IdentifierHashBase::lookup(const QString &str) const +{ + return lookup(d->identifierTable->identifier(str)); +} + +const IdentifierHashEntry *IdentifierHashBase::lookup(String *str) const +{ + return lookup(d->identifierTable->identifier(str)); +} + IdentifierTable::IdentifierTable(ExecutionEngine *engine) diff --git a/src/qml/qml/v4/qv4identifier_p.h b/src/qml/qml/v4/qv4identifier_p.h index 40d5207..8149d87 100644 --- a/src/qml/qml/v4/qv4identifier_p.h +++ b/src/qml/qml/v4/qv4identifier_p.h @@ -55,56 +55,64 @@ struct Identifier { QString string; uint hashValue; + + static inline uint hash(const QV4::Identifier *id) + { + quintptr h = (quintptr)id; + if (sizeof(quintptr) == sizeof(uint)) + return h ^ (h >> 8); + else + return (uint)(h ^ (h >> 8) ^ (h >> 32)); + } }; -inline uint hash(const QV4::Identifier *id) +struct IdentifierTable { - quintptr h = (quintptr)id; - if (sizeof(quintptr) == sizeof(uint)) - return h ^ (h >> 8); - else - return (uint)(h ^ (h >> 8) ^ (h >> 32)); -} + ExecutionEngine *engine; + int alloc; + int size; + int numBits; + String **entries; + void addEntry(String *str); -struct IdentifierIntHashData; -struct IdentifierIntHash -{ - struct Entry { - const Identifier *identifier; - int value; - }; +public: - IdentifierIntHashData *d; + IdentifierTable(ExecutionEngine *engine); + ~IdentifierTable(); - IdentifierIntHash() : d(0) {} - IdentifierIntHash(ExecutionEngine *engine); - inline IdentifierIntHash(const IdentifierIntHash &other); - inline ~IdentifierIntHash(); - inline IdentifierIntHash &operator=(const IdentifierIntHash &other); + String *insertString(const QString &s); - bool isEmpty() const { return !d; } - // ### - void reserve(int) {} + Identifier *identifier(String *str); + Identifier *identifier(const QString &s); + Identifier *identifier(const char *s, int len); + + void mark() { + for (int i = 0; i < alloc; ++i) + if (entries[i]) + entries[i]->mark(); + } +}; - inline int count() const; - void add(const QString &str, int value); - int value(const QString &); - int value(String *str); - QString findId(int value) const; -private: - void addEntry(const Identifier *i, uint value); - int lookup(const Identifier *identifier) const; +struct IdentifierHashEntry { + const Identifier *identifier; + union { + int value; + void *pointer; + }; + int get(int *) const { return this ? value : -1; } + bool get(bool *) const { return this != 0; } + void *get(void **) const { return this ? pointer : 0; } }; -struct IdentifierIntHashData +struct IdentifierHashData { - IdentifierIntHashData(int numBits); - ~IdentifierIntHashData() { + IdentifierHashData(int numBits); + ~IdentifierHashData() { free(entries); } @@ -113,23 +121,73 @@ struct IdentifierIntHashData int size; int numBits; IdentifierTable *identifierTable; - IdentifierIntHash::Entry *entries; + IdentifierHashEntry *entries; }; -inline IdentifierIntHash::IdentifierIntHash(const IdentifierIntHash &other) +struct IdentifierHashBase +{ + + IdentifierHashData *d; + + IdentifierHashBase() : d(0) {} + IdentifierHashBase(ExecutionEngine *engine); + inline IdentifierHashBase(const IdentifierHashBase &other); + inline ~IdentifierHashBase(); + inline IdentifierHashBase &operator=(const IdentifierHashBase &other); + + bool isEmpty() const { return !d; } + // ### + void reserve(int) {} + + inline int count() const; + bool contains(const Identifier *i) const; + bool contains(const QString &str) const; + bool contains(String *str) const; + +protected: + IdentifierHashEntry *addEntry(const Identifier *i); + const IdentifierHashEntry *lookup(const Identifier *identifier) const; + const IdentifierHashEntry *lookup(const QString &str) const; + const IdentifierHashEntry *lookup(String *str) const; +}; + + +template +struct IdentifierHash : public IdentifierHashBase +{ + IdentifierHash() + : IdentifierHashBase() {} + IdentifierHash(ExecutionEngine *engine) + : IdentifierHashBase(engine) {} + inline IdentifierHash(const IdentifierHash &other) + : IdentifierHashBase(other) {} + inline ~IdentifierHash() {} + inline IdentifierHash &operator=(const IdentifierHash &other) { + IdentifierHashBase::operator =(other); + return *this; + } + + void add(const QString &str, const T &value); + + inline T value(const QString &str) const; + inline T value(String *str) const; + QString findId(T value) const; +}; + +inline IdentifierHashBase::IdentifierHashBase(const IdentifierHashBase &other) { d = other.d; if (d) d->refCount.ref(); } -inline IdentifierIntHash::~IdentifierIntHash() +inline IdentifierHashBase::~IdentifierHashBase() { if (d && !d->refCount.deref()) delete d; } -IdentifierIntHash &IdentifierIntHash::operator=(const IdentifierIntHash &other) +IdentifierHashBase &IdentifierHashBase::operator=(const IdentifierHashBase &other) { if (other.d) other.d->refCount.ref(); @@ -139,40 +197,59 @@ IdentifierIntHash &IdentifierIntHash::operator=(const IdentifierIntHash &other) return *this; } -inline int IdentifierIntHash::count() const +inline int IdentifierHashBase::count() const { return d ? d->size : 0; } - -struct IdentifierTable +inline bool IdentifierHashBase::contains(const Identifier *i) const { - ExecutionEngine *engine; + return lookup(i) != 0; +} - int alloc; - int size; - int numBits; - String **entries; +inline bool IdentifierHashBase::contains(const QString &str) const +{ + return lookup(str) != 0; +} - void addEntry(String *str); +inline bool IdentifierHashBase::contains(String *str) const +{ + return lookup(str) != 0; +} -public: +template +void IdentifierHash::add(const QString &str, const T &value) +{ + Identifier *i = d->identifierTable->identifier(str); + IdentifierHashEntry *e = addEntry(i); + e->value = value; +} - IdentifierTable(ExecutionEngine *engine); - ~IdentifierTable(); +template +inline T IdentifierHash::value(const QString &str) const +{ + return lookup(str)->get((T*)0); +} - String *insertString(const QString &s); +template +inline T IdentifierHash::value(String *str) const +{ + return lookup(str)->get((T*)0); +} - Identifier *identifier(String *str); - Identifier *identifier(const QString &s); - Identifier *identifier(const char *s, int len); - void mark() { - for (int i = 0; i < alloc; ++i) - if (entries[i]) - entries[i]->mark(); +template +QString IdentifierHash::findId(T value) const +{ + IdentifierHashEntry *e = d->entries; + IdentifierHashEntry *end = e + d->alloc; + while (e < end) { + if (e->get((T*)0) == value) + return e->identifier->string; } -}; + return QString(); +} + } diff --git a/src/qml/qml/v4/qv4internalclass.cpp b/src/qml/qml/v4/qv4internalclass.cpp index 4e3e006..f7f898d 100644 --- a/src/qml/qml/v4/qv4internalclass.cpp +++ b/src/qml/qml/v4/qv4internalclass.cpp @@ -50,7 +50,7 @@ QT_BEGIN_NAMESPACE uint QV4::qHash(const QV4::InternalClassTransition &t, uint) { - return hash(t.id) ^ t.flags; + return Identifier::hash(t.id) ^ t.flags; } using namespace QV4; @@ -91,7 +91,7 @@ void PropertyHash::addEntry(const PropertyHash::Entry &entry, int classSize) const Entry &e = d->entries[i]; if (!e.identifier || e.index >= classSize) continue; - uint idx = hash(e.identifier) % dd->alloc; + uint idx = Identifier::hash(e.identifier) % dd->alloc; while (dd->entries[idx].identifier) { ++idx; idx %= dd->alloc; @@ -104,7 +104,7 @@ void PropertyHash::addEntry(const PropertyHash::Entry &entry, int classSize) d = dd; } - uint idx = hash(entry.identifier) % d->alloc; + uint idx = Identifier::hash(entry.identifier) % d->alloc; while (d->entries[idx].identifier) { ++idx; idx %= d->alloc; @@ -117,7 +117,7 @@ uint PropertyHash::lookup(const Identifier *identifier) const { assert(d->entries); - uint idx = hash(identifier) % d->alloc; + uint idx = Identifier::hash(identifier) % d->alloc; while (1) { if (d->entries[idx].identifier == identifier) return d->entries[idx].index; -- 2.7.4