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 <unordered_map>
      41             : 
      42             : namespace lru11
      43             : {
      44             : /*
      45             :  * a noop lockable concept that can be used in place of std::mutex
      46             :  */
      47             : class NullLock
      48             : {
      49             :   public:
      50     5934716 :     void lock()
      51             :     {
      52     5934716 :     }
      53             : 
      54     5935816 :     void unlock()
      55             :     {
      56     5935816 :     }
      57             : 
      58             :     bool try_lock()
      59             :     {
      60             :         return true;
      61             :     }
      62             : };
      63             : 
      64             : #if defined(__clang__)
      65             : #pragma clang diagnostic push
      66             : #pragma clang diagnostic ignored "-Wweak-vtables"
      67             : #endif
      68             : 
      69             : /**
      70             :  * error raised when a key not in cache is passed to get()
      71             :  */
      72             : class KeyNotFound : public std::invalid_argument
      73             : {
      74             :   public:
      75           1 :     KeyNotFound() : std::invalid_argument("key_not_found")
      76             :     {
      77           1 :     }
      78             : };
      79             : 
      80             : #if defined(__clang__)
      81             : #pragma clang diagnostic pop
      82             : #endif
      83             : 
      84             : template <typename K, typename V> struct KeyValuePair
      85             : {
      86             :   public:
      87             :     K key;
      88             :     V value;
      89             : 
      90        6279 :     KeyValuePair(const K &k, const V &v) : key(k), value(v)
      91             :     {
      92        6275 :     }
      93             : 
      94       17723 :     KeyValuePair(const K &k, V &&v) : key(k), value(std::move(v))
      95             :     {
      96       17722 :     }
      97             : 
      98             :   private:
      99             :     KeyValuePair(const KeyValuePair &) = delete;
     100             :     KeyValuePair &operator=(const KeyValuePair &) = delete;
     101             : };
     102             : 
     103             : /**
     104             :  *  The LRU Cache class templated by
     105             :  *    Key - key type
     106             :  *    Value - value type
     107             :  *    MapType - an associative container like std::unordered_map
     108             :  *    LockType - a lock type derived from the Lock class (default:
     109             :  *NullLock = no synchronization)
     110             :  *
     111             :  *  The default NullLock based template is not thread-safe, however passing
     112             :  *Lock=std::mutex will make it
     113             :  *  thread-safe
     114             :  */
     115             : template <class Key, class Value, class Lock = NullLock,
     116             :           class Map = std::unordered_map<
     117             :               Key, typename std::list<KeyValuePair<Key, Value>>::iterator>>
     118             : class Cache final
     119             : {
     120             :   public:
     121             :     typedef KeyValuePair<Key, Value> node_type;
     122             :     typedef std::list<KeyValuePair<Key, Value>> list_type;
     123             :     typedef Map map_type;
     124             :     typedef Lock lock_type;
     125             :     using Guard = std::lock_guard<lock_type>;
     126             : 
     127             :     /**
     128             :      * the max size is the hard limit of keys and (maxSize + elasticity) is the
     129             :      * soft limit
     130             :      * the cache is allowed to grow till maxSize + elasticity and is pruned back
     131             :      * to maxSize keys
     132             :      * set maxSize = 0 for an unbounded cache (but in that case, you're better
     133             :      * off using a std::unordered_map directly anyway! :)
     134             :      */
     135       97328 :     explicit Cache(size_t maxSize = 64, size_t elasticity = 10)
     136       97328 :         : maxSize_(maxSize), elasticity_(elasticity)
     137             :     {
     138       97318 :     }
     139             : 
     140       81187 :     ~Cache() = default;
     141             : 
     142         822 :     size_t size() const
     143             :     {
     144        1644 :         Guard g(lock_);
     145         822 :         return cache_.size();
     146             :     }
     147             : 
     148        4722 :     bool empty() const
     149             :     {
     150        9444 :         Guard g(lock_);
     151        4722 :         return cache_.empty();
     152             :     }
     153             : 
     154       64403 :     void clear()
     155             :     {
     156      128805 :         Guard g(lock_);
     157       64403 :         cache_.clear();
     158       64402 :         keys_.clear();
     159       64402 :     }
     160             : 
     161        7996 :     void insert(const Key &k, const Value &v)
     162             :     {
     163        7996 :         Guard g(lock_);
     164        7989 :         const auto iter = cache_.find(k);
     165        7991 :         if (iter != cache_.end())
     166             :         {
     167        1713 :             iter->second->value = v;
     168        1713 :             keys_.splice(keys_.begin(), keys_, iter->second);
     169        1713 :             return;
     170             :         }
     171             : 
     172        6280 :         keys_.emplace_front(k, v);
     173        6278 :         cache_[k] = keys_.begin();
     174        6279 :         prune();
     175             :     }
     176             : 
     177       18350 :     Value &insert(const Key &k, Value &&v)
     178             :     {
     179       36701 :         Guard g(lock_);
     180       18351 :         const auto iter = cache_.find(k);
     181       18350 :         if (iter != cache_.end())
     182             :         {
     183         628 :             iter->second->value = std::move(v);
     184         628 :             keys_.splice(keys_.begin(), keys_, iter->second);
     185         628 :             return keys_.front().value;
     186             :         }
     187             : 
     188       17723 :         keys_.emplace_front(k, std::move(v));
     189       17723 :         cache_[k] = keys_.begin();
     190       17722 :         prune();
     191       17722 :         return keys_.front().value;
     192             :     }
     193             : 
     194     5599276 :     bool tryGet(const Key &kIn, Value &vOut)
     195             :     {
     196    11194955 :         Guard g(lock_);
     197     5591136 :         const auto iter = cache_.find(kIn);
     198     5599208 :         if (iter == cache_.end())
     199             :         {
     200     4443994 :             return false;
     201             :         }
     202     1148032 :         keys_.splice(keys_.begin(), keys_, iter->second);
     203     1150825 :         vOut = iter->second->value;
     204     1151692 :         return true;
     205             :     }
     206             : 
     207             :     /**
     208             :      *  The const reference returned here is only
     209             :      *    guaranteed to be valid till the next insert/delete
     210             :      */
     211           4 :     const Value &get(const Key &k)
     212             :     {
     213           5 :         Guard g(lock_);
     214           4 :         const auto iter = cache_.find(k);
     215           4 :         if (iter == cache_.end())
     216             :         {
     217           1 :             throw KeyNotFound();
     218             :         }
     219           3 :         keys_.splice(keys_.begin(), keys_, iter->second);
     220           6 :         return iter->second->value;
     221             :     }
     222             : 
     223      198420 :     Value *getPtr(const Key &k)
     224             :     {
     225      396836 :         Guard g(lock_);
     226      198420 :         const auto iter = cache_.find(k);
     227      198418 :         if (iter == cache_.end())
     228             :         {
     229       15300 :             return nullptr;
     230             :         }
     231      183116 :         keys_.splice(keys_.begin(), keys_, iter->second);
     232      183117 :         return &(iter->second->value);
     233             :     }
     234             : 
     235             :     /**
     236             :      * returns a copy of the stored object (if found)
     237             :      */
     238           1 :     Value getCopy(const Key &k)
     239             :     {
     240           1 :         return get(k);
     241             :     }
     242             : 
     243        3177 :     bool remove(const Key &k)
     244             :     {
     245        6354 :         Guard g(lock_);
     246        3177 :         auto iter = cache_.find(k);
     247        3177 :         if (iter == cache_.end())
     248             :         {
     249         103 :             return false;
     250             :         }
     251        3074 :         keys_.erase(iter->second);
     252        3074 :         cache_.erase(iter);
     253        3074 :         return true;
     254             :     }
     255             : 
     256       16853 :     bool contains(const Key &k)
     257             :     {
     258       16853 :         Guard g(lock_);
     259       33706 :         return cache_.find(k) != cache_.end();
     260             :     }
     261             : 
     262           0 :     bool getOldestEntry(Key &kOut, Value &vOut)
     263             :     {
     264           0 :         Guard g(lock_);
     265           0 :         if (keys_.empty())
     266             :         {
     267           0 :             return false;
     268             :         }
     269           0 :         kOut = keys_.back().key;
     270           0 :         vOut = keys_.back().value;
     271           0 :         return true;
     272             :     }
     273             : 
     274         137 :     bool removeAndRecycleOldestEntry(Value &vOut)
     275             :     {
     276         274 :         Guard g(lock_);
     277         137 :         if (keys_.empty())
     278             :         {
     279           1 :             return false;
     280             :         }
     281         136 :         vOut = std::move(keys_.back().value);
     282         136 :         cache_.erase(keys_.back().key);
     283         136 :         keys_.pop_back();
     284         136 :         return true;
     285             :     }
     286             : 
     287         653 :     size_t getMaxSize() const
     288             :     {
     289         653 :         return maxSize_;
     290             :     }
     291             : 
     292           1 :     size_t getElasticity() const
     293             :     {
     294           1 :         return elasticity_;
     295             :     }
     296             : 
     297         165 :     size_t getMaxAllowedSize() const
     298             :     {
     299         165 :         return maxSize_ + elasticity_;
     300             :     }
     301             : 
     302       25691 :     template <typename F> void cwalk(F &f) const
     303             :     {
     304       51049 :         Guard g(lock_);
     305       25691 :         std::for_each(keys_.begin(), keys_.end(), f);
     306       25691 :     }
     307             : 
     308             :     Cache(Cache &&other)
     309             :         : cache_(std::move(other.cache_)), keys_(std::move(other.keys_)),
     310             :           maxSize_(other.maxSize_), elasticity_(other.elasticity_)
     311             :     {
     312             :     }
     313             : 
     314             :   protected:
     315       24003 :     size_t prune()
     316             :     {
     317       24003 :         size_t maxAllowed = maxSize_ + elasticity_;
     318       24003 :         if (maxSize_ == 0 || cache_.size() <= maxAllowed)
     319             :         { /* ERO: changed < to <= */
     320       22207 :             return 0;
     321             :         }
     322        1791 :         size_t count = 0;
     323       11568 :         while (cache_.size() > maxSize_)
     324             :         {
     325        9776 :             cache_.erase(keys_.back().key);
     326        9776 :             keys_.pop_back();
     327        9777 :             ++count;
     328             :         }
     329        1786 :         return count;
     330             :     }
     331             : 
     332             :   private:
     333             :     // Disallow copying.
     334             :     Cache(const Cache &) = delete;
     335             :     Cache &operator=(const Cache &) = delete;
     336             : 
     337             :     mutable Lock lock_{};
     338             :     Map cache_{};
     339             :     list_type keys_{};
     340             :     size_t maxSize_;
     341             :     size_t elasticity_;
     342             : };
     343             : 
     344             : }  // namespace lru11
     345             : 
     346             : /*! @endcond */