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     6191316 :     void lock()
      51             :     {
      52     6191316 :     }
      53             : 
      54     6187956 :     void unlock()
      55             :     {
      56     6187956 :     }
      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       11140 :     KeyValuePair(const K &k, const V &v) : key(k), value(v)
      91             :     {
      92       11140 :     }
      93             : 
      94       27998 :     KeyValuePair(const K &k, V &&v) : key(k), value(std::move(v))
      95             :     {
      96       27998 :     }
      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       97866 :     explicit Cache(size_t maxSize = 64, size_t elasticity = 10)
     136       97866 :         : maxSize_(maxSize), elasticity_(elasticity)
     137             :     {
     138       97866 :     }
     139             : 
     140       84722 :     ~Cache() = default;
     141             : 
     142         845 :     size_t size() const
     143             :     {
     144        1690 :         Guard g(lock_);
     145         845 :         return cache_.size();
     146             :     }
     147             : 
     148        5773 :     bool empty() const
     149             :     {
     150       11546 :         Guard g(lock_);
     151        5773 :         return cache_.empty();
     152             :     }
     153             : 
     154       85279 :     void clear()
     155             :     {
     156      170558 :         Guard g(lock_);
     157       85279 :         cache_.clear();
     158       85279 :         keys_.clear();
     159       85279 :     }
     160             : 
     161       12743 :     void insert(const Key &k, const Value &v)
     162             :     {
     163       12743 :         Guard g(lock_);
     164       12743 :         const auto iter = cache_.find(k);
     165       12743 :         if (iter != cache_.end())
     166             :         {
     167        1603 :             iter->second->value = v;
     168        1603 :             keys_.splice(keys_.begin(), keys_, iter->second);
     169        1603 :             return;
     170             :         }
     171             : 
     172       11140 :         keys_.emplace_front(k, v);
     173       11140 :         cache_[k] = keys_.begin();
     174       11140 :         prune();
     175             :     }
     176             : 
     177       28215 :     Value &insert(const Key &k, Value &&v)
     178             :     {
     179       56430 :         Guard g(lock_);
     180       28215 :         const auto iter = cache_.find(k);
     181       28215 :         if (iter != cache_.end())
     182             :         {
     183         217 :             iter->second->value = std::move(v);
     184         217 :             keys_.splice(keys_.begin(), keys_, iter->second);
     185         217 :             return keys_.front().value;
     186             :         }
     187             : 
     188       27998 :         keys_.emplace_front(k, std::move(v));
     189       27998 :         cache_[k] = keys_.begin();
     190       27998 :         prune();
     191       27998 :         return keys_.front().value;
     192             :     }
     193             : 
     194     5854606 :     bool tryGet(const Key &kIn, Value &vOut)
     195             :     {
     196    11709210 :         Guard g(lock_);
     197     5854606 :         const auto iter = cache_.find(kIn);
     198     5854606 :         if (iter == cache_.end())
     199             :         {
     200     4491887 :             return false;
     201             :         }
     202     1362718 :         keys_.splice(keys_.begin(), keys_, iter->second);
     203     1362718 :         vOut = iter->second->value;
     204     1362718 :         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      208717 :     Value *getPtr(const Key &k)
     224             :     {
     225      417434 :         Guard g(lock_);
     226      208717 :         const auto iter = cache_.find(k);
     227      208717 :         if (iter == cache_.end())
     228             :         {
     229       16496 :             return nullptr;
     230             :         }
     231      192221 :         keys_.splice(keys_.begin(), keys_, iter->second);
     232      192221 :         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        3322 :     bool remove(const Key &k)
     244             :     {
     245        6644 :         Guard g(lock_);
     246        3322 :         auto iter = cache_.find(k);
     247        3322 :         if (iter == cache_.end())
     248             :         {
     249          76 :             return false;
     250             :         }
     251        3246 :         keys_.erase(iter->second);
     252        3246 :         cache_.erase(iter);
     253        3246 :         return true;
     254             :     }
     255             : 
     256       17226 :     bool contains(const Key &k)
     257             :     {
     258       17226 :         Guard g(lock_);
     259       34452 :         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         188 :     size_t getMaxAllowedSize() const
     298             :     {
     299         188 :         return maxSize_ + elasticity_;
     300             :     }
     301             : 
     302       16873 :     template <typename F> void cwalk(F &f)
     303             :     {
     304       33405 :         Guard g(lock_);
     305       16873 :         std::for_each(keys_.begin(), keys_.end(), f);
     306       16873 :     }
     307             : 
     308             :     template <typename F> void cwalk(F &f) const
     309             :     {
     310             :         Guard g(lock_);
     311             :         std::for_each(keys_.begin(), keys_.end(), f);
     312             :     }
     313             : 
     314             :     Cache(Cache &&other)
     315             :         : cache_(std::move(other.cache_)), keys_(std::move(other.keys_)),
     316             :           maxSize_(other.maxSize_), elasticity_(other.elasticity_)
     317             :     {
     318             :     }
     319             : 
     320             :   protected:
     321       39138 :     size_t prune()
     322             :     {
     323       39138 :         size_t maxAllowed = maxSize_ + elasticity_;
     324       39138 :         if (maxSize_ == 0 || cache_.size() <= maxAllowed)
     325             :         { /* ERO: changed < to <= */
     326       36660 :             return 0;
     327             :         }
     328        2478 :         size_t count = 0;
     329       19727 :         while (cache_.size() > maxSize_)
     330             :         {
     331       17249 :             cache_.erase(keys_.back().key);
     332       17249 :             keys_.pop_back();
     333       17249 :             ++count;
     334             :         }
     335        2478 :         return count;
     336             :     }
     337             : 
     338             :   private:
     339             :     // Disallow copying.
     340             :     Cache(const Cache &) = delete;
     341             :     Cache &operator=(const Cache &) = delete;
     342             : 
     343             :     mutable Lock lock_{};
     344             :     Map cache_{};
     345             :     list_type keys_{};
     346             :     size_t maxSize_;
     347             :     size_t elasticity_;
     348             : };
     349             : 
     350             : }  // namespace lru11
     351             : 
     352             : /*! @endcond */