package mymap
import ( "fmt" "sync" "sync/atomic" "unsafe")
type Map struct { //用来锁dirty mu sync.Mutex //白桶 read atomic.Value //黑桶 dirty map[interface{}]*entry //脏值 misses int}
type readOnly struct { //封装的map m map[interface{}]*entry //白条 amended bool}
//expunged是一个指针指向一个空对象，也就是指向interface{}var expunged = unsafe.Pointer(new(interface{}))
//entry就是一个指针type entry struct { p unsafe.Pointer}
func newEntry(i interface{}) *entry { return &entry{p: unsafe.Pointer(&i)}}
//从sync.map读数据func (m *Map) Load(key interface{}) (value interface{}, ok bool) { //先看白桶里面有没有key read, _ := m.read.Load().(readOnly) //有则直接返回 e, ok := read.m[key] //如果白桶里没有这个key，而且白条写着“欠收拾”，说明黑桶里面可能有key if !ok && read.amended { m.mu.Lock() //上面白桶获取时没有加锁，上锁后再检查一次 read, _ = m.read.Load().(readOnly) e, ok = read.m[key] //再检查一次也没有，则直接从黑桶里面读取数据 if !ok && read.amended { e, ok = m.dirty[key] //脏值+1, 如果脏值比黑桶数据数量还大，则收拾黑桶 m.missLocked() } m.mu.Unlock() } //如果白桶黑桶里都没有数据，返回nil if !ok { return nil, false } //返回entry指针对应的值 return e.load()}
//获取entry指针对应的值func (e *entry) load() (value interface{}, ok bool) { p := atomic.LoadPointer(&e.p) if p == nil || p == expunged { return nil, false } return *(*interface{})(p), true}
//往sync.map写数据func (m *Map) Store(key, value interface{}) { //先看白桶里面有没有key read, _ := m.read.Load().(readOnly) //白桶存在key直接更新白桶里面的数据 if e, ok := read.m[key]; ok && e.tryStore(&value) { return }
m.mu.Lock() //上面白桶获取没有加锁，上锁后再写入一次白桶 read, _ = m.read.Load().(readOnly) if e, ok := read.m[key]; ok { if e.unexpungeLocked() { //白桶存在key直接更新白桶里面的数据 m.dirty[key] = e } //将黑桶里面的key也指向value，相当于黑桶和白桶都指向同一份数据 e.storeLocked(&value) } else if e, ok := m.dirty[key]; ok { //如果白桶里面没有这个key，但是黑桶里面有，直接更新黑桶里面的数据 e.storeLocked(&value) } else { //白桶和黑桶都没有这个key if !read.amended { //如果黑桶刚刚被收拾过，白条“已收拾”，则需要将白桶里的数据，复制一份到黑桶 m.dirtyLocked() //设置白条为“欠收拾” m.read.Store(readOnly{m: read.m, amended: true}) } //将新数据丢到黑桶 m.dirty[key] = newEntry(value) } m.mu.Unlock()}
//tryStore就是一个基于CAS的原子写操作func (e *entry) tryStore(i *interface{}) bool { for { p := atomic.LoadPointer(&e.p) //如果原先key对应的值是一个interface{}空对象，返回失败 if p == expunged { return false } //CAS原子写入entity if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) { return true } }}
//判断entry是否=expunged（interface{}）,如果是将entry设置为nilfunc (e *entry) unexpungeLocked() (wasExpunged bool) { return atomic.CompareAndSwapPointer(&e.p, expunged, nil)}
//原子写入entryfunc (e *entry) storeLocked(i *interface{}) { atomic.StorePointer(&e.p, unsafe.Pointer(i))}
//参照Storefunc (m *Map) LoadOrStore(key, value interface{}) (actual interface{}, loaded bool) { read, _ := m.read.Load().(readOnly) if e, ok := read.m[key]; ok { actual, loaded, ok := e.tryLoadOrStore(value) if ok { return actual, loaded } }
m.mu.Lock() read, _ = m.read.Load().(readOnly) if e, ok := read.m[key]; ok { if e.unexpungeLocked() { m.dirty[key] = e } actual, loaded, _ = e.tryLoadOrStore(value) } else if e, ok := m.dirty[key]; ok { actual, loaded, _ = e.tryLoadOrStore(value) m.missLocked() } else { if !read.amended { m.dirtyLocked() m.read.Store(readOnly{m: read.m, amended: true}) } m.dirty[key] = newEntry(value) actual, loaded = value, false } m.mu.Unlock()
return actual, loaded}
func (e *entry) tryLoadOrStore(i interface{}) (actual interface{}, loaded, ok bool) { p := atomic.LoadPointer(&e.p) if p == expunged { return nil, false, false } if p != nil { return *(*interface{})(p), true, true }
ic := i for { if atomic.CompareAndSwapPointer(&e.p, nil, unsafe.Pointer(&ic)) { return i, false, true } p = atomic.LoadPointer(&e.p) if p == expunged { return nil, false, false } if p != nil { return *(*interface{})(p), true, true } }}
func (m *Map) Delete(key interface{}) { read, _ := m.read.Load().(readOnly) //数据在白桶，直接删除白桶里面的数据 e, ok := read.m[key] if !ok && read.amended { m.mu.Lock() read, _ = m.read.Load().(readOnly) e, ok = read.m[key] //数据不在白桶，黑桶“欠收拾” if !ok && read.amended { //直接黑桶清除数据 delete(m.dirty, key) } m.mu.Unlock() } if ok { e.delete() }}
func (e *entry) delete() (hadValue bool) { for { p := atomic.LoadPointer(&e.p) if p == nil || p == expunged { return false } if atomic.CompareAndSwapPointer(&e.p, p, nil) { return true } }}
func (m *Map) Range(f func(key, value interface{}) bool) { read, _ := m.read.Load().(readOnly) if read.amended { m.mu.Lock() read, _ = m.read.Load().(readOnly) if read.amended { read = readOnly{m: m.dirty} m.read.Store(read) m.dirty = nil m.misses = 0 } m.mu.Unlock() }
for k, e := range read.m { v, ok := e.load() if !ok { continue } if !f(k, v) { break } }}
//脏值+1,func (m *Map) missLocked() { //脏值+1, m.misses++ //如果脏值比黑桶数据数量还大，则收拾黑桶 if m.misses < len(m.dirty) { return } m.read.Store(readOnly{m: m.dirty}) //将黑桶map清空 m.dirty = nil //将脏值清零 m.misses = 0}
func (m *Map) dirtyLocked() { if m.dirty != nil { return }
//黑桶已经被清洗过了，这里要重新初始化黑桶 read, _ := m.read.Load().(readOnly) m.dirty = make(map[interface{}]*entry, len(read.m)) //将白桶里面的复制一份到黑桶 for k, e := range read.m { if !e.tryExpungeLocked() { m.dirty[k] = e } }}
//这里就是判断entry是不是指向空对象或者是nil//如果entry=是nil，赋值为空对象,也返回truefunc (e *entry) tryExpungeLocked() (isExpunged bool) { p := atomic.LoadPointer(&e.p) for p == nil { //如果entry指向nil，给entry赋值空对象interface{},返回true if atomic.CompareAndSwapPointer(&e.p, nil, expunged) { return true } p = atomic.LoadPointer(&e.p) } return p == expunged}
评论