]>
Commit | Line | Data |
---|---|---|
14798e73 | 1 | /* |
4ac4a490 | 2 | * Copyright (C) 1996-2017 The Squid Software Foundation and contributors |
bbc27441 AJ |
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. | |
14798e73 CT |
7 | */ |
8 | ||
9 | #ifndef SQUID_LRUMAP_H | |
10 | #define SQUID_LRUMAP_H | |
11 | ||
12 | #include "SquidTime.h" | |
074d6a40 | 13 | |
14798e73 | 14 | #include <list> |
14798e73 | 15 | #include <map> |
14798e73 | 16 | |
5107d2c4 | 17 | template <class Key, class EntryValue, size_t EntryCost = sizeof(EntryValue)> class LruMap |
14798e73 CT |
18 | { |
19 | public: | |
20 | class Entry | |
21 | { | |
22 | public: | |
5107d2c4 | 23 | Entry(const Key &aKey, EntryValue *t): key(aKey), value(t), date(squid_curtime) {} |
14798e73 CT |
24 | ~Entry() {delete value;} |
25 | private: | |
a70d5f19 CT |
26 | Entry(Entry &); |
27 | Entry & operator = (Entry &); | |
14798e73 | 28 | public: |
5107d2c4 | 29 | Key key; ///< the key of entry |
14798e73 CT |
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; | |
4c304fb9 | 35 | |
14798e73 | 36 | /// key:queue_item mapping for fast lookups by key |
5107d2c4 | 37 | typedef std::map<Key, QueueIterator> Map; |
14798e73 | 38 | typedef typename Map::iterator MapIterator; |
5107d2c4 | 39 | typedef std::pair<Key, QueueIterator> MapPair; |
14798e73 | 40 | |
14798e73 CT |
41 | LruMap(int ttl, size_t size); |
42 | ~LruMap(); | |
43 | /// Search for an entry, and return a pointer | |
5107d2c4 | 44 | EntryValue *get(const Key &key); |
14798e73 | 45 | /// Add an entry to the map |
5107d2c4 | 46 | bool add(const Key &key, EntryValue *t); |
14798e73 | 47 | /// Delete an entry from the map |
5107d2c4 | 48 | bool del(const Key &key); |
14798e73 CT |
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 | |
9873e378 | 54 | size_t freeMem() const { return (memLimit() > size() ? memLimit() - size() : 0);} |
14798e73 CT |
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: | |
a70d5f19 CT |
60 | LruMap(LruMap const &); |
61 | LruMap & operator = (LruMap const &); | |
4c304fb9 | 62 | |
0cef2d4b | 63 | bool expired(const Entry &e) const; |
14798e73 CT |
64 | void trim(); |
65 | void touch(const MapIterator &i); | |
66 | bool del(const MapIterator &i); | |
5107d2c4 | 67 | void findEntry(const Key &key, LruMap::MapIterator &i); |
14798e73 CT |
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 | ||
5107d2c4 | 76 | template <class Key, class EntryValue, size_t EntryCost> |
62b9cc19 | 77 | LruMap<Key, EntryValue, EntryCost>::LruMap(int aTtl, size_t aSize): entries_(0) |
14798e73 CT |
78 | { |
79 | ttl = aTtl; | |
80 | ||
81 | setMemLimit(aSize); | |
82 | } | |
83 | ||
5107d2c4 CT |
84 | template <class Key, class EntryValue, size_t EntryCost> |
85 | LruMap<Key, EntryValue, EntryCost>::~LruMap() | |
14798e73 CT |
86 | { |
87 | for (QueueIterator i = index.begin(); i != index.end(); ++i) { | |
88 | delete *i; | |
89 | } | |
90 | } | |
91 | ||
5107d2c4 | 92 | template <class Key, class EntryValue, size_t EntryCost> |
14798e73 | 93 | void |
5107d2c4 | 94 | LruMap<Key, EntryValue, EntryCost>::setMemLimit(size_t aSize) |
14798e73 CT |
95 | { |
96 | if (aSize > 0) | |
97 | memLimit_ = aSize; | |
98 | else | |
99 | memLimit_ = 0; | |
100 | } | |
101 | ||
5107d2c4 | 102 | template <class Key, class EntryValue, size_t EntryCost> |
14798e73 | 103 | void |
5107d2c4 | 104 | LruMap<Key, EntryValue, EntryCost>::findEntry(const Key &key, LruMap::MapIterator &i) |
14798e73 CT |
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(); | |
4c304fb9 | 113 | |
0cef2d4b CT |
114 | if (const Entry *e = *i->second) { |
115 | if (!expired(*e)) | |
116 | return; | |
117 | // else fall through to cleanup | |
14798e73 | 118 | } |
0cef2d4b CT |
119 | |
120 | del(i); | |
121 | i = storage.end(); | |
14798e73 CT |
122 | } |
123 | ||
5107d2c4 | 124 | template <class Key, class EntryValue, size_t EntryCost> |
14798e73 | 125 | EntryValue * |
5107d2c4 | 126 | LruMap<Key, EntryValue, EntryCost>::get(const Key &key) |
14798e73 | 127 | { |
9aea094e | 128 | MapIterator i; |
14798e73 | 129 | findEntry(key, i); |
14798e73 CT |
130 | if (i != storage.end()) { |
131 | touch(i); | |
0cef2d4b | 132 | Entry *e = *i->second; |
14798e73 CT |
133 | return e->value; |
134 | } | |
135 | return NULL; | |
136 | } | |
137 | ||
5107d2c4 | 138 | template <class Key, class EntryValue, size_t EntryCost> |
14798e73 | 139 | bool |
5107d2c4 | 140 | LruMap<Key, EntryValue, EntryCost>::add(const Key &key, EntryValue *t) |
14798e73 CT |
141 | { |
142 | if (ttl == 0) | |
143 | return false; | |
144 | ||
145 | del(key); | |
146 | trim(); | |
c661b1c9 CT |
147 | |
148 | if (memLimit() == 0) | |
149 | return false; | |
150 | ||
14798e73 CT |
151 | index.push_front(new Entry(key, t)); |
152 | storage.insert(MapPair(key, index.begin())); | |
153 | ||
154 | ++entries_; | |
155 | return true; | |
156 | } | |
157 | ||
5107d2c4 | 158 | template <class Key, class EntryValue, size_t EntryCost> |
14798e73 | 159 | bool |
5107d2c4 | 160 | LruMap<Key, EntryValue, EntryCost>::expired(const LruMap::Entry &entry) const |
14798e73 CT |
161 | { |
162 | if (ttl < 0) | |
163 | return false; | |
164 | ||
165 | return (entry.date + ttl < squid_curtime); | |
166 | } | |
167 | ||
5107d2c4 | 168 | template <class Key, class EntryValue, size_t EntryCost> |
14798e73 | 169 | bool |
5107d2c4 | 170 | LruMap<Key, EntryValue, EntryCost>::del(LruMap::MapIterator const &i) |
14798e73 | 171 | { |
4c304fb9 | 172 | if (i != storage.end()) { |
e5ec7440 | 173 | Entry *e = *i->second; |
14798e73 CT |
174 | index.erase(i->second); |
175 | storage.erase(i); | |
0cef2d4b | 176 | delete e; |
14798e73 CT |
177 | --entries_; |
178 | return true; | |
179 | } | |
180 | return false; | |
181 | } | |
182 | ||
5107d2c4 | 183 | template <class Key, class EntryValue, size_t EntryCost> |
14798e73 | 184 | bool |
5107d2c4 | 185 | LruMap<Key, EntryValue, EntryCost>::del(const Key &key) |
14798e73 | 186 | { |
9aea094e | 187 | MapIterator i; |
14798e73 CT |
188 | findEntry(key, i); |
189 | return del(i); | |
190 | } | |
191 | ||
5107d2c4 | 192 | template <class Key, class EntryValue, size_t EntryCost> |
14798e73 | 193 | void |
5107d2c4 | 194 | LruMap<Key, EntryValue, EntryCost>::trim() |
14798e73 | 195 | { |
3f9d0e1c | 196 | while (size() >= memLimit()) { |
9aea094e | 197 | QueueIterator i = index.end(); |
14798e73 CT |
198 | --i; |
199 | if (i != index.end()) { | |
5107d2c4 | 200 | del((*i)->key); |
14798e73 CT |
201 | } |
202 | } | |
203 | } | |
204 | ||
5107d2c4 | 205 | template <class Key, class EntryValue, size_t EntryCost> |
14798e73 | 206 | void |
5107d2c4 | 207 | LruMap<Key, EntryValue, EntryCost>::touch(LruMap::MapIterator const &i) |
14798e73 CT |
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 | |
f53969cc | 219 |