LibreOffice Module o3tl (master)  1
lru_map.hxx
Go to the documentation of this file.
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 
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 
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
69  lru_map(size_t nMaxSize)
70  : mMaxSize(nMaxSize ? nMaxSize : std::min(mLruMap.max_size(), mLruList.max_size()))
71  {}
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 
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 
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 
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>
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 
158  list_const_iterator_t begin() const
159  {
160  return mLruList.cbegin();
161  }
162 
163  list_const_iterator_t end() const
164  {
165  return mLruList.cend();
166  }
167 
168  size_t size() const
169  {
170  assert(mLruMap.size() == mLruList.size());
171  return mLruMap.size();
172  }
173 
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: */
list_const_iterator_t const_iterator
Definition: lru_map.hxx:66
lru_map(size_t nMaxSize)
Definition: lru_map.hxx:69
void checkLRU()
Definition: lru_map.hxx:53
list_const_iterator_t begin() const
Definition: lru_map.hxx:158
std::list< key_value_pair_t > list_t
Definition: lru_map.hxx:41
list_const_iterator_t end() const
Definition: lru_map.hxx:163
std::pair< Key, Value > key_value_pair_t
Definition: lru_map.hxx:38
list_t::const_iterator list_const_iterator_t
Definition: lru_map.hxx:43
#define min(a, b)
map_t mLruMap
Definition: lru_map.hxx:50
LRU map.
Definition: lru_map.hxx:35
size_t size() const
Definition: lru_map.hxx:168
void clear()
Definition: lru_map.hxx:174
int i
void const * base
list_const_iterator_t find(const Key &key)
Definition: lru_map.hxx:125
list_t mLruList
Definition: lru_map.hxx:49
list_iterator_t iterator
Definition: lru_map.hxx:65
list_t::iterator list_iterator_t
Definition: lru_map.hxx:42
void insert(key_value_pair_t &rPair)
Definition: lru_map.hxx:81
map_t::iterator map_iterator_t
Definition: lru_map.hxx:46
std::unordered_map< Key, list_iterator_t, KeyHash, KeyEqual > map_t
Definition: lru_map.hxx:45
const size_t mMaxSize
Definition: lru_map.hxx:51
struct _ADOKey Key
map_t::const_iterator map_const_iterator_t
Definition: lru_map.hxx:47
void remove_if(UnaryPredicate pred)
Definition: lru_map.hxx:143
void insert(key_value_pair_t &&rPair)
Definition: lru_map.hxx:103