lru_list.h 8.79 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
// Copyright (C) 2010  Internet Systems Consortium, Inc. ("ISC")
//
// Permission to use, copy, modify, and/or distribute this software for any
// purpose with or without fee is hereby granted, provided that the above
// copyright notice and this permission notice appear in all copies.
//
// THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
// REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
// AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
// OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
// PERFORMANCE OF THIS SOFTWARE.

#ifndef __LRU_LIST_H
#define __LRU_LIST_H

#include <list>
#include <string>

#include <boost/noncopyable.hpp>
#include <boost/shared_ptr.hpp>
23 24

#include "locks.h"
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

namespace isc {
namespace nsas {

/// \brief LRU List
///
/// Provides the LRU list for the zone and nameserver objects.  The list is
/// created with a specific size.  Entries are added to the back of the list
/// and removed from the front.  It is also possible to pull an element out
/// of the middle of the list and add it to the end of the list, an action that
/// should be done when the element is referenced.
///
/// It is not intended that the class be copied, and the derivation from
/// boost::noncopyable enforces this.
template <typename T>
class LruList : boost::noncopyable {
public:
42 43
    typedef typename std::list<boost::shared_ptr<T> > lru_list;
    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 49 50 51 52 53 54
    /// accessed for some time, it is possible that the action should trigger
    /// some other functions.  For this reason, it is possible to register
    /// a list-wide functor object to execute in this casee.
    ///
    /// Note that the function does not execute as the result of a call to
    /// remove() - that is an explicit call and it is assumed that the caller
    /// will handle any additional operations needed.
55
    class Dropped {
56
    public:
57 58 59 60 61
        /// \brief Constructor
        Dropped(){}

        /// \brief Virtual Destructor
        virtual ~Dropped(){}
62

63
        /// \brief Dropped Object Handler
64
        ///
65 66
        /// Function object called when the object drops off the end of the
        /// LRU list.
67
        ///
68
        /// \param drop Object being dropped.
69
        virtual void operator()(T* drop) const = 0;
70 71 72 73 74
    };

    /// \brief Constructor
    ///
    /// \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 77
    /// elements are dropped.  This object will be stored using a shared_ptr,
    /// so should be allocated with new().
78 79
    LruList(uint32_t max_size = 1000, Dropped* dropped = NULL) :
        max_size_(max_size), count_(0), dropped_(dropped)
80 81
    {}

82 83 84 85
    /// \brief Virtual Destructor
    virtual ~LruList()
    {}

86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
    /// \brief Add Element
    ///
    /// Add a new element to the end of the list.
    ///
    /// \param element Reference to the element to add.
    ///
    /// \return Handle describing the element in the LRU list.
    virtual void add(boost::shared_ptr<T>& element);

    /// \brief Remove Element
    ///
    /// Removes an element from the list.  If the element is not present (i.e.
    /// its internal list pointer is invalid), this is a no-op.
    ///
    /// \param element Reference to the element to remove.
    virtual void remove(boost::shared_ptr<T>& element);

    /// \brief Touch Element
    ///
    /// The name comes from the Unix "touch" command.  All this does is to
    /// move the specified entry from the middle of the list to the end of
    /// the list.
    ///
    /// \param element Reference to the element to touch.
    virtual void touch(boost::shared_ptr<T>& element);

112 113 114
    /// \brief Drop All the Elements in the List .
    ///
    /// All the elements will be dropped from the list container, and their
115 116
    /// drop handler(if there is one) will be called, when done, the size of
    /// of list will be 0.
117 118
    virtual void clear();

119 120 121 122 123 124
    /// \brief Return Size of the List
    ///
    /// An independent count is kept of the list size, as list.size() may take
    /// some time if the list is big.
    ///
    /// \return Number of elements in the list
125
    virtual uint32_t size() const {
126 127 128 129 130 131 132 133 134 135 136

        // Don't bother to lock the mutex.  If an update is in progress, we
        // receive either the value just before the update or just after it.
        // Either way, this call could have come just before or just after
        // that operation, so the value would have been just as uncertain.
        return count_;
    }

    /// \brief Return Maximum Size
    ///
    /// \return Maximum size of the list
137
    virtual uint32_t getMaxSize() const {
138 139 140 141 142 143 144 145 146 147 148
        return max_size_;
    }

    /// \brief Set Maximum Size
    ///
    /// \param new_size New maximum list size
    virtual void setMaxSize(uint32_t max_size) {
        max_size_ = max_size;
    }

private:
149
    isc::locks::mutex                   mutex_;     ///< List protection
150 151 152
    std::list<boost::shared_ptr<T> >    lru_;       ///< The LRU list itself
    uint32_t                            max_size_;  ///< Max size of the list
    uint32_t                            count_;     ///< Count of elements
153
    boost::shared_ptr<Dropped>          dropped_;   ///< Dropped object
154 155 156 157 158 159 160
};

// Add entry to the list
template <typename T>
void LruList<T>::add(boost::shared_ptr<T>& element) {

    // Protect list against concurrent access
161
    isc::locks::scoped_lock<isc::locks::mutex> lock(mutex_);
162 163 164

    // Add the entry and set its pointer field to point into the list.
    // insert() is used to get the pointer.
165
    element->setLruIterator(lru_.insert(lru_.end(), element));
166 167 168 169 170 171 172 173 174 175 176

    // ... and update the count while we have the mutex.
    ++count_;

    // If the count takes us above the maximum size of the list, remove elements
    // from the front.  The current list size could be more than one above the
    // maximum size of the list if the maximum size was changed after
    // construction.
    while (count_ > max_size_) {
        if (!lru_.empty()) {

177 178 179 180
            // Run the drop handler (if there is one) on the

            // to-be-dropped object.
            if (dropped_) {
181
                (*dropped_)(lru_.begin()->get());
182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206
            }

            // ... and get rid of it from the list
            lru_.pop_front();
            --count_;
        }
        else {

            // TODO: Log this condition (count_ > 0 when list empty) -
            // it should not happen
            count_ = 0;
            break;
        }
    }
}

// Remove an element from the list
template <typename T>
void LruList<T>::remove(boost::shared_ptr<T>& element) {

    // An element can only be removed it its internal pointer is valid.
    // If it is, the pointer can be used to access the list because no matter
    // what other elements are added or removed, the pointer remains valid.
    //
    // If the pointer is not valid, this is a no-op.
207
    if (element->iteratorValid()) {
208 209

        // Is valid, so protect list against concurrent access
210
        isc::locks::scoped_lock<isc::locks::mutex> lock(mutex_);
211

212 213 214
        lru_.erase(element->getLruIterator());  // Remove element from list
        element->invalidateIterator();          // Invalidate pointer
        --count_;                               // One less element
215 216 217 218 219 220 221 222
    }
}

// Touch an element - remove it from the list and add to the end
template <typename T>
void LruList<T>::touch(boost::shared_ptr<T>& element) {

    // As before, if the pointer is not valid, this is a no-op.
223
    if (element->iteratorValid()) {
224 225

        // Protect list against concurrent access
226
        isc::locks::scoped_lock<isc::locks::mutex> lock(mutex_);
227 228

        // Move the element to the end of the list.
229
        lru_.splice(lru_.end(), lru_, element->getLruIterator());
230 231 232 233

        // Update the iterator in the element to point to it.  We can
        // offset from end() as a list has a bidirectional iterator.
        iterator i = lru_.end();
234
        element->setLruIterator(--i);
235 236 237
    }
}

238
// Clear the list-  when done, the size of list will be 0.
239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256
template <typename T>
void LruList<T>::clear() {
    // Protect list against concurrent access
    isc::locks::scoped_lock<isc::locks::mutex> lock(mutex_);

    // ... and update the count while we have the mutex.
    count_ = 0;
    typename std::list<boost::shared_ptr<T> >::iterator iter;
    if (dropped_) {
        for (iter = lru_.begin(); iter != lru_.end(); ++iter) {
            // Call the drop handler.
            (*dropped_)(iter->get());
        }
    }

    lru_.clear();
}

257 258 259 260
}   // namespace nsas
}   // namespace isc

#endif // __LRU_LIST_H