1
# lrucache.py -- a simple LRU (Least-Recently-Used) cache class
3
# Copyright 2004 Evan Prodromou <evan@bad.dynu.ca>
4
# Licensed under the Academic Free License 2.1
6
# Modified to use monotonically increasing integer values as access times
7
# by Ivan Vilata i Balaguer <ivilata@carabos.com>.
9
# Modified to use a container in Pyrex for accelerating the heapify()
10
# process by Francesc Altet <faltet@carabos.com>.
12
# arch-tag: LRU cache main module
14
"""a simple LRU (Least-Recently-Used) cache module
16
This module provides very simple LRU (Least-Recently-Used) cache
19
An *in-memory cache* is useful for storing the results of an
20
'expensive' process (one that takes a lot of time or resources) for
21
later re-use. Typical examples are accessing data from the filesystem,
22
a database, or a network location. If you know you'll need to re-read
23
the data again, it can help to keep it in a cache.
25
You *can* use a Python dictionary as a cache for some purposes.
26
However, if the results you're caching are large, or you have a lot of
27
possible results, this can be impractical memory-wise.
29
An *LRU cache*, on the other hand, only keeps _some_ of the results in
30
memory, which keeps you from overusing resources. The cache is bounded
31
by a maximum size; if you try to add more values to the cache, it will
32
automatically discard the values that you haven't read or written to
33
in the longest time. In other words, the least-recently-used items are
36
.. [1]: 'Discarded' here means 'removed from the cache'.
40
from __future__ import generators
42
from heapq import heappush, heappop, heapify
43
from utilsExtension import _g_Node
46
__all__ = ['CacheKeyError', 'LRUCache', 'DEFAULT_SIZE']
47
__docformat__ = 'reStructuredText en'
50
"""Default size of a new LRUCache object, if no 'size' argument is given."""
52
class CacheKeyError(KeyError):
53
"""Error raised when cache requests fail
55
When a cache record is accessed which no longer exists (or never did),
56
this error is raised. To avoid it, you may want to check for the existence
57
of a cache record before reading or deleting it."""
60
class LRUCache(object):
61
"""Least-Recently-Used (LRU) cache.
63
Instances of this class provide a least-recently-used (LRU) cache. They
64
emulate a Python mapping type. You can use an LRU cache more or less like
65
a Python dictionary, with the exception that objects you put into the
66
cache may be discarded before you take them out.
70
cache = LRUCache(32) # new cache
71
cache['foo'] = get_file_contents('foo') # or whatever
73
if 'foo' in cache: # if it's still in cache...
75
contents = cache['foo']
78
contents = get_file_contents('foo')
79
# store in cache for next time
80
cache['foo'] = contents
82
print cache.size # Maximum size
84
print len(cache) # 0 <= len(cache) <= cache.size
86
cache.size = 10 # Auto-shrink on size assignment
88
for i in range(50): # note: larger than cache size
91
if 0 not in cache: print 'Zero was discarded.'
94
del cache[42] # Manual deletion
96
for j in cache: # iterate (in LRU order)
97
print j, cache[j] # iterator produces keys, not values
100
class __Node(object):
101
"""Record of a cached value. Not for public consumption."""
103
def __init__(self, key, obj, timestamp):
104
object.__init__(self)
107
self.atime = timestamp
108
#self.mtime = time.time()
110
def __cmp__(self, other):
111
return cmp(self.atime, other.atime)
114
return "<%s %s => %s (accessed at %s)>" % \
115
(self.__class__, self.key, self.obj, self.atime)
119
self.__seqn_ = seqn + 1
122
__seqn = property(__getseqn)
124
def __init__(self, size=DEFAULT_SIZE):
127
raise ValueError, size
128
elif type(size) is not type(0):
129
raise TypeError, size
130
object.__init__(self)
135
"""Maximum size of the cache.
136
If more than 'size' elements are added to the cache,
137
the least-recently-used ones will be discarded."""
140
return len(self.__heap)
142
def __contains__(self, key):
143
return self.__dict.has_key(key)
145
def __setitem__(self, key, obj):
146
if self.__dict.has_key(key):
147
node = self.__dict[key]
149
node.atime = self.__seqn
152
# size may have been reset, so we loop
153
while len(self.__heap) >= self.size:
154
lru = heappop(self.__heap)
155
del self.__dict[lru.key]
156
# Using _g_Node ext. is almost 4x faster than __Node in pure python
157
node = self.__Node(key, obj, self.__seqn)
158
#node = _g_Node(key, obj, self.__seqn)
159
self.__dict[key] = node
160
heappush(self.__heap, node)
162
def __getitem__(self, key):
163
if not self.__dict.has_key(key):
164
raise CacheKeyError(key)
166
node = self.__dict[key]
167
node.atime = self.__seqn
171
def __delitem__(self, key):
172
if not self.__dict.has_key(key):
173
raise CacheKeyError(key)
175
node = self.__dict[key]
177
self.__heap.remove(node)
182
copy = self.__heap[:]
188
def __setattr__(self, name, value):
189
object.__setattr__(self, name, value)
190
# automagically shrink heap on resize
192
while len(self.__heap) > value:
193
lru = heappop(self.__heap)
194
del self.__dict[lru.key]
197
return "<%s (%d elements)>" % (str(self.__class__), len(self.__heap))
199
def mtime(self, key):
200
"""Return the last modification time for the cache record with key.
201
May be useful for cache instances where the stored values can get
202
'stale', such as caching file or network resource contents."""
203
if not self.__dict.has_key(key):
204
raise CacheKeyError(key)
206
node = self.__dict[key]
209
if __name__ == "__main__":
226
print cache.mtime(46)
added
removed
tables/lrucache.py
