QLinkedList - fix erase with iterator when the list is shared.

Before a call to erase on a shared instance would imply that the
item was removed from the shared data (i.e all instances)

This patch improves the behavior to detach and erase the item
specified by the iterator (i.e same behavior as QVector)

Change-Id: Ib3cfb5363c86b400886c80b75b0c20ca854ce801
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

4 files changed, 115 insertions, 2 deletions

diff --git a/src/corelib/tools/qlinkedlist.h b/src/corelib/tools/qlinkedlist.h
index b9ca1b964a..99be770ae9 100644
--- a/src/corelib/tools/qlinkedlist.h
+++ b/src/corelib/tools/qlinkedlist.h
@@ -91,7 +91,7 @@ public:
 
     inline int size() const { return d->size; }
     inline void detach()
-    { if (d->ref.isShared()) detach_helper(); }
+    { if (d->ref.isShared()) detach_helper2(this->e); }
     inline bool isDetached() const { return !d->ref.isShared(); }
     inline void setSharable(bool sharable) { if (!sharable) detach(); if (d != &QLinkedListData::shared_null) d->sharable = sharable; }
     inline bool isSharedWith(const QLinkedList<T> &other) const { return d == other.d; }
@@ -232,6 +232,7 @@ public:
 
 private:
     void detach_helper();
+    iterator detach_helper2(iterator);
     void freeData(QLinkedListData*);
 };
 
@@ -245,6 +246,14 @@ inline QLinkedList<T>::~QLinkedList()
 template <typename T>
 void QLinkedList<T>::detach_helper()
 {
+    detach_helper2(this->e);
+}
+
+template <typename T>
+typename QLinkedList<T>::iterator QLinkedList<T>::detach_helper2(iterator orgite)
+{
+    // detach and convert orgite to an iterator in the detached instance
+    bool isEndIterator = (orgite.i == this->e);
     union { QLinkedListData *d; Node *e; } x;
     x.d = new QLinkedListData;
     x.d->ref.initializeOwned();
@@ -252,6 +261,22 @@ void QLinkedList<T>::detach_helper()
     x.d->sharable = true;
     Node *original = e->n;
     Node *copy = x.e;
+    Node *org = orgite.i;
+
+    while (original != org) {
+        QT_TRY {
+            copy->n = new Node(original->t);
+            copy->n->p = copy;
+            original = original->n;
+            copy = copy->n;
+        } QT_CATCH(...) {
+            copy->n = x.e;
+            Q_ASSERT(!x.d->ref.deref()); // Don't trigger assert in free
+            freeData(x.d);
+            QT_RETHROW;
+        }
+    }
+    iterator r(copy);
     while (original != e) {
         QT_TRY {
             copy->n = new Node(original->t);
@@ -270,6 +295,9 @@ void QLinkedList<T>::detach_helper()
     if (!d->ref.deref())
         freeData(d);
     d = x.d;
+    if (!isEndIterator)
+        ++r; // since we stored the element right before the original node.
+    return r;
 }
 
 template <typename T>
@@ -448,7 +476,9 @@ typename QLinkedList<T>::iterator QLinkedList<T>::erase(typename QLinkedList<T>:
 template <typename T>
 typename QLinkedList<T>::iterator QLinkedList<T>::erase(iterator pos)
 {
-    detach();
+    if (d->ref.isShared())
+        pos = detach_helper2(pos);
+
     Node *i = pos.i;
     if (i != e) {
         Node *n = i;
diff --git a/tests/auto/corelib/tools/qlinkedlist/qlinkedlist.pro b/tests/auto/corelib/tools/qlinkedlist/qlinkedlist.pro
new file mode 100644
index 0000000000..439bf03707
--- /dev/null
+++ b/tests/auto/corelib/tools/qlinkedlist/qlinkedlist.pro
@@ -0,0 +1,5 @@
+CONFIG += testcase parallel_test
+TARGET = tst_qlinkedlist
+QT = core testlib
+SOURCES = tst_qlinkedlist.cpp
+DEFINES += QT_DISABLE_DEPRECATED_BEFORE=0
diff --git a/tests/auto/corelib/tools/qlinkedlist/tst_qlinkedlist.cpp b/tests/auto/corelib/tools/qlinkedlist/tst_qlinkedlist.cpp
new file mode 100644
index 0000000000..b1a9946a0f
--- /dev/null
+++ b/tests/auto/corelib/tools/qlinkedlist/tst_qlinkedlist.cpp
@@ -0,0 +1,77 @@
+/****************************************************************************
+**
+** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/legal
+**
+** This file is part of the test suite of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and Digia.  For licensing terms and
+** conditions see http://qt.digia.com/licensing.  For further information
+** use the contact form at http://qt.digia.com/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Digia gives you certain additional
+** rights.  These rights are described in the Digia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include <QtTest/QtTest>
+#include <QLinkedList>
+
+class tst_QLinkedList : public QObject
+{
+    Q_OBJECT
+private slots:
+    void eraseValidIteratorsOnSharedList() const;
+};
+
+void tst_QLinkedList::eraseValidIteratorsOnSharedList() const
+{
+    QLinkedList<int> a, b;
+    a.append(5);
+    a.append(10);
+    a.append(20);
+    a.append(20);
+    a.append(20);
+    a.append(20);
+    a.append(30);
+
+    QLinkedList<int>::iterator i = a.begin();
+    ++i;
+    ++i;
+    ++i;
+    b = a;
+    QLinkedList<int>::iterator r = a.erase(i);
+    QCOMPARE(b.size(), 7);
+    QCOMPARE(a.size(), 6);
+    --r;
+    --r;
+    QCOMPARE(*r, 10); // Ensure that number 2 instance was removed;
+}
+
+QTEST_MAIN(tst_QLinkedList)
+#include "tst_qlinkedlist.moc"
diff --git a/tests/auto/corelib/tools/tools.pro b/tests/auto/corelib/tools/tools.pro
index f8b2437d35..afa5e5b613 100644
--- a/tests/auto/corelib/tools/tools.pro
+++ b/tests/auto/corelib/tools/tools.pro
@@ -18,6 +18,7 @@ SUBDIRS=\
     qfreelist \
     qhash \
     qline \
+    qlinkedlist \
     qlist \
     qlocale \
     qmap \