1 /*
2 * Copyright (C) 1996-2021 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:
Entry(const Key & aKey,EntryValue * t)23 Entry(const Key &aKey, EntryValue *t): key(aKey), value(t), date(squid_curtime) {}
~Entry()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
memLimit()52 size_t memLimit() const {return memLimit_;}
53 /// The free space of the map
freeMem()54 size_t freeMem() const { return (memLimit() > size() ? memLimit() - size() : 0);}
55 /// The current size of the map
size()56 size_t size() const {return (entries_ * EntryCost);}
57 /// The number of stored entries
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>
LruMap(int aTtl,size_t aSize)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>
~LruMap()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
setMemLimit(size_t aSize)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
findEntry(const Key & key,LruMap::MapIterator & i)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 *
get(const Key & key)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
add(const Key & key,EntryValue * t)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
expired(const LruMap::Entry & entry)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
del(LruMap::MapIterator const & i)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
del(const Key & key)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
trim()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
touch(LruMap::MapIterator const & i)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
220