From 57671bebbcfc06d0ad390dd470f51eb1f8556314 Mon Sep 17 00:00:00 2001
From: Marc Mutz <marc.mutz@kdab.com>
Date: Thu, 14 Jan 2016 16:35:40 +0100
Subject: QGraphicsAnchorLayout: remove a misguided use of QLinkedList

QSimplexConstraints are held in QList everywhere, yet one
single function, getGraphParts(), used a temporary
QLinkedList. It did so because the function repeatedly
walks the list, erasing elements from it until no more
elements have been removed.

Thus, in O-terms, QLinkedList is the correct choice here.
Sadly, O-notation completely ignores the per-element cost,
and this is where QLinkedList suffers. By the time a QList
has shifted all of its elements left once, the QLinkedList
probably has just finished allocating its first node.

So, use a QList instead.

That, however, turns the it = erase(it) loop quadratic, so
re-formulate the processing part as a lambda and use
std::remove_if. Don't even erase until we know how many
items to erase.

As a benefit, we save the final conversion of the remaining
items back to a QList, and we can use QList::op+ to build
the initial list, reducing the number of allocations
performed by that container to one.

Also saves ~770b in text size on optimized GCC 5.3 Linux
AMD64 builds.

Change-Id: Iecf9e7961dd2b6b20039b9b0d472e32b3fae6994
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
---
 .../graphicsview/qgraphicsanchorlayout_p.cpp       | 37 ++++++++--------------
 1 file changed, 13 insertions(+), 24 deletions(-)

diff --git a/src/widgets/graphicsview/qgraphicsanchorlayout_p.cpp b/src/widgets/graphicsview/qgraphicsanchorlayout_p.cpp
index 1e5aea9688..95cdaaddc1 100644
--- a/src/widgets/graphicsview/qgraphicsanchorlayout_p.cpp
+++ b/src/widgets/graphicsview/qgraphicsanchorlayout_p.cpp
@@ -2513,13 +2513,7 @@ QGraphicsAnchorLayoutPrivate::getGraphParts(Orientation orientation)
         edgeL1 = graph[orientation].edgeData(layoutFirstVertex[orientation], layoutLastVertex[orientation]);
     }
 
-    QLinkedList<QSimplexConstraint *> remainingConstraints;
-    for (int i = 0; i < constraints[orientation].count(); ++i) {
-        remainingConstraints += constraints[orientation].at(i);
-    }
-    for (int i = 0; i < itemCenterConstraints[orientation].count(); ++i) {
-        remainingConstraints += itemCenterConstraints[orientation].at(i);
-    }
+    QList<QSimplexConstraint *> remainingConstraints = constraints[orientation] + itemCenterConstraints[orientation];
 
     QList<QSimplexConstraint *> trunkConstraints;
     QSet<QSimplexVariable *> trunkVariables;
@@ -2529,12 +2523,11 @@ QGraphicsAnchorLayoutPrivate::getGraphParts(Orientation orientation)
         trunkVariables += edgeL2;
 
     bool dirty;
+    auto end = remainingConstraints.end();
     do {
         dirty = false;
 
-        QLinkedList<QSimplexConstraint *>::iterator it = remainingConstraints.begin();
-        while (it != remainingConstraints.end()) {
-            QSimplexConstraint *c = *it;
+        auto isMatch = [&trunkConstraints, &trunkVariables](QSimplexConstraint *c) -> bool {
             bool match = false;
 
             // Check if this constraint have some overlap with current
@@ -2552,8 +2545,7 @@ QGraphicsAnchorLayoutPrivate::getGraphParts(Orientation orientation)
                 trunkConstraints += c;
                 for (auto jt = c->variables.cbegin(), end = c->variables.cend(); jt != end; ++jt)
                     trunkVariables.insert(jt.key());
-                it = remainingConstraints.erase(it);
-                dirty = true;
+                return true;
             } else {
                 // Note that we don't erase the constraint if it's not
                 // a match, since in a next iteration of a do-while we
@@ -2563,24 +2555,21 @@ QGraphicsAnchorLayoutPrivate::getGraphParts(Orientation orientation)
                 // remainingConstraints[1] and it shares with
                 // remainingConstraints[0], we need a second iteration
                 // of the do-while loop to match both.
-                ++it;
+                return false;
             }
-        }
+        };
+        const auto newEnd = std::remove_if(remainingConstraints.begin(), end, isMatch);
+        dirty = newEnd != end;
+        end = newEnd;
     } while (dirty);
 
+    remainingConstraints.erase(end, remainingConstraints.end());
+
     QList< QList<QSimplexConstraint *> > result;
     result += trunkConstraints;
 
-    if (!remainingConstraints.isEmpty()) {
-        QList<QSimplexConstraint *> nonTrunkConstraints;
-        nonTrunkConstraints.reserve(remainingConstraints.size());
-        QLinkedList<QSimplexConstraint *>::iterator it = remainingConstraints.begin();
-        while (it != remainingConstraints.end()) {
-            nonTrunkConstraints += *it;
-            ++it;
-        }
-        result += nonTrunkConstraints;
-    }
+    if (!remainingConstraints.isEmpty())
+        result += remainingConstraints; // non-trunk constraints
 
     return result;
 }
-- 
cgit v1.2.3