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
|
cdef object _LRU_MARKER = object()
@cython.final
cdef class LruCache:
cdef:
object _dict
int _maxsize
object _dict_move_to_end
object _dict_get
# We use an OrderedDict for LRU implementation. Operations:
#
# * We use a simple `__setitem__` to push a new entry:
# `entries[key] = new_entry`
# That will push `new_entry` to the *end* of the entries dict.
#
# * When we have a cache hit, we call
# `entries.move_to_end(key, last=True)`
# to move the entry to the *end* of the entries dict.
#
# * When we need to remove entries to maintain `max_size`, we call
# `entries.popitem(last=False)`
# to remove an entry from the *beginning* of the entries dict.
#
# So new entries and hits are always promoted to the end of the
# entries dict, whereas the unused one will group in the
# beginning of it.
def __init__(self, *, maxsize):
if maxsize <= 0:
raise ValueError(
f'maxsize is expected to be greater than 0, got {maxsize}')
self._dict = col_OrderedDict()
self._dict_move_to_end = self._dict.move_to_end
self._dict_get = self._dict.get
self._maxsize = maxsize
cdef get(self, key, default):
o = self._dict_get(key, _LRU_MARKER)
if o is _LRU_MARKER:
return default
self._dict_move_to_end(key) # last=True
return o
cdef inline needs_cleanup(self):
return len(self._dict) > self._maxsize
cdef inline cleanup_one(self):
k, _ = self._dict.popitem(last=False)
return k
def __getitem__(self, key):
o = self._dict[key]
self._dict_move_to_end(key) # last=True
return o
def __setitem__(self, key, o):
if key in self._dict:
self._dict[key] = o
self._dict_move_to_end(key) # last=True
else:
self._dict[key] = o
while self.needs_cleanup():
self.cleanup_one()
def __delitem__(self, key):
del self._dict[key]
def __contains__(self, key):
return key in self._dict
def __len__(self):
return len(self._dict)
def __iter__(self):
return iter(self._dict)
|
