package queue

import (
    "sync/atomic"
    "unsafe"
)

// 无锁队列
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节点是队列中的最后一个节点，
        //代码尝试将新节点n链接到队列的尾部，然后将tail指针向前移动到新添加的节点
        if next == nil {
            if cas(&tail.next, next, n) {
                cas(&q.tail, tail, n)
                atomic.AddInt32(&q.size, 1)
                return
            }
        } else {
            //如果next不为空，表示tail节点并不是指向队列中的最后一个节点，此时代码尝试将tail指针向前移动到下一个节点。
            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之前读取，否则会被另一个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))
}