Mercurial > hg > orthanc
annotate Core/Cache/CacheIndex.h @ 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 | Core/MultiThreading/CacheIndex.h@c9977db00e1d |
| children | bdd72233b105 |
| rev | line source |
|---|---|
| 282 | 1 /** |
| 2 * Orthanc - A Lightweight, RESTful DICOM Store | |
| 3 * Copyright (C) 2012 Medical Physics Department, CHU of Liege, | |
| 4 * Belgium | |
| 5 * | |
| 6 * This program is free software: you can redistribute it and/or | |
| 7 * modify it under the terms of the GNU General Public License as | |
| 8 * published by the Free Software Foundation, either version 3 of the | |
| 9 * License, or (at your option) any later version. | |
| 10 * | |
| 11 * In addition, as a special exception, the copyright holders of this | |
| 12 * program give permission to link the code of its release with the | |
| 13 * OpenSSL project's "OpenSSL" library (or with modified versions of it | |
| 14 * that use the same license as the "OpenSSL" library), and distribute | |
| 15 * the linked executables. You must obey the GNU General Public License | |
| 16 * in all respects for all of the code used other than "OpenSSL". If you | |
| 17 * modify file(s) with this exception, you may extend this exception to | |
| 18 * your version of the file(s), but you are not obligated to do so. If | |
| 19 * you do not wish to do so, delete this exception statement from your | |
| 20 * version. If you delete this exception statement from all source files | |
| 21 * in the program, then also delete it here. | |
| 22 * | |
| 23 * This program is distributed in the hope that it will be useful, but | |
| 24 * WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 25 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
| 26 * General Public License for more details. | |
| 27 * | |
| 28 * You should have received a copy of the GNU General Public License | |
| 29 * along with this program. If not, see <http://www.gnu.org/licenses/>. | |
| 30 **/ | |
| 31 | |
| 32 | |
| 33 #pragma once | |
| 34 | |
| 35 #include <list> | |
| 36 #include <map> | |
| 37 #include <boost/noncopyable.hpp> | |
| 283 | 38 #include <cassert> |
| 39 | |
| 40 #include "../OrthancException.h" | |
|
284
06aa7b7b6723
implementation of a single-threaded cache mechanism
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
283
diff
changeset
|
41 #include "../Toolbox.h" |
| 282 | 42 |
| 43 namespace Orthanc | |
| 44 { | |
| 45 /** | |
| 46 * This class implements the index of a cache with least recently | |
| 47 * used (LRU) recycling policy. All the items of the cache index | |
| 48 * can be associated with a payload. | |
| 49 * Reference: http://stackoverflow.com/a/2504317 | |
| 50 **/ | |
| 51 template <typename T, typename Payload = NullType> | |
| 52 class CacheIndex : public boost::noncopyable | |
| 53 { | |
| 54 private: | |
| 55 typedef std::list< std::pair<T, Payload> > Queue; | |
| 56 typedef std::map<T, typename Queue::iterator> Index; | |
| 57 | |
| 58 Index index_; | |
| 59 Queue queue_; | |
| 60 | |
| 61 /** | |
| 62 * Internal method for debug builds to check whether the internal | |
| 63 * data structures are not corrupted. | |
| 64 **/ | |
| 65 void CheckInvariants() const; | |
| 66 | |
| 67 public: | |
| 68 /** | |
| 69 * Add a new element to the cache index, and make it the most | |
| 70 * recent element. | |
| 71 * \param id The ID of the element. | |
| 72 * \param payload The payload of the element. | |
| 73 **/ | |
| 74 void Add(T id, Payload payload = Payload()); | |
| 75 | |
| 76 /** | |
| 77 * When accessing an element of the cache, this method tags the | |
| 78 * element as the most recently used. | |
| 79 * \param id The most recently accessed item. | |
| 80 **/ | |
| 81 void TagAsMostRecent(T id); | |
| 82 | |
| 83 /** | |
| 84 * Remove an element from the cache index. | |
| 85 * \param id The item to remove. | |
| 86 **/ | |
| 87 Payload Invalidate(T id); | |
| 88 | |
| 89 /** | |
| 90 * Get the oldest element in the cache and remove it. | |
| 91 * \return The oldest item. | |
| 92 **/ | |
| 93 T RemoveOldest() | |
| 94 { | |
| 95 Payload p; | |
| 96 return RemoveOldest(p); | |
| 97 } | |
| 98 | |
| 99 /** | |
| 100 * Get the oldest element in the cache, remove it and return the | |
| 101 * associated payload. | |
| 102 * \param payload Where to store the associated payload. | |
| 103 * \return The oldest item. | |
| 104 **/ | |
| 105 T RemoveOldest(Payload& payload); | |
| 106 | |
| 107 /** | |
| 108 * Check whether an element is contained in the cache. | |
| 109 * \param id The item. | |
| 110 * \return \c true iff the item is indexed by the cache. | |
| 111 **/ | |
| 112 bool Contains(T id) const | |
| 113 { | |
| 114 return index_.find(id) != index_.end(); | |
| 115 } | |
| 116 | |
| 283 | 117 bool Contains(T id, Payload& payload) const |
| 118 { | |
| 119 typename Index::const_iterator it = index_.find(id); | |
| 120 if (it == index_.end()) | |
| 121 { | |
| 122 return false; | |
| 123 } | |
| 124 else | |
| 125 { | |
| 126 payload = it->second->second; | |
| 127 return true; | |
| 128 } | |
| 129 } | |
| 130 | |
| 131 /** | |
| 132 * Return the number of elements in the cache. | |
| 133 * \return The number of elements. | |
| 134 **/ | |
| 135 size_t GetSize() const | |
| 136 { | |
| 137 assert(index_.size() == queue_.size()); | |
| 138 return queue_.size(); | |
| 139 } | |
| 140 | |
| 282 | 141 /** |
| 142 * Check whether the cache index is empty. | |
| 143 * \return \c true iff the cache is empty. | |
| 144 **/ | |
| 145 bool IsEmpty() const | |
| 146 { | |
| 147 return index_.empty(); | |
| 148 } | |
| 149 }; | |
| 283 | 150 |
| 151 | |
| 152 | |
| 153 | |
| 154 /****************************************************************** | |
| 155 ** Implementation of the template | |
| 156 ******************************************************************/ | |
| 157 | |
| 158 template <typename T, typename Payload> | |
| 159 void CacheIndex<T, Payload>::CheckInvariants() const | |
| 160 { | |
| 161 #ifndef NDEBUG | |
| 162 assert(index_.size() == queue_.size()); | |
| 163 | |
| 164 for (typename Index::const_iterator | |
| 165 it = index_.begin(); it != index_.end(); it++) | |
| 166 { | |
| 167 assert(it->second != queue_.end()); | |
| 168 assert(it->second->first == it->first); | |
| 169 } | |
| 170 #endif | |
| 171 } | |
| 172 | |
| 173 | |
| 174 template <typename T, typename Payload> | |
| 175 void CacheIndex<T, Payload>::Add(T id, Payload payload) | |
| 176 { | |
| 177 if (Contains(id)) | |
| 178 { | |
| 179 throw OrthancException(ErrorCode_BadSequenceOfCalls); | |
| 180 } | |
| 181 | |
| 182 queue_.push_front(std::make_pair(id, payload)); | |
| 183 index_[id] = queue_.begin(); | |
| 184 | |
| 185 CheckInvariants(); | |
| 186 } | |
| 187 | |
| 188 | |
| 189 template <typename T, typename Payload> | |
| 190 void CacheIndex<T, Payload>::TagAsMostRecent(T id) | |
| 191 { | |
| 192 if (!Contains(id)) | |
| 193 { | |
| 194 throw OrthancException(ErrorCode_InexistentItem); | |
| 195 } | |
| 196 | |
| 197 typename Index::iterator it = index_.find(id); | |
| 198 assert(it != index_.end()); | |
| 199 | |
| 200 std::pair<T, Payload> item = *(it->second); | |
| 201 | |
| 202 queue_.erase(it->second); | |
| 203 queue_.push_front(item); | |
| 204 index_[id] = queue_.begin(); | |
| 205 | |
| 206 CheckInvariants(); | |
| 207 } | |
| 208 | |
| 209 | |
| 210 template <typename T, typename Payload> | |
| 211 Payload CacheIndex<T, Payload>::Invalidate(T id) | |
| 212 { | |
| 213 if (!Contains(id)) | |
| 214 { | |
| 215 throw OrthancException(ErrorCode_InexistentItem); | |
| 216 } | |
| 217 | |
| 218 typename Index::iterator it = index_.find(id); | |
| 219 assert(it != index_.end()); | |
| 220 | |
| 221 Payload payload = it->second->second; | |
| 222 queue_.erase(it->second); | |
| 223 index_.erase(it); | |
| 224 | |
| 225 CheckInvariants(); | |
| 226 return payload; | |
| 227 } | |
| 228 | |
| 229 | |
| 230 template <typename T, typename Payload> | |
| 231 T CacheIndex<T, Payload>::RemoveOldest(Payload& payload) | |
| 232 { | |
| 233 if (IsEmpty()) | |
| 234 { | |
| 235 throw OrthancException(ErrorCode_BadSequenceOfCalls); | |
| 236 } | |
| 237 | |
| 238 std::pair<T, Payload> item = queue_.back(); | |
| 239 T oldest = item.first; | |
| 240 payload = item.second; | |
| 241 | |
| 242 queue_.pop_back(); | |
| 243 assert(index_.find(oldest) != index_.end()); | |
| 244 index_.erase(oldest); | |
| 245 | |
| 246 CheckInvariants(); | |
| 247 | |
| 248 return oldest; | |
| 249 } | |
| 282 | 250 } |