Adding QKeyValueStore.

QKeyValueStore is a simple key-value storage system,
that is very space efficient.

Change-Id: I569bfe5c99b75057bc2cfcf60e13253af7524af2
Reviewed-by: Ali Akhtarzada <ali.akhtarzada@nokia.com>

37 files changed, 3801 insertions, 32 deletions

diff --git a/src/daemon/daemon.pri b/src/daemon/daemon.pri
index 1deaa06..13fbc91 100644
--- a/src/daemon/daemon.pri
+++ b/src/daemon/daemon.pri
@@ -1,5 +1,6 @@
 include($$PWD/../3rdparty/btree/btree.pri)
 include($$PWD/../hbtree/hbtree.pri)
+include($$PWD/../qkeyvaluestore/qkeyvaluestore.pri)
 include($$PWD/../common/common.pri)
 
 DEFINES += $$quote(QT_BEGIN_MOC_NAMESPACE=\"QT_USE_NAMESPACE QT_USE_NAMESPACE_JSONDB\")
diff --git a/src/daemon/jsondbbtree.cpp b/src/daemon/jsondbbtree.cpp
index 4efc5bb..efb1ed2 100644
--- a/src/daemon/jsondbbtree.cpp
+++ b/src/daemon/jsondbbtree.cpp
@@ -51,7 +51,7 @@ QT_BEGIN_NAMESPACE_JSONDB
 JsonDbBtree::JsonDbBtree()
     : mBtree(new Btree())
 {
-#ifndef JSONDB_USE_HBTREE
+#if !defined(JSONDB_USE_HBTREE) && !defined(JSONDB_USE_KVS)
     mBtree->setAutoCompactRate(jsondbSettings->compactRate());
 #endif
 }
@@ -71,6 +71,10 @@ bool JsonDbBtree::open(const QString &filename, OpenFlags flags)
         mode = HBtree::ReadOnly;
     mBtree->setOpenMode(mode);
     return mBtree->open();
+#elif defined(JSONDB_USE_KVS)
+    Q_UNUSED(flags);
+    mBtree->setSyncThreshold(0);
+    return mBtree->open();
 #else
     QBtree::DbFlags dbFlags = QBtree::UseSyncMarker | QBtree::NoSync;
     if (flags & ReadOnly)
@@ -146,7 +150,7 @@ bool JsonDbBtree::rollback()
 void JsonDbBtree::setAutoCompactRate(int rate) const
 {
     Q_ASSERT(mBtree);
-#ifdef JSONDB_USE_HBTREE
+#if defined(JSONDB_USE_HBTREE) || defined(JSONDB_USE_KVS)
     Q_UNUSED(rate);
 #else
     mBtree->setAutoCompactRate(rate);
diff --git a/src/daemon/jsondbbtree.h b/src/daemon/jsondbbtree.h
index 6798509..a84bffc 100644
--- a/src/daemon/jsondbbtree.h
+++ b/src/daemon/jsondbbtree.h
@@ -42,18 +42,28 @@
 #ifndef JSONDB_MANAGED_BTREE_H
 #define JSONDB_MANAGED_BTREE_H
 
-#define JSONDB_USE_HBTREE
+/*
+ * There are three BTree implementations:
+ * - JSONDB_USE_AOB: Original Append Only BTree.
+ * - JSONDB_USE_HBTREE: Ali's hybrid BTree.
+ * - JSONDB_USE_KVS: Carlos' Key-Value Store.
+ */
 
 #include "jsondb-global.h"
-
-#ifndef JSONDB_USE_HBTREE
-#include "qbtree.h"
-#include "qbtreecursor.h"
-#include "qbtreetxn.h"
-#else
+#define JSONDB_USE_KVS
+#if defined(JSONDB_USE_HBTREE)
 #include "hbtree.h"
 #include "hbtreecursor.h"
 #include "hbtreetransaction.h"
+#elif defined(JSONDB_USE_KVS)
+#include "qkeyvaluestore.h"
+#include "qkeyvaluestorecursor.h"
+#include "qkeyvaluestoretxn.h"
+#else
+// We assume JSONDB_USE_AOB
+#include "qbtree.h"
+#include "qbtreecursor.h"
+#include "qbtreetxn.h"
 #endif
 
 QT_BEGIN_HEADER
@@ -72,7 +82,9 @@ public:
 
 #ifdef JSONDB_USE_HBTREE
     typedef HBtree Btree;
-#else
+#elif defined(JSONDB_USE_KVS)
+    typedef QKeyValueStore Btree;
+#else // JSONDB_USE_AOB
     typedef QBtree Btree;
 #endif
 
diff --git a/src/qkeyvaluestore/qkeyvaluestore.cpp b/src/qkeyvaluestore/qkeyvaluestore.cpp
new file mode 100644
index 0000000..9aceb40
--- /dev/null
+++ b/src/qkeyvaluestore/qkeyvaluestore.cpp
@@ -0,0 +1,664 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/
+**
+** This file is part of the QtAddOn.JsonDb module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qkeyvaluestore.h"
+#include "qkeyvaluestore_p.h"
+#include "qkeyvaluestoreentry.h"
+#include "qkeyvaluestoretxn.h"
+
+#include <QDataStream>
+#include <QDateTime>
+#include <QCryptographicHash>
+
+#include <QDebug>
+
+#include <unistd.h>
+
+QKeyValueStore::QKeyValueStore() :
+    p(0)
+{
+}
+
+QKeyValueStore::QKeyValueStore(const QString &name)
+{
+    p = new QKeyValueStorePrivate(this, name);
+}
+
+bool QKeyValueStore::open()
+{
+    if (!p)
+        return false;
+    return p->open() ? false : true;
+}
+
+bool QKeyValueStore::close()
+{
+    if (!p)
+        return false;
+    return p->close() ? false : true;
+}
+
+void QKeyValueStore::setFileName(QString name)
+{
+    if (p)
+        return;
+    p = new QKeyValueStorePrivate(this, name);
+}
+
+QKeyValueStoreTxn *QKeyValueStore::beginRead()
+{
+    Q_ASSERT(p);
+    return p->beginRead();
+}
+
+QKeyValueStoreTxn *QKeyValueStore::beginWrite()
+{
+    Q_ASSERT(p);
+    return p->beginWrite();
+}
+
+bool QKeyValueStore::sync()
+{
+    Q_ASSERT(p);
+    return p->sync();
+}
+
+void QKeyValueStore::setSyncThreshold(quint32 threshold)
+{
+    p->m_syncThreshold = threshold;
+    if (0 == threshold)
+        p->m_autoSync = false;
+    else
+        p->m_autoSync = true;
+}
+
+QKeyValueStoreTxn *QKeyValueStore::writeTransaction() const
+{
+    Q_ASSERT(p);
+    return p->writeTransaction();
+}
+
+/*
+ * PRIVATE  API BELOW
+ */
+
+QKeyValueStorePrivate::QKeyValueStorePrivate(QKeyValueStore *parent, const QString &name) :
+    m_parent(parent),
+    m_name(name),
+    m_writeTransaction(0),
+    m_currentTag(0),
+    // By default we resort to automatic syncing. Set threshold to zero to disable this.
+    m_autoSync(true),
+    m_runCompaction(false),
+    m_needCompaction(false),
+    // To prevent compaction from happening
+    // Same threshold as AOB
+    m_compactThreshold(1000),
+    m_compactableOperations(0),
+    m_state(Closed),
+    m_pendingBytes(0),
+    m_syncThreshold(1024),
+    m_marker(0x55AAAA55),
+    m_ongoingReadTransactions(0),
+    m_ongoingWriteTransactions(0)
+{
+    m_file = new QKeyValueStoreFile(m_name + ".dat");
+}
+
+QKeyValueStorePrivate::~QKeyValueStorePrivate()
+{
+    syncToDisk();
+    delete m_file;
+}
+
+int QKeyValueStorePrivate::open()
+{
+    bool result = false;
+    Q_ASSERT(m_file);
+    // Let's open the data file.
+    result = m_file->open();
+    if (!result) {
+        m_state = Error;
+        return -1;
+    }
+    // Small optimization, if the file size is 0 then just return
+    if ((qint64)0 == m_file->size()) {
+        m_state = Ready;
+        return 0;
+    }
+    // We need to examine the btree file and see if we have a valid btree.
+    quint64 btreeTimestamp = checkTreeContents();
+    // Now, let's check the file contents.
+    quint64 dataTimestamp = checkFileContents();
+    /*
+     * 0 is not a valid timestamp... well it is if the journal was started
+     * exactly on the epoch but that is very unlikely.
+     */
+    if ((0 == dataTimestamp) || (0 == btreeTimestamp) || (dataTimestamp != btreeTimestamp)) {
+        // Well, we need to rebuild the btree.
+        rebuildBTree();
+    }
+    m_state = Ready;
+    return 0;
+}
+
+int QKeyValueStorePrivate::close()
+{
+    if (m_state == Error)
+        return -1;
+    syncToDisk();
+    m_file->close();
+    m_state = Closed;
+    return 0;
+}
+
+bool QKeyValueStorePrivate::sync()
+{
+    syncToDisk();
+    return true;
+}
+
+/*
+ * This is an expensive operation, however it can reduce the file size
+ * considerably.
+ * We traverse the tree and copy only those elements that are needed,
+ * discarding the history.
+ */
+bool QKeyValueStorePrivate::compact()
+{
+    // Are the any ongoing write transactions going on?
+    // If so, abort and do it later.
+    if (m_writeTransaction) {
+        m_runCompaction = true;
+        return true;
+    }
+    quint32 numberOfElements = m_offsets.count();
+    // We walk the tree and copy elements to the new file.
+    QKeyValueStoreFile *file = new QKeyValueStoreFile(m_name + ".dat.cpt", true);
+    if (!file->open()) {
+        return false;
+    }
+    if (file->write(&numberOfElements, sizeof(quint32)) != sizeof(quint32))
+        return false;
+    QMap<QByteArray, qint64>::iterator i;
+    for (i = m_offsets.begin(); i != m_offsets.end(); ++i) {
+        qint64 offset = i.value();
+        // Retrieve the current data
+        int readBytes = 0, writeBytes = 0;
+        m_file->setOffset(offset);
+        quint32 rawRecoveredKeySize = 0, rawValueSize = 0;
+        char *rawRecoveredKey = 0, *rawValue = 0;
+        // Read the key
+        readBytes = m_file->read((void *)&rawRecoveredKeySize, sizeof(quint32));
+        if (readBytes < 0)
+            return false;
+        if ((quint32)readBytes < sizeof(quint32))
+            return false;
+        QByteArray recoveredKey;
+        if ((quint32)recoveredKey.capacity() < rawRecoveredKeySize) {
+            recoveredKey.resize(rawRecoveredKeySize);
+        }
+        rawRecoveredKey = recoveredKey.data();
+        readBytes = m_file->read((void *)rawRecoveredKey, rawRecoveredKeySize);
+        if (readBytes < 0)
+            return false;
+        if ((quint32)readBytes < rawRecoveredKeySize)
+            return false;
+        // Read the operation
+        quint8 operation = 0;
+        readBytes = m_file->read((void *)&operation, sizeof(quint8));
+        if (readBytes < 0)
+            return false;
+        if ((quint32)readBytes < sizeof(quint8))
+            return false;
+        // Read the value
+        readBytes = m_file->read((void *)&rawValueSize, sizeof(quint32));
+        if (readBytes < 0)
+            return false;
+        if ((quint32)readBytes < sizeof(quint32))
+            return false;
+        QByteArray value;
+        if ((quint32)value.capacity() < rawValueSize) {
+            value.resize(rawValueSize);
+        }
+        rawValue = value.data();
+        readBytes = m_file->read((void *)rawValue, rawValueSize);
+        if (readBytes < 0)
+            return false;
+        if ((quint32)readBytes < rawValueSize)
+            return false;
+        // Read  the hash
+        quint32 hash = 0;
+        readBytes = m_file->read((void *)&hash, sizeof(quint32));
+        if (readBytes < 0)
+            return false;
+        if ((quint32)readBytes < sizeof(quint32))
+            return false;
+        // Check that the data is valid
+        if (hash != qHash(recoveredKey + value)) {
+            return false;
+        }
+        // First fix the offset
+        i.value() = file->size();
+        // Now write the key
+        writeBytes = file->write(&rawRecoveredKeySize, sizeof(quint32));
+        if (writeBytes < 0)
+            return false;
+        writeBytes = file->write(rawRecoveredKey, rawRecoveredKeySize);
+        if (writeBytes < 0)
+            return false;
+        // Write the operation
+        writeBytes = file->write(&operation, sizeof(quint8));
+        if (writeBytes < 0)
+            return false;
+        // Write the value
+        writeBytes = file->write(&rawValueSize, sizeof(quint32));
+        if (writeBytes < 0)
+            return false;
+        writeBytes = file->write(rawValue, rawValueSize);
+        if (writeBytes < 0)
+            return false;
+        // Write the hash
+        writeBytes = file->write(&hash, sizeof(quint32));
+        if (writeBytes < 0)
+            return false;
+    }
+    // Write the last tag to close the file and mark preserve the state
+    int bytes = file->write(&m_currentTag, sizeof(quint32));
+    if (bytes < 0)
+        return false;
+    file->close();
+    m_file->close();
+    QFile::copy(m_name + ".dat", m_name + ".old");
+    QFile::remove(m_name + ".dat");
+    QFile::copy(m_name + ".dat.cpt", m_name + ".dat");
+    QFile::remove(m_name + ".dat.cpt");
+    delete m_file;
+    delete file;
+    m_file = new QKeyValueStoreFile(m_name + ".dat", false);
+    m_runCompaction = false;
+    m_compactableOperations = 0;
+    m_state = DataToSync;
+    return m_file->open();
+}
+
+QKeyValueStoreTxn *QKeyValueStorePrivate::beginRead()
+{
+    QKeyValueStoreTxn *txn = new QKeyValueStoreTxn(QKeyValueStoreTxn::ReadOnly);
+    Q_ASSERT(txn);
+    txn->setStore(this);
+    txn->setBTree(m_parent);
+    m_ongoingReadTransactions++;
+    return txn;
+}
+
+QKeyValueStoreTxn *QKeyValueStorePrivate::beginWrite()
+{
+    if (m_ongoingWriteTransactions)
+        return (QKeyValueStoreTxn *)0;
+    QKeyValueStoreTxn *txn = new QKeyValueStoreTxn(QKeyValueStoreTxn::ReadWrite);
+    Q_ASSERT(txn);
+    txn->setStore(this);
+    txn->setBTree(m_parent);
+    m_writeTransaction = txn;
+    m_ongoingWriteTransactions++;
+    return txn;
+}
+
+bool QKeyValueStorePrivate::isWriting() const
+{
+    return m_ongoingWriteTransactions ? true : false;
+}
+
+QKeyValueStoreTxn *QKeyValueStorePrivate::writeTransaction()
+{
+    return m_writeTransaction;
+}
+
+void QKeyValueStorePrivate::addEntry(QKeyValueStoreEntry *entry)
+{
+    if (!entry)
+        return;
+    QByteArray key = entry->key();
+    if (entry->operation() == QKeyValueStoreEntry::Remove) {
+        m_offsets.remove(key);
+        m_pendingBytes += key.size();
+        m_compactableOperations++;
+    } else {
+        if (m_offsets.contains(key))
+            m_compactableOperations++;
+        m_offsets[key] = entry->offset();
+        m_pendingBytes += (entry->value().size() + key.size());
+    }
+    m_state = DataToSync;
+}
+
+void QKeyValueStorePrivate::reportReadyWrite()
+{
+    // Do we need to sync to disk?
+    if (m_autoSync)
+        if (m_syncThreshold <= m_pendingBytes)
+            syncToDisk();
+    m_ongoingWriteTransactions--;
+    m_writeTransaction = 0;
+    if (m_runCompaction)
+        compact();
+}
+
+void QKeyValueStorePrivate::reportReadyRead()
+{
+    // Not much to do, just fix the counters...
+    m_ongoingReadTransactions--;
+}
+
+void QKeyValueStorePrivate::syncToDisk()
+{
+    if (m_compactableOperations >= m_compactThreshold)
+        compact();
+    if (m_state != DataToSync)
+        return;
+    // Write the marker
+    m_file->write((void *)&m_marker, sizeof(quint32));
+    // We write the timestamp + hash
+    quint64 timestamp = QDateTime::currentMSecsSinceEpoch();
+    m_file->write((void *)&timestamp, sizeof(quint64));
+    quint32 hash = qHash(timestamp);
+    m_file->write((void *)&hash, sizeof(quint32));
+    // Now we sync
+    m_file->sync();
+    // Sync the btree
+    syncTree(timestamp);
+    // Reset the counter
+    m_pendingBytes = 0;
+    m_state = Ready;
+}
+
+void QKeyValueStorePrivate::syncTree(quint64 timestamp)
+{
+    QKeyValueStoreFile btree(m_name + ".btr", true);
+    if (!btree.open())
+        return;
+    quint32 count = m_offsets.count();
+    btree.write((void *)&count, sizeof(quint32));
+    QMapIterator<QByteArray, qint64> i(m_offsets);
+    while (i.hasNext()) {
+        i.next();
+        QByteArray key = i.key();
+        int keySize = key.size();
+        qint64 value = i.value();
+        char *keyData = key.data();
+        btree.write((void *)&keySize, sizeof(int));
+        btree.write(keyData, (quint32)keySize);
+        btree.write((void *)&value, sizeof(qint64));
+    }
+    // Now the timestamp
+    btree.write((void *)&timestamp, sizeof(quint64));
+    quint32 hash = qHash(timestamp);
+    btree.write((void *)&hash, sizeof(quint32));
+}
+
+/*
+ * The situation goes like this: we don't know how many timestamps we have,
+ * we might not have timestamps at all. We skipped the reading process when
+ * opening the journal to speed up things. That means that we need to read
+ * things here and find out the timestamps. At the same time we need to rebuild
+ * the tree using the journal entries.
+ * For that reason we resort to read the journal from scratch and rebuild the
+ * tree from scratch.
+ */
+int QKeyValueStorePrivate::rebuildBTree()
+{
+    if (!m_offsets.isEmpty())
+        m_offsets.clear();
+    if (!m_dataMarks.isEmpty())
+        m_dataMarks.clear();
+    m_file->setOffset((qint64)0);
+    quint32 count = 0, found = 0;
+    m_file->read((void *)&count, sizeof(quint32));
+    while (found < count) {
+        char *rawKey = 0, *rawValue = 0;
+        quint32 rawKeySize = 0, rawValueSize = 0;
+        quint8 operation = 0;
+        quint32 hash = 0xFFFFFFFF;
+        qint64 offset = 0;
+        offset = m_file->offset();
+        m_file->read((void *)&rawKeySize, sizeof(quint32));
+        QByteArray key;
+        key.resize(rawKeySize);
+        rawKey = key.data();
+        m_file->read((void *)rawKey, rawKeySize);
+        m_file->read((void *)&operation, sizeof(quint8));
+        m_file->read((void *)&rawValueSize, sizeof(quint32));
+        QByteArray value;
+        value.resize(rawValueSize);
+        rawValue = value.data();
+        m_file->read((void *)rawValue, rawValueSize);
+        m_file->read((void *)&hash, sizeof(quint32));
+        // Calculate the hash
+        quint32 computedHash = 0xFFFFFFFF;
+        switch (operation) {
+        case QKeyValueStoreEntry::Add:
+            computedHash = qHash(key + value);
+            m_offsets[key] = offset;
+            break;
+        case QKeyValueStoreEntry::Remove:
+            computedHash = qHash(key);
+            m_offsets.remove(key);
+            break;
+        default:
+            break;
+        }
+        /*
+         * The question here is what to do if the entry hash does not match?
+         * Marking the journal as invalid is an option, but then we lose
+         * all the entries. A simple option is to ignore the entry with
+         * a bad hash, but in that case we might run into troubles afterwards
+         * because there might be dangling entries.
+         * On second thoughts, the whole purpose of having a per entry hash
+         * is to be able to detect which entries are problematic, so we will
+         * just ignore the entries with a bad hash.
+         */
+        if (computedHash != hash)
+            m_offsets.remove(key);
+        found++;
+        if (count == found) {
+            quint32 tag = 0;
+            m_file->read((void *)&tag, sizeof(quint32));
+            // Do we have a marker?
+            quint32 marker = 0;
+            quint64 fileTimestamp = 0;
+            m_file->read((void *)&marker, sizeof(quint32));
+            if (marker == m_marker) {
+                // Yes we do!
+                m_file->read((void *)&fileTimestamp, sizeof(quint64));
+                m_file->read((void *)&hash, sizeof(quint32));
+                // Is it a valid hash?
+                if (hash == qHash(fileTimestamp)) {
+                    /*
+                     * There are two options here, to accept the previous
+                     * entries as valid or to remove them.
+                     * We already know that each entry is a valid one, so
+                     * the only real problem is the fact that the marker is
+                     * invalid. Ignoring the entries will lose all the
+                     * information we have recovered. Accepting them means
+                     * we accept that the sync failed but the data is ok.
+                     * For now we will accept the entries but do not record
+                     * the marker. This way we just keep going and if we find
+                     * a new valid marker we just use that one instead.
+                     */
+                    m_dataMarks[fileTimestamp] = m_file->offset();
+                }
+                /*
+                 * The tag is written at commit time, while the marker is
+                 * written at sync time. That is why we include the tag
+                 * regardless of the hash check.
+                 */
+                m_currentTag = tag;
+                m_file->read((void *)&count, sizeof(quint32));
+            } else
+                count = marker;
+            found = 0;
+        }
+    }
+    return 0;
+}
+
+/*
+ * In this method we check if the last thing written to it was a marker.
+ * If so, we just read the last timestamp and go on from there.
+ * If not we return 0 to indicate that we need to replay the journal and
+ * rebuild the tree.
+ */
+quint64 QKeyValueStorePrivate::checkFileContents()
+{
+    qint64 size = m_file->size();
+    int result = 0;
+    if (size == 0)
+        return 0;
+    // tag - marker - timestamp - hash
+    qint64 offset = size - (sizeof(quint32) + sizeof(quint32) + sizeof(quint64) + sizeof(quint32));
+    m_file->setOffset(offset);
+    quint32 tempTag = 0, tempMarker = 0;
+    result = m_file->read((void *)&tempTag, sizeof(quint32));
+    if (result <= 0)
+        return 0;
+    result = m_file->read((void *)&tempMarker, sizeof(quint32));
+    if (result <= 0)
+        return 0;
+    if (tempMarker == m_marker) {
+        quint64 tempTimestamp = 0;
+        quint32 tempHash = 0;
+        result = m_file->read((void *)&tempTimestamp, sizeof(quint64));
+        if (result <= 0)
+            return 0;
+        result = m_file->read((void *)&tempHash, sizeof(quint32));
+        if (result <= 0)
+            return 0;
+        if (tempHash == qHash(tempTimestamp)) {
+            m_dataMarks[tempTimestamp] = offset;
+            m_currentTag = tempTag;
+            return tempTimestamp;
+        }
+    }
+    /*
+     * If the file was not closed correctly, we should abort the read operation.
+     * We return 0 to signal that we need to rebuild the tree, since there will
+     * be some operations missing.
+     * While rebuilding the tree we can start from a known point and check the
+     * new entries.
+     */
+    return 0;
+}
+
+/*
+ * This method goes through the btree file and checks its contents.
+ * There is only one btree version at any given time, so we try to build
+ * it and if there are problems with the file we just bail out.
+ */
+quint64 QKeyValueStorePrivate::checkTreeContents()
+{
+    QString name = m_name + ".btr";
+    QKeyValueStoreFile btree(name);
+    if (!btree.open()) {
+        return 0;
+    }
+    if (btree.size() == 0) {
+        return 0;
+    }
+    quint32 count = 0, found = 0;
+    quint64 timestamp = 0;
+    int result = 0;
+    result = btree.read((void *)&count, sizeof(quint32));
+    if (result <=0)
+        return 0;
+    while (found < count) {
+        qint64 offset = 0;
+        // The key is already in SHA1 format
+        char *rawKey = 0;
+        quint32 rawKeySize;
+        result = btree.read((void *)&rawKeySize, sizeof(quint32));
+        // <= 0 means either EOF or problems, therefore we just abort
+        if (result <= 0) {
+            if (!m_offsets.isEmpty())
+                m_offsets.clear();
+            return 0;
+        }
+        QByteArray key;
+        if ((quint32)key.capacity() < rawKeySize) {
+            key.resize(rawKeySize);
+        }
+        rawKey = key.data();
+        result = btree.read((void *)rawKey, rawKeySize);
+        if (result <= 0) {
+            if (!m_offsets.isEmpty())
+                m_offsets.clear();
+            return 0;
+        }
+        result = btree.read((void *)&offset, sizeof(qint64));
+        if (result <= 0) {
+            if (!m_offsets.isEmpty())
+                m_offsets.clear();
+            return 0;
+        }
+        m_offsets[key] = offset;
+        found++;
+        if (count == found) {
+            // Check the timestamp
+            result = btree.read((void *)&timestamp, sizeof(quint64));
+            if (result <= 0) {
+                if (!m_offsets.isEmpty())
+                    m_offsets.clear();
+                return 0;
+            }
+            quint32 hash = 0;
+            result = btree.read((void *)&hash, sizeof(quint32));
+            if (result <= 0) {
+                if (!m_offsets.isEmpty())
+                    m_offsets.clear();
+                return 0;
+            }
+            if (hash != qHash(timestamp))
+                timestamp = 0;
+            break;
+        }
+    }
+    return timestamp;
+}
diff --git a/src/qkeyvaluestore/qkeyvaluestore.h b/src/qkeyvaluestore/qkeyvaluestore.h
new file mode 100644
index 0000000..25181f2
--- /dev/null
+++ b/src/qkeyvaluestore/qkeyvaluestore.h
@@ -0,0 +1,144 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/
+**
+** This file is part of the QtAddOn.JsonDb module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QKEYVALUESTORE_H
+#define QKEYVALUESTORE_H
+
+#include <QString>
+#include <QByteArray>
+#include <QMap>
+
+#include "qkeyvaluestoretxn.h"
+#include "qkeyvaluestore_p.h"
+#include "qkeyvaluestorecursor.h"
+
+class QKeyValueStore {
+    QKeyValueStorePrivate *p;
+public:
+    QKeyValueStore();
+    QKeyValueStore(const QString &name);
+    bool open();
+    bool close();
+    bool compact() { return p->compact(); }
+    bool dump() { return false; }
+    bool rollback() { return false; }
+    QString fileName() const { return p->m_name; }
+    void setFileName(QString name);
+    // Transaction support
+    QKeyValueStoreTxn *beginRead();
+    QKeyValueStoreTxn *beginWrite();
+    // Operations required by the BTree implementation
+    bool isWriting() const { return p->isWriting(); }
+    bool sync();
+    quint64 count() const { return p->m_offsets.count(); }
+    quint32 tag() const { return p->m_currentTag; }
+    void setCacheSize(int size) { Q_UNUSED(size); }
+    int cacheSize() const { return 0; }
+    typedef int (*CompareFunction)(const QByteArray &, const QByteArray &);
+    void setCompareFunction(CompareFunction cmp) { Q_UNUSED(cmp); Q_ASSERT(false); }
+
+    quint32 syncThreshold() const { return p->m_syncThreshold; }
+    void setSyncThreshold(quint32 threshold);
+    quint32 compactThreshold() const { return p->m_compactThreshold; }
+    void setCompactThreshold(quint32 threshold) { p->m_compactThreshold = threshold; }
+    // This is mostly needed for testing purposes.
+    int markers() const { return p->m_dataMarks.count(); }
+
+    // To support jsondbtree.h
+    struct Stat
+    {
+        Stat()
+            : numCommits(0), numSyncs(0), numBranchPages(0), numLeafPages(0), numOverflowPages(0), numEntries(0),
+              numBranchSplits(0), numLeafSplits(0), depth(0),
+              reads(0), hits(0), writes(0), psize(0), ksize(0)
+        {}
+
+        int numCommits;
+        int numSyncs;
+        int numBranchPages;
+        int numLeafPages;
+        int numOverflowPages;
+        int numEntries;
+        int numBranchSplits;
+        int numLeafSplits;
+        int depth;
+
+        qint32 reads;
+        qint32 hits;
+        qint32 writes;
+        quint32 psize;
+        quint32 ksize;
+
+        Stat &operator += (const Stat &o)
+        {
+            reads += o.reads;
+            hits += o.hits;
+            writes += o.writes;
+            psize = o.psize;
+            ksize = o.ksize;
+
+            numCommits += o.numCommits;
+            numSyncs += o.numSyncs;
+            numEntries += o.numEntries;
+            numBranchPages += o.numBranchPages;
+            numBranchSplits += o.numBranchSplits;
+            numLeafPages += o.numLeafPages;
+            numLeafSplits += numLeafSplits;
+            numOverflowPages += o.numOverflowPages;
+
+            depth = qMax(depth, o.depth);
+            return *this;
+        }
+    };
+    typedef QKeyValueStoreCursor CursorType;
+    typedef QKeyValueStoreTxn TransactionType;
+    typedef Stat StatType;
+    QKeyValueStoreTxn *writeTransaction() const;
+    QString errorMessage() const { return QString("Some error"); }
+    Stat stats_;
+    const Stat& stats() const { return stats_; }
+
+private:
+    // We put this here for now, since we are not using it.
+    CompareFunction m_cmp;
+};
+
+#endif // QKEYVALUESTORE_H
diff --git a/src/qkeyvaluestore/qkeyvaluestore.pri b/src/qkeyvaluestore/qkeyvaluestore.pri
new file mode 100644
index 0000000..637a488
--- /dev/null
+++ b/src/qkeyvaluestore/qkeyvaluestore.pri
@@ -0,0 +1,19 @@
+INCLUDEPATH += $$PWD/
+
+HEADERS += \
+    $$PWD/qkeyvaluestore.h \
+    $$PWD/qkeyvaluestore_p.h \
+    $$PWD/qkeyvaluestorecursor.h \
+    $$PWD/qkeyvaluestorecursor_p.h \
+    $$PWD/qkeyvaluestoreentry.h \
+    $$PWD/qkeyvaluestoretxn.h \
+    $$PWD/qkeyvaluestoretxn_p.h \
+    $$PWD/qkeyvaluestorefile.h \
+    $$PWD/qkeyvaluestorefile_p.h
+
+SOURCES += \
+    $$PWD/qkeyvaluestore.cpp \
+    $$PWD/qkeyvaluestorecursor.cpp \
+    $$PWD/qkeyvaluestoreentry.cpp \
+    $$PWD/qkeyvaluestoretxn.cpp \
+    $$PWD/qkeyvaluestorefile.cpp
diff --git a/src/qkeyvaluestore/qkeyvaluestore_p.h b/src/qkeyvaluestore/qkeyvaluestore_p.h
new file mode 100644
index 0000000..c3ddd5c
--- /dev/null
+++ b/src/qkeyvaluestore/qkeyvaluestore_p.h
@@ -0,0 +1,107 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/
+**
+** This file is part of the QtAddOn.JsonDb module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QKEYVALUESTORE_P_H
+#define QKEYVALUESTORE_P_H
+
+#include <QString>
+#include <QByteArray>
+#include <QHash>
+#include <QFile>
+#include <QMap>
+#include <QQueue>
+#include <QDebug>
+
+#include "qkeyvaluestoreentry.h"
+#include "qkeyvaluestoretxn.h"
+#include "qkeyvaluestorefile.h"
+
+class QKeyValueStore;
+class QKeyValueStoreTxn;
+class QKeyValueStorePrivate {
+public:
+    QKeyValueStorePrivate(QKeyValueStore *parent, const QString &name);
+    ~QKeyValueStorePrivate();
+
+    // Public API Mirror
+    int open();
+    int close();
+    bool sync();
+    bool compact();
+    QKeyValueStoreTxn *beginRead();
+    QKeyValueStoreTxn *beginWrite();
+    bool isWriting() const;
+    QKeyValueStoreTxn *writeTransaction();
+    // This is for write transactions to report back.
+    void addEntry(QKeyValueStoreEntry *entry);
+    void reportReadyWrite();
+    void reportReadyRead();
+
+    // Internals
+    QKeyValueStore *m_parent;
+    QString m_name;
+    QKeyValueStoreTxn *m_writeTransaction;
+    QKeyValueStoreFile *m_file;
+    quint32 m_currentTag;
+    bool m_autoSync;
+    bool m_runCompaction;
+    bool m_needCompaction;
+    quint32 m_compactThreshold;
+    quint32 m_compactableOperations;
+    enum QKeyValueStoreState { Closed, Ready, DataToSync, RebuildBTree, Error = 0xFFFF };
+    QKeyValueStoreState m_state;
+    quint32 m_pendingBytes;
+    quint32 m_syncThreshold;
+    quint32 m_marker;
+    quint32 m_ongoingReadTransactions;
+    quint32 m_ongoingWriteTransactions;
+    QMap<quint64, qint64> m_dataMarks;
+    QMap<QByteArray, qint64> m_offsets;
+
+    // Internal methods, should not be called from the public class!!!
+    void syncToDisk();
+    void syncTree(quint64 timestamp);
+    int rebuildBTree();
+    quint64 checkFileContents();
+    quint64 checkTreeContents();
+};
+
+#endif // QKEYVALUESTORE_P_H
diff --git a/src/qkeyvaluestore/qkeyvaluestorecursor.cpp b/src/qkeyvaluestore/qkeyvaluestorecursor.cpp
new file mode 100644
index 0000000..dcaa759
--- /dev/null
+++ b/src/qkeyvaluestore/qkeyvaluestorecursor.cpp
@@ -0,0 +1,210 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/
+**
+** This file is part of the QtAddOn.JsonDb module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include <QByteArray>
+#include <QMap>
+#include <QDebug>
+
+#include "qkeyvaluestorecursor.h"
+
+QKeyValueStoreCursor::QKeyValueStoreCursor(QKeyValueStoreTxn *txn)
+{
+    p = new QKeyValueStoreCursorPrivate(txn);
+}
+
+QKeyValueStoreCursor::~QKeyValueStoreCursor()
+{
+    delete p;
+}
+
+bool QKeyValueStoreCursor::first()
+{
+    return p->first();
+}
+
+bool QKeyValueStoreCursor::last()
+{
+    return p->last();
+}
+
+bool QKeyValueStoreCursor::next()
+{
+    return p->next();
+}
+
+bool QKeyValueStoreCursor::previous()
+{
+    return p->prev();
+}
+
+bool QKeyValueStoreCursor::current(QByteArray *baKey, QByteArray *baValue) const
+{
+    return p->current(baKey, baValue);
+}
+
+bool QKeyValueStoreCursor::seek(const QByteArray &baKey)
+{
+    return p->seek(baKey);
+}
+
+bool QKeyValueStoreCursor::seekRange(const QByteArray &baKey)
+{
+    return p->seekRange(baKey);
+}
+
+/*
+ * PRIVATE API, DO NOT TOUCH THIS UNLESS YOU KNOW WHAT YOU ARE DOING!
+ */
+
+/*
+ * The cursor uses lazy fetching of values, that means that the cursor only
+ * gets the key when moving, and only if there is a call to current it
+ * retrieves the value.
+ */
+#if defined(JSONDB_USE_KVS_MULTIPLE_TRANSACTIONS)
+#define TXN_OFFSETS m_txn->p->m_offsets
+#else
+#define TXN_OFFSETS m_txn->p->m_store->m_offsets
+#endif
+
+// Joao's hack to get a const element
+template <class T> const T &const_(const T &t) { return t; }
+QKeyValueStoreCursorPrivate::QKeyValueStoreCursorPrivate(QKeyValueStoreTxn *txn) :
+    m_txn(txn)
+{
+    if (TXN_OFFSETS.isEmpty())
+        return;
+    m_cursor = TXN_OFFSETS.constBegin();
+    // Load the corresponding key
+    m_key = m_cursor.key();
+}
+
+QKeyValueStoreCursorPrivate::~QKeyValueStoreCursorPrivate()
+{
+}
+
+bool QKeyValueStoreCursorPrivate::first()
+{
+    if (TXN_OFFSETS.isEmpty())
+        return false;
+    // Move to the right position
+    m_cursor = TXN_OFFSETS.constBegin();
+    // Load the corresponding key
+    m_key = m_cursor.key();
+    return true;
+}
+
+bool QKeyValueStoreCursorPrivate::last()
+{
+    if (TXN_OFFSETS.isEmpty())
+        return false;
+    // Move to the right position
+    m_cursor = TXN_OFFSETS.constEnd();
+    m_cursor--;
+    // Load the corresponding key
+    m_key = m_cursor.key();
+    return true;
+}
+
+bool QKeyValueStoreCursorPrivate::next()
+{
+    if (TXN_OFFSETS.isEmpty())
+        return false;
+    m_cursor++;
+    if (m_cursor == TXN_OFFSETS.constEnd()) {
+        m_cursor--;
+        return false;
+    }
+    // Load the corresponding key
+    m_key = m_cursor.key();
+    return true;
+}
+
+bool QKeyValueStoreCursorPrivate::prev()
+{
+    if (TXN_OFFSETS.isEmpty())
+        return false;
+    if (m_cursor == TXN_OFFSETS.constBegin())
+        return false;
+    // Move to the right position
+    m_cursor--;
+    // Load the corresponding key
+    m_key = m_cursor.key();
+    return true;
+}
+
+/*
+ * Unless the transaction and the db are empty, current cannot return false.
+ */
+bool QKeyValueStoreCursorPrivate::current(QByteArray *baKey, QByteArray *baValue) const
+{
+    if (TXN_OFFSETS.isEmpty())
+        return false;
+    if (baKey)
+        *baKey = m_key;
+    // We use the transaction to find the item
+    if (baValue) {
+        if (!m_txn->get(m_key, baValue))
+            return false;
+        m_value = *baValue;
+    }
+    return true;
+}
+
+bool QKeyValueStoreCursorPrivate::seek(const QByteArray &baKey)
+{
+    if (TXN_OFFSETS.contains(baKey)) {
+        m_cursor = const_(TXN_OFFSETS).find(baKey);
+    } else {
+        return false;
+    }
+    m_key = m_cursor.key();
+    return true;
+}
+
+bool QKeyValueStoreCursorPrivate::seekRange(const QByteArray &baKey)
+{
+    m_cursor = const_(TXN_OFFSETS).lowerBound(baKey);
+    if (m_cursor == TXN_OFFSETS.constEnd())
+        return false;
+    m_key = m_cursor.key();
+    return true;
+}
diff --git a/src/qkeyvaluestore/qkeyvaluestorecursor.h b/src/qkeyvaluestore/qkeyvaluestorecursor.h
new file mode 100644
index 0000000..25ef4df
--- /dev/null
+++ b/src/qkeyvaluestore/qkeyvaluestorecursor.h
@@ -0,0 +1,75 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/
+**
+** This file is part of the QtAddOn.JsonDb module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QKEYVALUESTORECURSOR_H
+#define QKEYVALUESTORECURSOR_H
+
+#include "qkeyvaluestore.h"
+#include "qkeyvaluestoretxn.h"
+#include "qkeyvaluestorecursor_p.h"
+
+class QKeyValueStore;
+class QKeyValueStoreCursor
+{
+    QKeyValueStoreCursorPrivate *p;
+public:
+    explicit QKeyValueStoreCursor(QKeyValueStoreTxn *txn);
+    ~QKeyValueStoreCursor();
+
+    QKeyValueStoreCursor(const QKeyValueStoreCursor &other);
+    QKeyValueStoreCursor &operator=(const QKeyValueStoreCursor &other);
+
+    bool current(QByteArray *baKey, QByteArray *baValue) const;
+
+    const QByteArray &key() const { return p->m_key; }
+    const QByteArray &value() const { return p->m_value; }
+
+    bool first();
+    bool last();
+
+    bool next();
+    bool previous();
+
+    bool seek(const QByteArray &baKey);
+    bool seekRange(const QByteArray &baKey);
+};
+
+#endif // QKEYVALUESTORECURSOR_H
diff --git a/src/qkeyvaluestore/qkeyvaluestorecursor_p.h b/src/qkeyvaluestore/qkeyvaluestorecursor_p.h
new file mode 100644
index 0000000..2511b8b
--- /dev/null
+++ b/src/qkeyvaluestore/qkeyvaluestorecursor_p.h
@@ -0,0 +1,72 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/
+**
+** This file is part of the QtAddOn.JsonDb module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QKEYVALUESTORECURSOR_P_H
+#define QKEYVALUESTORECURSOR_P_H
+
+#include <QByteArray>
+
+#include "qkeyvaluestore.h"
+#include "qkeyvaluestoretxn.h"
+
+class QKeyValueStore;
+class QKeyValueStoreCursorPrivate {
+public:
+    QKeyValueStoreCursorPrivate(QKeyValueStore *store, bool commited = false);
+    QKeyValueStoreCursorPrivate(QKeyValueStoreTxn *txn);
+    ~QKeyValueStoreCursorPrivate();
+    // Public API Mirror
+    bool first();
+    bool last();
+    bool next();
+    bool prev();
+    bool current(QByteArray *baKey, QByteArray *baValue) const;
+    bool seek(const QByteArray &baKey);
+    bool seekRange(const QByteArray &baKey);
+
+    QByteArray m_key;
+    mutable QByteArray m_value;
+    QKeyValueStoreTxn *m_txn;
+    QMap<QByteArray, qint64>::const_iterator m_cursor;
+    QKeyValueStore *m_store;
+};
+
+#endif // QKEYVALUESTORECURSOR_P_H
diff --git a/src/qkeyvaluestore/qkeyvaluestoreentry.cpp b/src/qkeyvaluestore/qkeyvaluestoreentry.cpp
new file mode 100644
index 0000000..7c8280b
--- /dev/null
+++ b/src/qkeyvaluestore/qkeyvaluestoreentry.cpp
@@ -0,0 +1,63 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/
+**
+** This file is part of the QtAddOn.JsonDb module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qkeyvaluestoreentry.h"
+
+#include <QHash>
+
+QKeyValueStoreEntry::QKeyValueStoreEntry() :
+    m_key(""),
+    m_value(""),
+    m_offset(0),
+    m_hash(0xFFFFFFFF)
+{
+}
+
+quint32 QKeyValueStoreEntry::hash()
+{
+    if (m_key.isEmpty() && m_value.isEmpty())
+        return 0xFFFFFFFF;
+    if (m_value.isEmpty())
+        m_hash = qHash(m_key);
+    if (!m_key.isEmpty() && !m_value.isEmpty())
+        m_hash = qHash(m_key + m_value);
+    return m_hash;
+}
diff --git a/src/qkeyvaluestore/qkeyvaluestoreentry.h b/src/qkeyvaluestore/qkeyvaluestoreentry.h
new file mode 100644
index 0000000..97c6414
--- /dev/null
+++ b/src/qkeyvaluestore/qkeyvaluestoreentry.h
@@ -0,0 +1,70 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/
+**
+** This file is part of the QtAddOn.JsonDb module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QKEYVALUESTOREENTRY_H
+#define QKEYVALUESTOREENTRY_H
+
+#include <QByteArray>
+
+class QKeyValueStoreEntry
+{
+    QByteArray m_key;
+    QByteArray m_value;
+    qint64 m_offset;
+    quint32 m_hash;
+public:
+    QKeyValueStoreEntry();
+    enum QKeyValueStoreEntryOperation { Add = 0x00, Remove = 0x01};
+    QByteArray key() const { return m_key; }
+    void setKey(const QByteArray &key) { m_key = key; }
+    QByteArray value() const { return m_value; }
+    void setValue(const QByteArray &value) { m_value = value; }
+    qint64 offset() const { return m_offset; }
+    void setOffset(qint64 offset) { m_offset = offset; }
+    quint32 hash();
+private:
+    QKeyValueStoreEntryOperation m_operation;
+public:
+    quint8 operation() const { return (quint8)m_operation; }
+    void setOperation(QKeyValueStoreEntryOperation operation) { m_operation = operation; }
+};
+
+#endif // QDATASTORAGEENTRY_H
diff --git a/src/qkeyvaluestore/qkeyvaluestorefile.cpp b/src/qkeyvaluestore/qkeyvaluestorefile.cpp
new file mode 100644
index 0000000..7531888
--- /dev/null
+++ b/src/qkeyvaluestore/qkeyvaluestorefile.cpp
@@ -0,0 +1,140 @@
+#include "qkeyvaluestorefile.h"
+
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+
+QKeyValueStoreFile::QKeyValueStoreFile(QString name, bool truncate)
+{
+    p = new QKeyValueStoreFilePrivate(name, truncate);
+}
+
+QKeyValueStoreFile::~QKeyValueStoreFile()
+{
+    delete p;
+}
+
+bool QKeyValueStoreFile::open()
+{
+    return p->open();
+}
+
+int QKeyValueStoreFile::read(void *buffer, quint32 count)
+{
+    return p->read(buffer, count);
+}
+
+int QKeyValueStoreFile::write(void *buffer, quint32 count)
+{
+    return p->write(buffer, count);
+}
+
+void QKeyValueStoreFile::sync()
+{
+    p->sync();
+}
+
+qint64 QKeyValueStoreFile::size() const
+{
+    return p->size();
+}
+
+bool QKeyValueStoreFile::close()
+{
+    return p->close();
+}
+
+/*
+ * PRIVATE API BELOW!!!!
+ */
+
+int doOpen(const char *name, bool truncate)
+{
+    if (truncate)
+        return open(name,
+                    O_RDWR | O_CREAT | O_TRUNC,
+                    S_IRWXU |S_IRGRP );
+    return open(name,
+                O_RDWR | O_CREAT,
+                S_IRWXU |S_IRGRP );
+}
+
+int doClose(int fd)
+{
+    return close(fd);
+}
+
+QKeyValueStoreFilePrivate::QKeyValueStoreFilePrivate(QString name, bool truncate) :
+    m_name(name)
+{
+    m_fd = -1;
+    m_size = 0;
+    m_truncate = truncate;
+    m_offset = 0;
+}
+
+QKeyValueStoreFilePrivate::~QKeyValueStoreFilePrivate()
+{
+    if (m_fd >= 0)
+        doClose(m_fd);
+}
+
+bool QKeyValueStoreFilePrivate::open()
+{
+    m_fd = doOpen(m_name.toLocal8Bit().constData(), m_truncate);
+    if (m_fd < 0)
+        return false;
+    struct stat s;
+    int result = fstat(m_fd, &s);
+    if (result < 0) {
+        doClose(m_fd);
+        return false;
+    }
+    m_size = s.st_size;
+    return true;
+}
+
+int QKeyValueStoreFilePrivate::read(void *buffer, quint32 count)
+{
+    if (!buffer || m_fd < 0)
+        return -1;
+    ssize_t s = pread(m_fd, buffer, count, m_offset);
+    if (s < 0)
+        return s;
+    m_offset += s;
+    return s;
+}
+
+int QKeyValueStoreFilePrivate::write(void *buffer, quint32 count)
+{
+    if (!buffer || m_fd < 0)
+        return -1;
+    ssize_t s = pwrite(m_fd, buffer, count, m_size);
+    if (s < 0)
+        return s;
+    // The write was successful, update the counters.
+    m_size += s;
+    return s;
+}
+
+void QKeyValueStoreFilePrivate::sync()
+{
+    if (m_fd < 0)
+        return;
+    fsync(m_fd);
+}
+
+qint64 QKeyValueStoreFilePrivate::size()
+{
+    return m_size;
+}
+
+bool QKeyValueStoreFilePrivate::close()
+{
+    int result = doClose(m_fd);
+    if (result < 0)
+        return false;
+    m_fd = -1;
+    return true;
+}
diff --git a/src/qkeyvaluestore/qkeyvaluestorefile.h b/src/qkeyvaluestore/qkeyvaluestorefile.h
new file mode 100644
index 0000000..9239562
--- /dev/null
+++ b/src/qkeyvaluestore/qkeyvaluestorefile.h
@@ -0,0 +1,26 @@
+#ifndef QKEYVALUESTOREFILE_H
+#define QKEYVALUESTOREFILE_H
+
+#include <QDebug>
+#include <QString>
+
+#include "qkeyvaluestorefile_p.h"
+
+class QKeyValueStoreFile
+{
+    QKeyValueStoreFilePrivate *p;
+public:
+    QKeyValueStoreFile(QString name, bool truncate = false);
+    ~QKeyValueStoreFile();
+    bool open();
+    int read(void *buffer, quint32 count);
+    int write(void *buffer, quint32 count);
+    void sync();
+    qint64 size() const;
+    qint64 offset() const { return p->m_offset; }
+    void setOffset(qint64 offset) { p->m_offset = offset; }
+    bool close();
+    bool truncate() const { return p->m_truncate; }
+};
+
+#endif // QKEYVALUESTOREFILE_H
diff --git a/src/qkeyvaluestore/qkeyvaluestorefile_p.h b/src/qkeyvaluestore/qkeyvaluestorefile_p.h
new file mode 100644
index 0000000..c3374ba
--- /dev/null
+++ b/src/qkeyvaluestore/qkeyvaluestorefile_p.h
@@ -0,0 +1,29 @@
+#ifndef QKEYVALUESTOREFILE_P_H
+#define QKEYVALUESTOREFILE_P_H
+
+#include <QString>
+
+int doOpen(const char *name, bool truncate);
+int doClose(int fd);
+
+class QKeyValueStoreFilePrivate {
+public:
+    QKeyValueStoreFilePrivate(QString name, bool truncate = false);
+    ~QKeyValueStoreFilePrivate();
+
+    // Public API mirror
+    bool open();
+    int read(void *buffer, quint32 count);
+    int write(void *buffer, quint32 count);
+    void sync();
+    qint64 size();
+    bool close();
+
+    QString m_name;
+    qint64 m_size;
+    qint64 m_offset;
+    qint32 m_fd;
+    bool m_truncate;
+};
+
+#endif // QKEYVALUESTOREFILE_P_H
diff --git a/src/qkeyvaluestore/qkeyvaluestoretxn.cpp b/src/qkeyvaluestore/qkeyvaluestoretxn.cpp
new file mode 100644
index 0000000..40676a5
--- /dev/null
+++ b/src/qkeyvaluestore/qkeyvaluestoretxn.cpp
@@ -0,0 +1,329 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/
+**
+** This file is part of the QtAddOn.JsonDb module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qkeyvaluestoretxn.h"
+#include "qkeyvaluestoreentry.h"
+
+#include <QDataStream>
+#include <QHash>
+#include <QCryptographicHash>
+#include <QDebug>
+
+QKeyValueStoreTxn::QKeyValueStoreTxn(QKeyValueStoreTxnType type)
+{
+    bool readOnly = true;
+    switch (type) {
+    case ReadOnly:
+        break;
+    case ReadWrite:
+        readOnly = false;
+    default:
+        break;
+    }
+    p = new QKeyValueStoreTxnPrivate(readOnly);
+}
+
+QKeyValueStoreTxn::~QKeyValueStoreTxn()
+{
+    // Given that we might have a temporary write transaction we need to make
+    // sure that we don't leave any dangling pointers.
+    if (p->m_store->m_writeTransaction == this) {
+        if (p && p->m_store && p->m_store->m_writeTransaction)
+            p->m_store->reportReadyWrite();
+    }
+    delete p;
+}
+
+void QKeyValueStoreTxn::setStore(QKeyValueStorePrivate *store)
+{
+    p->m_store = store;
+#if defined(JSONDB_USE_KVS_MULTIPLE_TRANSACTIONS)
+    p->m_offsets = p->m_store->m_offsets;
+#endif
+}
+
+bool QKeyValueStoreTxn::get(const QByteArray &key, QByteArray *value)
+{
+    return p->get(key, value);
+}
+
+/*
+ * The transaction object is no longer valid after this.
+ */
+bool QKeyValueStoreTxn::commit(quint32 tag)
+{
+    bool result = p->commit(tag);
+    delete this;
+    return result;
+}
+
+/*
+ * The transaction object is no longer valid after this.
+ */
+bool QKeyValueStoreTxn::abort()
+{
+    bool result = p->abort();
+    delete this;
+    return result;
+}
+
+bool QKeyValueStoreTxn::put(const QByteArray &key, const QByteArray &value)
+{
+    return p->put(key, value);
+}
+
+bool QKeyValueStoreTxn::remove(const QByteArray &key)
+{
+    return p->remove(key);
+}
+
+/*
+ * PRIVATE  API BELOW
+ */
+
+#if defined(JSONDB_USE_KVS_MULTIPLE_TRANSACTIONS)
+#define TXN_OFFSETS m_offsets
+#else
+#define TXN_OFFSETS m_store->m_offsets
+#endif
+QKeyValueStoreTxnPrivate::QKeyValueStoreTxnPrivate(bool readonly)
+{
+    m_readonly = readonly;
+    m_incommingBytes = 0;
+    m_tag = 0;
+#if !defined(JSONDB_USE_KVS_MULTIPLE_TRANSACTIONS)
+    m_localModifications = false;
+#endif
+}
+
+QKeyValueStoreTxnPrivate::~QKeyValueStoreTxnPrivate()
+{
+}
+
+bool QKeyValueStoreTxnPrivate::put(const QByteArray &key, const QByteArray &value)
+{
+    Q_ASSERT(!m_readonly);
+    m_incommingBytes += (key.size() + value.size());
+    QKeyValueStoreEntry * entry = new QKeyValueStoreEntry();
+    entry->setKey(key);
+    entry->setOperation(QKeyValueStoreEntry::Add);
+    entry->setValue(value);
+    m_incomming[key] = entry;
+#if !defined(JSONDB_USE_KVS_MULTIPLE_TRANSACTIONS)
+    m_localModifications = true;
+#endif
+    TXN_OFFSETS[key] = 0;
+
+    return true;
+}
+
+bool QKeyValueStoreTxnPrivate::remove(const QByteArray &key)
+{
+    // First of all, is the key stored on disk?
+    if (TXN_OFFSETS.contains(key)) {
+        // Record the operation and remove it.
+        m_incommingBytes += key.size();
+        QKeyValueStoreEntry *entry = new QKeyValueStoreEntry();
+        entry->setKey(key);
+        entry->setOperation(QKeyValueStoreEntry::Remove);
+        m_incomming[key] = entry;
+#if !defined(JSONDB_USE_KVS_MULTIPLE_TRANSACTIONS)
+        m_localModifications = true;
+#endif
+        TXN_OFFSETS.remove(key);
+        return true;
+    }
+    // Is the key on the incomming queue?
+    if (m_incomming.contains(key)) {
+        m_incomming.remove(key);
+        // Since we add "phantom" elements, we need to delete those too!
+#if !defined(JSONDB_USE_KVS_MULTIPLE_TRANSACTIONS)
+        m_localModifications = true;
+#endif
+        TXN_OFFSETS.remove(key);
+        return true;
+    }
+    return false;
+}
+
+bool QKeyValueStoreTxnPrivate::get(const QByteArray &key, QByteArray *value)
+{
+    int readBytes = 0;
+    qint64 offset = -1;
+    if (!value) {
+        return false;
+    }
+    // Is it in the buffer?
+    if (m_incomming.contains(key)) {
+        QKeyValueStoreEntry *entry = m_incomming.value(key);
+        if (entry->operation() == QKeyValueStoreEntry::Add) {
+            *value = entry->value();
+            return true;
+        }
+        // If the last operation was a remove operation we need to signal that by saying not found
+        return false;
+    }
+    // Is it on the file?
+    if (!TXN_OFFSETS.contains(key)) {
+        return false;
+    }
+    offset = TXN_OFFSETS.value(key);
+    if (offset == 0) {
+        // This is an impossible situation, if offset == 0 then it should be in the incomming queue.
+        return false;
+    }
+    m_store->m_file->setOffset(offset);
+    quint32 rawRecoveredKeySize = 0, rawValueSize = 0;
+    char *rawRecoveredKey = 0, *rawValue = 0;
+    readBytes = m_store->m_file->read((void *)&rawRecoveredKeySize, sizeof(quint32));
+    if (readBytes < 0)
+        return false;
+    if ((quint32)readBytes < sizeof(quint32))
+        return false;
+    QByteArray recoveredKey;
+    if ((quint32)recoveredKey.capacity() < rawRecoveredKeySize) {
+        recoveredKey.resize(rawRecoveredKeySize);
+    }
+    rawRecoveredKey = recoveredKey.data();
+    readBytes = m_store->m_file->read((void *)rawRecoveredKey, rawRecoveredKeySize);
+    if (readBytes < 0)
+        return false;
+    if ((quint32)readBytes < rawRecoveredKeySize)
+        return false;
+    quint8 operation = 0;
+    readBytes = m_store->m_file->read((void *)&operation, sizeof(quint8));
+    if (readBytes < 0)
+        return false;
+    if ((quint32)readBytes < sizeof(quint8))
+        return false;
+    readBytes = m_store->m_file->read((void *)&rawValueSize, sizeof(quint32));
+    if (readBytes < 0)
+        return false;
+    if ((quint32)readBytes < sizeof(quint32))
+        return false;
+    if ((quint32)value->capacity() < rawValueSize) {
+        value->resize(rawValueSize);
+    }
+    rawValue = value->data();
+    readBytes = m_store->m_file->read((void *)rawValue, rawValueSize);
+    if (readBytes < 0)
+        return false;
+    if ((quint32)readBytes < rawValueSize)
+        return false;
+    quint32 hash = 0;
+    readBytes = m_store->m_file->read((void *)&hash, sizeof(quint32));
+    if (readBytes < 0)
+        return false;
+    if ((quint32)readBytes < sizeof(quint32))
+        return false;
+    // Do we have the right data?
+    if (recoveredKey != key) {
+        return false;
+    }
+    // Check that the data is valid
+    if (hash != qHash(recoveredKey + *value)) {
+        return false;
+    }
+    return true;
+}
+
+bool QKeyValueStoreTxnPrivate::commit(quint32 tag)
+{
+    if (m_readonly)
+        return false;
+    if (m_incomming.isEmpty())
+        return true;
+    // First the number of objects
+    quint32 count = m_incomming.count();
+    m_store->m_file->write((void *)&count, sizeof(quint32));
+    foreach (QKeyValueStoreEntry *entry, m_incomming) {
+        QByteArray key = entry->key();
+        quint32 keySize = key.size();
+        QByteArray value = entry->value();
+        quint32 valueSize = value.size();
+        quint8 operation = entry->operation();
+        quint32 hash = entry->hash();
+        char *valueData = value.data();
+        entry->setOffset(m_store->m_file->size());
+        m_store->m_file->write((void *)&keySize, sizeof(quint32));
+        m_store->m_file->write((void *)key.constData(), keySize);
+        m_store->m_file->write((void *)&operation, sizeof(quint8));
+        m_store->m_file->write((void *)&valueSize, sizeof(quint32));
+        m_store->m_file->write((void *)valueData, valueSize);
+        m_store->m_file->write((void *)&hash, sizeof(quint32));
+        m_store->addEntry(entry);
+        // Adjust the counters
+        m_incommingBytes -= (keySize + valueSize);
+    }
+    m_tag = tag;
+    m_store->m_file->write((void *)&tag, sizeof(quint32));
+    qDeleteAll(m_incomming);
+    m_incomming.clear();
+    m_store->m_currentTag = m_tag;
+    m_store->reportReadyWrite();
+    return true;
+}
+
+bool QKeyValueStoreTxnPrivate::abort()
+{
+    if (m_incomming.isEmpty())
+        return true;
+    qDeleteAll(m_incomming);
+    m_incomming.clear();
+    m_incommingBytes = 0;
+#if !defined(JSONDB_USE_KVS_MULTIPLE_TRANSACTIONS)
+    // Remove phantom elements from the offsets
+    if (m_localModifications) {
+        QMap<QByteArray, qint64>::iterator i = TXN_OFFSETS.begin();
+        while (i != TXN_OFFSETS.end()) {
+            if (i.value() == (qint64)0)
+                i = TXN_OFFSETS.erase(i);
+            else
+                ++i;
+        }
+    } // No modifications, just go on!
+#endif
+    if (m_readonly)
+        m_store->reportReadyRead();
+    else
+        m_store->reportReadyWrite();
+    return true;
+}
diff --git a/src/qkeyvaluestore/qkeyvaluestoretxn.h b/src/qkeyvaluestore/qkeyvaluestoretxn.h
new file mode 100644
index 0000000..5a17f5b
--- /dev/null
+++ b/src/qkeyvaluestore/qkeyvaluestoretxn.h
@@ -0,0 +1,83 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/
+**
+** This file is part of the QtAddOn.JsonDb module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QKEYVALUESTORETXN_H
+#define QKEYVALUESTORETXN_H
+
+#include <QMap>
+#include <QByteArray>
+
+#include "qkeyvaluestore_p.h"
+#include "qkeyvaluestoretxn_p.h"
+
+class QKeyValueStoreCursor;
+class QKeyValueStoreCursorPrivate;
+
+class QKeyValueStoreTxn
+{
+    friend class QKeyValueStoreCursor;
+    friend class QKeyValueStoreCursorPrivate;
+    QKeyValueStoreTxnPrivate *p;
+    Q_DISABLE_COPY(QKeyValueStoreTxn)
+public:
+    enum QKeyValueStoreTxnType { ReadOnly, ReadWrite };
+    QKeyValueStoreTxn(QKeyValueStoreTxnType type);
+    ~QKeyValueStoreTxn();
+    void setStore(QKeyValueStorePrivate *store);
+    quint32 tag() const { return p->m_tag; }
+    bool isReadOnly() const { return p->m_readonly; }
+    bool isReadWrite() const { return !p->m_readonly; }
+    QKeyValueStore *btree() const { return p->m_btree; }
+    void setBTree(QKeyValueStore *btree) { p->m_btree = btree; }
+
+    // Writing needs to be done by the store itself.
+    bool put(const QByteArray &key, const QByteArray &value);
+    bool remove(const QByteArray &key);
+
+    // Reading can be done in parallel.
+    bool get(const QByteArray &key, QByteArray *value);
+
+    // Closing operations
+    bool commit(quint32 tag);
+    bool abort();
+};
+
+#endif // QKEYVALUESTORETXN_H
diff --git a/src/qkeyvaluestore/qkeyvaluestoretxn_p.h b/src/qkeyvaluestore/qkeyvaluestoretxn_p.h
new file mode 100644
index 0000000..4eb0a1e
--- /dev/null
+++ b/src/qkeyvaluestore/qkeyvaluestoretxn_p.h
@@ -0,0 +1,85 @@
+/****************************************************************************
+**
+** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: http://www.qt-project.org/
+**
+** This file is part of the QtAddOn.JsonDb module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** GNU Lesser General Public License Usage
+** This file may be used under the terms of the GNU Lesser General Public
+** License version 2.1 as published by the Free Software Foundation and
+** appearing in the file LICENSE.LGPL included in the packaging of this
+** file. Please review the following information to ensure the GNU Lesser
+** General Public License version 2.1 requirements will be met:
+** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU General
+** Public License version 3.0 as published by the Free Software Foundation
+** and appearing in the file LICENSE.GPL included in the packaging of this
+** file. Please review the following information to ensure the GNU General
+** Public License version 3.0 requirements will be met:
+** http://www.gnu.org/copyleft/gpl.html.
+**
+** Other Usage
+** Alternatively, this file may be used in accordance with the terms and
+** conditions contained in a signed written agreement between you and Nokia.
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QKEYVALUESTORETXN_P_H
+#define QKEYVALUESTORETXN_P_H
+
+#include "qkeyvaluestore.h"
+#include "qkeyvaluestore_p.h"
+
+#include <QMap>
+#include <QHash>
+#include <QByteArray>
+#include <QFile>
+
+class QKeyValueStore;
+class QKeyValueStoreTxnPrivate {
+public:
+    QKeyValueStoreTxnPrivate(bool readonly = true);
+    ~QKeyValueStoreTxnPrivate();
+    bool put(const QByteArray &key, const QByteArray &value);
+    bool remove(const QByteArray &key);
+    bool get(const QByteArray &key, QByteArray *value);
+    bool commit(quint32 tag);
+    bool abort();
+
+    bool m_readonly;
+    quint32 m_incommingBytes;
+    quint32 m_tag;
+    QKeyValueStore *m_btree;
+    // This is all the data we need, these are all the entries we care about when writing.
+    QMap<QByteArray, QKeyValueStoreEntry *> m_incomming;
+#if defined(JSONDB_USE_KVS_MULTIPLE_TRANSACTIONS)
+    /*
+     * The reason this is protected is because for this version we assume
+     * only one transaction at all times, therefore there is no need to
+     * keep track of the changes.
+     */
+    // We need this in order to preserve the state.
+    QMap<QByteArray, qint64> m_offsets;
+#else
+    // Since we modified the QMap directly we need to mark it.
+    bool m_localModifications;
+#endif
+    QKeyValueStorePrivate *m_store;
+};
+
+#endif // QKEYVALUESTORETXN_P_H
diff --git a/tests/auto/accesscontrol/testjsondb.cpp b/tests/auto/accesscontrol/testjsondb.cpp
index 4339934..81760ee 100644
--- a/tests/auto/accesscontrol/testjsondb.cpp
+++ b/tests/auto/accesscontrol/testjsondb.cpp
@@ -135,7 +135,7 @@ TestJsonDb::TestJsonDb() :
 void TestJsonDb::removeDbFiles()
 {
     QStringList filters;
-    filters << QLatin1String("*.db")
+    filters << QLatin1String("*.db*")
             << "objectFile.bin" << "objectFile2.bin";
     QStringList lst = QDir().entryList(filters);
     foreach (const QString &fileName, lst)
diff --git a/tests/auto/auto.pro b/tests/auto/auto.pro
index dc24337..5e28f20 100644
--- a/tests/auto/auto.pro
+++ b/tests/auto/auto.pro
@@ -15,4 +15,5 @@ SUBDIRS = \
     queries \
     qjsondbwatcher \
     jsonstream \
-    hbtree
+    hbtree \
+    qkeyvaluestore
diff --git a/tests/auto/client/test-jsondb-client.cpp b/tests/auto/client/test-jsondb-client.cpp
index 81290c5..fee8172 100644
--- a/tests/auto/client/test-jsondb-client.cpp
+++ b/tests/auto/client/test-jsondb-client.cpp
@@ -209,7 +209,7 @@ TestJsonDbClient::~TestJsonDbClient()
 void TestJsonDbClient::removeDbFiles()
 {
 #ifndef DONT_START_SERVER
-    QStringList lst = QDir().entryList(QStringList() << QLatin1String("*.db"));
+    QStringList lst = QDir().entryList(QStringList() << QLatin1String("*.db*"));
     lst << "objectFile.bin" << "objectFile2.bin";
     foreach (const QString &fileName, lst)
         QFile::remove(fileName);
diff --git a/tests/auto/daemon/testjsondb.cpp b/tests/auto/daemon/testjsondb.cpp
index ce2781e..04d7e73 100644
--- a/tests/auto/daemon/testjsondb.cpp
+++ b/tests/auto/daemon/testjsondb.cpp
@@ -270,7 +270,7 @@ TestJsonDb::TestJsonDb() :
 void TestJsonDb::removeDbFiles()
 {
     QStringList filters;
-    filters << QLatin1String("*.db")
+    filters << QLatin1String("*.db*")
             << "objectFile.bin" << "objectFile2.bin";
     QStringList lst = QDir().entryList(filters);
     foreach (const QString &fileName, lst)
diff --git a/tests/auto/jsondb-listmodel/test-jsondb-listmodel.cpp b/tests/auto/jsondb-listmodel/test-jsondb-listmodel.cpp
index 257b432..9f1de98 100644
--- a/tests/auto/jsondb-listmodel/test-jsondb-listmodel.cpp
+++ b/tests/auto/jsondb-listmodel/test-jsondb-listmodel.cpp
@@ -79,7 +79,7 @@ void TestJsonDbListModel::deleteDbFiles()
     // remove all the test files.
     QDir currentDir;
     QStringList nameFilter;
-    nameFilter << QString("*.db");
+    nameFilter << QString("*.db*");
     nameFilter << "objectFile.bin" << "objectFile2.bin";
     QFileInfoList databaseFiles = currentDir.entryInfoList(nameFilter, QDir::Files);
     foreach (QFileInfo fileInfo, databaseFiles) {
diff --git a/tests/auto/jsondbcachinglistmodel/testjsondbcachinglistmodel.cpp b/tests/auto/jsondbcachinglistmodel/testjsondbcachinglistmodel.cpp
index c11f048..ce76e91 100644
--- a/tests/auto/jsondbcachinglistmodel/testjsondbcachinglistmodel.cpp
+++ b/tests/auto/jsondbcachinglistmodel/testjsondbcachinglistmodel.cpp
@@ -93,7 +93,7 @@ void TestJsonDbCachingListModel::deleteDbFiles()
     // remove all the test files.
     QDir currentDir;
     QStringList nameFilter;
-    nameFilter << QString("*.db");
+    nameFilter << QString("*.db*");
     nameFilter << "objectFile.bin" << "objectFile2.bin";
     QFileInfoList databaseFiles = currentDir.entryInfoList(nameFilter, QDir::Files);
     foreach (QFileInfo fileInfo, databaseFiles) {
diff --git a/tests/auto/jsondbchangessinceobject/testjsondbchangessinceobject.cpp b/tests/auto/jsondbchangessinceobject/testjsondbchangessinceobject.cpp
index 8ad35d5..020e3db 100644
--- a/tests/auto/jsondbchangessinceobject/testjsondbchangessinceobject.cpp
+++ b/tests/auto/jsondbchangessinceobject/testjsondbchangessinceobject.cpp
@@ -87,7 +87,7 @@ void TestJsonDbChangesSinceObject::deleteDbFiles()
     // remove all the test files.
     QDir currentDir;
     QStringList nameFilter;
-    nameFilter << QString("*.db");
+    nameFilter << QString("*.db*");
     nameFilter << "objectFile.bin" << "objectFile2.bin";
     QFileInfoList databaseFiles = currentDir.entryInfoList(nameFilter, QDir::Files);
     foreach (QFileInfo fileInfo, databaseFiles) {
diff --git a/tests/auto/jsondblistmodel/testjsondblistmodel.cpp b/tests/auto/jsondblistmodel/testjsondblistmodel.cpp
index 598353c..305d54f 100644
--- a/tests/auto/jsondblistmodel/testjsondblistmodel.cpp
+++ b/tests/auto/jsondblistmodel/testjsondblistmodel.cpp
@@ -99,7 +99,7 @@ void TestJsonDbListModel::deleteDbFiles()
     // remove all the test files.
     QDir currentDir;
     QStringList nameFilter;
-    nameFilter << QString("*.db");
+    nameFilter << QString("*.db*");
     nameFilter << "objectFile.bin" << "objectFile2.bin";
     QFileInfoList databaseFiles = currentDir.entryInfoList(nameFilter, QDir::Files);
     foreach (QFileInfo fileInfo, databaseFiles) {
diff --git a/tests/auto/jsondbnotification/testjsondbnotification.cpp b/tests/auto/jsondbnotification/testjsondbnotification.cpp
index 6e3610f..f0e49d4 100644
--- a/tests/auto/jsondbnotification/testjsondbnotification.cpp
+++ b/tests/auto/jsondbnotification/testjsondbnotification.cpp
@@ -93,7 +93,7 @@ void TestJsonDbNotification::deleteDbFiles()
     // remove all the test files.
     QDir currentDir;
     QStringList nameFilter;
-    nameFilter << QString("*.db");
+    nameFilter << QString("*.db*");
     nameFilter << "objectFile.bin" << "objectFile2.bin";
     QFileInfoList databaseFiles = currentDir.entryInfoList(nameFilter, QDir::Files);
     foreach (QFileInfo fileInfo, databaseFiles) {
diff --git a/tests/auto/jsondbpartition/testjsondbpartition.cpp b/tests/auto/jsondbpartition/testjsondbpartition.cpp
index bfdafa6..c079303 100644
--- a/tests/auto/jsondbpartition/testjsondbpartition.cpp
+++ b/tests/auto/jsondbpartition/testjsondbpartition.cpp
@@ -78,7 +78,7 @@ void TestJsonDbPartition::deleteDbFiles()
     // remove all the test files.
     QDir currentDir;
     QStringList nameFilter;
-    nameFilter << QString("*.db");
+    nameFilter << QString("*.db*");
     nameFilter << "objectFile.bin" << "objectFile2.bin";
     QFileInfoList databaseFiles = currentDir.entryInfoList(nameFilter, QDir::Files);
     foreach (QFileInfo fileInfo, databaseFiles) {
diff --git a/tests/auto/jsondbqueryobject/testjsondbqueryobject.cpp b/tests/auto/jsondbqueryobject/testjsondbqueryobject.cpp
index 8205a18..e3cbaef 100644
--- a/tests/auto/jsondbqueryobject/testjsondbqueryobject.cpp
+++ b/tests/auto/jsondbqueryobject/testjsondbqueryobject.cpp
@@ -95,7 +95,7 @@ void TestJsonDbQueryObject::deleteDbFiles()
     // remove all the test files.
     QDir currentDir;
     QStringList nameFilter;
-    nameFilter << QString("*.db");
+    nameFilter << QString("*.db*");
     nameFilter << "objectFile.bin" << "objectFile2.bin";
     QFileInfoList databaseFiles = currentDir.entryInfoList(nameFilter, QDir::Files);
     foreach (QFileInfo fileInfo, databaseFiles) {
diff --git a/tests/auto/jsondbsortinglistmodel/testjsondbsortinglistmodel.cpp b/tests/auto/jsondbsortinglistmodel/testjsondbsortinglistmodel.cpp
index 762ce59..05c2a28 100644
--- a/tests/auto/jsondbsortinglistmodel/testjsondbsortinglistmodel.cpp
+++ b/tests/auto/jsondbsortinglistmodel/testjsondbsortinglistmodel.cpp
@@ -114,7 +114,7 @@ void TestJsonDbSortingListModel::deleteDbFiles()
     // remove all the test files.
     QDir currentDir;
     QStringList nameFilter;
-    nameFilter << QString("*.db");
+    nameFilter << QString("*.db*");
     nameFilter << "objectFile.bin" << "objectFile2.bin";
     QFileInfoList databaseFiles = currentDir.entryInfoList(nameFilter, QDir::Files);
     foreach (QFileInfo fileInfo, databaseFiles) {
diff --git a/tests/auto/qbtree/main.cpp b/tests/auto/qbtree/main.cpp
index 0b39005..6ceeba3 100644
--- a/tests/auto/qbtree/main.cpp
+++ b/tests/auto/qbtree/main.cpp
@@ -126,7 +126,9 @@ void TestQBtree::cleanup()
 {
     delete db;
     db = 0;
-    QFile::remove(dbname);
+    QString dbFileName(dbname);
+    dbFileName.append("*");
+    QFile::remove(dbFileName);
 }
 
 void TestQBtree::create()
diff --git a/tests/auto/qjsondbwatcher/testqjsondbwatcher.cpp b/tests/auto/qjsondbwatcher/testqjsondbwatcher.cpp
index 61d4bc0..48d59e2 100644
--- a/tests/auto/qjsondbwatcher/testqjsondbwatcher.cpp
+++ b/tests/auto/qjsondbwatcher/testqjsondbwatcher.cpp
@@ -198,7 +198,7 @@ void TestQJsonDbWatcher::onWatcherError(QtJsonDb::QJsonDbWatcher::ErrorCode code
 void TestQJsonDbWatcher::removeDbFiles()
 {
 #ifndef DONT_START_SERVER
-    QStringList lst = QDir().entryList(QStringList() << QLatin1String("*.db"));
+    QStringList lst = QDir().entryList(QStringList() << QLatin1String("*.db*"));
     lst << "objectFile.bin" << "objectFile2.bin";
     foreach (const QString &fileName, lst)
         QFile::remove(fileName);
diff --git a/tests/auto/qkeyvaluestore/qkeyvaluestore.pro b/tests/auto/qkeyvaluestore/qkeyvaluestore.pro
new file mode 100644
index 0000000..62840fe
--- /dev/null
+++ b/tests/auto/qkeyvaluestore/qkeyvaluestore.pro
@@ -0,0 +1,11 @@
+include($$PWD/../../../src/qkeyvaluestore/qkeyvaluestore.pri)
+QT       += testlib
+QT       -= gui
+
+TARGET = tst_qkeyvaluestore
+CONFIG   += testcase
+CONFIG   -= app_bundle
+
+TEMPLATE = app
+
+SOURCES += tst_qkeyvaluestore.cpp
diff --git a/tests/auto/qkeyvaluestore/tst_qkeyvaluestore.cpp b/tests/auto/qkeyvaluestore/tst_qkeyvaluestore.cpp
new file mode 100644
index 0000000..6c67bf5
--- /dev/null
+++ b/tests/auto/qkeyvaluestore/tst_qkeyvaluestore.cpp
@@ -0,0 +1,1403 @@
+#include <QtCore/QString>
+#include <QtTest/QtTest>
+
+#include <QFile>
+#include <QString>
+#include <QByteArray>
+#include <QHash>
+#include <unistd.h>
+#include <string.h>
+
+#include "qkeyvaluestore.h"
+#include "qkeyvaluestoretxn.h"
+#include "qkeyvaluestorecursor.h"
+#include "qkeyvaluestorefile.h"
+#include "qkeyvaluestoreentry.h"
+
+char testString[] = "this is a test";
+quint32 testStringSize = 14;
+
+class QKeyValueStoreTest : public QObject
+{
+    Q_OBJECT
+    QString m_dbName;
+    QString m_journal;
+    QString m_tree;
+    QString m_treeCopy;
+
+public:
+    QKeyValueStoreTest();
+    void removeTemporaryFiles();
+private Q_SLOTS:
+    void sanityCheck();
+    void storeAndLoad();
+    void transactionLifetime();
+    void autoSync();
+    void manualSync();
+    void compactionAfterRemove();
+    void compactionAfterPut();
+    void compactionAutoTrigger();
+    void compactionContinuation();
+    void fastOpen();
+    void testNonAsciiChars();
+    void buildBTreeFromScratch();
+    void buildBTreeFromKnownState();
+    void cursorSanityCheck();
+    void cursorAscendingOrder();
+    void cursorSeek();
+    void cursorSeekRange();
+    void fileSanityCheck();
+    void fileWrite();
+    void fileRead();
+    void fileOffset();
+    void fileSync();
+    void fileTruncate();
+#if 0
+#endif
+};
+
+QKeyValueStoreTest::QKeyValueStoreTest()
+{
+    m_dbName = "db";
+    m_journal = m_dbName + ".dat";
+    m_tree = m_dbName + ".btr";
+    m_treeCopy = m_dbName + ".old";
+}
+
+void QKeyValueStoreTest::removeTemporaryFiles()
+{
+    QFile::remove(m_journal);
+    QFile::remove(m_tree);
+    QFile::remove(m_treeCopy);
+}
+
+/*
+ * In a way this is a useless test, however it fulfills a purpose.
+ * All this operations should succeed unless something is really wrong.
+ * So despite not testing the functionality, we test that the API returns
+ * the right values.
+ */
+void QKeyValueStoreTest::sanityCheck()
+{
+    removeTemporaryFiles();
+    QKeyValueStore storage(m_dbName);
+    bool test = false;
+    test = storage.open();
+    QCOMPARE(test, true);
+
+    QKeyValueStoreTxn *readTxn = storage.beginRead();
+    QVERIFY2(readTxn, "Read txn is NULL");
+    QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+    QVERIFY2(writeTxn, "Write txn is NULL");
+
+    delete readTxn;
+    delete writeTxn;
+
+    test = storage.close();
+    QCOMPARE(test, true);
+    removeTemporaryFiles();
+}
+
+/*
+ * Simple test. We store some values, then read the values back.
+ */
+void QKeyValueStoreTest::storeAndLoad()
+{
+    removeTemporaryFiles();
+    QKeyValueStore storage(m_dbName);
+    bool test = false;
+    test = storage.open();
+    QCOMPARE(test, true);
+
+    // Set the sync threshold very low
+    storage.setSyncThreshold(5);
+
+    QByteArray key("key");
+    QByteArray value("value");
+
+    // Create a write transaction
+    QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+    QVERIFY2(writeTxn, "Write txn is NULL");
+    test = writeTxn->put(key, value);
+    QCOMPARE(test, true);
+    test = writeTxn->commit(100);
+    QCOMPARE(test, true);
+
+    // Create a read transaction
+    QKeyValueStoreTxn *readTxn = storage.beginRead();
+    QVERIFY2(readTxn, "Read txn is NULL");
+    QByteArray retrievedValue;
+    test = readTxn->get(key, &retrievedValue);
+    QCOMPARE(test, true);
+    QCOMPARE(value, retrievedValue);
+    delete readTxn;
+
+    test = storage.close();
+    QCOMPARE(test, true);
+    removeTemporaryFiles();
+}
+
+/*
+ * We create a write transaction and store some values into the db.
+ * Afterwards we create two transactions, one read and one write and
+ * start writing on the db. The read transaction shouldn't see the changes.
+ * After commiting the changes we create a new read transaction and see the
+ * new values.
+ */
+void QKeyValueStoreTest::transactionLifetime()
+{
+    QByteArray key0("key0"), value0("value0");
+    QByteArray key1("key1"), value1("value1");
+    QByteArray key2("key2"), value2("value2");
+    QByteArray key3("key3"), value3("value3");
+
+    removeTemporaryFiles();
+    QKeyValueStore storage(m_dbName);
+    QVERIFY(storage.open());
+
+    // Set the sync threshold very low
+    storage.setSyncThreshold(5);
+
+    // Create a write transaction
+    QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+    QVERIFY2(writeTxn, "Write txn is NULL");
+    QVERIFY(writeTxn->put(key0, value0));
+    QVERIFY(writeTxn->commit(100));
+#if defined(JSONDB_USE_KVS_MULTIPLE_TRANSACTIONS)
+    // Now, the transaction is commited. Let's create the other two.
+    QKeyValueStoreTxn *readTxn = storage.beginRead();
+    QVERIFY2(readTxn, "Read txn is NULL");
+    QKeyValueStoreTxn *newWriteTxn = storage.beginWrite();
+    QVERIFY2(newWriteTxn, "newWrite txn is NULL");
+
+    // Write some more entries
+    QVERIFY(newWriteTxn->put(key1, value1));
+    QVERIFY(newWriteTxn->put(key2, value2));
+    QVERIFY(newWriteTxn->put(key3, value3));
+
+    // Try to read those entries
+    QByteArray recoveredValue;
+    QVERIFY(readTxn->get(key0, &recoveredValue));
+    QCOMPARE(recoveredValue, value0);
+    QVERIFY(!readTxn->get(key1, &recoveredValue));
+    QVERIFY(!readTxn->get(key2, &recoveredValue));
+    QVERIFY(!readTxn->get(key3, &recoveredValue));
+
+    // However the write transaction can see it
+    QVERIFY(newWriteTxn->get(key1, &recoveredValue));
+    QCOMPARE(value1, recoveredValue);
+
+    // Commit the writes
+    QVERIFY(newWriteTxn->commit(101));
+
+    // Try to get them, once more
+    QVERIFY(!readTxn->get(key1, &recoveredValue));
+    QVERIFY(!readTxn->get(key2, &recoveredValue));
+    QVERIFY(!readTxn->get(key3, &recoveredValue));
+
+    // Create a new read transaction and get them
+    QKeyValueStoreTxn *newReadTxn = storage.beginRead();
+    QByteArray recoveredValue1, recoveredValue2, recoveredValue3;
+    // Try to get them, once more
+    QVERIFY(newReadTxn->get(key1, &recoveredValue1));
+    QCOMPARE(value1, recoveredValue1);
+    QVERIFY(newReadTxn->get(key2, &recoveredValue2));
+    QCOMPARE(value2, recoveredValue2);
+    QVERIFY(newReadTxn->get(key3, &recoveredValue3));
+    QCOMPARE(value3, recoveredValue3);
+#endif
+    QVERIFY(storage.close());
+    removeTemporaryFiles();
+}
+
+/*
+ * It seems that QMap and QByteArray do not share its love for non-ascii
+ * characters. This test case checks that.
+ */
+void QKeyValueStoreTest::testNonAsciiChars()
+{
+    removeTemporaryFiles();
+
+    char rawKey0[] = { 0, 0, 0, 2, 0 };
+    char rawKey1[] = { 0, 0, 0, 2, 1 };
+    char rawKey2[] = { 0, 0, 0, 2, 2 };
+    char rawKey3[] = { 0, 0, 0, 2, 3 };
+    int rawKeySize = 5;
+    QByteArray key0(rawKey0, rawKeySize);
+    QByteArray key1(rawKey1, rawKeySize);
+    QByteArray key2(rawKey2, rawKeySize);
+    QByteArray key3(rawKey3, rawKeySize);
+    char rawValue0[] = { 1, 0, 0, 2, 0 };
+    char rawValue1[] = { 1, 0, 0, 2, 1 };
+    char rawValue2[] = { 1, 0, 0, 2, 2 };
+    char rawValue3[] = { 1, 0, 0, 2, 3 };
+    int rawValueSize = 5;
+    QByteArray value0(rawValue0, rawValueSize);
+    QByteArray value1(rawValue1, rawValueSize);
+    QByteArray value2(rawValue2, rawValueSize);
+    QByteArray value3(rawValue3, rawValueSize);
+
+    QKeyValueStore storage(m_dbName);
+    QVERIFY(storage.open());
+    // Set the sync threshold very low
+    storage.setSyncThreshold(5);
+
+    // Create a write transaction
+    QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+    QVERIFY2(writeTxn, "Write txn is NULL");
+    QVERIFY(writeTxn->put(key0, value0));
+    QVERIFY(writeTxn->put(key1, value1));
+    QVERIFY(writeTxn->put(key2, value2));
+    QVERIFY(writeTxn->put(key3, value3));
+    QVERIFY(writeTxn->commit(100));
+
+    QKeyValueStoreTxn *readTxn = storage.beginRead();
+    QVERIFY2(readTxn, "Read txn is NULL");
+    QByteArray recoveredValue;
+    QVERIFY(readTxn->get(key0, &recoveredValue));
+    QCOMPARE(recoveredValue, value0);
+    QVERIFY(readTxn->get(key1, &recoveredValue));
+    QCOMPARE(recoveredValue, value1);
+    QVERIFY(readTxn->get(key2, &recoveredValue));
+    QCOMPARE(recoveredValue, value2);
+    QVERIFY(readTxn->get(key3, &recoveredValue));
+    QCOMPARE(recoveredValue, value3);
+    QVERIFY(readTxn->abort());
+
+    removeTemporaryFiles();
+}
+
+/*
+ * We create a database and start writing elements to it.
+ * We count the number of marks on the DB and check the status
+ * of the btree.
+ */
+void QKeyValueStoreTest::autoSync()
+{
+    removeTemporaryFiles();
+    QKeyValueStore storage(m_dbName);
+    QVERIFY(storage.open());
+    /*
+     * We write 100 entries, and check if the automatic sync kicked in.
+     * This can be verified by checking the number of marks on the db file.
+     * Entries 0..9 weight 20 bytes, and the rest 21. That's about 2090
+     * bytes, therefore we should have 2 marks (2nd mark comes at 2048 bytes).
+     */
+    QByteArray value("012345678901234");
+    for (int i = 0; i < 100; i++) {
+        QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+        QVERIFY2(writeTxn, "writeTxn is NULL");
+        QString number;
+        number.setNum(i);
+        QString baseKey("key-");
+        baseKey.append(number);
+        QByteArray key = baseKey.toAscii();
+        QVERIFY(writeTxn->put(key, value));
+        QVERIFY(writeTxn->commit(i + 1024));
+    }
+    QVERIFY(storage.close());
+    // Now we open the file and inspect it.
+    QFile db(m_journal);
+    db.open(QIODevice::ReadOnly);
+    QVERIFY(db.size() != 0);
+    QDataStream stream(&db);
+    stream.setByteOrder(QDataStream::LittleEndian);
+    quint32 count = 0, found = 0;
+    int numberOfMarkers = 0;
+    quint32 m_marker = 0x55AAAA55;
+    quint32 tag = 0;
+    quint64 dataTimestamp = 0;
+    stream >> count;
+    while (!stream.atEnd()) {
+        QByteArray key;
+        stream >> key;
+        quint8 operation = 0;
+        stream >> operation;
+        QByteArray value;
+        stream >> value;
+        quint32 hash = 0xFFFFFFFF;
+        stream >> hash;
+        found++;
+        if (count == found) {
+            // Do we have a marker?
+            stream >> tag;
+            quint32 marker = 0;
+            stream >> marker;
+            if (marker == m_marker) {
+                // Yes we do!
+                stream >> dataTimestamp;
+                stream >> hash;
+                numberOfMarkers++;
+                stream >> count;
+            } else {
+                count = marker;
+            }
+            found = 0;
+        }
+    }
+    // 2 automatic markers and one after calling close
+    QCOMPARE(numberOfMarkers, 3);
+    // And now to inspect the btree
+    QFile tree(m_tree);
+    tree.open(QIODevice::ReadOnly);
+    QDataStream treeStream(&tree);
+    treeStream.setByteOrder(QDataStream::LittleEndian);
+    quint64 treeTimestamp = 0;
+    found = 0;
+    treeStream >> count;
+    QCOMPARE(count, (quint32)100);
+    while (!treeStream.atEnd()) {
+        QByteArray key;
+        qint64 value;
+        treeStream >> key;
+        treeStream >> value;
+        found++;
+        if (count == found)
+            break;
+    }
+    treeStream >> treeTimestamp;
+    quint32 hash = 0xFFFFFFFF;
+    treeStream >> hash;
+    quint32 computedHash = qHash(treeTimestamp);
+    QCOMPARE(hash, computedHash);
+    QCOMPARE(treeTimestamp, dataTimestamp);
+
+    removeTemporaryFiles();
+}
+
+/*
+ * We create a database and start writing elements to it.
+ * We count the number of marks on the DB and check the status
+ * of the btree.
+ */
+void QKeyValueStoreTest::manualSync()
+{
+    removeTemporaryFiles();
+    QKeyValueStore storage(m_dbName);
+    // Set it on manual sync mode
+    storage.setSyncThreshold(0);
+    // Now run the test
+    QVERIFY(storage.open());
+    /*
+     * We write 100 entries, and check if the automatic sync kicked in.
+     * This can be verified by checking the number of marks on the db file.
+     * Entries 0..9 weight 20 bytes, and the rest 21. That's about 2090
+     * bytes. Since this is in manual sync mode, we should have no markers until
+     * we call close or sync.
+     */
+    QByteArray value("012345678901234");
+    for (int i = 0; i < 100; i++) {
+        QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+        QVERIFY2(writeTxn, "writeTxn is NULL");
+        QString number;
+        number.setNum(i);
+        QString baseKey("key-");
+        baseKey.append(number);
+        QByteArray key = baseKey.toAscii();
+        QVERIFY(writeTxn->put(key, value));
+        QVERIFY(writeTxn->commit(100));
+    }
+    QVERIFY(storage.close());
+    // Now we open the file and inspect it.
+    QFile db(m_journal);
+    db.open(QIODevice::ReadOnly);
+    QDataStream stream(&db);
+    stream.setByteOrder(QDataStream::LittleEndian);
+    quint32 count = 0, found = 0;
+    int numberOfMarkers = 0;
+    quint32 m_marker = 0x55AAAA55;
+    quint32 tag = 0;
+    quint64 dataTimestamp = 0;
+    stream >> count;
+    while (!stream.atEnd()) {
+        QByteArray key;
+        stream >> key;
+        quint8 operation = 0;
+        stream >> operation;
+        QByteArray value;
+        stream >> value;
+        quint32 hash = 0xFFFFFFFF;
+        stream >> hash;
+        found++;
+        if (count == found) {
+            // Do we have a marker?
+            stream >> tag;
+            quint32 marker = 0;
+            stream >> marker;
+            if (marker == m_marker) {
+                // Yes we do!
+                stream >> dataTimestamp;
+                stream >> hash;
+                numberOfMarkers++;
+                stream >> count;
+            } else
+                count = marker;
+            found = 0;
+        }
+    }
+    // One marker after calling close
+    QCOMPARE(numberOfMarkers, 1);
+    // And now to inspect the btree
+    QFile tree(m_tree);
+    tree.open(QIODevice::ReadOnly);
+    QDataStream treeStream(&tree);
+    treeStream.setByteOrder(QDataStream::LittleEndian);
+    quint64 treeTimestamp = 0;
+    found = 0;
+    treeStream >> count;
+    QCOMPARE(count, (quint32)100);
+    while (!treeStream.atEnd()) {
+        QByteArray key;
+        qint64 value;
+        treeStream >> key;
+        treeStream >> value;
+        found++;
+        if (count == found)
+            break;
+    }
+    treeStream >> treeTimestamp;
+    quint32 hash = 0xFFFFFFFF;
+    treeStream >> hash;
+    quint32 computedHash = qHash(treeTimestamp);
+    QCOMPARE(hash, computedHash);
+    QCOMPARE(treeTimestamp, dataTimestamp);
+
+    removeTemporaryFiles();
+}
+
+/*
+ * To test compaction we need to add elements and then
+ * remove some of them. The compacted file should not have those elements.
+ */
+void QKeyValueStoreTest::compactionAfterRemove()
+{
+    removeTemporaryFiles();
+    QKeyValueStore storage(m_dbName);
+    // Set it on manual sync mode
+    storage.setSyncThreshold(0);
+    // Now run the test
+    QVERIFY(storage.open());
+    QByteArray value("012345678901234");
+    for (int i = 0; i < 100; i++) {
+        QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+        QVERIFY2(writeTxn, "writeTxn is NULL");
+        QString number;
+        number.setNum(i);
+        QString baseKey("key-");
+        baseKey.append(number);
+        QByteArray key = baseKey.toAscii();
+        QVERIFY(writeTxn->put(key, value));
+        QVERIFY(writeTxn->commit(i));
+    }
+    // Let's remove all of them but one
+    for (int i = 0; i < 99; i++) {
+        QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+        QVERIFY2(writeTxn, "writeTxn is NULL");
+        QString number;
+        number.setNum(i);
+        QString baseKey("key-");
+        baseKey.append(number);
+        QByteArray key = baseKey.toAscii();
+        QVERIFY(writeTxn->remove(key));
+        QVERIFY(writeTxn->commit(i));
+    }
+    QVERIFY(storage.sync());
+    // Check that all elements are there.
+    qint32 addOperations = 0, removeOperations = 0;
+    QFile check1(m_dbName + ".dat");
+    QVERIFY(check1.open(QIODevice::ReadOnly));
+    QDataStream stream1(&check1);
+    stream1.setByteOrder(QDataStream::LittleEndian);
+    quint32 count = 0, found = 0;
+    int numberOfMarkers = 0;
+    quint32 m_marker = 0x55AAAA55;
+    quint32 tag = 0;
+    quint64 dataTimestamp = 0;
+    stream1 >> count;
+    while (!stream1.atEnd()) {
+        QByteArray key;
+        stream1 >> key;
+        quint8 operation = 0;
+        stream1 >> operation;
+        // Add
+        if (operation == QKeyValueStoreEntry::Add)
+            addOperations++;
+        else
+            removeOperations++;
+        QByteArray value;
+        stream1 >> value;
+        quint32 hash = 0xFFFFFFFF;
+        stream1 >> hash;
+        found++;
+        if (count == found) {
+            // Do we have a marker?
+            stream1 >> tag;
+            quint32 marker = 0;
+            stream1 >> marker;
+            if (marker == m_marker) {
+                // Yes we do!
+                stream1 >> dataTimestamp;
+                stream1 >> hash;
+                numberOfMarkers++;
+                stream1 >> count;
+            } else
+                count = marker;
+            found = 0;
+        }
+    }
+    check1.close();
+    QCOMPARE(addOperations, 100);
+    QCOMPARE(removeOperations, 99);
+    // Let's compact the file and check that only one element is there.
+    QVERIFY(storage.compact());
+    QFile check2(m_dbName + ".dat");
+    QVERIFY(check2.open(QIODevice::ReadOnly));
+    QDataStream stream2(&check2);
+    stream2.setByteOrder(QDataStream::LittleEndian);
+    addOperations = 0;
+    removeOperations = 0;
+    while (!stream2.atEnd()) {
+        QByteArray key;
+        stream2 >> key;
+        quint8 operation = 0;
+        stream2 >> operation;
+        if (operation == QKeyValueStoreEntry::Add)
+            addOperations++;
+        else
+            removeOperations++;
+        QByteArray value;
+        stream2 >> value;
+        quint32 hash = 0xFFFFFFFF;
+        stream2 >> hash;
+        found++;
+        if (count == found) {
+            // Do we have a marker?
+            stream2 >> tag;
+            quint32 marker = 0;
+            stream2 >> marker;
+            if (marker == m_marker) {
+                // Yes we do!
+                stream2 >> dataTimestamp;
+                stream2 >> hash;
+                numberOfMarkers++;
+                stream2 >> count;
+            } else
+                count = marker;
+            found = 0;
+        }
+    }
+    check2.close();
+    QCOMPARE(addOperations, 1);
+    QCOMPARE(removeOperations, 0);
+    // Close the file
+    QVERIFY(storage.close());
+    removeTemporaryFiles();
+}
+
+/*
+ * To test compaction we need to add elements and update them.
+ * The compacted file should have only one version of each element.
+ */
+void QKeyValueStoreTest::compactionAfterPut()
+{
+    removeTemporaryFiles();
+    QKeyValueStore storage(m_dbName);
+    // Set it on manual sync mode
+    storage.setSyncThreshold(0);
+    // Now run the test
+    QVERIFY(storage.open());
+    QByteArray value("012345678901234");
+    for (int i = 0; i < 100; i++) {
+        QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+        QVERIFY2(writeTxn, "writeTxn is NULL");
+        QString number;
+        number.setNum(i);
+        QByteArray key("key-0");
+        QVERIFY(writeTxn->put(key, value));
+        QVERIFY(writeTxn->commit(i));
+    }
+    QVERIFY(storage.sync());
+    // Check that all elements are there.
+    qint32 addOperations = 0, removeOperations = 0;
+    QFile check1(m_dbName + ".dat");
+    QVERIFY(check1.open(QIODevice::ReadOnly));
+    QDataStream stream1(&check1);
+    stream1.setByteOrder(QDataStream::LittleEndian);
+    quint32 count = 0, found = 0;
+    int numberOfMarkers = 0;
+    quint32 m_marker = 0x55AAAA55;
+    quint32 tag = 0;
+    quint64 dataTimestamp = 0;
+    stream1 >> count;
+    while (!stream1.atEnd()) {
+        QByteArray key;
+        stream1 >> key;
+        quint8 operation = 0;
+        stream1 >> operation;
+        // Add
+        if (operation == QKeyValueStoreEntry::Add)
+            addOperations++;
+        else
+            removeOperations++;
+        QByteArray value;
+        stream1 >> value;
+        quint32 hash = 0xFFFFFFFF;
+        stream1 >> hash;
+        found++;
+        if (count == found) {
+            // Do we have a marker?
+            stream1 >> tag;
+            quint32 marker = 0;
+            stream1 >> marker;
+            if (marker == m_marker) {
+                // Yes we do!
+                stream1 >> dataTimestamp;
+                stream1 >> hash;
+                numberOfMarkers++;
+                stream1 >> count;
+            } else
+                count = marker;
+            found = 0;
+        }
+    }
+    check1.close();
+    QCOMPARE(addOperations, 100);
+    QCOMPARE(removeOperations, 0);
+    // Let's compact the file and check that only one element is there.
+    QVERIFY(storage.compact());
+    QFile check2(m_dbName + ".dat");
+    QVERIFY(check2.open(QIODevice::ReadOnly));
+    QDataStream stream2(&check2);
+    stream2.setByteOrder(QDataStream::LittleEndian);
+    addOperations = 0;
+    removeOperations = 0;
+    while (!stream2.atEnd()) {
+        QByteArray key;
+        stream2 >> key;
+        quint8 operation = 0;
+        stream2 >> operation;
+        if (operation == QKeyValueStoreEntry::Add)
+            addOperations++;
+        else
+            removeOperations++;
+        QByteArray value;
+        stream2 >> value;
+        quint32 hash = 0xFFFFFFFF;
+        stream2 >> hash;
+        found++;
+        if (count == found) {
+            // Do we have a marker?
+            stream2 >> tag;
+            quint32 marker = 0;
+            stream2 >> marker;
+            if (marker == m_marker) {
+                // Yes we do!
+                stream2 >> dataTimestamp;
+                stream2 >> hash;
+                numberOfMarkers++;
+                stream2 >> count;
+            } else
+                count = marker;
+            found = 0;
+        }
+    }
+    check2.close();
+    QCOMPARE(addOperations, 1);
+    QCOMPARE(removeOperations, 0);
+    // Close the file
+    QVERIFY(storage.close());
+    removeTemporaryFiles();
+}
+
+/*
+ * To test this type of compaction we need to add elements until we trigger
+ * a compaction round. There are two cases, after remove or after too many
+ * updates.
+ */
+void QKeyValueStoreTest::compactionAutoTrigger()
+{
+    removeTemporaryFiles();
+    QKeyValueStore storage(m_dbName);
+    // Now run the test
+    QVERIFY(storage.open());
+    // Manual sync
+    storage.setSyncThreshold(0);
+    // Compact after 100 operations
+    storage.setCompactThreshold(100);
+    QByteArray value("012345678901234");
+    QByteArray key("key-0");
+    for (int i = 0; i < 100; i++) {
+        QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+        QVERIFY2(writeTxn, "writeTxn is NULL");
+        QVERIFY(writeTxn->put(key, value));
+        QVERIFY(writeTxn->commit(i));
+    }
+    // After sync there should be only one element
+    QVERIFY(storage.sync());
+    qint32 addOperations = 0, removeOperations = 0;
+    QFile check1(m_dbName + ".dat");
+    QVERIFY(check1.open(QIODevice::ReadOnly));
+    QDataStream stream1(&check1);
+    stream1.setByteOrder(QDataStream::LittleEndian);
+    quint32 count = 0, found = 0;
+    int numberOfMarkers = 0;
+    quint32 m_marker = 0x55AAAA55;
+    quint32 tag = 0;
+    quint64 dataTimestamp = 0;
+    stream1 >> count;
+    while (!stream1.atEnd()) {
+        QByteArray key;
+        stream1 >> key;
+        quint8 operation = 0;
+        stream1 >> operation;
+        // Add
+        if (operation == QKeyValueStoreEntry::Add)
+            addOperations++;
+        else
+            removeOperations++;
+        QByteArray value;
+        stream1 >> value;
+        quint32 hash = 0xFFFFFFFF;
+        stream1 >> hash;
+        found++;
+        if (count == found) {
+            // Do we have a marker?
+            stream1 >> tag;
+            quint32 marker = 0;
+            stream1 >> marker;
+            if (marker == m_marker) {
+                // Yes we do!
+                stream1 >> dataTimestamp;
+                stream1 >> hash;
+                numberOfMarkers++;
+                stream1 >> count;
+            } else
+                count = marker;
+            found = 0;
+        }
+    }
+    check1.close();
+    // There should be only one element
+    QCOMPARE(addOperations, 1);
+    QCOMPARE(removeOperations, 0);
+
+    removeTemporaryFiles();
+}
+
+/*
+ * What we test here is if the file is usable after compaction.
+ * First test is to write some more elements and then to close it
+ * and open it.
+ */
+void QKeyValueStoreTest::compactionContinuation()
+{
+    removeTemporaryFiles();
+    QKeyValueStore storage(m_dbName);
+    // Manual sync
+    storage.setSyncThreshold(0);
+    // Compact after 100 operations
+    storage.setCompactThreshold(100);
+    // Now run the test
+    QVERIFY(storage.open());
+    {
+        QByteArray value("012345678901234");
+        QByteArray key("key-0");
+        for (int i = 0; i < 100; i++) {
+            QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+            QVERIFY2(writeTxn, "writeTxn is NULL");
+            QVERIFY(writeTxn->put(key, value));
+            QVERIFY(writeTxn->commit(i));
+        }
+    }
+    // After sync there should be only one element
+    QVERIFY(storage.sync());
+    qint32 addOperations = 0, removeOperations = 0;
+    QFile check1(m_dbName + ".dat");
+    QVERIFY(check1.open(QIODevice::ReadOnly));
+    QDataStream stream1(&check1);
+    stream1.setByteOrder(QDataStream::LittleEndian);
+    quint32 count = 0, found = 0;
+    int numberOfMarkers = 0;
+    quint32 m_marker = 0x55AAAA55;
+    quint32 tag = 0;
+    quint64 dataTimestamp = 0;
+    stream1 >> count;
+    while (!stream1.atEnd()) {
+        QByteArray key;
+        stream1 >> key;
+        quint8 operation = 0;
+        stream1 >> operation;
+        // Add
+        if (operation == QKeyValueStoreEntry::Add)
+            addOperations++;
+        else
+            removeOperations++;
+        QByteArray value;
+        stream1 >> value;
+        quint32 hash = 0xFFFFFFFF;
+        stream1 >> hash;
+        found++;
+        if (count == found) {
+            // Do we have a marker?
+            stream1 >> tag;
+            quint32 marker = 0;
+            stream1 >> marker;
+            if (marker == m_marker) {
+                // Yes we do!
+                stream1 >> dataTimestamp;
+                stream1 >> hash;
+                numberOfMarkers++;
+                stream1 >> count;
+            } else
+                count = marker;
+            found = 0;
+        }
+    }
+    check1.close();
+    // There should be only one element
+    QCOMPARE(addOperations, 1);
+    QCOMPARE(removeOperations, 0);
+    QCOMPARE(storage.tag(), (quint32)99);
+    // Now we add some more elements and see what happens
+    {
+        QByteArray value("012345678901234");
+        QByteArray key("key-1");
+        for (int i = 100; i < 200; i++) {
+            QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+            QVERIFY2(writeTxn, "writeTxn is NULL");
+            QVERIFY(writeTxn->put(key, value));
+            QVERIFY(writeTxn->commit(i));
+        }
+    }
+    QVERIFY(storage.sync());
+    addOperations = 0;
+    removeOperations = 0;
+    QFile check2(m_dbName + ".dat");
+    QVERIFY(check2.open(QIODevice::ReadOnly));
+    QDataStream stream2(&check2);
+    stream2.setByteOrder(QDataStream::LittleEndian);
+    count = 0;
+    found = 0;
+    numberOfMarkers = 0;
+    stream2 >> count;
+    while (!stream2.atEnd()) {
+        QByteArray key;
+        stream2 >> key;
+        quint8 operation = 0;
+        stream2 >> operation;
+        // Add
+        if (operation == QKeyValueStoreEntry::Add)
+            addOperations++;
+        else
+            removeOperations++;
+        QByteArray value;
+        stream2 >> value;
+        quint32 hash = 0xFFFFFFFF;
+        stream2 >> hash;
+        found++;
+        if (count == found) {
+            // Do we have a marker?
+            stream2 >> tag;
+            quint32 marker = 0;
+            stream2 >> marker;
+            if (marker == m_marker) {
+                // Yes we do!
+                stream2 >> dataTimestamp;
+                stream2 >> hash;
+                numberOfMarkers++;
+                stream2 >> count;
+            } else
+                count = marker;
+            found = 0;
+        }
+    }
+    check2.close();
+    // There should be only two elements
+    QCOMPARE(addOperations, 2);
+    QCOMPARE(removeOperations, 0);
+
+    // Now close the file
+    QVERIFY(storage.close());
+    // And open it in a new element
+    QKeyValueStore storage2(m_dbName);
+    QVERIFY(storage2.open());
+    QCOMPARE(storage2.tag(), (quint32)199);
+    removeTemporaryFiles();
+}
+
+/*
+ * We store values in the file.
+ * We close it and then try to open it again.
+ */
+void QKeyValueStoreTest::fastOpen()
+{
+    removeTemporaryFiles();
+    QKeyValueStore storage(m_dbName);
+    QVERIFY(storage.open());
+
+    // Disable the autosync
+    storage.setSyncThreshold(0);
+
+    QByteArray key1("key1");
+    QByteArray value1("value1");
+
+    // Create a write transaction
+    QKeyValueStoreTxn *writeTxn1 = storage.beginWrite();
+    QVERIFY2(writeTxn1, "Write txn1 is NULL");
+    QVERIFY(writeTxn1->put(key1, value1));
+    QVERIFY(writeTxn1->commit(100));
+    QVERIFY(storage.sync());
+    // At this point we have one marker.
+    QByteArray key2("key2");
+    QByteArray value2("value2");
+
+    // Create a write transaction
+    QKeyValueStoreTxn *writeTxn2 = storage.beginWrite();
+    QVERIFY2(writeTxn2, "Write txn2 is NULL");
+    QVERIFY(writeTxn2->put(key2, value2));
+    QVERIFY(writeTxn2->commit(200));
+    // Now we have two markers, so we close the storage.
+    QVERIFY(storage.close());
+
+    /*
+     * We open the storage and count the markers. There should be two of them,
+     * however since this will be a fast open, we will only find the last one.
+     * That means there will be only one marker.
+     */
+    QKeyValueStore storage2(m_dbName);
+    QVERIFY(storage2.open());
+    // Now we count the markers
+    QCOMPARE(storage2.markers(), 1);
+
+    // Done, let's go.
+    QVERIFY(storage2.close());
+    removeTemporaryFiles();
+}
+
+/*
+ * We write entries to the database and then close it.
+ * We delete the btree file and open the database again.
+ * The algorithm should rebuild the btree from the journal.
+ */
+void QKeyValueStoreTest::buildBTreeFromScratch()
+{
+    removeTemporaryFiles();
+    QKeyValueStore storage(m_dbName);
+    QVERIFY(storage.open());
+    QByteArray value("012345678901234");
+    for (int i = 0; i < 100; i++) {
+        QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+        QVERIFY2(writeTxn, "writeTxn is NULL");
+        QString number;
+        number.setNum(i);
+        QString baseKey("key-");
+        baseKey.append(number);
+        QByteArray key = baseKey.toAscii();
+        QVERIFY(writeTxn->put(key, value));
+        QVERIFY(writeTxn->commit(100));
+    }
+    // Now we close the file
+    QVERIFY(storage.close());
+    // Remove the file
+    QFile::remove(m_tree);
+    // Now create a new storage and see if it builds the tree.
+    QKeyValueStore storage2(m_dbName);
+    QVERIFY(storage2.open());
+    QKeyValueStoreTxn *readTxn = storage2.beginRead();
+    QVERIFY2(readTxn, "readTxn is NULL");
+    QByteArray getKey("key-89");
+    QByteArray getValue;
+    QVERIFY(readTxn->get(getKey, &getValue));
+    QCOMPARE(getValue, value);
+    storage2.close();
+
+    removeTemporaryFiles();
+}
+
+/*
+ * We write entries to the database and then close it.
+ * We copy the btree file and then add some more entries to the db.
+ * We replace the new btree file with the old one and open the database again.
+ * The algorithm should rebuild the btree from the journal.
+ */
+void QKeyValueStoreTest::buildBTreeFromKnownState()
+{
+    removeTemporaryFiles();
+    QKeyValueStore storage(m_dbName);
+    bool test = false;
+    test = storage.open();
+    QCOMPARE(test, true);
+    QByteArray value("012345678901234");
+    for (int i = 0; i < 100; i++) {
+        QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+        QVERIFY2(writeTxn, "writeTxn is NULL");
+        QString number;
+        number.setNum(i);
+        QString baseKey("key-");
+        baseKey.append(number);
+        QByteArray key = baseKey.toAscii();
+        test = writeTxn->put(key, value);
+        QCOMPARE(test, true);
+        test = writeTxn->commit(100);
+        QCOMPARE(test, true);
+    }
+    // At this time we only have two markers.
+    QFile::copy(m_tree, m_treeCopy);
+    // Now we close the file
+    test = storage.close();
+    // Remove the file
+    QFile::remove(m_tree);
+    QFile::rename(m_treeCopy, m_tree);
+
+    // Now create a new storage and see if it builds the tree.
+    QKeyValueStore storage2(m_dbName);
+    test = storage2.open();
+    QCOMPARE(test, true);
+    QKeyValueStoreTxn *readTxn = storage2.beginRead();
+    QVERIFY2(readTxn, "readTxn is NULL");
+    QByteArray getKey("key-89");
+    QByteArray getValue;
+    test = readTxn->get(getKey, &getValue);
+    QCOMPARE(test, true);
+    QCOMPARE(getValue, value);
+    storage2.close();
+    removeTemporaryFiles();
+}
+
+/*
+ * This is a very useless test, but everything here should work.
+ */
+void QKeyValueStoreTest::cursorSanityCheck()
+{
+    removeTemporaryFiles();
+    QKeyValueStore storage(m_dbName);
+    bool test = false;
+    test = storage.open();
+    QCOMPARE(test, true);
+    QByteArray value("012345678901234");
+    QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+    for (int i = 0; i < 100; i++) {
+        QVERIFY2(writeTxn, "writeTxn is NULL");
+        QString number;
+        number.setNum(i);
+        QString baseKey("key-");
+        baseKey.append(number);
+        QByteArray key = baseKey.toAscii();
+        test = writeTxn->put(key, value);
+        QCOMPARE(test, true);
+        QCOMPARE(test, true);
+    }
+    // Now we have 100 items, let's use the cursor and iterate over the first and the last.
+    QKeyValueStoreCursor *cursor = new QKeyValueStoreCursor(writeTxn);
+    // At this point the cursor should be pointing to the first item
+    QByteArray firstElementKey("key-0");
+    QByteArray lastElementKey("key-99");
+    QByteArray recoveredKey;
+    QByteArray recoveredValue;
+    QVERIFY(cursor->current(&recoveredKey, &recoveredValue));
+    QCOMPARE(recoveredKey, firstElementKey);
+    QCOMPARE(recoveredValue, value);
+    // Move to the last element
+    QVERIFY(cursor->last());
+    QVERIFY(cursor->current(&recoveredKey, &recoveredValue));
+    QCOMPARE(recoveredKey, lastElementKey);
+    QCOMPARE(recoveredValue, value);
+    removeTemporaryFiles();
+}
+
+/*
+ * This is a funny test, ascending order means ascending in a string kind of way.
+ * Therefore the keys are ordered as follows:
+ * key-0
+ * key-1
+ * key-10
+ * key-11
+ * ...
+ * key-2
+ * key-20
+ * ...
+ * key-98
+ * key-99
+ */
+void QKeyValueStoreTest::cursorAscendingOrder()
+{
+    removeTemporaryFiles();
+    QKeyValueStore storage(m_dbName);
+    bool test = false;
+    test = storage.open();
+    QCOMPARE(test, true);
+    QByteArray value("012345678901234");
+    QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+    for (int i = 0; i < 100; i++) {
+        QVERIFY2(writeTxn, "writeTxn is NULL");
+        QString number;
+        number.setNum(i);
+        QString baseKey("key-");
+        baseKey.append(number);
+        QByteArray key = baseKey.toAscii();
+        test = writeTxn->put(key, value);
+        QCOMPARE(test, true);
+    }
+    // Now we have 100 items, let's use the cursor and iterate over them
+    QKeyValueStoreCursor *cursor = new QKeyValueStoreCursor(writeTxn);
+    // At this point the cursor should be pointing to the first item
+    for (int i = 0; i < 10; i++) {
+        QString number;
+        number.setNum(i);
+        QString baseKey("key-");
+        baseKey.append(number);
+        QByteArray key = baseKey.toAscii();
+        QByteArray recoveredKey;
+        QByteArray recoveredValue;
+        QVERIFY(cursor->current(&recoveredKey, &recoveredValue));
+        QCOMPARE(recoveredKey, key);
+        QCOMPARE(recoveredValue, value);
+        QVERIFY(cursor->next());
+        if (0 == i)
+            continue;
+        for (int j = 0; j < 10; j++, cursor->next()) {
+            QString baseKey2(baseKey);
+            QString number2;
+            number2.setNum(j);
+            baseKey2.append(number2);
+            key = baseKey2.toAscii();
+            QVERIFY(cursor->current(&recoveredKey, &recoveredValue));
+            QCOMPARE(recoveredKey, key);
+            QCOMPARE(recoveredValue, value);
+        }
+    }
+    removeTemporaryFiles();
+}
+
+void QKeyValueStoreTest::cursorSeek()
+{
+    removeTemporaryFiles();
+    QKeyValueStore storage(m_dbName);
+    QVERIFY(storage.open());
+    QByteArray value("012345678901234");
+    QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+    for (int i = 0; i < 100; i++) {
+        QVERIFY2(writeTxn, "writeTxn is NULL");
+        QString number;
+        number.setNum(i);
+        QString baseKey("key-");
+        baseKey.append(number);
+        QByteArray key = baseKey.toAscii();
+        QVERIFY(writeTxn->put(key, value));
+    }
+    // Now we have 100 items, let's use the cursor and iterate over them.
+    QKeyValueStoreCursor *cursor = new QKeyValueStoreCursor(writeTxn);
+    // At this point the cursor should be pointing to the first item
+    // First let's try seeking a known element
+    QByteArray key55("key-55");
+    QByteArray recoveredKey;
+    QByteArray recoveredValue;
+    QVERIFY(cursor->seek(key55));
+    QVERIFY(cursor->current(&recoveredKey, &recoveredValue));
+    QCOMPARE(recoveredKey, key55);
+    QCOMPARE(recoveredValue, value);
+    // Now let's try an unknown element
+    QByteArray key101("key-101");
+    QVERIFY2(!cursor->seek(key101), "We have an unknown element on the array (101)");
+    // And let's finish with a new known element
+    QByteArray key10("key-10");
+    QVERIFY(cursor->seek(key10));
+    QVERIFY(cursor->current(&recoveredKey, &recoveredValue));
+    QCOMPARE(recoveredKey, key10);
+    QCOMPARE(recoveredValue, value);
+    // Done
+    removeTemporaryFiles();
+}
+
+/*
+ * seek and seekRange are similar. The difference is on the "not found"
+ * reply. While seeks returns false, seekRange can return an element.
+ */
+void QKeyValueStoreTest::cursorSeekRange()
+{
+    removeTemporaryFiles();
+    QKeyValueStore storage(m_dbName);
+    QVERIFY(storage.open());
+    QByteArray value("012345678901234");
+    QKeyValueStoreTxn *writeTxn = storage.beginWrite();
+    for (int i = 0; i < 100; i++) {
+        QVERIFY2(writeTxn, "writeTxn is NULL");
+        QString number;
+        number.setNum(i);
+        QString baseKey("key-");
+        baseKey.append(number);
+        QByteArray key = baseKey.toAscii();
+        QVERIFY(writeTxn->put(key, value));
+    }
+    // Now we have 100 items, let's use the cursor and iterate over them.
+    QKeyValueStoreCursor *cursor = new QKeyValueStoreCursor(writeTxn);
+    // At this point the cursor should be pointing to the first item
+    // First let's try seeking a known element
+    QByteArray key55("key-55");
+    QByteArray recoveredKey;
+    QByteArray recoveredValue;
+    QVERIFY(cursor->seekRange(key55));
+    QVERIFY(cursor->current(&recoveredKey, &recoveredValue));
+    QCOMPARE(recoveredKey, key55);
+    QCOMPARE(recoveredValue, value);
+    // Now let's try an unknown element
+    QByteArray key999("key-999");
+    QVERIFY2(!cursor->seekRange(key999), "We have an unknown element on the array (999)");
+    // And let's finish with a new known element
+    QByteArray key10("key-10");
+    QVERIFY(cursor->seekRange(key10));
+    QVERIFY(cursor->current(&recoveredKey, &recoveredValue));
+    QCOMPARE(recoveredKey, key10);
+    QCOMPARE(recoveredValue, value);
+    // Now we try elements that are not found but have a greater than
+    QByteArray key101("key-101");
+    QByteArray key101greater("key-11");
+    QVERIFY(cursor->seekRange(key101));
+    QVERIFY(cursor->current(&recoveredKey, &recoveredValue));
+    QCOMPARE(recoveredKey, key101greater);
+    QCOMPARE(recoveredValue, value);
+    // Done
+    removeTemporaryFiles();
+}
+
+/*
+ * As all the other sanity checks this is pretty useless, although it
+ * checks that the API returns the correct values.
+ */
+void QKeyValueStoreTest::fileSanityCheck()
+{
+    removeTemporaryFiles();
+    QKeyValueStoreFile file("db.dat");
+    QVERIFY(file.open());
+    QCOMPARE(file.size(), (qint64)0);
+    QVERIFY(file.close());
+    removeTemporaryFiles();
+}
+
+/*
+ * Create a file and write something to it, then check the file size.
+ */
+void QKeyValueStoreTest::fileWrite()
+{
+    removeTemporaryFiles();
+    QKeyValueStoreFile file("db.dat");
+    QVERIFY(file.open());
+    QCOMPARE(file.size(), (qint64)0);
+    QCOMPARE(file.write(testString, testStringSize), (qint32)testStringSize);
+    QCOMPARE(file.size(), (qint64)testStringSize);
+    QVERIFY(file.close());
+    removeTemporaryFiles();
+}
+
+/*
+ * Create a file and write something to it, then check the file size.
+ * Once that is done, read the content back and check it is the same.
+ */
+void QKeyValueStoreTest::fileRead()
+{
+    removeTemporaryFiles();
+    QKeyValueStoreFile file("db.dat");
+    QVERIFY(file.open());
+    QCOMPARE(file.size(), (qint64)0);
+    QCOMPARE(file.write(testString, testStringSize), (qint32)testStringSize);
+    QCOMPARE(file.size(), (qint64)testStringSize);
+    // Now read the content back
+    char buffer[15];
+    file.setOffset(0);
+    QCOMPARE(file.read(buffer, testStringSize), (qint32)testStringSize);
+    QCOMPARE(strncmp(buffer, testString, testStringSize), 0);
+    QVERIFY(file.close());
+    removeTemporaryFiles();
+}
+
+/*
+ * Create a file and write some data into it. Store the offset and then
+ * write some more data into it. Read the new data using the stored offset.
+ * Check the total file size.
+ */
+void QKeyValueStoreTest::fileOffset()
+{
+    removeTemporaryFiles();
+    QKeyValueStoreFile file("db.dat");
+    QVERIFY(file.open());
+    QCOMPARE(file.size(), (qint64)0);
+    QCOMPARE(file.write(testString, testStringSize), (qint32)testStringSize);
+    QCOMPARE(file.size(), (qint64)testStringSize);
+    qint64 offset = file.size();
+    // Write some more data into the file
+    QCOMPARE(file.write(testString, testStringSize), (qint32)testStringSize);
+    QCOMPARE(file.size(), (qint64)(2*testStringSize));
+    // Now read the data from the stored offset.
+    char buffer[15];
+    file.setOffset(offset);
+    QCOMPARE(file.read(buffer, testStringSize), (qint32)testStringSize);
+    QCOMPARE(strncmp(buffer, testString, testStringSize), 0);
+    offset = file.size();
+    // Write some more data into the file
+    QCOMPARE(file.write(testString, testStringSize), (qint32)testStringSize);
+    QCOMPARE(file.size(), (qint64)(3*testStringSize));
+    // Now read the data from the stored offset.
+    file.setOffset(offset);
+    QCOMPARE(file.read(buffer, testStringSize), (qint32)testStringSize);
+    QCOMPARE(strncmp(buffer, testString, testStringSize), 0);
+    QVERIFY(file.close());
+    removeTemporaryFiles();
+}
+
+/*
+ * Create a new file and write some data to it. Without closing the file,
+ * open a new instance of it and start reading it. It might or not return the
+ * contents. On the first file call sync. Now read on the second file, the content
+ * should be visible.
+ */
+void QKeyValueStoreTest::fileSync()
+{
+    removeTemporaryFiles();
+    QKeyValueStoreFile file("db.dat");
+    QKeyValueStoreFile file2("db.dat");
+    QVERIFY(file.open());
+    QCOMPARE(file.size(), (qint64)0);
+    QCOMPARE(file.write(testString, testStringSize), (qint32)testStringSize);
+    QCOMPARE(file.size(), (qint64)testStringSize);
+    // Open the file a second time and try to read from it.
+    QVERIFY(file2.open());
+    char buffer[15];
+    file.setOffset(0);
+    QCOMPARE(file2.read(buffer, testStringSize), (qint32)testStringSize);
+    QCOMPARE(file2.size(), (qint64)testStringSize);
+    QVERIFY(file2.close());
+    // Now sync the file
+    file.sync();
+    // Open the other file and check the content
+    QVERIFY(file2.open());
+    QCOMPARE(file2.size(), (qint64)testStringSize);
+    QVERIFY(file2.close());
+    QVERIFY(file.close());
+    removeTemporaryFiles();
+}
+
+/*
+ * Create a new file and write some data to it checking the file size.
+ * Open the file again with the truncate flag on and check the file size.
+ */
+void QKeyValueStoreTest::fileTruncate()
+{
+    removeTemporaryFiles();
+    QKeyValueStoreFile file("db.dat");
+    QVERIFY(file.open());
+    QCOMPARE(file.size(), (qint64)0);
+    QCOMPARE(file.write(testString, testStringSize), (qint32)testStringSize);
+    QCOMPARE(file.size(), (qint64)testStringSize);
+    QVERIFY(file.close());
+    QKeyValueStoreFile file2("db.dat", true);
+    QVERIFY(file2.open());
+    QCOMPARE(file2.size(), (qint64)0);
+    QVERIFY(file2.close());
+    removeTemporaryFiles();
+}
+
+#if 0
+#endif
+QTEST_APPLESS_MAIN(QKeyValueStoreTest)
+
+#include "tst_qkeyvaluestore.moc"
diff --git a/tests/auto/queries/testjsondbqueries.cpp b/tests/auto/queries/testjsondbqueries.cpp
index d5218b6..608dcf3 100644
--- a/tests/auto/queries/testjsondbqueries.cpp
+++ b/tests/auto/queries/testjsondbqueries.cpp
@@ -191,7 +191,7 @@ TestJsonDbQueries::TestJsonDbQueries() :
 void TestJsonDbQueries::removeDbFiles()
 {
     QStringList filters;
-    filters << QLatin1String("*.db");
+    filters << QLatin1String("*.db*");
     QStringList lst = QDir().entryList(filters);
     foreach (const QString &fileName, lst)
         QFile::remove(fileName);
diff --git a/tests/benchmarks/btrees/btrees.pro b/tests/benchmarks/btrees/btrees.pro
index c569fbd..e6f6196 100644
--- a/tests/benchmarks/btrees/btrees.pro
+++ b/tests/benchmarks/btrees/btrees.pro
@@ -1,5 +1,6 @@
 include($$PWD/../../../src/hbtree/hbtree.pri)
 include($$PWD/../../../src/3rdparty/btree/btree.pri)
+include($$PWD/../../../src/qkeyvaluestore/qkeyvaluestore.pri)
 
 TARGET = tst_bench_btrees
 
diff --git a/tests/benchmarks/btrees/main.cpp b/tests/benchmarks/btrees/main.cpp
index fcfec44..6ef7e03 100644
--- a/tests/benchmarks/btrees/main.cpp
+++ b/tests/benchmarks/btrees/main.cpp
@@ -44,6 +44,7 @@
 #include <QByteArray>
 #include <QFile>
 #include <QMap>
+#include <QString>
 
 #include "hbtree.h"
 #include "hbtree_p.h"
@@ -51,6 +52,9 @@
 #include "hbtreetransaction.h"
 #include "qbtreetxn.h"
 #include "qbtreecursor.h"
+#include "qkeyvaluestore.h"
+#include "qkeyvaluestoretxn.h"
+#include "qkeyvaluestorecursor.h"
 
 class TestBtrees: public QObject
 {
@@ -60,7 +64,8 @@ public:
 
     enum BtreeType {
         Hybrid,
-        AppendOnly
+        AppendOnly,
+        KeyValue
     };
 
 private slots:
@@ -87,18 +92,23 @@ private slots:
     void searchRange_data();
     void searchRange();
 
+    void compact_data();
+    void compact();
+
 private:
 
     HBtree *hybridDb;
     QBtree *appendOnlyDb;
+    QKeyValueStore *keyValueDb;
     const HBtreePrivate *hybridPrivate;
 
     struct SizeStat {
         SizeStat()
-            : hybridSize(0), appendOnlySize(0), numCollectible(0)
+            : hybridSize(0), appendOnlySize(0), keyValueSize(0), numCollectible(0)
         {}
         qint64 hybridSize;
         qint64 appendOnlySize;
+        qint64 keyValueSize;
         int numCollectible;
     };
 
@@ -106,14 +116,17 @@ private:
 };
 
 TestBtrees::TestBtrees()
-    : hybridDb(0), appendOnlyDb(0)
+    : hybridDb(0), appendOnlyDb(0), keyValueDb(0)
 {
 }
 
 static const char hybridDbFileName[] = "tst_hbtree.db";
 static const char appendOnlyDbFileName[] = "tst_aobtree.db";
+static const char keyValueDbFileName[] = "tst_kvs";
 static const char hybridDataTag[] = "Hybrid";
 static const char appendOnlyDataTag[] = "Append-Only";
+static const char keyValueDataTag[] = "KeyValue";
+
 
 const char * sizeStr(size_t sz)
 {
@@ -142,6 +155,7 @@ void TestBtrees::cleanupTestCase()
         qDebug() << it.key();
         qDebug() << "\tAppend-Only:" << sizeStr(it.value().appendOnlySize);
         qDebug() << "\tHybrid:" << sizeStr(it.value().hybridSize) << "with" << it.value().numCollectible << "reusable pages";
+        qDebug() << "\tKeyValue:" << sizeStr(it.value().keyValueSize);
         ++it;
     }
 }
@@ -150,9 +164,19 @@ void TestBtrees::init()
 {
     QFile::remove(hybridDbFileName);
     QFile::remove(appendOnlyDbFileName);
+    QString kvsTree = keyValueDbFileName;
+    kvsTree.append(".btr");
+    QString kvsJournal = keyValueDbFileName;
+    kvsJournal.append(".dat");
+    QString kvsOldJournal = keyValueDbFileName;
+    kvsOldJournal.append(".old");
+    QFile::remove(kvsTree);
+    QFile::remove(kvsJournal);
+    QFile::remove(kvsOldJournal);
 
     hybridDb = new HBtree(hybridDbFileName);
     appendOnlyDb = new QBtree(appendOnlyDbFileName);
+    keyValueDb = new QKeyValueStore(QString(keyValueDbFileName));
 
     if (!hybridDb->open(HBtree::ReadWrite))
         Q_ASSERT(false);
@@ -160,13 +184,22 @@ void TestBtrees::init()
     if (!appendOnlyDb->open(QBtree::NoSync | QBtree::UseSyncMarker))
         Q_ASSERT(false);
 
+    if (!keyValueDb->open())
+        Q_ASSERT(false);
+
     appendOnlyDb->setAutoCompactRate(1000);
+    // Manual sync only
+    keyValueDb->setSyncThreshold(0);
 
     hybridPrivate = hybridDb->d_func();
 }
 
 void TestBtrees::cleanup()
 {
+    QString keyValueJournal(keyValueDbFileName);
+    QString keyValueTree(keyValueDbFileName);
+    keyValueJournal.append(".dat");
+    keyValueTree.append(".btr");
 
     QString tag = QTest::currentDataTag();
 
@@ -181,15 +214,29 @@ void TestBtrees::cleanup()
         file.open(QFile::ReadOnly);
         SizeStat &ss = sizeStats_[QTest::currentTestFunction()];
         ss.appendOnlySize = qMax(file.size(), ss.appendOnlySize);
+    } else if (tag == keyValueDataTag) {
+        QFile journal(keyValueJournal);
+        QFile tree(keyValueTree);
+        journal.open(QFile::ReadOnly);
+        tree.open(QFile::ReadOnly);
+        qint64 journalSize = 0, treeSize = 0, totalSize = 0;
+        journalSize = journal.size();
+        treeSize = tree.size();
+        totalSize = journalSize + treeSize;
+        SizeStat &ss = sizeStats_[QTest::currentTestFunction()];
+        ss.keyValueSize = qMax(totalSize, ss.keyValueSize);
     }
 
     delete hybridDb;
     delete appendOnlyDb;
+    delete keyValueDb;
     appendOnlyDb = 0;
     hybridDb = 0;
+    keyValueDb = 0;
     QFile::remove(hybridDbFileName);
     QFile::remove(appendOnlyDbFileName);
-
+    QFile::remove(keyValueJournal);
+    QFile::remove(keyValueTree);
 }
 
 void TestBtrees::openClose_data()
@@ -197,6 +244,7 @@ void TestBtrees::openClose_data()
     QTest::addColumn<int>("btreeType");
     QTest::newRow(hybridDataTag) << (int)Hybrid;
     QTest::newRow(appendOnlyDataTag) << (int)AppendOnly;
+    QTest::newRow(keyValueDataTag) << (int)KeyValue;
 }
 
 void TestBtrees::openClose()
@@ -208,11 +256,16 @@ void TestBtrees::openClose()
             hybridDb->close();
             QVERIFY(hybridDb->open());
         }
-    } else {
+    } else if (btreeType == AppendOnly){
         QBENCHMARK {
             appendOnlyDb->close();
             QVERIFY(appendOnlyDb->open());
         }
+    } else if (btreeType == KeyValue){
+        QBENCHMARK {
+            keyValueDb->close();
+            QVERIFY(keyValueDb->open());
+        }
     }
 }
 
@@ -221,6 +274,7 @@ void TestBtrees::insertItem_data()
     QTest::addColumn<int>("btreeType");
     QTest::newRow(hybridDataTag) << (int)Hybrid;
     QTest::newRow(appendOnlyDataTag) << (int)AppendOnly;
+    QTest::newRow(keyValueDataTag) << (int)KeyValue;
 }
 
 void TestBtrees::insertItem()
@@ -237,7 +291,7 @@ void TestBtrees::insertItem()
             QVERIFY(txn->put(key, value));
             QVERIFY(txn->commit(i));
         }
-    } else {
+    } else if (btreeType == AppendOnly){
         QBENCHMARK {
             ++i;
             QByteArray key = QByteArray::number(i);
@@ -247,6 +301,16 @@ void TestBtrees::insertItem()
             QVERIFY(txn->put(key, value));
             QVERIFY(txn->commit(i));
         }
+    } else if (btreeType == KeyValue){
+        QBENCHMARK {
+            ++i;
+            QByteArray key = QByteArray::number(i);
+            QByteArray value = QByteArray::number(i);
+            QKeyValueStoreTxn *txn = keyValueDb->beginWrite();
+            QVERIFY(txn);
+            QVERIFY(txn->put(key, value));
+            QVERIFY(txn->commit(i));
+        }
     }
 }
 
@@ -255,6 +319,7 @@ void TestBtrees::insert1000Items_data()
     QTest::addColumn<int>("btreeType");
     QTest::newRow(hybridDataTag) << (int)Hybrid;
     QTest::newRow(appendOnlyDataTag) << (int)AppendOnly;
+    QTest::newRow(keyValueDataTag) << (int)KeyValue;
 }
 
 void TestBtrees::insert1000Items()
@@ -273,7 +338,7 @@ void TestBtrees::insert1000Items()
                 QVERIFY(txn->commit(i));
             }
         }
-    } else {
+    } else if (btreeType == AppendOnly){
         QBENCHMARK {
             for (int i = 0; i < numItems; ++i) {
                 QByteArray key = QByteArray::number(i);
@@ -284,6 +349,17 @@ void TestBtrees::insert1000Items()
                 QVERIFY(txn->commit(i));
             }
         }
+    } else if (btreeType == KeyValue){
+        QBENCHMARK {
+            for (int i = 0; i < numItems; ++i) {
+                QByteArray key = QByteArray::number(i);
+                QByteArray value = QByteArray::number(i);
+                QKeyValueStoreTxn *txn = keyValueDb->beginWrite();
+                QVERIFY(txn);
+                QVERIFY(txn->put(key, value));
+                QVERIFY(txn->commit(i));
+            }
+        }
     }
 }
 
@@ -292,6 +368,7 @@ void TestBtrees::delete1000Items_data()
     QTest::addColumn<int>("btreeType");
     QTest::newRow(hybridDataTag) << (int)Hybrid;
     QTest::newRow(appendOnlyDataTag) << (int)AppendOnly;
+    QTest::newRow(keyValueDataTag) << (int)KeyValue;
 }
 
 void TestBtrees::delete1000Items()
@@ -317,6 +394,15 @@ void TestBtrees::delete1000Items()
             QVERIFY(txn->put(key, value));
         }
         QVERIFY(txn->commit(0));
+    } else if (btreeType == KeyValue) {
+        QKeyValueStoreTxn *txn = keyValueDb->beginWrite();
+        QVERIFY(txn);
+        for (int i = 0; i < numItems; ++i) {
+            QByteArray key = QByteArray::number(i);
+            QByteArray value = QByteArray::number(i);
+            QVERIFY(txn->put(key, value));
+        }
+        QVERIFY(txn->commit(0));
     }
 
     if (btreeType == Hybrid) {
@@ -339,6 +425,16 @@ void TestBtrees::delete1000Items()
                 QVERIFY(txn->commit(i));
             }
         }
+    } else if (btreeType == KeyValue) {
+        QBENCHMARK_ONCE {
+            for (int i = 0; i < numItems; ++i) {
+                QByteArray key = QByteArray::number(i);
+                QKeyValueStoreTxn *txn = keyValueDb->beginWrite();
+                QVERIFY(txn);
+                QVERIFY(txn->remove(key));
+                QVERIFY(txn->commit(i));
+            }
+        }
     }
 }
 
@@ -347,6 +443,7 @@ void TestBtrees::find1000Items_data()
     QTest::addColumn<int>("btreeType");
     QTest::newRow(hybridDataTag) << (int)Hybrid;
     QTest::newRow(appendOnlyDataTag) << (int)AppendOnly;
+    QTest::newRow(keyValueDataTag) << (int)KeyValue;
 }
 
 void TestBtrees::find1000Items()
@@ -372,6 +469,15 @@ void TestBtrees::find1000Items()
             QVERIFY(txn->put(key, value));
         }
         QVERIFY(txn->commit(0));
+    } else if (btreeType == KeyValue) {
+        QKeyValueStoreTxn *txn = keyValueDb->beginWrite();
+        QVERIFY(txn);
+        for (int i = 0; i < numItems; ++i) {
+            QByteArray key = QByteArray::number(i);
+            QByteArray value = QByteArray::number(i);
+            QVERIFY(txn->put(key, value));
+        }
+        QVERIFY(txn->commit(0));
     }
 
     if (btreeType == Hybrid) {
@@ -398,6 +504,19 @@ void TestBtrees::find1000Items()
                 txn->abort();
             }
         }
+    } else if (btreeType == KeyValue) {
+        QBENCHMARK {
+            for (int i = 0; i < numItems; ++i) {
+                QByteArray key = QByteArray::number(i);
+                QByteArray value = QByteArray::number(i);
+                QByteArray baOut;
+                QKeyValueStoreTxn *txn = keyValueDb->beginRead();
+                QVERIFY(txn);
+                QVERIFY(txn->get(key, &baOut));
+                QCOMPARE(baOut, value);
+                txn->abort();
+            }
+        }
     }
 }
 
@@ -406,6 +525,7 @@ void TestBtrees::searchRange_data()
     QTest::addColumn<int>("btreeType");
     QTest::newRow(hybridDataTag) << (int)Hybrid;
     QTest::newRow(appendOnlyDataTag) << (int)AppendOnly;
+    QTest::newRow(keyValueDataTag) << (int)KeyValue;
 }
 
 void TestBtrees::searchRange()
@@ -432,6 +552,15 @@ void TestBtrees::searchRange()
             QVERIFY(txn->put(key, value));
         }
         QVERIFY(txn->commit(0));
+    } else if (btreeType == KeyValue) {
+        QKeyValueStoreTxn *txn = keyValueDb->beginWrite();
+        QVERIFY(txn);
+        for (int i = 0; i < numItems * gapLength; i += gapLength) {
+            QByteArray key = QByteArray::number(i);
+            QByteArray value = QByteArray::number(i);
+            QVERIFY(txn->put(key, value));
+        }
+        QVERIFY(txn->commit(0));
     }
 
 
@@ -457,6 +586,95 @@ void TestBtrees::searchRange()
                 txn->abort();
             }
         }
+    } else if (btreeType == KeyValue) {
+        QBENCHMARK {
+            for (int i = 0; i < (numItems * gapLength) - (gapLength); i += (gapLength / 10)) {
+                QByteArray key = QByteArray::number(i);
+                QKeyValueStoreTxn *txn = keyValueDb->beginRead();
+                QKeyValueStoreCursor cursor(txn);
+                QVERIFY(cursor.seekRange(key));
+                txn->abort();
+            }
+        }
+    }
+}
+
+void TestBtrees::compact_data()
+{
+    QTest::addColumn<int>("btreeType");
+    QTest::newRow(appendOnlyDataTag) << (int)AppendOnly;
+    QTest::newRow(keyValueDataTag) << (int)KeyValue;
+}
+
+void TestBtrees::compact()
+{
+    QFETCH(int, btreeType);
+    int numItems = 1000;
+
+    if (btreeType == AppendOnly) {
+        for (int i = 0; i < numItems; ++i) {
+            QBtreeTxn *txn = appendOnlyDb->beginWrite();
+            QVERIFY(txn);
+            QByteArray key = QByteArray::number(i);
+            QByteArray value = QByteArray::number(i);
+            QVERIFY(txn->put(key, value));
+            QVERIFY(txn->commit(i));
+        }
+        appendOnlyDb->sync();
+        for (int i = 0; i < numItems; ++i) {
+            QBtreeTxn *txn = appendOnlyDb->beginWrite();
+            QVERIFY(txn);
+            QByteArray key = QByteArray::number(i);
+            QByteArray value = QByteArray::number(i);
+            QVERIFY(txn->put(key, value));
+            QVERIFY(txn->commit(i));
+        }
+        appendOnlyDb->sync();
+        for (int i = 0; i < numItems/2; ++i) {
+            QBtreeTxn *txn = appendOnlyDb->beginWrite();
+            QVERIFY(txn);
+            QByteArray key = QByteArray::number(i);
+            QVERIFY(txn->remove(key));
+            QVERIFY(txn->commit(i));
+        }
+        appendOnlyDb->sync();
+    } else if (btreeType == KeyValue) {
+        keyValueDb->setSyncThreshold(0);
+        for (int i = 0; i < numItems; ++i) {
+            QKeyValueStoreTxn *txn = keyValueDb->beginWrite();
+            QVERIFY(txn);
+            QByteArray key = QByteArray::number(i);
+            QByteArray value = QByteArray::number(i);
+            QVERIFY(txn->put(key, value));
+            QVERIFY(txn->commit(i));
+        }
+        keyValueDb->sync();
+        for (int i = 0; i < numItems; ++i) {
+            QKeyValueStoreTxn *txn = keyValueDb->beginWrite();
+            QVERIFY(txn);
+            QByteArray key = QByteArray::number(i);
+            QByteArray value = QByteArray::number(i);
+            QVERIFY(txn->put(key, value));
+            QVERIFY(txn->commit(i));
+        }
+        keyValueDb->sync();
+        for (int i = 0; i < numItems/2; ++i) {
+            QKeyValueStoreTxn *txn = keyValueDb->beginWrite();
+            QVERIFY(txn);
+            QByteArray key = QByteArray::number(i);
+            QVERIFY(txn->remove(key));
+            QVERIFY(txn->commit(i));
+        }
+        keyValueDb->sync();
+    }
+    if (btreeType == AppendOnly) {
+        QBENCHMARK_ONCE {
+            QVERIFY(appendOnlyDb->compact());
+        }
+    } else if (btreeType == KeyValue) {
+        QBENCHMARK_ONCE {
+            QVERIFY(keyValueDb->compact());
+        }
     }
 }