Go语言中结构体原子比较与交换：实现无锁数据结构的策略

package main

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

// node_t 模拟链表节点
type node_t struct {
    value interface{}
    // 其他字段
}

// pointer_t 包含一个节点指针和一个计数器
// 在位窃取策略中，我们不会直接使用这个结构体，而是将其信息编码到 uintptr 中
// type pointer_t struct {
//     ptr   *node_t
//     count uint
// }

// 掩码定义：假设低3位用于计数器，其余位用于指针
const (
    countMask = 0x7 // 000...0111，用于获取计数器
    ptrMask   = ^countMask // 111...1000，用于获取指针
)

// encode 将 *node_t 和 uint 编码成一个 uintptr
func encode(ptr *node_t, count uint) uintptr {
    // 确保计数器不会溢出可用位数
    if count > countMask {
        panic("count exceeds available bits")
    }
    // 将指针转换为 uintptr，并清除其低位（因为是8字节对齐，低3位通常为0）
    // 然后将计数器编码到这些低位
    return (uintptr(unsafe.Pointer(ptr)) & ptrMask) | (uintptr(count) & countMask)
}

// decode 从编码后的 uintptr 中解码出 *node_t 和 uint
func decode(encoded uintptr) (*node_t, uint) {
    ptr := (*node_t)(unsafe.Pointer(encoded & ptrMask))
    count := uint(encoded & countMask)
    return ptr, count
}

func main() {
    // 模拟一个需要原子更新的 "next" 字段
    var atomicNext uintptr // 使用 uintptr 来存储编码后的指针和计数器

    // 初始状态
    initialNode := &node_t{value: "A"}
    initialCount := uint(0)
    initialEncoded := encode(initialNode, initialCount)
    atomic.StorePointer((*unsafe.Pointer)(unsafe.Pointer(&atomicNext)), unsafe.Pointer(initialEncoded))

    fmt.Printf("初始值: ptr=%p, count=%d, encoded=0x%x\n", initialNode, initialCount, initialEncoded)

    // 尝试进行 CAS 操作
    // 假设我们想将 next 更新为 newNodeB 和 count+1
    newNodeB := &node_t{value: "B"}
    expectedEncoded := initialEncoded // 期望的旧值
    newEncoded := encode(newNodeB, initialCount+1) // 编码新值

    // 执行 CAS
    // 注意：CompareAndSwapPointer 期望 *unsafe.Pointer, old, new
    // 我们需要将 uintptr 转换为 unsafe.Pointer
    swapped := atomic.CompareAndSwapPointer(
        (*unsafe.Pointer)(unsafe.Pointer(&atomicNext)),
        unsafe.Pointer(expectedEncoded),
        unsafe.Pointer(newEncoded),
    )

    if swapped {
        fmt.Println("CAS 成功!")
    } else {
        fmt.Println("CAS 失败!")
    }

    // 读取更新后的值
    currentEncoded := atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&atomicNext)))
    currentPtr, currentCount := decode(uintptr(currentEncoded))
    fmt.Printf("更新后值: ptr=%p, count=%d, encoded=0x%x\n", currentPtr, currentCount, currentEncoded)
    fmt.Printf("更新后节点值: %v\n", currentPtr.value)
}

package main

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

type pointer_t struct {
    ptr   *node_t
    count uint
}

type node_t struct {
    value interface{}
    next  *pointer_t // 关键改变：next 现在是一个指向 pointer_t 的指针
}

func main() {
    // 初始状态
    initialNode := &node_t{value: "A"}
    initialPointerT := &pointer_t{ptr: initialNode, count: 0}

    // 假设这是一个全局或共享的节点，其 next 字段需要原子更新
    var headNode node_t
    atomic.StorePointer((*unsafe.Pointer)(unsafe.Pointer(&headNode.next)), unsafe.Pointer(initialPointerT))

    fmt.Printf("初始值: headNode.next 指向 %p, 包含 ptr=%p, count=%d\n", initialPointerT, initialPointerT.ptr, initialPointerT.count)

    // 尝试进行 CAS 操作
    // 假设我们想将 headNode.next 更新为指向 newNodeB 和 count+1
    newNodeB := &node_t{value: "B"}

    // 循环直到 CAS 成功
    for {
        // 1. 获取当前 headNode.next 指针
        oldNextPtrValue := atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&headNode.next)))
        oldPointerT := (*pointer_t)(oldNextPtrValue) // 解引用得到当前的 pointer_t 结构体

        // 2. 创建新的 pointer_t 实例（副本）并进行修改
        // 注意：这里我们创建一个新的结构体，而不是修改 oldPointerT
        newPointerT := &pointer_t{
            ptr:   newNodeB,
            count: oldPointerT.count + 1,
        }

        // 3. 尝试原子交换：将旧指针替换为新指针
        swapped := atomic.CompareAndSwapPointer(
            (*unsafe.Pointer)(unsafe.Pointer(&headNode.next)), // 目标地址
            oldNextPtrValue,                                   // 期望的旧值（指针）
            unsafe.Pointer(newPointerT),                       // 新值（指针）
        )

        if swapped {
            fmt.Println("CAS 成功!")
            break // 成功，退出循环
        }
        // 如果 CAS 失败，说明 headNode.next 已被其他协程修改，需要重试
        fmt.Println("CAS 失败，重试...")
    }

    // 读取更新后的值
    currentNextPtrValue := atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&headNode.next)))
    currentPointerT := (*pointer_t)(currentNextPtrValue)
    fmt.Printf("更新后值: headNode.next 指向 %p, 包含 ptr=%p, count=%d\n", currentPointerT, currentPointerT.ptr, currentPointerT.count)
    fmt.Printf("更新后节点值: %v\n", currentPointerT.ptr.value)
}