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