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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
|
########################################################################
# File name: cache.py
# This file is part of: aioxmpp
#
# LICENSE
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU Lesser General Public License as
# published by the Free Software Foundation, either version 3 of the
# License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful, but
# WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
# Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser General Public
# License along with this program. If not, see
# <http://www.gnu.org/licenses/>.
#
########################################################################
"""
:mod:`~aioxmpp.cache` --- Utilities for implementing caches
###########################################################
.. versionadded:: 0.9
This module was added in version 0.9.
.. autoclass:: LRUDict
"""
import collections.abc
class Node:
__slots__ = ("prev", "next_", "key", "value")
def _init_linked_list():
root = Node()
root.prev = root
root.next_ = root
root.key = None
root.value = None
return root
def _remove_node(node):
node.next_.prev = node.prev
node.prev.next_ = node.next_
return node
def _insert_node(before, new_node):
new_node.next_ = before.next_
new_node.next_.prev = new_node
new_node.prev = before
before.next_ = new_node
def _length(node):
# this is used only for testing
cur = node.next_
i = 0
while cur is not node:
i += 1
cur = cur.next_
return i
def _has_consistent_links(node, node_dict=None):
# this is used only for testing
cur = node.next_
if cur.prev is not node:
return False
while cur is not node:
if node_dict is not None and node_dict[cur.key] is not cur:
return False
if cur is not cur.next_.prev:
return False
cur = cur.next_
return True
class LRUDict(collections.abc.MutableMapping):
"""
Size-restricted dictionary with Least Recently Used expiry policy.
.. versionadded:: 0.9
The :class:`LRUDict` supports normal dictionary-style access and implements
:class:`collections.abc.MutableMapping`.
When the :attr:`maxsize` is exceeded, as many entries as needed to get
below the :attr:`maxsize` are removed from the dict. Least recently used
entries are purged first. Setting an entry does *not* count as use!
.. autoattribute:: maxsize
"""
def __init__(self, **kwargs):
super().__init__(**kwargs)
self.__links = {}
self.__root = _init_linked_list()
self.__maxsize = 1
def _test_consistency(self):
"""
This method is only used for testing to assert that the operations
leave the LRUDict in a valid state.
"""
return (_length(self.__root) == len(self.__links) and
_has_consistent_links(self.__root, self.__links))
def _purge(self):
if self.__maxsize is None:
return
while len(self.__links) > self.__maxsize:
link = _remove_node(self.__root.prev)
del self.__links[link.key]
@property
def maxsize(self):
"""
Maximum size of the cache. Changing this property purges overhanging
entries immediately.
If set to :data:`None`, no limit on the number of entries is imposed.
Do **not** use a limit of :data:`None` for data where the `key` is
under control of a remote entity.
Use cases for :data:`None` are those where you only need the explicit
expiry feature, but not the LRU feature.
"""
return self.__maxsize
@maxsize.setter
def maxsize(self, value):
if value is not None and value <= 0:
raise ValueError("maxsize must be positive integer or None")
self.__maxsize = value
self._purge()
def __len__(self):
return len(self.__links)
def __iter__(self):
return iter(self.__links)
def __setitem__(self, key, value):
try:
self.__links[key].value = value
except KeyError:
link = Node()
link.key = key
link.value = value
self.__links[key] = link
_insert_node(self.__root, link)
self._purge()
def __getitem__(self, key):
link = self.__links[key]
_remove_node(link)
_insert_node(self.__root, link)
return link.value
def __delitem__(self, key):
link = self.__links.pop(key)
_remove_node(link)
def clear(self):
self.__links.clear()
self.__root = _init_linked_list()
|
