Mercurial > hg > orthanc-stone

comparison Resources/Orthanc/Core/Cache/LeastRecentlyUsedIndex.h @ 200:03afbee0cc7b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
integration of Orthanc core into Stone
author Sebastien Jodogne <s.jodogne@gmail.com>
date Fri, 23 Mar 2018 11:04:03 +0100
parents
children
comparison
equal deleted inserted replaced
199:dabe9982fca3 200:03afbee0cc7b
1 /**
2 * Orthanc - A Lightweight, RESTful DICOM Store
3 * Copyright (C) 2012-2016 Sebastien Jodogne, Medical Physics
4 * Department, University Hospital of Liege, Belgium
5 * Copyright (C) 2017-2018 Osimis S.A., Belgium
6 *
7 * This program is free software: you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License as
9 * published by the Free Software Foundation, either version 3 of the
10 * License, or (at your option) any later version.
11 *
12 * In addition, as a special exception, the copyright holders of this
13 * program give permission to link the code of its release with the
14 * OpenSSL project's "OpenSSL" library (or with modified versions of it
15 * that use the same license as the "OpenSSL" library), and distribute
16 * the linked executables. You must obey the GNU General Public License
17 * in all respects for all of the code used other than "OpenSSL". If you
18 * modify file(s) with this exception, you may extend this exception to
19 * your version of the file(s), but you are not obligated to do so. If
20 * you do not wish to do so, delete this exception statement from your
21 * version. If you delete this exception statement from all source files
22 * in the program, then also delete it here.
23 *
24 * This program is distributed in the hope that it will be useful, but
25 * WITHOUT ANY WARRANTY; without even the implied warranty of
26 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
27 * General Public License for more details.
28 *
29 * You should have received a copy of the GNU General Public License
30 * along with this program. If not, see <http://www.gnu.org/licenses/>.
31 **/
32
33
34 #pragma once
35
36 #include <list>
37 #include <map>
38 #include <boost/noncopyable.hpp>
39 #include <cassert>
40
41 #include "../OrthancException.h"
42 #include "../Toolbox.h"
43
44 namespace Orthanc
45 {
46 /**
47 * This class implements the index of a cache with least recently
48 * used (LRU) recycling policy. All the items of the cache index
49 * can be associated with a payload.
50 * Reference: http://stackoverflow.com/a/2504317
51 **/
52 template <typename T, typename Payload = NullType>
53 class LeastRecentlyUsedIndex : public boost::noncopyable
54 {
55 private:
56 typedef std::list< std::pair<T, Payload> > Queue;
57 typedef std::map<T, typename Queue::iterator> Index;
58
59 Index index_;
60 Queue queue_;
61
62 /**
63 * Internal method for debug builds to check whether the internal
64 * data structures are not corrupted.
65 **/
66 void CheckInvariants() const;
67
68 public:
69 /**
70 * Add a new element to the cache index, and make it the most
71 * recent element.
72 * \param id The ID of the element.
73 * \param payload The payload of the element.
74 **/
75 void Add(T id, Payload payload = Payload());
76
77 void AddOrMakeMostRecent(T id, Payload payload = Payload());
78
79 /**
80 * When accessing an element of the cache, this method tags the
81 * element as the most recently used.
82 * \param id The most recently accessed item.
83 **/
84 void MakeMostRecent(T id);
85
86 void MakeMostRecent(T id, Payload updatedPayload);
87
88 /**
89 * Remove an element from the cache index.
90 * \param id The item to remove.
91 **/
92 Payload Invalidate(T id);
93
94 /**
95 * Get the oldest element in the cache and remove it.
96 * \return The oldest item.
97 **/
98 T RemoveOldest();
99
100 /**
101 * Get the oldest element in the cache, remove it and return the
102 * associated payload.
103 * \param payload Where to store the associated payload.
104 * \return The oldest item.
105 **/
106 T RemoveOldest(Payload& payload);
107
108 /**
109 * Check whether an element is contained in the cache.
110 * \param id The item.
111 * \return \c true iff the item is indexed by the cache.
112 **/
113 bool Contains(T id) const
114 {
115 return index_.find(id) != index_.end();
116 }
117
118 bool Contains(T id, Payload& payload) const
119 {
120 typename Index::const_iterator it = index_.find(id);
121 if (it == index_.end())
122 {
123 return false;
124 }
125 else
126 {
127 payload = it->second->second;
128 return true;
129 }
130 }
131
132 /**
133 * Return the number of elements in the cache.
134 * \return The number of elements.
135 **/
136 size_t GetSize() const
137 {
138 assert(index_.size() == queue_.size());
139 return queue_.size();
140 }
141
142 /**
143 * Check whether the cache index is empty.
144 * \return \c true iff the cache is empty.
145 **/
146 bool IsEmpty() const
147 {
148 return index_.empty();
149 }
150
151 const T& GetOldest() const;
152
153 const Payload& GetOldestPayload() const;
154 };
155
156
157
158
159 /******************************************************************
160 ** Implementation of the template
161 ******************************************************************/
162
163 template <typename T, typename Payload>
164 void LeastRecentlyUsedIndex<T, Payload>::CheckInvariants() const
165 {
166 #ifndef NDEBUG
167 assert(index_.size() == queue_.size());
168
169 for (typename Index::const_iterator
170 it = index_.begin(); it != index_.end(); it++)
171 {
172 assert(it->second != queue_.end());
173 assert(it->second->first == it->first);
174 }
175 #endif
176 }
177
178
179 template <typename T, typename Payload>
180 void LeastRecentlyUsedIndex<T, Payload>::Add(T id, Payload payload)
181 {
182 if (Contains(id))
183 {
184 throw OrthancException(ErrorCode_BadSequenceOfCalls);
185 }
186
187 queue_.push_front(std::make_pair(id, payload));
188 index_[id] = queue_.begin();
189
190 CheckInvariants();
191 }
192
193
194 template <typename T, typename Payload>
195 void LeastRecentlyUsedIndex<T, Payload>::MakeMostRecent(T id)
196 {
197 if (!Contains(id))
198 {
199 throw OrthancException(ErrorCode_InexistentItem);
200 }
201
202 typename Index::iterator it = index_.find(id);
203 assert(it != index_.end());
204
205 std::pair<T, Payload> item = *(it->second);
206
207 queue_.erase(it->second);
208 queue_.push_front(item);
209 index_[id] = queue_.begin();
210
211 CheckInvariants();
212 }
213
214
215 template <typename T, typename Payload>
216 void LeastRecentlyUsedIndex<T, Payload>::AddOrMakeMostRecent(T id, Payload payload)
217 {
218 typename Index::iterator it = index_.find(id);
219
220 if (it != index_.end())
221 {
222 // Already existing. Make it most recent.
223 std::pair<T, Payload> item = *(it->second);
224 item.second = payload;
225 queue_.erase(it->second);
226 queue_.push_front(item);
227 }
228 else
229 {
230 // New item
231 queue_.push_front(std::make_pair(id, payload));
232 }
233
234 index_[id] = queue_.begin();
235
236 CheckInvariants();
237 }
238
239
240 template <typename T, typename Payload>
241 void LeastRecentlyUsedIndex<T, Payload>::MakeMostRecent(T id, Payload updatedPayload)
242 {
243 if (!Contains(id))
244 {
245 throw OrthancException(ErrorCode_InexistentItem);
246 }
247
248 typename Index::iterator it = index_.find(id);
249 assert(it != index_.end());
250
251 std::pair<T, Payload> item = *(it->second);
252 item.second = updatedPayload;
253
254 queue_.erase(it->second);
255 queue_.push_front(item);
256 index_[id] = queue_.begin();
257
258 CheckInvariants();
259 }
260
261
262 template <typename T, typename Payload>
263 Payload LeastRecentlyUsedIndex<T, Payload>::Invalidate(T id)
264 {
265 if (!Contains(id))
266 {
267 throw OrthancException(ErrorCode_InexistentItem);
268 }
269
270 typename Index::iterator it = index_.find(id);
271 assert(it != index_.end());
272
273 Payload payload = it->second->second;
274 queue_.erase(it->second);
275 index_.erase(it);
276
277 CheckInvariants();
278 return payload;
279 }
280
281
282 template <typename T, typename Payload>
283 T LeastRecentlyUsedIndex<T, Payload>::RemoveOldest(Payload& payload)
284 {
285 if (IsEmpty())
286 {
287 throw OrthancException(ErrorCode_BadSequenceOfCalls);
288 }
289
290 std::pair<T, Payload> item = queue_.back();
291 T oldest = item.first;
292 payload = item.second;
293
294 queue_.pop_back();
295 assert(index_.find(oldest) != index_.end());
296 index_.erase(oldest);
297
298 CheckInvariants();
299
300 return oldest;
301 }
302
303
304 template <typename T, typename Payload>
305 T LeastRecentlyUsedIndex<T, Payload>::RemoveOldest()
306 {
307 if (IsEmpty())
308 {
309 throw OrthancException(ErrorCode_BadSequenceOfCalls);
310 }
311
312 std::pair<T, Payload> item = queue_.back();
313 T oldest = item.first;
314
315 queue_.pop_back();
316 assert(index_.find(oldest) != index_.end());
317 index_.erase(oldest);
318
319 CheckInvariants();
320
321 return oldest;
322 }
323
324
325 template <typename T, typename Payload>
326 const T& LeastRecentlyUsedIndex<T, Payload>::GetOldest() const
327 {
328 if (IsEmpty())
329 {
330 throw OrthancException(ErrorCode_BadSequenceOfCalls);
331 }
332
333 return queue_.back().first;
334 }
335
336
337 template <typename T, typename Payload>
338 const Payload& LeastRecentlyUsedIndex<T, Payload>::GetOldestPayload() const
339 {
340 if (IsEmpty())
341 {
342 throw OrthancException(ErrorCode_BadSequenceOfCalls);
343 }
344
345 return queue_.back().second;
346 }
347 }