Git commit 6e5b41e88d92c90df8e54d99163cea08f17d0554 by Christoph Cullmann.
Committed on 11/09/2016 at 20:37.
Pushed by cullmann into branch 'master'.

Fix sorted insert (aka flat_map like insert).

REVIEW: 128893
BUG: 367991

unit test covers more cases, in any case: should not corrupt your memory ;=
=3D)

M  +47   -0    autotests/unit/engine/documenturldbtest.cpp
M  +2    -12   src/engine/documenturldb.cpp
M  +27   -0    src/engine/idutils.h
M  +5    -29   src/engine/writetransaction.cpp

http://commits.kde.org/baloo/6e5b41e88d92c90df8e54d99163cea08f17d0554

diff --git a/autotests/unit/engine/documenturldbtest.cpp b/autotests/unit/e=
ngine/documenturldbtest.cpp
index 448821b..db919b8 100644
--- a/autotests/unit/engine/documenturldbtest.cpp
+++ b/autotests/unit/engine/documenturldbtest.cpp
@@ -147,6 +147,53 @@ private Q_SLOTS:
         QCOMPARE(db.getId(id, QByteArray("file")), id1);
         QCOMPARE(db.getId(id, QByteArray("file2")), id2);
     }
+
+    void testSortedIdInsert()
+    {
+        // test sorted insert used in Baloo::DocumentUrlDB::add, bug 367991
+        std::vector<quint64> test;
+        test.push_back(9);
+
+        // shall not crash
+        sortedIdInsert(test, quint64(1));
+
+        // stuff shall be ok inserted
+        QVERIFY(test.size() =3D=3D 2);
+        QVERIFY(test[0] =3D=3D 1);
+        QVERIFY(test[1] =3D=3D 9);
+
+        // shall not crash
+        sortedIdInsert(test, quint64(1));
+
+        // no insert please
+        QVERIFY(test.size() =3D=3D 2);
+
+        // shall not crash
+        sortedIdInsert(test, quint64(10));
+
+        // stuff shall be ok inserted
+        QVERIFY(test.size() =3D=3D 3);
+        QVERIFY(test[0] =3D=3D 1);
+        QVERIFY(test[1] =3D=3D 9);
+        QVERIFY(test[2] =3D=3D 10);
+
+        // shall not crash
+        sortedIdInsert(test, quint64(2));
+
+        // stuff shall be ok inserted
+        QVERIFY(test.size() =3D=3D 4);
+        QVERIFY(test[0] =3D=3D 1);
+        QVERIFY(test[1] =3D=3D 2);
+        QVERIFY(test[2] =3D=3D 9);
+        QVERIFY(test[3] =3D=3D 10);
+
+        // shall not crash
+        sortedIdInsert(test, quint64(2));
+
+        // no insert please
+        QVERIFY(test.size() =3D=3D 4);
+    }
+
 protected:
     MDB_env* m_env;
     MDB_txn* m_txn;
diff --git a/src/engine/documenturldb.cpp b/src/engine/documenturldb.cpp
index 5083e7a..ef2a22c 100644
--- a/src/engine/documenturldb.cpp
+++ b/src/engine/documenturldb.cpp
@@ -112,18 +112,8 @@ void DocumentUrlDB::add(quint64 id, quint64 parentId, =
const QByteArray& name)
 =

     QVector<quint64> subDocs =3D idTreeDb.get(parentId);
 =

-    // Find if the id exists
-    if (subDocs.isEmpty()) {
-        subDocs.append(id);
-    } else {
-        auto it =3D std::upper_bound(subDocs.begin(), subDocs.end(), id);
-
-        // Merge the id if it does not
-        auto prev =3D it - 1;
-        if (*prev !=3D id) {
-            subDocs.insert(it, id);
-        }
-    }
+    // insert if not there
+    sortedIdInsert(subDocs, id);
 =

     idTreeDb.put(parentId, subDocs);
 =

diff --git a/src/engine/idutils.h b/src/engine/idutils.h
index cc7da9c..e1d513f 100644
--- a/src/engine/idutils.h
+++ b/src/engine/idutils.h
@@ -85,6 +85,33 @@ inline quint32 idToDeviceId(quint64 id)
     return arr[0];
 }
 =

+
+template<typename T, typename V>
+inline void sortedIdInsert(T& vec, const V& id)
+{
+    /**
+     * search with normal <
+     */
+    const auto i(std::lower_bound(vec.begin(), vec.end(), id));
+
+    /**
+     * end reached or element found smaller?
+     * =3D> insert new element!
+     */
+    if (i =3D=3D vec.end() || (id !=3D *i))
+        vec.insert(i, id);
+}
+
+template<typename T, typename V>
+inline void sortedIdRemove(T& vec, const V& id)
+{
+    const int idx =3D vec.indexOf(id);
+    if (idx >=3D 0) {
+        vec.remove(idx);
+    }
+}
+
+
 }
 =

 #endif
diff --git a/src/engine/writetransaction.cpp b/src/engine/writetransaction.=
cpp
index 3808970..171f5ba 100644
--- a/src/engine/writetransaction.cpp
+++ b/src/engine/writetransaction.cpp
@@ -30,6 +30,7 @@
 #include "documenttimedb.h"
 #include "documentdatadb.h"
 #include "mtimedb.h"
+#include "idutils.h"
 =

 using namespace Baloo;
 =

@@ -243,31 +244,6 @@ QVector< QByteArray > WriteTransaction::replaceTerms(q=
uint64 id, const QVector<Q
     return addTerms(id, terms);
 }
 =

-template<typename T>
-static void insert(QVector<T>& vec, const T& id)
-{
-    if (vec.isEmpty()) {
-        vec.append(id);
-    } else {
-        auto it =3D std::upper_bound(vec.begin(), vec.end(), id);
-
-        // Merge the id if it does not
-        auto prev =3D it - 1;
-        if (*prev !=3D id) {
-            vec.insert(it, id);
-        }
-    }
-}
-
-template<typename T>
-static void removeOne(QVector<T>& vec, const T& id)
-{
-    const int idx =3D vec.indexOf(id);
-    if (idx >=3D 0) {
-        vec.remove(idx);
-    }
-}
-
 void WriteTransaction::commit()
 {
     PostingDB postingDB(m_dbis.postingDbi, m_txn);
@@ -289,23 +265,23 @@ void WriteTransaction::commit()
             quint64 id =3D op.data.docId;
 =

             if (op.type =3D=3D AddId) {
-                insert(list, id);
+                sortedIdInsert(list, id);
 =

                 if (!op.data.positions.isEmpty()) {
                     if (!fetchedPositionList) {
                         positionList =3D positionDB.get(term);
                         fetchedPositionList =3D true;
                     }
-                    insert(positionList, op.data);
+                    sortedIdInsert(positionList, op.data);
                 }
             }
             else {
-                removeOne(list, id);
+                sortedIdRemove(list, id);
                 if (!fetchedPositionList) {
                     positionList =3D positionDB.get(term);
                     fetchedPositionList =3D true;
                 }
-                removeOne(positionList, PositionInfo(id));
+                sortedIdRemove(positionList, PositionInfo(id));
             }
         }
=20