# HG changeset patch
# User Sebastien Jodogne <s.jodogne@gmail.com>
# Date 1355322735 -3600
# Node ID c9977db00e1da48ab1a876fc455d0a32a9cab990
# Parent  915ed24547eadd65b6e0f517fa8057db24963844
caching

diff -r 915ed24547ea -r c9977db00e1d CMakeLists.txt
--- a/CMakeLists.txt	Wed Dec 12 13:17:42 2012 +0100
+++ b/CMakeLists.txt	Wed Dec 12 15:32:15 2012 +0100
@@ -125,7 +125,6 @@
   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
diff -r 915ed24547ea -r c9977db00e1d Core/MultiThreading/CacheIndex.cpp
--- a/Core/MultiThreading/CacheIndex.cpp	Wed Dec 12 13:17:42 2012 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,140 +0,0 @@
-/**
- * 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*>;
-}
diff -r 915ed24547ea -r c9977db00e1d Core/MultiThreading/CacheIndex.h
--- a/Core/MultiThreading/CacheIndex.h	Wed Dec 12 13:17:42 2012 +0100
+++ b/Core/MultiThreading/CacheIndex.h	Wed Dec 12 15:32:15 2012 +0100
@@ -35,6 +35,9 @@
 #include <list>
 #include <map>
 #include <boost/noncopyable.hpp>
+#include <cassert>
+
+#include "../OrthancException.h"
 
 namespace Orthanc
 {
@@ -114,6 +117,30 @@
       return index_.find(id) != index_.end();
     }
 
+    bool Contains(T id, Payload& payload) const
+    {
+      typename Index::const_iterator it = index_.find(id);
+      if (it == index_.end())
+      {
+        return false;
+      }
+      else
+      {
+        payload = it->second->second;
+        return true;
+      }
+    }
+
+    /**
+     * Return the number of elements in the cache.
+     * \return The number of elements.
+     **/
+    size_t GetSize() const
+    {
+      assert(index_.size() == queue_.size());
+      return queue_.size();
+    }
+
     /**
      * Check whether the cache index is empty.
      * \return \c true iff the cache is empty.
@@ -123,4 +150,104 @@
       return index_.empty();
     }
   };
+
+
+
+
+  /******************************************************************
+   ** Implementation of the template
+   ******************************************************************/
+
+  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;
+  }
 }
diff -r 915ed24547ea -r c9977db00e1d UnitTests/MemoryCache.cpp
--- a/UnitTests/MemoryCache.cpp	Wed Dec 12 13:17:42 2012 +0100
+++ b/UnitTests/MemoryCache.cpp	Wed Dec 12 15:32:15 2012 +0100
@@ -1,6 +1,9 @@
 #include "gtest/gtest.h"
 
+#include <glog/logging.h>
 #include <memory>
+#include <boost/thread.hpp>
+#include <boost/lexical_cast.hpp>
 #include "../Core/IDynamicObject.h"
 #include "../Core/MultiThreading/CacheIndex.h"
 
@@ -51,6 +54,10 @@
   ASSERT_FALSE(r.Contains("b"));
 
   int p;
+  ASSERT_TRUE(r.Contains("a", p)); ASSERT_EQ(420, p);
+  ASSERT_TRUE(r.Contains("c", p)); ASSERT_EQ(422, p);
+  ASSERT_TRUE(r.Contains("d", p)); ASSERT_EQ(423, 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);
@@ -61,21 +68,174 @@
 
 namespace Orthanc
 {
+
+  class ICacheProvider
+  {
+  public:
+    virtual ~ICacheProvider()
+    {
+    }
+
+    virtual IDynamicObject* Provide(const std::string& id) = 0;
+  };
+
   class MemoryCache
   {
   private:
-    struct CacheElement
+    struct Page
     {
       std::string id_;
-      std::auto_ptr<IDynamicObject> object_;
+      std::auto_ptr<IDynamicObject> content_;
+    };
+
+    ICacheProvider& provider_;
+    size_t cacheSize_;
+    CacheIndex<std::string, Page*>  index_;
+
+    Page& Load(const std::string& id)
+    {
+      // Reuse the cache entry if it already exists
+      Page* p = NULL;
+      if (index_.Contains(id, p))
+      {
+        assert(p != NULL);
+        index_.TagAsMostRecent(id);
+        return *p;
+      }
+
+      // The id is not in the cache yet. Make some room if the cache
+      // is full.
+      if (index_.GetSize() == cacheSize_)
+      {
+        index_.RemoveOldest(p);
+        delete p;
+      }
+
+      // Create a new cache page
+      std::auto_ptr<Page> result(new Page);
+      result->id_ = id;
+      result->content_.reset(provider_.Provide(id));
+
+      // Add the newly create page to the cache
+      p = result.release();
+      index_.Add(id, p);
+      return *p;
+    }
+
+  public:
+    class Accessor
+    {
+      friend class MemoryCache;
+
+    private:
+      Page& element_;
+
+      Accessor(Page& element) : 
+        element_(element)
+      {
+      }
+
+    public:
+      const std::string GetId() const
+      {
+        return element_.id_;
+      }
+
+      IDynamicObject& GetContent()
+      {
+        return *element_.content_;
+      }
+
+      const IDynamicObject& GetContent() const
+      {
+        return *element_.content_;
+      }
     };
 
-    //typedef std::map<CacheElement
+    MemoryCache(ICacheProvider& provider,
+                size_t cacheSize) : 
+      provider_(provider),
+      cacheSize_(cacheSize)
+    {
+    }
+
+    ~MemoryCache()
+    {
+      while (!index_.IsEmpty())
+      {
+        Page* element = NULL;
+        index_.RemoveOldest(element);
+        assert(element != NULL);
+        delete element;
+      }
+    }
 
-    size_t places_;
-    CacheIndex<const char*>  index_;
+    Accessor* Access(const std::string& id)
+    {
+      Page& element = Load(id);
+      return new Accessor(element);
+    }
+  };
+}
+
+
+
+namespace
+{
+  class Integer : public Orthanc::IDynamicObject
+  {
+  private:
+    std::string& log_;
+    int value_;
 
   public:
-    
+    Integer(std::string& log, int v) : log_(log), value_(v)
+    {
+    }
+
+    virtual ~Integer()
+    {
+      LOG(INFO) << "Removing cache entry for " << value_;
+      log_ += boost::lexical_cast<std::string>(value_) + " ";
+    }
+
+    int GetValue() const 
+    {
+      return value_;
+    }
+  };
+
+  class IntegerProvider : public Orthanc::ICacheProvider
+  {
+  public:
+    std::string log_;
+
+    Orthanc::IDynamicObject* Provide(const std::string& s)
+    {
+      LOG(INFO) << "Providing " << s;
+      return new Integer(log_, boost::lexical_cast<int>(s));
+    }
   };
 }
+
+
+TEST(MemoryCache, Basic)
+{
+  IntegerProvider provider;
+
+  {
+    Orthanc::MemoryCache cache(provider, 3);
+    std::auto_ptr<Orthanc::MemoryCache::Accessor> a;
+    a.reset(cache.Access("42"));  // 42 -> exit
+    a.reset(cache.Access("43"));  // 43, 42 -> exit
+    a.reset(cache.Access("45"));  // 45, 43, 42 -> exit
+    a.reset(cache.Access("42"));  // 42, 45, 43 -> exit
+    a.reset(cache.Access("43"));  // 43, 42, 45 -> exit
+    a.reset(cache.Access("47"));  // 45 is removed; 47, 43, 42 -> exit 
+    a.reset(cache.Access("44"));  // 42 is removed; 44, 47, 43 -> exit
+    a.reset(cache.Access("42"));  // 43 is removed; 42, 44, 47 -> exit
+    // Closing the cache: 47, 44, 42 are successively removed
+  }
+
+  ASSERT_EQ("45 42 43 47 44 42 ", provider.log_);
+}