|
282
|
1 /**
|
|
|
2 * Orthanc - A Lightweight, RESTful DICOM Store
|
|
|
3 * Copyright (C) 2012 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>
|
|
283
|
38 #include <cassert>
|
|
|
39
|
|
|
40 #include "../OrthancException.h"
|
|
282
|
41
|
|
|
42 namespace Orthanc
|
|
|
43 {
|
|
|
44 class NullType
|
|
|
45 {
|
|
|
46 };
|
|
|
47
|
|
|
48 /**
|
|
|
49 * This class implements the index of a cache with least recently
|
|
|
50 * used (LRU) recycling policy. All the items of the cache index
|
|
|
51 * can be associated with a payload.
|
|
|
52 * Reference: http://stackoverflow.com/a/2504317
|
|
|
53 **/
|
|
|
54 template <typename T, typename Payload = NullType>
|
|
|
55 class CacheIndex : public boost::noncopyable
|
|
|
56 {
|
|
|
57 private:
|
|
|
58 typedef std::list< std::pair<T, Payload> > Queue;
|
|
|
59 typedef std::map<T, typename Queue::iterator> Index;
|
|
|
60
|
|
|
61 Index index_;
|
|
|
62 Queue queue_;
|
|
|
63
|
|
|
64 /**
|
|
|
65 * Internal method for debug builds to check whether the internal
|
|
|
66 * data structures are not corrupted.
|
|
|
67 **/
|
|
|
68 void CheckInvariants() const;
|
|
|
69
|
|
|
70 public:
|
|
|
71 /**
|
|
|
72 * Add a new element to the cache index, and make it the most
|
|
|
73 * recent element.
|
|
|
74 * \param id The ID of the element.
|
|
|
75 * \param payload The payload of the element.
|
|
|
76 **/
|
|
|
77 void Add(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 TagAsMostRecent(T id);
|
|
|
85
|
|
|
86 /**
|
|
|
87 * Remove an element from the cache index.
|
|
|
88 * \param id The item to remove.
|
|
|
89 **/
|
|
|
90 Payload Invalidate(T id);
|
|
|
91
|
|
|
92 /**
|
|
|
93 * Get the oldest element in the cache and remove it.
|
|
|
94 * \return The oldest item.
|
|
|
95 **/
|
|
|
96 T RemoveOldest()
|
|
|
97 {
|
|
|
98 Payload p;
|
|
|
99 return RemoveOldest(p);
|
|
|
100 }
|
|
|
101
|
|
|
102 /**
|
|
|
103 * Get the oldest element in the cache, remove it and return the
|
|
|
104 * associated payload.
|
|
|
105 * \param payload Where to store the associated payload.
|
|
|
106 * \return The oldest item.
|
|
|
107 **/
|
|
|
108 T RemoveOldest(Payload& payload);
|
|
|
109
|
|
|
110 /**
|
|
|
111 * Check whether an element is contained in the cache.
|
|
|
112 * \param id The item.
|
|
|
113 * \return \c true iff the item is indexed by the cache.
|
|
|
114 **/
|
|
|
115 bool Contains(T id) const
|
|
|
116 {
|
|
|
117 return index_.find(id) != index_.end();
|
|
|
118 }
|
|
|
119
|
|
283
|
120 bool Contains(T id, Payload& payload) const
|
|
|
121 {
|
|
|
122 typename Index::const_iterator it = index_.find(id);
|
|
|
123 if (it == index_.end())
|
|
|
124 {
|
|
|
125 return false;
|
|
|
126 }
|
|
|
127 else
|
|
|
128 {
|
|
|
129 payload = it->second->second;
|
|
|
130 return true;
|
|
|
131 }
|
|
|
132 }
|
|
|
133
|
|
|
134 /**
|
|
|
135 * Return the number of elements in the cache.
|
|
|
136 * \return The number of elements.
|
|
|
137 **/
|
|
|
138 size_t GetSize() const
|
|
|
139 {
|
|
|
140 assert(index_.size() == queue_.size());
|
|
|
141 return queue_.size();
|
|
|
142 }
|
|
|
143
|
|
282
|
144 /**
|
|
|
145 * Check whether the cache index is empty.
|
|
|
146 * \return \c true iff the cache is empty.
|
|
|
147 **/
|
|
|
148 bool IsEmpty() const
|
|
|
149 {
|
|
|
150 return index_.empty();
|
|
|
151 }
|
|
|
152 };
|
|
283
|
153
|
|
|
154
|
|
|
155
|
|
|
156
|
|
|
157 /******************************************************************
|
|
|
158 ** Implementation of the template
|
|
|
159 ******************************************************************/
|
|
|
160
|
|
|
161 template <typename T, typename Payload>
|
|
|
162 void CacheIndex<T, Payload>::CheckInvariants() const
|
|
|
163 {
|
|
|
164 #ifndef NDEBUG
|
|
|
165 assert(index_.size() == queue_.size());
|
|
|
166
|
|
|
167 for (typename Index::const_iterator
|
|
|
168 it = index_.begin(); it != index_.end(); it++)
|
|
|
169 {
|
|
|
170 assert(it->second != queue_.end());
|
|
|
171 assert(it->second->first == it->first);
|
|
|
172 }
|
|
|
173 #endif
|
|
|
174 }
|
|
|
175
|
|
|
176
|
|
|
177 template <typename T, typename Payload>
|
|
|
178 void CacheIndex<T, Payload>::Add(T id, Payload payload)
|
|
|
179 {
|
|
|
180 if (Contains(id))
|
|
|
181 {
|
|
|
182 throw OrthancException(ErrorCode_BadSequenceOfCalls);
|
|
|
183 }
|
|
|
184
|
|
|
185 queue_.push_front(std::make_pair(id, payload));
|
|
|
186 index_[id] = queue_.begin();
|
|
|
187
|
|
|
188 CheckInvariants();
|
|
|
189 }
|
|
|
190
|
|
|
191
|
|
|
192 template <typename T, typename Payload>
|
|
|
193 void CacheIndex<T, Payload>::TagAsMostRecent(T id)
|
|
|
194 {
|
|
|
195 if (!Contains(id))
|
|
|
196 {
|
|
|
197 throw OrthancException(ErrorCode_InexistentItem);
|
|
|
198 }
|
|
|
199
|
|
|
200 typename Index::iterator it = index_.find(id);
|
|
|
201 assert(it != index_.end());
|
|
|
202
|
|
|
203 std::pair<T, Payload> item = *(it->second);
|
|
|
204
|
|
|
205 queue_.erase(it->second);
|
|
|
206 queue_.push_front(item);
|
|
|
207 index_[id] = queue_.begin();
|
|
|
208
|
|
|
209 CheckInvariants();
|
|
|
210 }
|
|
|
211
|
|
|
212
|
|
|
213 template <typename T, typename Payload>
|
|
|
214 Payload CacheIndex<T, Payload>::Invalidate(T id)
|
|
|
215 {
|
|
|
216 if (!Contains(id))
|
|
|
217 {
|
|
|
218 throw OrthancException(ErrorCode_InexistentItem);
|
|
|
219 }
|
|
|
220
|
|
|
221 typename Index::iterator it = index_.find(id);
|
|
|
222 assert(it != index_.end());
|
|
|
223
|
|
|
224 Payload payload = it->second->second;
|
|
|
225 queue_.erase(it->second);
|
|
|
226 index_.erase(it);
|
|
|
227
|
|
|
228 CheckInvariants();
|
|
|
229 return payload;
|
|
|
230 }
|
|
|
231
|
|
|
232
|
|
|
233 template <typename T, typename Payload>
|
|
|
234 T CacheIndex<T, Payload>::RemoveOldest(Payload& payload)
|
|
|
235 {
|
|
|
236 if (IsEmpty())
|
|
|
237 {
|
|
|
238 throw OrthancException(ErrorCode_BadSequenceOfCalls);
|
|
|
239 }
|
|
|
240
|
|
|
241 std::pair<T, Payload> item = queue_.back();
|
|
|
242 T oldest = item.first;
|
|
|
243 payload = item.second;
|
|
|
244
|
|
|
245 queue_.pop_back();
|
|
|
246 assert(index_.find(oldest) != index_.end());
|
|
|
247 index_.erase(oldest);
|
|
|
248
|
|
|
249 CheckInvariants();
|
|
|
250
|
|
|
251 return oldest;
|
|
|
252 }
|
|
282
|
253 }
|
