Branch data Line data Source code
1 : : // Copyright (C) 2010 Internet Systems Consortium, Inc. ("ISC")
2 : : //
3 : : // Permission to use, copy, modify, and/or distribute this software for any
4 : : // purpose with or without fee is hereby granted, provided that the above
5 : : // copyright notice and this permission notice appear in all copies.
6 : : //
7 : : // THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
8 : : // REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
9 : : // AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
10 : : // INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
11 : : // LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
12 : : // OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
13 : : // PERFORMANCE OF THIS SOFTWARE.
14 : :
15 : : #ifndef __LRU_LIST_H
16 : : #define __LRU_LIST_H
17 : :
18 : : #include <list>
19 : : #include <string>
20 : :
21 : : #include <boost/noncopyable.hpp>
22 : : #include <boost/shared_ptr.hpp>
23 : :
24 : : #include <util/locks.h>
25 : :
26 : : namespace isc {
27 : : namespace util {
28 : :
29 : : /// \brief LRU List
30 : : ///
31 : : /// Provides the LRU list for the zone and nameserver objects. The list is
32 : : /// created with a specific size. Entries are added to the back of the list
33 : : /// and removed from the front. It is also possible to pull an element out
34 : : /// of the middle of the list and add it to the end of the list, an action that
35 : : /// should be done when the element is referenced.
36 : : ///
37 : : /// It is not intended that the class be copied, and the derivation from
38 : : /// boost::noncopyable enforces this.
39 : : template <typename T>
40 : : class LruList : boost::noncopyable {
41 : : public:
42 : : typedef typename std::list<boost::shared_ptr<T> > lru_list;
43 : : typedef typename lru_list::iterator iterator;
44 : :
45 : : /// \brief Dropped Operation
46 : : ///
47 : : /// When an object is dropped from the LRU list because it has not been
48 : : /// accessed for some time, it is possible that the action should trigger
49 : : /// some other functions. For this reason, it is possible to register
50 : : /// a list-wide functor object to execute in this casee.
51 : : ///
52 : : /// Note that the function does not execute as the result of a call to
53 : : /// remove() - that is an explicit call and it is assumed that the caller
54 : : /// will handle any additional operations needed.
55 : : class Dropped {
56 : : public:
57 : : /// \brief Constructor
58 : 221 : Dropped(){}
59 : :
60 : : /// \brief Virtual Destructor
61 : 217 : virtual ~Dropped(){}
62 : :
63 : : /// \brief Dropped Object Handler
64 : : ///
65 : : /// Function object called when the object drops off the end of the
66 : : /// LRU list.
67 : : ///
68 : : /// \param drop Object being dropped.
69 : : virtual void operator()(T* drop) const = 0;
70 : : };
71 : :
72 : : /// \brief Constructor
73 : : ///
74 : : /// \param max_size Maximum size of the list before elements are dropped.
75 : : /// \param dropped Pointer to a function object that will get called as
76 : : /// elements are dropped. This object will be stored using a shared_ptr,
77 : : /// so should be allocated with new().
78 : 10 : LruList(uint32_t max_size = 1000, Dropped* dropped = NULL) :
79 : 458 : max_size_(max_size), count_(0), dropped_(dropped)
80 : 10 : {}
81 : :
82 : : /// \brief Virtual Destructor
83 : 295 : virtual ~LruList()
84 : 295 : {}
85 : :
86 : : /// \brief Add Element
87 : : ///
88 : : /// Add a new element to the end of the list.
89 : : ///
90 : : /// \param element Reference to the element to add.
91 : : ///
92 : : /// \return Handle describing the element in the LRU list.
93 : : virtual void add(boost::shared_ptr<T>& element);
94 : :
95 : : /// \brief Remove Element
96 : : ///
97 : : /// Removes an element from the list. If the element is not present (i.e.
98 : : /// its internal list pointer is invalid), this is a no-op.
99 : : ///
100 : : /// \param element Reference to the element to remove.
101 : : virtual void remove(boost::shared_ptr<T>& element);
102 : :
103 : : /// \brief Touch Element
104 : : ///
105 : : /// The name comes from the Unix "touch" command. All this does is to
106 : : /// move the specified entry from the middle of the list to the end of
107 : : /// the list.
108 : : ///
109 : : /// \param element Reference to the element to touch.
110 : : virtual void touch(boost::shared_ptr<T>& element);
111 : :
112 : : /// \brief Drop All the Elements in the List .
113 : : ///
114 : : /// All the elements will be dropped from the list container, and their
115 : : /// drop handler(if there is one) will be called, when done, the size of
116 : : /// of list will be 0.
117 : : virtual void clear();
118 : :
119 : : /// \brief Return Size of the List
120 : : ///
121 : : /// An independent count is kept of the list size, as list.size() may take
122 : : /// some time if the list is big.
123 : : ///
124 : : /// \return Number of elements in the list
125 : 0 : virtual uint32_t size() const {
126 : :
127 : : // Don't bother to lock the mutex. If an update is in progress, we
128 : : // receive either the value just before the update or just after it.
129 : : // Either way, this call could have come just before or just after
130 : : // that operation, so the value would have been just as uncertain.
131 : 0 : return count_;
132 : : }
133 : :
134 : : /// \brief Return Maximum Size
135 : : ///
136 : : /// \return Maximum size of the list
137 : 0 : virtual uint32_t getMaxSize() const {
138 : 0 : return max_size_;
139 : : }
140 : :
141 : : /// \brief Set Maximum Size
142 : : ///
143 : : /// \param max_size New maximum list size
144 : 0 : virtual void setMaxSize(uint32_t max_size) {
145 : 1 : max_size_ = max_size;
146 : 0 : }
147 : :
148 : : private:
149 : : locks::mutex mutex_; ///< List protection
150 : : std::list<boost::shared_ptr<T> > lru_; ///< The LRU list itself
151 : : uint32_t max_size_; ///< Max size of the list
152 : : uint32_t count_; ///< Count of elements
153 : : boost::shared_ptr<Dropped> dropped_; ///< Dropped object
154 : : };
155 : :
156 : : // Add entry to the list
157 : : template <typename T>
158 : 264 : void LruList<T>::add(boost::shared_ptr<T>& element) {
159 : :
160 : : // Protect list against concurrent access
161 : : locks::scoped_lock<locks::mutex> lock(mutex_);
162 : :
163 : : // Add the entry and set its pointer field to point into the list.
164 : : // insert() is used to get the pointer.
165 : 528 : element->setLruIterator(lru_.insert(lru_.end(), element));
166 : :
167 : : // ... and update the count while we have the mutex.
168 : 264 : ++count_;
169 : :
170 : : // If the count takes us above the maximum size of the list, remove elements
171 : : // from the front. The current list size could be more than one above the
172 : : // maximum size of the list if the maximum size was changed after
173 : : // construction.
174 [ + + ][ + + ]: 281 : while (count_ > max_size_) {
175 [ + - ][ + - ]: 17 : if (!lru_.empty()) {
176 : :
177 : : // Run the drop handler (if there is one) on the
178 : :
179 : : // to-be-dropped object.
180 [ + + ][ + - ]: 17 : if (dropped_) {
181 : 10 : (*dropped_)(lru_.begin()->get());
182 : : }
183 : :
184 : : // ... and get rid of it from the list
185 : 17 : lru_.pop_front();
186 : 17 : --count_;
187 : : }
188 : : else {
189 : :
190 : : // TODO: Log this condition (count_ > 0 when list empty) -
191 : : // it should not happen
192 : 0 : count_ = 0;
193 : 0 : break;
194 : : }
195 : : }
196 : 264 : }
197 : :
198 : : // Remove an element from the list
199 : : template <typename T>
200 : 30 : void LruList<T>::remove(boost::shared_ptr<T>& element) {
201 : :
202 : : // An element can only be removed it its internal pointer is valid.
203 : : // If it is, the pointer can be used to access the list because no matter
204 : : // what other elements are added or removed, the pointer remains valid.
205 : : //
206 : : // If the pointer is not valid, this is a no-op.
207 [ + + ][ + - ]: 30 : if (element->iteratorValid()) {
208 : :
209 : : // Is valid, so protect list against concurrent access
210 : : locks::scoped_lock<locks::mutex> lock(mutex_);
211 : :
212 : 29 : lru_.erase(element->getLruIterator()); // Remove element from list
213 : 29 : element->invalidateIterator(); // Invalidate pointer
214 : 29 : --count_; // One less element
215 : : }
216 : 30 : }
217 : :
218 : : // Touch an element - remove it from the list and add to the end
219 : : template <typename T>
220 : 2135 : void LruList<T>::touch(boost::shared_ptr<T>& element) {
221 : :
222 : : // As before, if the pointer is not valid, this is a no-op.
223 [ + + ][ + - ]: 2135 : if (element->iteratorValid()) {
224 : :
225 : : // Protect list against concurrent access
226 : : locks::scoped_lock<locks::mutex> lock(mutex_);
227 : :
228 : : // Move the element to the end of the list.
229 : 2129 : lru_.splice(lru_.end(), lru_, element->getLruIterator());
230 : :
231 : : // Update the iterator in the element to point to it. We can
232 : : // offset from end() as a list has a bidirectional iterator.
233 : 4258 : iterator i = lru_.end();
234 : 2129 : element->setLruIterator(--i);
235 : : }
236 : 2135 : }
237 : :
238 : : // Clear the list- when done, the size of list will be 0.
239 : : template <typename T>
240 : 145 : void LruList<T>::clear() {
241 : : // Protect list against concurrent access
242 : : locks::scoped_lock<locks::mutex> lock(mutex_);
243 : :
244 : : // ... and update the count while we have the mutex.
245 : 145 : count_ = 0;
246 : : typename std::list<boost::shared_ptr<T> >::iterator iter;
247 [ + - ][ # # ]: 145 : if (dropped_) {
248 [ + + ][ # # ]: 304 : for (iter = lru_.begin(); iter != lru_.end(); ++iter) {
249 : : // Call the drop handler.
250 : 159 : (*dropped_)(iter->get());
251 : : }
252 : : }
253 : :
254 : 145 : lru_.clear();
255 : 145 : }
256 : :
257 : : } // namespace util
258 : : } // namespace isc
259 : :
260 : : #endif // __LRU_LIST_H
|
