Mercurial > hg > orthanc

comparison OrthancFramework/Sources/Cache/LeastRecentlyUsedIndex.h @ 4044:d25f4c0fa160 framework

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
splitting code into OrthancFramework and OrthancServer
author Sebastien Jodogne <s.jodogne@gmail.com>
date Wed, 10 Jun 2020 20:30:34 +0200
parents Core/Cache/LeastRecentlyUsedIndex.h@94f4a18a79cc
children bf7b9edf6b81
comparison
equal deleted inserted replaced
4043:6c6239aec462 4044:d25f4c0fa160
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-2020 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 <vector>
39 #include <boost/noncopyable.hpp>
40 #include <cassert>
41
42 #include "../OrthancException.h"
43 #include "../Toolbox.h"
44
45 namespace Orthanc
46 {
47 /**
48 * This class implements the index of a cache with least recently
49 * used (LRU) recycling policy. All the items of the cache index
50 * can be associated with a payload.
51 * Reference: http://stackoverflow.com/a/2504317
52 **/
53 template <typename T, typename Payload = NullType>
54 class LeastRecentlyUsedIndex : public boost::noncopyable
55 {
56 private:
57 typedef std::list< std::pair<T, Payload> > Queue;
58 typedef std::map<T, typename Queue::iterator> Index;
59
60 Index index_;
61 Queue queue_;
62
63 /**
64 * Internal method for debug builds to check whether the internal
65 * data structures are not corrupted.
66 **/
67 void CheckInvariants() const;
68
69 public:
70 /**
71 * Add a new element to the cache index, and make it the most
72 * recent element.
73 * \param id The ID of the element.
74 * \param payload The payload of the element.
75 **/
76 void Add(T id, Payload payload = Payload());
77
78 void AddOrMakeMostRecent(T id, Payload payload = Payload());
79
80 /**
81 * When accessing an element of the cache, this method tags the
82 * element as the most recently used.
83 * \param id The most recently accessed item.
84 **/
85 void MakeMostRecent(T id);
86
87 void MakeMostRecent(T id, Payload updatedPayload);
88
89 /**
90 * Remove an element from the cache index.
91 * \param id The item to remove.
92 **/
93 Payload Invalidate(T id);
94
95 /**
96 * Get the oldest element in the cache and remove it.
97 * \return The oldest item.
98 **/
99 T RemoveOldest();
100
101 /**
102 * Get the oldest element in the cache, remove it and return the
103 * associated payload.
104 * \param payload Where to store the associated payload.
105 * \return The oldest item.
106 **/
107 T RemoveOldest(Payload& payload);
108
109 /**
110 * Check whether an element is contained in the cache.
111 * \param id The item.
112 * \return \c true iff the item is indexed by the cache.
113 **/
114 bool Contains(T id) const
115 {
116 return index_.find(id) != index_.end();
117 }
118
119 bool Contains(T id, Payload& payload) const
120 {
121 typename Index::const_iterator it = index_.find(id);
122 if (it == index_.end())
123 {
124 return false;
125 }
126 else
127 {
128 payload = it->second->second;
129 return true;
130 }
131 }
132
133 /**
134 * Return the number of elements in the cache.
135 * \return The number of elements.
136 **/
137 size_t GetSize() const
138 {
139 assert(index_.size() == queue_.size());
140 return queue_.size();
141 }
142
143 /**
144 * Check whether the cache index is empty.
145 * \return \c true iff the cache is empty.
146 **/
147 bool IsEmpty() const
148 {
149 return index_.empty();
150 }
151
152 const T& GetOldest() const;
153
154 const Payload& GetOldestPayload() const;
155
156 void GetAllKeys(std::vector<T>& keys) const
157 {
158 keys.clear();
159 keys.reserve(GetSize());
160 for (typename Index::const_iterator it = index_.begin(); it != index_.end(); it++)
161 {
162 keys.push_back(it->first);
163 }
164 }
165
166 };
167
168
169
170
171 /******************************************************************
172 ** Implementation of the template
173 ******************************************************************/
174
175 template <typename T, typename Payload>
176 void LeastRecentlyUsedIndex<T, Payload>::CheckInvariants() const
177 {
178 #ifndef NDEBUG
179 assert(index_.size() == queue_.size());
180
181 for (typename Index::const_iterator
182 it = index_.begin(); it != index_.end(); it++)
183 {
184 assert(it->second != queue_.end());
185 assert(it->second->first == it->first);
186 }
187 #endif
188 }
189
190
191 template <typename T, typename Payload>
192 void LeastRecentlyUsedIndex<T, Payload>::Add(T id, Payload payload)
193 {
194 if (Contains(id))
195 {
196 throw OrthancException(ErrorCode_BadSequenceOfCalls);
197 }
198
199 queue_.push_front(std::make_pair(id, payload));
200 index_[id] = queue_.begin();
201
202 CheckInvariants();
203 }
204
205
206 template <typename T, typename Payload>
207 void LeastRecentlyUsedIndex<T, Payload>::MakeMostRecent(T id)
208 {
209 if (!Contains(id))
210 {
211 throw OrthancException(ErrorCode_InexistentItem);
212 }
213
214 typename Index::iterator it = index_.find(id);
215 assert(it != index_.end());
216
217 std::pair<T, Payload> item = *(it->second);
218
219 queue_.erase(it->second);
220 queue_.push_front(item);
221 index_[id] = queue_.begin();
222
223 CheckInvariants();
224 }
225
226
227 template <typename T, typename Payload>
228 void LeastRecentlyUsedIndex<T, Payload>::AddOrMakeMostRecent(T id, Payload payload)
229 {
230 typename Index::iterator it = index_.find(id);
231
232 if (it != index_.end())
233 {
234 // Already existing. Make it most recent.
235 std::pair<T, Payload> item = *(it->second);
236 item.second = payload;
237 queue_.erase(it->second);
238 queue_.push_front(item);
239 }
240 else
241 {
242 // New item
243 queue_.push_front(std::make_pair(id, payload));
244 }
245
246 index_[id] = queue_.begin();
247
248 CheckInvariants();
249 }
250
251
252 template <typename T, typename Payload>
253 void LeastRecentlyUsedIndex<T, Payload>::MakeMostRecent(T id, Payload updatedPayload)
254 {
255 if (!Contains(id))
256 {
257 throw OrthancException(ErrorCode_InexistentItem);
258 }
259
260 typename Index::iterator it = index_.find(id);
261 assert(it != index_.end());
262
263 std::pair<T, Payload> item = *(it->second);
264 item.second = updatedPayload;
265
266 queue_.erase(it->second);
267 queue_.push_front(item);
268 index_[id] = queue_.begin();
269
270 CheckInvariants();
271 }
272
273
274 template <typename T, typename Payload>
275 Payload LeastRecentlyUsedIndex<T, Payload>::Invalidate(T id)
276 {
277 if (!Contains(id))
278 {
279 throw OrthancException(ErrorCode_InexistentItem);
280 }
281
282 typename Index::iterator it = index_.find(id);
283 assert(it != index_.end());
284
285 Payload payload = it->second->second;
286 queue_.erase(it->second);
287 index_.erase(it);
288
289 CheckInvariants();
290 return payload;
291 }
292
293
294 template <typename T, typename Payload>
295 T LeastRecentlyUsedIndex<T, Payload>::RemoveOldest(Payload& payload)
296 {
297 if (IsEmpty())
298 {
299 throw OrthancException(ErrorCode_BadSequenceOfCalls);
300 }
301
302 std::pair<T, Payload> item = queue_.back();
303 T oldest = item.first;
304 payload = item.second;
305
306 queue_.pop_back();
307 assert(index_.find(oldest) != index_.end());
308 index_.erase(oldest);
309
310 CheckInvariants();
311
312 return oldest;
313 }
314
315
316 template <typename T, typename Payload>
317 T LeastRecentlyUsedIndex<T, Payload>::RemoveOldest()
318 {
319 if (IsEmpty())
320 {
321 throw OrthancException(ErrorCode_BadSequenceOfCalls);
322 }
323
324 std::pair<T, Payload> item = queue_.back();
325 T oldest = item.first;
326
327 queue_.pop_back();
328 assert(index_.find(oldest) != index_.end());
329 index_.erase(oldest);
330
331 CheckInvariants();
332
333 return oldest;
334 }
335
336
337 template <typename T, typename Payload>
338 const T& LeastRecentlyUsedIndex<T, Payload>::GetOldest() const
339 {
340 if (IsEmpty())
341 {
342 throw OrthancException(ErrorCode_BadSequenceOfCalls);
343 }
344
345 return queue_.back().first;
346 }
347
348
349 template <typename T, typename Payload>
350 const Payload& LeastRecentlyUsedIndex<T, Payload>::GetOldestPayload() const
351 {
352 if (IsEmpty())
353 {
354 throw OrthancException(ErrorCode_BadSequenceOfCalls);
355 }
356
357 return queue_.back().second;
358 }
359 }