cmap: Split to Map and ComparableMap

3 files changed, 544 insertions, 175 deletions

diff --git a/cmap/comparable_map.go b/cmap/comparable_map.go
new file mode 100644
index 0000000..e89175c
--- /dev/null
+++ b/cmap/comparable_map.go
@@ -0,0 +1,539 @@
+// Inspired by github.com/SaveTheRbtz/generic-sync-map-go but technically
+// written from scratch with Go 1.23's sync.Map.
+// Copyright 2024 Runxi Yu (porting it to generics)
+// Copyright 2016 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package cmap
+
+import (
+	"sync"
+	"sync/atomic"
+	"unsafe"
+)
+
+// ComparableMap[K comparable, V comparable] is like a Go map[K]V but is safe for concurrent use
+// by multiple goroutines without additional locking or coordination.  Loads,
+// stores, and deletes run in amortized constant time.
+//
+// The ComparableMap type is optimized for two common use cases: (1) when the comparableEntry for a given
+// key is only ever written once but read many times, as in caches that only grow,
+// or (2) when multiple goroutines read, write, and overwrite entries for disjoint
+// sets of keys. In these two cases, use of a ComparableMap may significantly reduce lock
+// contention compared to a Go map paired with a separate [Mutex] or [RWMutex].
+//
+// The zero ComparableMap is empty and ready for use. A ComparableMap must not be copied after first use.
+//
+// In the terminology of [the Go memory model], ComparableMap arranges that a write operation
+// “synchronizes before” any read operation that observes the effect of the write, where
+// read and write operations are defined as follows.
+// [ComparableMap.Load], [ComparableMap.LoadAndDelete], [ComparableMap.LoadOrStore], [ComparableMap.Swap], [ComparableMap.CompareAndSwap],
+// and [ComparableMap.CompareAndDelete] are read operations;
+// [ComparableMap.Delete], [ComparableMap.LoadAndDelete], [ComparableMap.Store], and [ComparableMap.Swap] are write operations;
+// [ComparableMap.LoadOrStore] is a write operation when it returns loaded set to false;
+// [ComparableMap.CompareAndSwap] is a write operation when it returns swapped set to true;
+// and [ComparableMap.CompareAndDelete] is a write operation when it returns deleted set to true.
+//
+// [the Go memory model]: https://go.dev/ref/mem
+type ComparableMap[K comparable, V comparable] struct {
+	mu sync.Mutex
+
+	// read contains the portion of the map's contents that are safe for
+	// concurrent access (with or without mu held).
+	//
+	// The read field itself is always safe to load, but must only be stored with
+	// mu held.
+	//
+	// Entries stored in read may be updated concurrently without mu, but updating
+	// a previously-comparableExpunged comparableEntry requires that the comparableEntry be copied to the dirty
+	// map and uncomparableExpunged with mu held.
+	read atomic.Pointer[comparableReadOnly[K, V]]
+
+	// dirty contains the portion of the map's contents that require mu to be
+	// held. To ensure that the dirty map can be promoted to the read map quickly,
+	// it also includes all of the non-comparableExpunged entries in the read map.
+	//
+	// Expunged entries are not stored in the dirty map. An comparableExpunged comparableEntry in the
+	// clean map must be uncomparableExpunged and added to the dirty map before a new value
+	// can be stored to it.
+	//
+	// If the dirty map is nil, the next write to the map will initialize it by
+	// making a shallow copy of the clean map, omitting stale entries.
+	dirty map[K]*comparableEntry[V]
+
+	// misses counts the number of loads since the read map was last updated that
+	// needed to lock mu to determine whether the key was present.
+	//
+	// Once enough misses have occurred to cover the cost of copying the dirty
+	// map, the dirty map will be promoted to the read map (in the unamended
+	// state) and the next store to the map will make a new dirty copy.
+	misses int
+}
+
+// comparableReadOnly is an immutable struct stored atomically in the ComparableMap.read field.
+type comparableReadOnly[K comparable, V comparable] struct {
+	m       map[K]*comparableEntry[V]
+	amended bool // true if the dirty map contains some key not in m.
+}
+
+// comparableExpunged is an arbitrary pointer that marks entries which have been deleted
+// from the dirty map.
+var comparableExpunged = unsafe.Pointer(new(any))
+
+// An comparableEntry is a slot in the map corresponding to a particular key.
+type comparableEntry[V comparable] struct {
+	// p points to the value stored for the comparableEntry.
+	//
+	// If p == nil, the comparableEntry has been deleted, and either m.dirty == nil or
+	// m.dirty[key] is e.
+	//
+	// If p == comparableExpunged, the comparableEntry has been deleted, m.dirty != nil, and the comparableEntry
+	// is missing from m.dirty.
+	//
+	// Otherwise, the comparableEntry is valid and recorded in m.read.m[key] and, if m.dirty
+	// != nil, in m.dirty[key].
+	//
+	// An comparableEntry can be deleted by atomic replacement with nil: when m.dirty is
+	// next created, it will atomically replace nil with comparableExpunged and leave
+	// m.dirty[key] unset.
+	//
+	// An comparableEntry's associated value can be updated by atomic replacement, provided
+	// p != comparableExpunged. If p == comparableExpunged, an comparableEntry's associated value can be updated
+	// only after first setting m.dirty[key] = e so that lookups using the dirty
+	// map find the comparableEntry.
+	p unsafe.Pointer
+}
+
+func newComparableEntry[V comparable](i V) *comparableEntry[V] {
+	return &comparableEntry[V]{p: unsafe.Pointer(&i)}
+}
+
+func (m *ComparableMap[K, V]) loadReadOnly() comparableReadOnly[K, V] {
+	if p := m.read.Load(); p != nil {
+		return *p
+	}
+	return comparableReadOnly[K, V]{}
+}
+
+// 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 *ComparableMap[K, V]) Load(key K) (value V, ok bool) {
+	read := m.loadReadOnly()
+	e, ok := read.m[key]
+	if !ok && read.amended {
+		m.mu.Lock()
+		// Avoid reporting a spurious miss if m.dirty got promoted while we were
+		// blocked on m.mu. (If further loads of the same key will not miss, it's
+		// not worth copying the dirty map for this key.)
+		read = m.loadReadOnly()
+		e, ok = read.m[key]
+		if !ok && read.amended {
+			e, ok = m.dirty[key]
+			// Regardless of whether the comparableEntry was present, record a miss: this key
+			// will take the slow path until the dirty map is promoted to the read
+			// map.
+			m.missLocked()
+		}
+		m.mu.Unlock()
+	}
+	if !ok {
+		return *new(V), false
+	}
+	return e.load()
+}
+
+func (e *comparableEntry[V]) load() (value V, ok bool) {
+	p := atomic.LoadPointer(&e.p)
+	if p == nil || p == comparableExpunged {
+		return value, false
+	}
+	return *(*V)(p), true
+}
+
+// Store sets the value for a key.
+func (m *ComparableMap[K, V]) Store(key K, value V) {
+	_, _ = m.Swap(key, value)
+}
+
+// Clear deletes all the entries, resulting in an empty ComparableMap.
+func (m *ComparableMap[K, V]) Clear() {
+	read := m.loadReadOnly()
+	if len(read.m) == 0 && !read.amended {
+		// Avoid allocating a new comparableReadOnly when the map is already clear.
+		return
+	}
+
+	m.mu.Lock()
+	defer m.mu.Unlock()
+
+	read = m.loadReadOnly()
+	if len(read.m) > 0 || read.amended {
+		m.read.Store(&comparableReadOnly[K, V]{})
+	}
+
+	clear(m.dirty)
+	// Don't immediately promote the newly-cleared dirty map on the next operation.
+	m.misses = 0
+}
+
+// tryCompareAndSwap compare the comparableEntry with the given old value and swaps
+// it with a new value if the comparableEntry is equal to the old value, and the comparableEntry
+// has not been comparableExpunged.
+//
+// If the comparableEntry is comparableExpunged, tryCompareAndSwap returns false and leaves
+// the comparableEntry unchanged.
+func (e *comparableEntry[V]) tryCompareAndSwap(old V, new V) bool {
+	p := atomic.LoadPointer(&e.p)
+	if p == nil || p == comparableExpunged || *(*V)(p) != old { // XXX
+		return false
+	}
+
+	// Copy the pointer after the first load to make this method more amenable
+	// to escape analysis: if the comparison fails from the start, we shouldn't
+	// bother heap-allocating a pointer to store.
+	nc := new
+	for {
+		if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(&nc)) {
+			return true
+		}
+		p = atomic.LoadPointer(&e.p)
+		if p == nil || p == comparableExpunged || *(*V)(p) != old {
+			return false
+		}
+	}
+}
+
+// unexpungeLocked ensures that the comparableEntry is not marked as comparableExpunged.
+//
+// If the comparableEntry was previously comparableExpunged, it must be added to the dirty map
+// before m.mu is unlocked.
+func (e *comparableEntry[V]) unexpungeLocked() (wasExpunged bool) {
+	return atomic.CompareAndSwapPointer(&e.p, comparableExpunged, nil)
+}
+
+// swapLocked unconditionally swaps a value into the comparableEntry.
+//
+// The comparableEntry must be known not to be comparableExpunged.
+func (e *comparableEntry[V]) swapLocked(i *V) *V {
+	return (*V)(atomic.SwapPointer(&e.p, unsafe.Pointer(i)))
+}
+
+// LoadOrStore returns the existing value for the key if present.
+// Otherwise, it stores and returns the given value.
+// The loaded result is true if the value was loaded, false if stored.
+func (m *ComparableMap[K, V]) LoadOrStore(key K, value V) (actual V, loaded bool) {
+	// Avoid locking if it's a clean hit.
+	read := m.loadReadOnly()
+	if e, ok := read.m[key]; ok {
+		actual, loaded, ok := e.tryLoadOrStore(value)
+		if ok {
+			return actual, loaded
+		}
+	}
+
+	m.mu.Lock()
+	read = m.loadReadOnly()
+	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 {
+			// 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.Store(&comparableReadOnly[K, V]{m: read.m, amended: true})
+		}
+		m.dirty[key] = newComparableEntry(value)
+		actual, loaded = value, false
+	}
+	m.mu.Unlock()
+
+	return actual, loaded
+}
+
+// tryLoadOrStore atomically loads or stores a value if the comparableEntry is not
+// comparableExpunged.
+//
+// If the comparableEntry is comparableExpunged, tryLoadOrStore leaves the comparableEntry unchanged and
+// returns with ok==false.
+func (e *comparableEntry[V]) tryLoadOrStore(i V) (actual V, loaded, ok bool) {
+	p := atomic.LoadPointer(&e.p)
+	if p == comparableExpunged {
+		return actual, false, false
+	}
+	if p != nil {
+		return *(*V)(p), true, true
+	}
+
+	// Copy the pointer after the first load to make this method more amenable
+	// to escape analysis: if we hit the "load" path or the comparableEntry is comparableExpunged, we
+	// shouldn't bother heap-allocating.
+	ic := i
+	for {
+		if atomic.CompareAndSwapPointer(&e.p, nil, unsafe.Pointer(&ic)) {
+			return i, false, true
+		}
+		p = atomic.LoadPointer(&e.p)
+		if p == comparableExpunged {
+			return actual, false, false
+		}
+		if p != nil {
+			return *(*V)(p), true, true
+		}
+	}
+}
+
+// LoadAndDelete deletes the value for a key, returning the previous value if any.
+// The loaded result reports whether the key was present.
+func (m *ComparableMap[K, V]) LoadAndDelete(key K) (value V, loaded bool) {
+	read := m.loadReadOnly()
+	e, ok := read.m[key]
+	if !ok && read.amended {
+		m.mu.Lock()
+		read = m.loadReadOnly()
+		e, ok = read.m[key]
+		if !ok && read.amended {
+			e, ok = m.dirty[key]
+			delete(m.dirty, key)
+			// Regardless of whether the comparableEntry was present, record a miss: this key
+			// will take the slow path until the dirty map is promoted to the read
+			// map.
+			m.missLocked()
+		}
+		m.mu.Unlock()
+	}
+	if ok {
+		return e.delete()
+	}
+	return value, false
+}
+
+// Delete deletes the value for a key.
+func (m *ComparableMap[K, V]) Delete(key K) {
+	m.LoadAndDelete(key)
+}
+
+func (e *comparableEntry[V]) delete() (value V, ok bool) {
+	for {
+		p := atomic.LoadPointer(&e.p)
+		if p == nil || p == comparableExpunged {
+			return value, false
+		}
+		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
+			return *(*V)(p), true
+		}
+	}
+}
+
+// trySwap swaps a value if the comparableEntry has not been comparableExpunged.
+//
+// If the comparableEntry is comparableExpunged, trySwap returns false and leaves the comparableEntry
+// unchanged.
+func (e *comparableEntry[V]) trySwap(i *V) (*V, bool) {
+	for {
+		p := atomic.LoadPointer(&e.p)
+		if p == comparableExpunged {
+			return nil, false
+		}
+		if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
+			return (*V)(p), true
+		}
+	}
+}
+
+// Swap swaps the value for a key and returns the previous value if any.
+// The loaded result reports whether the key was present.
+func (m *ComparableMap[K, V]) Swap(key K, value V) (previous V, loaded bool) {
+	read := m.loadReadOnly()
+	if e, ok := read.m[key]; ok {
+		if v, ok := e.trySwap(&value); ok {
+			if v == nil {
+				return previous, false
+			}
+			return *v, true
+		}
+	}
+
+	m.mu.Lock()
+	read = m.loadReadOnly()
+	if e, ok := read.m[key]; ok {
+		if e.unexpungeLocked() {
+			// The comparableEntry was previously comparableExpunged, which implies that there is a
+			// non-nil dirty map and this comparableEntry is not in it.
+			m.dirty[key] = e
+		}
+		if v := e.swapLocked(&value); v != nil {
+			loaded = true
+			previous = *v
+		}
+	} else if e, ok := m.dirty[key]; ok {
+		if v := e.swapLocked(&value); v != nil {
+			loaded = true
+			previous = *v
+		}
+	} else {
+		if !read.amended {
+			// 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.Store(&comparableReadOnly[K, V]{m: read.m, amended: true})
+		}
+		m.dirty[key] = newComparableEntry(value)
+	}
+	m.mu.Unlock()
+	return previous, loaded
+}
+
+// CompareAndSwap swaps the old and new values for key
+// if the value stored in the map is equal to old.
+// The old value must be of a comparable type.
+func (m *ComparableMap[K, V]) CompareAndSwap(key K, old, new V) (swapped bool) {
+	read := m.loadReadOnly()
+	if e, ok := read.m[key]; ok {
+		return e.tryCompareAndSwap(old, new)
+	} else if !read.amended {
+		return false // No existing value for key.
+	}
+
+	m.mu.Lock()
+	defer m.mu.Unlock()
+	read = m.loadReadOnly()
+	swapped = false
+	if e, ok := read.m[key]; ok {
+		swapped = e.tryCompareAndSwap(old, new)
+	} else if e, ok := m.dirty[key]; ok {
+		swapped = e.tryCompareAndSwap(old, new)
+		// We needed to lock mu in order to load the comparableEntry for key,
+		// and the operation didn't change the set of keys in the map
+		// (so it would be made more efficient by promoting the dirty
+		// map to read-only).
+		// Count it as a miss so that we will eventually switch to the
+		// more efficient steady state.
+		m.missLocked()
+	}
+	return swapped
+}
+
+// CompareAndDelete deletes the comparableEntry for key if its value is equal to old.
+// The old value must be of a comparable type.
+//
+// If there is no current value for key in the map, CompareAndDelete
+// returns false (even if the old value is a nil pointer).
+func (m *ComparableMap[K, V]) CompareAndDelete(key K, old V) (deleted bool) {
+	read := m.loadReadOnly()
+	e, ok := read.m[key]
+	if !ok && read.amended {
+		m.mu.Lock()
+		read = m.loadReadOnly()
+		e, ok = read.m[key]
+		if !ok && read.amended {
+			e, ok = m.dirty[key]
+			// Don't delete key from m.dirty: we still need to do the “compare” part
+			// of the operation. The comparableEntry will eventually be comparableExpunged when the
+			// dirty map is promoted to the read map.
+			//
+			// Regardless of whether the comparableEntry was present, record a miss: this key
+			// will take the slow path until the dirty map is promoted to the read
+			// map.
+			m.missLocked()
+		}
+		m.mu.Unlock()
+	}
+	for ok {
+		p := atomic.LoadPointer(&e.p)
+		if p == nil || p == comparableExpunged || *(*V)(p) != old {
+			return false
+		}
+		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
+			return true
+		}
+	}
+	return false
+}
+
+// Range calls f sequentially for each key and value present in the map.
+// If f returns false, range stops the iteration.
+//
+// Range does not necessarily correspond to any consistent snapshot of the ComparableMap's
+// contents: no key will be visited more than once, but if the value for any key
+// is stored or deleted concurrently (including by f), Range may reflect any
+// mapping for that key from any point during the Range call. Range does not
+// block other methods on the receiver; even f itself may call any method on m.
+//
+// Range may be O(N) with the number of elements in the map even if f returns
+// false after a constant number of calls.
+func (m *ComparableMap[K, V]) Range(f func(key K, value V) bool) {
+	// We need to be able to iterate over all of the keys that were already
+	// present at the start of the call to Range.
+	// If read.amended is false, then read.m satisfies that property without
+	// requiring us to hold m.mu for a long time.
+	read := m.loadReadOnly()
+	if read.amended {
+		// m.dirty contains keys not in read.m. Fortunately, Range is already O(N)
+		// (assuming the caller does not break out early), so a call to Range
+		// amortizes an entire copy of the map: we can promote the dirty copy
+		// immediately!
+		m.mu.Lock()
+		read = m.loadReadOnly()
+		if read.amended {
+			read = comparableReadOnly[K, V]{m: m.dirty}
+			copyRead := read
+			m.read.Store(&copyRead)
+			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
+		}
+	}
+}
+
+func (m *ComparableMap[K, V]) missLocked() {
+	m.misses++
+	if m.misses < len(m.dirty) {
+		return
+	}
+	m.read.Store(&comparableReadOnly[K, V]{m: m.dirty})
+	m.dirty = nil
+	m.misses = 0
+}
+
+func (m *ComparableMap[K, V]) dirtyLocked() {
+	if m.dirty != nil {
+		return
+	}
+
+	read := m.loadReadOnly()
+	m.dirty = make(map[K]*comparableEntry[V], len(read.m))
+	for k, e := range read.m {
+		if !e.tryExpungeLocked() {
+			m.dirty[k] = e
+		}
+	}
+}
+
+func (e *comparableEntry[V]) tryExpungeLocked() (isExpunged bool) {
+	p := atomic.LoadPointer(&e.p)
+	for p == nil {
+		if atomic.CompareAndSwapPointer(&e.p, nil, comparableExpunged) {
+			return true
+		}
+		p = atomic.LoadPointer(&e.p)
+	}
+	return p == comparableExpunged
+}
diff --git a/cmap/map.go b/cmap/map.go
index bfc0070..7a1fe5b 100644
--- a/cmap/map.go
+++ b/cmap/map.go
@@ -14,7 +14,7 @@ import (
 	"unsafe"
 )
 
-// Map[K comparable, V comparable] is like a Go map[K]V but is safe for concurrent use
+// Map[K comparable, V any] is like a Go map[K]V but is safe for concurrent use
 // by multiple goroutines without additional locking or coordination.  Loads,
 // stores, and deletes run in amortized constant time.
 //
@@ -37,7 +37,7 @@ import (
 // and [Map.CompareAndDelete] is a write operation when it returns deleted set to true.
 //
 // [the Go memory model]: https://go.dev/ref/mem
-type Map[K comparable, V comparable] struct {
+type Map[K comparable, V any] struct {
 	mu sync.Mutex
 
 	// read contains the portion of the map's contents that are safe for
@@ -73,7 +73,7 @@ type Map[K comparable, V comparable] struct {
 }
 
 // readOnly is an immutable struct stored atomically in the Map.read field.
-type readOnly[K comparable, V comparable] struct {
+type readOnly[K comparable, V any] struct {
 	m       map[K]*entry[V]
 	amended bool // true if the dirty map contains some key not in m.
 }
@@ -83,7 +83,7 @@ type readOnly[K comparable, V comparable] struct {
 var expunged = unsafe.Pointer(new(any))
 
 // An entry is a slot in the map corresponding to a particular key.
-type entry[V comparable] struct {
+type entry[V any] struct {
 	// p points to the value stored for the entry.
 	//
 	// If p == nil, the entry has been deleted, and either m.dirty == nil or
@@ -106,7 +106,7 @@ type entry[V comparable] struct {
 	p unsafe.Pointer
 }
 
-func newEntry[V comparable](i V) *entry[V] {
+func newEntry[V any](i V) *entry[V] {
 	return &entry[V]{p: unsafe.Pointer(&i)}
 }
 
@@ -179,33 +179,6 @@ func (m *Map[K, V]) Clear() {
 	m.misses = 0
 }
 
-// tryCompareAndSwap compare the entry with the given old value and swaps
-// it with a new value if the entry is equal to the old value, and the entry
-// has not been expunged.
-//
-// If the entry is expunged, tryCompareAndSwap returns false and leaves
-// the entry unchanged.
-func (e *entry[V]) tryCompareAndSwap(old V, new V) bool {
-	p := atomic.LoadPointer(&e.p)
-	if p == nil || p == expunged || *(*V)(p) != old { // XXX
-		return false
-	}
-
-	// Copy the pointer after the first load to make this method more amenable
-	// to escape analysis: if the comparison fails from the start, we shouldn't
-	// bother heap-allocating a pointer to store.
-	nc := new
-	for {
-		if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(&nc)) {
-			return true
-		}
-		p = atomic.LoadPointer(&e.p)
-		if p == nil || p == expunged || *(*V)(p) != old {
-			return false
-		}
-	}
-}
-
 // unexpungeLocked ensures that the entry is not marked as expunged.
 //
 // If the entry was previously expunged, it must be added to the dirty map
@@ -392,73 +365,6 @@ func (m *Map[K, V]) Swap(key K, value V) (previous V, loaded bool) {
 	return previous, loaded
 }
 
-// CompareAndSwap swaps the old and new values for key
-// if the value stored in the map is equal to old.
-// The old value must be of a comparable type.
-func (m *Map[K, V]) CompareAndSwap(key K, old, new V) (swapped bool) {
-	read := m.loadReadOnly()
-	if e, ok := read.m[key]; ok {
-		return e.tryCompareAndSwap(old, new)
-	} else if !read.amended {
-		return false // No existing value for key.
-	}
-
-	m.mu.Lock()
-	defer m.mu.Unlock()
-	read = m.loadReadOnly()
-	swapped = false
-	if e, ok := read.m[key]; ok {
-		swapped = e.tryCompareAndSwap(old, new)
-	} else if e, ok := m.dirty[key]; ok {
-		swapped = e.tryCompareAndSwap(old, new)
-		// We needed to lock mu in order to load the entry for key,
-		// and the operation didn't change the set of keys in the map
-		// (so it would be made more efficient by promoting the dirty
-		// map to read-only).
-		// Count it as a miss so that we will eventually switch to the
-		// more efficient steady state.
-		m.missLocked()
-	}
-	return swapped
-}
-
-// CompareAndDelete deletes the entry for key if its value is equal to old.
-// The old value must be of a comparable type.
-//
-// If there is no current value for key in the map, CompareAndDelete
-// returns false (even if the old value is a nil pointer).
-func (m *Map[K, V]) CompareAndDelete(key K, old V) (deleted bool) {
-	read := m.loadReadOnly()
-	e, ok := read.m[key]
-	if !ok && read.amended {
-		m.mu.Lock()
-		read = m.loadReadOnly()
-		e, ok = read.m[key]
-		if !ok && read.amended {
-			e, ok = m.dirty[key]
-			// Don't delete key from m.dirty: we still need to do the “compare” part
-			// of the operation. The entry will eventually be expunged when the
-			// dirty map is promoted to the read map.
-			//
-			// Regardless of whether the entry was present, record a miss: this key
-			// will take the slow path until the dirty map is promoted to the read
-			// map.
-			m.missLocked()
-		}
-		m.mu.Unlock()
-	}
-	for ok {
-		p := atomic.LoadPointer(&e.p)
-		if p == nil || p == expunged || *(*V)(p) != old {
-			return false
-		}
-		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
-			return true
-		}
-	}
-	return false
-}
-
 // Range calls f sequentially for each key and value present in the map.
 // If f returns false, range stops the iteration.
 //
diff --git a/cmap/map_test.go b/cmap/map_test.go
deleted file mode 100644
index c407c18..0000000
--- a/cmap/map_test.go
+++ /dev/null
@@ -1,76 +0,0 @@
-// This is directly ported from github.com/SaveTheRbtz/generic-sync-map-go
-// and does not test the new CompareAndSwap and related functions yet.
-// Copyright 2016 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package cmap_test
-
-import (
-	"math/rand"
-	"runtime"
-	"sync"
-	"testing"
-
-	"go.lindenii.runxiyu.org/lindenii-common/cmap"
-)
-
-func TestConcurrentRange(t *testing.T) {
-	const mapSize = 1 << 10
-
-	m := new(cmap.Map[int64, int64])
-	for n := int64(1); n <= mapSize; n++ {
-		m.Store(n, int64(n))
-	}
-
-	done := make(chan struct{})
-	var wg sync.WaitGroup
-	defer func() {
-		close(done)
-		wg.Wait()
-	}()
-	for g := int64(runtime.GOMAXPROCS(0)); g > 0; g-- {
-		r := rand.New(rand.NewSource(g))
-		wg.Add(1)
-		go func(g int64) {
-			defer wg.Done()
-			for i := int64(0); ; i++ {
-				select {
-				case <-done:
-					return
-				default:
-				}
-				for n := int64(1); n < mapSize; n++ {
-					if r.Int63n(mapSize) == 0 {
-						m.Store(n, n*i*g)
-					} else {
-						m.Load(n)
-					}
-				}
-			}
-		}(g)
-	}
-
-	iters := 1 << 10
-	if testing.Short() {
-		iters = 16
-	}
-	for n := iters; n > 0; n-- {
-		seen := make(map[int64]bool, mapSize)
-
-		m.Range(func(k, v int64) bool {
-			if v%k != 0 {
-				t.Fatalf("while Storing multiples of %v, Range saw value %v", k, v)
-			}
-			if seen[k] {
-				t.Fatalf("Range visited key %v twice", k)
-			}
-			seen[k] = true
-			return true
-		})
-
-		if len(seen) != mapSize {
-			t.Fatalf("Range visited %v elements of %v-element Map", len(seen), mapSize)
-		}
-	}
-}