Merge branch 'master' into subfolders-8.3
[pyTivo.git] / lrucache.py
blob7f8752e5db1f1733b132230eb90b400765971c16
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 # arch-tag: LRU cache main module
8 """a simple LRU (Least-Recently-Used) cache module
10 This module provides very simple LRU (Least-Recently-Used) cache
11 functionality.
13 An *in-memory cache* is useful for storing the results of an
14 'expensive' process (one that takes a lot of time or resources) for
15 later re-use. Typical examples are accessing data from the filesystem,
16 a database, or a network location. If you know you'll need to re-read
17 the data again, it can help to keep it in a cache.
19 You *can* use a Python dictionary as a cache for some purposes.
20 However, if the results you're caching are large, or you have a lot of
21 possible results, this can be impractical memory-wise.
23 An *LRU cache*, on the other hand, only keeps _some_ of the results in
24 memory, which keeps you from overusing resources. The cache is bounded
25 by a maximum size; if you try to add more values to the cache, it will
26 automatically discard the values that you haven't read or written to
27 in the longest time. In other words, the least-recently-used items are
28 discarded. [1]_
30 .. [1]: 'Discarded' here means 'removed from the cache'.
32 """
34 from __future__ import generators
35 import time
36 from heapq import heappush, heappop, heapify
38 __version__ = "0.2"
39 __all__ = ['CacheKeyError', 'LRUCache', 'DEFAULT_SIZE']
40 __docformat__ = 'reStructuredText en'
42 DEFAULT_SIZE = 16
43 """Default size of a new LRUCache object, if no 'size' argument is given."""
45 class CacheKeyError(KeyError):
46 """Error raised when cache requests fail
48 When a cache record is accessed which no longer exists (or never did),
49 this error is raised. To avoid it, you may want to check for the existence
50 of a cache record before reading or deleting it."""
51 pass
53 class LRUCache(object):
54 """Least-Recently-Used (LRU) cache.
56 Instances of this class provide a least-recently-used (LRU) cache. They
57 emulate a Python mapping type. You can use an LRU cache more or less like
58 a Python dictionary, with the exception that objects you put into the
59 cache may be discarded before you take them out.
61 Some example usage::
63 cache = LRUCache(32) # new cache
64 cache['foo'] = get_file_contents('foo') # or whatever
66 if 'foo' in cache: # if it's still in cache...
67 # use cached version
68 contents = cache['foo']
69 else:
70 # recalculate
71 contents = get_file_contents('foo')
72 # store in cache for next time
73 cache['foo'] = contents
75 print cache.size # Maximum size
77 print len(cache) # 0 <= len(cache) <= cache.size
79 cache.size = 10 # Auto-shrink on size assignment
81 for i in range(50): # note: larger than cache size
82 cache[i] = i
84 if 0 not in cache: print 'Zero was discarded.'
86 if 42 in cache:
87 del cache[42] # Manual deletion
89 for j in cache: # iterate (in LRU order)
90 print j, cache[j] # iterator produces keys, not values
91 """
93 class __Node(object):
94 """Record of a cached value. Not for public consumption."""
96 def __init__(self, key, obj, timestamp):
97 object.__init__(self)
98 self.key = key
99 self.obj = obj
100 self.atime = timestamp
101 self.mtime = self.atime
103 def __cmp__(self, other):
104 return cmp(self.atime, other.atime)
106 def __repr__(self):
107 return "<%s %s => %s (%s)>" % \
108 (self.__class__, self.key, self.obj, \
109 time.asctime(time.localtime(self.atime)))
111 def __init__(self, size=DEFAULT_SIZE):
112 # Check arguments
113 if size <= 0:
114 raise ValueError, size
115 elif type(size) is not type(0):
116 raise TypeError, size
117 object.__init__(self)
118 self.__heap = []
119 self.__dict = {}
120 self.size = size
121 """Maximum size of the cache.
122 If more than 'size' elements are added to the cache,
123 the least-recently-used ones will be discarded."""
125 def __len__(self):
126 return len(self.__heap)
128 def __contains__(self, key):
129 return self.__dict.has_key(key)
131 def __setitem__(self, key, obj):
132 if self.__dict.has_key(key):
133 node = self.__dict[key]
134 node.obj = obj
135 node.atime = time.time()
136 node.mtime = node.atime
137 heapify(self.__heap)
138 else:
139 # size may have been reset, so we loop
140 while len(self.__heap) >= self.size:
141 lru = heappop(self.__heap)
142 del self.__dict[lru.key]
143 node = self.__Node(key, obj, time.time())
144 self.__dict[key] = node
145 heappush(self.__heap, node)
147 def __getitem__(self, key):
148 if not self.__dict.has_key(key):
149 raise CacheKeyError(key)
150 else:
151 node = self.__dict[key]
152 node.atime = time.time()
153 heapify(self.__heap)
154 return node.obj
156 def __delitem__(self, key):
157 if not self.__dict.has_key(key):
158 raise CacheKeyError(key)
159 else:
160 node = self.__dict[key]
161 del self.__dict[key]
162 self.__heap.remove(node)
163 heapify(self.__heap)
164 return node.obj
166 def __iter__(self):
167 copy = self.__heap[:]
168 while len(copy) > 0:
169 node = heappop(copy)
170 yield node.key
171 raise StopIteration
173 def __setattr__(self, name, value):
174 object.__setattr__(self, name, value)
175 # automagically shrink heap on resize
176 if name == 'size':
177 while len(self.__heap) > value:
178 lru = heappop(self.__heap)
179 del self.__dict[lru.key]
181 def __repr__(self):
182 return "<%s (%d elements)>" % (str(self.__class__), len(self.__heap))
184 def mtime(self, key):
185 """Return the last modification time for the cache record with key.
186 May be useful for cache instances where the stored values can get
187 'stale', such as caching file or network resource contents."""
188 if not self.__dict.has_key(key):
189 raise CacheKeyError(key)
190 else:
191 node = self.__dict[key]
192 return node.mtime
194 if __name__ == "__main__":
195 cache = LRUCache(25)
196 print cache
197 for i in range(50):
198 cache[i] = str(i)
199 print cache
200 if 46 in cache:
201 del cache[46]
202 print cache
203 cache.size = 10
204 print cache
205 cache[46] = '46'
206 print cache
207 print len(cache)
208 for c in cache:
209 print c
210 print cache
211 print cache.mtime(46)
212 for c in cache:
213 print c