# HG changeset patch # User Sebastien Jodogne # Date 1355314662 -3600 # Node ID 915ed24547eadd65b6e0f517fa8057db24963844 # Parent 77e526e6fdf89d5a04e4e9d28352eb4123d6fa34 cache lru policy diff -r 77e526e6fdf8 -r 915ed24547ea CMakeLists.txt --- 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) diff -r 77e526e6fdf8 -r 915ed24547ea Core/Enumerations.h --- 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, diff -r 77e526e6fdf8 -r 915ed24547ea Core/MultiThreading/CacheIndex.cpp --- /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 . + **/ + + +#include "CacheIndex.h" + +#include +#include +#include "../OrthancException.h" +#include "../IDynamicObject.h" + +namespace Orthanc +{ + template + void CacheIndex::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 + void CacheIndex::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 + void CacheIndex::TagAsMostRecent(T id) + { + if (!Contains(id)) + { + throw OrthancException(ErrorCode_InexistentItem); + } + + typename Index::iterator it = index_.find(id); + assert(it != index_.end()); + + std::pair item = *(it->second); + + queue_.erase(it->second); + queue_.push_front(item); + index_[id] = queue_.begin(); + + CheckInvariants(); + } + + + template + Payload CacheIndex::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 + T CacheIndex::RemoveOldest(Payload& payload) + { + if (IsEmpty()) + { + throw OrthancException(ErrorCode_BadSequenceOfCalls); + } + + std::pair 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; + template class CacheIndex; + template class CacheIndex; +} diff -r 77e526e6fdf8 -r 915ed24547ea Core/MultiThreading/CacheIndex.h --- /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 . + **/ + + +#pragma once + +#include +#include +#include + +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 + class CacheIndex : public boost::noncopyable + { + private: + typedef std::list< std::pair > Queue; + typedef std::map 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(); + } + }; +} diff -r 77e526e6fdf8 -r 915ed24547ea Core/OrthancException.cpp --- 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 "???"; diff -r 77e526e6fdf8 -r 915ed24547ea UnitTests/MemoryCache.cpp --- /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 +#include "../Core/IDynamicObject.h" +#include "../Core/MultiThreading/CacheIndex.h" + + +TEST(CacheIndex, Basic) +{ + Orthanc::CacheIndex 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 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 object_; + }; + + //typedef std::map index_; + + public: + + }; +}