HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
UT_LRUCache.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_LRUCache.h ( UT Library, C++)
7  *
8  * COMMENTS:
9  * The LRU cache has a hash table for fast access and a link list for
10  * quick removal when the cache is full. Items are unique in the cache.
11  */
12 
13 #ifndef UT_LRU_CACHE_H
14 #define UT_LRU_CACHE_H
15 
16 #include "UT_Assert.h"
17 #include "UT_IteratorRange.h"
18 #include "UT_NonCopyable.h"
19 
20 #include <SYS/SYS_Types.h>
21 #include <SYS/SYS_TypeTraits.h>
22 
23 #include <functional>
24 #include <list>
25 #include <type_traits>
26 #include <unordered_map>
27 
28 namespace UT
29 {
30  // A dummy implementation of UT_RWLock that does nothing.
31  class RWNullLock
32  {
33  public:
34  void readLock() {}
35  void writeLock() {}
36  void readUnlock() {}
37  void writeUnlock() {}
38  };
39 }
40 
41 /// A default helper function used by UT_LRUCache to determine the size of the
42 /// objects it stores to help prune the storage so that it doesn't exceed the
43 /// maximum given in the constructor.
44 template<typename V>
45 inline exint
46 UTlruGetItemSize(const V &)
47 {
48  static_assert(!std::is_pointer<V>::value,
49  "Pointer types need their own size function.");
50  return sizeof(V);
51 }
52 
53 
54 /// A default helper function used by UT_LRUCache to determine whether an
55 /// object is currently in use and so should not be deleted when the cache
56 /// gets pruned.
57 template<typename V>
58 inline bool
60 {
61  return false;
62 }
63 
64 
65 
66 template<typename K,
67  typename V,
68  exint(*SizeFunc)(const V &) = UTlruGetItemSize<V>,
69  bool(*InUseFunc)(const V &) = UTlruGetItemInUse<V>,
70  typename L=UT::RWNullLock>
71 class UT_LRUCache :
72  public UT_NonCopyable
73 {
74  using ValueType = std::pair<const K, V>;
75  using ValueList = std::list<ValueType> ;
76  using KeyIteratorMap = std::unordered_map<K, typename ValueList::iterator>;
77 
78  template<typename PROXIED, typename TYPE>
79  friend class iterator_base;
80 
81  ValueList myValueList;
82  KeyIteratorMap myKeyMap;
83  exint myMaxSize;
84  exint myCurrentSize;
85  std::function<exint(const V &)> mySizeFunc;
86  std::function<bool(const V &)> myInUseFunc;
87  mutable L *myLock;
88 
89 protected:
90  /// This iterator is just a simple proxy around either the regular iterator
91  /// or the const_iterator on the internal list.
92  template<typename PROXIED, typename TYPE>
93  class iterator_base :
94  public std::iterator<std::bidirectional_iterator_tag, TYPE>
95  {
96  using Base =
97  typename std::iterator<std::bidirectional_iterator_tag, TYPE>;
98  using proxied_iterator = PROXIED;
99  public:
100  using typename Base::pointer;
101  using typename Base::reference;
102 
103  iterator_base() : myLock(nullptr) {}
104 
106  {
107  other.myLock->readLock();
108  myIt = other.myIt;
109  myLock = other.myLock;
110  }
111 
113  {
114  myIt = std::move(other.myIt);
115  other.myIt = proxied_iterator();
116  myLock = other.myLock;
117  other.myLock = nullptr;
118  }
119 
121  {
122  other.myLock->readLock();
123  myIt = other.myIt;
124  myLock = other.myLock;
125  return *this;
126  }
127 
129  {
130  myIt = std::move(other.myIt);
131  other.myIt = proxied_iterator();
132  myLock = other.myLock;
133  other.myLock = nullptr;
134  return *this;
135  }
136 
138  {
139  // Release the read lock on destroy.
140  if (myLock)
141  myLock->readUnlock();
142  }
143 
144  iterator_base &operator++() { ++myIt; return *this; }
145  iterator_base &operator--() { --myIt; return *this; }
146 
147  pointer operator->() const { return &(*myIt); }
148  reference operator*() const { return *myIt; }
149 
150  bool operator==(const iterator_base &other) const
151  {
152  return myIt == other.myIt;
153  }
154  bool operator!=(const iterator_base &other) const
155  {
156  return myIt != other.myIt;
157  }
158 
159  protected:
161 
162  iterator_base(proxied_iterator it, L *lock) :
163  myIt(it), myLock(lock) { }
164 
165  private:
166  proxied_iterator myIt;
167  L *myLock;
168  };
169 
170 public:
171  /// A iterator pointing to mutable values.
172  using iterator = iterator_base<typename ValueList::iterator, std::pair<const K, V>>;
173 
174  /// A const iterator pointing to immutable values.
175  using const_iterator = iterator_base<typename ValueList::const_iterator, const std::pair<const K, V>>;
176 
177  /// Construct a new LRU cache of a given @c max_size. By default the cache
178  /// is not thread-safe, but by setting the template argument @c L to
179  /// @c UT_RWLock, the cache is automatically thread-safe. This incurs some
180  /// overhead due to the locking, however, so only do that if absolutely
181  /// required.
183  myMaxSize(max_size),
184  myCurrentSize(0),
185  mySizeFunc(SizeFunc),
186  myInUseFunc(InUseFunc),
187  myLock(nullptr)
188  {
190  myLock = new L;
191  }
192 
193  /// Sets the new maximum size for the cache. If the new maximum is smaller
194  /// than the current maximum, the cache will be pruned to fit the new
195  /// maximums size.
196  void setMaxSize(exint max_size)
197  {
198  if (max_size >= myMaxSize)
199  {
200  myMaxSize = max_size;
201  }
202  else
203  {
204  myMaxSize = max_size;
205  if (myLock)
206  myLock->writeLock();
207 
208  prune(nullptr);
209 
210  if (myLock)
211  myLock->writeUnlock();
212  }
213  }
214 
215  /// Returns the current maximum size of the cache.
216  exint maxSize() const { return myMaxSize; }
217 
218  /// Returns the current size of the cache, in arbitrary units.
219  /// If the cache is thread-safe this value may not be the most up-to-date.
221  {
222  if (myLock)
223  myLock->readLock();
224 
225  exint size = myCurrentSize;
226 
227  if (myLock)
228  myLock->readUnlock();
229  return size;
230  }
231 
232  /// Returns the number of items in the cache.
233  exint count() const
234  {
235  if (myLock)
236  myLock->readLock();
237 
238  exint size = myValueList.size();
239 
240  if (myLock)
241  myLock->readUnlock();
242  return size;
243  }
244 
245  /// Checks for the presence of the item with the given @c key. Does not
246  /// affect their ordering, like @c find.
247  bool contains(const K &key) const
248  {
249  if (myLock)
250  myLock->readLock();
251 
252  bool found = (myKeyMap.find(key) != myKeyMap.end());
253 
254  if (myLock)
255  myLock->readUnlock();
256  return found;
257  }
258 
259  /// Find the item in the cache with the given key. If nothing is found
260  /// then the iterator will point to the end.
261  /// There's no const version, since looking up the key modifies the LRU
262  /// cache's state and the iterator holds a read lock, if the cache is
263  /// thread-safe.
264  /// @note Since the iterator holds a lock, do
265  iterator find(const K &key)
266  {
267  if (myLock)
268  myLock->readLock();
269 
270  auto itK = myKeyMap.find(key);
271  if (itK == myKeyMap.end())
272  {
273  if (myLock)
274  myLock->readUnlock();
275  return iterator(myValueList.end(), nullptr);
276  }
277 
278  // Move this item to the top of the list.
279  if (itK->second != myValueList.begin())
280  {
281  myValueList.splice(itK->second, myValueList, myValueList.begin());
282  itK->second = myValueList.begin();
283  }
284 
285  return iterator(itK->second, myLock);
286  }
287 
288  /// Insert a new item into the cache. The item is automatically marked as
289  /// the most recently used. The cache is pruned beforehand, to avoid
290  /// evicting the item immediately. Returns a pair of an iterator and a
291  /// @c bool. The iterator points to the item inserted, or the existing item
292  /// if not evicted. The @c bool value indicates whether the item got
293  /// inserted or not.
294  std::pair<iterator, bool>
295  insert(const K &key, V &&value, bool evict=false)
296  {
297  if (myLock)
298  {
299  // Get both read and write locks. Upon exit, we relinquish the
300  // write lock, but the read lock gets carried out through the
301  // iterator.
302  myLock->writeLock();
303  myLock->readLock();
304  }
305 
306  std::pair<iterator, bool> result;
307  auto itK = myKeyMap.find(key);
308  if (itK != myKeyMap.end() && !evict)
309  {
310  // The item already exists and we don't want to evict the existing
311  // item.
312  result = std::make_pair(iterator(itK->second, myLock), false);
313  }
314  else
315  {
316  if (itK != myKeyMap.end())
317  {
318  // If we're replacing an item, take that away from the current
319  // size before updating it with the new value.
320  myCurrentSize -= mySizeFunc((itK->second)->second);
321  myCurrentSize += mySizeFunc(value);
322 
323  prune(&itK->second);
324 
325  // We're just updating an existing item. Move it to the
326  // beginning and move the contents of the existing object onto
327  // the old one.
328  myValueList.splice(itK->second, myValueList,
329  myValueList.begin());
330 
331  myValueList.begin()->second = std::move(value);
332  itK->second = myValueList.begin();
333 
334  result = std::make_pair(iterator(itK->second, myLock), true);
335  }
336  else
337  {
338  myCurrentSize += mySizeFunc(value);
339 
340  prune(nullptr);
341 
342  myValueList.push_front(std::make_pair(key, std::move(value)));
343  myKeyMap.insert(std::make_pair(key, myValueList.begin()));
344 
345  result = std::make_pair(iterator(myValueList.begin(), myLock),
346  true);
347  }
348  }
349 
350  if (myLock)
351  myLock->writeUnlock();
352 
353  return result;
354  }
355 
356 
357  /// Removes the item matching the @c key. If the item existed and was
358  /// successfully removed, then this function returns @c true.
359  bool erase(const K &key)
360  {
361  bool updated = false;
362  if (myLock)
363  myLock->writeLock();
364 
365  auto itK = myKeyMap.find(key);
366  if (itK != myKeyMap.end())
367  {
368  myCurrentSize -= mySizeFunc((itK->second)->second);
369  myValueList.erase(itK->second);
370  myKeyMap.erase(itK);
371  updated = true;
372  }
373 
374  if (myLock)
375  myLock->writeUnlock();
376 
377  return updated;
378  }
379 
380  /// Steals an item from the cache. This is functionally equivalent to
381  /// @c erase with a key, except the item in the cache also gets hoisted
382  /// outside into @c value, if it exists.
383  bool steal(const K &key, V &&value)
384  {
385  bool updated = false;
386  if (myLock)
387  myLock->writeLock();
388 
389  auto itK = myKeyMap.find(key);
390  if (itK != myKeyMap.end())
391  {
392  myCurrentSize -= mySizeFunc((itK->second)->second);
393 
394  // Move the contents of the cache item into the outside item.
395  value = std::move((itK->second)->second);
396 
397  myValueList.erase(itK->second);
398  myKeyMap.erase(itK);
399  updated = true;
400  }
401 
402  if (myLock)
403  myLock->writeUnlock();
404 
405  return updated;
406  }
407 
408  /// Clears the cache completely.
409  void clear()
410  {
411  if (myLock) myLock->writeLock();
412 
413  myKeyMap.clear();
414  myValueList.clear();
415  myCurrentSize = 0;
416 
417  if (myLock) myLock->writeUnlock();
418  }
419 
420  /// Returns an iterator to the front-most item in the LRU cache.
422  {
423  if (myLock) myLock->readLock();
424  return iterator(myValueList.begin(), myLock);
425  }
426 
427  /// Returns an iterator to the end of the LRU list.
429  {
430  // The iterator will unlock the read lock when it destroys.
431  return iterator(myValueList.end(), nullptr);
432  }
433 
434  /// Returns a const iterator to the front-most item in the LRU cache.
436  {
437  if (myLock) myLock->readLock();
438  return const_iterator(myValueList.begin(), myLock);
439  }
440 
441  /// Returns a const iterator to the end of the LRU list.
443  {
444  // The iterator will unlock the read lock when it destroys.
445  return const_iterator(myValueList.end(), nullptr);
446  }
447 
448 private:
449  /// Prune the list, from the last to the first. We skip objects that define
450  /// inUse() which returns @c true.
451  /// @note This function assumes that the caller holds the write lock.
452  void prune(typename ValueList::iterator *itSkipV = nullptr)
453  {
454  for (auto ritV = myValueList.rbegin();
455  myCurrentSize > myMaxSize && ritV != myValueList.rend(); ++ritV)
456  {
457  if ((itSkipV && ritV.base() == *itSkipV) ||
458  myInUseFunc(ritV->second))
459  {
460  continue;
461  }
462 
463  myCurrentSize -= mySizeFunc(ritV->second);
464 
465  auto itK = myKeyMap.find(ritV->first);
466  myKeyMap.erase(itK);
467  // Delicate dance because erase takes a forward iterator, but we're
468  // using a reverse iterator.
469  auto itV = myValueList.erase(std::prev(ritV.base()));
470  ritV = typename ValueList::reverse_iterator(itV);
471  }
472  }
473 };
474 
475 #endif
iterator_base(proxied_iterator it, L *lock)
Definition: UT_LRUCache.h:162
bool erase(const K &key)
Definition: UT_LRUCache.h:359
std::pair< iterator, bool > insert(const K &key, V &&value, bool evict=false)
Definition: UT_LRUCache.h:295
bool steal(const K &key, V &&value)
Definition: UT_LRUCache.h:383
iterator find(const K &key)
Definition: UT_LRUCache.h:265
bool UTlruGetItemInUse(const V &)
Definition: UT_LRUCache.h:59
#define SYS_EXINT_MAX
Definition: SYS_Types.h:165
bool operator!=(const iterator_base &other) const
Definition: UT_LRUCache.h:154
iterator_base< typename ValueList::iterator, std::pair< const cl_mem, ut_clBuffer >> iterator
A iterator pointing to mutable values.
Definition: UT_LRUCache.h:172
GLsizeiptr size
Definition: glcorearb.h:663
iterator_base< typename ValueList::const_iterator, const std::pair< const cl_mem, ut_clBuffer >> const_iterator
A const iterator pointing to immutable values.
Definition: UT_LRUCache.h:175
int64 exint
Definition: SYS_Types.h:109
exint currentSize() const
Definition: UT_LRUCache.h:220
iterator begin()
Returns an iterator to the front-most item in the LRU cache.
Definition: UT_LRUCache.h:421
void readUnlock()
Definition: UT_LRUCache.h:36
iterator_base & operator=(iterator_base &&other)
Definition: UT_LRUCache.h:128
exint UTlruGetItemSize(const V &)
Definition: UT_LRUCache.h:46
iterator_base(iterator_base &&other)
Definition: UT_LRUCache.h:112
bool operator==(const iterator_base &other) const
Definition: UT_LRUCache.h:150
iterator end()
Returns an iterator to the end of the LRU list.
Definition: UT_LRUCache.h:428
void writeLock()
Definition: UT_LRUCache.h:35
pointer operator->() const
Definition: UT_LRUCache.h:147
exint maxSize() const
Returns the current maximum size of the cache.
Definition: UT_LRUCache.h:216
UT_LRUCache(exint max_size=SYS_EXINT_MAX)
Definition: UT_LRUCache.h:182
void setMaxSize(exint max_size)
Definition: UT_LRUCache.h:196
bool contains(const K &key) const
Definition: UT_LRUCache.h:247
GLsizei const GLfloat * value
Definition: glcorearb.h:823
GLenum void ** pointer
Definition: glcorearb.h:809
const_iterator begin() const
Returns a const iterator to the front-most item in the LRU cache.
Definition: UT_LRUCache.h:435
const_iterator end() const
Returns a const iterator to the end of the LRU list.
Definition: UT_LRUCache.h:442
exint count() const
Returns the number of items in the cache.
Definition: UT_LRUCache.h:233
iterator_base(const iterator_base &other)
Definition: UT_LRUCache.h:105
iterator_base & operator=(const iterator_base &other)
Definition: UT_LRUCache.h:120
void prune(TreeT &tree, typename TreeT::ValueType tolerance=zeroVal< typename TreeT::ValueType >(), bool threaded=true, size_t grainSize=1)
Reduce the memory footprint of a tree by replacing with tiles any nodes whose values are all the same...
Definition: Prune.h:374
reference operator*() const
Definition: UT_LRUCache.h:148
friend class iterator_base
Definition: UT_LRUCache.h:79
void readLock()
Definition: UT_LRUCache.h:34
iterator_base & operator++()
Definition: UT_LRUCache.h:144
void clear()
Clears the cache completely.
Definition: UT_LRUCache.h:409
iterator_base & operator--()
Definition: UT_LRUCache.h:145
void writeUnlock()
Definition: UT_LRUCache.h:37