[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kde-commits
Subject:    [baloo] /: Fix sorted insert (aka flat_map like insert).
From:       Christoph Cullmann <cullmann () kde ! org>
Date:       2016-09-11 20:40:40
Message-ID: E1bjBYO-0001SB-CX () code ! kde ! org
[Download RAW message or body]

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 ;=)

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/engine/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() == 2);
+        QVERIFY(test[0] == 1);
+        QVERIFY(test[1] == 9);
+
+        // shall not crash
+        sortedIdInsert(test, quint64(1));
+
+        // no insert please
+        QVERIFY(test.size() == 2);
+
+        // shall not crash
+        sortedIdInsert(test, quint64(10));
+
+        // stuff shall be ok inserted
+        QVERIFY(test.size() == 3);
+        QVERIFY(test[0] == 1);
+        QVERIFY(test[1] == 9);
+        QVERIFY(test[2] == 10);
+
+        // shall not crash
+        sortedIdInsert(test, quint64(2));
+
+        // stuff shall be ok inserted
+        QVERIFY(test.size() == 4);
+        QVERIFY(test[0] == 1);
+        QVERIFY(test[1] == 2);
+        QVERIFY(test[2] == 9);
+        QVERIFY(test[3] == 10);
+
+        // shall not crash
+        sortedIdInsert(test, quint64(2));
+
+        // no insert please
+        QVERIFY(test.size() == 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 = idTreeDb.get(parentId);
 
-    // Find if the id exists
-    if (subDocs.isEmpty()) {
-        subDocs.append(id);
-    } else {
-        auto it = std::upper_bound(subDocs.begin(), subDocs.end(), id);
-
-        // Merge the id if it does not
-        auto prev = it - 1;
-        if (*prev != 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?
+     * => insert new element!
+     */
+    if (i == vec.end() || (id != *i))
+        vec.insert(i, id);
+}
+
+template<typename T, typename V>
+inline void sortedIdRemove(T& vec, const V& id)
+{
+    const int idx = vec.indexOf(id);
+    if (idx >= 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(quint64 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 = std::upper_bound(vec.begin(), vec.end(), id);
-
-        // Merge the id if it does not
-        auto prev = it - 1;
-        if (*prev != id) {
-            vec.insert(it, id);
-        }
-    }
-}
-
-template<typename T>
-static void removeOne(QVector<T>& vec, const T& id)
-{
-    const int idx = vec.indexOf(id);
-    if (idx >= 0) {
-        vec.remove(idx);
-    }
-}
-
 void WriteTransaction::commit()
 {
     PostingDB postingDB(m_dbis.postingDbi, m_txn);
@@ -289,23 +265,23 @@ void WriteTransaction::commit()
             quint64 id = op.data.docId;
 
             if (op.type == AddId) {
-                insert(list, id);
+                sortedIdInsert(list, id);
 
                 if (!op.data.positions.isEmpty()) {
                     if (!fetchedPositionList) {
                         positionList = positionDB.get(term);
                         fetchedPositionList = true;
                     }
-                    insert(positionList, op.data);
+                    sortedIdInsert(positionList, op.data);
                 }
             }
             else {
-                removeOne(list, id);
+                sortedIdRemove(list, id);
                 if (!fetchedPositionList) {
                     positionList = positionDB.get(term);
                     fetchedPositionList = true;
                 }
-                removeOne(positionList, PositionInfo(id));
+                sortedIdRemove(positionList, PositionInfo(id));
             }
         }
 
[prev in list] [next in list] [prev in thread] [next in thread]