package main
func main()  {
	m := make(map[int]int)
	go func()  {
		for {
			_ = m[1]
		}
	}()
	go func()  {
		for {
			m[2] = 2
		}
	}()
	select {}
}

import "sync"
func main() {
	m := make(map[int]int)
	var lock sync.RWMutex
	go func() {
		for {
			lock.RLock()
			_ = m[1]
			lock.RUnlock()
		}
	}()
	go func() {
		for {
			lock.Lock()
			m[2] = 2
			lock.Unlock()
		}
	}()
	select {}
}

package main
import (
	"fmt"
	"sync"
)
func main() {
	var m sync.Map
	// 1. 寫入
	m.Store("apple", 1)
	m.Store("banana", 2)
	// 2. 讀取
	price, _ := m.Load("apple")
	fmt.Println(price.(int))
	// 3. 遍歷
	m.Range(func(key, value interface{}) bool {
		fruit := key.(string)
		price := value.(int)
		fmt.Println(fruit, price)
		return true
	})
	// 4. 刪除
	m.Delete("apple")
	// 5. 讀取或寫入
	m.LoadOrStore("peach", 3)
}

type Map struct {
    // 當涉及到臟數據(dirty)操作時候，需要使用這個鎖
    mu Mutex
    // read是一個只讀數據結構，包含一個map結構，
    // 讀不需要加鎖，只需要通過 atomic 加載最新的指正即可
    read atomic.Value // readOnly
    // dirty 包含部分map的鍵值對，如果操作需要mutex獲取鎖
    // 最后dirty中的元素會被全部提升到read里的map去
    dirty map[interface{}]*entry
    // misses是一個計數器，用于記錄read中沒有的數據而在dirty中有的數據的數量。
    // 也就是說如果read不包含這個數據，會從dirty中讀取，并misses+1
    // 當misses的數量等于dirty的長度，就會將dirty中的數據遷移到read中
    misses int
}

// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
    // m包含所有只讀數據，不會進行任何的數據增加和刪除操作 
    // 但是可以修改entry的指針因為這個不會導致map的元素移動
    m       map[interface{}]*entry
    // 標志位，如果為true則表明當前read只讀map的數據不完整，dirty map中包含部分數據
    amended bool // true if the dirty map contains some key not in m.
}

type entry struct {
    p unsafe.Pointer // *interface{}
}

// src/sync/map.go
// Load returns the value stored in the map for a key, or nil if no
// value is present.
// The ok result indicates whether value was found in the map.
func (m *Map) Load(key interface{}) (value interface{}, ok bool) {
    // 首先從只讀ready的map中查找，這時不需要加鎖
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    // 如果沒有找到，并且read.amended為true，說明dirty中有新數據，從dirty中查找，開始加鎖了
    if !ok && read.amended {
        m.mu.Lock() // 加鎖
       // 又在 readonly 中檢查一遍，因為在加鎖的時候 dirty 的數據可能已經遷移到了read中
        read, _ = m.read.Load().(readOnly)
        e, ok = read.m[key]
        // read 還沒有找到，并且dirty中有數據
        if !ok && read.amended {
            e, ok = m.dirty[key] //從 dirty 中查找數據
            // 不管m.dirty中存不存在，都將misses + 1
            // missLocked() 中滿足條件后就會把m.dirty中數據遷移到m.read中
            m.missLocked()
        }
        m.mu.Unlock()
    }
    if !ok {
        return nil, false
    }
    return e.load()
}

// src/sync/map.go
func (m *Map) missLocked() {
    m.misses++
    if m.misses < len(m.dirty) {//misses次數小于 dirty的長度，就不遷移數據，直接返回
        return
    }
    m.read.Store(readOnly{m: m.dirty}) //開始遷移數據
    m.dirty = nil   //遷移完dirty就賦值為nil
    m.misses = 0  //遷移完 misses歸0
}

// src/sync/map.go
// Store sets the value for a key.
func (m *Map) Store(key, value interface{}) {
   // 直接在read中查找值，找到了，就嘗試 tryStore() 更新值
    read, _ := m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok && e.tryStore(&value) {
        return
    }
    // m.read 中不存在
    m.mu.Lock()
    read, _ = m.read.Load().(readOnly)
    if e, ok := read.m[key]; ok {
        if e.unexpungeLocked() { // 未被標記成刪除，前面講到entry數據結構時，里面的p值有3種。1.nil 2.expunged，這個值含義有點復雜，可以看看前面entry數據結構 3.正常值
            m.dirty[key] = e // 加入到dirty里
        }
        e.storeLocked(&value) // 更新值
    } else if e, ok := m.dirty[key]; ok { // 存在于 dirty 中，直接更新
        e.storeLocked(&value)
    } else { // 新的值
        if !read.amended { // m.dirty 中沒有新數據，增加到 m.dirty 中
            // We're adding the first new key to the dirty map.
            // Make sure it is allocated and mark the read-only map as incomplete.
            m.dirtyLocked() // 從 m.read中復制未刪除的數據
            m.read.Store(readOnly{m: read.m, amended: true}) 
        }
        m.dirty[key] = newEntry(value) //將這個entry加入到m.dirty中
    }
    m.mu.Unlock()
}

// tryStore stores a value if the entry has not been expunged.
//
// If the entry is expunged, tryStore returns false and leaves the entry
// unchanged.
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
		}
	}
}

// storeLocked unconditionally stores a value to the entry.
//
// The entry must be known not to be expunged.
func (e *entry) storeLocked(i *interface{}) {
	atomic.StorePointer(&e.p, unsafe.Pointer(i))
}

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 {
		// 判斷值是否被刪除，被標記為expunged的值不會被復制到read map中
		if !e.tryExpungeLocked() {
			m.dirty[k] = e
		}
	}
}
// expunged實際上是一個指向空接口的unsafe指針
var expunged = unsafe.Pointer(new(interface{}))
func (e *entry) tryExpungeLocked() (isExpunged bool) {
	p := atomic.LoadPointer(&e.p)
	// 如果p為nil，就會被標記為expunged
	for p == nil {
		if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
			return true
		}
		p = atomic.LoadPointer(&e.p)
	}
	return p == expunged
}

// src/sync/map.go
// Delete deletes the value for a key.
func (m *Map) Delete(key interface{}) {
    // 從 m.read 中開始查找
    read, _ := m.read.Load().(readOnly)
    e, ok := read.m[key]
    if !ok && read.amended { // m.read中沒有找到，并且可能存在于m.dirty中，加鎖查找
        m.mu.Lock() // 加鎖
        read, _ = m.read.Load().(readOnly) // 再在m.read中查找一次
        e, ok = read.m[key]
        if !ok && read.amended { //m.read中又沒找到，amended標志位true，說明在m.dirty中
            delete(m.dirty, key) // 刪除
        }
        m.mu.Unlock()
    }
    if ok { // 在 m.read 中就直接刪除
        e.delete()
    }
}

func (e *entry) delete() (hadValue bool) {
	for {
		p := atomic.LoadPointer(&e.p)
		// 已標記為刪除
		if p == nil || p == expunged {
			return false
		}
		// 原子操作，e.p標記為nil，GO的GC會將對象自動刪除
		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
			return true
		}
	}
}