Mercurial > hg > orthanc-authorization
comparison Resources/Orthanc/Core/Cache/LeastRecentlyUsedIndex.h @ 1:d5d3cb00556a
initial release
author | Sebastien Jodogne <s.jodogne@gmail.com> |
---|---|
date | Wed, 22 Mar 2017 16:13:52 +0100 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
0:decac5df19c4 | 1:d5d3cb00556a |
---|---|
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 Osimis, 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 } |