diff options
Diffstat (limited to 'Lib/functools.py')
| -rw-r--r-- | Lib/functools.py | 203 |
1 files changed, 163 insertions, 40 deletions
diff --git a/Lib/functools.py b/Lib/functools.py index 85ea257..053e44e 100644 --- a/Lib/functools.py +++ b/Lib/functools.py @@ -12,16 +12,25 @@ __all__ = ['update_wrapper', 'wraps', 'WRAPPER_ASSIGNMENTS', 'WRAPPER_UPDATES', 'total_ordering', 'cmp_to_key', 'lru_cache', 'reduce', 'partial'] from _functools import partial, reduce -from collections import OrderedDict, namedtuple +from collections import namedtuple try: - from _thread import allocate_lock as Lock + from _thread import RLock except: - from _dummy_thread import allocate_lock as Lock + class RLock: + 'Dummy reentrant lock for builds without threads' + def __enter__(self): pass + def __exit__(self, exctype, excinst, exctb): pass + + +################################################################################ +### update_wrapper() and wraps() decorator +################################################################################ # update_wrapper() and wraps() are tools to help write # wrapper functions that can handle naive introspection -WRAPPER_ASSIGNMENTS = ('__module__', '__name__', '__doc__', '__annotations__') +WRAPPER_ASSIGNMENTS = ('__module__', '__name__', '__qualname__', '__doc__', + '__annotations__') WRAPPER_UPDATES = ('__dict__',) def update_wrapper(wrapper, wrapped, @@ -65,6 +74,11 @@ def wraps(wrapped, return partial(update_wrapper, wrapped=wrapped, assigned=assigned, updated=updated) + +################################################################################ +### total_ordering class decorator +################################################################################ + def total_ordering(cls): """Class decorator that fills in missing ordering methods""" convert = { @@ -93,6 +107,11 @@ def total_ordering(cls): setattr(cls, opname, opfunc) return cls + +################################################################################ +### cmp_to_key() function converter +################################################################################ + def cmp_to_key(mycmp): """Convert a cmp= function into a key= function""" class K(object): @@ -114,79 +133,181 @@ def cmp_to_key(mycmp): __hash__ = None return K -_CacheInfo = namedtuple("CacheInfo", "hits misses maxsize currsize") +try: + from _functools import cmp_to_key +except ImportError: + pass + + +################################################################################ +### LRU Cache function decorator +################################################################################ + +_CacheInfo = namedtuple("CacheInfo", ["hits", "misses", "maxsize", "currsize"]) + +class _HashedSeq(list): + """ This class guarantees that hash() will be called no more than once + per element. This is important because the lru_cache() will hash + the key multiple times on a cache miss. + + """ + + __slots__ = 'hashvalue' + + def __init__(self, tup, hash=hash): + self[:] = tup + self.hashvalue = hash(tup) + + def __hash__(self): + return self.hashvalue + +def _make_key(args, kwds, typed, + kwd_mark = (object(),), + fasttypes = {int, str, frozenset, type(None)}, + sorted=sorted, tuple=tuple, type=type, len=len): + """Make a cache key from optionally typed positional and keyword arguments -def lru_cache(maxsize=100): + The key is constructed in a way that is flat as possible rather than + as a nested structure that would take more memory. + + If there is only a single argument and its data type is known to cache + its hash value, then that argument is returned without a wrapper. This + saves space and improves lookup speed. + + """ + key = args + if kwds: + sorted_items = sorted(kwds.items()) + key += kwd_mark + for item in sorted_items: + key += item + if typed: + key += tuple(type(v) for v in args) + if kwds: + key += tuple(type(v) for k, v in sorted_items) + elif len(key) == 1 and type(key[0]) in fasttypes: + return key[0] + return _HashedSeq(key) + +def lru_cache(maxsize=128, typed=False): """Least-recently-used cache decorator. If *maxsize* is set to None, the LRU features are disabled and the cache can grow without bound. + If *typed* is True, arguments of different types will be cached separately. + For example, f(3.0) and f(3) will be treated as distinct calls with + distinct results. + Arguments to the cached function must be hashable. - View the cache statistics named tuple (hits, misses, maxsize, currsize) with - f.cache_info(). Clear the cache and statistics with f.cache_clear(). + View the cache statistics named tuple (hits, misses, maxsize, currsize) + with f.cache_info(). Clear the cache and statistics with f.cache_clear(). Access the underlying function with f.__wrapped__. See: http://en.wikipedia.org/wiki/Cache_algorithms#Least_Recently_Used """ + # Users should only access the lru_cache through its public API: # cache_info, cache_clear, and f.__wrapped__ # The internals of the lru_cache are encapsulated for thread safety and # to allow the implementation to change (including a possible C version). - def decorating_function(user_function, - tuple=tuple, sorted=sorted, len=len, KeyError=KeyError): + # Constants shared by all lru cache instances: + sentinel = object() # unique object used to signal cache misses + make_key = _make_key # build a key from the function arguments + PREV, NEXT, KEY, RESULT = 0, 1, 2, 3 # names for the link fields + + def decorating_function(user_function): + cache = {} hits = misses = 0 - kwd_mark = (object(),) # separates positional and keyword args - lock = Lock() # needed because OrderedDict isn't threadsafe + full = False + cache_get = cache.get # bound method to lookup a key or return None + lock = RLock() # because linkedlist updates aren't threadsafe + root = [] # root of the circular doubly linked list + root[:] = [root, root, None, None] # initialize by pointing to self - if maxsize is None: - cache = dict() # simple cache without ordering or size limit + if maxsize == 0: - @wraps(user_function) def wrapper(*args, **kwds): + # No caching -- just a statistics update after a successful call + nonlocal misses + result = user_function(*args, **kwds) + misses += 1 + return result + + elif maxsize is None: + + def wrapper(*args, **kwds): + # Simple caching without ordering or size limit nonlocal hits, misses - key = args - if kwds: - key += kwd_mark + tuple(sorted(kwds.items())) - try: - result = cache[key] + key = make_key(args, kwds, typed) + result = cache_get(key, sentinel) + if result is not sentinel: hits += 1 return result - except KeyError: - pass result = user_function(*args, **kwds) cache[key] = result misses += 1 return result + else: - cache = OrderedDict() # ordered least recent to most recent - cache_popitem = cache.popitem - cache_renew = cache.move_to_end - @wraps(user_function) def wrapper(*args, **kwds): - nonlocal hits, misses - key = args - if kwds: - key += kwd_mark + tuple(sorted(kwds.items())) + # Size limited caching that tracks accesses by recency + nonlocal root, hits, misses, full + key = make_key(args, kwds, typed) with lock: - try: - result = cache[key] - cache_renew(key) # record recent use of this key + link = cache_get(key) + if link is not None: + # Move the link to the front of the circular queue + link_prev, link_next, _key, result = link + link_prev[NEXT] = link_next + link_next[PREV] = link_prev + last = root[PREV] + last[NEXT] = root[PREV] = link + link[PREV] = last + link[NEXT] = root hits += 1 return result - except KeyError: - pass result = user_function(*args, **kwds) with lock: - cache[key] = result # record recent use of this key + if key in cache: + # Getting here means that this same key was added to the + # cache while the lock was released. Since the link + # update is already done, we need only return the + # computed result and update the count of misses. + pass + elif full: + # Use the old root to store the new key and result. + oldroot = root + oldroot[KEY] = key + oldroot[RESULT] = result + # Empty the oldest link and make it the new root. + # Keep a reference to the old key and old result to + # prevent their ref counts from going to zero during the + # update. That will prevent potentially arbitrary object + # clean-up code (i.e. __del__) from running while we're + # still adjusting the links. + root = oldroot[NEXT] + oldkey = root[KEY] + oldresult = root[RESULT] + root[KEY] = root[RESULT] = None + # Now update the cache dictionary. + del cache[oldkey] + # Save the potentially reentrant cache[key] assignment + # for last, after the root and links have been put in + # a consistent state. + cache[key] = oldroot + else: + # Put result in a new link at the front of the queue. + last = root[PREV] + link = [last, root, key, result] + last[NEXT] = root[PREV] = cache[key] = link + full = (len(cache) >= maxsize) misses += 1 - if len(cache) > maxsize: - cache_popitem(0) # purge least recently used cache entry return result def cache_info(): @@ -196,13 +317,15 @@ def lru_cache(maxsize=100): def cache_clear(): """Clear the cache and cache statistics""" - nonlocal hits, misses + nonlocal hits, misses, full with lock: cache.clear() + root[:] = [root, root, None, None] hits = misses = 0 + full = False wrapper.cache_info = cache_info wrapper.cache_clear = cache_clear - return wrapper + return update_wrapper(wrapper, user_function) return decorating_function |