13 #ifndef UT_LRU_CACHE_H
14 #define UT_LRU_CACHE_H
25 #include <type_traits>
26 #include <unordered_map>
49 "Pointer types need their own size function.");
68 exint(*SizeFunc)(
const V &) = UTlruGetItemSize<V>,
69 bool(*InUseFunc)(
const V &) = UTlruGetItemInUse<V>,
74 using ValueType = std::pair<const K, V>;
75 using ValueList = std::list<ValueType> ;
76 using KeyIteratorMap = std::unordered_map<K, typename ValueList::iterator>;
78 template<
typename PROXIED,
typename TYPE>
81 ValueList myValueList;
82 KeyIteratorMap myKeyMap;
92 template<
typename PROXIED,
typename TYPE>
95 using proxied_iterator = PROXIED;
108 other.myLock->readLock();
110 myLock = other.myLock;
115 myIt = std::move(other.myIt);
116 other.myIt = proxied_iterator();
117 myLock = other.myLock;
118 other.myLock =
nullptr;
123 other.myLock->readLock();
125 myLock = other.myLock;
131 myIt = std::move(other.myIt);
132 other.myIt = proxied_iterator();
133 myLock = other.myLock;
134 other.myLock =
nullptr;
142 myLock->readUnlock();
153 return myIt == other.myIt;
157 return myIt != other.myIt;
164 myIt(it), myLock(lock) { }
167 proxied_iterator myIt;
173 using iterator = iterator_base<typename ValueList::iterator, std::pair<const K, V>>;
176 using const_iterator = iterator_base<typename ValueList::const_iterator, const std::pair<const K, V>>;
186 mySizeFunc(SizeFunc),
187 myInUseFunc(InUseFunc),
199 if (max_size >= myMaxSize)
201 myMaxSize = max_size;
205 myMaxSize = max_size;
212 myLock->writeUnlock();
229 myLock->readUnlock();
242 myLock->readUnlock();
253 bool found = (myKeyMap.find(key) != myKeyMap.end());
256 myLock->readUnlock();
271 auto itK = myKeyMap.find(key);
272 if (itK == myKeyMap.end())
275 myLock->readUnlock();
276 return iterator(myValueList.end(),
nullptr);
280 if (itK->second != myValueList.begin())
282 myValueList.splice(myValueList.begin(), myValueList,
284 itK->second = myValueList.begin();
287 return iterator(itK->second, myLock);
296 std::pair<iterator, bool>
308 std::pair<iterator, bool>
result;
309 auto itK = myKeyMap.find(key);
310 if (itK != myKeyMap.end() && !evict)
318 result = std::make_pair(
iterator(itK->second, myLock),
false);
322 if (itK != myKeyMap.end())
326 myCurrentSize -= mySizeFunc((itK->second)->second);
327 myCurrentSize += mySizeFunc(
value);
334 myValueList.splice(myValueList.begin(), myValueList,
337 myValueList.begin()->second = std::move(
value);
338 itK->second = myValueList.begin();
340 result = std::make_pair(
iterator(itK->second, myLock),
true);
344 myCurrentSize += mySizeFunc(
value);
348 myValueList.push_front(std::make_pair(key, std::move(
value)));
349 myKeyMap.insert(std::make_pair(key, myValueList.begin()));
351 result = std::make_pair(
iterator(myValueList.begin(), myLock),
357 myLock->writeUnlock();
367 bool updated =
false;
371 auto itK = myKeyMap.find(key);
372 if (itK != myKeyMap.end())
374 myCurrentSize -= mySizeFunc((itK->second)->second);
375 myValueList.erase(itK->second);
381 myLock->writeUnlock();
391 bool updated =
false;
395 auto itK = myKeyMap.find(key);
396 if (itK != myKeyMap.end())
398 myCurrentSize -= mySizeFunc((itK->second)->second);
401 value = std::move((itK->second)->second);
403 myValueList.erase(itK->second);
409 myLock->writeUnlock();
417 if (myLock) myLock->writeLock();
423 if (myLock) myLock->writeUnlock();
429 if (myLock) myLock->readLock();
430 return iterator(myValueList.begin(), myLock);
437 return iterator(myValueList.end(),
nullptr);
443 if (myLock) myLock->readLock();
458 void prune(
typename ValueList::iterator *itSkipV =
nullptr)
460 for (
auto ritV = myValueList.rbegin();
461 myCurrentSize > myMaxSize && ritV != myValueList.rend(); ++ritV)
463 if ((itSkipV && ritV.base() == *itSkipV) ||
464 myInUseFunc(ritV->second))
469 myCurrentSize -= mySizeFunc(ritV->second);
471 auto itK = myKeyMap.find(ritV->first);
475 auto itV = myValueList.erase(std::prev(ritV.base()));
476 ritV =
typename ValueList::reverse_iterator(itV);
iterator_base(proxied_iterator it, L *lock)
std::pair< iterator, bool > insert(const K &key, V &&value, bool evict=false)
bool steal(const K &key, V &&value)
GLsizei const GLfloat * value
iterator find(const K &key)
bool UTlruGetItemInUse(const V &)
**But if you need a result
bool operator!=(const iterator_base &other) const
iterator_base< typename ValueList::iterator, std::pair< const cl_mem, ut_clBuffer >> iterator
A iterator pointing to mutable values.
iterator_base< typename ValueList::const_iterator, const std::pair< const cl_mem, ut_clBuffer >> const_iterator
A const iterator pointing to immutable values.
exint currentSize() const
iterator begin()
Returns an iterator to the front-most item in the LRU cache.
iterator_base & operator=(iterator_base &&other)
exint UTlruGetItemSize(const V &)
iterator_base(iterator_base &&other)
bool operator==(const iterator_base &other) const
iterator end()
Returns an iterator to the end of the LRU list.
pointer operator->() const
std::function< T > UT_Function
exint maxSize() const
Returns the current maximum size of the cache.
UT_LRUCache(exint max_size=SYS_EXINT_MAX)
void setMaxSize(exint max_size)
bool contains(const K &key) const
const_iterator begin() const
Returns a const iterator to the front-most item in the LRU cache.
const_iterator end() const
Returns a const iterator to the end of the LRU list.
exint count() const
Returns the number of items in the cache.
iterator_base(const iterator_base &other)
iterator_base & operator=(const iterator_base &other)
std::bidirectional_iterator_tag iterator_category
reference operator*() const
friend class iterator_base
iterator_base & operator++()
void clear()
Clears the cache completely.
iterator_base & operator--()
std::ptrdiff_t difference_type