Replace the hash tables with simple association lists.

Change-Id: If4fdd14bba6d800699be1bfd9f6b147bb5279a30
Reviewed-on: http://codereview.qt.nokia.com/3785
Reviewed-by: Roberto Raggi <roberto.raggi@nokia.com>
Reviewed-by: Qt Sanity Bot <qt_sanity_bot@ovi.com>

3 files changed, 80 insertions, 33 deletions

diff --git a/src/declarative/qml/v4/qdeclarativev4compiler.cpp b/src/declarative/qml/v4/qdeclarativev4compiler.cpp
index 9d7c9f7462..fa4cd25952 100644
--- a/src/declarative/qml/v4/qdeclarativev4compiler.cpp
+++ b/src/declarative/qml/v4/qdeclarativev4compiler.cpp
@@ -986,7 +986,6 @@ This does not clear the global "committed binding" states.
 */
 void QDeclarativeV4CompilerPrivate::resetInstanceState()
 {
-    registerCleanups.clear();
     data = committed.data;
     exceptions = committed.exceptions;
     usedSubscriptionIds.clear();
@@ -1095,9 +1094,9 @@ int QDeclarativeV4CompilerPrivate::registerString(const QString &string)
 {
     Q_ASSERT(!string.isEmpty());
 
-    QHash<QString, QPair<int, int> >::ConstIterator iter = registeredStrings.find(string);
+    QPair<int, int> *iter = registeredStrings.value(string);
 
-    if (iter == registeredStrings.end()) {
+    if (!iter) {
         quint32 len = string.length();
         QByteArray lendata((const char *)&len, sizeof(quint32));
         QByteArray strdata((const char *)string.constData(), string.length() * sizeof(QChar));
@@ -1105,7 +1104,8 @@ int QDeclarativeV4CompilerPrivate::registerString(const QString &string)
         int rv = data.count();
         data += strdata;
 
-        iter = registeredStrings.insert(string, qMakePair(registeredStrings.count(), rv));
+        iter = &registeredStrings[string];
+        *iter = qMakePair(registeredStrings.count(), rv);
     } 
 
     Instr reg;
@@ -1123,12 +1123,12 @@ bool QDeclarativeV4CompilerPrivate::blockNeedsSubscription(const QStringList &su
 {
     QString str = sub.join(QLatin1String("."));
 
-    QHash<QString, int>::ConstIterator iter = subscriptionIds.find(str);
-    if (iter == subscriptionIds.end())
+    int *iter = subscriptionIds.value(str);
+    if (!iter)
         return true;
 
-    QHash<int, quint32>::ConstIterator uiter = usedSubscriptionIds.find(*iter);
-    if (uiter == usedSubscriptionIds.end())
+    quint32 *uiter = usedSubscriptionIds.value(*iter);
+    if (!uiter)
         return true;
     else
         return !(*uiter & currentBlockMask);
@@ -1137,11 +1137,15 @@ bool QDeclarativeV4CompilerPrivate::blockNeedsSubscription(const QStringList &su
 int QDeclarativeV4CompilerPrivate::subscriptionIndex(const QStringList &sub)
 {
     QString str = sub.join(QLatin1String("."));
-    QHash<QString, int>::ConstIterator iter = subscriptionIds.find(str);
-    if (iter == subscriptionIds.end()) 
-        iter = subscriptionIds.insert(str, subscriptionIds.count());
-    if (!(usedSubscriptionIds[*iter] & currentBlockMask)) {
-        usedSubscriptionIds[*iter] |= currentBlockMask;
+    int *iter = subscriptionIds.value(str);
+    if (!iter) {
+        int count = subscriptionIds.count();
+        iter = &subscriptionIds[str];
+        *iter = count;
+    }
+    quint32 &u = usedSubscriptionIds[*iter];
+    if (!(u & currentBlockMask)) {
+        u |= currentBlockMask;
         usedSubscriptionIdsChanged = true;
     }
     return *iter;
@@ -1151,11 +1155,11 @@ quint32 QDeclarativeV4CompilerPrivate::subscriptionBlockMask(const QStringList &
 {
     QString str = sub.join(QLatin1String("."));
 
-    QHash<QString, int>::ConstIterator iter = subscriptionIds.find(str);
-    Q_ASSERT(iter != subscriptionIds.end());
+    int *iter = subscriptionIds.value(str);
+    Q_ASSERT(iter != 0);
 
-    QHash<int, quint32>::ConstIterator uiter = usedSubscriptionIds.find(*iter);
-    Q_ASSERT(uiter != usedSubscriptionIds.end());
+    quint32 *uiter = usedSubscriptionIds.value(*iter);
+    Q_ASSERT(uiter != 0);
 
     return *uiter;
 }
@@ -1230,9 +1234,9 @@ QByteArray QDeclarativeV4CompilerPrivate::buildSignalTable() const
     QHash<int, QList<QPair<int, quint32> > > table;
 
     for (int ii = 0; ii < committed.count(); ++ii) {
-        const QHash<int, quint32> &deps = committed.dependencies.at(ii);
-        for (QHash<int, quint32>::ConstIterator iter = deps.begin(); iter != deps.end(); ++iter) 
-            table[iter.key()].append(qMakePair(ii, iter.value()));
+        const QDeclarativeAssociationList<int, quint32> &deps = committed.dependencies.at(ii);
+        for (QDeclarativeAssociationList<int, quint32>::const_iterator iter = deps.begin(); iter != deps.end(); ++iter)
+            table[iter->first].append(qMakePair(ii, iter->second));
     }
 
     QVector<quint32> header;
@@ -1315,13 +1319,12 @@ QByteArray QDeclarativeV4Compiler::program() const
     if (bindingsDump()) {
         qWarning().nospace() << "Subscription slots:";
 
-        for (QHash<QString, int>::ConstIterator iter = d->committed.subscriptionIds.begin();
+        for (QDeclarativeAssociationList<QString, int>::ConstIterator iter = d->committed.subscriptionIds.begin();
                 iter != d->committed.subscriptionIds.end();
                 ++iter) {
-            qWarning().nospace() << "    " << iter.value() << "\t-> " << iter.key();
+            qWarning().nospace() << "    " << iter->first << "\t-> " << iter->second;
         }
 
-
         QDeclarativeV4Compiler::dump(programData);
     }
 
diff --git a/src/declarative/qml/v4/qdeclarativev4compiler_p_p.h b/src/declarative/qml/v4/qdeclarativev4compiler_p_p.h
index b64aff940d..0aa76f2165 100644
--- a/src/declarative/qml/v4/qdeclarativev4compiler_p_p.h
+++ b/src/declarative/qml/v4/qdeclarativev4compiler_p_p.h
@@ -93,6 +93,54 @@ inline bool operator==(const QDeclarative1AnchorLine& a, const QDeclarative1Anch
 }
 
 
+template <typename _Key, typename _Value>
+class QDeclarativeAssociationList
+{
+public:
+    typedef QVarLengthArray<QPair<_Key, _Value>, 8> Container;
+    typedef typename Container::const_iterator const_iterator;
+    typedef typename Container::const_iterator ConstIterator;
+
+    const_iterator begin() const { return _container.begin(); }
+    const_iterator end() const { return _container.end(); }
+    int count() const { return _container.count(); }
+    void clear() { _container.clear(); }
+
+    _Value *value(const _Key &key) {
+        for (int i = 0; i < _container.size(); ++i) {
+            QPair<_Key, _Value> &p = _container[i];
+            if (p.first == key)
+                return &p.second;
+        }
+        return 0;
+    }
+
+    _Value &operator[](const _Key &key) {
+        for (int i = 0; i < _container.size(); ++i) {
+            QPair<_Key, _Value> &p = _container[i];
+            if (p.first == key)
+                return p.second;
+        }
+        int index = _container.size();
+        _container.append(qMakePair(key, _Value()));
+        return _container[index].second;
+    }
+
+    void insert(const _Key &key, _Value &value) {
+        for (int i = 0; i < _container.size(); ++i) {
+            QPair<_Key, _Value> &p = _container[i];
+            if (p.first == key) {
+                p.second = value;
+                return;
+            }
+        }
+        _container.append(qMakePair(key, value));
+    }
+
+private:
+    Container _container;
+};
+
 class QDeclarativeV4CompilerPrivate: protected QDeclarativeJS::IR::ExprVisitor, 
                                      protected QDeclarativeJS::IR::StmtVisitor
 {
@@ -109,11 +157,9 @@ public:
 
     bool compile(QDeclarativeJS::AST::Node *);
 
-    QHash<int, QPair<int, int> > registerCleanups;
-
     int registerLiteralString(quint8 reg, const QStringRef &);
     int registerString(const QString &);
-    QHash<QString, QPair<int, int> > registeredStrings;
+    QDeclarativeAssociationList<QString, QPair<int, int> > registeredStrings;
     QByteArray data;
 
     bool blockNeedsSubscription(const QStringList &);
@@ -124,9 +170,9 @@ public:
     quint8 exceptionId(QDeclarativeJS::AST::ExpressionNode *);
     QVector<quint64> exceptions;
 
-    QHash<int, quint32> usedSubscriptionIds;
+    QDeclarativeAssociationList<int, quint32> usedSubscriptionIds;
 
-    QHash<QString, int> subscriptionIds;
+    QDeclarativeAssociationList<QString, int> subscriptionIds;
     QDeclarativeJS::Bytecode bytecode;
 
     // back patching
@@ -142,15 +188,15 @@ public:
     // Committed binding data
     struct {
         QList<int> offsets;
-        QList<QHash<int, quint32> > dependencies;
+        QList<QDeclarativeAssociationList<int, quint32> > dependencies;
 
         //QDeclarativeJS::Bytecode bytecode;
         QByteArray bytecode;
         QByteArray data;
-        QHash<QString, int> subscriptionIds;
+        QDeclarativeAssociationList<QString, int> subscriptionIds;
         QVector<quint64> exceptions;
 
-        QHash<QString, QPair<int, int> > registeredStrings;
+        QDeclarativeAssociationList<QString, QPair<int, int> > registeredStrings;
 
         int count() const { return offsets.count(); }
     } committed;
diff --git a/src/declarative/qml/v4/qdeclarativev4instruction.cpp b/src/declarative/qml/v4/qdeclarativev4instruction.cpp
index 93bb206c1a..dd6892369b 100644
--- a/src/declarative/qml/v4/qdeclarativev4instruction.cpp
+++ b/src/declarative/qml/v4/qdeclarativev4instruction.cpp
@@ -512,8 +512,6 @@ void Instr::block(quint32 mask)
 
 Bytecode::Bytecode()
 {
-    d.reserve(8 * 1024);
-
 #ifdef QML_THREADED_INTERPRETER
     decodeInstr = QDeclarativeV4Bindings::getDecodeInstrTable();
 #endif