This file is indexed.

/usr/include/dune/common/lru.hh is in libdune-common-dev 2.2.1-2.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
#ifndef DUNE_COMMON_LRU_HH
#define DUNE_COMMON_LRU_HH

#include <list>
#include <utility>
#include <map>

/** @file
    @author Christian Engwer
    @brief LRU Cache Container, using an STL like interface
*/

namespace Dune {

namespace {

/*
   hide the default traits in an empty namespace
 */
template <typename _Key, typename _Tp,
          typename _Alloc = std::allocator<_Tp> >
struct _lru_default_traits
{
    typedef _Key key_type;
    typedef _Alloc allocator;
    typedef std::list< std::pair<_Key, _Tp> > list_type;
    typedef typename list_type::iterator iterator;
    typedef typename std::less<key_type> cmp;
    typedef std::map< key_type, iterator, cmp, 
		      typename allocator::template rebind<std::pair<const key_type, iterator> >::other > map_type;
};

} // end empty namespace

/**
    @brief LRU Cache Container
    
    Implementatation of an LRU (least recently used) cache
    container. This implementation follows the approach presented in
    http://aim.adc.rmit.edu.au/phd/sgreuter/papers/graphite2003.pdf
 */
template <typename _Key, typename _Tp,
          typename _Traits = _lru_default_traits<_Key, _Tp> >
class lru
{
    typedef typename _Traits::list_type       list_type;
    typedef typename _Traits::map_type        map_type;
    typedef typename _Traits::allocator       allocator;
    typedef typename map_type::iterator       map_iterator;
    typedef typename map_type::const_iterator const_map_iterator;
    
public:
    typedef typename _Traits::key_type          key_type;
    typedef typename allocator::value_type      value_type;
    typedef typename allocator::pointer         pointer;
    typedef typename allocator::const_pointer   const_pointer;
    typedef typename allocator::const_reference const_reference;
    typedef typename allocator::reference       reference;
    typedef typename allocator::size_type       size_type;
    typedef typename list_type::iterator        iterator;
    typedef typename list_type::const_iterator  const_iterator;
  
    /**
     *  Returns a read/write reference to the data of the most
     *  recently used entry.
     */
    reference front()
    {
        return _data.front().second;
    }

    /**
     *  Returns a read-only (constant) reference to the data of the
     *  most recently used entry.
     */
    const_reference front() const
    {
        return _data.front().second;
    }

    /**
     *  Returns a read/write reference to the data of the least
     *  recently used entry.
     */
    reference back()
    {
        return _data.back().second;
    }

    /**
     *  Returns a read-only (constant) reference to the data of the
     *  least recently used entry.
     */
    const_reference back (int i) const
    {
        return _data.back().second;
    }


    /**
     * @brief Removes the first element.
     */
    const void pop_front()
    {
        key_type k = _data.front().first;
        _data.pop_front();
        _index.erase(k);
    }
    /**
     * @brief Removes the last element.
     */
    const void pop_back()
    {
        key_type k = _data.back().first;
        _data.pop_back();
        _index.erase(k);
    }

    /**
     * @brief Finds the element whose key is k.
     *
     * @return iterator
     */
    iterator find (const key_type & key)
    {
        const map_iterator it = _index.find(key);
        if (it == _index.end()) return _data.end();
        return it->second;
    }
    
    /**
     * @brief Finds the element whose key is k.
     *
     * @return const_iterator
     */
    const_iterator find (const key_type & key) const
    {
        const map_iterator it = _index.find(key);
        if (it == _index.end()) return _data.end();
        return it->second;
    }

    /**
     * @brief Insert a value into the container
     *
     * Stores value under key and marks it as most recent.
     *
     * @param key   associated with data
     * @param data  to store
     *
     * @return reference of stored data
     */
    reference insert (const key_type & key, const_reference data)
    {
        std::pair<key_type, value_type> x(key, data);
        /* insert item as mru */
        iterator it = _data.insert(_data.begin(), x);
        /* store index */
        _index.insert(std::make_pair(key,it));

        return it->second;
    }

    /**
     * @copydoc touch
     */
    reference insert (const key_type & key)
    {
        return touch (key);
    }

    /**
     * @brief mark data associateed with key as most recent
     *
     * @return reference of stored data
     */
    reference touch (const key_type & key)
    {
        /* query _index for iterator */
        iterator it = _index[key];
        /* update _data
           move it to the front
         */
        _data.splice(_data.begin(), _data, it);
        return it->second;
    }

    /**
     *
     */
    size_type size() const
    {
        return _data.size();
    }    
    
    /**
     *
     */
    void resize(size_type new_size)
    {
        assert(new_size <= size());

        while (new_size < size())
            pop_back();
    }
    
    /**
     *
     */
    void clear()
    {
        _data.clear();
        _index.clear();
    }    
    
private:
    list_type _data;
    map_type  _index;
  
};

} // namespace Dune

#endif // DUNE_COMMON_LRU_HH