golang 高并发安全顺序链表实现

package main

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


// - 完成 插入、查询 功能
// - 完成 删除、遍历 功能
// - 通过 测试，并且不发生 data race

type IntSortList struct {
    head   atomic.Value
    length int64 // 多写多读
    mu     sync.RWMutex
}

type Node struct {
    value  int
    marked atomic.Value // 一写多读
    next   atomic.Value // 一写多读
    mu     sync.Mutex
}

func newNode(value int) *Node {
    n := new(Node)
    n.value = value
    n.marked.Store(uint32(0))
    return n
}

func NewIntSortList() *IntSortList {
    sl := new(IntSortList)
    sl.head.Store(newNode(0))
    return sl
}

// 并发写操作 insert and delete
// 逻辑删除 marked 标志，即为非法的。

// insert: 7 节点 找A，B =  6，9
// 1 找到节点A和B,不存在直接返回
// 2 锁定节点A，检查A.next != B OR A.marked 如果为真，则解锁A然后返回step1 （为什么锁定A后，没有占领A->区域，有可能被别人更改，为了找到真正的A和B）
// 3 创建新节点X
// 4 X.next = B; A.next(atomic.Store) = X  这里需要atomic.Store是因为保证原子性
// 5 解锁节点A

// 保护不被别人改变，造成未定义的行为（加两个锁）

func (l *IntSortList) InsertNode(value int) bool {
    var a *Node
    var b *Node
    for {
        a = l.head.Load().(*Node)
        if nil != a.next.Load() {
            b = a.next.Load().(*Node)
        }
        for b != nil && b.value < value {
            a = b
            if nil != b.next.Load() {
                b = b.next.Load().(*Node)
            }
        }

        // Check if the node is exist.
        if b != nil && b.value == value {
            return false
        }

        a.mu.Lock()
        // data race 重试
        aNext := a.next.Load()
        if aNext != nil {
            aNext = aNext.(*Node)
        }

        // nil != nil
        change := true
        if nil == aNext && b == nil {
            change = false
        } else if b == aNext {
            change = false
        }
        if change || a.marked.Load().(uint32) > 0 {
            a.mu.Unlock()
            continue
        }

        x := newNode(value)
        x.next.Store(b)
        a.next.Store(x)

        l.mu.Lock()
        l.length++
        l.mu.Unlock()

        a.mu.Unlock()
        return true
    }
}

func main() {
    l := NewIntSortList()
    l.InsertNode(10)
    l.InsertNode(11)
    l.InsertNode(11)
    l.InsertNode(14)
    fmt.Println(l)
    l.DeleteNode(14)
    fmt.Println(l)
    fmt.Println(l.SortedListContains(11))
}

func (l *IntSortList) SortedListContains(value int) bool {

    x := l.head.Load().(*Node).next.Load().(*Node)
    for x != nil && x.value < value {
        x = x.next.Load().(*Node)
    }
    if x == nil {
        return false
    }
    return x.value == value
}


func (l *IntSortList) SortListLen() int {
    return int(l.length)
}

// Delete:
// 1 找到节点A和B（atomic.Load）,不存在则直接返回
// 2 锁定节点B，检查b.marked == true, 如果为真，则解锁B然后返回step1
// 3 锁定节点A，检查A.next != B OR  a.marked ，如果为真，则解锁A和B然后返回step1
// 4 b.marked=true; A.next=B.next
// 5 解锁节点A和B

// 写： atomic + LOCK

func (l *IntSortList) DeleteNode(value int) bool {
    var a *Node
    var b *Node
    for {
        a = l.head.Load().(*Node)
        if nil != a.next.Load() {
            b = a.next.Load().(*Node)
        }
        for b != nil && b.value < value {
            a = b
            if nil != b.next.Load() {
                b = b.next.Load().(*Node)
            }
        }

        // Check if the node is exist.
        if b == nil || b.value != value {
            return false
        }

        b.mu.Lock()
        // data race 重试
        if b.marked.Load().(uint32) > 0 {
            b.mu.Unlock()
            continue
        }

        a.mu.Lock()
        // data race 重试
        if a.next.Load().(*Node) != b || a.marked.Load().(uint32) > 0 {
            b.mu.Unlock()
            a.mu.Unlock()
            continue
        }

        //  b.marked=true; A.next=B.next
        b.marked.Store(uint32(1))
        a.next.Store(b.next.Load())

        l.mu.Lock()
        l.length--
        l.mu.Unlock()

        b.mu.Unlock()
        a.mu.Unlock()
        return true
    }
}

// 并发读  一个区域内：一写多读 使用atomic， （全局）多个区域：多写多读； 缺点，查询效率低，使用skiplist （实践2）
// 无锁读

// Contains:
// 1 找到节点X，存在则返回!x.marked, 不存在则直接返回false