<s> """<STR_LIT>""" <EOL> import copy <EOL> import threading <EOL> from uuid import uuid4 <EOL> __author__ = '<STR_LIT>' <EOL> __all__ = [ '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' ] <EOL> class Error ( Exception ) : <EOL> """<STR_LIT>""" <EOL> pass <EOL> class NodeNotFoundError ( Error ) : <EOL> """<STR_LIT>""" <EOL> pass <EOL> class SetError ( Error ) : <EOL> """<STR_LIT>""" <EOL> pass <EOL> class AddError ( Error ) : <EOL> """<STR_LIT>""" <EOL> pass <EOL> class _Node ( object ) : <EOL> def __init__ ( self , uuid = None ) : <EOL> self . uuid = uuid or uuid4 ( ) . hex <EOL> self . value = None <EOL> self . next_uuid = None <EOL> self . prev_uuid = None <EOL> def __getstate__ ( self ) : <EOL> state = self . __dict__ . copy ( ) <EOL> del state [ '<STR_LIT>' ] <EOL> return state <EOL> def __eq__ ( self , other ) : <EOL> return self . __dict__ == other . __dict__ <EOL> def __ne__ ( self , other ) : <EOL> return self . __dict__ != other . __dict__ <EOL> class _DequeClient : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , memcache_client ) : <EOL> self . mc = memcache_client <EOL> def SaveNode ( self , node ) : <EOL> if not self . mc . set ( node . uuid , node ) : <EOL> raise SetError <EOL> def AddNode ( self , node ) : <EOL> if not self . mc . add ( node . uuid , node ) : <EOL> raise AddError <EOL> def DeleteNode ( self , node ) : <EOL> self . mc . delete ( node . uuid ) <EOL> def LoadNodeFromUuid ( self , uuid ) : <EOL> node = self . mc . gets ( uuid ) <EOL> if node is None : <EOL> raise NodeNotFoundError <EOL> node . uuid = uuid <EOL> return node <EOL> def Cas ( self , node , attributes , update_on_success = False ) : <EOL> """<STR_LIT>""" <EOL> new_node = copy . copy ( node ) <EOL> new_node . uuid = node . uuid <EOL> new_node . __dict__ . update ( attributes ) <EOL> result = self . mc . cas ( node . uuid , new_node ) <EOL> if result and update_on_success : <EOL> node . __dict__ . update ( attributes ) <EOL> return result <EOL> class _Status ( object ) : <EOL> STABLE = '<STR_LIT>' <EOL> R_PUSH = '<STR_LIT>' <EOL> L_PUSH = '<STR_LIT>' <EOL> class deque ( object ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , deque_client , uuid ) : <EOL> """<STR_LIT>""" <EOL> self . client = deque_client <EOL> self . anchor_uuid = uuid <EOL> self . thread_local = threading . local ( ) <EOL> self . thread_local . last_missing_node = None <EOL> @ classmethod <EOL> def create ( cls , memcache_client , name = None ) : <EOL> """<STR_LIT>""" <EOL> client = _DequeClient ( memcache_client ) <EOL> anchor = _Node ( name ) <EOL> anchor . value = _Status . STABLE <EOL> client . AddNode ( anchor ) <EOL> return cls ( client , anchor . uuid ) <EOL> @ classmethod <EOL> def bind ( cls , memcache_client , name ) : <EOL> """<STR_LIT>""" <EOL> return cls ( _DequeClient ( memcache_client ) , name ) <EOL> @ property <EOL> def name ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . anchor_uuid <EOL> def _SafeLoadNodeFromUuid ( self , uuid ) : <EOL> """<STR_LIT>""" <EOL> try : <EOL> return self . client . LoadNodeFromUuid ( uuid ) <EOL> except NodeNotFoundError , e : <EOL> if uuid == self . thread_local . last_missing_node : <EOL> raise e <EOL> else : <EOL> self . thread_local . last_missing_node = uuid <EOL> def _Stabilize ( self , anchor , last = None ) : <EOL> """<STR_LIT>""" <EOL> is_right = ( anchor . value == _Status . R_PUSH ) <EOL> link , reverse_link = ( '<STR_LIT>' , '<STR_LIT>' ) [ : : <NUM_LIT:1> if is_right else - <NUM_LIT:1> ] <EOL> if last is None : <EOL> last = self . _SafeLoadNodeFromUuid ( getattr ( anchor , link ) ) <EOL> if last is None : <EOL> return <EOL> penultimate = self . _SafeLoadNodeFromUuid ( getattr ( last , reverse_link ) ) <EOL> if penultimate is None : <EOL> return <EOL> if getattr ( penultimate , link ) != last . uuid : <EOL> if self . client . LoadNodeFromUuid ( anchor . uuid ) != anchor : <EOL> return <EOL> if not self . client . Cas ( penultimate , { link : last . uuid } ) : <EOL> return <EOL> self . client . Cas ( anchor , { '<STR_LIT:value>' : _Status . STABLE } ) <EOL> def _PushCommon ( self , value , target_status ) : <EOL> node = _Node ( ) <EOL> node . value = value <EOL> while True : <EOL> anchor = self . client . LoadNodeFromUuid ( self . anchor_uuid ) <EOL> if anchor . next_uuid is None : <EOL> self . client . SaveNode ( node ) <EOL> if self . client . Cas ( anchor , <EOL> { '<STR_LIT>' : node . uuid , '<STR_LIT>' : node . uuid } ) : <EOL> break <EOL> elif anchor . value == _Status . STABLE : <EOL> node . prev_uuid = anchor . next_uuid <EOL> node . next_uuid = anchor . prev_uuid <EOL> self . client . SaveNode ( node ) <EOL> link = '<STR_LIT>' if target_status == _Status . R_PUSH else '<STR_LIT>' <EOL> if self . client . Cas ( anchor , <EOL> { link : node . uuid , '<STR_LIT:value>' : target_status } , <EOL> update_on_success = True ) : <EOL> self . _Stabilize ( anchor , node ) <EOL> break <EOL> else : <EOL> self . _Stabilize ( anchor ) <EOL> def append ( self , value ) : <EOL> """<STR_LIT>""" <EOL> self . _PushCommon ( value , _Status . R_PUSH ) <EOL> def appendleft ( self , value ) : <EOL> """<STR_LIT>""" <EOL> self . _PushCommon ( value , _Status . L_PUSH ) <EOL> def _PopCommon ( self , is_right ) : <EOL> link , reverse_link = ( '<STR_LIT>' , '<STR_LIT>' ) [ : : <NUM_LIT:1> if is_right else - <NUM_LIT:1> ] <EOL> while True : <EOL> anchor = self . client . LoadNodeFromUuid ( self . anchor_uuid ) <EOL> node_uuid = getattr ( anchor , link ) <EOL> if node_uuid is None : <EOL> raise IndexError <EOL> is_single_item = anchor . prev_uuid == anchor . next_uuid <EOL> if not ( is_single_item or anchor . value == _Status . STABLE ) : <EOL> self . _Stabilize ( anchor ) <EOL> continue <EOL> node = self . _SafeLoadNodeFromUuid ( node_uuid ) <EOL> if node is None : <EOL> continue <EOL> if self . client . Cas ( anchor , <EOL> { '<STR_LIT>' : None , '<STR_LIT>' : None } if is_single_item <EOL> else { link : getattr ( node , reverse_link ) } ) : <EOL> break <EOL> self . client . DeleteNode ( node ) <EOL> return node . value <EOL> def pop ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . _PopCommon ( is_right = True ) <EOL> def popleft ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . _PopCommon ( is_right = False ) <EOL> def _last_iter ( iterable ) : <EOL> """<STR_LIT>""" <EOL> it = iter ( iterable ) <EOL> last = it . next ( ) <EOL> for val in it : <EOL> yield last , False <EOL> last = val <EOL> yield last , True <EOL> class _McasStatus ( object ) : <EOL> UNDECIDED = '<STR_LIT>' <EOL> SUCCESSFUL = '<STR_LIT>' <EOL> FAILED = '<STR_LIT>' <EOL> class Entry ( object ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , key , value , cas_id ) : <EOL> self . _key = key <EOL> self . _value = value <EOL> self . _cas_id = cas_id <EOL> @ property <EOL> def key ( self ) : <EOL> return self . _key <EOL> @ property <EOL> def value ( self ) : <EOL> return self . _value <EOL> @ property <EOL> def cas_id ( self ) : <EOL> return self . _cas_id <EOL> class _McasRecord ( object ) : <EOL> def __init__ ( self , mc , entries ) : <EOL> self . uuid = uuid4 ( ) . hex <EOL> self . status = _McasStatus . UNDECIDED <EOL> self . items = sorted ( ( entry . key , entry . value , entry . cas_id , new_value ) for <EOL> entry , new_value in entries ) <EOL> def __getstate__ ( self ) : <EOL> state = self . __dict__ . copy ( ) <EOL> del state [ '<STR_LIT>' ] <EOL> return state <EOL> def __eq__ ( self , other ) : <EOL> return self . __dict__ == other . __dict__ <EOL> def __ne__ ( self , other ) : <EOL> return self . __dict__ != other . __dict__ <EOL> REF_SENTINEL = '<STR_LIT>' <EOL> def make_ref ( self ) : <EOL> """<STR_LIT>""" <EOL> return self . REF_SENTINEL + self . uuid <EOL> @ classmethod <EOL> def deref ( cls , dc , value , last_missing_value ) : <EOL> """<STR_LIT>""" <EOL> mcas_record , is_missing = None , False <EOL> if type ( value ) == str and value . startswith ( cls . REF_SENTINEL ) : <EOL> try : <EOL> mcas_record = dc . LoadNodeFromUuid ( value [ len ( cls . REF_SENTINEL ) : ] ) <EOL> except NodeNotFoundError , e : <EOL> if ( value == last_missing_value ) : <EOL> raise e <EOL> else : <EOL> is_missing = True <EOL> return mcas_record , is_missing <EOL> def _get_cas_ids ( mc ) : <EOL> """<STR_LIT>""" <EOL> cas_ids = getattr ( mc , '<STR_LIT>' , None ) <EOL> if cas_ids == None : <EOL> cas_ids = getattr ( mc , '<STR_LIT>' , None ) <EOL> assert cas_ids != None , '<STR_LIT>' <EOL> return cas_ids <EOL> def _explicit_cas ( mc , key , value , cas_id ) : <EOL> """<STR_LIT>""" <EOL> cas_ids = _get_cas_ids ( mc ) <EOL> original_id = cas_ids . get ( key ) <EOL> cas_ids [ key ] = cas_id <EOL> result = mc . cas ( key , value ) <EOL> if original_id == None : <EOL> del cas_ids [ key ] <EOL> else : <EOL> cas_ids [ key ] = original_id <EOL> return result <EOL> class _ReleaseMcas ( Exception ) : <EOL> pass <EOL> def _mcas_help ( dc , mcas_record , is_originator = False ) : <EOL> """<STR_LIT>""" <EOL> result_status = None <EOL> mcas_ref = mcas_record . make_ref ( ) <EOL> try : <EOL> if mcas_record . status != _McasStatus . UNDECIDED : <EOL> raise _ReleaseMcas <EOL> for key , _ , cas_id , _ in mcas_record . items : <EOL> last_missing_mcas_ref = None <EOL> while True : <EOL> if _explicit_cas ( dc . mc , key , mcas_ref , cas_id ) : <EOL> break <EOL> location = dc . mc . get ( key ) <EOL> if location == mcas_ref : <EOL> break <EOL> else : <EOL> nested_mcas_record , is_missing = _McasRecord . deref ( dc , location , <EOL> last_missing_mcas_ref ) <EOL> if is_missing : <EOL> last_missing_mcas_ref = location <EOL> continue <EOL> elif nested_mcas_record : <EOL> _mcas_help ( dc , nested_mcas_record ) <EOL> else : <EOL> result_status = _McasStatus . FAILED <EOL> raise _ReleaseMcas <EOL> result_status = _McasStatus . SUCCESSFUL <EOL> except _ReleaseMcas : <EOL> pass <EOL> if result_status is not None : <EOL> if not dc . Cas ( mcas_record , { '<STR_LIT:status>' : result_status } , <EOL> update_on_success = True ) : <EOL> try : <EOL> mcas_record = dc . LoadNodeFromUuid ( mcas_record . uuid ) <EOL> except NodeNotFoundError : <EOL> if is_originator : <EOL> raise <EOL> else : <EOL> return <EOL> is_success = mcas_record . status == _McasStatus . SUCCESSFUL <EOL> for ( key , value , _ , new_value ) , is_last in _last_iter ( mcas_record . items ) : <EOL> location = dc . mc . gets ( key ) <EOL> if location == mcas_ref : <EOL> if ( dc . mc . cas ( key , new_value if is_success else value ) and is_last ) : <EOL> if is_originator : <EOL> dc . DeleteNode ( mcas_record ) <EOL> if is_originator : <EOL> return is_success <EOL> def mcas ( mc , entries ) : <EOL> """<STR_LIT>""" <EOL> dc = _DequeClient ( mc ) <EOL> mcas_record = _McasRecord ( mc , entries ) <EOL> dc . AddNode ( mcas_record ) <EOL> dc . mc . gets ( mcas_record . uuid ) <EOL> return _mcas_help ( dc , mcas_record , is_originator = True ) <EOL> def mcas_get ( mc , key ) : <EOL> """<STR_LIT>""" <EOL> dc = _DequeClient ( mc ) <EOL> last_missing_mcas_ref = None <EOL> while True : <EOL> value = mc . gets ( key ) <EOL> cas_id = None if value is None else _get_cas_ids ( mc ) [ key ] <EOL> mcas_record , is_missing = _McasRecord . deref ( dc , value , <EOL> last_missing_mcas_ref ) <EOL> if is_missing : <EOL> last_missing_mcas_ref = value <EOL> continue <EOL> elif mcas_record : <EOL> _mcas_help ( dc , mcas_record ) <EOL> else : <EOL> return Entry ( key , value , cas_id ) <EOL> def test ( ) : <EOL> import doctest <EOL> import mockcache <EOL> doctest . testmod ( extraglobs = { '<STR_LIT>' : mockcache } ) <EOL> if __name__ == '<STR_LIT:__main__>' : <EOL> test ( ) </s>
