From 0456cef80e909e545897ac9eb107fd832d4dfde8 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?R=C3=A9mi=20Nicole?= Date: Thu, 24 May 2018 12:10:24 +0200 Subject: Add findAllInRange function in the storage layer Summary: In preparation of the support for ranged queries. Notes: Since they are pretty similar, it could be nice to refactor `scan` and `findAllInRange` to use common 3rd function Test Plan: This is tested in storagetest.cpp Reviewers: cmollekopf Tags: #sink Differential Revision: https://phabricator.kde.org/D13066 --- common/storage.h | 9 ++++++ common/storage_lmdb.cpp | 54 +++++++++++++++++++++++++++++++++++ tests/storagetest.cpp | 76 +++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 139 insertions(+) diff --git a/common/storage.h b/common/storage.h index bb8c1fa..a8c486c 100644 --- a/common/storage.h +++ b/common/storage.h @@ -108,6 +108,15 @@ public: void findLatest(const QByteArray &uid, const std::function &resultHandler, const std::function &errorHandler = std::function()) 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 &resultHandler, + const std::function &errorHandler = + std::function()) const; + /** * Returns true if the database contains the substring key. */ 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 &resultHandler, + const std::function &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, ¤tKey, &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, ¤tKey, &data, MDB_NEXT) == MDB_SUCCESS && + mdb_cmp(d->transaction, d->dbi, ¤tKey, &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) { -- cgit v1.2.3