/usr/lib/python3/dist-packages/cachetools/lru.py is in python3-cachetools 1.1.5-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | from .cache import Cache
class _Link(object):
__slots__ = 'key', 'prev', 'next'
def __getstate__(self):
if hasattr(self, 'key'):
return (self.key,)
else:
return None
def __setstate__(self, state):
self.key, = state
def insert(self, next):
self.next = next
self.prev = prev = next.prev
prev.next = next.prev = self
def unlink(self):
next = self.next
prev = self.prev
prev.next = next
next.prev = prev
class LRUCache(Cache):
"""Least Recently Used (LRU) cache implementation."""
def __init__(self, maxsize, missing=None, getsizeof=None):
Cache.__init__(self, maxsize, missing, getsizeof)
self.__root = root = _Link()
root.prev = root.next = root
self.__links = {}
def __repr__(self, cache_getitem=Cache.__getitem__):
# prevent item reordering
return '%s(%r, maxsize=%d, currsize=%d)' % (
self.__class__.__name__,
[(key, cache_getitem(self, key)) for key in self],
self.maxsize,
self.currsize,
)
def __getitem__(self, key, cache_getitem=Cache.__getitem__):
value = cache_getitem(self, key)
link = self.__links[key]
link.unlink()
link.insert(self.__root)
return value
def __setitem__(self, key, value, cache_setitem=Cache.__setitem__):
cache_setitem(self, key, value)
try:
link = self.__links[key]
except KeyError:
link = self.__links[key] = _Link()
else:
link.unlink()
link.key = key
link.insert(self.__root)
def __delitem__(self, key, cache_delitem=Cache.__delitem__):
cache_delitem(self, key)
links = self.__links
links[key].unlink()
del links[key]
def __getstate__(self):
state = self.__dict__.copy()
root = self.__root
links = state['__links'] = [root]
link = root.next
while link is not root:
links.append(link)
link = link.next
return state
def __setstate__(self, state):
links = state.pop('__links')
count = len(links)
for index, link in enumerate(links):
link.prev = links[index - 1]
link.next = links[(index + 1) % count]
self.__dict__.update(state)
def popitem(self):
"""Remove and return the `(key, value)` pair least recently used."""
root = self.__root
link = root.next
if link is root:
raise KeyError('%s is empty' % self.__class__.__name__)
key = link.key
return (key, self.pop(key))
|