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     5090586 :     void lock()
      52             :     {
      53     5090586 :     }
      54             : 
      55     5090586 :     void unlock()
      56             :     {
      57     5090586 :     }
      58             : 
      59             :     bool try_lock()
      60             :     {
      61             :         return true;
      62             :     }
      63             : };
      64             : 
      65             : /**
      66             :  * error raised when a key not in cache is passed to get()
      67             :  */
      68             : class KeyNotFound : public std::invalid_argument
      69             : {
      70             :   public:
      71           1 :     KeyNotFound() : std::invalid_argument("key_not_found")
      72             :     {
      73           1 :     }
      74             : };
      75             : 
      76             : template <typename K, typename V> struct KeyValuePair
      77             : {
      78             :   public:
      79             :     K key;
      80             :     V value;
      81             : 
      82        1783 :     KeyValuePair(const K &k, const V &v) : key(k), value(v)
      83             :     {
      84        1783 :     }
      85             : 
      86       13980 :     KeyValuePair(const K &k, V &&v) : key(k), value(std::move(v))
      87             :     {
      88       13980 :     }
      89             : };
      90             : 
      91             : /**
      92             :  *  The LRU Cache class templated by
      93             :  *    Key - key type
      94             :  *    Value - value type
      95             :  *    MapType - an associative container like std::unordered_map
      96             :  *    LockType - a lock type derived from the Lock class (default:
      97             :  *NullLock = no synchronization)
      98             :  *
      99             :  *  The default NullLock based template is not thread-safe, however passing
     100             :  *Lock=std::mutex will make it
     101             :  *  thread-safe
     102             :  */
     103             : template <class Key, class Value, class Lock = NullLock,
     104             :           class Map = std::unordered_map<
     105             :               Key, typename std::list<KeyValuePair<Key, Value>>::iterator>>
     106             : class Cache
     107             : {
     108             :   public:
     109             :     typedef KeyValuePair<Key, Value> node_type;
     110             :     typedef std::list<KeyValuePair<Key, Value>> list_type;
     111             :     typedef Map map_type;
     112             :     typedef Lock lock_type;
     113             :     using Guard = std::lock_guard<lock_type>;
     114             : 
     115             :     /**
     116             :      * the max size is the hard limit of keys and (maxSize + elasticity) is the
     117             :      * soft limit
     118             :      * the cache is allowed to grow till maxSize + elasticity and is pruned back
     119             :      * to maxSize keys
     120             :      * set maxSize = 0 for an unbounded cache (but in that case, you're better
     121             :      * off using a std::unordered_map directly anyway! :)
     122             :      */
     123       63142 :     explicit Cache(size_t maxSize = 64, size_t elasticity = 10)
     124       63142 :         : maxSize_(maxSize), elasticity_(elasticity)
     125             :     {
     126       63122 :     }
     127             : 
     128       61759 :     virtual ~Cache() = default;
     129             : 
     130         769 :     size_t size() const
     131             :     {
     132        1538 :         Guard g(lock_);
     133         769 :         return cache_.size();
     134             :     }
     135             : 
     136        3366 :     bool empty() const
     137             :     {
     138        6732 :         Guard g(lock_);
     139        3366 :         return cache_.empty();
     140             :     }
     141             : 
     142       47390 :     void clear()
     143             :     {
     144       94780 :         Guard g(lock_);
     145       47390 :         cache_.clear();
     146       47390 :         keys_.clear();
     147       47390 :     }
     148             : 
     149        2501 :     void insert(const Key &k, const Value &v)
     150             :     {
     151        2501 :         Guard g(lock_);
     152        2501 :         const auto iter = cache_.find(k);
     153        2501 :         if (iter != cache_.end())
     154             :         {
     155         718 :             iter->second->value = v;
     156         718 :             keys_.splice(keys_.begin(), keys_, iter->second);
     157         718 :             return;
     158             :         }
     159             : 
     160        1783 :         keys_.emplace_front(k, v);
     161        1783 :         cache_[k] = keys_.begin();
     162        1783 :         prune();
     163             :     }
     164             : 
     165       14591 :     Value &insert(const Key &k, Value &&v)
     166             :     {
     167       29182 :         Guard g(lock_);
     168       14591 :         const auto iter = cache_.find(k);
     169       14591 :         if (iter != cache_.end())
     170             :         {
     171         611 :             iter->second->value = std::move(v);
     172         611 :             keys_.splice(keys_.begin(), keys_, iter->second);
     173         611 :             return keys_.front().value;
     174             :         }
     175             : 
     176       13980 :         keys_.emplace_front(k, std::move(v));
     177       13980 :         cache_[k] = keys_.begin();
     178       13980 :         prune();
     179       13980 :         return keys_.front().value;
     180             :     }
     181             : 
     182     4796856 :     bool tryGet(const Key &kIn, Value &vOut)
     183             :     {
     184     9593712 :         Guard g(lock_);
     185     4796856 :         const auto iter = cache_.find(kIn);
     186     4796856 :         if (iter == cache_.end())
     187             :         {
     188     4341589 :             return false;
     189             :         }
     190      455263 :         keys_.splice(keys_.begin(), keys_, iter->second);
     191      455263 :         vOut = iter->second->value;
     192      455263 :         return true;
     193             :     }
     194             : 
     195             :     /**
     196             :      *  The const reference returned here is only
     197             :      *    guaranteed to be valid till the next insert/delete
     198             :      */
     199           4 :     const Value &get(const Key &k)
     200             :     {
     201           5 :         Guard g(lock_);
     202           4 :         const auto iter = cache_.find(k);
     203           4 :         if (iter == cache_.end())
     204             :         {
     205           1 :             throw KeyNotFound();
     206             :         }
     207           3 :         keys_.splice(keys_.begin(), keys_, iter->second);
     208           6 :         return iter->second->value;
     209             :     }
     210             : 
     211      190180 :     Value *getPtr(const Key &k)
     212             :     {
     213      380360 :         Guard g(lock_);
     214      190180 :         const auto iter = cache_.find(k);
     215      190180 :         if (iter == cache_.end())
     216             :         {
     217       11839 :             return nullptr;
     218             :         }
     219      178341 :         keys_.splice(keys_.begin(), keys_, iter->second);
     220      178341 :         return &(iter->second->value);
     221             :     }
     222             : 
     223             :     /**
     224             :      * returns a copy of the stored object (if found)
     225             :      */
     226           1 :     Value getCopy(const Key &k)
     227             :     {
     228           1 :         return get(k);
     229             :     }
     230             : 
     231        2405 :     bool remove(const Key &k)
     232             :     {
     233        4810 :         Guard g(lock_);
     234        2405 :         auto iter = cache_.find(k);
     235        2405 :         if (iter == cache_.end())
     236             :         {
     237         116 :             return false;
     238             :         }
     239        2289 :         keys_.erase(iter->second);
     240        2289 :         cache_.erase(iter);
     241        2289 :         return true;
     242             :     }
     243             : 
     244       13219 :     bool contains(const Key &k)
     245             :     {
     246       13219 :         Guard g(lock_);
     247       26438 :         return cache_.find(k) != cache_.end();
     248             :     }
     249             : 
     250           0 :     bool getOldestEntry(Key &kOut, Value &vOut)
     251             :     {
     252           0 :         Guard g(lock_);
     253           0 :         if (keys_.empty())
     254             :         {
     255           0 :             return false;
     256             :         }
     257           0 :         kOut = keys_.back().key;
     258           0 :         vOut = keys_.back().value;
     259           0 :         return true;
     260             :     }
     261             : 
     262         137 :     bool removeAndRecycleOldestEntry(Value &vOut)
     263             :     {
     264         274 :         Guard g(lock_);
     265         137 :         if (keys_.empty())
     266             :         {
     267           1 :             return false;
     268             :         }
     269         136 :         vOut = std::move(keys_.back().value);
     270         136 :         cache_.erase(keys_.back().key);
     271         136 :         keys_.pop_back();
     272         136 :         return true;
     273             :     }
     274             : 
     275         645 :     size_t getMaxSize() const
     276             :     {
     277         645 :         return maxSize_;
     278             :     }
     279             : 
     280           1 :     size_t getElasticity() const
     281             :     {
     282           1 :         return elasticity_;
     283             :     }
     284             : 
     285         120 :     size_t getMaxAllowedSize() const
     286             :     {
     287         120 :         return maxSize_ + elasticity_;
     288             :     }
     289             : 
     290       19173 :     template <typename F> void cwalk(F &f) const
     291             :     {
     292       38134 :         Guard g(lock_);
     293       19173 :         std::for_each(keys_.begin(), keys_.end(), f);
     294       19173 :     }
     295             : 
     296             :     Cache(Cache &&other)
     297             :         : cache_(std::move(other.cache_)), keys_(std::move(other.keys_)),
     298             :           maxSize_(other.maxSize_), elasticity_(other.elasticity_)
     299             :     {
     300             :     }
     301             : 
     302             :   protected:
     303       15763 :     size_t prune()
     304             :     {
     305       15763 :         size_t maxAllowed = maxSize_ + elasticity_;
     306       15763 :         if (maxSize_ == 0 || cache_.size() <= maxAllowed)
     307             :         { /* ERO: changed < to <= */
     308       15051 :             return 0;
     309             :         }
     310         712 :         size_t count = 0;
     311        7635 :         while (cache_.size() > maxSize_)
     312             :         {
     313        6923 :             cache_.erase(keys_.back().key);
     314        6923 :             keys_.pop_back();
     315        6923 :             ++count;
     316             :         }
     317         712 :         return count;
     318             :     }
     319             : 
     320             :   private:
     321             :     // Disallow copying.
     322             :     Cache(const Cache &) = delete;
     323             :     Cache &operator=(const Cache &) = delete;
     324             : 
     325             :     mutable Lock lock_{};
     326             :     Map cache_{};
     327             :     list_type keys_{};
     328             :     size_t maxSize_;
     329             :     size_t elasticity_;
     330             : };
     331             : 
     332             : }  // namespace lru11
     333             : 
     334             : /*! @endcond */