Example: Michael and Scott queue

WIP (TODO: add explanation)

https://www.cs.rochester.edu/u/scott/papers/1996PODCqueues.pdf

using Reagents

struct MSQNode{T,R}
    next::R
    data::T
    # Node{T,R}() = new{T,R}()
    MSQNode{T,R}(next) where {T,R} = new{T,R}(next)
    MSQNode{T,R}(next, data) where {T,R} = new{T,R}(next, data)
end

const MSQNodeRef{T} = Reagents.Ref{Union{Nothing,MSQNode{T}}}
const MSQHeadRef{T} = Reagents.Ref{MSQNode{T}}

MSQNode(next::MSQNodeRef{T}) where {T} = MSQNode{T,typeof(next)}(next)
MSQNode(next::MSQNodeRef{T}, data) where {T} = MSQNode{T,typeof(next)}(next, data)

struct MSQueue{T,R<:MSQHeadRef{T}}
    head::R
    tail::R
    function MSQueue{T}() where {T}
        node = MSQNode(MSQNodeRef{T}(nothing))
        head = MSQHeadRef{T}(node)
        tail = MSQHeadRef{T}(node)
        return new{T,typeof(head)}(head, tail)
    end
end

nodetype(::MSQueue{<:Any,R}) where {N,R<:Reagents.Ref{N}} = N

Base.eltype(::Type{<:MSQueue{T}}) where {T} = T

trypoppingfirst(q::MSQueue{T}) where {T} =
    Reagents.Update(q.head) do node, _
        next = node.next[]
        if next === nothing
            (node, nothing)
        else
            next::nodetype(q)
            (next, Some(next.data))
        end
    end

pushing(q::MSQueue{T}) where {T} =
    Reagents.Computed() do x
        node = MSQNode(MSQNodeRef{T}(nothing), x)
        while true
            tail = q.tail[]
            tail::nodetype(q)
            next = tail.next[]
            if next === nothing  # found the tail
                return Reagents.CAS(tail.next, nothing, node) ⨟ Reagents.PostCommit() do _
                    Reagents.try!(Reagents.CAS(q.tail, tail, node))
                end
            else  # need the fixup
                next::nodetype(q)
                Reagents.try!(Reagents.CAS(q.tail, tail, next))
            end
        end
    end

trypopfirst!(q::MSQueue) = trypoppingfirst(q)()
Base.popfirst!(q::MSQueue) = something(trypopfirst!(q))
Base.push!(q::MSQueue, x) = pushing(q)(convert(eltype(q), x))

This page was generated using Literate.jl.