HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups 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_Function.h"
18 #include "UT_IteratorRange.h"
19 #include "UT_NonCopyable.h"
20 
21 #include <SYS/SYS_Types.h>
22 #include <SYS/SYS_TypeTraits.h>
23 
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;
86  UT_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>
94  {
95  using proxied_iterator = PROXIED;
96 
97  public:
98  using iterator_category = std::bidirectional_iterator_tag;
99  using value_type = TYPE;
100  using difference_type = std::ptrdiff_t;
101  using pointer = TYPE*;
102  using reference = TYPE&;
103 
104  iterator_base() : myLock(nullptr) {}
105 
107  {
108  other.myLock->readLock();
109  myIt = other.myIt;
110  myLock = other.myLock;
111  }
112 
114  {
115  myIt = std::move(other.myIt);
116  other.myIt = proxied_iterator();
117  myLock = other.myLock;
118  other.myLock = nullptr;
119  }
120 
122  {
123  other.myLock->readLock();
124  myIt = other.myIt;
125  myLock = other.myLock;
126  return *this;
127  }
128 
130  {
131  myIt = std::move(other.myIt);
132  other.myIt = proxied_iterator();
133  myLock = other.myLock;
134  other.myLock = nullptr;
135  return *this;
136  }
137 
139  {
140  // Release the read lock on destroy.
141  if (myLock)
142  myLock->readUnlock();
143  }
144 
145  iterator_base &operator++() { ++myIt; return *this; }
146  iterator_base &operator--() { --myIt; return *this; }
147 
148  pointer operator->() const { return &(*myIt); }
149  reference operator*() const { return *myIt; }
150 
151  bool operator==(const iterator_base &other) const
152  {
153  return myIt == other.myIt;
154  }
155  bool operator!=(const iterator_base &other) const
156  {
157  return myIt != other.myIt;
158  }
159 
160  protected:
162 
163  iterator_base(proxied_iterator it, L *lock) :
164  myIt(it), myLock(lock) { }
165 
166  private:
167  proxied_iterator myIt;
168  L *myLock;
169  };
170 
171 public:
172  /// A iterator pointing to mutable values.
173  using iterator = iterator_base<typename ValueList::iterator, std::pair<const K, V>>;
174 
175  /// A const iterator pointing to immutable values.
176  using const_iterator = iterator_base<typename ValueList::const_iterator, const std::pair<const K, V>>;
177 
178  /// Construct a new LRU cache of a given @c max_size. By default the cache
179  /// is not thread-safe, but by setting the template argument @c L to
180  /// @c UT_RWLock, the cache is automatically thread-safe. This incurs some
181  /// overhead due to the locking, however, so only do that if absolutely
182  /// required.
184  myMaxSize(max_size),
185  myCurrentSize(0),
186  mySizeFunc(SizeFunc),
187  myInUseFunc(InUseFunc),
188  myLock(nullptr)
189  {
191  myLock = new L;
192  }
193 
194  /// Sets the new maximum size for the cache. If the new maximum is smaller
195  /// than the current maximum, the cache will be pruned to fit the new
196  /// maximums size.
197  void setMaxSize(exint max_size)
198  {
199  if (max_size >= myMaxSize)
200  {
201  myMaxSize = max_size;
202  }
203  else
204  {
205  myMaxSize = max_size;
206  if (myLock)
207  myLock->writeLock();
208 
209  prune(nullptr);
210 
211  if (myLock)
212  myLock->writeUnlock();
213  }
214  }
215 
216  /// Returns the current maximum size of the cache.
217  exint maxSize() const { return myMaxSize; }
218 
219  /// Returns the current size of the cache, in arbitrary units.
220  /// If the cache is thread-safe this value may not be the most up-to-date.
222  {
223  if (myLock)
224  myLock->readLock();
225 
226  exint size = myCurrentSize;
227 
228  if (myLock)
229  myLock->readUnlock();
230  return size;
231  }
232 
233  /// Returns the number of items in the cache.
234  exint count() const
235  {
236  if (myLock)
237  myLock->readLock();
238 
239  exint size = myValueList.size();
240 
241  if (myLock)
242  myLock->readUnlock();
243  return size;
244  }
245 
246  /// Checks for the presence of the item with the given @c key. Does not
247  /// affect their ordering, like @c find.
248  bool contains(const K &key) const
249  {
250  if (myLock)
251  myLock->readLock();
252 
253  bool found = (myKeyMap.find(key) != myKeyMap.end());
254 
255  if (myLock)
256  myLock->readUnlock();
257  return found;
258  }
259 
260  /// Find the item in the cache with the given key. If nothing is found
261  /// then the iterator will point to the end.
262  /// There's no const version, since looking up the key modifies the LRU
263  /// cache's state and the iterator holds a read lock, if the cache is
264  /// thread-safe.
265  /// @note Since the iterator holds a lock, do
266  iterator find(const K &key)
267  {
268  if (myLock)
269  myLock->readLock();
270 
271  auto itK = myKeyMap.find(key);
272  if (itK == myKeyMap.end())
273  {
274  if (myLock)
275  myLock->readUnlock();
276  return iterator(myValueList.end(), nullptr);
277  }
278 
279  // Move this item to the top of the list.
280  if (itK->second != myValueList.begin())
281  {
282  myValueList.splice(myValueList.begin(), myValueList,
283  itK->second);
284  itK->second = myValueList.begin();
285  }
286 
287  return iterator(itK->second, myLock);
288  }
289 
290  /// Insert a new item into the cache. The item is automatically marked as
291  /// the most recently used. The cache is pruned beforehand, to avoid
292  /// evicting the item immediately. Returns a pair of an iterator and a
293  /// @c bool. The iterator points to the item inserted, or the existing item
294  /// if not evicted. The @c bool value indicates whether the item got
295  /// inserted or not.
296  std::pair<iterator, bool>
297  insert(const K &key, V &&value, bool evict=false)
298  {
299  if (myLock)
300  {
301  // Get both read and write locks. Upon exit, we relinquish the
302  // write lock, but the read lock gets carried out through the
303  // iterator.
304  myLock->writeLock();
305  myLock->readLock();
306  }
307 
308  std::pair<iterator, bool> result;
309  auto itK = myKeyMap.find(key);
310  if (itK != myKeyMap.end() && !evict)
311  {
312  // The item already exists and we don't want to evict the existing
313  // item.
314  // Note we should probably move this to the front of the
315  // LRU, there is a test for this disabled in the testut.
316  // In practice it likely is moot as usually people will
317  // have just done a find.
318  result = std::make_pair(iterator(itK->second, myLock), false);
319  }
320  else
321  {
322  if (itK != myKeyMap.end())
323  {
324  // If we're replacing an item, take that away from the current
325  // size before updating it with the new value.
326  myCurrentSize -= mySizeFunc((itK->second)->second);
327  myCurrentSize += mySizeFunc(value);
328 
329  prune(&itK->second);
330 
331  // We're just updating an existing item. Move it to the
332  // beginning and move the contents of the existing object onto
333  // the old one.
334  myValueList.splice(myValueList.begin(), myValueList,
335  itK->second);
336 
337  myValueList.begin()->second = std::move(value);
338  itK->second = myValueList.begin();
339 
340  result = std::make_pair(iterator(itK->second, myLock), true);
341  }
342  else
343  {
344  myCurrentSize += mySizeFunc(value);
345 
346  prune(nullptr);
347 
348  myValueList.push_front(std::make_pair(key, std::move(value)));
349  myKeyMap.insert(std::make_pair(key, myValueList.begin()));
350 
351  result = std::make_pair(iterator(myValueList.begin(), myLock),
352  true);
353  }
354  }
355 
356  if (myLock)
357  myLock->writeUnlock();
358 
359  return result;
360  }
361 
362 
363  /// Removes the item matching the @c key. If the item existed and was
364  /// successfully removed, then this function returns @c true.
365  bool erase(const K &key)
366  {
367  bool updated = false;
368  if (myLock)
369  myLock->writeLock();
370 
371  auto itK = myKeyMap.find(key);
372  if (itK != myKeyMap.end())
373  {
374  myCurrentSize -= mySizeFunc((itK->second)->second);
375  myValueList.erase(itK->second);
376  myKeyMap.erase(itK);
377  updated = true;
378  }
379 
380  if (myLock)
381  myLock->writeUnlock();
382 
383  return updated;
384  }
385 
386  /// Steals an item from the cache. This is functionally equivalent to
387  /// @c erase with a key, except the item in the cache also gets hoisted
388  /// outside into @c value, if it exists.
389  bool steal(const K &key, V &&value)
390  {
391  bool updated = false;
392  if (myLock)
393  myLock->writeLock();
394 
395  auto itK = myKeyMap.find(key);
396  if (itK != myKeyMap.end())
397  {
398  myCurrentSize -= mySizeFunc((itK->second)->second);
399 
400  // Move the contents of the cache item into the outside item.
401  value = std::move((itK->second)->second);
402 
403  myValueList.erase(itK->second);
404  myKeyMap.erase(itK);
405  updated = true;
406  }
407 
408  if (myLock)
409  myLock->writeUnlock();
410 
411  return updated;
412  }
413 
414  /// Clears the cache completely.
415  void clear()
416  {
417  if (myLock) myLock->writeLock();
418 
419  myKeyMap.clear();
420  myValueList.clear();
421  myCurrentSize = 0;
422 
423  if (myLock) myLock->writeUnlock();
424  }
425 
426  /// Returns an iterator to the front-most item in the LRU cache.
428  {
429  if (myLock) myLock->readLock();
430  return iterator(myValueList.begin(), myLock);
431  }
432 
433  /// Returns an iterator to the end of the LRU list.
435  {
436  // The iterator will unlock the read lock when it destroys.
437  return iterator(myValueList.end(), nullptr);
438  }
439 
440  /// Returns a const iterator to the front-most item in the LRU cache.
442  {
443  if (myLock) myLock->readLock();
444  return const_iterator(myValueList.begin(), myLock);
445  }
446 
447  /// Returns a const iterator to the end of the LRU list.
449  {
450  // The iterator will unlock the read lock when it destroys.
451  return const_iterator(myValueList.end(), nullptr);
452  }
453 
454 private:
455  /// Prune the list, from the last to the first. We skip objects that define
456  /// inUse() which returns @c true.
457  /// @note This function assumes that the caller holds the write lock.
458  void prune(typename ValueList::iterator *itSkipV = nullptr)
459  {
460  for (auto ritV = myValueList.rbegin();
461  myCurrentSize > myMaxSize && ritV != myValueList.rend(); ++ritV)
462  {
463  if ((itSkipV && ritV.base() == *itSkipV) ||
464  myInUseFunc(ritV->second))
465  {
466  continue;
467  }
468 
469  myCurrentSize -= mySizeFunc(ritV->second);
470 
471  auto itK = myKeyMap.find(ritV->first);
472  myKeyMap.erase(itK);
473  // Delicate dance because erase takes a forward iterator, but we're
474  // using a reverse iterator.
475  auto itV = myValueList.erase(std::prev(ritV.base()));
476  ritV = typename ValueList::reverse_iterator(itV);
477  }
478  }
479 };
480 
481 #endif
iterator_base(proxied_iterator it, L *lock)
Definition: UT_LRUCache.h:163
bool erase(const K &key)
Definition: UT_LRUCache.h:365
std::pair< iterator, bool > insert(const K &key, V &&value, bool evict=false)
Definition: UT_LRUCache.h:297
bool steal(const K &key, V &&value)
Definition: UT_LRUCache.h:389
GLsizei const GLfloat * value
Definition: glcorearb.h:824
int64 exint
Definition: SYS_Types.h:125
iterator find(const K &key)
Definition: UT_LRUCache.h:266
bool UTlruGetItemInUse(const V &)
Definition: UT_LRUCache.h:59
**But if you need a result
Definition: thread.h:613
#define SYS_EXINT_MAX
Definition: SYS_Types.h:181
bool operator!=(const iterator_base &other) const
Definition: UT_LRUCache.h:155
iterator_base< typename ValueList::iterator, std::pair< const cl_mem, ut_clBuffer >> iterator
A iterator pointing to mutable values.
Definition: UT_LRUCache.h:173
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:176
exint currentSize() const
Definition: UT_LRUCache.h:221
iterator begin()
Returns an iterator to the front-most item in the LRU cache.
Definition: UT_LRUCache.h:427
void readUnlock()
Definition: UT_LRUCache.h:36
iterator_base & operator=(iterator_base &&other)
Definition: UT_LRUCache.h:129
exint UTlruGetItemSize(const V &)
Definition: UT_LRUCache.h:46
iterator_base(iterator_base &&other)
Definition: UT_LRUCache.h:113
bool operator==(const iterator_base &other) const
Definition: UT_LRUCache.h:151
iterator end()
Returns an iterator to the end of the LRU list.
Definition: UT_LRUCache.h:434
void writeLock()
Definition: UT_LRUCache.h:35
pointer operator->() const
Definition: UT_LRUCache.h:148
std::function< T > UT_Function
Definition: UT_Function.h:37
exint maxSize() const
Returns the current maximum size of the cache.
Definition: UT_LRUCache.h:217
UT_LRUCache(exint max_size=SYS_EXINT_MAX)
Definition: UT_LRUCache.h:183
void setMaxSize(exint max_size)
Definition: UT_LRUCache.h:197
bool contains(const K &key) const
Definition: UT_LRUCache.h:248
GLsizeiptr size
Definition: glcorearb.h:664
const_iterator begin() const
Returns a const iterator to the front-most item in the LRU cache.
Definition: UT_LRUCache.h:441
const_iterator end() const
Returns a const iterator to the end of the LRU list.
Definition: UT_LRUCache.h:448
exint count() const
Returns the number of items in the cache.
Definition: UT_LRUCache.h:234
Definition: core.h:1131
iterator_base(const iterator_base &other)
Definition: UT_LRUCache.h:106
iterator_base & operator=(const iterator_base &other)
Definition: UT_LRUCache.h:121
std::bidirectional_iterator_tag iterator_category
Definition: UT_LRUCache.h:98
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:335
reference operator*() const
Definition: UT_LRUCache.h:149
friend class iterator_base
Definition: UT_LRUCache.h:79
void readLock()
Definition: UT_LRUCache.h:34
iterator_base & operator++()
Definition: UT_LRUCache.h:145
void clear()
Clears the cache completely.
Definition: UT_LRUCache.h:415
iterator_base & operator--()
Definition: UT_LRUCache.h:146
void writeUnlock()
Definition: UT_LRUCache.h:37
std::ptrdiff_t difference_type
Definition: UT_LRUCache.h:100