]>
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 CT |
16 | |
17 | template <class EntryValue, size_t EntryCost = sizeof(EntryValue)> class LruMap | |
18 | { | |
19 | public: | |
20 | class Entry | |
21 | { | |
22 | public: | |
23 | Entry(const char *aKey, EntryValue *t): key(aKey), value(t), date(squid_curtime) {} | |
24 | ~Entry() {delete value;} | |
25 | private: | |
a70d5f19 CT |
26 | Entry(Entry &); |
27 | Entry & operator = (Entry &); | |
14798e73 CT |
28 | public: |
29 | std::string 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; | |
4c304fb9 | 35 | |
14798e73 CT |
36 | /// key:queue_item mapping for fast lookups by key |
37 | typedef std::map<std::string, QueueIterator> Map; | |
38 | typedef typename Map::iterator MapIterator; | |
39 | typedef std::pair<std::string, QueueIterator> MapPair; | |
40 | ||
14798e73 CT |
41 | LruMap(int ttl, size_t size); |
42 | ~LruMap(); | |
43 | /// Search for an entry, and return a pointer | |
44 | EntryValue *get(const char *key); | |
45 | /// Add an entry to the map | |
46 | bool add(const char *key, EntryValue *t); | |
47 | /// Delete an entry from the map | |
48 | bool del(const char *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 | |
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); | |
67 | void findEntry(const char *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 EntryValue, size_t EntryCost> | |
77 | LruMap<EntryValue, EntryCost>::LruMap(int aTtl, size_t aSize): entries_(0) | |
78 | { | |
79 | ttl = aTtl; | |
80 | ||
81 | setMemLimit(aSize); | |
82 | } | |
83 | ||
84 | template <class EntryValue, size_t EntryCost> | |
85 | LruMap<EntryValue, EntryCost>::~LruMap() | |
86 | { | |
87 | for (QueueIterator i = index.begin(); i != index.end(); ++i) { | |
88 | delete *i; | |
89 | } | |
90 | } | |
91 | ||
92 | template <class EntryValue, size_t EntryCost> | |
93 | void | |
94 | LruMap<EntryValue, EntryCost>::setMemLimit(size_t aSize) | |
95 | { | |
96 | if (aSize > 0) | |
97 | memLimit_ = aSize; | |
98 | else | |
99 | memLimit_ = 0; | |
100 | } | |
101 | ||
102 | template <class EntryValue, size_t EntryCost> | |
103 | void | |
104 | LruMap<EntryValue, EntryCost>::findEntry(const char *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(); | |
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 | ||
124 | template <class EntryValue, size_t EntryCost> | |
125 | EntryValue * | |
126 | LruMap<EntryValue, EntryCost>::get(const char *key) | |
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 | ||
138 | template <class EntryValue, size_t EntryCost> | |
139 | bool | |
140 | LruMap<EntryValue, EntryCost>::add(const char *key, EntryValue *t) | |
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 | ||
158 | template <class EntryValue, size_t EntryCost> | |
159 | bool | |
0cef2d4b | 160 | LruMap<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 | ||
168 | template <class EntryValue, size_t EntryCost> | |
169 | bool | |
170 | LruMap<EntryValue, EntryCost>::del(LruMap::MapIterator const &i) | |
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 | ||
183 | template <class EntryValue, size_t EntryCost> | |
184 | bool | |
185 | LruMap<EntryValue, EntryCost>::del(const char *key) | |
186 | { | |
9aea094e | 187 | MapIterator i; |
14798e73 CT |
188 | findEntry(key, i); |
189 | return del(i); | |
190 | } | |
191 | ||
192 | template <class EntryValue, size_t EntryCost> | |
193 | void | |
194 | LruMap<EntryValue, EntryCost>::trim() | |
195 | { | |
3f9d0e1c | 196 | while (size() >= memLimit()) { |
9aea094e | 197 | QueueIterator i = index.end(); |
14798e73 CT |
198 | --i; |
199 | if (i != index.end()) { | |
200 | del((*i)->key.c_str()); | |
201 | } | |
202 | } | |
203 | } | |
204 | ||
205 | template <class EntryValue, size_t EntryCost> | |
206 | void | |
207 | LruMap<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 | |
f53969cc | 219 |