Use a linked list for signal/slot ConnectionList

Using a linked list, rather than a QList improves connection
performance by eliminating the QList allocation costs.

Reviewed-by: brad

2 files changed, 86 insertions, 39 deletions

diff --git a/src/corelib/kernel/qobject.cpp b/src/corelib/kernel/qobject.cpp
index 6520170..371770f 100644
--- a/src/corelib/kernel/qobject.cpp
+++ b/src/corelib/kernel/qobject.cpp
@@ -257,11 +257,13 @@ bool QObjectPrivate::isSender(const QObject *receiver, const char *signal) const
     QMutexLocker locker(signalSlotLock(q));
     if (connectionLists) {
         if (signal_index < connectionLists->count()) {
-            const ConnectionList &connectionList = connectionLists->at(signal_index);
-            for (int i = 0; i < connectionList.count(); ++i) {
-                const QObjectPrivate::Connection *c = connectionList.at(i);
+            const QObjectPrivate::Connection *c = 
+                connectionLists->at(signal_index).first;
+
+            while (c) {
                 if (c->receiver == receiver)
                     return true;
+                c = c->nextConnectionList;
             }
         }
     }
@@ -279,11 +281,12 @@ QObjectList QObjectPrivate::receiverList(const char *signal) const
     QMutexLocker locker(signalSlotLock(q));
     if (connectionLists) {
         if (signal_index < connectionLists->count()) {
-            const ConnectionList &connectionList = connectionLists->at(signal_index);
-            for (int i = 0; i < connectionList.count(); ++i) {
-                const QObjectPrivate::Connection *c = connectionList.at(i);
+            const QObjectPrivate::Connection *c = connectionLists->at(signal_index).first;
+
+            while (c) {
                 if (c->receiver)
                     returnValue << c->receiver;
+                c = c->nextConnectionList;
             }
         }
     }
@@ -308,7 +311,13 @@ void QObjectPrivate::addConnection(int signal, Connection *c)
         connectionLists->resize(signal + 1);
 
     ConnectionList &connectionList = (*connectionLists)[signal];
-    connectionList.append(c);
+    if (connectionList.last) {
+        connectionList.last->nextConnectionList = c;
+    } else {
+        connectionList.first = c;
+    }
+    connectionList.last = c;
+
     cleanConnectionLists();
 }
 
@@ -317,14 +326,32 @@ void QObjectPrivate::cleanConnectionLists()
     if (connectionLists->dirty && !connectionLists->inUse) {
         // remove broken connections
         for (int signal = -1; signal < connectionLists->count(); ++signal) {
-            QObjectPrivate::ConnectionList &connectionList = (*connectionLists)[signal];
-            for (int i = 0; i < connectionList.count(); ++i) {
-                QObjectPrivate::Connection *c = connectionList.at(i);
-                if (!c->receiver) {
+            QObjectPrivate::ConnectionList &connectionList = 
+                (*connectionLists)[signal];
+
+            // Set to the last entry in the connection list that was *not*
+            // deleted.  This is needed to update the list's last pointer
+            // at the end of the cleanup.
+            QObjectPrivate::Connection *last = 0;
+
+            QObjectPrivate::Connection **prev = &connectionList.first;
+            QObjectPrivate::Connection *c = *prev;
+            while (c) {
+                if (c->receiver) {
+                    last = c;
+                    prev = &c->nextConnectionList;
+                    c = *prev;
+                } else {
+                    QObjectPrivate::Connection *next = c->nextConnectionList;
+                    *prev = next;
                     delete c;
-                    connectionList.removeAt(i--);
+                    c = next;
                 }
             }
+
+            // Correct the connection list's last pointer.  As 
+            // conectionList.last could equal last, this could be a noop
+            connectionList.last = last;
         }
         connectionLists->dirty = false;
     }
@@ -797,17 +824,19 @@ QObject::~QObject()
         if (d->connectionLists) {
             ++d->connectionLists->inUse;
             for (int signal = -1; signal < d->connectionLists->count(); ++signal) {
-                QObjectPrivate::ConnectionList &connectionList = (*d->connectionLists)[signal];
-                for (int i = 0; i < connectionList.count(); ++i) {
-                    QObjectPrivate::Connection *c = connectionList[i];
+                QObjectPrivate::ConnectionList &connectionList = 
+                    (*d->connectionLists)[signal];
+
+                while (QObjectPrivate::Connection *c = connectionList.first) {
                     if (!c->receiver) {
+                        connectionList.first = c->nextConnectionList;
                         delete c;
                         continue;
                     }
 
                     QMutex *m = signalSlotLock(c->receiver);
                     bool needToUnlock = QOrderedMutexLocker::relock(locker.mutex(), m);
-                    c = connectionList[i];
+
                     if (c->receiver) {
                         *c->prev = c->next;
                         if (c->next) c->next->prev = c->prev;
@@ -815,6 +844,7 @@ QObject::~QObject()
                     if (needToUnlock)
                         m->unlock();
 
+                    connectionList.first = c->nextConnectionList;
                     delete c;
                 }
             }
@@ -2412,11 +2442,11 @@ int QObject::receivers(const char *signal) const
         QMutexLocker locker(signalSlotLock(this));
         if (d->connectionLists) {
             if (signal_index < d->connectionLists->count()) {
-                const QObjectPrivate::ConnectionList &connectionList =
-                    d->connectionLists->at(signal_index);
-                for (int i = 0; i < connectionList.count(); ++i) {
-                    const QObjectPrivate::Connection *c = connectionList.at(i);
+                const QObjectPrivate::Connection *c = 
+                    d->connectionLists->at(signal_index).first;
+                while (c) {
                     receivers += c->receiver ? 1 : 0;
+                    c = c->nextConnectionList;
                 }
             }
         }
@@ -2861,11 +2891,13 @@ bool QMetaObject::connect(const QObject *sender, int signal_index,
     if (type & Qt::UniqueConnection) {
         QObjectConnectionListVector *connectionLists = s->d_func()->connectionLists;
         if (connectionLists && connectionLists->count() > signal_index) {
-            QObjectPrivate::ConnectionList &connectionList = (*connectionLists)[signal_index];
-            for (int i = 0; i < connectionList.count(); ++i) {
-                QObjectPrivate::Connection *c2 = connectionList.at(i);
+            const QObjectPrivate::Connection *c2 = 
+                (*connectionLists)[signal_index].first;
+
+            while (c2) {
                 if (c2->receiver == receiver && c2->method == method_index)
                     return false;
+                c2 = c2->nextConnectionList;
             }
         }
         type &= Qt::UniqueConnection - 1;
@@ -2877,6 +2909,7 @@ bool QMetaObject::connect(const QObject *sender, int signal_index,
     c->method = method_index;
     c->connectionType = type;
     c->argumentTypes = types;
+    c->nextConnectionList = 0;
     c->prev = &r->d_func()->senders;
     c->next = *c->prev;
     *c->prev = c;
@@ -2926,9 +2959,9 @@ bool QMetaObject::disconnect(const QObject *sender, int signal_index,
     if (signal_index < 0) {
         // remove from all connection lists
         for (signal_index = -1; signal_index < connectionLists->count(); ++signal_index) {
-            QObjectPrivate::ConnectionList &connectionList = (*connectionLists)[signal_index];
-            for (int i = 0; i < connectionList.count(); ++i) {
-                QObjectPrivate::Connection *c = connectionList[i];
+            QObjectPrivate::Connection *c = 
+                (*connectionLists)[signal_index].first;
+            while (c) {
                 if (c->receiver
                     && (r == 0 || (c->receiver == r
                                    && (method_index < 0 || c->method == method_index)))) {
@@ -2937,7 +2970,6 @@ bool QMetaObject::disconnect(const QObject *sender, int signal_index,
                     if (!receiverMutex && senderMutex != m) {
                         // need to relock this receiver and sender in the correct order
                         needToUnlock = QOrderedMutexLocker::relock(senderMutex, m);
-                        c = connectionList[i];
                     }
                     if (c->receiver) {
                         *c->prev = c->next;
@@ -2952,12 +2984,13 @@ bool QMetaObject::disconnect(const QObject *sender, int signal_index,
                     success = true;
                     connectionLists->dirty = true;
                 }
+                c = c->nextConnectionList;
             }
         }
     } else if (signal_index < connectionLists->count()) {
-        QObjectPrivate::ConnectionList &connectionList = (*connectionLists)[signal_index];
-        for (int i = 0; i < connectionList.count(); ++i) {
-            QObjectPrivate::Connection *c = connectionList[i];
+        QObjectPrivate::Connection *c = 
+            (*connectionLists)[signal_index].first;
+        while (c) {
             if (c->receiver
                 && (r == 0 || (c->receiver == r
                                && (method_index < 0 || c->method == method_index)))) {
@@ -2966,7 +2999,6 @@ bool QMetaObject::disconnect(const QObject *sender, int signal_index,
                 if (!receiverMutex && senderMutex != m) {
                     // need to relock this receiver and sender in the correct order
                     needToUnlock = QOrderedMutexLocker::relock(senderMutex, m);
-                    c = connectionList[i];
                 }
                 if (c->receiver) {
                     *c->prev = c->next;
@@ -2980,6 +3012,7 @@ bool QMetaObject::disconnect(const QObject *sender, int signal_index,
                 success = true;
                 connectionLists->dirty = true;
             }
+            c = c->nextConnectionList;
         }
     }
 
@@ -3144,9 +3177,14 @@ void QMetaObject::activate(QObject *sender, int from_signal_index, int to_signal
             signal = to_signal_index;
             continue;
         }
-        int count = connectionLists->at(signal).count();
-        for (int i = 0; i < count; ++i) {
-            QObjectPrivate::Connection *c = connectionLists->at(signal)[i];
+        
+        QObjectPrivate::Connection *c = connectionLists->at(signal).first;
+        if (!c) continue;
+        // We need to check against last here to ensure that signals added
+        // during the signal emission are not emitted in this emission.
+        QObjectPrivate::Connection *last = connectionLists->at(signal).last;
+
+        do {
             if (!c->receiver)
                 continue;
 
@@ -3208,7 +3246,7 @@ void QMetaObject::activate(QObject *sender, int from_signal_index, int to_signal
 
             if (connectionLists->orphaned)
                 break;
-        }
+        } while (c != last && (c = c->nextConnectionList) != 0);
 
         if (connectionLists->orphaned)
             break;
@@ -3527,11 +3565,12 @@ void QObject::dumpObjectInfo()
             qDebug("        signal: %s", signal.signature());
 
             // receivers
-            const QObjectPrivate::ConnectionList &connectionList = d->connectionLists->at(signal_index);
-            for (int i = 0; i < connectionList.count(); ++i) {
-                const QObjectPrivate::Connection *c = connectionList.at(i);
+            const QObjectPrivate::Connection *c = 
+                d->connectionLists->at(signal_index).first;
+            while (c) {
                 if (!c->receiver) {
                     qDebug("          <Disconnected receiver>");
+                    c = c->nextConnectionList;
                     continue;
                 }
                 const QMetaObject *receiverMetaObject = c->receiver->metaObject();
@@ -3540,6 +3579,7 @@ void QObject::dumpObjectInfo()
                        receiverMetaObject->className(),
                        c->receiver->objectName().isEmpty() ? "unnamed" : qPrintable(c->receiver->objectName()),
                        method.signature());
+                c = c->nextConnectionList;
             }
         }
     } else {
diff --git a/src/corelib/kernel/qobject_p.h b/src/corelib/kernel/qobject_p.h
index 5d17bfd..4f8f1b9 100644
--- a/src/corelib/kernel/qobject_p.h
+++ b/src/corelib/kernel/qobject_p.h
@@ -113,12 +113,19 @@ public:
         int method;
         uint connectionType : 3; // 0 == auto, 1 == direct, 2 == queued, 4 == blocking
         QBasicAtomicPointer<int> argumentTypes;
+        // The next pointer for the singly-linked ConnectionList
+        Connection *nextConnectionList;
         //senders linked list
         Connection *next;
         Connection **prev;
         ~Connection();
     };
-    typedef QList<Connection *> ConnectionList;
+    // ConnectionList is a singly-linked list
+    struct ConnectionList {
+        ConnectionList() : first(0), last(0) {}
+        Connection *first;
+        Connection *last;
+    };
 
     struct Sender
     {