src/base/LruMap.h

   1 /*
   2  * Copyright (C) 1996-2020 The Squid Software Foundation and contributors
   3  *
   4  * Squid software is distributed under GPLv2+ license and includes
   5  * contributions from numerous individuals and organizations.
   6  * Please see the COPYING and CONTRIBUTORS files for details.
   7  */
   8
   9 #ifndef SQUID_LRUMAP_H
  10 #define SQUID_LRUMAP_H
  11
  12 #include "SquidTime.h"
  13
  14 #include <list>
  15 #include <map>
  16
  17 template <class Key, class EntryValue, size_t EntryCost = sizeof(EntryValue)> class LruMap
  18 {
  19 public:
  20     class Entry
  21     {
  22     public:
  23         Entry(const Key &aKey, EntryValue *t): key(aKey), value(t), date(squid_curtime) {}
  24         ~Entry() {delete value;}
  25     private:
  26         Entry(Entry &);
  27         Entry & operator = (Entry &);
  28     public:
  29         Key key; ///< the key of entry
  30         EntryValue *value; ///< A pointer to the stored value
  31         time_t date; ///< The date the entry created
  32     };
  33     typedef std::list<Entry *> Queue;
  34     typedef typename std::list<Entry *>::iterator QueueIterator;
  35
  36     /// key:queue_item mapping for fast lookups by key
  37     typedef std::map<Key, QueueIterator> Map;
  38     typedef typename Map::iterator MapIterator;
  39     typedef std::pair<Key, QueueIterator> MapPair;
  40
  41     LruMap(int ttl, size_t size);
  42     ~LruMap();
  43     /// Search for an entry, and return a pointer
  44     EntryValue *get(const Key &key);
  45     /// Add an entry to the map
  46     bool add(const Key &key, EntryValue *t);
  47     /// Delete an entry from the map
  48     bool del(const Key &key);
  49     /// (Re-)set the maximum size for this map
  50     void setMemLimit(size_t aSize);
  51     /// The available size for the map
  52     size_t memLimit() const {return memLimit_;}
  53     /// The free space of the map
  54     size_t freeMem() const { return (memLimit() > size() ? memLimit() - size() : 0);}
  55     /// The current size of the map
  56     size_t size() const {return (entries_ * EntryCost);}
  57     /// The number of stored entries
  58     int entries() const {return entries_;}
  59 private:
  60     LruMap(LruMap const &);
  61     LruMap & operator = (LruMap const &);
  62
  63     bool expired(const Entry &e) const;
  64     void trim();
  65     void touch(const MapIterator &i);
  66     bool del(const MapIterator &i);
  67     void findEntry(const Key &key, LruMap::MapIterator &i);
  68
  69     Map storage; ///< The Key/value * pairs
  70     Queue index; ///< LRU cache index
  71     int ttl;///< >0 ttl for caching, == 0 cache is disabled, < 0 store for ever
  72     size_t memLimit_; ///< The maximum memory to use
  73     int entries_; ///< The stored entries
  74 };
  75
  76 template <class Key, class EntryValue, size_t EntryCost>
  77 LruMap<Key, EntryValue, EntryCost>::LruMap(int aTtl, size_t aSize): entries_(0)
  78 {
  79     ttl = aTtl;
  80
  81     setMemLimit(aSize);
  82 }
  83
  84 template <class Key, class EntryValue, size_t EntryCost>
  85 LruMap<Key, EntryValue, EntryCost>::~LruMap()
  86 {
  87     for (QueueIterator i = index.begin(); i != index.end(); ++i) {
  88         delete *i;
  89     }
  90 }
  91
  92 template <class Key, class EntryValue, size_t EntryCost>
  93 void
  94 LruMap<Key, EntryValue, EntryCost>::setMemLimit(size_t aSize)
  95 {
  96     if (aSize > 0)
  97         memLimit_ = aSize;
  98     else
  99         memLimit_ = 0;
 100 }
 101
 102 template <class Key, class EntryValue, size_t EntryCost>
 103 void
 104 LruMap<Key, EntryValue, EntryCost>::findEntry(const Key &key, LruMap::MapIterator &i)
 105 {
 106     i = storage.find(key);
 107     if (i == storage.end()) {
 108         return;
 109     }
 110     index.push_front(*(i->second));
 111     index.erase(i->second);
 112     i->second = index.begin();
 113
 114     if (const Entry *e = *i->second) {
 115         if (!expired(*e))
 116             return;
 117         // else fall through to cleanup
 118     }
 119
 120     del(i);
 121     i = storage.end();
 122 }
 123
 124 template <class Key, class EntryValue, size_t EntryCost>
 125 EntryValue *
 126 LruMap<Key, EntryValue, EntryCost>::get(const Key &key)
 127 {
 128     MapIterator i;
 129     findEntry(key, i);
 130     if (i != storage.end()) {
 131         touch(i);
 132         Entry *e = *i->second;
 133         return e->value;
 134     }
 135     return NULL;
 136 }
 137
 138 template <class Key, class EntryValue, size_t EntryCost>
 139 bool
 140 LruMap<Key, EntryValue, EntryCost>::add(const Key &key, EntryValue *t)
 141 {
 142     if (ttl == 0)
 143         return false;
 144
 145     del(key);
 146     trim();
 147
 148     if (memLimit() == 0)
 149         return false;
 150
 151     index.push_front(new Entry(key, t));
 152     storage.insert(MapPair(key, index.begin()));
 153
 154     ++entries_;
 155     return true;
 156 }
 157
 158 template <class Key, class EntryValue, size_t EntryCost>
 159 bool
 160 LruMap<Key, EntryValue, EntryCost>::expired(const LruMap::Entry &entry) const
 161 {
 162     if (ttl < 0)
 163         return false;
 164
 165     return (entry.date + ttl < squid_curtime);
 166 }
 167
 168 template <class Key, class EntryValue, size_t EntryCost>
 169 bool
 170 LruMap<Key, EntryValue, EntryCost>::del(LruMap::MapIterator const &i)
 171 {
 172     if (i != storage.end()) {
 173         Entry *e = *i->second;
 174         index.erase(i->second);
 175         storage.erase(i);
 176         delete e;
 177         --entries_;
 178         return true;
 179     }
 180     return false;
 181 }
 182
 183 template <class Key, class EntryValue, size_t EntryCost>
 184 bool
 185 LruMap<Key, EntryValue, EntryCost>::del(const Key &key)
 186 {
 187     MapIterator i;
 188     findEntry(key, i);
 189     return del(i);
 190 }
 191
 192 template <class Key, class EntryValue, size_t EntryCost>
 193 void
 194 LruMap<Key, EntryValue, EntryCost>::trim()
 195 {
 196     while (size() >= memLimit()) {
 197         QueueIterator i = index.end();
 198         --i;
 199         if (i != index.end()) {
 200             del((*i)->key);
 201         }
 202     }
 203 }
 204
 205 template <class Key, class EntryValue, size_t EntryCost>
 206 void
 207 LruMap<Key, EntryValue, EntryCost>::touch(LruMap::MapIterator const &i)
 208 {
 209     // this must not be done when nothing is being cached.
 210     if (ttl == 0)
 211         return;
 212
 213     index.push_front(*(i->second));
 214     index.erase(i->second);
 215     i->second = index.begin();
 216 }
 217
 218 #endif
 219