summaryrefslogtreecommitdiffstats
path: root/src/cache.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/cache.h')
-rw-r--r--src/cache.h162
1 files changed, 162 insertions, 0 deletions
diff --git a/src/cache.h b/src/cache.h
new file mode 100644
index 0000000..5f7c834
--- /dev/null
+++ b/src/cache.h
@@ -0,0 +1,162 @@
+/*****************************************************************************
+ *
+ * Copyright (C) 1997-2020 by Dimitri van Heesch.
+ *
+ * Permission to use, copy, modify, and distribute this software and its
+ * documentation under the terms of the GNU General Public License is hereby
+ * granted. No representations are made about the suitability of this software
+ * for any purpose. It is provided "as is" without express or implied warranty.
+ * See the GNU General Public License for more details.
+ *
+ * Documents produced by Doxygen are derivative works derived from the
+ * input used in their production; they are not affected by this license.
+ *
+ */
+
+#ifndef CACHE_H
+#define CACHE_H
+
+#include <list>
+#include <unordered_map>
+#include <mutex>
+#include <ctype.h>
+
+/*! Fixed size cache for value type V using keys of type K.
+ *
+ * When the maximum capacity has reached, the least recently used value is removed from the cache
+ * (LRU strategy).
+ */
+template<typename K,typename V>
+class Cache
+{
+ public:
+ using kv_pair = std::pair<K,V>;
+ using iterator = typename std::list<kv_pair>::iterator;
+ using const_iterator = typename std::list<kv_pair>::const_iterator;
+
+ //! creates a cache that can hold \a capacity elements
+ Cache(size_t capacity) : m_capacity(capacity)
+ {
+ }
+
+ //! Inserts \a value under \a key in the cache
+ V *insert(const K &key,V &&value)
+ {
+ // remove item if it already exists
+ remove(key);
+ // store new item
+ m_cacheItemList.push_front(kv_pair(key,std::move(value)));
+ V *result = &m_cacheItemList.front().second;
+ m_cacheItemMap[key] = m_cacheItemList.begin();
+ // remove least recently used item if cache is full
+ resize();
+ return result;
+ }
+
+ //! Inserts \a value under \a key in the cache
+ V *insert(const K &key,const V &value)
+ {
+ // remove item if it already exists
+ remove(key);
+ // store new item
+ m_cacheItemList.push_front(kv_pair(key,value));
+ V *result = &m_cacheItemList.front().second;
+ m_cacheItemMap[key] = m_cacheItemList.begin();
+ // remove least recently used item if cache is full
+ resize();
+ return result;
+ }
+
+ //! Removes entry \a key from the cache.
+ //! \note this invalidates any iterators
+ void remove(const K &key)
+ {
+ // remove item if it already exists
+ auto it = m_cacheItemMap.find(key);
+ if (it != m_cacheItemMap.end())
+ {
+ m_cacheItemList.erase(it->second);
+ m_cacheItemMap.erase(it);
+ }
+ }
+
+ //! Finds a value in the cache given the corresponding \a key.
+ //! @returns a pointer to the value or nullptr if the key is not found in the cache
+ //! @note The hit and miss counters are updated, see hits() and misses().
+ V *find(const K &key)
+ {
+ auto it = m_cacheItemMap.find(key);
+ if (it != m_cacheItemMap.end())
+ {
+ // move the item to the front of the list
+ m_cacheItemList.splice(m_cacheItemList.begin(),
+ m_cacheItemList,
+ it->second);
+ m_hits++;
+ // return the value
+ return &it->second->second;
+ }
+ else
+ {
+ m_misses++;
+ }
+ return nullptr;
+ }
+
+ //! Returns the number of values stored in the cache.
+ size_t size() const
+ {
+ return m_cacheItemMap.size();
+ }
+
+ //! Returns the maximum number of values that can be stored in the cache.
+ size_t capacity() const
+ {
+ return m_capacity;
+ }
+
+ //! Returns how many of the find() calls did find a value in the cache.
+ uint64_t hits() const
+ {
+ return m_hits;
+ }
+
+ //! Returns how many of the find() calls did not found a value in the cache.
+ uint64_t misses() const
+ {
+ return m_misses;
+ }
+
+ //! Clears all values in the cache.
+ void clear()
+ {
+ m_cacheItemMap.clear();
+ m_cacheItemList.clear();
+ }
+
+ iterator begin() { return m_cacheItemList.begin(); }
+ iterator end() { return m_cacheItemList.end(); }
+ const_iterator begin() const { return m_cacheItemList.cbegin(); }
+ const_iterator end() const { return m_cacheItemList.cend(); }
+
+ private:
+ void resize()
+ {
+ if (m_cacheItemMap.size() > m_capacity)
+ {
+ auto last_it = m_cacheItemList.end();
+ --last_it;
+ m_cacheItemMap.erase(last_it->first);
+ m_cacheItemList.pop_back();
+ }
+ }
+ size_t m_capacity;
+ // list of items in the cache, sorted by most to least recently used.
+ std::list<kv_pair> m_cacheItemList;
+ // mapping for each key to a place in the list where item is found
+ std::unordered_map<K,iterator> m_cacheItemMap;
+ uint64_t m_hits=0;
+ uint64_t m_misses=0;
+};
+
+#endif