<s> try : <EOL> from functools import lru_cache <EOL> except ImportError : <EOL> from collections import namedtuple <EOL> from functools import update_wrapper <EOL> from threading import RLock <EOL> _CacheInfo = namedtuple ( "<STR_LIT>" , [ "<STR_LIT>" , "<STR_LIT>" , "<STR_LIT>" , "<STR_LIT>" ] ) <EOL> class _HashedSeq ( list ) : <EOL> __slots__ = '<STR_LIT>' <EOL> def __init__ ( self , tup , hash = hash ) : <EOL> self [ : ] = tup <EOL> self . hashvalue = hash ( tup ) <EOL> def __hash__ ( self ) : <EOL> return self . hashvalue <EOL> def _make_key ( args , kwds , typed , <EOL> kwd_mark = ( object ( ) , ) , <EOL> fasttypes = { int , str , frozenset , type ( None ) } , <EOL> sorted = sorted , tuple = tuple , type = type , len = len ) : <EOL> '<STR_LIT>' <EOL> key = args <EOL> if kwds : <EOL> sorted_items = sorted ( kwds . items ( ) ) <EOL> key += kwd_mark <EOL> for item in sorted_items : <EOL> key += item <EOL> if typed : <EOL> key += tuple ( type ( v ) for v in args ) <EOL> if kwds : <EOL> key += tuple ( type ( v ) for k , v in sorted_items ) <EOL> elif len ( key ) == <NUM_LIT:1> and type ( key [ <NUM_LIT:0> ] ) in fasttypes : <EOL> return key [ <NUM_LIT:0> ] <EOL> return _HashedSeq ( key ) <EOL> def lru_cache ( maxsize = <NUM_LIT:100> , typed = False ) : <EOL> """<STR_LIT>""" <EOL> def decorating_function ( user_function ) : <EOL> cache = dict ( ) <EOL> stats = [ <NUM_LIT:0> , <NUM_LIT:0> ] <EOL> HITS , MISSES = <NUM_LIT:0> , <NUM_LIT:1> <EOL> make_key = _make_key <EOL> cache_get = cache . get <EOL> _len = len <EOL> lock = RLock ( ) <EOL> root = [ ] <EOL> root [ : ] = [ root , root , None , None ] <EOL> nonlocal_root = [ root ] <EOL> PREV , NEXT , KEY , RESULT = <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> <EOL> if maxsize == <NUM_LIT:0> : <EOL> def wrapper ( * args , ** kwds ) : <EOL> result = user_function ( * args , ** kwds ) <EOL> stats [ MISSES ] += <NUM_LIT:1> <EOL> return result <EOL> elif maxsize is None : <EOL> def wrapper ( * args , ** kwds ) : <EOL> key = make_key ( args , kwds , typed ) <EOL> result = cache_get ( key , root ) <EOL> if result is not root : <EOL> stats [ HITS ] += <NUM_LIT:1> <EOL> return result <EOL> result = user_function ( * args , ** kwds ) <EOL> cache [ key ] = result <EOL> stats [ MISSES ] += <NUM_LIT:1> <EOL> return result <EOL> else : <EOL> def wrapper ( * args , ** kwds ) : <EOL> key = make_key ( args , kwds , typed ) if kwds or typed else args <EOL> with lock : <EOL> link = cache_get ( key ) <EOL> if link is not None : <EOL> root , = nonlocal_root <EOL> link_prev , link_next , key , result = link <EOL> link_prev [ NEXT ] = link_next <EOL> link_next [ PREV ] = link_prev <EOL> last = root [ PREV ] <EOL> last [ NEXT ] = root [ PREV ] = link <EOL> link [ PREV ] = last <EOL> link [ NEXT ] = root <EOL> stats [ HITS ] += <NUM_LIT:1> <EOL> return result <EOL> result = user_function ( * args , ** kwds ) <EOL> with lock : <EOL> root , = nonlocal_root <EOL> if key in cache : <EOL> pass <EOL> elif _len ( cache ) >= maxsize : <EOL> oldroot = root <EOL> oldroot [ KEY ] = key <EOL> oldroot [ RESULT ] = result <EOL> root = nonlocal_root [ <NUM_LIT:0> ] = oldroot [ NEXT ] <EOL> oldkey = root [ KEY ] <EOL> oldvalue = root [ RESULT ] <EOL> root [ KEY ] = root [ RESULT ] = None <EOL> del cache [ oldkey ] <EOL> cache [ key ] = oldroot <EOL> else : <EOL> last = root [ PREV ] <EOL> link = [ last , root , key , result ] <EOL> last [ NEXT ] = root [ PREV ] = cache [ key ] = link <EOL> stats [ MISSES ] += <NUM_LIT:1> <EOL> return result <EOL> def cache_info ( ) : <EOL> """<STR_LIT>""" <EOL> with lock : <EOL> return _CacheInfo ( stats [ HITS ] , stats [ MISSES ] , maxsize , len ( cache ) ) <EOL> def cache_clear ( ) : <EOL> """<STR_LIT>""" <EOL> with lock : <EOL> cache . clear ( ) <EOL> root = nonlocal_root [ <NUM_LIT:0> ] <EOL> root [ : ] = [ root , root , None , None ] <EOL> stats [ : ] = [ <NUM_LIT:0> , <NUM_LIT:0> ] <EOL> wrapper . __wrapped__ = user_function <EOL> wrapper . cache_info = cache_info <EOL> wrapper . cache_clear = cache_clear <EOL> return update_wrapper ( wrapper , user_function ) <EOL> return decorating_function </s>
