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
  76 protected:
  77         void evict(size_t itemsToKeep)
  78         {
  79                 for(ItemsList::iterator it = itemsList.begin();
  80                         itemsList.size() > itemsToKeep && it != itemsList.end();)
  81                 {
  82                         itemsMap.erase(it->key);
  83                         it = itemsList.erase(it);
  84                 }
  85         }
  86
  87 private:
  88         struct ListItem
  89         {
  90                 ListItem(const key_t & key, const value_t & val)
  91                         : key(key), val(val)
  92                 {
  93                 }
  94
  95                 key_t key;
  96                 value_t val;
  97         };
  98
  99         typedef std::list<ListItem> ItemsList;
 100         typedef std::unordered_map<key_t, typename ItemsList::iterator> ItemsMap;
 101
 102         size_t maxSize;
 103         ItemsMap itemsMap;
 104         ItemsList itemsList;
 105 };