Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/repoze/lru/__init__.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
1 """ LRU caching class and decorator """
2 from abc import abstractmethod
3 from abc import ABCMeta
4
5 import threading
6 import time
7 import uuid
8
9
10 _MARKER = object()
11 # By default, expire items after 2**60 seconds. This fits into 64 bit
12 # integers and is close enough to "never" for practical purposes.
13 _DEFAULT_TIMEOUT = 2 ** 60
14
15
16 class Cache(object):
17 __metaclass__ = ABCMeta
18
19 @abstractmethod
20 def clear(self):
21 """Remove all entries from the cache"""
22
23 @abstractmethod
24 def get(self, key, default=None):
25 """Return value for key. If not in cache, return default"""
26
27 @abstractmethod
28 def put(self, key, val):
29 """Add key to the cache with value val"""
30
31 @abstractmethod
32 def invalidate(self, key):
33 """Remove key from the cache"""
34
35
36 class UnboundedCache(Cache):
37 """
38 a simple unbounded cache backed by a dictionary
39 """
40
41 def __init__(self):
42 self._data = dict()
43
44 def get(self, key, default=None):
45 return self._data.get(key, default)
46
47 def clear(self):
48 self._data.clear()
49
50 def invalidate(self, key):
51 try:
52 del self._data[key]
53 except KeyError:
54 pass
55
56 def put(self, key, val):
57 self._data[key] = val
58
59
60 class LRUCache(Cache):
61 """ Implements a pseudo-LRU algorithm (CLOCK)
62
63 The Clock algorithm is not kept strictly to improve performance, e.g. to
64 allow get() and invalidate() to work without acquiring the lock.
65 """
66 def __init__(self, size):
67 size = int(size)
68 if size < 1:
69 raise ValueError('size must be >0')
70 self.size = size
71 self.lock = threading.Lock()
72 self.hand = 0
73 self.maxpos = size - 1
74 self.clock_keys = None
75 self.clock_refs = None
76 self.data = None
77 self.evictions = 0
78 self.hits = 0
79 self.misses = 0
80 self.lookups = 0
81 self.clear()
82
83 def clear(self):
84 """Remove all entries from the cache"""
85 with self.lock:
86 # If really clear()ing a full cache, clean up self.data first to
87 # give garbage collection a chance to reduce memorey usage.
88 # Instantiating "[_MARKER] * size" will temporarily have 2 lists
89 # in memory -> high peak memory usage for tiny amount of time.
90 # With self.data already clear, that peak should not exceed what
91 # we normally use.
92 self.data = {}
93 size = self.size
94 self.clock_keys = [_MARKER] * size
95 self.clock_refs = [False] * size
96 self.hand = 0
97 self.evictions = 0
98 self.hits = 0
99 self.misses = 0
100 self.lookups = 0
101
102 def get(self, key, default=None):
103 """Return value for key. If not in cache, return default"""
104 self.lookups += 1
105 try:
106 pos, val = self.data[key]
107 self.hits += 1
108 except KeyError:
109 self.misses += 1
110 return default
111 self.clock_refs[pos] = True
112 return val
113
114 def put(self, key, val):
115 """Add key to the cache with value val"""
116 # These do not change or they are just references, no need for locking.
117 maxpos = self.maxpos
118 clock_refs = self.clock_refs
119 clock_keys = self.clock_keys
120 data = self.data
121
122 with self.lock:
123 entry = data.get(key)
124 if entry is not None:
125 # We already have key. Only make sure data is up to date and
126 # to remember that it was used.
127 pos, old_val = entry
128 if old_val is not val:
129 data[key] = (pos, val)
130 self.clock_refs[pos] = True
131 return
132 # else: key is not yet in cache. Search place to insert it.
133
134 hand = self.hand
135 count = 0
136 max_count = 107
137 while 1:
138 ref = clock_refs[hand]
139 if ref == True:
140 clock_refs[hand] = False
141 hand += 1
142 if hand > maxpos:
143 hand = 0
144
145 count += 1
146 if count >= max_count:
147 # We have been searching long enough. Force eviction of
148 # next entry, no matter what its status is.
149 clock_refs[hand] = False
150 else:
151 oldkey = clock_keys[hand]
152 # Maybe oldkey was not in self.data to begin with. If it
153 # was, self.invalidate() in another thread might have
154 # already removed it. del() would raise KeyError, so pop().
155 oldentry = data.pop(oldkey, _MARKER)
156 if oldentry is not _MARKER:
157 self.evictions += 1
158 clock_keys[hand] = key
159 clock_refs[hand] = True
160 data[key] = (hand, val)
161 hand += 1
162 if hand > maxpos:
163 hand = 0
164 self.hand = hand
165 break
166
167 def invalidate(self, key):
168 """Remove key from the cache"""
169 # pop with default arg will not raise KeyError
170 entry = self.data.pop(key, _MARKER)
171 if entry is not _MARKER:
172 # We have no lock, but worst thing that can happen is that we
173 # set another key's entry to False.
174 self.clock_refs[entry[0]] = False
175 # else: key was not in cache. Nothing to do.
176
177
178 class ExpiringLRUCache(Cache):
179 """ Implements a pseudo-LRU algorithm (CLOCK) with expiration times
180
181 The Clock algorithm is not kept strictly to improve performance, e.g. to
182 allow get() and invalidate() to work without acquiring the lock.
183 """
184 def __init__(self, size, default_timeout=_DEFAULT_TIMEOUT):
185 self.default_timeout = default_timeout
186 size = int(size)
187 if size < 1:
188 raise ValueError('size must be >0')
189 self.size = size
190 self.lock = threading.Lock()
191 self.hand = 0
192 self.maxpos = size - 1
193 self.clock_keys = None
194 self.clock_refs = None
195 self.data = None
196 self.evictions = 0
197 self.hits = 0
198 self.misses = 0
199 self.lookups = 0
200 self.clear()
201
202 def clear(self):
203 """Remove all entries from the cache"""
204 with self.lock:
205 # If really clear()ing a full cache, clean up self.data first to
206 # give garbage collection a chance to reduce memorey usage.
207 # Instantiating "[_MARKER] * size" will temporarily have 2 lists
208 # in memory -> high peak memory usage for tiny amount of time.
209 # With self.data already clear, that peak should not exceed what
210 # we normally use.
211 # self.data contains (pos, val, expires) triplets
212 self.data = {}
213 size = self.size
214 self.clock_keys = [_MARKER] * size
215 self.clock_refs = [False] * size
216 self.hand = 0
217 self.evictions = 0
218 self.hits = 0
219 self.misses = 0
220 self.lookups = 0
221
222 def get(self, key, default=None):
223 """Return value for key. If not in cache or expired, return default"""
224 self.lookups += 1
225 try:
226 pos, val, expires = self.data[key]
227 except KeyError:
228 self.misses += 1
229 return default
230 if expires > time.time():
231 # cache entry still valid
232 self.hits += 1
233 self.clock_refs[pos] = True
234 return val
235 else:
236 # cache entry has expired. Make sure the space in the cache can
237 # be recycled soon.
238 self.misses += 1
239 self.clock_refs[pos] = False
240 return default
241
242 def put(self, key, val, timeout=None):
243 """Add key to the cache with value val
244
245 key will expire in $timeout seconds. If key is already in cache, val
246 and timeout will be updated.
247 """
248 # These do not change or they are just references, no need for locking.
249 maxpos = self.maxpos
250 clock_refs = self.clock_refs
251 clock_keys = self.clock_keys
252 data = self.data
253 lock = self.lock
254 if timeout is None:
255 timeout = self.default_timeout
256
257 with self.lock:
258 entry = data.get(key)
259 if entry is not None:
260 # We already have key. Only make sure data is up to date and
261 # to remember that it was used.
262 pos = entry[0]
263 data[key] = (pos, val, time.time() + timeout)
264 clock_refs[pos] = True
265 return
266 # else: key is not yet in cache. Search place to insert it.
267
268 hand = self.hand
269 count = 0
270 max_count = 107
271 while 1:
272 ref = clock_refs[hand]
273 if ref == True:
274 clock_refs[hand] = False
275 hand += 1
276 if hand > maxpos:
277 hand = 0
278
279 count += 1
280 if count >= max_count:
281 # We have been searching long enough. Force eviction of
282 # next entry, no matter what its status is.
283 clock_refs[hand] = False
284 else:
285 oldkey = clock_keys[hand]
286 # Maybe oldkey was not in self.data to begin with. If it
287 # was, self.invalidate() in another thread might have
288 # already removed it. del() would raise KeyError, so pop().
289 oldentry = data.pop(oldkey, _MARKER)
290 if oldentry is not _MARKER:
291 self.evictions += 1
292 clock_keys[hand] = key
293 clock_refs[hand] = True
294 data[key] = (hand, val, time.time() + timeout)
295 hand += 1
296 if hand > maxpos:
297 hand = 0
298 self.hand = hand
299 break
300
301 def invalidate(self, key):
302 """Remove key from the cache"""
303 # pop with default arg will not raise KeyError
304 entry = self.data.pop(key, _MARKER)
305 if entry is not _MARKER:
306 # We have no lock, but worst thing that can happen is that we
307 # set another key's entry to False.
308 self.clock_refs[entry[0]] = False
309 # else: key was not in cache. Nothing to do.
310
311
312 class lru_cache(object):
313 """ Decorator for LRU-cached function
314
315 timeout parameter specifies after how many seconds a cached entry should
316 be considered invalid.
317 """
318 def __init__(self,
319 maxsize,
320 cache=None, # cache is an arg to serve tests
321 timeout=None,
322 ignore_unhashable_args=False):
323 if cache is None:
324 if maxsize is None:
325 cache = UnboundedCache()
326 elif timeout is None:
327 cache = LRUCache(maxsize)
328 else:
329 cache = ExpiringLRUCache(maxsize, default_timeout=timeout)
330 self.cache = cache
331 self._ignore_unhashable_args = ignore_unhashable_args
332
333 def __call__(self, func):
334 cache = self.cache
335 marker = _MARKER
336
337 def cached_wrapper(*args, **kwargs):
338 try:
339 key = (args, frozenset(kwargs.items())) if kwargs else args
340 except TypeError as e:
341 if self._ignore_unhashable_args:
342 return func(*args, **kwargs)
343 else:
344 raise e
345 else:
346 val = cache.get(key, marker)
347 if val is marker:
348 val = func(*args, **kwargs)
349 cache.put(key, val)
350 return val
351
352 def _maybe_copy(source, target, attr):
353 value = getattr(source, attr, source)
354 if value is not source:
355 setattr(target, attr, value)
356
357 _maybe_copy(func, cached_wrapper, '__module__')
358 _maybe_copy(func, cached_wrapper, '__name__')
359 _maybe_copy(func, cached_wrapper, '__doc__')
360 cached_wrapper._cache = cache
361 return cached_wrapper
362
363
364 class CacheMaker(object):
365 """Generates decorators that can be cleared later
366 """
367 def __init__(self, maxsize=None, timeout=_DEFAULT_TIMEOUT):
368 """Create cache decorator factory.
369
370 - maxsize : the default size for created caches.
371
372 - timeout : the defaut expiraiton time for created caches.
373 """
374 self._maxsize = maxsize
375 self._timeout = timeout
376 self._cache = {}
377
378 def _resolve_setting(self, name=None, maxsize=None, timeout=None):
379 if name is None:
380 while True:
381 name = str(uuid.uuid4())
382 ## the probability of collision is so low ....
383 if name not in self._cache: # pragma: NO COVER
384 break
385
386 if name in self._cache:
387 raise KeyError("cache %s already in use" % name)
388
389 if maxsize is None:
390 maxsize = self._maxsize
391
392 if maxsize is None:
393 raise ValueError("Cache must have a maxsize set")
394
395 if timeout is None:
396 timeout = self._timeout
397
398 return name, maxsize, timeout
399
400 def memoized(self, name=None):
401 name, maxsize, _ = self._resolve_setting(name, 0)
402 cache = self._cache[name] = UnboundedCache()
403 return lru_cache(None, cache)
404
405 def lrucache(self, name=None, maxsize=None):
406 """Named arguments:
407
408 - name (optional) is a string, and should be unique amongst all caches
409
410 - maxsize (optional) is an int, overriding any default value set by
411 the constructor
412 """
413 name, maxsize, _ = self._resolve_setting(name, maxsize)
414 cache = self._cache[name] = LRUCache(maxsize)
415 return lru_cache(maxsize, cache)
416
417 def expiring_lrucache(self, name=None, maxsize=None, timeout=None):
418 """Named arguments:
419
420 - name (optional) is a string, and should be unique amongst all caches
421
422 - maxsize (optional) is an int, overriding any default value set by
423 the constructor
424
425 - timeout (optional) is an int, overriding any default value set by
426 the constructor or the default value (%d seconds)
427 """ % _DEFAULT_TIMEOUT
428 name, maxsize, timeout = self._resolve_setting(name, maxsize, timeout)
429 cache = self._cache[name] = ExpiringLRUCache(maxsize, timeout)
430 return lru_cache(maxsize, cache, timeout)
431
432 def clear(self, *names):
433 """Clear the given cache(s).
434
435 If no 'names' are passed, clear all caches.
436 """
437 if len(names) == 0:
438 names = self._cache.keys()
439
440 for name in names:
441 self._cache[name].clear()