Line data    Source code

       1             : /*
       2             :  * LRUCache11 - a templated C++11 based LRU cache class that allows
       3             :  * specification of
       4             :  * key, value and optionally the map container type (defaults to
       5             :  * std::unordered_map)
       6             :  * By using the std::map and a linked list of keys it allows O(1) insert, delete
       7             :  * and
       8             :  * refresh operations.
       9             :  *
      10             :  * This is a header-only library and all you need is the LRUCache11.hpp file
      11             :  *
      12             :  * Github: https://github.com/mohaps/lrucache11
      13             :  *
      14             :  * This is a follow-up to the LRUCache project -
      15             :  * https://github.com/mohaps/lrucache
      16             :  *
      17             :  * Copyright (c) 2012-22 SAURAV MOHAPATRA <mohaps@gmail.com>
      18             :  *
      19             :  * Permission to use, copy, modify, and distribute this software for any
      20             :  * purpose with or without fee is hereby granted, provided that the above
      21             :  * copyright notice and this permission notice appear in all copies.
      22             :  *
      23             :  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
      24             :  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
      25             :  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
      26             :  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
      27             :  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
      28             :  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
      29             :  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
      30             :  */
      31             : 
      32             : /*! @cond Doxygen_Suppress */
      33             : 
      34             : #pragma once
      35             : #include <algorithm>
      36             : #include <cstdint>
      37             : #include <list>
      38             : #include <mutex>
      39             : #include <stdexcept>
      40             : #include <thread>
      41             : #include <unordered_map>
      42             : 
      43             : namespace lru11
      44             : {
      45             : /*
      46             :  * a noop lockable concept that can be used in place of std::mutex
      47             :  */
      48             : class NullLock
      49             : {
      50             :   public:
      51     5913366 :     void lock()
      52             :     {
      53     5913366 :     }
      54             : 
      55     5914836 :     void unlock()
      56             :     {
      57     5914836 :     }
      58             : 
      59             :     bool try_lock()
      60             :     {
      61             :         return true;
      62             :     }
      63             : };
      64             : 
      65             : #if defined(__clang__)
      66             : #pragma clang diagnostic push
      67             : #pragma clang diagnostic ignored "-Wweak-vtables"
      68             : #endif
      69             : 
      70             : /**
      71             :  * error raised when a key not in cache is passed to get()
      72             :  */
      73             : class KeyNotFound : public std::invalid_argument
      74             : {
      75             :   public:
      76           1 :     KeyNotFound() : std::invalid_argument("key_not_found")
      77             :     {
      78           1 :     }
      79             : };
      80             : 
      81             : #if defined(__clang__)
      82             : #pragma clang diagnostic pop
      83             : #endif
      84             : 
      85             : template <typename K, typename V> struct KeyValuePair
      86             : {
      87             :   public:
      88             :     K key;
      89             :     V value;
      90             : 
      91        5016 :     KeyValuePair(const K &k, const V &v) : key(k), value(v)
      92             :     {
      93        4986 :     }
      94             : 
      95       16801 :     KeyValuePair(const K &k, V &&v) : key(k), value(std::move(v))
      96             :     {
      97       16801 :     }
      98             : 
      99             :   private:
     100             :     KeyValuePair(const KeyValuePair &) = delete;
     101             :     KeyValuePair &operator=(const KeyValuePair &) = delete;
     102             : };
     103             : 
     104             : /**
     105             :  *  The LRU Cache class templated by
     106             :  *    Key - key type
     107             :  *    Value - value type
     108             :  *    MapType - an associative container like std::unordered_map
     109             :  *    LockType - a lock type derived from the Lock class (default:
     110             :  *NullLock = no synchronization)
     111             :  *
     112             :  *  The default NullLock based template is not thread-safe, however passing
     113             :  *Lock=std::mutex will make it
     114             :  *  thread-safe
     115             :  */
     116             : template <class Key, class Value, class Lock = NullLock,
     117             :           class Map = std::unordered_map<
     118             :               Key, typename std::list<KeyValuePair<Key, Value>>::iterator>>
     119             : class Cache
     120             : {
     121             :   public:
     122             :     typedef KeyValuePair<Key, Value> node_type;
     123             :     typedef std::list<KeyValuePair<Key, Value>> list_type;
     124             :     typedef Map map_type;
     125             :     typedef Lock lock_type;
     126             :     using Guard = std::lock_guard<lock_type>;
     127             : 
     128             :     /**
     129             :      * the max size is the hard limit of keys and (maxSize + elasticity) is the
     130             :      * soft limit
     131             :      * the cache is allowed to grow till maxSize + elasticity and is pruned back
     132             :      * to maxSize keys
     133             :      * set maxSize = 0 for an unbounded cache (but in that case, you're better
     134             :      * off using a std::unordered_map directly anyway! :)
     135             :      */
     136       91087 :     explicit Cache(size_t maxSize = 64, size_t elasticity = 10)
     137       91087 :         : maxSize_(maxSize), elasticity_(elasticity)
     138             :     {
     139       90917 :     }
     140             : 
     141       86990 :     virtual ~Cache() = default;
     142             : 
     143         820 :     size_t size() const
     144             :     {
     145        1640 :         Guard g(lock_);
     146         820 :         return cache_.size();
     147             :     }
     148             : 
     149        4253 :     bool empty() const
     150             :     {
     151        8506 :         Guard g(lock_);
     152        4253 :         return cache_.empty();
     153             :     }
     154             : 
     155       63009 :     void clear()
     156             :     {
     157      126018 :         Guard g(lock_);
     158       63009 :         cache_.clear();
     159       63009 :         keys_.clear();
     160       63009 :     }
     161             : 
     162        6841 :     void insert(const Key &k, const Value &v)
     163             :     {
     164        6841 :         Guard g(lock_);
     165        6705 :         const auto iter = cache_.find(k);
     166        6777 :         if (iter != cache_.end())
     167             :         {
     168        1764 :             iter->second->value = v;
     169        1769 :             keys_.splice(keys_.begin(), keys_, iter->second);
     170        1771 :             return;
     171             :         }
     172             : 
     173        5011 :         keys_.emplace_front(k, v);
     174        5020 :         cache_[k] = keys_.begin();
     175        4950 :         prune();
     176             :     }
     177             : 
     178       17484 :     Value &insert(const Key &k, Value &&v)
     179             :     {
     180       34968 :         Guard g(lock_);
     181       17484 :         const auto iter = cache_.find(k);
     182       17485 :         if (iter != cache_.end())
     183             :         {
     184         683 :             iter->second->value = std::move(v);
     185         683 :             keys_.splice(keys_.begin(), keys_, iter->second);
     186         683 :             return keys_.front().value;
     187             :         }
     188             : 
     189       16802 :         keys_.emplace_front(k, std::move(v));
     190       16799 :         cache_[k] = keys_.begin();
     191       16801 :         prune();
     192       16801 :         return keys_.front().value;
     193             :     }
     194             : 
     195     5585207 :     bool tryGet(const Key &kIn, Value &vOut)
     196             :     {
     197    11169912 :         Guard g(lock_);
     198     5581850 :         const auto iter = cache_.find(kIn);
     199     5584883 :         if (iter == cache_.end())
     200             :         {
     201     4430734 :             return false;
     202             :         }
     203     1151310 :         keys_.splice(keys_.begin(), keys_, iter->second);
     204     1152643 :         vOut = iter->second->value;
     205     1153964 :         return true;
     206             :     }
     207             : 
     208             :     /**
     209             :      *  The const reference returned here is only
     210             :      *    guaranteed to be valid till the next insert/delete
     211             :      */
     212           4 :     const Value &get(const Key &k)
     213             :     {
     214           5 :         Guard g(lock_);
     215           4 :         const auto iter = cache_.find(k);
     216           4 :         if (iter == cache_.end())
     217             :         {
     218           1 :             throw KeyNotFound();
     219             :         }
     220           3 :         keys_.splice(keys_.begin(), keys_, iter->second);
     221           6 :         return iter->second->value;
     222             :     }
     223             : 
     224      194168 :     Value *getPtr(const Key &k)
     225             :     {
     226      388337 :         Guard g(lock_);
     227      194168 :         const auto iter = cache_.find(k);
     228      194169 :         if (iter == cache_.end())
     229             :         {
     230       14321 :             return nullptr;
     231             :         }
     232      179848 :         keys_.splice(keys_.begin(), keys_, iter->second);
     233      179848 :         return &(iter->second->value);
     234             :     }
     235             : 
     236             :     /**
     237             :      * returns a copy of the stored object (if found)
     238             :      */
     239           1 :     Value getCopy(const Key &k)
     240             :     {
     241           1 :         return get(k);
     242             :     }
     243             : 
     244        3015 :     bool remove(const Key &k)
     245             :     {
     246        6030 :         Guard g(lock_);
     247        3015 :         auto iter = cache_.find(k);
     248        3015 :         if (iter == cache_.end())
     249             :         {
     250         105 :             return false;
     251             :         }
     252        2910 :         keys_.erase(iter->second);
     253        2910 :         cache_.erase(iter);
     254        2910 :         return true;
     255             :     }
     256             : 
     257       16451 :     bool contains(const Key &k)
     258             :     {
     259       16451 :         Guard g(lock_);
     260       32902 :         return cache_.find(k) != cache_.end();
     261             :     }
     262             : 
     263           0 :     bool getOldestEntry(Key &kOut, Value &vOut)
     264             :     {
     265           0 :         Guard g(lock_);
     266           0 :         if (keys_.empty())
     267             :         {
     268           0 :             return false;
     269             :         }
     270           0 :         kOut = keys_.back().key;
     271           0 :         vOut = keys_.back().value;
     272           0 :         return true;
     273             :     }
     274             : 
     275         137 :     bool removeAndRecycleOldestEntry(Value &vOut)
     276             :     {
     277         274 :         Guard g(lock_);
     278         137 :         if (keys_.empty())
     279             :         {
     280           1 :             return false;
     281             :         }
     282         136 :         vOut = std::move(keys_.back().value);
     283         136 :         cache_.erase(keys_.back().key);
     284         136 :         keys_.pop_back();
     285         136 :         return true;
     286             :     }
     287             : 
     288         653 :     size_t getMaxSize() const
     289             :     {
     290         653 :         return maxSize_;
     291             :     }
     292             : 
     293           1 :     size_t getElasticity() const
     294             :     {
     295           1 :         return elasticity_;
     296             :     }
     297             : 
     298         163 :     size_t getMaxAllowedSize() const
     299             :     {
     300         163 :         return maxSize_ + elasticity_;
     301             :     }
     302             : 
     303       25123 :     template <typename F> void cwalk(F &f) const
     304             :     {
     305       49980 :         Guard g(lock_);
     306       25123 :         std::for_each(keys_.begin(), keys_.end(), f);
     307       25123 :     }
     308             : 
     309             :     Cache(Cache &&other)
     310             :         : cache_(std::move(other.cache_)), keys_(std::move(other.keys_)),
     311             :           maxSize_(other.maxSize_), elasticity_(other.elasticity_)
     312             :     {
     313             :     }
     314             : 
     315             :   protected:
     316       21840 :     size_t prune()
     317             :     {
     318       21840 :         size_t maxAllowed = maxSize_ + elasticity_;
     319       21840 :         if (maxSize_ == 0 || cache_.size() <= maxAllowed)
     320             :         { /* ERO: changed < to <= */
     321       20470 :             return 0;
     322             :         }
     323        1367 :         size_t count = 0;
     324       10584 :         while (cache_.size() > maxSize_)
     325             :         {
     326        9211 :             cache_.erase(keys_.back().key);
     327        9217 :             keys_.pop_back();
     328        9217 :             ++count;
     329             :         }
     330        1278 :         return count;
     331             :     }
     332             : 
     333             :   private:
     334             :     // Disallow copying.
     335             :     Cache(const Cache &) = delete;
     336             :     Cache &operator=(const Cache &) = delete;
     337             : 
     338             :     mutable Lock lock_{};
     339             :     Map cache_{};
     340             :     list_type keys_{};
     341             :     size_t maxSize_;
     342             :     size_t elasticity_;
     343             : };
     344             : 
     345             : }  // namespace lru11
     346             : 
     347             : /*! @endcond */