Improve QTextDocumentPrivate cursor performance

The cursors in QTextDocumentPrivate are held in a QList.
This becomes a serious performance problem with lots of
extra selections due to a call to
QTextDocumentPrivate::removeCursor() from the QTextCursor
destructor.

Given the following test program:

    QPlainTextEdit *editor = ...
    std::list< QTextCursor> list;
    for(int i = 0; i < 100000; ++i) {
    QTextCursor c(editor->document());
    c.setPosition(std::rand()%100);
    list.push_front(c);
    }
    list.clear(); // <-- clear calls hangs for 3+ seconds
                  // due to time spent in
                  // QTextDocumentPrivate::removeCursor()
                  // due to QList::removeAll() call

Note the push_front because it exacerbates the issue because
the entire list will be traversed.

The change submitted changes the structure to a set,
removing the issue.
In theory, this limits that a cursors cannot be in the
structure twice, but this neither happens nor would it make sense.

Change-Id: I817dc5d1bda1d98c6725a531b32d1c711a029a34
Reviewed-by: Langonda Agag <namezero@afim.info>
Reviewed-by: Friedemann Kleint <Friedemann.Kleint@qt.io>
Reviewed-by: Simon Hausmann <simon.hausmann@qt.io>
Reviewed-by: Eskil Abrahamsen Blomfeldt <eskil.abrahamsen-blomfeldt@qt.io>
Reviewed-by: Jesus Fernandez <jsfdez@gmail.com>

2 files changed, 4 insertions, 4 deletions

diff --git a/src/gui/text/qtextdocument_p.cpp b/src/gui/text/qtextdocument_p.cpp
index a1b1c2e92b..2f02f62a57 100644
--- a/src/gui/text/qtextdocument_p.cpp
+++ b/src/gui/text/qtextdocument_p.cpp
@@ -243,7 +243,7 @@ void QTextDocumentPrivate::clear()
         curs->adjusted_anchor = 0;
     }
 
-    QList<QTextCursorPrivate *>oldCursors = cursors;
+    QSet<QTextCursorPrivate *> oldCursors = cursors;
     QT_TRY{
         cursors.clear();
 
diff --git a/src/gui/text/qtextdocument_p.h b/src/gui/text/qtextdocument_p.h
index f4e7a25f22..94c67b3264 100644
--- a/src/gui/text/qtextdocument_p.h
+++ b/src/gui/text/qtextdocument_p.h
@@ -277,8 +277,8 @@ private:
 public:
     void documentChange(int from, int length);
 
-    inline void addCursor(QTextCursorPrivate *c) { cursors.append(c); }
-    inline void removeCursor(QTextCursorPrivate *c) { cursors.removeAll(c); }
+    inline void addCursor(QTextCursorPrivate *c) { cursors.insert(c); }
+    inline void removeCursor(QTextCursorPrivate *c) { cursors.remove(c); }
 
     QTextFrame *frameAt(int pos) const;
     QTextFrame *rootFrame() const;
@@ -330,7 +330,7 @@ private:
     BlockMap blocks;
     int initialBlockCharFormatIndex;
 
-    QList<QTextCursorPrivate *> cursors;
+    QSet<QTextCursorPrivate *> cursors;
     QMap<int, QTextObject *> objects;
     QMap<QUrl, QVariant> resources;
     QMap<QUrl, QVariant> cachedResources;