aboutsummaryrefslogtreecommitdiff
path: root/immutable_test.go
diff options
context:
space:
mode:
Diffstat (limited to 'immutable_test.go')
-rw-r--r--immutable_test.go145
1 files changed, 117 insertions, 28 deletions
diff --git a/immutable_test.go b/immutable_test.go
index ca2393b..9c3f548 100644
--- a/immutable_test.go
+++ b/immutable_test.go
@@ -1545,7 +1545,7 @@ func TestInternalSortedMapLeafNode(t *testing.T) {
for _, i := range rand.Perm(32) {
var resized bool
var splitNode sortedMapNode
- node, splitNode = node.set(i, i*10, &cmpr, &resized)
+ node, splitNode = node.set(i, i*10, &cmpr, false, &resized)
if !resized {
t.Fatal("expected resize")
} else if splitNode != nil {
@@ -1578,11 +1578,11 @@ func TestInternalSortedMapLeafNode(t *testing.T) {
var node sortedMapNode = &sortedMapLeafNode{}
for _, i := range rand.Perm(32) {
var resized bool
- node, _ = node.set(i, i*2, &cmpr, &resized)
+ node, _ = node.set(i, i*2, &cmpr, false, &resized)
}
for _, i := range rand.Perm(32) {
var resized bool
- node, _ = node.set(i, i*3, &cmpr, &resized)
+ node, _ = node.set(i, i*3, &cmpr, false, &resized)
if resized {
t.Fatal("expected no resize")
}
@@ -1602,12 +1602,12 @@ func TestInternalSortedMapLeafNode(t *testing.T) {
var node sortedMapNode = &sortedMapLeafNode{}
for i := 0; i < 32; i++ {
var resized bool
- node, _ = node.set(i, i*10, &cmpr, &resized)
+ node, _ = node.set(i, i*10, &cmpr, false, &resized)
}
// Add one more and expect split.
var resized bool
- newNode, splitNode := node.set(32, 320, &cmpr, &resized)
+ newNode, splitNode := node.set(32, 320, &cmpr, false, &resized)
// Verify node contents.
newLeafNode, ok := newNode.(*sortedMapLeafNode)
@@ -1658,7 +1658,7 @@ func TestInternalSortedMapBranchNode(t *testing.T) {
var resized bool
var splitNode sortedMapNode
- node, splitNode = node.set(key, key*10, &cmpr, &resized)
+ node, splitNode = node.set(key, key*10, &cmpr, false, &resized)
if key == leaf0.entries[0].key || key == leaf1.entries[0].key {
if resized {
t.Fatalf("expected no resize: key=%d", key)
@@ -1701,7 +1701,7 @@ func TestInternalSortedMapBranchNode(t *testing.T) {
// Add one more and expect split.
var resized bool
- newNode, splitNode := node.set((32 * 32), (32*32)*100, &cmpr, &resized)
+ newNode, splitNode := node.set((32 * 32), (32*32)*100, &cmpr, false, &resized)
// Verify node contents.
var idx int
@@ -1843,7 +1843,7 @@ func TestSortedMap_Set(t *testing.T) {
})
RunRandom(t, "Random", func(t *testing.T, rand *rand.Rand) {
- m := NewTestSortedMap()
+ m := NewTSortedMap()
for j := 0; j < 10000; j++ {
switch rand.Intn(2) {
case 1: // overwrite
@@ -1950,7 +1950,7 @@ func TestSortedMap_Delete(t *testing.T) {
})
RunRandom(t, "Random", func(t *testing.T, rand *rand.Rand) {
- m := NewTestSortedMap()
+ m := NewTSortedMap()
for j := 0; j < 10000; j++ {
switch rand.Intn(8) {
case 0: // overwrite
@@ -1966,6 +1966,16 @@ func TestSortedMap_Delete(t *testing.T) {
if err := m.Validate(); err != nil {
t.Fatal(err)
}
+
+ // Delete all keys.
+ keys := make([]int, len(m.keys))
+ copy(keys, m.keys)
+ for _, k := range keys {
+ m.Delete(k)
+ }
+ if err := m.Validate(); err != nil {
+ t.Fatal(err)
+ }
})
}
@@ -2057,21 +2067,23 @@ func TestSortedMap_Iterator(t *testing.T) {
})
}
-// TestSortedMap represents a combined immutable and stdlib sorted map.
-type TestSortedMap struct {
+// TSortedMap represents a combined immutable and stdlib sorted map.
+type TSortedMap struct {
im, prev *SortedMap
+ builder *SortedMapBuilder
std map[int]int
keys []int
}
-func NewTestSortedMap() *TestSortedMap {
- return &TestSortedMap{
- im: NewSortedMap(nil),
- std: make(map[int]int),
+func NewTSortedMap() *TSortedMap {
+ return &TSortedMap{
+ im: NewSortedMap(nil),
+ builder: NewSortedMapBuilder(NewSortedMap(nil)),
+ std: make(map[int]int),
}
}
-func (m *TestSortedMap) NewKey(rand *rand.Rand) int {
+func (m *TSortedMap) NewKey(rand *rand.Rand) int {
for {
k := rand.Int()
if _, ok := m.std[k]; !ok {
@@ -2080,16 +2092,17 @@ func (m *TestSortedMap) NewKey(rand *rand.Rand) int {
}
}
-func (m *TestSortedMap) ExistingKey(rand *rand.Rand) int {
+func (m *TSortedMap) ExistingKey(rand *rand.Rand) int {
if len(m.keys) == 0 {
return 0
}
return m.keys[rand.Intn(len(m.keys))]
}
-func (m *TestSortedMap) Set(k, v int) {
+func (m *TSortedMap) Set(k, v int) {
m.prev = m.im
m.im = m.im.Set(k, v)
+ m.builder.Set(k, v)
if _, ok := m.std[k]; !ok {
m.keys = append(m.keys, k)
@@ -2098,9 +2111,10 @@ func (m *TestSortedMap) Set(k, v int) {
m.std[k] = v
}
-func (m *TestSortedMap) Delete(k int) {
+func (m *TSortedMap) Delete(k int) {
m.prev = m.im
m.im = m.im.Delete(k)
+ m.builder.Delete(k)
delete(m.std, k)
for i := range m.keys {
@@ -2111,26 +2125,41 @@ func (m *TestSortedMap) Delete(k int) {
}
}
-func (m *TestSortedMap) Validate() error {
+func (m *TSortedMap) Validate() error {
for _, k := range m.keys {
if v, ok := m.im.Get(k); !ok {
return fmt.Errorf("key not found: %d", k)
} else if v != m.std[k] {
return fmt.Errorf("key (%d) mismatch: immutable=%d, std=%d", k, v, m.std[k])
}
+ if v, ok := m.builder.Get(k); !ok {
+ return fmt.Errorf("builder key not found: %d", k)
+ } else if v != m.std[k] {
+ return fmt.Errorf("builder key (%d) mismatch: immutable=%d, std=%d", k, v, m.std[k])
+ }
+ }
+
+ if got, exp := m.builder.Len(), len(m.std); got != exp {
+ return fmt.Errorf("SortedMapBuilder.Len()=%d, expected %d", got, exp)
}
sort.Ints(m.keys)
- if err := m.validateForwardIterator(); err != nil {
- return err
- } else if err := m.validateBackwardIterator(); err != nil {
- return err
+ if err := m.validateForwardIterator(m.im); err != nil {
+ return fmt.Errorf("basic: %s", err)
+ } else if err := m.validateBackwardIterator(m.im); err != nil {
+ return fmt.Errorf("basic: %s", err)
+ }
+
+ if err := m.validateForwardIterator(m.builder.Map()); err != nil {
+ return fmt.Errorf("basic: %s", err)
+ } else if err := m.validateBackwardIterator(m.builder.Map()); err != nil {
+ return fmt.Errorf("basic: %s", err)
}
return nil
}
-func (m *TestSortedMap) validateForwardIterator() error {
- itr := m.im.Iterator()
+func (m *TSortedMap) validateForwardIterator(mm *SortedMap) error {
+ itr := mm.Iterator()
for i, k0 := range m.keys {
v0 := m.std[k0]
if k1, v1 := itr.Next(); k0 != k1 || v0 != v1 {
@@ -2148,8 +2177,8 @@ func (m *TestSortedMap) validateForwardIterator() error {
return nil
}
-func (m *TestSortedMap) validateBackwardIterator() error {
- itr := m.im.Iterator()
+func (m *TSortedMap) validateBackwardIterator(mm *SortedMap) error {
+ itr := mm.Iterator()
itr.Last()
for i := len(m.keys) - 1; i >= 0; i-- {
k0 := m.keys[i]
@@ -2222,6 +2251,29 @@ func BenchmarkSortedMap_Iterator(b *testing.B) {
})
}
+func BenchmarkSortedMapBuilder_Set(b *testing.B) {
+ b.ReportAllocs()
+ builder := NewSortedMapBuilder(NewSortedMap(nil))
+ for i := 0; i < b.N; i++ {
+ builder.Set(i, i)
+ }
+}
+
+func BenchmarkSortedMapBuilder_Delete(b *testing.B) {
+ const n = 1000000
+
+ builder := NewSortedMapBuilder(NewSortedMap(nil))
+ for i := 0; i < n; i++ {
+ builder.Set(i, i)
+ }
+ b.ReportAllocs()
+ b.ResetTimer()
+
+ for i := 0; i < b.N; i++ {
+ builder.Delete(i % n)
+ }
+}
+
func ExampleSortedMap_Set() {
m := NewSortedMap(nil)
m = m.Set("foo", "bar")
@@ -2286,6 +2338,43 @@ func ExampleSortedMap_Iterator() {
// strawberry 900
}
+func ExampleSortedMapBuilder_Set() {
+ b := NewSortedMapBuilder(NewSortedMap(nil))
+ b.Set("foo", "bar")
+ b.Set("baz", 100)
+
+ m := b.Map()
+ v, ok := m.Get("foo")
+ fmt.Println("foo", v, ok)
+
+ v, ok = m.Get("baz")
+ fmt.Println("baz", v, ok)
+
+ v, ok = m.Get("bat") // does not exist
+ fmt.Println("bat", v, ok)
+ // Output:
+ // foo bar true
+ // baz 100 true
+ // bat <nil> false
+}
+
+func ExampleSortedMapBuilder_Delete() {
+ b := NewSortedMapBuilder(NewSortedMap(nil))
+ b.Set("foo", "bar")
+ b.Set("baz", 100)
+ b.Delete("baz")
+
+ m := b.Map()
+ v, ok := m.Get("foo")
+ fmt.Println("foo", v, ok)
+
+ v, ok = m.Get("baz")
+ fmt.Println("baz", v, ok)
+ // Output:
+ // foo bar true
+ // baz <nil> false
+}
+
// RunRandom executes fn multiple times with a different rand.
func RunRandom(t *testing.T, name string, fn func(t *testing.T, rand *rand.Rand)) {
if testing.Short() {
generated by cgit v1.2.3 (git 2.49.0) at 2025-07-13 22:20:34 +0000