3 files changed, 139 insertions, 0 deletions

diff --git a/common/storage.h b/common/storage.h
index bb8c1fa..a8c486c 100644
--- a/common/storage.h
+++ b/common/storage.h
@@ -109,6 +109,15 @@ public:
             const std::function<void(const DataStore::Error &error)> &errorHandler = std::function<void(const DataStore::Error &error)>()) const;
 
         /**
+         * Finds all the keys and values whose keys are in a given range
+         * (inclusive).
+         */
+        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.
          */
         bool contains(const QByteArray &uid);
diff --git a/common/storage_lmdb.cpp b/common/storage_lmdb.cpp
index bf631a8..4ac5724 100644
--- a/common/storage_lmdb.cpp
+++ b/common/storage_lmdb.cpp
@@ -551,6 +551,60 @@ 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() };
+    MDB_val idealLastKey = { .mv_size = (size_t)upperBound.size(), .mv_data = (void *)upperBound.constData() };
+    MDB_val lastKey = idealLastKey;
+    MDB_val currentKey;
+    MDB_val data;
+
+    // Find the first key in the range
+    int rc = mdb_cursor_get(cursor, &firstKey, &data, MDB_SET_RANGE);
+
+    if (rc != MDB_SUCCESS) {
+        // Nothing is greater or equal than the lower bound, meaning no result
+        mdb_cursor_close(cursor);
+        return 0;
+    }
+
+    currentKey = firstKey;
+
+    // If already bigger than the upper bound
+    if (mdb_cmp(d->transaction, d->dbi, &currentKey, &idealLastKey) > 0) {
+        mdb_cursor_close(cursor);
+        return 0;
+    }
+
+    do {
+        const auto currentBAKey = QByteArray::fromRawData((char *)currentKey.mv_data, currentKey.mv_size);
+        const auto currentBAValue = QByteArray::fromRawData((char *)data.mv_data, data.mv_size);
+        resultHandler(currentBAKey, currentBAValue);
+    } while (mdb_cursor_get(cursor, &currentKey, &data, MDB_NEXT) == MDB_SUCCESS &&
+             mdb_cmp(d->transaction, d->dbi, &currentKey, &idealLastKey) <= 0);
+
+    mdb_cursor_close(cursor);
+}
+
 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) {