type RWMap struct { // 一個(gè)讀寫鎖保護(hù)的線程安全的map
    sync.RWMutex // 讀寫鎖保護(hù)下面的map字段
    m map[int]int
}
// 新建一個(gè)RWMap
func NewRWMap(n int) *RWMap {
    return &RWMap{
        m: make(map[int]int, n),
    }
}
func (m *RWMap) Get(k int) (int, bool) { //從map中讀取一個(gè)值
    m.RLock()
    defer m.RUnlock()
    v, existed := m.m[k] // 在鎖的保護(hù)下從map中讀取
    return v, existed
}
func (m *RWMap) Set(k int, v int) { // 設(shè)置一個(gè)鍵值對(duì)
    m.Lock()              // 鎖保護(hù)
    defer m.Unlock()
    m.m[k] = v
}
func (m *RWMap) Delete(k int) { //刪除一個(gè)鍵
    m.Lock()                   // 鎖保護(hù)
    defer m.Unlock()
    delete(m.m, k)
}
func (m *RWMap) Len() int { // map的長(zhǎng)度
    m.RLock()   // 鎖保護(hù)
    defer m.RUnlock()
    return len(m.m)
}
func (m *RWMap) Each(f func(k, v int) bool) { // 遍歷map
    m.RLock()             //遍歷期間一直持有讀鎖
    defer m.RUnlock()
    for k, v := range m.m {
        if !f(k, v) {
            return
        }
    }
}

var SHARD_COUNT = 32   
// 分成SHARD_COUNT個(gè)分片的map
type ConcurrentMap []*ConcurrentMapShared
// 通過(guò)RWMutex保護(hù)的線程安全的分片，包含一個(gè)map
type ConcurrentMapShared struct {
    items        map[string]interface{}
    sync.RWMutex // Read Write mutex, guards access to internal map.
}
// 創(chuàng)建并發(fā)map
func New() ConcurrentMap {
    m := make(ConcurrentMap, SHARD_COUNT)
    for i := 0; i < SHARD_COUNT; i++ {
        m[i] = &ConcurrentMapShared{items: make(map[string]interface{})}
    }
    return m
}
// 根據(jù)key計(jì)算分片索引
func (m ConcurrentMap) GetShard(key string) *ConcurrentMapShared {
    return m[uint(fnv32(key))%uint(SHARD_COUNT)]
}

func (m ConcurrentMap) Set(key string, value interface{}) {
    // 根據(jù)key計(jì)算出對(duì)應(yīng)的分片
    shard := m.GetShard(key)
    shard.Lock() //對(duì)這個(gè)分片加鎖，執(zhí)行業(yè)務(wù)操作
    shard.items[key] = value
    shard.Unlock()
}
func (m ConcurrentMap) Get(key string) (interface{}, bool) {
    // 根據(jù)key計(jì)算出對(duì)應(yīng)的分片
    shard := m.GetShard(key)
    shard.RLock()
    // 從這個(gè)分片讀取key的值
    val, ok := shard.items[key]
    shard.RUnlock()
    return val, ok
}

type Map struct {
    mu Mutex
    // 基本上你可以把它看成一個(gè)安全的只讀的map
    // 它包含的元素其實(shí)也是通過(guò)原子操作更新的，但是已刪除的entry就需要加鎖操作了
    read atomic.Value // readOnly
    // 包含需要加鎖才能訪問(wèn)的元素
    // 包括所有在read字段中但未被expunged（刪除）的元素以及新加的元素
    dirty map[interface{}]*entry
    // 記錄從read中讀取miss的次數(shù)，一旦miss數(shù)和dirty長(zhǎng)度一樣了，就會(huì)把dirty提升為read，并把dirty置空
    misses int
}
type readOnly struct {
    m       map[interface{}]*entry
    amended bool // 當(dāng)dirty中包含read沒(méi)有的數(shù)據(jù)時(shí)為true，比如新增一條數(shù)據(jù)
}
// expunged是用來(lái)標(biāo)識(shí)此項(xiàng)已經(jīng)刪掉的指針
// 當(dāng)map中的一個(gè)項(xiàng)目被刪除了，只是把它的值標(biāo)記為expunged，以后才有機(jī)會(huì)真正刪除此項(xiàng)
var expunged = unsafe.Pointer(new(interface{}))
// entry代表一個(gè)值
type entry struct {
    p unsafe.Pointer // *interface{}
}

func (m *Map) Store(key, value interface{}) {
    read, _ := m.read.Load().(readOnly)
    // 如果read字段包含這個(gè)項(xiàng)，說(shuō)明是更新，cas更新項(xiàng)目的值即可
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }
    // read中不存在，或者cas更新失敗，就需要加鎖訪問(wèn)dirty了
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok { // 雙檢查，看看read是否已經(jīng)存在了
        if e.unexpungeLocked() {
            // 此項(xiàng)目先前已經(jīng)被刪除了，需要添加到 dirty 中
            m.dirty[key] = e
        }
        e.storeLocked(&value) // 更新
    } else if e, ok := m.dirty[key]; ok { // 如果dirty中有此項(xiàng)
        e.storeLocked(&value) // 直接更新
    } else { // 否則就是一個(gè)新的key
        if !read.amended { //如果dirty為nil
            // 需要?jiǎng)?chuàng)建dirty對(duì)象，并且標(biāo)記read的amended為true,
            // 說(shuō)明有元素它不包含而dirty包含
            m.dirtyLocked()
            m.read.Store(readOnly{m: read.m, amended: true})
        }
        m.dirty[key] = newEntry(value) //將新值增加到dirty對(duì)象中
    }
    m.mu.Unlock()
}
// tryStore利用 cas 操作來(lái)更新value。
// 更新之前會(huì)判斷這個(gè)鍵值對(duì)有沒(méi)有被打上刪除的標(biāo)記
func (e *entry) tryStore(i *interface{}) bool {
    for {
        p := atomic.LoadPointer(&e.p)
        if p == expunged {
            return false
        }
        if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
            return true
        }
    }
}
// 將值設(shè)置成 nil，表示沒(méi)有被刪除
func (e *entry) unexpungeLocked() (wasExpunged bool) {
    return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}
// 通過(guò)復(fù)制 read 生成 dirty
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
        }
    }
}
// 標(biāo)記刪除
func (e *entry) tryExpungeLocked() (isExpunged bool) {
    p := atomic.LoadPointer(&e.p)
    for p == nil {
        if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
            return true
        }
        p = atomic.LoadPointer(&e.p)
    }
    return p == expunged
}

func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    // 首先從read處理
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended { // 如果不存在并且dirty不為nil(有新的元素)
        m.mu.Lock()
        // 雙檢查，看看read中現(xiàn)在是否存在此key
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        if !ok && read.amended {//依然不存在，并且dirty不為nil
            e, ok = m.dirty[key]// 從dirty中讀取
            // 不管dirty中存不存在，miss數(shù)都加1
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    return e.load() //返回讀取的對(duì)象，e既可能是從read中獲得的，也可能是從dirty中獲得的
}
func (m *Map) missLocked() {
    m.misses++ // misses計(jì)數(shù)加一
    if m.misses < len(m.dirty) { // 如果沒(méi)達(dá)到閾值(dirty字段的長(zhǎng)度),返回
        return
    }
    m.read.Store(readOnly{m: m.dirty}) //把dirty字段的內(nèi)存提升為read字段
    m.dirty = nil // 清空dirty
    m.misses = 0  // misses數(shù)重置為0
}

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 { // 說(shuō)明可能在
            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
        }
    }
}