Add and test findAllInRange for ranged lookups

3 files changed, 143 insertions, 0 deletions

diff --git a/common/storage.h b/common/storage.h
index bb8c1fa..1fde8e6 100644
--- a/common/storage.h
+++ b/common/storage.h
@@ -108,6 +108,11 @@ public:
         void findLatest(const QByteArray &uid, const std::function<void(const QByteArray &key, const QByteArray &value)> &resultHandler,
             const std::function<void(const DataStore::Error &error)> &errorHandler = std::function<void(const DataStore::Error &error)>()) const;
 
+        int findAllInRange(const QByteArray &lowerBound, const QByteArray &upperBound,
+            const std::function<void(const QByteArray &key, const QByteArray &value)> &resultHandler,
+            const std::function<void(const DataStore::Error &error)> &errorHandler =
+                std::function<void(const DataStore::Error &error)>()) const;
+
         /**
          * Returns true if the database contains the substring key.
          */
diff --git a/common/storage_lmdb.cpp b/common/storage_lmdb.cpp
index 5fb1d0f..bd9bdce 100644
--- a/common/storage_lmdb.cpp
+++ b/common/storage_lmdb.cpp
@@ -558,6 +558,68 @@ void DataStore::NamedDatabase::findLatest(const QByteArray &k, const std::functi
     return;
 }
 
+int DataStore::NamedDatabase::findAllInRange(const QByteArray &lowerBound, const QByteArray &upperBound,
+    const std::function<void(const QByteArray &key, const QByteArray &value)> &resultHandler,
+    const std::function<void(const DataStore::Error &error)> &errorHandler) const
+{
+    if (!d || !d->transaction) {
+        // Not an error. We rely on this to read nothing from non-existing databases.
+        return 0;
+    }
+
+    MDB_cursor *cursor;
+    if (int rc = mdb_cursor_open(d->transaction, d->dbi, &cursor)) {
+        // Invalid arguments can mean that the transaction doesn't contain the db dbi
+        Error error(d->name.toLatin1() + d->db, getErrorCode(rc),
+            QByteArray("Error during mdb_cursor_open: ") + QByteArray(mdb_strerror(rc)) +
+                ". Lower bound: " + lowerBound + " Upper bound: " + upperBound);
+        errorHandler ? errorHandler(error) : d->defaultErrorHandler(error);
+        return 0;
+    }
+
+    int numberOfRetrievedValues = 0;
+
+    MDB_val firstKey = { .mv_size = (size_t)lowerBound.size(), .mv_data = (void *)lowerBound.constData() },
+            idealLastKey = { .mv_size = (size_t)upperBound.size(), .mv_data = (void *)upperBound.constData() },
+            lastKey = idealLastKey, currentKey;
+    MDB_val reference;
+
+    // Find the last key past the range
+    int rc = mdb_cursor_get(cursor, &lastKey, &reference, MDB_SET_RANGE);
+
+    // If only equal, move forward one spot
+    if (rc == MDB_SUCCESS && mdb_cmp(d->transaction, d->dbi, &lastKey, &idealLastKey) == 0) {
+        rc = mdb_cursor_get(cursor, &lastKey, &reference, MDB_NEXT);
+    }
+
+    bool untilEnd = false;
+    if (rc != MDB_SUCCESS) {
+        // Nothing is greater than the upper bound, meaning search until the end
+        untilEnd = true;
+    }
+
+    // Find the first key in the range
+    rc = mdb_cursor_get(cursor, &firstKey, &reference, MDB_SET_RANGE);
+
+    if (rc != MDB_SUCCESS) {
+        // Nothing is greater or equal than the lower bound, meaning no result
+        return 0;
+    }
+
+    currentKey = firstKey;
+
+    do {
+        // If we have a stopping point and this is the stopping point
+        if (!untilEnd && mdb_cmp(d->transaction, d->dbi, &currentKey, &lastKey) == 0) {
+            break;
+        }
+
+        const auto currentBAKey = QByteArray::fromRawData((char *)currentKey.mv_data, currentKey.mv_size);
+        const auto currentBAValue = QByteArray::fromRawData((char *)reference.mv_data, reference.mv_size);
+        resultHandler(currentBAKey, currentBAValue);
+    } while (mdb_cursor_get(cursor, &currentKey, &reference, MDB_NEXT) == MDB_SUCCESS);
+}
+
 qint64 DataStore::NamedDatabase::getSize()
 {
     if (!d || !d->transaction) {
diff --git a/tests/storagetest.cpp b/tests/storagetest.cpp
index 618f9d0..bca91b1 100644
--- a/tests/storagetest.cpp
+++ b/tests/storagetest.cpp
@@ -462,6 +462,82 @@ private slots:
         QCOMPARE(result, QByteArray("value2"));
     }
 
+    void setupTestFindRange(Sink::Storage::DataStore::NamedDatabase &db)
+    {
+        db.write("0002", "value1");
+        db.write("0003", "value2");
+        db.write("0004", "value3");
+        db.write("0005", "value4");
+    }
+
+    void testFindRangeOptimistic()
+    {
+        Sink::Storage::DataStore store(testDataPath, dbName, Sink::Storage::DataStore::ReadWrite);
+        auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
+        auto db = transaction.openDatabase("test", nullptr, false);
+        setupTestFindRange(db);
+        QByteArrayList results;
+        db.findAllInRange("0002", "0004", [&](const QByteArray &key, const QByteArray &value) { results << value; });
+
+        QCOMPARE(results, (QByteArrayList{"value1", "value2", "value3"}));
+    }
+
+    void testFindRangeNothing()
+    {
+        Sink::Storage::DataStore store(testDataPath, dbName, Sink::Storage::DataStore::ReadWrite);
+        auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
+        auto db = transaction.openDatabase("test", nullptr, false);
+        setupTestFindRange(db);
+
+        QByteArrayList results1;
+        db.findAllInRange("0000", "0001", [&](const QByteArray &key, const QByteArray &value) { results1 << value; });
+        QCOMPARE(results1, QByteArrayList{});
+
+        QByteArrayList results2;
+        db.findAllInRange("0000", "0000", [&](const QByteArray &key, const QByteArray &value) { results2 << value; });
+        QCOMPARE(results2, QByteArrayList{});
+
+        QByteArrayList results3;
+        db.findAllInRange("0006", "0010", [&](const QByteArray &key, const QByteArray &value) { results3 << value; });
+        QCOMPARE(results3, QByteArrayList{});
+
+        QByteArrayList results4;
+        db.findAllInRange("0010", "0010", [&](const QByteArray &key, const QByteArray &value) { results4 << value; });
+        QCOMPARE(results4, QByteArrayList{});
+    }
+
+    void testFindRangeSingle()
+    {
+        Sink::Storage::DataStore store(testDataPath, dbName, Sink::Storage::DataStore::ReadWrite);
+        auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
+        auto db = transaction.openDatabase("test", nullptr, false);
+        setupTestFindRange(db);
+
+        QByteArrayList results1;
+        db.findAllInRange("0004", "0004", [&](const QByteArray &key, const QByteArray &value) { results1 << value; });
+        QCOMPARE(results1, QByteArrayList{"value3"});
+    }
+
+    void testFindRangeOutofBounds()
+    {
+        Sink::Storage::DataStore store(testDataPath, dbName, Sink::Storage::DataStore::ReadWrite);
+        auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
+        auto db = transaction.openDatabase("test", nullptr, false);
+        setupTestFindRange(db);
+
+        QByteArrayList results1;
+        db.findAllInRange("0000", "0010", [&](const QByteArray &key, const QByteArray &value) { results1 << value; });
+        QCOMPARE(results1, (QByteArrayList{"value1", "value2", "value3", "value4"}));
+
+        QByteArrayList results2;
+        db.findAllInRange("0003", "0010", [&](const QByteArray &key, const QByteArray &value) { results2 << value; });
+        QCOMPARE(results2, (QByteArrayList{"value2", "value3", "value4"}));
+
+        QByteArrayList results3;
+        db.findAllInRange("0000", "0003", [&](const QByteArray &key, const QByteArray &value) { results3 << value; });
+        QCOMPARE(results3, (QByteArrayList{"value1", "value2"}));
+    }
+
     void testTransactionVisibility()
     {
         auto readValue = [](const Sink::Storage::DataStore::NamedDatabase &db, const QByteArray) {