]>
git.ipfire.org Git - thirdparty/squid.git/blob - src/base/LruMap.h
2 * Copyright (C) 1996-2017 The Squid Software Foundation and contributors
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.
10 #define SQUID_LRUMAP_H
12 #include "SquidTime.h"
17 template <class Key
, class EntryValue
, size_t EntryCost
= sizeof(EntryValue
)> class LruMap
23 Entry(const Key
&aKey
, EntryValue
*t
): key(aKey
), value(t
), date(squid_curtime
) {}
24 ~Entry() {delete value
;}
27 Entry
& operator = (Entry
&);
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
33 typedef std::list
<Entry
*> Queue
;
34 typedef typename
std::list
<Entry
*>::iterator QueueIterator
;
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
;
41 LruMap(int ttl
, size_t size
);
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_
;}
60 LruMap(LruMap
const &);
61 LruMap
& operator = (LruMap
const &);
63 bool expired(const Entry
&e
) const;
65 void touch(const MapIterator
&i
);
66 bool del(const MapIterator
&i
);
67 void findEntry(const Key
&key
, LruMap::MapIterator
&i
);
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
76 template <class Key
, class EntryValue
, size_t EntryCost
>
77 LruMap
<Key
, EntryValue
, EntryCost
>::LruMap(int aTtl
, size_t aSize
): entries_(0)
84 template <class Key
, class EntryValue
, size_t EntryCost
>
85 LruMap
<Key
, EntryValue
, EntryCost
>::~LruMap()
87 for (QueueIterator i
= index
.begin(); i
!= index
.end(); ++i
) {
92 template <class Key
, class EntryValue
, size_t EntryCost
>
94 LruMap
<Key
, EntryValue
, EntryCost
>::setMemLimit(size_t aSize
)
102 template <class Key
, class EntryValue
, size_t EntryCost
>
104 LruMap
<Key
, EntryValue
, EntryCost
>::findEntry(const Key
&key
, LruMap::MapIterator
&i
)
106 i
= storage
.find(key
);
107 if (i
== storage
.end()) {
110 index
.push_front(*(i
->second
));
111 index
.erase(i
->second
);
112 i
->second
= index
.begin();
114 if (const Entry
*e
= *i
->second
) {
117 // else fall through to cleanup
124 template <class Key
, class EntryValue
, size_t EntryCost
>
126 LruMap
<Key
, EntryValue
, EntryCost
>::get(const Key
&key
)
130 if (i
!= storage
.end()) {
132 Entry
*e
= *i
->second
;
138 template <class Key
, class EntryValue
, size_t EntryCost
>
140 LruMap
<Key
, EntryValue
, EntryCost
>::add(const Key
&key
, EntryValue
*t
)
151 index
.push_front(new Entry(key
, t
));
152 storage
.insert(MapPair(key
, index
.begin()));
158 template <class Key
, class EntryValue
, size_t EntryCost
>
160 LruMap
<Key
, EntryValue
, EntryCost
>::expired(const LruMap::Entry
&entry
) const
165 return (entry
.date
+ ttl
< squid_curtime
);
168 template <class Key
, class EntryValue
, size_t EntryCost
>
170 LruMap
<Key
, EntryValue
, EntryCost
>::del(LruMap::MapIterator
const &i
)
172 if (i
!= storage
.end()) {
173 Entry
*e
= *i
->second
;
174 index
.erase(i
->second
);
183 template <class Key
, class EntryValue
, size_t EntryCost
>
185 LruMap
<Key
, EntryValue
, EntryCost
>::del(const Key
&key
)
192 template <class Key
, class EntryValue
, size_t EntryCost
>
194 LruMap
<Key
, EntryValue
, EntryCost
>::trim()
196 while (size() >= memLimit()) {
197 QueueIterator i
= index
.end();
199 if (i
!= index
.end()) {
205 template <class Key
, class EntryValue
, size_t EntryCost
>
207 LruMap
<Key
, EntryValue
, EntryCost
>::touch(LruMap::MapIterator
const &i
)
209 // this must not be done when nothing is being cached.
213 index
.push_front(*(i
->second
));
214 index
.erase(i
->second
);
215 i
->second
= index
.begin();