63 lines
1.2 KiB
Go
63 lines
1.2 KiB
Go
|
package types
|
||
|
|
|
||
|
|
import (
|
||
|
|
"sync/atomic"
|
||
|
|
"unsafe"
|
||
|
|
)
|
||
|
|
|
||
|
|
type node[T any] struct {
|
||
|
|
val atomic.Pointer[T]
|
||
|
|
next atomic.Pointer[node[T]]
|
||
|
|
}
|
||
|
|
|
||
|
|
type Queue[T any] interface {
|
||
|
|
Enqueue(T)
|
||
|
|
Dequeue() T
|
||
|
|
Len() uint64
|
||
|
|
}
|
||
|
|
|
||
|
|
type queue[T any] struct {
|
||
|
|
head, tail *node[T]
|
||
|
|
length atomic.Uint64
|
||
|
|
}
|
||
|
|
|
||
|
|
func NewQueue[T any]() Queue[T] {
|
||
|
|
n := node[T]{}
|
||
|
|
return &queue[T]{head: &n, tail: &n}
|
||
|
|
}
|
||
|
|
|
||
|
|
func (q *queue[T]) Enqueue(v T) {
|
||
|
|
n := node[T]{val: atomic.Pointer[T]{}}
|
||
|
|
n.val.Store(&v)
|
||
|
|
for {
|
||
|
|
if q.tail.next.CompareAndSwap(nil, &n) {
|
||
|
|
atomic.StorePointer((*unsafe.Pointer)(unsafe.Pointer(&q.tail)), unsafe.Pointer(&n))
|
||
|
|
q.length.Add(1)
|
||
|
|
return
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
func (q *queue[T]) Dequeue() T {
|
||
|
|
headAddr := (*unsafe.Pointer)(unsafe.Pointer(&q.head))
|
||
|
|
for {
|
||
|
|
var result T
|
||
|
|
head := atomic.LoadPointer(headAddr)
|
||
|
|
n := q.head.next.Load()
|
||
|
|
if n == nil {
|
||
|
|
return result
|
||
|
|
}
|
||
|
|
if atomic.CompareAndSwapPointer(headAddr, head, unsafe.Pointer(n)) {
|
||
|
|
q.length.Add(^uint64(0)) // Переполнение намеренное, это отнимает единицу от счетчика.
|
||
|
|
if r := n.val.Load(); r != nil {
|
||
|
|
return *r
|
||
|
|
}
|
||
|
|
return result
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
func (q *queue[T]) Len() uint64 {
|
||
|
|
return q.length.Load()
|
||
|
|
}
|