New: introduce MUniqueStringCache

RevBy: Thomas Mönicke, Björn Schnabel, Peter Penz

Details:
MUniqueStringCache is a class to map strings to unique ids
across process boundaries.
The cache is backed up by a file which will be mmaped in every
process.
Locking ensures that the cache can be updated by multiple running
processes.

4 files changed, 544 insertions, 3 deletions

diff --git a/src/corelib/style/muniquestringcache.cpp b/src/corelib/style/muniquestringcache.cpp
new file mode 100644
index 00000000..1951b610
--- /dev/null
+++ b/src/corelib/style/muniquestringcache.cpp
@@ -0,0 +1,366 @@
+/***************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (directui@nokia.com)
+**
+** This file is part of libmeegotouch.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at directui@nokia.com.
+**
+** This library is free software; you can redistribute it and/or
+** modify it 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.
+**
+****************************************************************************/
+
+#include "muniquestringcache_p.h"
+#include "muniquestringcache.h"
+
+#include "mdebug.h"
+#include "mcomponentdata.h"
+
+#include <QFile>
+#include <QFileInfo>
+#include <QDir>
+#include <QSystemSemaphore>
+#include <QHash>
+#include <QByteArray>
+#include <QApplication>
+#include <QScopedPointer>
+
+const int MAX_CACHE_SIZE = 1024*1024;
+#define CACHE_NAME "MTF_UNIQUE_STRING_CACHE"
+
+class UniqueStringCacheMappedMemory
+{
+public:
+    UniqueStringCacheMappedMemory(const QString& filename)
+        : cacheFile(filename),
+        accessSemaphore(filename + "_UNIQUE_STRING_SEMAPHORE", 1),
+        attached(false),
+        locked(false)
+    {
+        if (!accessSemaphore.acquire()) {
+            mWarning("UniqueStringCacheMappedMemory::UniqueStringCacheMappedMemory") << "Unable to aquire semaphore:" << accessSemaphore.errorString();
+            return;
+        }
+
+        attachToCache();
+
+        accessSemaphore.release();
+    }
+
+    bool isAttached() const { return attached; }
+
+    uchar* data() { return rawMappedMemory; }
+    QString errorString() { return accessSemaphore.errorString(); }
+
+    ~UniqueStringCacheMappedMemory()
+    {
+    }
+
+    bool isLocked()
+    {
+        return locked;
+    }
+
+    bool lock() {
+        bool result = accessSemaphore.acquire();
+        locked = result;
+        return result;
+
+    }
+    bool unlock() {
+        locked = false;
+        return accessSemaphore.release();
+    }
+
+private:
+    friend class MUniqueStringCacheLocker;
+
+    void attachToCache()
+    {
+        if (!cacheFile.exists()) {
+            if (!initializeCache()) {
+                attached = false;
+                return;
+            }
+        }
+
+        if (!cacheFile.open(QIODevice::ReadWrite)) {
+            mWarning("UniqueStringCacheMappedMemory") << "Could not open" <<
+                cacheFile.fileName();
+            return;
+        }
+
+        if (cacheFile.size() != MAX_CACHE_SIZE) {
+            mWarning("UniqueStringCacheMappedMemory") << "Wrong cache file size" <<
+                cacheFile.size() << "Expected:" << MAX_CACHE_SIZE;
+            return;
+        }
+
+        rawMappedMemory = cacheFile.map(0, MAX_CACHE_SIZE);
+
+        attached = true;
+
+        cacheFile.close();
+    }
+
+    bool initializeCache() {
+        if (!cacheFile.open(QFile::WriteOnly)) {
+            //Maybe it failed because the directory doesn't exist
+            QDir().mkpath(QFileInfo(cacheFile.fileName()).absolutePath());
+            if (!cacheFile.open(QFile::WriteOnly)) {
+                mWarning("UniqueStringCacheMappedMemory") <<
+                         "Wrong permissions for cache directory. Cannot create" <<
+                          cacheFile.fileName();
+                return false;
+            }
+        }
+        cacheFile.resize(MAX_CACHE_SIZE);
+        cacheFile.close();
+        return true;
+    }
+
+    QFile cacheFile;
+    QSystemSemaphore accessSemaphore;
+    uchar* rawMappedMemory;
+    bool attached;
+    bool locked;
+};
+
+MUniqueStringCachePrivate::MUniqueStringCachePrivate(MUniqueStringCache *parent, const QString &filename)
+    : q_ptr(parent),
+    filename(filename),
+    uniqueStringCacheMappedMemory(new UniqueStringCacheMappedMemory(filename)),
+    offset(sizeof(int)),
+    cacheFilled(false),
+    stringToIdCacheFilled(false)
+{
+}
+
+MUniqueStringCachePrivate::~MUniqueStringCachePrivate()
+{
+    delete uniqueStringCacheMappedMemory;
+}
+
+// fills our datastructures from memory
+// this method can be called several times to update the internal representation
+// if the cache has been changed by another application
+void MUniqueStringCachePrivate::fillUniqueStringCache() {
+    uchar *rawCache = uniqueStringCacheMappedMemory->data();
+    int elementsInCache = *reinterpret_cast<int*>(rawCache);
+    int oldSize = idToOffsetCache.count();
+    idToStringCache.resize(elementsInCache);
+    idToOffsetCache.resize(elementsInCache);
+
+    for (int i = oldSize; i < elementsInCache; ++i) {
+        uchar *stringAdress = rawCache + offset;
+        int stringLength = *reinterpret_cast<int*>(stringAdress);
+
+        idToOffsetCache[i] = stringAdress;
+
+        offset += sizeof(int) + stringLength + 1;
+
+        if (stringToIdCacheFilled) {
+            stringToIdCache.insert(q_ptr->indexToString(i), i);
+        }
+    }
+    if (elementsInCache == 0) {
+        // we want the empty string as first element
+        insertStringToCache(QByteArray());
+    }
+
+    mDebug("MUniqueStringCachePrivate::fillUniqueStringCache")
+            << QString("Elements in cache %1: %2, %3% filled").arg(filename).arg(elementsInCache).arg((float)offset/MAX_CACHE_SIZE*100);
+}
+
+// insert one string into the cache, makes sure to handle it gracefully when the cache has
+// changed before it has been locked
+int MUniqueStringCachePrivate::insertStringToCache(const QByteArray &string) {
+    uchar *rawCache = uniqueStringCacheMappedMemory->data();
+    int elementsInCache = *reinterpret_cast<int*>(rawCache);
+    if (elementsInCache != idToOffsetCache.count()) {
+        // cache has changed, check if the string has been added
+        // in the meanwhile
+        fillUniqueStringCache();
+        if (!stringToIdCacheFilled) {
+            fillStringToIdCache();
+        }
+        StringToIdCache::const_iterator it = stringToIdCache.constFind(string);
+        if (it != stringToIdCache.constEnd()) {
+            return *it;
+        }
+    }
+
+    ++*reinterpret_cast<int*>(rawCache);
+
+    uchar *stringAdress = rawCache + offset;
+    *reinterpret_cast<int*>(stringAdress) = string.length();
+    memcpy(stringAdress + sizeof(int), string.constData(), string.length() + 1);
+
+    offset += sizeof(int) + string.length() + 1;
+    if (offset >= MAX_CACHE_SIZE) {
+        qFatal("unique string cache is full");
+    }
+
+    idToStringCache.append(string);
+    idToOffsetCache.append(0);
+    stringToIdCache.insert(string, idToStringCache.count() - 1);
+
+    return idToStringCache.count() - 1;
+}
+
+// triggers initialization of our data structures from the cache if this
+// did not happen yet
+void MUniqueStringCachePrivate::initiallyFillCache() {
+    if (!cacheFilled) {
+        QScopedPointer<MUniqueStringCacheLocker> locker;
+        if (!q_ptr->isLocked()) {
+            locker.reset(new MUniqueStringCacheLocker(q_ptr));
+            if (!locker->isLocked()) {
+                return;
+            }
+        }
+        fillUniqueStringCache();
+
+        cacheFilled = true;
+    }
+}
+
+QByteArray MUniqueStringCachePrivate::stringFromOffset(uchar *stringAdress)
+{
+    int stringLength = *reinterpret_cast<int*>(stringAdress);
+
+    return QByteArray::fromRawData(reinterpret_cast<const char*>(stringAdress + sizeof(int)), stringLength);
+}
+
+void MUniqueStringCachePrivate::fillStringToIdCache()
+{
+    mDebug("MUniqueStringCachePrivate::fillStringToIdCache") << "filling stringToIdCache for" << filename;
+    for (int i = 0; i < idToOffsetCache.count(); ++i) {
+        stringToIdCache.insert(q_ptr->indexToString(i), i);
+    }
+    stringToIdCacheFilled = true;
+}
+
+//////////////////////////////////////
+
+MUniqueStringCache::MUniqueStringCache(const QString& filename)
+    : d_ptr(new MUniqueStringCachePrivate(this, filename))
+{
+}
+
+MUniqueStringCache::~MUniqueStringCache()
+{
+    delete d_ptr;
+}
+
+bool MUniqueStringCache::isAttached()
+{
+    return d_ptr->uniqueStringCacheMappedMemory->isAttached();
+}
+
+MUniqueStringCache::Index MUniqueStringCache::stringToIndex(const QByteArray& string)
+{
+    if (string.isEmpty()) {
+        return EmptyStringIndex;
+    }
+
+    d_ptr->initiallyFillCache();
+
+    if (!d_ptr->stringToIdCacheFilled) {
+        d_ptr->fillStringToIdCache();
+    }
+
+    MUniqueStringCachePrivate::StringToIdCache::const_iterator it = d_ptr->stringToIdCache.constFind(string);
+    if (it != d_ptr->stringToIdCache.constEnd()) {
+        return *it;
+    }
+
+    // string is unknown, we need to add it to the cache
+    QScopedPointer<MUniqueStringCacheLocker> locker;
+    if (!isLocked()) {
+        locker.reset(new MUniqueStringCacheLocker(this));
+        if (!locker->isLocked()) {
+            return UndefinedIndex;
+        }
+    }
+    return d_ptr->insertStringToCache(string);
+}
+
+QByteArray MUniqueStringCache::indexToString(Index id)
+{
+    d_ptr->initiallyFillCache();
+    if (id < 0) {
+        return QByteArray();
+    } else if (id >= d_ptr->idToStringCache.count())  {
+        // it may be a new string in the cache. try to update the cache and then check again
+        QScopedPointer<MUniqueStringCacheLocker> locker;
+        if (!isLocked()) {
+            locker.reset(new MUniqueStringCacheLocker(this));
+            if (!locker->isLocked()) {
+                return QByteArray();
+            }
+        }
+        d_ptr->fillUniqueStringCache();
+        if (id >= d_ptr->idToStringCache.count()) {
+            mWarning("MUniqueStringCache::indexToString") << "Id" << id << "is unknown. Has the string cache been deleted?" << d_ptr->idToStringCache.count();
+            return QByteArray();
+        }
+    }
+
+    uchar *offset = d_ptr->idToOffsetCache.at(id);
+    if (offset != 0) {
+        QByteArray string = d_ptr->stringFromOffset(offset);
+        d_ptr->idToStringCache[id] = string;
+        d_ptr->idToOffsetCache[id] = 0;
+        return string;
+    } else {
+        return d_ptr->idToStringCache.at(id);
+    }
+}
+
+bool MUniqueStringCache::lock()
+{
+    return d_ptr->uniqueStringCacheMappedMemory->lock();
+}
+
+bool MUniqueStringCache::unlock()
+{
+    return d_ptr->uniqueStringCacheMappedMemory->unlock();
+}
+
+bool MUniqueStringCache::isLocked()
+{
+    return d_ptr->uniqueStringCacheMappedMemory->isLocked();
+}
+
+////////////////////////
+
+MUniqueStringCacheLocker::MUniqueStringCacheLocker(MUniqueStringCache *cache)
+    : cache(cache->lock() ? cache : (MUniqueStringCache *)0)
+{
+    if (!cache) {
+        mWarning("MUniqueStringCacheLocker") << "Unable to lock unique string cache" << cache->d_ptr->uniqueStringCacheMappedMemory->accessSemaphore.errorString();
+    }
+}
+
+MUniqueStringCacheLocker::~MUniqueStringCacheLocker()
+{
+    if (!cache) {
+        return;
+    }
+    if (!cache->unlock()) {
+        mWarning("MUniqueStringCacheLocker") << "Unable to unlock unique string cache" << cache->d_ptr->uniqueStringCacheMappedMemory->accessSemaphore.errorString();
+    }
+}
+
+bool MUniqueStringCacheLocker::isLocked() const
+{
+    return cache;
+}
diff --git a/src/corelib/style/muniquestringcache.h b/src/corelib/style/muniquestringcache.h
new file mode 100644
index 00000000..19a0b59e
--- /dev/null
+++ b/src/corelib/style/muniquestringcache.h
@@ -0,0 +1,110 @@
+/***************************************************************************
+**
+** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (directui@nokia.com)
+**
+** This file is part of libmeegotouch.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at directui@nokia.com.
+**
+** This library is free software; you can redistribute it and/or
+** modify it 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.
+**
+****************************************************************************/
+
+#ifndef MUNIQUESTRINGCACHE_H
+#define MUNIQUESTRINGCACHE_H
+
+#include <QByteArray>
+#include <QString>
+#include <QSharedPointer>
+
+class MUniqueStringCachePrivate;
+
+/**
+  * MUniqueStringCache can be used to map strings to unique ids.
+  * The mapping is backed up by a file on disk which will be mmaped
+  * into memory at runtime. Therefor the ids can be shared between
+  * several running programs. Additionally the memory occupied by the
+  * strings will be shared between the processes.
+  * Proper locking will make sure that two processes cannot add strings
+  * to the cache at the same time.
+  * Reading values from the cache happens without locking.
+  */
+class MUniqueStringCache
+{
+public:
+    MUniqueStringCache(const QString& filename);
+    ~MUniqueStringCache();
+
+    typedef int Index;
+    static const Index UndefinedIndex = -1;
+    static const Index EmptyStringIndex = 0;
+
+    /**
+      * Returns true when the cache is properly attached to the file on disk.
+      */
+    bool isAttached();
+
+    /**
+      * Converts a given index into a string. This lookup is very fast.
+      */
+    QByteArray indexToString(Index id);
+
+    /**
+      * Returns the id for a given string. If the string is not in the cache yet
+      * it will be added.
+      * If possible use this function only to fill the cache. To work it needs
+      * to read in the whole cache file to find the given string. Depending on
+      * the cache size this might be costly.
+      */
+    Index stringToIndex(const QByteArray& string);
+
+    /**
+      * indexToString() and stringToIndex() internally automatically lock the cache
+      * to ensure that no two processes are changing the cache at the same time.
+      * If you know that the cache needs to be locked very often, e.g. because stringToIndex()
+      * is called often with strings likely not in the cache, this method can be used to lock
+      * it just once. This avoids the need to lock and unlock it seperately for every call to
+      * stringToIndex().
+      * Make sure to call unlock() after all strings have been processed.
+      */
+    bool lock();
+
+    /**
+      * Unlocks the cache formerly locked with lock()
+      */
+    bool unlock();
+
+    /**
+      * Return true if the cache is locked.
+      */
+    bool isLocked();
+
+private:
+    friend class MUniqueStringCacheLocker;
+    MUniqueStringCachePrivate * const d_ptr;
+};
+
+/**
+  * Class which locks the cache when created and unlocks the cache once it gets out of scope.
+  */
+class MUniqueStringCacheLocker
+{
+public:
+    MUniqueStringCacheLocker(MUniqueStringCache *cache);
+
+    ~MUniqueStringCacheLocker();
+
+    bool isLocked() const;
+
+private:
+    MUniqueStringCache *cache;
+};
+
+#endif // MUNIQUESTRINGCACHE_H
diff --git a/src/corelib/style/muniquestringcache_p.h b/src/corelib/style/muniquestringcache_p.h
new file mode 100644
index 00000000..74c5ea90
--- /dev/null
+++ b/src/corelib/style/muniquestringcache_p.h
@@ -0,0 +1,62 @@
+/***************************************************************************
+**
+** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (directui@nokia.com)
+**
+** This file is part of libmeegotouch.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at directui@nokia.com.
+**
+** This library is free software; you can redistribute it and/or
+** modify it 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.
+**
+****************************************************************************/
+
+#ifndef MUNIQUESTRINGCACHE_P_H
+#define MUNIQUESTRINGCACHE_P_H
+
+#include <QString>
+#include <QHash>
+#include <QByteArray>
+#include <QVector>
+
+class MUniqueStringCache;
+class UniqueStringCacheMappedMemory;
+
+class MUniqueStringCachePrivate {
+public:
+    MUniqueStringCachePrivate(MUniqueStringCache *parent, const QString& filename);
+    ~MUniqueStringCachePrivate();
+
+    void fillUniqueStringCache();
+    int insertStringToCache(const QByteArray &string);
+    void initiallyFillCache();
+    QByteArray stringFromOffset(uchar *stringAdress);
+    void fillStringToIdCache();
+
+    MUniqueStringCache *q_ptr;
+
+    QString filename;
+
+    UniqueStringCacheMappedMemory *uniqueStringCacheMappedMemory;
+
+    // mapping id => string
+    typedef QVector<QByteArray> IdToStringCache;
+    IdToStringCache idToStringCache;
+    // mapping id => offset
+    QVector<uchar*> idToOffsetCache;
+    // mapping string => id
+    typedef QHash<QByteArray, int> StringToIdCache;
+    StringToIdCache stringToIdCache;
+    int offset;
+
+    bool cacheFilled;
+    bool stringToIdCacheFilled;
+};
+
+#endif
diff --git a/src/corelib/style/style.pri b/src/corelib/style/style.pri
index 43905df6..e30429c4 100644
--- a/src/corelib/style/style.pri
+++ b/src/corelib/style/style.pri
@@ -15,7 +15,8 @@ PRIVATE_HEADERS += \
     $$STYLE_SRC_DIR/mstylesheetselector.h \
     $$STYLE_SRC_DIR/mstylesheetattribute.h \
     $$STYLE_SRC_DIR/mstylesheet.h \
-    $$STYLE_SRC_DIR/mstylesheetselector_p.h
+    $$STYLE_SRC_DIR/mstylesheetselector_p.h \
+    $$STYLE_SRC_DIR/muniquestringcache.h \
 
 STYLE_HEADERS += \
     $$STYLE_SRC_DIR/mstyle.h \
@@ -49,7 +50,7 @@ STYLE_HEADERS += \
     $$STYLE_SRC_DIR/mcontentfadeandslideanimationstyle.h \
 
 PUBLIC_HEADERS += \
-    $$STYLE_HEADERS \
+    $$STYLE_HEADERS
 
 SOURCES += \
     $$STYLE_SRC_DIR/mstyle.cpp \
@@ -57,4 +58,6 @@ SOURCES += \
     $$STYLE_SRC_DIR/mstylesheet.cpp \
     $$STYLE_SRC_DIR/mstylesheetparser.cpp \
     $$STYLE_SRC_DIR/mstylesheetselector.cpp \
-    $$STYLE_SRC_DIR/mstylesheetattribute.cpp
+    $$STYLE_SRC_DIR/mstylesheetattribute.cpp \
+    $$STYLE_SRC_DIR/muniquestringcache.cpp \
+