src/Utils/LruCache.h

   1 // TortoiseGit - a Windows shell extension for easy version control
   2
   3 // Copyright (C) 2016 - TortoiseSVN
   4
   5 // This program is free software; you can redistribute it and/or
   6 // modify it under the terms of the GNU General Public License
   7 // as published by the Free Software Foundation; either version 2
   8 // of the License, or (at your option) any later version.
   9
  10 // This program is distributed in the hope that it will be useful,
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 // GNU General Public License for more details.
  14
  15 // You should have received a copy of the GNU General Public License
  16 // along with this program; if not, write to the Free Software Foundation,
  17 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 //
  19
  20 #pragma once
  21
  22 #include <unordered_map>
  23 #include <list>
  24
  25 template<typename key_t, typename value_t>
  26 class LruCache
  27 {
  28 public:
  29     LruCache(size_t maxSize)
  30         : maxSize(maxSize)
  31     {
  32     }
  33
  34     void insert_or_assign(const key_t & key, const value_t & val)
  35     {
  36         ItemsMap::iterator mapIt = itemsMap.find(key);
  37         if (mapIt == itemsMap.end())
  38         {
  39             evict(maxSize - 1);
  40
  41             ItemsList::iterator listIt = itemsList.insert(itemsList.cend(), ListItem(key, val));
  42             itemsMap.insert(std::make_pair(key, listIt));
  43         }
  44         else
  45         {
  46             mapIt->second->val = val;
  47         }
  48     }
  49
  50     const value_t * try_get(const key_t & key)
  51     {
  52         ItemsMap::const_iterator it = itemsMap.find(key);
  53         if (it == itemsMap.end())
  54             return nullptr;
  55
  56         // Move last recently accessed item to the end.
  57         if (it->second != itemsList.end())
  58         {
  59             itemsList.splice(itemsList.end(), itemsList, it->second);
  60         }
  61
  62         return &it->second->val;
  63     }
  64
  65     void reserve(size_t size)
  66     {
  67         itemsMap.reserve(min(maxSize, size));
  68     }
  69
  70     void clear()
  71     {
  72         itemsMap.clear();
  73         itemsList.clear();
  74     }
  75 protected:
  76     void evict(size_t itemsToKeep)
  77     {
  78         for(ItemsList::iterator it = itemsList.begin();
  79             itemsList.size() > itemsToKeep && it != itemsList.end();)
  80         {
  81             itemsMap.erase(it->key);
  82             it = itemsList.erase(it);
  83         }
  84     }
  85 private:
  86     struct ListItem
  87     {
  88         ListItem(const key_t & key, const value_t & val)
  89             : key(key), val(val)
  90         {
  91         }
  92
  93         key_t key;
  94         value_t val;
  95     };
  96
  97     typedef std::list<ListItem> ItemsList;
  98     typedef std::unordered_map<key_t, typename ItemsList::iterator> ItemsMap;
  99
 100     size_t maxSize;
 101     ItemsMap itemsMap;
 102     ItemsList itemsList;
 103 };