--- a/CMakeLists.txt	Mon Dec 10 11:33:42 2012 +0100
+++ b/CMakeLists.txt	Wed Dec 12 13:17:42 2012 +0100
@@ -125,6 +125,7 @@
   Core/RestApi/RestApiOutput.cpp
   Core/RestApi/RestApi.cpp
   Core/MultiThreading/BagOfRunnablesBySteps.cpp
+  Core/MultiThreading/CacheIndex.cpp
   Core/PngWriter.cpp
   Core/SQLite/Connection.cpp
   Core/SQLite/FunctionContext.cpp
@@ -189,6 +190,7 @@
       UnitTests/Versions.cpp
       UnitTests/Zip.cpp
       UnitTests/FileStorage.cpp
+      UnitTests/MemoryCache.cpp
       UnitTests/main.cpp
       )
     target_link_libraries(UnitTests ServerLibrary CoreLibrary)

--- a/Core/Enumerations.h	Mon Dec 10 11:33:42 2012 +0100
+++ b/Core/Enumerations.h	Wed Dec 12 13:17:42 2012 +0100
@@ -47,6 +47,7 @@
     ErrorCode_NotEnoughMemory,
     ErrorCode_BadParameterType,
     ErrorCode_BadSequenceOfCalls,
+    ErrorCode_InexistentItem,
 
     // Specific error codes
     ErrorCode_UriSyntax,

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Core/MultiThreading/CacheIndex.cpp	Wed Dec 12 13:17:42 2012 +0100
@@ -0,0 +1,140 @@
+/**
+ * Orthanc - A Lightweight, RESTful DICOM Store
+ * Copyright (C) 2012 Medical Physics Department, CHU of Liege,
+ * Belgium
+ *
+ * This program is free software: you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * In addition, as a special exception, the copyright holders of this
+ * program give permission to link the code of its release with the
+ * OpenSSL project's "OpenSSL" library (or with modified versions of it
+ * that use the same license as the "OpenSSL" library), and distribute
+ * the linked executables. You must obey the GNU General Public License
+ * in all respects for all of the code used other than "OpenSSL". If you
+ * modify file(s) with this exception, you may extend this exception to
+ * your version of the file(s), but you are not obligated to do so. If
+ * you do not wish to do so, delete this exception statement from your
+ * version. If you delete this exception statement from all source files
+ * in the program, then also delete it here.
+ * 
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ **/
+
+
+#include "CacheIndex.h"
+
+#include <cassert>
+#include <string>
+#include "../OrthancException.h"
+#include "../IDynamicObject.h"
+
+namespace Orthanc
+{
+  template <typename T, typename Payload>
+  void CacheIndex<T, Payload>::CheckInvariants() const
+  {
+#ifndef NDEBUG
+    assert(index_.size() == queue_.size());
+
+    for (typename Index::const_iterator 
+           it = index_.begin(); it != index_.end(); it++)
+    {
+      assert(it->second != queue_.end());
+      assert(it->second->first == it->first);
+    }
+#endif
+  }
+
+
+  template <typename T, typename Payload>
+  void CacheIndex<T, Payload>::Add(T id, Payload payload)
+  {
+    if (Contains(id))
+    {
+      throw OrthancException(ErrorCode_BadSequenceOfCalls);
+    }
+
+    queue_.push_front(std::make_pair(id, payload));
+    index_[id] = queue_.begin();
+
+    CheckInvariants();
+  }
+
+
+  template <typename T, typename Payload>
+  void CacheIndex<T, Payload>::TagAsMostRecent(T id)
+  {
+    if (!Contains(id))
+    {
+      throw OrthancException(ErrorCode_InexistentItem);
+    }
+
+    typename Index::iterator it = index_.find(id);
+    assert(it != index_.end());
+
+    std::pair<T, Payload> item = *(it->second);
+    
+    queue_.erase(it->second);
+    queue_.push_front(item);
+    index_[id] = queue_.begin();
+
+    CheckInvariants();
+  }
+
+
+  template <typename T, typename Payload>
+  Payload CacheIndex<T, Payload>::Invalidate(T id)
+  {
+    if (!Contains(id))
+    {
+      throw OrthancException(ErrorCode_InexistentItem);
+    }
+
+    typename Index::iterator it = index_.find(id);
+    assert(it != index_.end());
+
+    Payload payload = it->second->second;
+    queue_.erase(it->second);
+    index_.erase(it);
+
+    CheckInvariants();
+    return payload;
+  }
+
+
+  template <typename T, typename Payload>
+  T CacheIndex<T, Payload>::RemoveOldest(Payload& payload)
+  {
+    if (IsEmpty())
+    {
+      throw OrthancException(ErrorCode_BadSequenceOfCalls);
+    }
+
+    std::pair<T, Payload> item = queue_.back();
+    T oldest = item.first;
+    payload = item.second;
+
+    queue_.pop_back();
+    assert(index_.find(oldest) != index_.end());
+    index_.erase(oldest);
+
+    CheckInvariants();
+
+    return oldest;
+  }
+
+
+  // Explicit template instanciation for some data types
+  template class CacheIndex<std::string, NullType>;
+  template class CacheIndex<std::string, int>;
+  template class CacheIndex<const char*, IDynamicObject*>;
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Core/MultiThreading/CacheIndex.h	Wed Dec 12 13:17:42 2012 +0100
@@ -0,0 +1,126 @@
+/**
+ * Orthanc - A Lightweight, RESTful DICOM Store
+ * Copyright (C) 2012 Medical Physics Department, CHU of Liege,
+ * Belgium
+ *
+ * This program is free software: you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation, either version 3 of the
+ * License, or (at your option) any later version.
+ *
+ * In addition, as a special exception, the copyright holders of this
+ * program give permission to link the code of its release with the
+ * OpenSSL project's "OpenSSL" library (or with modified versions of it
+ * that use the same license as the "OpenSSL" library), and distribute
+ * the linked executables. You must obey the GNU General Public License
+ * in all respects for all of the code used other than "OpenSSL". If you
+ * modify file(s) with this exception, you may extend this exception to
+ * your version of the file(s), but you are not obligated to do so. If
+ * you do not wish to do so, delete this exception statement from your
+ * version. If you delete this exception statement from all source files
+ * in the program, then also delete it here.
+ * 
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ **/
+
+
+#pragma once
+
+#include <list>
+#include <map>
+#include <boost/noncopyable.hpp>
+
+namespace Orthanc
+{
+  class NullType
+  {
+  };
+
+  /**
+   * This class implements the index of a cache with least recently
+   * used (LRU) recycling policy. All the items of the cache index
+   * can be associated with a payload.
+   * Reference: http://stackoverflow.com/a/2504317
+   **/
+  template <typename T, typename Payload = NullType>
+  class CacheIndex : public boost::noncopyable
+  {
+  private:
+    typedef std::list< std::pair<T, Payload> >  Queue;
+    typedef std::map<T, typename Queue::iterator>  Index;
+
+    Index  index_;
+    Queue  queue_;
+
+    /**
+     * Internal method for debug builds to check whether the internal
+     * data structures are not corrupted.
+     **/
+    void CheckInvariants() const;
+
+  public:
+    /**
+     * Add a new element to the cache index, and make it the most
+     * recent element.
+     * \param id The ID of the element.
+     * \param payload The payload of the element.
+     **/
+    void Add(T id, Payload payload = Payload());
+
+    /**
+     * When accessing an element of the cache, this method tags the
+     * element as the most recently used.
+     * \param id The most recently accessed item.
+     **/
+    void TagAsMostRecent(T id);
+
+    /**
+     * Remove an element from the cache index.
+     * \param id The item to remove.
+     **/
+    Payload Invalidate(T id);
+
+    /**
+     * Get the oldest element in the cache and remove it.
+     * \return The oldest item.
+     **/
+    T RemoveOldest()
+    {
+      Payload p;
+      return RemoveOldest(p);
+    }
+
+    /**
+     * Get the oldest element in the cache, remove it and return the
+     * associated payload.
+     * \param payload Where to store the associated payload.
+     * \return The oldest item.
+     **/
+    T RemoveOldest(Payload& payload);
+
+    /**
+     * Check whether an element is contained in the cache.
+     * \param id The item.
+     * \return \c true iff the item is indexed by the cache.
+     **/
+    bool Contains(T id) const
+    {
+      return index_.find(id) != index_.end();
+    }
+
+    /**
+     * Check whether the cache index is empty.
+     * \return \c true iff the cache is empty.
+     **/
+    bool IsEmpty() const
+    {
+      return index_.empty();
+    }
+  };
+}

--- a/Core/OrthancException.cpp	Mon Dec 10 11:33:42 2012 +0100
+++ b/Core/OrthancException.cpp	Wed Dec 12 13:17:42 2012 +0100
@@ -96,6 +96,9 @@
       case ErrorCode_FullStorage:
         return "The file storage is full";
 
+      case ErrorCode_InexistentItem:
+        return "Accessing an inexistent item";
+
       case ErrorCode_Custom:
       default:
         return "???";

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/UnitTests/MemoryCache.cpp	Wed Dec 12 13:17:42 2012 +0100
@@ -0,0 +1,81 @@
+#include "gtest/gtest.h"
+
+#include <memory>
+#include "../Core/IDynamicObject.h"
+#include "../Core/MultiThreading/CacheIndex.h"
+
+
+TEST(CacheIndex, Basic)
+{
+  Orthanc::CacheIndex<std::string> r;
+  
+  r.Add("d");
+  r.Add("a");
+  r.Add("c");
+  r.Add("b");
+
+  r.TagAsMostRecent("a");
+  r.TagAsMostRecent("d");
+  r.TagAsMostRecent("b");
+  r.TagAsMostRecent("c");
+  r.TagAsMostRecent("d");
+  r.TagAsMostRecent("c");
+
+  ASSERT_EQ("a", r.RemoveOldest());
+  ASSERT_EQ("b", r.RemoveOldest());
+  ASSERT_EQ("d", r.RemoveOldest());
+  ASSERT_EQ("c", r.RemoveOldest());
+
+  ASSERT_TRUE(r.IsEmpty());
+}
+
+
+TEST(CacheIndex, Payload)
+{
+  Orthanc::CacheIndex<std::string, int> r;
+  
+  r.Add("a", 420);
+  r.Add("b", 421);
+  r.Add("c", 422);
+  r.Add("d", 423);
+
+  r.TagAsMostRecent("a");
+  r.TagAsMostRecent("d");
+  r.TagAsMostRecent("b");
+  r.TagAsMostRecent("c");
+  r.TagAsMostRecent("d");
+  r.TagAsMostRecent("c");
+
+  ASSERT_TRUE(r.Contains("b"));
+  ASSERT_EQ(421, r.Invalidate("b"));
+  ASSERT_FALSE(r.Contains("b"));
+
+  int p;
+  ASSERT_EQ("a", r.RemoveOldest(p)); ASSERT_EQ(420, p);
+  ASSERT_EQ("d", r.RemoveOldest(p)); ASSERT_EQ(423, p);
+  ASSERT_EQ("c", r.RemoveOldest(p)); ASSERT_EQ(422, p);
+
+  ASSERT_TRUE(r.IsEmpty());
+}
+
+
+namespace Orthanc
+{
+  class MemoryCache
+  {
+  private:
+    struct CacheElement
+    {
+      std::string id_;
+      std::auto_ptr<IDynamicObject> object_;
+    };
+
+    //typedef std::map<CacheElement
+
+    size_t places_;
+    CacheIndex<const char*>  index_;
+
+  public:
+    
+  };
+}