Lock-Free Data Structures

sync/atomic can also be used to implement lock-free data structures.

a lock-free stack

package main

import (
	"fmt"
	"sync"
	"sync/atomic"
)

type Node[T any] struct {
	value T
	next  *Node[T]
}

type Stack[T any] struct {
	head atomic.Pointer[Node[T]]
}

func (s *Stack[T]) Push(value T) {
	node := &Node[T]{value: value}

	for {
		node.next = s.head.Load()
		if s.head.CompareAndSwap(node.next, node) {
			return
		}
	}
}

func (s *Stack[T]) Pop() (T, bool) {
	for {
		head := s.head.Load()
		if head == nil {
			return *new(T), false
		}

		if s.head.CompareAndSwap(head, head.next) {
			return head.value, true
		}
	}
}

func main() {
	stack := &Stack[int]{}

	for i := range 10 {
		stack.Push(i)
	}

	wg := sync.WaitGroup{}
	wg.Add(10)

	for range 10 {
		go func() {
			value, _ := stack.Pop()
			fmt.Printf("%d ", value)
			wg.Done()
		}()
	}

	wg.Wait()
}