Mercurial > hg > orthanc

comparison Core/Cache/LeastRecentlyUsedIndex.h @ 505:f59e4518fd57

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
rename CacheIndex as LeastRecentlyUsedIndex
author Sebastien Jodogne <s.jodogne@gmail.com>
date Fri, 16 Aug 2013 10:17:45 +0200
parents Core/Cache/CacheIndex.h@bdd72233b105
children c4122c3a47c1
comparison
equal deleted inserted replaced
503:273e7ad98ea9 505:f59e4518fd57
1 /**
2 * Orthanc - A Lightweight, RESTful DICOM Store
3 * Copyright (C) 2012-2013 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>
38 #include <cassert>
39
40 #include "../OrthancException.h"
41 #include "../Toolbox.h"
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 LeastRecentlyUsedIndex : 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
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
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 };
150
151
152
153
154 /******************************************************************
155 ** Implementation of the template
156 ******************************************************************/
157
158 template <typename T, typename Payload>
159 void LeastRecentlyUsedIndex<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 LeastRecentlyUsedIndex<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 LeastRecentlyUsedIndex<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 LeastRecentlyUsedIndex<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 LeastRecentlyUsedIndex<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 }
250 }