Mercurial > hg > orthanc
changeset 284:06aa7b7b6723
implementation of a single-threaded cache mechanism
author | Sebastien Jodogne <s.jodogne@gmail.com> |
---|---|
date | Wed, 12 Dec 2012 15:40:18 +0100 |
parents | c9977db00e1d |
children | 4031f73fe0e4 |
files | CMakeLists.txt Core/Cache/CacheIndex.h Core/Cache/ICachePageProvider.h Core/Cache/MemoryCache.cpp Core/Cache/MemoryCache.h Core/MultiThreading/CacheIndex.h Core/Toolbox.h UnitTests/MemoryCache.cpp |
diffstat | 8 files changed, 492 insertions(+), 367 deletions(-) [+] |
line wrap: on
line diff
--- a/CMakeLists.txt Wed Dec 12 15:32:15 2012 +0100 +++ b/CMakeLists.txt Wed Dec 12 15:40:18 2012 +0100 @@ -99,6 +99,7 @@ ${AUTOGENERATED_SOURCES} ${THIRD_PARTY_SOURCES} + Core/Cache/MemoryCache.cpp Core/ChunkedBuffer.cpp Core/Compression/BufferCompressor.cpp Core/Compression/ZlibCompressor.cpp
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Core/Cache/CacheIndex.h Wed Dec 12 15:40:18 2012 +0100 @@ -0,0 +1,250 @@ +/** + * 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> +#include <cassert> + +#include "../OrthancException.h" +#include "../Toolbox.h" + +namespace Orthanc +{ + /** + * 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(); + } + + 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. + **/ + bool IsEmpty() const + { + 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; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Core/Cache/ICachePageProvider.h Wed Dec 12 15:40:18 2012 +0100 @@ -0,0 +1,49 @@ +/** + * 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 <string> +#include "../IDynamicObject.h" + +namespace Orthanc +{ + class ICachePageProvider + { + public: + virtual ~ICachePageProvider() + { + } + + virtual IDynamicObject* Provide(const std::string& id) = 0; + }; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Core/Cache/MemoryCache.cpp Wed Dec 12 15:40:18 2012 +0100 @@ -0,0 +1,90 @@ +/** + * 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 "MemoryCache.h" + +namespace Orthanc +{ + MemoryCache::Page& MemoryCache::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; + } + + MemoryCache::MemoryCache(ICachePageProvider& provider, + size_t cacheSize) : + provider_(provider), + cacheSize_(cacheSize) + { + } + + MemoryCache::~MemoryCache() + { + while (!index_.IsEmpty()) + { + Page* element = NULL; + index_.RemoveOldest(element); + assert(element != NULL); + delete element; + } + } + + MemoryCache::Accessor* MemoryCache::Access(const std::string& id) + { + Page& element = Load(id); + return new Accessor(element); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/Core/Cache/MemoryCache.h Wed Dec 12 15:40:18 2012 +0100 @@ -0,0 +1,96 @@ +/** + * 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 <memory> +#include "CacheIndex.h" +#include "ICachePageProvider.h" + +namespace Orthanc +{ + /** + * WARNING: This class is NOT thread-safe. + **/ + class MemoryCache + { + private: + struct Page + { + std::string id_; + std::auto_ptr<IDynamicObject> content_; + }; + + ICachePageProvider& provider_; + size_t cacheSize_; + CacheIndex<std::string, Page*> index_; + + Page& Load(const std::string& id); + + 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_; + } + }; + + MemoryCache(ICachePageProvider& provider, + size_t cacheSize); + + ~MemoryCache(); + + Accessor* Access(const std::string& id); + }; +}
--- a/Core/MultiThreading/CacheIndex.h Wed Dec 12 15:32:15 2012 +0100 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,253 +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/>. - **/ - - -#pragma once - -#include <list> -#include <map> -#include <boost/noncopyable.hpp> -#include <cassert> - -#include "../OrthancException.h" - -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(); - } - - 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. - **/ - bool IsEmpty() const - { - 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; - } -}
--- a/Core/Toolbox.h Wed Dec 12 15:32:15 2012 +0100 +++ b/Core/Toolbox.h Wed Dec 12 15:40:18 2012 +0100 @@ -40,6 +40,10 @@ { typedef std::vector<std::string> UriComponents; + class NullType + { + }; + namespace Toolbox { void ServerBarrier();
--- a/UnitTests/MemoryCache.cpp Wed Dec 12 15:32:15 2012 +0100 +++ b/UnitTests/MemoryCache.cpp Wed Dec 12 15:40:18 2012 +0100 @@ -5,7 +5,7 @@ #include <boost/thread.hpp> #include <boost/lexical_cast.hpp> #include "../Core/IDynamicObject.h" -#include "../Core/MultiThreading/CacheIndex.h" +#include "../Core/Cache/MemoryCache.h" TEST(CacheIndex, Basic) @@ -66,118 +66,6 @@ } -namespace Orthanc -{ - - class ICacheProvider - { - public: - virtual ~ICacheProvider() - { - } - - virtual IDynamicObject* Provide(const std::string& id) = 0; - }; - - class MemoryCache - { - private: - struct Page - { - std::string id_; - 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_; - } - }; - - 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; - } - } - - Accessor* Access(const std::string& id) - { - Page& element = Load(id); - return new Accessor(element); - } - }; -} - namespace @@ -205,7 +93,7 @@ } }; - class IntegerProvider : public Orthanc::ICacheProvider + class IntegerProvider : public Orthanc::ICachePageProvider { public: std::string log_;