<s> from pypy . rpython . lltypesystem import lltype , llmemory <EOL> from pypy . rlib . objectmodel import free_non_gc_object , we_are_translated <EOL> from pypy . rlib . rarithmetic import r_uint , LONG_BIT <EOL> from pypy . rlib . debug import ll_assert <EOL> DEFAULT_CHUNK_SIZE = <NUM_LIT> <EOL> def get_chunk_manager ( chunk_size = DEFAULT_CHUNK_SIZE , cache = { } ) : <EOL> try : <EOL> return cache [ chunk_size ] <EOL> except KeyError : <EOL> pass <EOL> CHUNK = lltype . ForwardReference ( ) <EOL> CHUNK . become ( lltype . Struct ( '<STR_LIT>' , <EOL> ( '<STR_LIT>' , lltype . Ptr ( CHUNK ) ) , <EOL> ( '<STR_LIT>' , lltype . FixedSizeArray ( <EOL> llmemory . Address , chunk_size ) ) ) ) <EOL> null_chunk = lltype . nullptr ( CHUNK ) <EOL> class FreeList ( object ) : <EOL> _alloc_flavor_ = "<STR_LIT>" <EOL> def __init__ ( self ) : <EOL> self . free_list = null_chunk <EOL> def get ( self ) : <EOL> if not self . free_list : <EOL> zero = not we_are_translated ( ) <EOL> return lltype . malloc ( CHUNK , flavor = "<STR_LIT>" , zero = zero ) <EOL> result = self . free_list <EOL> self . free_list = result . next <EOL> return result <EOL> def put ( self , chunk ) : <EOL> if we_are_translated ( ) : <EOL> chunk . next = self . free_list <EOL> self . free_list = chunk <EOL> else : <EOL> lltype . free ( chunk , flavor = "<STR_LIT>" ) <EOL> unused_chunks = FreeList ( ) <EOL> cache [ chunk_size ] = unused_chunks , null_chunk <EOL> return unused_chunks , null_chunk <EOL> def get_address_stack ( chunk_size = DEFAULT_CHUNK_SIZE , cache = { } ) : <EOL> try : <EOL> return cache [ chunk_size ] <EOL> except KeyError : <EOL> pass <EOL> unused_chunks , null_chunk = get_chunk_manager ( chunk_size ) <EOL> class AddressStack ( object ) : <EOL> _alloc_flavor_ = "<STR_LIT>" <EOL> def __init__ ( self ) : <EOL> self . chunk = unused_chunks . get ( ) <EOL> self . chunk . next = null_chunk <EOL> self . used_in_last_chunk = <NUM_LIT:0> <EOL> def enlarge ( self ) : <EOL> new = unused_chunks . get ( ) <EOL> new . next = self . chunk <EOL> self . chunk = new <EOL> self . used_in_last_chunk = <NUM_LIT:0> <EOL> enlarge . _dont_inline_ = True <EOL> def shrink ( self ) : <EOL> old = self . chunk <EOL> self . chunk = old . next <EOL> unused_chunks . put ( old ) <EOL> self . used_in_last_chunk = chunk_size <EOL> shrink . _dont_inline_ = True <EOL> def append ( self , addr ) : <EOL> used = self . used_in_last_chunk <EOL> if used == chunk_size : <EOL> self . enlarge ( ) <EOL> used = <NUM_LIT:0> <EOL> self . chunk . items [ used ] = addr <EOL> self . used_in_last_chunk = used + <NUM_LIT:1> <EOL> def non_empty ( self ) : <EOL> return self . used_in_last_chunk != <NUM_LIT:0> <EOL> def pop ( self ) : <EOL> used = self . used_in_last_chunk - <NUM_LIT:1> <EOL> ll_assert ( used >= <NUM_LIT:0> , "<STR_LIT>" ) <EOL> result = self . chunk . items [ used ] <EOL> self . used_in_last_chunk = used <EOL> if used == <NUM_LIT:0> and self . chunk . next : <EOL> self . shrink ( ) <EOL> return result <EOL> def delete ( self ) : <EOL> cur = self . chunk <EOL> while cur : <EOL> next = cur . next <EOL> unused_chunks . put ( cur ) <EOL> cur = next <EOL> free_non_gc_object ( self ) <EOL> def length ( self ) : <EOL> chunk = self . chunk <EOL> count = self . used_in_last_chunk <EOL> while chunk : <EOL> chunk = chunk . next <EOL> count += chunk_size <EOL> return count <EOL> def foreach ( self , callback , arg ) : <EOL> """<STR_LIT>""" <EOL> chunk = self . chunk <EOL> count = self . used_in_last_chunk <EOL> while chunk : <EOL> while count > <NUM_LIT:0> : <EOL> count -= <NUM_LIT:1> <EOL> callback ( chunk . items [ count ] , arg ) <EOL> chunk = chunk . next <EOL> count = chunk_size <EOL> foreach . _annspecialcase_ = '<STR_LIT>' <EOL> def stack2dict ( self ) : <EOL> result = AddressDict ( self . length ( ) ) <EOL> self . foreach ( _add_in_dict , result ) <EOL> return result <EOL> def remove ( self , addr ) : <EOL> """<STR_LIT>""" <EOL> got = self . pop ( ) <EOL> chunk = self . chunk <EOL> count = self . used_in_last_chunk <EOL> while got != addr : <EOL> count -= <NUM_LIT:1> <EOL> if count < <NUM_LIT:0> : <EOL> chunk = chunk . next <EOL> count = chunk_size - <NUM_LIT:1> <EOL> next = chunk . items [ count ] <EOL> chunk . items [ count ] = got <EOL> got = next <EOL> cache [ chunk_size ] = AddressStack <EOL> return AddressStack <EOL> def _add_in_dict ( item , d ) : <EOL> d . add ( item ) <EOL> def get_address_deque ( chunk_size = DEFAULT_CHUNK_SIZE , cache = { } ) : <EOL> try : <EOL> return cache [ chunk_size ] <EOL> except KeyError : <EOL> pass <EOL> unused_chunks , null_chunk = get_chunk_manager ( chunk_size ) <EOL> class AddressDeque ( object ) : <EOL> _alloc_flavor_ = "<STR_LIT>" <EOL> def __init__ ( self ) : <EOL> chunk = unused_chunks . get ( ) <EOL> chunk . next = null_chunk <EOL> self . oldest_chunk = self . newest_chunk = chunk <EOL> self . index_in_oldest = <NUM_LIT:0> <EOL> self . index_in_newest = <NUM_LIT:0> <EOL> def enlarge ( self ) : <EOL> new = unused_chunks . get ( ) <EOL> new . next = null_chunk <EOL> self . newest_chunk . next = new <EOL> self . newest_chunk = new <EOL> self . index_in_newest = <NUM_LIT:0> <EOL> enlarge . _dont_inline_ = True <EOL> def shrink ( self ) : <EOL> old = self . oldest_chunk <EOL> self . oldest_chunk = old . next <EOL> unused_chunks . put ( old ) <EOL> self . index_in_oldest = <NUM_LIT:0> <EOL> shrink . _dont_inline_ = True <EOL> def append ( self , addr ) : <EOL> index = self . index_in_newest <EOL> if index == chunk_size : <EOL> self . enlarge ( ) <EOL> index = <NUM_LIT:0> <EOL> self . newest_chunk . items [ index ] = addr <EOL> self . index_in_newest = index + <NUM_LIT:1> <EOL> def non_empty ( self ) : <EOL> return ( self . oldest_chunk != self . newest_chunk <EOL> or self . index_in_oldest < self . index_in_newest ) <EOL> def popleft ( self ) : <EOL> ll_assert ( self . non_empty ( ) , "<STR_LIT>" ) <EOL> index = self . index_in_oldest <EOL> if index == chunk_size : <EOL> self . shrink ( ) <EOL> index = <NUM_LIT:0> <EOL> result = self . oldest_chunk . items [ index ] <EOL> self . index_in_oldest = index + <NUM_LIT:1> <EOL> return result <EOL> def delete ( self ) : <EOL> cur = self . oldest_chunk <EOL> while cur : <EOL> next = cur . next <EOL> unused_chunks . put ( cur ) <EOL> cur = next <EOL> free_non_gc_object ( self ) <EOL> cache [ chunk_size ] = AddressDeque <EOL> return AddressDeque <EOL> def AddressDict ( length_estimate = <NUM_LIT:0> ) : <EOL> if we_are_translated ( ) : <EOL> from pypy . rpython . memory import lldict <EOL> return lldict . newdict ( length_estimate ) <EOL> else : <EOL> return BasicAddressDict ( ) <EOL> class BasicAddressDict ( object ) : <EOL> def __init__ ( self ) : <EOL> self . data = { } <EOL> def _key ( self , addr ) : <EOL> "<STR_LIT>" <EOL> return addr . _fixup ( ) . ptr . _obj <EOL> def _wrapkey ( self , obj ) : <EOL> return llmemory . cast_ptr_to_adr ( obj . _as_ptr ( ) ) <EOL> def delete ( self ) : <EOL> pass <EOL> def length ( self ) : <EOL> return len ( self . data ) <EOL> def contains ( self , keyaddr ) : <EOL> return self . _key ( keyaddr ) in self . data <EOL> def get ( self , keyaddr , default = llmemory . NULL ) : <EOL> return self . data . get ( self . _key ( keyaddr ) , default ) <EOL> def setitem ( self , keyaddr , valueaddr ) : <EOL> assert keyaddr <EOL> self . data [ self . _key ( keyaddr ) ] = valueaddr <EOL> def insertclean ( self , keyaddr , valueaddr ) : <EOL> assert keyaddr <EOL> key = self . _key ( keyaddr ) <EOL> assert key not in self . data <EOL> self . data [ key ] = valueaddr <EOL> def add ( self , keyaddr ) : <EOL> self . setitem ( keyaddr , llmemory . NULL ) <EOL> def clear ( self ) : <EOL> self . data . clear ( ) <EOL> def foreach ( self , callback , arg ) : <EOL> """<STR_LIT>""" <EOL> for key , value in self . data . iteritems ( ) : <EOL> callback ( self . _wrapkey ( key ) , value , arg ) <EOL> def copy_and_update ( dict , surviving , updated_address ) : <EOL> """<STR_LIT>""" <EOL> newdict = AddressDict <EOL> if not we_are_translated ( ) : <EOL> if not isinstance ( dict , BasicAddressDict ) : <EOL> from pypy . rpython . memory . lldict import newdict <EOL> result = newdict ( dict . length ( ) ) <EOL> dict . foreach ( _get_updater ( surviving , updated_address ) , result ) <EOL> return result <EOL> copy_and_update . _annspecialcase_ = '<STR_LIT>' <EOL> def _get_updater ( surviving , updated_address ) : <EOL> def callback ( key , value , arg ) : <EOL> if surviving ( key ) : <EOL> newkey = updated_address ( key ) <EOL> arg . setitem ( newkey , value ) <EOL> return callback <EOL> _get_updater . _annspecialcase_ = '<STR_LIT>' <EOL> def copy_without_null_values ( dict ) : <EOL> """<STR_LIT>""" <EOL> newdict = AddressDict <EOL> if not we_are_translated ( ) : <EOL> if not isinstance ( dict , BasicAddressDict ) : <EOL> from pypy . rpython . memory . lldict import newdict <EOL> result = newdict ( ) <EOL> dict . foreach ( _null_value_checker , result ) <EOL> return result <EOL> def _null_value_checker ( key , value , arg ) : <EOL> if value : <EOL> arg . setitem ( key , value ) </s>
