LruMap.h
Go to the documentation of this file.
1 /*
2  * Copyright (C) 1996-2017 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;
30  EntryValue *value;
31  time_t date;
32  };
33  typedef std::list<Entry *> Queue;
34  typedef typename std::list<Entry *>::iterator QueueIterator;
35 
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();
44  EntryValue *get(const Key &key);
46  bool add(const Key &key, EntryValue *t);
48  bool del(const Key &key);
50  void setMemLimit(size_t aSize);
52  size_t memLimit() const {return memLimit_;}
54  size_t freeMem() const { return (memLimit() > size() ? memLimit() - size() : 0);}
56  size_t size() const {return (entries_ * EntryCost);}
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 
71  int ttl;
72  size_t memLimit_;
73  int 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>
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
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
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 *
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
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
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
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
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
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
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 
Entry & operator=(Entry &)
static char const * trim(char const *s)
Definition: Expression.cc:657
void findEntry(const Key &key, LruMap::MapIterator &i)
Definition: LruMap.h:104
int i
Definition: membanger.c:49
int ttl
>0 ttl for caching, == 0 cache is disabled, < 0 store for ever
Definition: LruMap.h:71
Map::iterator MapIterator
Definition: LruMap.h:38
LruMap(int ttl, size_t size)
Definition: LruMap.h:77
time_t squid_curtime
Definition: stub_time.cc:17
void trim()
Definition: LruMap.h:194
~LruMap()
Definition: LruMap.h:85
void touch(const MapIterator &i)
Definition: LruMap.h:207
std::map< Key, QueueIterator > Map
key:queue_item mapping for fast lookups by key
Definition: LruMap.h:37
Definition: cf_gen.cc:87
::StoreEntry Entry
Definition: forward.h:44
bool add(const Key &key, EntryValue *t)
Add an entry to the map.
Definition: LruMap.h:140
Definition: LruMap.h:17
std::list< Entry * >::iterator QueueIterator
Definition: LruMap.h:34
int entries() const
The number of stored entries.
Definition: LruMap.h:58
Entry(const Key &aKey, EntryValue *t)
Definition: LruMap.h:23
std::list< Entry * > Queue
Definition: LruMap.h:33
std::pair< Key, QueueIterator > MapPair
Definition: LruMap.h:39
size_t freeMem() const
The free space of the map.
Definition: LruMap.h:54
size_t memLimit() const
The available size for the map.
Definition: LruMap.h:52
size_t size() const
The current size of the map.
Definition: LruMap.h:56
void setMemLimit(size_t aSize)
(Re-)set the maximum size for this map
Definition: LruMap.h:94
bool expired(const Entry &e) const
Definition: LruMap.h:160
int entries_
The stored entries.
Definition: LruMap.h:73
size_t memLimit_
The maximum memory to use.
Definition: LruMap.h:72
Map storage
The Key/value * pairs.
Definition: LruMap.h:69
void const cache_key * key
EntryValue * get(const Key &key)
Search for an entry, and return a pointer.
Definition: LruMap.h:126
Key key
the key of entry
Definition: LruMap.h:29
EntryValue * value
A pointer to the stored value.
Definition: LruMap.h:30
Queue index
LRU cache index.
Definition: LruMap.h:70
bool del(const Key &key)
Delete an entry from the map.
Definition: LruMap.h:185
LruMap & operator=(LruMap const &)
time_t date
The date the entry created.
Definition: LruMap.h:31
#define NULL
Definition: types.h:166
int size
Definition: ModDevPoll.cc:77

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors