base/linked_list.jl - master - githubmirror/julia

base/linked_list.jl
293 строки9 KB
Keno Fischer
cancellation: Hook up libuv to cancellation (#62557)
05 авг 2026, 07:46
05 авг 2026, 07:4635b7e12
# This file is a part of Julia. License is MIT: https://julialang.org/license

mutable struct IntrusiveLinkedList{T}
    # Invasive list requires that T have a field `.next >: U{T, Nothing}` and `.queue::Any`
    head::Union{T, Nothing}
    tail::Union{T, Nothing}
    IntrusiveLinkedList{T}() where {T} = new{T}(nothing, nothing)
end

struct ILLRef{T}
    list::IntrusiveLinkedList{T}
    waitee::Any # Invariant: waitqueue(waitee).list === list
end

# waitqueue(x) returns the ILLRef for the queue of waiters registered on `x`.
# Methods are added for each waitee type (conditions, tasks, workqueues, ...).
function waitqueue end

#const list_append!! = append!
#const list_deletefirst! = delete!

eltype(::Type{<:IntrusiveLinkedList{T}}) where {T} = @isdefined(T) ? T : Any

iterate(q::IntrusiveLinkedList) = (h = q.head; h === nothing ? nothing : (h, h))
iterate(q::IntrusiveLinkedList{T}, v::T) where {T} = (h = v.next; h === nothing ? nothing : (h, h))

isempty(q::IntrusiveLinkedList) = (q.head === nothing)

function length(q::IntrusiveLinkedList)
    i = 0
    head = q.head
    while head !== nothing
        i += 1
        head = head.next
    end
    return i
end

function list_append!!(q::IntrusiveLinkedList{T}, q2::IntrusiveLinkedList{T}) where T
    q === q2 && error("can't append list to itself")
    head2 = q2.head
    if head2 !== nothing
        tail2 = q2.tail::T
        q2.head = nothing
        q2.tail = nothing
        tail = q.tail
        q.tail = tail2
        if tail === nothing
            q.head = head2
        else
            tail.next = head2
        end
        while head2 !== nothing
            head2.queue = q
            head2 = head2.next
        end
    end
    return q
end

isempty(qr::ILLRef) = isempty(qr.list)
length(qr::ILLRef) = length(qr.list)

function push!(qr::ILLRef{T}, val::T) where T
    val.queue === nothing || error("val already in a list")
    val.queue = qr.waitee
    q = qr.list
    tail = q.tail
    if tail === nothing
        q.head = q.tail = val
    else
        tail.next = val
        q.tail = val
    end
    return q
end

function pushfirst!(qr::ILLRef{T}, val::T) where T
    val.queue === nothing || error("val already in a list")
    val.queue = qr.waitee
    q = qr.list
    head = q.head
    if head === nothing
        q.head = q.tail = val
    else
        val.next = head
        q.head = val
    end
    return q
end

function pop!(qr::ILLRef{T}) where {T}
    val = qr.list.tail::T
    _list_deletefirst!(qr.list, val) # expensive!
    return val
end

function popfirst!(qr::ILLRef{T}) where {T}
    val = qr.list.head::T
    _list_deletefirst!(qr.list, val) # cheap
    return val
end

# Delete `val` from the list, but only if it is actually in it, as witnessed by
# `val.queue` holding the ILLRef's waitee. This makes deletion a no-op if `val`
# was concurrently popped, which various cleanup paths rely upon.
function list_deletefirst!(qr::ILLRef{T}, val::T) where T
    val.queue === qr.waitee || return qr.list
    return _list_deletefirst!(qr.list, val)
end

push!(q::IntrusiveLinkedList{T}, val::T) where T = push!(ILLRef(q, q), val)
pushfirst!(q::IntrusiveLinkedList{T}, val::T) where T = pushfirst!(ILLRef(q, q), val)
pop!(q::IntrusiveLinkedList{T}) where T = pop!(ILLRef(q, q))
popfirst!(q::IntrusiveLinkedList{T}) where T = popfirst!(ILLRef(q, q))
list_deletefirst!(q::IntrusiveLinkedList{T}, val::T) where T = list_deletefirst!(ILLRef(q, q), val)

# this function assumes `val` is found in `q`
function _list_deletefirst!(q::IntrusiveLinkedList{T}, val::T) where T
    head = q.head::T
    if head === val
        if q.tail::T === val
            q.head = q.tail = nothing
        else
            q.head = val.next::T
        end
    else
        head_next = head.next::T
        while head_next !== val
            head = head_next
            head_next = head.next::T
        end
        if q.tail::T === val
            head.next = nothing
            q.tail = head
        else
            head.next = val.next::T
        end
    end
    val.next = nothing
    val.queue = nothing
    return q
end

#function list_deletefirst!(q::Array{T}, val::T) where T
#    i = findfirst(isequal(val), q)
#    i === nothing || deleteat!(q, i)
#    return q
#end


mutable struct LinkedListItem{T}
    # Adapter class to use any `T` in a LinkedList
    next::Union{LinkedListItem{T}, Nothing}
    queue::Union{IntrusiveLinkedList{LinkedListItem{T}}, Nothing}
    value::T
    LinkedListItem{T}(value::T) where {T} = new{T}(nothing, nothing, value)
end
const LinkedList{T} = IntrusiveLinkedList{LinkedListItem{T}}

# delegate methods, as needed
eltype(::Type{<:LinkedList{T}}) where {T} = @isdefined(T) ? T : Any
iterate(q::LinkedList) = (h = q.head; h === nothing ? nothing : (h.value, h))
iterate(q::IntrusiveLinkedList{LLT}, v::LLT) where {LLT<:LinkedListItem} = (h = v.next; h === nothing ? nothing : (h.value, h))
push!(q::LinkedList{T}, val::T) where {T} = push!(q, LinkedListItem{T}(val))
pushfirst!(q::LinkedList{T}, val::T) where {T} = pushfirst!(q, LinkedListItem{T}(val))
pop!(q::LinkedList) = invoke(pop!, Tuple{IntrusiveLinkedList,}, q).value
popfirst!(q::LinkedList) = invoke(popfirst!, Tuple{IntrusiveLinkedList,}, q).value
function list_deletefirst!(q::LinkedList{T}, val::T) where T
    h = q.head
    while h !== nothing
        if isequal(h.value, val)
            list_deletefirst!(q, h)
            break
        end
        h = h.next
    end
    return q
end

## Wait-entry lists
#
# Wait entries carry uniform {owner, next, aux} slots (see cancellation.jl)
# and can be registered on several waitables at once (wait-any), so the
# list operations locate each entry's slot for *this* list through the
# ILLRef's waitee identity - every list is populated under exactly one
# identity (the ILLRef invariant above). The generic `.next`/`.queue`
# methods above keep serving Task scheduler lists.

function push!(qr::ILLRef{WaitEntry}, val::WaitEntry)
    _find_slot(val, qr.waitee) == 0 || error("val already in this list")
    _acquire_slot!(val, qr.waitee)
    q = qr.list
    tail = q.tail
    if tail === nothing
        q.head = q.tail = val
    else
        tail = tail::WaitEntry
        _set_slot_next!(tail, _find_slot(tail, qr.waitee), val)
        q.tail = val
    end
    return q
end

function pushfirst!(qr::ILLRef{WaitEntry}, val::WaitEntry)
    _find_slot(val, qr.waitee) == 0 || error("val already in this list")
    i = _acquire_slot!(val, qr.waitee)
    q = qr.list
    head = q.head
    if head === nothing
        q.head = q.tail = val
    else
        _set_slot_next!(val, i, head)
        q.head = val
    end
    return q
end

function popfirst!(qr::ILLRef{WaitEntry})
    q = qr.list
    val = q.head::WaitEntry
    i = _find_slot(val, qr.waitee)
    vnext = _slot_next(val, i)
    q.head = vnext
    vnext === nothing && (q.tail = nothing)
    _release_slot!(val, i)
    return val
end

function pop!(qr::ILLRef{WaitEntry})
    val = qr.list.tail::WaitEntry
    list_deletefirst!(qr, val) # expensive!
    return val
end

# Delete `val` from the list, but only if it is actually in it, as witnessed
# by its slot for this list's identity. This makes deletion a no-op if `val`
# was concurrently popped, which various cleanup paths rely upon.
function list_deletefirst!(qr::ILLRef{WaitEntry}, val::WaitEntry)
    vi = _find_slot(val, qr.waitee)
    vi == 0 && return qr.list
    q = qr.list
    o = qr.waitee
    head = q.head
    if head === val
        vnext = _slot_next(val, vi)
        q.head = vnext
        vnext === nothing && (q.tail = nothing)
    else
        head === nothing && return q
        prev = head::WaitEntry
        while true
            previ = _find_slot(prev, o)
            previ == 0 && return q
            prevslot = slots(prev)[previ]
            cur = prevslot.next
            cur === nothing && return q
            cur = cur::WaitEntry
            if cur === val
                vnext = _slot_next(val, vi)
                prevslot.next = vnext
                vnext === nothing && (q.tail = prev)
                break
            end
            prev = cur
        end
    end
    _release_slot!(val, vi)
    return q
end

function length(qr::ILLRef{WaitEntry})
    n = 0
    w = qr.list.head
    while w !== nothing
        n += 1
        w = _next_on(w::WaitEntry, qr.waitee)
    end
    return n
end

# Whether any entry on the list is still armed (the emptiness that matters
# to waiters-pending queries; claimed corpses linger until popped).
function _waitq_isempty(qr::ILLRef{WaitEntry})
    w = qr.list.head
    while w !== nothing
        w = w::WaitEntry
        t = @atomic :monotonic w.task
        t isa Task && (@atomic t.waiting_on) === w && return false
        w = _next_on(w, qr.waitee)
    end
    return true
end