/* Ċ Ġ* ĠCopyright Ġ 2 0 1 6 - 2 0 2 0 Ġ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 .* Ċ Ċ /** Ċ Ġ* ĠThis Ġqueue Ġimplementation Ġis Ġbased Ġon Ġ[ Segment List ] Ġfor Ġtesting Ġpurposes Ġand Ġis Ġorganized Ġas Ġfollows . ĠEss entially , Ċ Ġ* Ġthe Ġ[ Segment Based Queue ] Ġis Ġrepresented Ġas Ġan Ġinfinite Ġarray Ġof Ġsegments , Ġeach Ġstores Ġone Ġelement Ġ( see Ġ[ One Element Segment ]). Ċ Ġ* ĠBoth Ġ[ enqueue ] Ġand Ġ[ de queue ] Ġoperations Ġincrement Ġthe Ġcorresponding Ġglobal Ġindex Ġ([ en q Idx ] Ġfor Ġ[ enqueue ] Ġand Ċ Ġ* Ġ[ de q Idx ] Ġfor Ġ[ de queue ]) Ġand Ġwork Ġwith Ġthe Ġindexed Ġby Ġthis Ġcounter Ġcell . ĠSince Ġboth Ġoperations Ġincrement Ġthe Ġindices Ċ Ġ* Ġat Ġfirst , Ġthere Ġcould Ġbe Ġa Ġrace : Ġ[ enqueue ] Ġincre ments Ġ[ en q Idx ], Ġthen Ġ[ de queue ] Ġchecks Ġthat Ġthe Ġqueue Ġis Ġnot Ġempty Ċ Ġ* Ġ( that 's Ġtrue ) Ġand Ġincre ments Ġ[ de q Idx ], Ġlooking Ġinto Ġthe Ġcorresponding Ġcell Ġafter Ġthat ; Ġhowever , Ġthe Ġcell Ġis Ġempty Ċ Ġ* Ġbecause Ġthe Ġ[ en q Idx ] Ġoperation Ġhas Ġnot Ġbeen Ġput Ġits Ġelement Ġyet . ĠTo Ġmake Ġthe Ġqueue Ġnon - blocking , Ġ[ de queue ] Ġcan Ġmark Ċ Ġ* Ġthe Ġcell Ġwith Ġ[ BRO KEN ] Ġtoken Ġand Ġretry Ġthe Ġoperation , Ġ[ enqueue ] Ġat Ġthe Ġsame Ġtime Ġshould Ġrestart Ġas Ġwell ; Ġthis Ġway , Ċ Ġ* Ġthe Ġqueue Ġis Ġob struction - free . Ċ Ġ*/ Ċ internal Ġclass ĠSegment Based Queue < T > Ġ{ ĊĠĠĠ Ġprivate Ġval Ġhead : ĠAtomic Ref < One Element Segment < T >> ĊĠĠĠ Ġprivate Ġval Ġtail : ĠAtomic Ref < One Element Segment < T >> ĊĊĠĠĠ Ġprivate Ġval Ġen q Idx Ġ= Ġatomic ( 0 L ) ĊĠĠĠ Ġprivate Ġval Ġde q Idx Ġ= Ġatomic ( 0 L ) ĊĊĠĠĠ Ġinit Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġs Ġ= ĠOne Element Segment < T >( 0 , Ġnull , Ġ 2 ) ĊĠĠĠĠĠĠĠ Ġhead Ġ= Ġatomic ( s ) ĊĠĠĠĠĠĠĠ Ġtail Ġ= Ġatomic ( s ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// ĠReturns Ġthe Ġsegments Ġassociated Ġwith Ġthe Ġen queued Ġelement , Ġor Ġ` null ` Ġif Ġthe Ġqueue Ġis Ġclosed . ĊĠĠĠ Ġfun Ġenqueue ( element : ĠT ): ĠOne Element Segment < T >? Ġ{ ĊĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcur Tail Ġ= Ġthis . tail . value ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġen q Idx Ġ= Ġthis . en q Idx . get And Increment () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsegment Or Closed Ġ= Ġthis . tail . find Segment And Move Forward ( id Ġ= Ġen q Idx , Ġstart From Ġ= Ġcur Tail , Ġcreate New Segment Ġ= Ġ:: create Segment ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( segment Or Closed . is Closed ) Ġreturn Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġs Ġ= Ġsegment Or Closed . segment ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( s . element . value Ġ=== ĠBRO KEN ) Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( s . element . compare AndSet ( null , Ġelement )) Ġreturn Ġs ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġde queue (): ĠT ? Ġ{ ĊĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( this . de q Idx . value Ġ>= Ġthis . en q Idx . value ) Ġreturn Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcur Head Ġ= Ġthis . head . value ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġde q Idx Ġ= Ġthis . de q Idx . get And Increment () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsegment Or Closed Ġ= Ġthis . head . find Segment And Move Forward ( id Ġ= Ġde q Idx , Ġstart From Ġ= Ġcur Head , Ġcreate New Segment Ġ= Ġ:: create Segment ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( segment Or Closed . is Closed ) Ġreturn Ġnull ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġs Ġ= Ġsegment Or Closed . segment ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( s . id Ġ> Ġde q Idx ) Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġel Ġ= Ġs . element . value ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( el Ġ=== Ġnull ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( s . element . compare AndSet ( null , ĠBRO KEN )) Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġel Ġ= Ġs . element . value ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠThe Ġlink Ġto Ġthe Ġprevious Ġsegment Ġshould Ġbe Ġcleaned Ġafter Ġretrieving Ġthe Ġelement ; ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġotherwise , Ġ` close ()` Ġcannot Ġclean Ġthe Ġslot . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġs . clean Prev () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( el Ġ=== ĠBRO KEN ) Ġcontinue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ@ Suppress (" UN CHECK ED _ CAST ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġel Ġas ĠT ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// Ġ` enqueue ` Ġshould Ġreturn Ġ` null ` Ġafter Ġthe Ġqueue Ġis Ġclosed ĊĠĠĠ Ġfun Ġclose (): ĠOne Element Segment < T > Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġs Ġ= Ġthis . tail . value . close () ĊĠĠĠĠĠĠĠ Ġvar Ġcur Ġ= Ġs ĊĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcur . element . compare AndSet ( null , ĠBRO KEN ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcur Ġ= Ġcur . prev Ġ?: Ġbreak ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġs ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġval ĠnumberOf Segments : ĠInt Ġget () Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġcur Ġ= Ġhead . value ĊĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġ 1 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcur Ġ= Ġcur . next Ġ?: Ġreturn Ġi ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi ++ ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġcheck Head Prev Is Clean ed () Ġ{ ĊĠĠĠĠĠĠĠ Ġcheck ( head . value . prev Ġ=== Ġnull ) Ġ{ Ġ" head . prev Ġis Ġnot Ġnull "} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġcheck All Segments Are Not Log ically Removed () Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġprev : ĠOne Element Segment < T >? Ġ= Ġnull ĊĠĠĠĠĠĠĠ Ġvar Ġcur Ġ= Ġhead . value ĊĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcheck (! cur . logic ally Removed Ġ|| Ġcur . is Tail ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" This Ġqueue Ġcontains Ġremoved Ġsegments , Ġmemory Ġleak Ġdetected " ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcheck ( cur . prev Ġ=== Ġprev ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" Two Ġneighbour Ġsegments Ġare Ġincorrectly Ġlinked : ĠS . next . prev Ġ!= ĠS " ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprev Ġ= Ġcur ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcur Ġ= Ġcur . next Ġ?: Ġreturn ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ Ċ } Ċ Ċ private Ġfun Ġ< T > Ġcreate Segment ( id : ĠLong , Ġprev : ĠOne Element Segment < T > ?) Ġ= ĠOne Element Segment ( id , Ġprev , Ġ 0 ) Ċ Ċ internal Ġclass ĠOne Element Segment < T >( id : ĠLong , Ġprev : ĠOne Element Segment < T > ?, Ġpointers : ĠInt ) Ġ: ĠSegment < One Element Segment < T >>( id , Ġprev , Ġpointers ) Ġ{ ĊĠĠĠ Ġval Ġelement Ġ= Ġatomic < Any ? >( null ) ĊĊĠĠĠ Ġoverride Ġval Ġmax Slots Ġget () Ġ= Ġ 1 ĊĊĠĠĠ Ġval Ġlog ically Removed Ġget () Ġ= Ġelement . value Ġ=== ĠBRO KEN ĊĊĠĠĠ Ġfun Ġremove Segment () Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġold Ġ= Ġelement . get AndSet ( BRO KEN ) ĊĠĠĠĠĠĠĠ Ġif Ġ( old Ġ!== ĠBRO KEN ) Ġon Slot Clean ed () ĊĠĠĠ Ġ} Ċ } Ċ Ċ private Ġval ĠBRO KEN Ġ= ĠSymbol (" BRO KEN ")