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