Repository: puzpuzpuz/xsync
Pull request #64 (2022-10-28 16:28:51)

Add Clear method to Map and MapOf


Patch:
diff --git a/map.go b/map.go
index a84a791..04ac7ea 100644
--- a/map.go
+++ b/map.go
@@ -15,6 +15,7 @@ type mapResizeHint int
 const (
 	mapGrowHint   mapResizeHint = 0
 	mapShrinkHint mapResizeHint = 1
+	mapClearHint  mapResizeHint = 2
 )
 
 const (
@@ -379,12 +380,17 @@ func (m *Map) resize(table *mapTable, hint mapResizeHint) {
 			m.resizeMu.Unlock()
 			return
 		}
+	case mapClearHint:
+		newTable = newMapTable(minMapTableLen)
 	default:
 		panic(fmt.Sprintf("unexpected resize hint: %d", hint))
 	}
-	for i := 0; i < tableLen; i++ {
-		copied := copyBucket(&table.buckets[i], newTable)
-		newTable.addSizePlain(uint64(i), copied)
+	// Copy the data only if we're not clearing the map.
+	if hint != mapClearHint {
+		for i := 0; i < tableLen; i++ {
+			copied := copyBucket(&table.buckets[i], newTable)
+			newTable.addSizePlain(uint64(i), copied)
+		}
 	}
 	// Publish the new table and wake up all waiters.
 	atomic.StorePointer(&m.table, unsafe.Pointer(newTable))
@@ -578,6 +584,12 @@ func copyRangeEntries(b *bucketPadded, destEntries *[entriesPerMapBucket]rangeEn
 	return n
 }
 
+// Clear deletes all keys and values currently stored in the map.
+func (m *Map) Clear() {
+	table := (*mapTable)(atomic.LoadPointer(&m.table))
+	m.resize(table, mapClearHint)
+}
+
 // Size returns current size of the map.
 func (m *Map) Size() int {
 	table := (*mapTable)(atomic.LoadPointer(&m.table))
diff --git a/mapof.go b/mapof.go
index adf4134..048e186 100644
--- a/mapof.go
+++ b/mapof.go
@@ -312,12 +312,17 @@ func (m *MapOf[K, V]) resize(table *mapTable, hint mapResizeHint) {
 			m.resizeMu.Unlock()
 			return
 		}
+	case mapClearHint:
+		newTable = newMapTable(minMapTableLen)
 	default:
 		panic(fmt.Sprintf("unexpected resize hint: %d", hint))
 	}
-	for i := 0; i < tableLen; i++ {
-		copied := copyBucketOf(&table.buckets[i], newTable, m.hasher)
-		newTable.addSizePlain(uint64(i), copied)
+	// Copy the data only if we're not clearing the map.
+	if hint != mapClearHint {
+		for i := 0; i < tableLen; i++ {
+			copied := copyBucketOf(&table.buckets[i], newTable, m.hasher)
+			newTable.addSizePlain(uint64(i), copied)
+		}
 	}
 	// Publish the new table and wake up all waiters.
 	atomic.StorePointer(&m.table, unsafe.Pointer(newTable))
@@ -449,6 +454,12 @@ func (m *MapOf[K, V]) Range(f func(key K, value V) bool) {
 	}
 }
 
+// Clear deletes all keys and values currently stored in the map.
+func (m *MapOf[K, V]) Clear() {
+	table := (*mapTable)(atomic.LoadPointer(&m.table))
+	m.resize(table, mapClearHint)
+}
+
 // Size returns current size of the map.
 func (m *MapOf[K, V]) Size() int {
 	table := (*mapTable)(atomic.LoadPointer(&m.table))


Test patch:
diff --git a/map_test.go b/map_test.go
index fff8b0e..92d00c0 100644
--- a/map_test.go
+++ b/map_test.go
@@ -367,6 +367,15 @@ func TestMapSerialStoreThenLoadAndDelete(t *testing.T) {
 	}
 }
 
+func sizeBasedOnRange(m *Map) int {
+	size := 0
+	m.Range(func(key string, value interface{}) bool {
+		size++
+		return true
+	})
+	return size
+}
+
 func TestMapSize(t *testing.T) {
 	const numEntries = 1000
 	m := NewMap()
@@ -382,6 +391,10 @@ func TestMapSize(t *testing.T) {
 		if size != expectedSize {
 			t.Errorf("size of %d was expected, got: %d", expectedSize, size)
 		}
+		rsize := sizeBasedOnRange(m)
+		if size != rsize {
+			t.Errorf("size does not match number of entries in Range: %v, %v", size, rsize)
+		}
 	}
 	for i := 0; i < numEntries; i++ {
 		m.Delete(strconv.Itoa(i))
@@ -390,6 +403,31 @@ func TestMapSize(t *testing.T) {
 		if size != expectedSize {
 			t.Errorf("size of %d was expected, got: %d", expectedSize, size)
 		}
+		rsize := sizeBasedOnRange(m)
+		if size != rsize {
+			t.Errorf("size does not match number of entries in Range: %v, %v", size, rsize)
+		}
+	}
+}
+
+func TestMapClear(t *testing.T) {
+	const numEntries = 1000
+	m := NewMap()
+	for i := 0; i < numEntries; i++ {
+		m.Store(strconv.Itoa(i), i)
+	}
+	size := m.Size()
+	if size != numEntries {
+		t.Errorf("size of %d was expected, got: %d", numEntries, size)
+	}
+	m.Clear()
+	size = m.Size()
+	if size != 0 {
+		t.Errorf("zero size was expected, got: %d", size)
+	}
+	rsize := sizeBasedOnRange(m)
+	if rsize != 0 {
+		t.Errorf("zero number of entries in Range was expected, got: %d", rsize)
 	}
 }
 
@@ -508,7 +546,7 @@ func parallelRandResizer(t *testing.T, m *Map, numIters, numEntries int, cdone c
 }
 
 func TestMapParallelResize(t *testing.T) {
-	const numIters = 1000
+	const numIters = 1_000
 	const numEntries = 2 * EntriesPerMapBucket * MinMapTableLen
 	m := NewMap()
 	cdone := make(chan bool)
@@ -532,11 +570,43 @@ func TestMapParallelResize(t *testing.T) {
 	if s > numEntries {
 		t.Errorf("unexpected size: %v", s)
 	}
-	rs := 0
-	m.Range(func(key string, value interface{}) bool {
-		rs++
-		return true
-	})
+	rs := sizeBasedOnRange(m)
+	if s != rs {
+		t.Errorf("size does not match number of entries in Range: %v, %v", s, rs)
+	}
+}
+
+func parallelRandClearer(t *testing.T, m *Map, numIters, numEntries int, cdone chan bool) {
+	r := rand.New(rand.NewSource(time.Now().UnixNano()))
+	for i := 0; i < numIters; i++ {
+		coin := r.Int63n(2)
+		for j := 0; j < numEntries; j++ {
+			if coin == 1 {
+				m.Store(strconv.Itoa(j), j)
+			} else {
+				m.Clear()
+			}
+		}
+	}
+	cdone <- true
+}
+
+func TestMapParallelClear(t *testing.T) {
+	const numIters = 100
+	const numEntries = 1_000
+	m := NewMap()
+	cdone := make(chan bool)
+	go parallelRandClearer(t, m, numIters, numEntries, cdone)
+	go parallelRandClearer(t, m, numIters, numEntries, cdone)
+	// Wait for the goroutines to finish.
+	<-cdone
+	<-cdone
+	// Verify map size.
+	s := m.Size()
+	if s > numEntries {
+		t.Errorf("unexpected size: %v", s)
+	}
+	rs := sizeBasedOnRange(m)
 	if s != rs {
 		t.Errorf("size does not match number of entries in Range: %v, %v", s, rs)
 	}
diff --git a/mapof_test.go b/mapof_test.go
index ac8b10f..fb8a26d 100644
--- a/mapof_test.go
+++ b/mapof_test.go
@@ -505,6 +505,15 @@ func TestTypedMapOfSerialStoreThenLoadAndDelete(t *testing.T) {
 	}
 }
 
+func sizeBasedOnTypedRange(m *MapOf[string, int]) int {
+	size := 0
+	m.Range(func(key string, value int) bool {
+		size++
+		return true
+	})
+	return size
+}
+
 func TestMapOfSize(t *testing.T) {
 	const numEntries = 1000
 	m := NewMapOf[int]()
@@ -520,6 +529,10 @@ func TestMapOfSize(t *testing.T) {
 		if size != expectedSize {
 			t.Errorf("size of %d was expected, got: %d", expectedSize, size)
 		}
+		rsize := sizeBasedOnTypedRange(m)
+		if size != rsize {
+			t.Errorf("size does not match number of entries in Range: %v, %v", size, rsize)
+		}
 	}
 	for i := 0; i < numEntries; i++ {
 		m.Delete(strconv.Itoa(i))
@@ -528,6 +541,31 @@ func TestMapOfSize(t *testing.T) {
 		if size != expectedSize {
 			t.Errorf("size of %d was expected, got: %d", expectedSize, size)
 		}
+		rsize := sizeBasedOnTypedRange(m)
+		if size != rsize {
+			t.Errorf("size does not match number of entries in Range: %v, %v", size, rsize)
+		}
+	}
+}
+
+func TestMapOfClear(t *testing.T) {
+	const numEntries = 1000
+	m := NewMapOf[int]()
+	for i := 0; i < numEntries; i++ {
+		m.Store(strconv.Itoa(i), i)
+	}
+	size := m.Size()
+	if size != numEntries {
+		t.Errorf("size of %d was expected, got: %d", numEntries, size)
+	}
+	m.Clear()
+	size = m.Size()
+	if size != 0 {
+		t.Errorf("zero size was expected, got: %d", size)
+	}
+	rsize := sizeBasedOnTypedRange(m)
+	if rsize != 0 {
+		t.Errorf("zero number of entries in Range was expected, got: %d", rsize)
 	}
 }
 
@@ -630,15 +668,15 @@ func TestMapOfParallelResize_GrowOnly(t *testing.T) {
 	}
 }
 
-func parallelRandTypedResizer(t *testing.T, m *MapOf[int, int], numIters, numEntries int, cdone chan bool) {
+func parallelRandTypedResizer(t *testing.T, m *MapOf[string, int], numIters, numEntries int, cdone chan bool) {
 	r := rand.New(rand.NewSource(time.Now().UnixNano()))
 	for i := 0; i < numIters; i++ {
 		coin := r.Int63n(2)
 		for j := 0; j < numEntries; j++ {
 			if coin == 1 {
-				m.Store(j, j)
+				m.Store(strconv.Itoa(j), j)
 			} else {
-				m.Delete(j)
+				m.Delete(strconv.Itoa(j))
 			}
 		}
 	}
@@ -646,9 +684,9 @@ func parallelRandTypedResizer(t *testing.T, m *MapOf[int, int], numIters, numEnt
 }
 
 func TestMapOfParallelResize(t *testing.T) {
-	const numIters = 1000
+	const numIters = 1_000
 	const numEntries = 2 * EntriesPerMapBucket * MinMapTableLen
-	m := NewIntegerMapOf[int, int]()
+	m := NewMapOf[int]()
 	cdone := make(chan bool)
 	go parallelRandTypedResizer(t, m, numIters, numEntries, cdone)
 	go parallelRandTypedResizer(t, m, numIters, numEntries, cdone)
@@ -657,7 +695,7 @@ func TestMapOfParallelResize(t *testing.T) {
 	<-cdone
 	// Verify map contents.
 	for i := 0; i < numEntries; i++ {
-		v, ok := m.Load(i)
+		v, ok := m.Load(strconv.Itoa(i))
 		if !ok {
 			// The entry may be deleted and that's ok.
 			continue
@@ -670,11 +708,43 @@ func TestMapOfParallelResize(t *testing.T) {
 	if s > numEntries {
 		t.Errorf("unexpected size: %v", s)
 	}
-	rs := 0
-	m.Range(func(key int, value int) bool {
-		rs++
-		return true
-	})
+	rs := sizeBasedOnTypedRange(m)
+	if s != rs {
+		t.Errorf("size does not match number of entries in Range: %v, %v", s, rs)
+	}
+}
+
+func parallelRandTypedClearer(t *testing.T, m *MapOf[string, int], numIters, numEntries int, cdone chan bool) {
+	r := rand.New(rand.NewSource(time.Now().UnixNano()))
+	for i := 0; i < numIters; i++ {
+		coin := r.Int63n(2)
+		for j := 0; j < numEntries; j++ {
+			if coin == 1 {
+				m.Store(strconv.Itoa(j), j)
+			} else {
+				m.Clear()
+			}
+		}
+	}
+	cdone <- true
+}
+
+func TestMapOfParallelClear(t *testing.T) {
+	const numIters = 100
+	const numEntries = 1_000
+	m := NewMapOf[int]()
+	cdone := make(chan bool)
+	go parallelRandTypedClearer(t, m, numIters, numEntries, cdone)
+	go parallelRandTypedClearer(t, m, numIters, numEntries, cdone)
+	// Wait for the goroutines to finish.
+	<-cdone
+	<-cdone
+	// Verify map size.
+	s := m.Size()
+	if s > numEntries {
+		t.Errorf("unexpected size: %v", s)
+	}
+	rs := sizeBasedOnTypedRange(m)
 	if s != rs {
 		t.Errorf("size does not match number of entries in Range: %v, %v", s, rs)
 	}