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