Mercurial > dedupe

changeset 16:06166d6c083b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add configuration processing. Cache DB values Add a custom RBTree to save space. Track multiple DB connections properly. More testing. Add ValueExistsException.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Tue, 28 Aug 2012 18:58:02 +0200
parents 199fc63c60c1
children 9a1825df8418
files CMakeLists.txt CompileTimeConstants.h ConfigurationProcessing.cpp ConfigurationProcessing.hpp DBCache.hpp DataController.cpp EditDistance.cpp EditDistance.hpp Exception.hpp RBTree.hpp SqliteDBLink.cpp TestDBCache.cpp TestEditDistance.cpp TestRBTree.cpp ThreadSafeLookup.hpp UniqueString.cpp UniqueString.hpp ValueExistsException.hpp
diffstat 18 files changed, 1081 insertions(+), 28 deletions(-) [+]
line wrap: on
line diff
--- a/CMakeLists.txt	Sat Aug 25 01:42:13 2012 +0200
+++ b/CMakeLists.txt	Tue Aug 28 18:58:02 2012 +0200
@@ -30,6 +30,20 @@
 	FileDBLink.cpp
 	SqliteDBLink.cpp
 	MemoryDBLink.cpp
+	ConfigurationProcessing.cpp
+	UniqueString.cpp
+)
+
+SET(CLASS_HEADERS
+	DataController.hpp
+	EditDistance.hpp
+	IOException.hpp
+	FileDBLink.hpp
+	SqliteDBLink.hpp
+	MemoryDBLink.hpp
+	ConfigurationProcessing.hpp
+	UniqueString.hpp
+	RBTree.hpp
 )
 
 SET(MOC_HEADERS
@@ -41,6 +55,7 @@
 
 SET(SOURCES
 	${CLASS_SOURCES}
+	${CLASS_HEADERS}
 	${MOC_SOURCES}
 )
 
@@ -52,7 +67,7 @@
 
 
 
-SET(CMAKE_CXX_FLAGS "-g2 -Wall -Werror -fno-inline")
+SET(CMAKE_CXX_FLAGS "-g2 -Wall -fno-inline")
 ADD_EXECUTABLE(DeDupe DeDupe.cpp ${SOURCES} ${MOC_SOURCES})
 TARGET_LINK_LIBRARIES(DeDupe ${QT_LIBRARIES} ${SQLITE3_LIBRARIES} ${Boost_LIBRARIES})
 
@@ -65,8 +80,17 @@
 ADD_TEST(TestEditDistance TestEditDistance)
 TARGET_LINK_LIBRARIES(TestEditDistance ${QT_LIBRARIES} ${Boost_LIBRARIES})
 
+#ADD_EXECUTABLE(TestDBCache TestDBCache.cpp ${TEST_SOURCES})
+ADD_EXECUTABLE(TestDBCache TestDBCache.cpp)
+ADD_TEST(TestDBCache TestDBCache)
+TARGET_LINK_LIBRARIES(TestDBCache ${QT_LIBRARIES} ${Boost_LIBRARIES})
+
 ADD_EXECUTABLE(TestSqliteDBLink TestSqliteDBLink.cpp ${TEST_SOURCES})
 ADD_TEST(TestSqliteDBLink TestSqliteDBLink)
 TARGET_LINK_LIBRARIES(TestSqliteDBLink ${QT_LIBRARIES} ${Boost_LIBRARIES} )
 
+ADD_EXECUTABLE(TestRBTree TestRBTree.cpp ${TEST_SOURCES})
+ADD_TEST(TestRBTree TestRBTree)
+TARGET_LINK_LIBRARIES(TestRBTree ${QT_LIBRARIES} ${Boost_LIBRARIES} )
+
 #ADD_PRECOMPILED_HEADER(TestEditDistance TestFramework.hpp)
--- a/CompileTimeConstants.h	Sat Aug 25 01:42:13 2012 +0200
+++ b/CompileTimeConstants.h	Tue Aug 28 18:58:02 2012 +0200
@@ -5,6 +5,10 @@
 #define DB_DEFAULT_LOCATION "~/.DeDupe.sqlite"
 #endif
 
+#ifndef EDITDISTANCE_CACHE_LOCATION
+#define EDITDISTANCE_CACHE_LOCATION "~/.EditDistance.sqlite"
+#endif
+
 #ifndef USE_BOOST_FIND
 #define USE_BOOST_FIND 1
 #endif
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ConfigurationProcessing.cpp	Tue Aug 28 18:58:02 2012 +0200
@@ -0,0 +1,13 @@
+#include "ConfigurationProcessing.hpp"
+
+#include <QtGui/QDesktopServices>
+#include <QtCore/QRegExp>
+#include <QtCore/QDir>
+
+QString processSetupVariables(const QString& inString)
+{
+  QString outString = inString;
+  outString.replace(QRegExp("^~/"),
+		    QString("%1%2").arg(QDesktopServices::storageLocation(QDesktopServices::HomeLocation)).arg(QDir::separator()));
+  return outString;
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ConfigurationProcessing.hpp	Tue Aug 28 18:58:02 2012 +0200
@@ -0,0 +1,8 @@
+#ifndef CONFIGURATIONPROCESSING_HPP
+#define CONFIGURATIONPROCESSING_HPP
+
+#include <QtCore/QString>
+
+QString processSetupVariables(const QString& inString);
+
+#endif //CONFIGURATIONPROCESSING_HPP
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/DBCache.hpp	Tue Aug 28 18:58:02 2012 +0200
@@ -0,0 +1,360 @@
+#ifndef DBCACHE_HPP
+#define DBCACHE_HPP
+
+#include <QtSql/QSqlDatabase>
+#include <QtSql/QSqlQuery>
+#include <QtSql/QSqlError>
+#include <QtSql/QSqlRecord>
+
+#include <QtCore/QDebug>
+#include <QtCore/QStringList>
+#include <cassert>
+#include "OrderedPair.hpp"
+
+#include <boost/optional.hpp>
+
+#include "ThreadSafeLookup.hpp"
+#include "UniqueString.hpp"
+
+
+template<typename T>
+struct SQLGenerator
+{
+};
+
+template<>
+struct SQLGenerator<int>
+{
+  static QString fieldName(const QString &prefix = QString())
+  {
+    return QString("%1_Int").arg(prefix);
+  }
+
+  static QString createFields(const QString &prefix = QString())
+  {
+    return QString("%1 INTEGER").arg(fieldName(prefix));
+  }
+
+  static QString valueString(const QString &prefix = QString())
+  {
+    return QString(":") + fieldName(prefix);
+  }
+
+  static void bindValue(QSqlQuery& query, int value, const QString& prefix = QString())
+  {
+    query.bindValue(valueString(prefix), value);
+  }
+
+  static void bindValues(QSqlQuery& query, const QVariantList& values, const QString& prefix = QString())
+  {
+    query.bindValue(valueString(prefix), values);
+  }
+
+  static void bindValues(QSqlQuery& query, const QList<int>& values, const QString& prefix = QString())
+  {
+    QVariantList list;
+    foreach(int value, values) {
+      list << value;
+    }
+    bindValues(query, list, prefix);
+  }
+
+  static boost::optional<int> extract(QSqlQuery& query, const QString& prefix = QString())
+  {
+    int fieldNo = query.record().indexOf(fieldName(prefix));
+    if (query.at() >= 0)
+      return query.value(fieldNo).toInt();
+    else
+      return boost::optional<int>();
+  }
+
+};
+
+template<>
+struct SQLGenerator<QString>
+{
+  static QString fieldName(const QString &prefix = QString())
+  {
+    return QString("%1_QString").arg(prefix);
+  }
+
+  static QString createFields(const QString &prefix = QString())
+  {
+    return QString("%1 TEXT").arg(fieldName(prefix));
+  }
+
+  static QString valueString(const QString &prefix = QString())
+  {
+    return QString(":") + fieldName(prefix);
+  }
+
+  static QString restrict(const QString &prefix = QString())
+  {
+    return QString("%1 = %2").arg(fieldName(prefix)).arg(valueString(prefix));
+  }
+
+  static void bindValue(QSqlQuery& query, const QString& value, const QString& prefix = QString())
+  {
+    query.bindValue(valueString(prefix), value);
+  }
+
+  static void bindValues(QSqlQuery& query, const QVariantList& value, const QString& prefix = QString())
+  {
+    query.bindValue(valueString(prefix), value);
+  }
+
+  static void bindValues(QSqlQuery& query, const QList<QString>& values, const QString& prefix = QString())
+  {
+    QVariantList list;
+    foreach(const QString& value, values) {
+      list << value;
+    }
+    bindValues(query, list, prefix);
+  }
+
+  static boost::optional<QString> extract(QSqlQuery& query, const QString& prefix = QString())
+  {
+    int fieldNo = query.record().indexOf(fieldName(prefix));
+    if (query.at() >= 0)
+      return query.value(fieldNo).toString();
+    else
+      return boost::optional<QString>();
+  }
+
+
+};
+
+template<>
+struct SQLGenerator<UniqueString>
+{
+  static QString fieldName(const QString &prefix = QString())
+  {
+    return QString("%1_QString").arg(prefix);
+  }
+
+  static QString createFields(const QString &prefix = QString())
+  {
+    return QString("%1 TEXT").arg(fieldName(prefix));
+  }
+
+  static QString valueString(const QString &prefix = QString())
+  {
+    return QString(":") + fieldName(prefix);
+  }
+
+  static QString restrict(const QString &prefix = QString())
+  {
+    return QString("%1 = %2").arg(fieldName(prefix)).arg(valueString(prefix));
+  }
+
+  static void bindValue(QSqlQuery& query, const QString& value, const QString& prefix = QString())
+  {
+    query.bindValue(valueString(prefix), value);
+  }
+
+  static void bindValues(QSqlQuery& query, const QVariantList& value, const QString& prefix = QString())
+  {
+    query.bindValue(valueString(prefix), value);
+  }
+
+  static void bindValues(QSqlQuery& query, const QList<UniqueString>& values, const QString& prefix = QString())
+  {
+    QVariantList list;
+    foreach(const QString& value, values) {
+      list << value;
+    }
+    bindValues(query, list, prefix);
+  }
+
+  static boost::optional<QString> extract(QSqlQuery& query, const QString& prefix = QString())
+  {
+    int fieldNo = query.record().indexOf(fieldName(prefix));
+    if (query.at() >= 0)
+      return query.value(fieldNo).toString();
+    else
+      return boost::optional<QString>();
+  }
+
+
+};
+
+template<typename T>
+struct SQLGenerator<OrderedPair<T> >
+{
+  static QString fieldName(const QString &prefix = QString())
+  {
+    return SQLGenerator<T>::fieldName(prefix + "_1") + ", " +
+      SQLGenerator<T>::fieldName(prefix + "_2");
+  }
+
+  static QString createFields(const QString &prefix = QString())
+  {
+    return SQLGenerator<T>::createFields(prefix + "_1") + ", " +
+      SQLGenerator<T>::createFields(prefix + "_2");
+  }
+
+  static QString restriction(const QString& prefix = QString())
+  {
+    return SQLGenerator<T>::restrict(prefix + "_1") + " AND " +
+      SQLGenerator<T>::restrict(prefix + "_2");    
+  }
+
+  static QString valueString(const QString &prefix = QString())
+  {
+    return SQLGenerator<T>::valueString(prefix + "_1") + ", " +
+      SQLGenerator<T>::valueString(prefix + "_2");
+  }
+
+  static void bindValue(QSqlQuery& query, const OrderedPair<T>& value, const QString& prefix = QString())
+  {
+    SQLGenerator<T>::bindValue(query, value.first, prefix + "_1");
+    SQLGenerator<T>::bindValue(query, value.second, prefix + "_2");
+  }
+
+  static void bindValues(QSqlQuery& query, const QList<OrderedPair<T> >& values, const QString& prefix = QString())
+  {
+    QList<T> first;
+    QList<T> second;
+    foreach(OrderedPair<T> value, values) {
+      first << value.first;
+      second << value.second;
+    }
+    SQLGenerator<T>::bindValues(query, first, prefix + "_1");
+    SQLGenerator<T>::bindValues(query, second, prefix + "_2");
+  }
+
+  static boost::optional<OrderedPair<T> > extract(QSqlQuery& query, const QString& prefix = QString())
+  {
+    if (query.at() >= 0)
+      return OrderedPair<T> (*SQLGenerator<T>::extract(query, prefix + "_1"),
+			     *SQLGenerator<T>::extract(query, prefix + "_2"));
+    else
+      return boost::optional<OrderedPair<T> >();
+  }
+
+
+};
+
+template<typename Key, typename Value, bool memoryMapped = false>
+class DBCache
+{
+private:
+  ThreadSafeLookup<Key, Value> memoryMap;
+  QList<Key> unsyncedKeys;
+
+  void setup(const QSqlDatabase& db, const QString& dictName)
+  {
+    this->dictName = dictName;
+    if (!db.tables().contains(dictName)) {
+      QString keyFields = SQLGenerator<Key>::createFields("key");
+      QString valueFields = SQLGenerator<Value>::createFields("value");
+      QString createQuery = QString("CREATE TABLE %1(%2, %3);").arg(dictName).arg(keyFields).arg(valueFields);
+      QSqlQuery query(db);
+      query.exec(createQuery);
+    }
+    if (!db.tables().contains(dictName)) {
+      qDebug()<<"No database";
+      exit(1);
+    }
+    if (memoryMapped) {
+      QString keyFields = SQLGenerator<Key>::fieldName("key");
+      QString valueFields = SQLGenerator<Value>::fieldName("value");
+      QString repopulateQuery = QString("SELECT %1, %2 FROM %3;").arg(keyFields).arg(valueFields).arg(dictName);
+      QSqlQuery query(db);
+      if (!query.exec(repopulateQuery)) {
+	qDebug() << query.lastError() << repopulateQuery;
+      }
+      while (query.next()) {
+	Key key = *SQLGenerator<Key>::extract(query, "key");
+	Value value = *SQLGenerator<Value>::extract(query, "value");
+	memoryMap.insert(key, value);
+      }
+    }
+    QString queryString = QString("INSERT into %1 (%2, %3) VALUES(%4, %5);")
+      .arg(dictName)
+      .arg(SQLGenerator<Key>::fieldName("key"))
+      .arg(SQLGenerator<Value>::fieldName("value"))
+      .arg(SQLGenerator<Key>::valueString("key"))
+      .arg(SQLGenerator<Value>::valueString("value"));
+    insertQuery = QSqlQuery(db);
+    insertQuery.prepare(queryString);
+  }
+
+  void syncInsert()
+  {
+    SQLGenerator<Key>::bindValues(insertQuery, unsyncedKeys, "key");
+    QList<Value> values;
+    foreach(Key key, unsyncedKeys) {
+      values << *memoryMap.value(key);
+    }
+    SQLGenerator<Value>::bindValues(insertQuery, values, "value");
+    if (!insertQuery.exec()) {
+      qDebug() << insertQuery.lastError() << insertQuery.lastQuery();
+    }
+    insertQuery.finish();
+    unsyncedKeys.clear();
+  }
+
+public:
+  DBCache(const QString& dbName, const QString& dictName) 
+  {
+    db = QSqlDatabase::addDatabase("QSQLITE", "dictName");
+    db.setDatabaseName(dbName);
+    bool ok = db.open();
+    assert(ok);
+    setup(db, dictName);
+  }
+
+  DBCache(const QSqlDatabase& db, const QString& dictName) 
+  {
+    setup(db, dictName);
+  }
+
+  boost::optional<Value> value(const Key& key) const
+  {
+    if (memoryMapped) {
+      return memoryMap.value(key);
+    }
+    else {
+      QString queryString = QString("SELECT %1 FROM %2 WHERE %3")
+	.arg(SQLGenerator<Value>::fieldName("value"))
+	.arg(dictName)
+	.arg(SQLGenerator<Key>::restriction("key"));
+      QSqlQuery query(db);
+      query.prepare(queryString);
+      SQLGenerator<Key>::bindValue(query, key, "key");
+      if (!query.exec()) {
+	qDebug() << query.lastError() << queryString;
+      }
+      query.next();
+      return SQLGenerator<Value>::extract(query, "value");
+    }
+  }
+
+  void insert(const Key& key, const Value& value)
+  {
+    if (memoryMapped) {
+      memoryMap.insert(key, value);
+      unsyncedKeys.append(key);
+      if (unsyncedKeys.size() > 1024) {
+	syncInsert();
+      }
+    }
+    else {
+      SQLGenerator<Key>::bindValue(insertQuery, key, "key");
+      SQLGenerator<Value>::bindValue(insertQuery, value, "value");
+      if (!insertQuery.exec()) {
+	qDebug() << insertQuery.lastError() << insertQuery.lastQuery();
+      }
+      insertQuery.finish();
+    }
+      
+  }
+
+private:
+  QSqlDatabase db;
+  QString dictName;
+  QSqlQuery insertQuery;
+};
+
+#endif //DBCACHE_HPP
--- a/DataController.cpp	Sat Aug 25 01:42:13 2012 +0200
+++ b/DataController.cpp	Tue Aug 28 18:58:02 2012 +0200
@@ -4,6 +4,7 @@
 #include "MemoryDBLink.hpp"
 #include "PermissionException.hpp"
 #include "SqliteDBLink.hpp"
+#include "ConfigurationProcessing.hpp"
 
 #include <QtCore/QCryptographicHash>
 #include <QtCore/QDateTime>
@@ -446,7 +447,6 @@
   QDesktopServices::openUrl(url);  
 }
 
-
 void DataController::setup(const QString& dbpath_in, const QString& searchPath_in, bool showGUI)
 {
   this->showGUI = showGUI;
@@ -460,10 +460,7 @@
     dbpath = dbpath_in;
   }
   else {
-    dbpath = DB_DEFAULT_LOCATION;
-    
-    dbpath.replace(QRegExp("^~/"),
-		   QString("%1%2").arg(QDesktopServices::storageLocation(QDesktopServices::HomeLocation)).arg(QDir::separator()));
+    dbpath = processSetupVariables(DB_DEFAULT_LOCATION);
   }
 
 #if 1
--- a/EditDistance.cpp	Sat Aug 25 01:42:13 2012 +0200
+++ b/EditDistance.cpp	Tue Aug 28 18:58:02 2012 +0200
@@ -1,10 +1,13 @@
 #include "EditDistance.hpp"
+#include "CompileTimeConstants.h"
+#include "ConfigurationProcessing.hpp"
 
 #include <QtCore/QList>
 
 #define CharComparer(A, B) (QChar(A) == QChar(B))
 
-EditDistance::cacheType EditDistance::cache;
+EditDistance::cacheType* EditDistance::cache = 0;
+//EditDistance::cacheType EditDistance::cache;
 
 QString EditDistance::removeDiacritics(QString in)
 {
@@ -27,9 +30,13 @@
     b = removeDiacritics(b);
   }
 
-  OrderedPair<QString> lup(a, b);
+  OrderedPair<UniqueString> lup(a, b);
 
-  boost::optional<int> res = cache.value(lup);
+  if (cache == 0) {
+    QString cacheLocation = processSetupVariables(EDITDISTANCE_CACHE_LOCATION);
+    EditDistance::cache = new cacheType(cacheLocation, "EditLUT");
+  }
+  boost::optional<int> res = cache->value(lup);
   if (res)
     return *res;
 
@@ -74,7 +81,7 @@
   
   // Return final value
   int retVal = d[a.size()][ b.size()];
-  cache.insert(lup, retVal);
+  cache->insert(lup, retVal);
 
   return retVal;
 }
--- a/EditDistance.hpp	Sat Aug 25 01:42:13 2012 +0200
+++ b/EditDistance.hpp	Tue Aug 28 18:58:02 2012 +0200
@@ -2,6 +2,8 @@
 #define EDITDISTANCE_HPP
 
 #include "OrderedPair.hpp"
+#include "DBCache.hpp"
+#include "UniqueString.hpp"
 
 #include <QtCore/QString>
 #include <QtCore/QMap>
@@ -11,14 +13,16 @@
 
 class EditDistance {
 protected:
-  typedef ThreadSafeLookup<OrderedPair<QString>, int> cacheType;
+  //typedef ThreadSafeLookup<OrderedPair<QString>, int> cacheType;
+  typedef DBCache<OrderedPair<UniqueString>, int, true> cacheType;
   //typedef QMap<OrderedPair<QString>, int> cacheType;
   //typedef QHash<OrderedPair<QString>, int> cacheType;
 public:
   static int Compute(QString a, QString b, bool removeDiacritics = false);
   static QString removeDiacritics(QString in);
 
-  static cacheType cache; 
+  //static cacheType cache; 
+  static cacheType* cache;
 };
 
 #endif //EDITDISTANCE_HPP
--- a/Exception.hpp	Sat Aug 25 01:42:13 2012 +0200
+++ b/Exception.hpp	Tue Aug 28 18:58:02 2012 +0200
@@ -19,7 +19,7 @@
 
 
 protected:
-  Exception(const string_t& errorMsg) : errorMsg_(errorMsg) {}
+  Exception(const string_t& errorMsg = string_t()) : errorMsg_(errorMsg) {}
   virtual ~Exception() {}
 
   void setErrorMsg(string_t& errorMsg);
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/RBTree.hpp	Tue Aug 28 18:58:02 2012 +0200
@@ -0,0 +1,344 @@
+#ifndef RBTREE_HPP
+#define RBTREE_HPP
+
+#include <boost/optional.hpp>
+#include <cmath>
+#include "ValueExistsException.hpp"
+
+#include <QtCore/QDebug>
+
+#define CONSISTENCY_CHECKING 0
+
+#if CONSISTENCY_CHECKING
+#define CONSISTENCY_CHECK(n) assert(!n || (n)->consistent())
+#else
+#define CONSISTENCY_CHECK(n)
+#endif
+
+template<typename Data>
+class RBTree {
+private:
+  class RBTreeNode {
+    Data data;
+    RBTreeNode* left;
+    RBTreeNode *right;
+    RBTreeNode *parent;
+    bool red;
+
+    enum Color { RED, BLACK };
+
+  public:
+    RBTreeNode(const Data& data) : left(0), right(0), parent(0), red(true)
+    {
+      this->data = data;
+    }
+
+    void setColor(Color color)
+    {
+      red = (color == RED);
+    }
+
+    Color color() const
+    {
+      return red ? RED : BLACK;
+    }
+
+    RBTreeNode* grandparent()
+    {
+      if ((this != NULL) && (this->parent != NULL))
+	return this->parent->parent;
+      else
+	return NULL;
+    }
+ 
+    RBTreeNode* uncle()
+    {
+      RBTreeNode* g = grandparent();
+      if (g == NULL)
+	return NULL; // No grandparent means no uncle
+      if (this->parent == g->left)
+	return g->right;
+      else
+	return g->left;
+    }
+
+    RBTreeNode* getRootNode()
+    {
+      RBTreeNode* p = this;
+      while(p->parent)
+	p = p->parent;
+      return p;
+    }
+
+    void rotate_left()
+    {
+      RBTreeNode* Q = this->right;
+      assert(Q);
+      //      Set Q to be the new root.
+      if (this->parent) {
+	if (this->parent->left == this) {
+	  this->parent->left = Q;
+	}
+	else {
+	  assert(this->parent->right == this);
+	  this->parent->right = Q;
+	}
+      }
+      this->right = Q->left;
+      if (this->right)
+	this->right->parent = this;
+      Q->left = this;
+      Q->parent = this->parent;
+      this->parent = Q;
+    }
+
+    void rotate_right()
+    {
+      RBTreeNode* P = this->left;
+      assert(P);
+      //Set P to be the new root.
+      if (this->parent) {
+	if (this->parent->left == this) {
+	  this->parent->left = P;
+	}
+	else {
+	  assert(this->parent->right == this);
+	  this->parent->right = P;
+	}
+      }
+      this->left = P->right;
+      if (this->left)
+	this->left->parent = this;
+      P->right = this;
+      P->parent = this->parent;
+      this->parent = P;
+    }
+
+    void insert_case5()
+    {
+      RBTreeNode* g = grandparent();
+      CONSISTENCY_CHECK(this);
+      CONSISTENCY_CHECK(g);
+      
+      this->parent->setColor(BLACK);
+      g->setColor(RED);
+      if (this == this->parent->left)
+	g->rotate_right();
+      else {
+	assert (this == this->parent->right);
+	g->rotate_left();
+      }
+    }
+    
+    void insert_case4()
+    {
+      RBTreeNode* g = grandparent();
+
+      CONSISTENCY_CHECK(this);
+
+      if (!g)
+	return;
+      CONSISTENCY_CHECK(g);
+
+      RBTreeNode* n = this;
+
+      if ((this == n->parent->right) && (n->parent == g->left)) {
+	n->parent->rotate_left();
+	n = n->left;
+      } else if ((n == n->parent->left) && (n->parent == g->right)) {
+	n->parent->rotate_right();
+	n = n->right;
+      }
+      n->insert_case5();
+    }
+
+
+    void insert_case3()
+    {
+      RBTreeNode *u = uncle();
+      CONSISTENCY_CHECK(this);
+      CONSISTENCY_CHECK(u);
+      
+      if ((u != NULL) && (u->color() == RED)) {
+	this->parent->setColor(BLACK);
+	u->setColor(BLACK);
+	RBTreeNode* g;
+	g = grandparent();
+	g->setColor(RED);
+	g->insert_case1();
+      } else {
+	insert_case4();
+      }
+    }
+
+    void insert_case2()
+    {
+      CONSISTENCY_CHECK(this);
+      if (this->parent->color() == BLACK)
+	return; /* Tree is still valid */
+      else
+	insert_case3();
+    }
+
+    void insert_case1()
+    {
+      CONSISTENCY_CHECK(this);
+
+      if (this->parent == NULL)
+	this->setColor(BLACK);
+      else
+	insert_case2();
+    }
+
+    void insert(const Data& data)
+    {
+      if (data < this->data) {
+	if (!left) {
+	  left = new RBTreeNode(data);
+	  left->parent = this;
+	  left->insert_case1();
+	}
+	else
+	  left->insert(data);
+      }
+      else if (data > this->data) {
+	if (!right) {
+	  right = new RBTreeNode(data);
+	  right->parent = this;
+	  right->insert_case1();
+	}
+	else
+	  right->insert(data);	
+      }
+      else {
+	throw ValueExistsException();
+      }
+      CONSISTENCY_CHECK(this);
+    }
+
+    boost::optional<Data> find(const Data& data)
+    {
+      if (this->data == data) {
+	return this->data;
+      }
+      else if (data < this->data) {
+	if (left)
+	  return left->find(data);
+	else
+	  return boost::optional<Data>();
+      }
+      else {
+	if (right)
+	  return right->find(data);
+	else
+	  return boost::optional<Data>();
+      }
+      return boost::optional<Data>();
+    }
+
+    uint size() const
+    {
+      return 1 + (left ? left->size() : 0) + (right ? right->size() : 0);
+    }
+
+    uint depth() const
+    {
+      return 1 + std::max((left ? left->depth() : 0), (right ? right->depth() : 0));
+    }
+
+    uint total_depth(uint n) const
+    {
+      return n + (left ? left->total_depth(n + 1) : 0) + (right ? right->total_depth(n + 1) : 0);
+    }
+
+    bool consistent() const 
+    {
+      bool retVal = true;
+      if (left)
+	retVal = retVal && (left->parent == this) && left->consistent();
+      if (right)
+	retVal = retVal && (right->parent == this) && right->consistent();
+      return retVal;
+    }
+
+    friend class RBTree;
+
+  };
+  RBTreeNode* node;
+public:
+  RBTree() : node(0)
+  {
+  }
+  
+  bool consistent() const 
+  {
+    if (node == 0)
+      return true;
+    if (node->parent == 0 && node->consistent())
+      return true;
+    return false;
+  }
+
+  void insert(const Data& data)
+  {
+    if (node == 0) {
+      node = new RBTreeNode(data);
+    }
+    else {
+      node->insert(data);
+    }
+    node = node->getRootNode();
+    CONSISTENCY_CHECK(this);
+  }
+  boost::optional<Data> find(const Data& data)
+  {
+    if (node) {
+      return node->find(data);
+    }
+    else
+      return boost::optional<Data>();
+  }
+
+  uint size() const
+  {
+    if (!node)
+      return 0;
+    else
+      return node->size();
+  }
+
+  uint depth() const
+  {
+    if (!node)
+      return 0;
+    return node->depth();
+  }
+
+  float avg_depth() const
+  {
+    if (!node)
+      return 0;
+    return double(total_depth())/size();
+  }
+
+  uint total_depth() const
+  {
+    if (!node)
+      return 0;
+    return node->total_depth(1);
+  }
+
+  uint optimal_depth() const
+  {
+    int s = size();
+    if (s == 0)
+      return 0;
+    int d = s;
+    int targetlevel = 1;
+    while (d >>= 1)
+      ++targetlevel;
+    return targetlevel;
+  }
+};
+
+#endif //RBTREE_HPP
--- a/SqliteDBLink.cpp	Sat Aug 25 01:42:13 2012 +0200
+++ b/SqliteDBLink.cpp	Tue Aug 28 18:58:02 2012 +0200
@@ -11,11 +11,11 @@
 
 SqliteDBLink::SqliteDBLink(const QString& dbPath)
 {
-  db = QSqlDatabase::addDatabase("QSQLITE");
+  db = QSqlDatabase::addDatabase("QSQLITE", "SqliteDBLink");
   db.setDatabaseName(dbPath);
   bool ok = db.open();
   assert(ok);
-  QSqlQuery query;
+  QSqlQuery query(db);
   if (!query.exec(QString("SELECT * FROM files;"))) {
     query.exec("CREATE TABLE files(path VARCHAR PRIMARY KEY ASC, size INTEGER, mtime TEXT, checksum TEXT);");
   }
@@ -33,7 +33,7 @@
 
 bool SqliteDBLink::exists(const QString& path)
 {
-  QSqlQuery query;
+  QSqlQuery query(db);
   query.prepare("SELECT path FROM files WHERE path = :path;");
   query.bindValue(":path", path);
   if (!query.exec()) {
@@ -44,7 +44,7 @@
 
 FileDBLink::DBStatus SqliteDBLink::existsWithMtime(const QString& path, const QDateTime& mtime)
 {
-  QSqlQuery query;
+  QSqlQuery query(db);
   query.prepare("SELECT mtime FROM files WHERE path = :path;");
   query.bindValue(":path", path);
   if (!query.exec()) {
@@ -69,7 +69,7 @@
 {
   if (exists(dbinfo.path()))
     return false;
-  QSqlQuery query;
+  QSqlQuery query(db);
   query.prepare("INSERT INTO files (path, size, mtime, checksum) "
 		"VALUES (:path, :size, :mtime, :checksum)");
   query.bindValue(":path", dbinfo.path());
@@ -89,7 +89,7 @@
 
 void SqliteDBLink::updateFile(const DBInfo& dbinfo)
 {
-  QSqlQuery query;
+  QSqlQuery query(db);
   query.prepare("UPDATE files SET size=:size, mtime=:mtime, checksum=:checksum WHERE path=:path");
   query.bindValue(":path", dbinfo.path());
   query.bindValue(":size", dbinfo.size());
@@ -124,7 +124,7 @@
 {
   QList<QSharedPointer<FileDBLink::DBInfo> > values;
 
-  QSqlQuery query;
+  QSqlQuery query(db);
 
   if (prefix.size() > 0) {
     query.prepare("SELECT * FROM files WHERE path LIKE :prefix");
@@ -158,12 +158,12 @@
 
 void SqliteDBLink::deleteFileFromDB(const QString& path)
 {
-  QSqlQuery query;
-    query.prepare("DELETE FROM files WHERE path = :path");
-    query.bindValue(":path", path);
-    if (!query.exec()) {
-      qDebug() << path << "::" << query.lastQuery() << "::" << query.lastError().text();
-    }
+  QSqlQuery query(db);
+  query.prepare("DELETE FROM files WHERE path = :path");
+  query.bindValue(":path", path);
+  if (!query.exec()) {
+    qDebug() << path << "::" << query.lastQuery() << "::" << query.lastError().text();
+  }
 }
 
 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/TestDBCache.cpp	Tue Aug 28 18:58:02 2012 +0200
@@ -0,0 +1,29 @@
+#include "DBCache.hpp"
+#include "OrderedPair.hpp"
+#include "TestFramework.hpp"
+
+#include <QtCore/QTemporaryFile>
+
+BOOST_AUTO_TEST_CASE( TestCache )
+{
+  QTemporaryFile sqlfile("XXXXXX.sqlite");
+  sqlfile.setAutoRemove(false);
+  sqlfile.open();
+
+  typedef OrderedPair<QString> key_t;
+
+  DBCache<key_t, int> cache (sqlfile.fileName(), "SomeLUT");
+  key_t key1("hei", "hei");
+  key_t key2("S'turday", "Sunday");
+
+  bool exists = cache.value(key1);
+  BOOST_REQUIRE_EQUAL(exists, false);
+  cache.insert(key1, 321);
+  BOOST_REQUIRE_EQUAL(cache.value(key1), 321);
+
+  exists = cache.value(key2);
+  BOOST_REQUIRE_EQUAL(exists, false);
+  cache.insert(key2, 19);
+  BOOST_REQUIRE_EQUAL(cache.value(key2), 19);
+
+}
--- a/TestEditDistance.cpp	Sat Aug 25 01:42:13 2012 +0200
+++ b/TestEditDistance.cpp	Tue Aug 28 18:58:02 2012 +0200
@@ -21,3 +21,9 @@
   BOOST_REQUIRE_EQUAL(EditDistance::removeDiacritics(QString::fromUtf8("Hånda")), "Handa");
   BOOST_REQUIRE_EQUAL(EditDistance::removeDiacritics(QString::fromUtf8("Líll")), "Lill");
 }
+
+BOOST_AUTO_TEST_CASE( TestStrangeChars )
+{
+  BOOST_REQUIRE_EQUAL(EditDistance::Compute("S'turday", "Sunday", false), 3);
+  BOOST_REQUIRE_EQUAL(EditDistance::Compute("S'turday", "Sunday", false), 3);
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/TestRBTree.cpp	Tue Aug 28 18:58:02 2012 +0200
@@ -0,0 +1,196 @@
+#include "RBTree.hpp"
+#include "TestFramework.hpp"
+
+#include <QtCore/QString>
+
+BOOST_AUTO_TEST_CASE( TestInsertLeftHeavy )
+{
+  RBTree<QString> map;
+
+  QString k1 = "9";
+  QString k2 = "8";
+  QString k3 = "7";
+  QString k4 = "6";
+
+  BOOST_REQUIRE(!map.find(k1));
+  BOOST_REQUIRE_EQUAL(map.depth(), 0u);
+  BOOST_REQUIRE_EQUAL(map.total_depth(), 0u);
+  BOOST_REQUIRE_EQUAL(map.size(), 0u);
+  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 0u);
+  map.insert(k1);
+  BOOST_REQUIRE_EQUAL(map.depth(), 1u);
+  BOOST_REQUIRE_EQUAL(map.total_depth(), 1u);
+  BOOST_REQUIRE_EQUAL(map.size(), 1u);
+  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 1u);
+  BOOST_REQUIRE_THROW(map.insert(k1), ValueExistsException);
+  BOOST_REQUIRE(map.find(k1));
+  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
+
+  BOOST_REQUIRE(!map.find(k3));
+  map.insert(k2);
+  BOOST_REQUIRE_EQUAL(map.depth(), 2u);
+  BOOST_REQUIRE_EQUAL(map.total_depth(), 3u);
+  BOOST_REQUIRE_EQUAL(map.size(), 2u);
+  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
+  BOOST_REQUIRE_THROW(map.insert(k2), ValueExistsException);
+  BOOST_REQUIRE(map.find(k1));
+  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
+  BOOST_REQUIRE(map.find(k2));
+  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
+
+  BOOST_REQUIRE(!map.find(k3));
+  map.insert(k3);
+  BOOST_WARN_EQUAL(map.depth(), 2u);
+  BOOST_WARN_EQUAL(map.total_depth(), 5u);
+  BOOST_REQUIRE_EQUAL(map.size(), 3u);
+  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
+  BOOST_REQUIRE_THROW(map.insert(k3), ValueExistsException);
+  BOOST_REQUIRE(map.find(k1));
+  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
+  BOOST_REQUIRE(map.find(k2));
+  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
+  BOOST_REQUIRE(map.find(k3));
+  BOOST_REQUIRE_EQUAL(*map.find(k3), k3);
+
+  BOOST_REQUIRE(!map.find(k4));
+  map.insert(k4);
+  BOOST_WARN_EQUAL(map.depth(), 2u);
+  BOOST_WARN_EQUAL(map.total_depth(), 8u);
+  BOOST_REQUIRE_EQUAL(map.size(), 4u);
+  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 3u);
+  BOOST_REQUIRE_THROW(map.insert(k4), ValueExistsException);
+  BOOST_REQUIRE(map.find(k1));
+  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
+  BOOST_REQUIRE(map.find(k2));
+  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
+  BOOST_REQUIRE(map.find(k4));
+  BOOST_REQUIRE_EQUAL(*map.find(k4), k4);
+}
+
+BOOST_AUTO_TEST_CASE( TestInsertRightHeavy )
+{
+  RBTree<QString> map;
+
+  QString k1 = "5";
+  QString k2 = "6";
+  QString k3 = "7";
+  QString k4 = "8";
+
+  BOOST_REQUIRE(!map.find(k1));
+  BOOST_REQUIRE_EQUAL(map.depth(), 0u);
+  BOOST_REQUIRE_EQUAL(map.total_depth(), 0u);
+  BOOST_REQUIRE_EQUAL(map.size(), 0u);
+  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 0u);
+  map.insert(k1);
+  BOOST_REQUIRE_EQUAL(map.depth(), 1u);
+  BOOST_REQUIRE_EQUAL(map.total_depth(), 1u);
+  BOOST_REQUIRE_EQUAL(map.size(), 1u);
+  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 1u);
+  BOOST_REQUIRE_THROW(map.insert(k1), ValueExistsException);
+  BOOST_REQUIRE(map.find(k1));
+  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
+
+  BOOST_REQUIRE(!map.find(k3));
+  map.insert(k2);
+  BOOST_REQUIRE_EQUAL(map.depth(), 2u);
+  BOOST_REQUIRE_EQUAL(map.total_depth(), 3u);
+  BOOST_REQUIRE_EQUAL(map.size(), 2u);
+  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
+  BOOST_REQUIRE_THROW(map.insert(k2), ValueExistsException);
+  BOOST_REQUIRE(map.find(k1));
+  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
+  BOOST_REQUIRE(map.find(k2));
+  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
+
+  BOOST_REQUIRE(!map.find(k3));
+  map.insert(k3);
+  BOOST_WARN_EQUAL(map.depth(), 2u);
+  BOOST_WARN_EQUAL(map.total_depth(), 5u);
+  BOOST_REQUIRE_EQUAL(map.size(), 3u);
+  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
+  BOOST_REQUIRE_THROW(map.insert(k3), ValueExistsException);
+  BOOST_REQUIRE(map.find(k1));
+  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
+  BOOST_REQUIRE(map.find(k2));
+  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
+  BOOST_REQUIRE(map.find(k3));
+  BOOST_REQUIRE_EQUAL(*map.find(k3), k3);
+
+  BOOST_REQUIRE(!map.find(k4));
+  map.insert(k4);
+  BOOST_WARN_EQUAL(map.depth(), 2u);
+  BOOST_WARN_EQUAL(map.total_depth(), 8u);
+  BOOST_REQUIRE_EQUAL(map.size(), 4u);
+  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 3u);
+  BOOST_REQUIRE_THROW(map.insert(k4), ValueExistsException);
+  BOOST_REQUIRE(map.find(k1));
+  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
+  BOOST_REQUIRE(map.find(k2));
+  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
+  BOOST_REQUIRE(map.find(k4));
+  BOOST_REQUIRE_EQUAL(*map.find(k4), k4);
+}
+
+BOOST_AUTO_TEST_CASE( TestInsertBalanced )
+{
+  RBTree<QString> map;
+
+  QString k1 = "8";
+  QString k2 = "4";
+  QString k3 = "12";
+  QString k4 = "2";
+
+  BOOST_REQUIRE(!map.find(k1));
+  BOOST_REQUIRE_EQUAL(map.depth(), 0u);
+  BOOST_REQUIRE_EQUAL(map.total_depth(), 0u);
+  BOOST_REQUIRE_EQUAL(map.size(), 0u);
+  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 0u);
+  map.insert(k1);
+  BOOST_REQUIRE_EQUAL(map.depth(), 1u);
+  BOOST_REQUIRE_EQUAL(map.total_depth(), 1u);
+  BOOST_REQUIRE_EQUAL(map.size(), 1u);
+  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 1u);
+  BOOST_REQUIRE_THROW(map.insert(k1), ValueExistsException);
+  BOOST_REQUIRE(map.find(k1));
+  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
+
+  BOOST_REQUIRE(!map.find(k3));
+  map.insert(k2);
+  BOOST_REQUIRE_EQUAL(map.depth(), 2u);
+  BOOST_REQUIRE_EQUAL(map.total_depth(), 3u);
+  BOOST_REQUIRE_EQUAL(map.size(), 2u);
+  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
+  BOOST_REQUIRE_THROW(map.insert(k2), ValueExistsException);
+  BOOST_REQUIRE(map.find(k1));
+  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
+  BOOST_REQUIRE(map.find(k2));
+  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
+
+  BOOST_REQUIRE(!map.find(k3));
+  map.insert(k3);
+  BOOST_WARN_EQUAL(map.depth(), 2u);
+  BOOST_WARN_EQUAL(map.total_depth(), 5u);
+  BOOST_REQUIRE_EQUAL(map.size(), 3u);
+  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 2u);
+  BOOST_REQUIRE_THROW(map.insert(k3), ValueExistsException);
+  BOOST_REQUIRE(map.find(k1));
+  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
+  BOOST_REQUIRE(map.find(k2));
+  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
+  BOOST_REQUIRE(map.find(k3));
+  BOOST_REQUIRE_EQUAL(*map.find(k3), k3);
+
+  BOOST_REQUIRE(!map.find(k4));
+  map.insert(k4);
+  BOOST_WARN_EQUAL(map.depth(), 2u);
+  BOOST_WARN_EQUAL(map.total_depth(), 8u);
+  BOOST_REQUIRE_EQUAL(map.size(), 4u);
+  BOOST_REQUIRE_EQUAL(map.optimal_depth(), 3u);
+  BOOST_REQUIRE_THROW(map.insert(k4), ValueExistsException);
+  BOOST_REQUIRE(map.find(k1));
+  BOOST_REQUIRE_EQUAL(*map.find(k1), k1);
+  BOOST_REQUIRE(map.find(k2));
+  BOOST_REQUIRE_EQUAL(*map.find(k2), k2);
+  BOOST_REQUIRE(map.find(k4));
+  BOOST_REQUIRE_EQUAL(*map.find(k4), k4);
+}
--- a/ThreadSafeLookup.hpp	Sat Aug 25 01:42:13 2012 +0200
+++ b/ThreadSafeLookup.hpp	Tue Aug 28 18:58:02 2012 +0200
@@ -31,10 +31,10 @@
   typedef QHash<Key_t, Value_t> map_t;
   map_t map;
 
-  typename Locking<isLocking>::Lock_t masterLock;
+  mutable typename Locking<isLocking>::Lock_t masterLock;
 public:
 
-  boost::optional<Value_t> value(const Key_t& key)
+  boost::optional<Value_t> value(const Key_t& key) const
   {
     boost::optional<Value_t> retVal;
     typename Locking<isLocking>::Locker_t lock(&masterLock);
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/UniqueString.cpp	Tue Aug 28 18:58:02 2012 +0200
@@ -0,0 +1,4 @@
+#include "UniqueString.hpp"
+
+//QMap<QString, QString> UniqueString::map;
+RBTree<QString> UniqueString::map;
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/UniqueString.hpp	Tue Aug 28 18:58:02 2012 +0200
@@ -0,0 +1,47 @@
+#ifndef UNIQUESTRING_HPP
+#define UNIQUESTRING_HPP
+
+#if 0
+#include <QtCore/QMap>
+#include <QtCore/QString>
+
+class UniqueString : public QString
+{
+private:
+  static QMap<QString, QString> map;
+  
+public:
+  UniqueString(const QString& str)
+  {
+    if (!map.contains(str)) {
+      map.insert(str, str);
+    }
+    QString::operator=(map.value(str)); 
+  }
+};
+#else
+#include "RBTree.hpp"
+#include <QtCore/QString>
+#include <QtCore/QDebug>
+
+class UniqueString : public QString
+{
+private:
+  static RBTree<QString> map;
+  
+public:
+  UniqueString(const QString& str)
+  {
+    boost::optional<QString> present = map.find(str);
+    if (!present) {
+      map.insert(str);
+      present = str;
+      //qDebug() << map.optimal_depth() << " : " << map.avg_depth() << " : " << map.depth();
+    }
+    QString::operator=(*present);
+
+  }
+};
+#endif
+
+#endif //UNIQUESTRING_HPP
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ValueExistsException.hpp	Tue Aug 28 18:58:02 2012 +0200
@@ -0,0 +1,10 @@
+#ifndef VALUEEXISTSEXCEPTION_HPP
+#define VALUEEXISTSEXCEPTION_HPP
+
+#include "Exception.hpp"
+
+class ValueExistsException : public Exception
+{
+};
+
+#endif //VALUEEXISTSEXCEPTION_HPP