/* Ċ Ġ* ĠCopyright Ġ 2 0 1 6 - 2 0 1 8 ĠJetBrains Ġs . r . o . ĠUse Ġof Ġthis Ġsource Ġcode Ġis Ġgoverned Ġby Ġthe ĠApache Ġ 2 . 0 Ġlicense . Ċ Ġ*/ Ċ Ċ package Ġkotlinx . coroutines . internal Ċ Ċ import Ġkotlinx . atomic fu .* Ċ Ċ private Ġtype alias ĠCore < E > Ġ= ĠLock Free MP SC Queue Core < E > Ċ Ċ /** Ċ Ġ* ĠLock - free ĠMultiply - Producer ĠSingle - Consumer ĠQueue . Ċ Ġ* Ġ* Note : ĠThis Ġqueue Ġis ĠNOT Ġlinear izable . ĠIt Ġprovides Ġonly Ġqu ies cent Ġconsistency Ġfor Ġits Ġoperations .* Ċ Ġ* Ċ Ġ* ĠIn Ġparticular , Ġthe Ġfollowing Ġexecution Ġis Ġpermitted Ġfor Ġthis Ġqueue , Ġbut Ġis Ġnot Ġpermitted Ġfor Ġa Ġlinear izable Ġqueue : Ċ Ġ* Ċ Ġ* Ġ``` Ċ Ġ* ĠThread Ġ 1 : Ġadd Last ( 1 ) Ġ= Ġtrue , Ġremove First OrNull () Ġ= Ġnull Ċ Ġ* ĠThread Ġ 2 : Ġadd Last ( 2 ) Ġ= Ġ 2 Ġ// Ġthis Ġoperation Ġis Ġconcurrent Ġwith Ġboth Ġoperations Ġin Ġthe Ġfirst Ġthread Ċ Ġ* Ġ``` Ċ Ġ* Ċ Ġ* Ġ@ suppress Ġ** This Ġis Ġun stable ĠAPI Ġand Ġit Ġis Ġsubject Ġto Ġchange .** Ċ Ġ*/ Ċ class ĠLock Free MP SC Queue < E Ġ: ĠAny > Ġ{ ĊĠĠĠ Ġprivate Ġval Ġ_ cur Ġ= Ġatomic ( Core < E >( Core . INITIAL _ CAP ACITY )) ĊĊĠĠĠ Ġ// ĠNote : Ġit Ġis Ġnot Ġatomic Ġw . r . t . Ġremove Ġoperation Ġ( remove Ġcan Ġtransient ly Ġfail Ġwhen ĠisEmpty Ġis Ġfalse ) ĊĠĠĠ Ġval ĠisEmpty : ĠBoolean Ġget () Ġ= Ġ_ cur . value . isEmpty ĊĊĠĠĠ Ġfun Ġclose () Ġ{ ĊĠĠĠĠĠĠĠ Ġ_ cur . loop Ġ{ Ġcur Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cur . close ()) Ġreturn Ġ// Ġclosed Ġthis Ġcopy ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ cur . compare AndSet ( cur , Ġcur . next ()) Ġ// Ġmove Ġto Ġnext ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġadd Last ( element : ĠE ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ_ cur . loop Ġ{ Ġcur Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġ( cur . add Last ( element )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠCore . ADD _ SUCCESS Ġ-> Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠCore . ADD _ CLOSED Ġ-> Ġreturn Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠCore . ADD _ F RO Z EN Ġ-> Ġ_ cur . compare AndSet ( cur , Ġcur . next ()) Ġ// Ġmove Ġto Ġnext ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Suppress (" UN CHECK ED _ CAST ") ĊĠĠĠ Ġfun Ġremove First OrNull (): ĠE ? Ġ{ ĊĠĠĠĠĠĠĠ Ġ_ cur . loop Ġ{ Ġcur Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġresult Ġ= Ġcur . remove First OrNull () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( result Ġ!== ĠCore . REMOVE _ F RO Z EN ) Ġreturn Ġresult Ġas ĠE ? ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ cur . compare AndSet ( cur , Ġcur . next ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ /** Ċ Ġ* ĠLock - free ĠMultiply - Producer ĠSingle - Consumer ĠQueue Ġcore . Ċ Ġ* Ġ* Note : ĠThis Ġqueue Ġis ĠNOT Ġlinear izable . ĠIt Ġprovides Ġonly Ġqu ies cent Ġconsistency Ġfor Ġits Ġoperations .* Ċ Ġ* Ċ Ġ* Ġ@ see ĠLock Free MP SC Queue Ċ Ġ* Ġ@ suppress Ġ** This Ġis Ġun stable ĠAPI Ġand Ġit Ġis Ġsubject Ġto Ġchange .** Ċ Ġ*/ Ċ internal Ġclass ĠLock Free MP SC Queue Core < E Ġ: ĠAny >( private Ġval Ġcapacity : ĠInt ) Ġ{ ĊĠĠĠ Ġprivate Ġval Ġmask Ġ= Ġcapacity Ġ- Ġ 1 ĊĠĠĠ Ġprivate Ġval Ġ_ next Ġ= Ġatomic < Core < E >? >( null ) ĊĠĠĠ Ġprivate Ġval Ġ_ state Ġ= Ġatomic ( 0 L ) ĊĠĠĠ Ġprivate Ġval Ġarray Ġ= ĠarrayOf Null s < Any ? >( capacity ); ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġcheck ( mask Ġ<= ĠMAX _ CAP ACITY _ MASK ) ĊĠĠĠĠĠĠĠ Ġcheck ( capacity Ġand Ġmask Ġ== Ġ 0 ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠNote : Ġit Ġis Ġnot Ġatomic Ġw . r . t . Ġremove Ġoperation Ġ( remove Ġcan Ġtransient ly Ġfail Ġwhen ĠisEmpty Ġis Ġfalse ) ĊĠĠĠ Ġval ĠisEmpty : ĠBoolean Ġget () Ġ= Ġ_ state . value . with State Ġ{ Ġhead , Ġtail Ġ-> Ġhead Ġ== Ġtail Ġ} ĊĊĠĠĠ Ġfun Ġclose (): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġ_ state . update Ġ{ Ġstate Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( state Ġand ĠCLO SED _ MASK Ġ!= Ġ 0 L ) Ġreturn Ġtrue Ġ// Ġok Ġ- Ġalready Ġclosed ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( state Ġand ĠF RO Z EN _ MASK Ġ!= Ġ 0 L ) Ġreturn Ġfalse Ġ// Ġfrozen Ġ-- Ġtry Ġnext ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstate Ġor ĠCLO SED _ MASK Ġ// Ġtry Ġset Ġclosed Ġbit ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠADD _ CLOSED Ġ| ĠADD _ F RO Z EN Ġ| ĠADD _ SUCCESS ĊĠĠĠ Ġfun Ġadd Last ( element : ĠE ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġ_ state . loop Ġ{ Ġstate Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( state Ġand Ġ( F RO Z EN _ MASK Ġor ĠCLO SED _ MASK ) Ġ!= Ġ 0 L ) Ġreturn Ġstate . add Fail Reason () Ġ// Ġcannot Ġadd ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstate . with State Ġ{ Ġhead , Ġtail Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġthere Ġcould Ġbe Ġone ĠREMOVE Ġelement Ġbeyond Ġhead Ġthat Ġwe Ġcannot Ġst ump Ġup , ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġso Ġwe Ġcheck Ġfor Ġfull Ġqueue Ġwith Ġan Ġextra Ġmargin Ġof Ġone Ġelement ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(( tail Ġ+ Ġ 2 ) Ġand Ġmask Ġ== Ġhead Ġand Ġmask ) Ġreturn ĠADD _ F RO Z EN Ġ// Ġover full , Ġso Ġdo Ġfreeze Ġ& Ġcopy ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Tail Ġ= Ġ( tail Ġ+ Ġ 1 ) Ġand ĠMAX _ CAP ACITY _ MASK ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(_ state . compare AndSet ( state , Ġstate . update Tail ( new Tail ))) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġsuccessfully Ġadded ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġarray [ tail Ġand Ġmask ] Ġ= Ġelement ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcould Ġhave Ġbeen Ġfrozen Ġ& Ġcopied Ġbefore Ġthis Ġitem Ġwas Ġset Ġ-- Ġcorrect Ġit Ġby Ġfilling Ġplaceholder ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġcur Ġ= Ġthis ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cur ._ state . value Ġand ĠF RO Z EN _ MASK Ġ== Ġ 0 L ) Ġbreak Ġ// Ġall Ġfine Ġ-- Ġnot Ġfrozen Ġyet ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcur Ġ= Ġcur . next (). fill Placeholder ( tail , Ġelement ) Ġ?: Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ĠADD _ SUCCESS Ġ// Ġadded Ġsuccessfully ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġfill Placeholder ( index : ĠInt , Ġelement : ĠE ): ĠCore < E >? Ġ{ Ċ // ĠĠĠĠĠĠĠ Ġif Ġ( array . compare AndSet ( index Ġand Ġmask , ĠPL ACE HOLDER , Ġelement )) Ġ{ Ċ // ĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwe 've Ġcorrected Ġmissing Ġelement , Ġshould Ġcheck Ġif Ġthat Ġpropag ated Ġto Ġfurther Ġcopies , Ġjust Ġin Ġcase Ċ // ĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġthis Ċ // ĠĠĠĠĠĠĠ Ġ} Ċ // ĠĠĠĠĠĠĠ Ġ// Ġit Ġis ĠOk , Ġno Ġneed Ġfor Ġfurther Ġaction Ċ // ĠĠĠĠĠĠĠ Ġreturn Ġnull ĊĠĠĠĠĠĠĠ Ġif Ġ( array [ index Ġand Ġmask ] Ġ!= ĠPL ACE HOLDER ) Ġreturn Ġnull ĊĠĠĠĠĠĠĠ Ġarray [ index Ġand Ġmask ] Ġ= Ġelement ĊĠĠĠĠĠĠĠ Ġreturn Ġthis ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠS INGLE ĠCON SUM ER ĊĠĠĠ Ġ// ĠREMOVE _ F RO Z EN Ġ| Ġnull Ġ( EMPTY ) Ġ| ĠE Ġ( SUCCESS ) ĊĠĠĠ Ġfun Ġremove First OrNull (): ĠAny ? Ġ{ ĊĠĠĠĠĠĠĠ Ġ_ state . loop Ġ{ Ġstate Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( state Ġand ĠF RO Z EN _ MASK Ġ!= Ġ 0 L ) Ġreturn ĠREMOVE _ F RO Z EN Ġ// Ġfrozen Ġ-- Ġcannot Ġmodify ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstate . with State Ġ{ Ġhead , Ġtail Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(( tail Ġand Ġmask ) Ġ== Ġ( head Ġand Ġmask )) Ġreturn Ġnull Ġ// Ġempty ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġbecause Ġqueue Ġis ĠSingle ĠConsumer , Ġthen Ġelement Ġ== Ġnull | PLACE HOLDER Ġcan Ġonly Ġbe Ġwhen Ġadd Ġhas Ġnot Ġfinished Ġyet ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġelement Ġ= Ġarray [ head Ġand Ġmask ] Ġ?: Ġreturn Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( element Ġ=== ĠPL ACE HOLDER ) Ġreturn Ġnull Ġ// Ġsame Ġstory Ġ-- Ġconsider Ġit Ġnot Ġadded Ġyet ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcheck ( element Ġ!== ĠRE MOVED ) Ġ{ Ġ" This Ġqueue Ġcan Ġhave Ġonly Ġone Ġconsumer " Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġtent atively Ġremove Ġelement Ġto Ġlet ĠGC Ġwork ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġwe Ġcannot Ġput Ġnull Ġinto Ġarray , Ġbecause Ġcopying Ġthread Ġcould Ġreplace Ġit Ġwith ĠPL ACE HOLDER ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġand Ġthat Ġis Ġa Ġdis aster , Ġso Ġa Ġseparate ĠRE MOVED Ġtoken Ġis Ġused Ġhere . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠNote : Ġat Ġmost Ġone ĠRE MOVED Ġin Ġthe Ġarray , Ġbecause Ġsingle Ġconsumer . ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġarray [ head Ġand Ġmask ] Ġ= ĠRE MOVED ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnew Head Ġ= Ġ( head Ġ+ Ġ 1 ) Ġand ĠMAX _ CAP ACITY _ MASK ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(_ state . compare AndSet ( state , Ġstate . update Head ( new Head ))) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġarray [ head Ġand Ġmask ] Ġ= Ġnull Ġ// Ġnow Ġcan Ġsafely Ġput Ġnull Ġ( state Ġwas Ġupdated ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġelement Ġ// Ġsuccessfully Ġremoved Ġin Ġfast - path ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠS low - path Ġfor Ġremove Ġin Ġcase Ġof Ġinter ference ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġcur Ġ= Ġthis ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcur Ġ= Ġcur . remove Slow Path ( head , Ġnew Head ) Ġ?: Ġreturn Ġelement ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġremove Slow Path ( old Head : ĠInt , Ġnew Head : ĠInt ): ĠCore < E >? Ġ{ ĊĠĠĠĠĠĠĠ Ġ_ state . loop Ġ{ Ġstate Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstate . with State Ġ{ Ġhead , Ġ_ Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcheck ( head Ġ== Ġold Head ) Ġ{ Ġ" This Ġqueue Ġcan Ġhave Ġonly Ġone Ġconsumer " Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( state Ġand ĠF RO Z EN _ MASK Ġ!= Ġ 0 L ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġstate Ġwas Ġalready Ġfrozen , Ġso Ġeither Ġold Ġor ĠRE MOVED Ġitem Ġcould Ġhave Ġbeen Ġcopied Ġto Ġnext ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġnext Ġ= Ġnext () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnext . array [ head Ġand Ġnext . mask ] Ġ= ĠRE MOVED Ġ// Ġmake Ġsure Ġit Ġis Ġremoved Ġin Ġnew Ġarray Ġregardless ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnext Ġ// Ġcontinue Ġto Ġcorrect Ġhead Ġin Ġnext ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(_ state . compare AndSet ( state , Ġstate . update Head ( new Head ))) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġarray [ head Ġand Ġmask ] Ġ= Ġnull Ġ// Ġnow Ġcan Ġsafely Ġput Ġnull Ġ( state Ġwas Ġupdated ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġnext (): ĠLock Free MP SC Queue Core < E > Ġ= Ġallocate Or GetNext Copy ( mark Frozen ()) ĊĊĠĠĠ Ġprivate Ġfun Ġmark Frozen (): ĠLong Ġ= ĊĠĠĠĠĠĠĠ Ġ_ state . update AndGet Ġ{ Ġstate Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( state Ġand ĠF RO Z EN _ MASK Ġ!= Ġ 0 L ) Ġreturn Ġstate Ġ// Ġalready Ġmarked ĊĠĠĠĠĠĠĠĠĠĠĠ Ġstate Ġor ĠF RO Z EN _ MASK ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġallocate Or GetNext Copy ( state : ĠLong ): ĠCore < E > Ġ{ ĊĠĠĠĠĠĠĠ Ġ_ next . loop Ġ{ Ġnext Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( next Ġ!= Ġnull ) Ġreturn Ġnext Ġ// Ġalready Ġallocated Ġ& Ġcopied ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ_ next . compare AndSet ( null , Ġallocate Next Copy ( state )) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġprivate Ġfun Ġallocate Next Copy ( state : ĠLong ): ĠCore < E > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġnext Ġ= ĠLock Free MP SC Queue Core < E >( capacity Ġ* Ġ 2 ) ĊĠĠĠĠĠĠĠ Ġstate . with State Ġ{ Ġhead , Ġtail Ġ-> ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġindex Ġ= Ġhead ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhile Ġ( index Ġand Ġmask Ġ!= Ġtail Ġand Ġmask ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġreplace Ġnull s Ġwith Ġplaceholders Ġon Ġcopy ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnext . array [ index Ġand Ġnext . mask ] Ġ= Ġarray [ index Ġand Ġmask ] Ġ?: ĠPL ACE HOLDER ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġindex ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġnext ._ state . value Ġ= Ġstate Ġwo ĠF RO Z EN _ MASK ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġnext ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ@ Suppress (" Private PropertyName ") ĊĠĠĠ Ġinternal Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġinternal Ġconst Ġval ĠINITIAL _ CAP ACITY Ġ= Ġ 8 ĊĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠCAP ACITY _ BITS Ġ= Ġ 3 0 ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠMAX _ CAP ACITY _ MASK Ġ= Ġ( 1 Ġshl ĠCAP ACITY _ BITS ) Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠHEAD _ SHIFT Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠHEAD _ MASK Ġ= ĠMAX _ CAP ACITY _ MASK . to Long () Ġshl ĠHEAD _ SHIFT ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠT AIL _ SHIFT Ġ= ĠHEAD _ SHIFT Ġ+ ĠCAP ACITY _ BITS ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠT AIL _ MASK Ġ= ĠMAX _ CAP ACITY _ MASK . to Long () Ġshl ĠT AIL _ SHIFT ĊĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠF RO Z EN _ SHIFT Ġ= ĠT AIL _ SHIFT Ġ+ ĠCAP ACITY _ BITS ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠF RO Z EN _ MASK Ġ= Ġ 1 L Ġshl ĠF RO Z EN _ SHIFT ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠCLO SED _ SHIFT Ġ= ĠF RO Z EN _ SHIFT Ġ+ Ġ 1 ĊĠĠĠĠĠĠĠ Ġprivate Ġconst Ġval ĠCLO SED _ MASK Ġ= Ġ 1 L Ġshl ĠCLO SED _ SHIFT ĊĊĠĠĠĠĠĠĠ Ġinternal Ġval ĠREMOVE _ F RO Z EN Ġ= ĠSymbol (" REMOVE _ F RO Z EN ") ĊĊĠĠĠĠĠĠĠ Ġinternal Ġconst Ġval ĠADD _ SUCCESS Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġinternal Ġconst Ġval ĠADD _ F RO Z EN Ġ= Ġ 1 ĊĠĠĠĠĠĠĠ Ġinternal Ġconst Ġval ĠADD _ CLOSED Ġ= Ġ 2 ĊĊĠĠĠĠĠĠĠ Ġprivate Ġval ĠPL ACE HOLDER Ġ= ĠSymbol (" PLACE HOLDER ") ĊĠĠĠĠĠĠĠ Ġprivate Ġval ĠRE MOVED Ġ= ĠSymbol (" PLACE HOLDER ") ĊĊĠĠĠĠĠĠĠ Ġprivate Ġin fix Ġfun ĠLong . wo ( other : ĠLong ) Ġ= Ġthis Ġand Ġother . inv () ĊĠĠĠĠĠĠĠ Ġprivate Ġfun ĠLong . update Head ( new Head : ĠInt ) Ġ= Ġ( this Ġwo ĠHEAD _ MASK ) Ġor Ġ( new Head . to Long () Ġshl ĠHEAD _ SHIFT ) ĊĠĠĠĠĠĠĠ Ġprivate Ġfun ĠLong . update Tail ( new Tail : ĠInt ) Ġ= Ġ( this Ġwo ĠT AIL _ MASK ) Ġor Ġ( new Tail . to Long () Ġshl ĠT AIL _ SHIFT ) ĊĊĠĠĠĠĠĠĠ Ġprivate Ġinline Ġfun Ġ< T > ĠLong . with State ( block : Ġ( head : ĠInt , Ġtail : ĠInt ) Ġ-> ĠT ): ĠT Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġhead Ġ= Ġ(( this Ġand ĠHEAD _ MASK ) Ġshr ĠHEAD _ SHIFT ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġtail Ġ= Ġ(( this Ġand ĠT AIL _ MASK ) Ġshr ĠT AIL _ SHIFT ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġblock ( head , Ġtail ) ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġ// ĠF RO Z EN Ġ| ĠCLO SED ĊĠĠĠĠĠĠĠ Ġprivate Ġfun ĠLong . add Fail Reason (): ĠInt Ġ= Ġif Ġ( this Ġand ĠCLO SED _ MASK Ġ!= Ġ 0 L ) ĠADD _ CLOSED Ġelse ĠADD _ F RO Z EN ĊĠĠĠ Ġ} Ċ }