lrucache.py

   1 # lrucache.py -- a simple LRU (Least-Recently-Used) cache class
   2
   3 # Copyright 2004 Evan Prodromou <evan@bad.dynu.ca>
   4 # Licensed under the Academic Free License 2.1
   5
   6 # Licensed for ftputil under the revised BSD license
   7 # with permission by the author, Evan Prodromou. Many
   8 # thanks, Evan! :-)
   9 #
  10 # The original file is available at
  11 # http://pypi.python.org/pypi/lrucache/0.2 .
  12
  13 # arch-tag: LRU cache main module
  14
  15 """a simple LRU (Least-Recently-Used) cache module
  16
  17 This module provides very simple LRU (Least-Recently-Used) cache
  18 functionality.
  19
  20 An *in-memory cache* is useful for storing the results of an
  21 'expensive' process (one that takes a lot of time or resources) for
  22 later re-use. Typical examples are accessing data from the filesystem,
  23 a database, or a network location. If you know you'll need to re-read
  24 the data again, it can help to keep it in a cache.
  25
  26 You *can* use a Python dictionary as a cache for some purposes.
  27 However, if the results you're caching are large, or you have a lot of
  28 possible results, this can be impractical memory-wise.
  29
  30 An *LRU cache*, on the other hand, only keeps _some_ of the results in
  31 memory, which keeps you from overusing resources. The cache is bounded
  32 by a maximum size; if you try to add more values to the cache, it will
  33 automatically discard the values that you haven't read or written to
  34 in the longest time. In other words, the least-recently-used items are
  35 discarded. [1]_
  36
  37 .. [1]: 'Discarded' here means 'removed from the cache'.
  38
  39 """
  40
  41 from __future__ import generators
  42 import time
  43 from heapq import heappush, heappop, heapify
  44
  45 __version__ = "0.2"
  46 __all__ = ['CacheKeyError', 'LRUCache', 'DEFAULT_SIZE']
  47 __docformat__ = 'reStructuredText en'
  48
  49 DEFAULT_SIZE = 16
  50 """Default size of a new LRUCache object, if no 'size' argument is given."""
  51
  52 class CacheKeyError(KeyError):
  53     """Error raised when cache requests fail
  54
  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."""
  58     pass
  59
  60 class LRUCache(object):
  61     """Least-Recently-Used (LRU) cache.
  62
  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.
  67
  68     Some example usage::
  69
  70     cache = LRUCache(32) # new cache
  71     cache['foo'] = get_file_contents('foo') # or whatever
  72
  73     if 'foo' in cache: # if it's still in cache...
  74         # use cached version
  75         contents = cache['foo']
  76     else:
  77         # recalculate
  78         contents = get_file_contents('foo')
  79         # store in cache for next time
  80         cache['foo'] = contents
  81
  82     print cache.size # Maximum size
  83
  84     print len(cache) # 0 <= len(cache) <= cache.size
  85
  86     cache.size = 10 # Auto-shrink on size assignment
  87
  88     for i in range(50): # note: larger than cache size
  89         cache[i] = i
  90
  91     if 0 not in cache: print 'Zero was discarded.'
  92
  93     if 42 in cache:
  94         del cache[42] # Manual deletion
  95
  96     for j in cache:   # iterate (in LRU order)
  97         print j, cache[j] # iterator produces keys, not values
  98     """
  99
 100     class __Node(object):
 101         """Record of a cached value. Not for public consumption."""
 102
 103         def __init__(self, key, obj, timestamp):
 104             object.__init__(self)
 105             self.key = key
 106             self.obj = obj
 107             self.atime = timestamp
 108             self.mtime = self.atime
 109
 110         def __cmp__(self, other):
 111             return cmp(self.atime, other.atime)
 112
 113         def __repr__(self):
 114             return "<%s %s => %s (%s)>" % \
 115                    (self.__class__, self.key, self.obj, \
 116                     time.asctime(time.localtime(self.atime)))
 117
 118     def __init__(self, size=DEFAULT_SIZE):
 119         # Check arguments
 120         if size <= 0:
 121             raise ValueError, size
 122         elif type(size) is not type(0):
 123             raise TypeError, size
 124         object.__init__(self)
 125         self.__heap = []
 126         self.__dict = {}
 127         self.size = size
 128         """Maximum size of the cache.
 129         If more than 'size' elements are added to the cache,
 130         the least-recently-used ones will be discarded."""
 131
 132     def __len__(self):
 133         return len(self.__heap)
 134
 135     def __contains__(self, key):
 136         return self.__dict.has_key(key)
 137
 138     def __setitem__(self, key, obj):
 139         if self.__dict.has_key(key):
 140             node = self.__dict[key]
 141             node.obj = obj
 142             node.atime = time.time()
 143             node.mtime = node.atime
 144             heapify(self.__heap)
 145         else:
 146             # size may have been reset, so we loop
 147             overage = len(self.__heap) - self.size + 1
 148             for i in xrange(overage):
 149                 lru = heappop(self.__heap)
 150                 del self.__dict[lru.key]
 151             node = self.__Node(key, obj, time.time())
 152             self.__dict[key] = node
 153             heappush(self.__heap, node)
 154
 155     def __getitem__(self, key):
 156         if not self.__dict.has_key(key):
 157             raise CacheKeyError(key)
 158         else:
 159             node = self.__dict[key]
 160             node.atime = time.time()
 161             heapify(self.__heap)
 162             return node.obj
 163
 164     def __delitem__(self, key):
 165         if not self.__dict.has_key(key):
 166             raise CacheKeyError(key)
 167         else:
 168             node = self.__dict[key]
 169             del self.__dict[key]
 170             self.__heap.remove(node)
 171             heapify(self.__heap)
 172             return node.obj
 173
 174     def __iter__(self):
 175         copy = self.__heap[:]
 176         while len(copy) > 0:
 177             node = heappop(copy)
 178             yield node.key
 179         raise StopIteration
 180
 181     def __setattr__(self, name, value):
 182         object.__setattr__(self, name, value)
 183         # automagically shrink heap on resize
 184         if name == 'size':
 185             overage = len(self.__heap) - value
 186             for i in xrange(overage):
 187                 lru = heappop(self.__heap)
 188                 del self.__dict[lru.key]
 189
 190     def __repr__(self):
 191         return "<%s (%d elements)>" % (str(self.__class__), len(self.__heap))
 192
 193     def mtime(self, key):
 194         """Return the last modification time for the cache record with key.
 195         May be useful for cache instances where the stored values can get
 196         'stale', such as caching file or network resource contents."""
 197         if not self.__dict.has_key(key):
 198             raise CacheKeyError(key)
 199         else:
 200             node = self.__dict[key]
 201             return node.mtime
 202
 203 if __name__ == "__main__":
 204     cache = LRUCache(25)
 205     print cache
 206     for i in range(50):
 207         cache[i] = str(i)
 208     print cache
 209     if 46 in cache:
 210         del cache[46]
 211     print cache
 212     cache.size = 10
 213     print cache
 214     cache[46] = '46'
 215     print cache
 216     print len(cache)
 217     for c in cache:
 218         print c
 219     print cache
 220     print cache.mtime(46)
 221     for c in cache:
 222         print c