1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 /*
3  * This file is part of the LibreOffice project.
4  *
5  * This Source Code Form is subject to the terms of the Mozilla Public
6  * License, v. 2.0. If a copy of the MPL was not distributed with this
7  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8  *
9  */
10 
11 #ifndef INCLUDED_O3TL_LRU_MAP_HXX
12 #define INCLUDED_O3TL_LRU_MAP_HXX
13 
14 #include <algorithm>
15 #include <cassert>
16 #include <list>
17 #include <unordered_map>
18 #include <cstddef>
19 
20 namespace o3tl
21 {
22 /** LRU map
23  *
24  * Similar to unordered_map (it actually uses it) with additionally functionality
25  * which removes the entries that have been "least recently used" when the size
26  * hits the specified capacity.
27  *
28  * It only implements the minimal methods needed and the implementation is NOT
29  * thread safe.
30  *
31  * The implementation is as simple as possible but it still uses O(1) complexity
32  * for most of the operations with a combination unordered map and linked list.
33  *
34  **/
35 template <typename Key, typename Value, class KeyHash = std::hash<Key>,
36           class KeyEqual = std::equal_to<Key>>
37 class lru_map final
38 {
39 public:
40     typedef typename std::pair<Key, Value> key_value_pair_t;
41 
42 private:
43     typedef std::list<key_value_pair_t> list_t;
44     typedef typename list_t::iterator list_iterator_t;
45     typedef typename list_t::const_iterator list_const_iterator_t;
46 
47     typedef std::unordered_map<Key, list_iterator_t, KeyHash, KeyEqual> map_t;
48     typedef typename map_t::iterator map_iterator_t;
49     typedef typename map_t::const_iterator map_const_iterator_t;
50 
51     list_t mLruList;
52     map_t mLruMap;
53     size_t mMaxSize;
54 
checkLRU()55     void checkLRU()
56     {
57         if (mLruMap.size() > mMaxSize)
58         {
59             // remove from map
60             mLruMap.erase(mLruList.back().first);
61             // remove from list
62             mLruList.pop_back();
63         }
64     }
65 
66 public:
67     typedef list_iterator_t iterator;
68     typedef list_const_iterator_t const_iterator;
69 
70     // a size of 0 effectively disables the LRU cleanup code
lru_map(size_t nMaxSize)71     lru_map(size_t nMaxSize)
72         : mMaxSize(nMaxSize ? nMaxSize : std::min(mLruMap.max_size(), mLruList.max_size()))
73     {
74     }
~lru_map()75     ~lru_map()
76     {
77         // Some code .e.g. SalBitmap likes to remove itself from a cache during it's destructor, which means we
78         // get calls into lru_map while we are in destruction, so use the swap-and-clear idiom to avoid those problems.
79         mLruMap.clear();
80         list_t().swap(mLruList);
81     }
82 
setMaxSize(size_t nMaxSize)83     void setMaxSize(size_t nMaxSize)
84     {
85         mMaxSize = nMaxSize ? nMaxSize : std::min(mLruMap.max_size(), mLruList.max_size());
86         while (mLruMap.size() > mMaxSize)
87             checkLRU();
88     }
89 
insert(key_value_pair_t & rPair)90     void insert(key_value_pair_t& rPair)
91     {
92         map_iterator_t i = mLruMap.find(rPair.first);
93 
94         if (i == mLruMap.end()) // doesn't exist -> add to queue and map
95         {
96             // add to front of the list
97             mLruList.push_front(rPair);
98             // add the list position (iterator) to the map
99             auto it = mLruList.begin();
100             mLruMap[it->first] = it;
101             checkLRU();
102         }
103         else // already exists -> replace value
104         {
105             // replace value
106             i->second->second = rPair.second;
107             // bring to front of the lru list
108             mLruList.splice(mLruList.begin(), mLruList, i->second);
109         }
110     }
111 
insert(key_value_pair_t && rPair)112     void insert(key_value_pair_t&& rPair)
113     {
114         map_iterator_t i = mLruMap.find(rPair.first);
115 
116         if (i == mLruMap.end()) // doesn't exist -> add to list and map
117         {
118             // add to front of the list
119             mLruList.push_front(std::move(rPair));
120             // add the list position (iterator) to the map
121             auto it = mLruList.begin();
122             mLruMap[it->first] = it;
123             checkLRU();
124         }
125         else // already exists -> replace value
126         {
127             // replace value
128             i->second->second = std::move(rPair.second);
129             // push to back of the lru list
130             mLruList.splice(mLruList.begin(), mLruList, i->second);
131         }
132     }
133 
find(const Key & key)134     list_const_iterator_t find(const Key& key)
135     {
136         const map_iterator_t i = mLruMap.find(key);
137         if (i == mLruMap.cend()) // can't find entry for the key
138         {
139             // return empty iterator
140             return mLruList.cend();
141         }
142         else
143         {
144             // push to back of the lru list
145             mLruList.splice(mLruList.begin(), mLruList, i->second);
146             return i->second;
147         }
148     }
149 
150     // reverse-iterates the list removing all items matching the predicate
remove_if(UnaryPredicate pred)151     template <class UnaryPredicate> void remove_if(UnaryPredicate pred)
152     {
153         auto it = mLruList.rbegin();
154         while (it != mLruList.rend())
155         {
156             if (pred(*it))
157             {
158                 mLruMap.erase(it->first);
159                 it = decltype(it){ mLruList.erase(std::next(it).base()) };
160             }
161             else
162                 ++it;
163         }
164     }
165 
begin() const166     list_const_iterator_t begin() const { return mLruList.cbegin(); }
167 
end() const168     list_const_iterator_t end() const { return mLruList.cend(); }
169 
size() const170     size_t size() const
171     {
172         assert(mLruMap.size() == mLruList.size());
173         return mLruMap.size();
174     }
175 
clear()176     void clear()
177     {
178         mLruMap.clear();
179         mLruList.clear();
180     }
181 };
182 }
183 
184 #endif /* INCLUDED_O3TL_LRU_MAP_HXX */
185 
186 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
187