package queue

import (
    "sync/atomic"
    "unsafe"
)

// 無鎖隊(duì)列
type Queue struct {
    head, tail unsafe.Pointer
    size       int32
}

type Node struct {
    value any
    next  unsafe.Pointer
}

func (q *Queue) Enqueue(value any) {
    n := &Node{value: value}
retry:
    tail := load(&q.tail)
    next := load(&tail.next)
    if tail == load(&q.tail) {
        //如果next為空，則表示tail節(jié)點(diǎn)是隊(duì)列中的最后一個(gè)節(jié)點(diǎn)，
        //代碼嘗試將新節(jié)點(diǎn)n鏈接到隊(duì)列的尾部，然后將tail指針向前移動(dòng)到新添加的節(jié)點(diǎn)
        if next == nil {
            if cas(&tail.next, next, n) {
                cas(&q.tail, tail, n)
                atomic.AddInt32(&q.size, 1)
                return
            }
        } else {
            //如果next不為空，表示tail節(jié)點(diǎn)并不是指向隊(duì)列中的最后一個(gè)節(jié)點(diǎn)，此時(shí)代碼嘗試將tail指針向前移動(dòng)到下一個(gè)節(jié)點(diǎn)。
            cas(&q.tail, tail, next)
        }
    }
    goto retry
}

func (q *Queue) Dequeue() any {
retry:
    head := load(&q.head)
    tail := load(&q.tail)
    next := load(&head.next)
    if head == load(&q.head) {
        if head == tail {
            if next == nil {
                return nil
            }
            cas(&q.tail, tail, next)
        } else {
            //此行不能省略，在CAS之前讀取，否則會被另一個(gè)dequeue操作修改
            value := next.value
            if cas(&q.head, head, next) {
                atomic.AddInt32(&q.size, -1)
                return value
            }
        }
    }

    goto retry
}

func (q *Queue) IsEmpty() bool {
    return atomic.LoadInt32(&q.size) == 0
}

func load(p *unsafe.Pointer) *Node {
    return (*Node)(atomic.LoadPointer(p))
}

func cas(p *unsafe.Pointer, old, new *Node) bool {
    return atomic.CompareAndSwapPointer(p, unsafe.Pointer(old), unsafe.Pointer(new))
}