aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--README.md3
-rw-r--r--immutable.go193
-rw-r--r--immutable_test.go145
3 files changed, 280 insertions, 61 deletions
diff --git a/README.md b/README.md
index 653b9bb..c151641 100644
--- a/README.md
+++ b/README.md
@@ -263,7 +263,8 @@ built-in comparer implementations for `int`, `string`, and `[]byte` keys. You
may pass a `nil` comparer to `NewSortedMap()` if you are using one of these key
types.
-The API is identical to the `Map` implementation.
+The API is identical to the `Map` implementation. The sorted map also has a
+companion `SortedMapBuilder` for more efficiently building maps.
### Implementing a custom Comparer
diff --git a/immutable.go b/immutable.go
index 307b324..e8fac90 100644
--- a/immutable.go
+++ b/immutable.go
@@ -1577,6 +1577,10 @@ func (m *SortedMap) Get(key interface{}) (interface{}, bool) {
// Set returns a copy of the map with the key set to the given value.
func (m *SortedMap) Set(key, value interface{}) *SortedMap {
+ return m.set(key, value, false)
+}
+
+func (m *SortedMap) set(key, value interface{}, mutable bool) *SortedMap {
// Set a comparer on the first value if one does not already exist.
comparer := m.comparer
if comparer == nil {
@@ -1592,29 +1596,31 @@ func (m *SortedMap) Set(key, value interface{}) *SortedMap {
}
}
+ // Create copy, if necessary.
+ other := m
+ if !mutable {
+ other = m.clone()
+ }
+ other.comparer = comparer
+
// If no values are set then initialize with a leaf node.
if m.root == nil {
- return &SortedMap{
- size: 1,
- root: &sortedMapLeafNode{entries: []mapEntry{{key: key, value: value}}},
- comparer: comparer,
- }
+ other.size = 1
+ other.root = &sortedMapLeafNode{entries: []mapEntry{{key: key, value: value}}}
+ return other
}
// Otherwise delegate to root node.
// If a split occurs then grow the tree from the root.
var resized bool
- newRoot, splitNode := m.root.set(key, value, comparer, &resized)
+ newRoot, splitNode := m.root.set(key, value, comparer, mutable, &resized)
if splitNode != nil {
newRoot = newSortedMapBranchNode(newRoot, splitNode)
}
- // Return a new map with the new root.
- other := &SortedMap{
- size: m.size,
- root: newRoot,
- comparer: comparer,
- }
+ // Update root and size (if resized).
+ other.size = m.size
+ other.root = newRoot
if resized {
other.size++
}
@@ -1624,23 +1630,38 @@ func (m *SortedMap) Set(key, value interface{}) *SortedMap {
// Delete returns a copy of the map with the key removed.
// Returns the original map if key does not exist.
func (m *SortedMap) Delete(key interface{}) *SortedMap {
+ return m.delete(key, false)
+}
+
+func (m *SortedMap) delete(key interface{}, mutable bool) *SortedMap {
// Return original map if no keys exist.
if m.root == nil {
return m
}
// If the delete did not change the node then return the original map.
- newRoot := m.root.delete(key, m.comparer)
- if newRoot == m.root {
+ var resized bool
+ newRoot := m.root.delete(key, m.comparer, mutable, &resized)
+ if !resized {
return m
}
- // Return new copy with the root and size updated.
- return &SortedMap{
- size: m.size - 1,
- root: newRoot,
- comparer: m.comparer,
+ // Create copy, if necessary.
+ other := m
+ if !mutable {
+ other = m.clone()
}
+
+ // Update root and size.
+ other.size = m.size - 1
+ other.root = newRoot
+ return other
+}
+
+// clone returns a shallow copy of m.
+func (m *SortedMap) clone() *SortedMap {
+ other := *m
+ return &other
}
// Iterator returns a new iterator for this map positioned at the first key.
@@ -1650,13 +1671,58 @@ func (m *SortedMap) Iterator() *SortedMapIterator {
return itr
}
+// SortedMapBuilder represents an efficient builder for creating sorted maps.
+//
+// Maps returned from the builder are safe to use even after you continue to
+// use the builder. However, for efficiency, you should only retrieve your map
+// after you have completed building it.
+type SortedMapBuilder struct {
+ m *SortedMap // current state
+ mutable bool // if true, next mutation will operate in-place.
+}
+
+// NewSortedMapBuilder returns a new instance of SortedMapBuilder to build on a base map.
+func NewSortedMapBuilder(m *SortedMap) *SortedMapBuilder {
+ return &SortedMapBuilder{m: m}
+}
+
+// SortedMap returns the current copy of the map.
+// The returned map is safe to use even if after the builder continues to be used.
+func (b *SortedMapBuilder) Map() *SortedMap {
+ m := b.m
+ b.mutable = false
+ return m
+}
+
+// Len returns the number of elements in the underlying map.
+func (b *SortedMapBuilder) Len() int {
+ return b.m.Len()
+}
+
+// Get returns the value for the given key.
+func (b *SortedMapBuilder) Get(key interface{}) (value interface{}, ok bool) {
+ return b.m.Get(key)
+}
+
+// Set sets the value of the given key. See SortedMap.Set() for additional details.
+func (b *SortedMapBuilder) Set(key, value interface{}) {
+ b.m = b.m.set(key, value, b.mutable)
+ b.mutable = true
+}
+
+// Delete removes the given key. See SortedMap.Delete() for additional details.
+func (b *SortedMapBuilder) Delete(key interface{}) {
+ b.m = b.m.delete(key, b.mutable)
+ b.mutable = true
+}
+
// sortedMapNode represents a branch or leaf node in the sorted map.
type sortedMapNode interface {
minKey() interface{}
indexOf(key interface{}, c Comparer) int
get(key interface{}, c Comparer) (value interface{}, ok bool)
- set(key, value interface{}, c Comparer, resized *bool) (sortedMapNode, sortedMapNode)
- delete(key interface{}, c Comparer) sortedMapNode
+ set(key, value interface{}, c Comparer, mutable bool, resized *bool) (sortedMapNode, sortedMapNode)
+ delete(key interface{}, c Comparer, mutable bool, resized *bool) sortedMapNode
}
var _ sortedMapNode = (*sortedMapBranchNode)(nil)
@@ -1701,11 +1767,30 @@ func (n *sortedMapBranchNode) get(key interface{}, c Comparer) (value interface{
}
// set returns a copy of the node with the key set to the given value.
-func (n *sortedMapBranchNode) set(key, value interface{}, c Comparer, resized *bool) (sortedMapNode, sortedMapNode) {
+func (n *sortedMapBranchNode) set(key, value interface{}, c Comparer, mutable bool, resized *bool) (sortedMapNode, sortedMapNode) {
idx := n.indexOf(key, c)
// Delegate insert to child node.
- newNode, splitNode := n.elems[idx].node.set(key, value, c, resized)
+ newNode, splitNode := n.elems[idx].node.set(key, value, c, mutable, resized)
+
+ // Update in-place, if mutable.
+ if mutable {
+ n.elems[idx] = sortedMapBranchElem{key: newNode.minKey(), node: newNode}
+ if splitNode != nil {
+ n.elems = append(n.elems, sortedMapBranchElem{})
+ copy(n.elems[idx+1:], n.elems[idx:])
+ n.elems[idx+1] = sortedMapBranchElem{key: splitNode.minKey(), node: splitNode}
+ }
+
+ // If the child splits and we have no more room then we split too.
+ if len(n.elems) > sortedMapNodeSize {
+ splitIdx := len(n.elems) / 2
+ newNode := &sortedMapBranchNode{elems: n.elems[:splitIdx:splitIdx]}
+ splitNode := &sortedMapBranchNode{elems: n.elems[splitIdx:]}
+ return newNode, splitNode
+ }
+ return n, nil
+ }
// If no split occurs, copy branch and update keys.
// If the child splits, insert new key/child into copy of branch.
@@ -1734,7 +1819,7 @@ func (n *sortedMapBranchNode) set(key, value interface{}, c Comparer, resized *b
// If the child splits and we have no more room then we split too.
if len(other.elems) > sortedMapNodeSize {
splitIdx := len(other.elems) / 2
- newNode := &sortedMapBranchNode{elems: other.elems[:splitIdx]}
+ newNode := &sortedMapBranchNode{elems: other.elems[:splitIdx:splitIdx]}
splitNode := &sortedMapBranchNode{elems: other.elems[splitIdx:]}
return newNode, splitNode
}
@@ -1745,12 +1830,12 @@ func (n *sortedMapBranchNode) set(key, value interface{}, c Comparer, resized *b
// delete returns a node with the key removed. Returns the same node if the key
// does not exist. Returns nil if all child nodes are removed.
-func (n *sortedMapBranchNode) delete(key interface{}, c Comparer) sortedMapNode {
+func (n *sortedMapBranchNode) delete(key interface{}, c Comparer, mutable bool, resized *bool) sortedMapNode {
idx := n.indexOf(key, c)
// Return original node if child has not changed.
- newNode := n.elems[idx].node.delete(key, c)
- if newNode == n.elems[idx].node {
+ newNode := n.elems[idx].node.delete(key, c, mutable, resized)
+ if !*resized {
return n
}
@@ -1761,6 +1846,14 @@ func (n *sortedMapBranchNode) delete(key interface{}, c Comparer) sortedMapNode
return nil
}
+ // If mutable, update in-place.
+ if mutable {
+ copy(n.elems[idx:], n.elems[idx+1:])
+ n.elems[len(n.elems)-1] = sortedMapBranchElem{}
+ n.elems = n.elems[:len(n.elems)-1]
+ return n
+ }
+
// Return a copy without the given node.
other := &sortedMapBranchNode{elems: make([]sortedMapBranchElem, len(n.elems)-1)}
copy(other.elems[:idx], n.elems[:idx])
@@ -1768,6 +1861,12 @@ func (n *sortedMapBranchNode) delete(key interface{}, c Comparer) sortedMapNode
return other
}
+ // If mutable, update in-place.
+ if mutable {
+ n.elems[idx] = sortedMapBranchElem{key: newNode.minKey(), node: newNode}
+ return n
+ }
+
// Return a copy with the updated node.
other := &sortedMapBranchNode{elems: make([]sortedMapBranchElem, len(n.elems))}
copy(other.elems, n.elems)
@@ -1815,14 +1914,34 @@ func (n *sortedMapLeafNode) get(key interface{}, c Comparer) (value interface{},
// set returns a copy of node with the key set to the given value. If the update
// causes the node to grow beyond the maximum size then it is split in two.
-func (n *sortedMapLeafNode) set(key, value interface{}, c Comparer, resized *bool) (sortedMapNode, sortedMapNode) {
+func (n *sortedMapLeafNode) set(key, value interface{}, c Comparer, mutable bool, resized *bool) (sortedMapNode, sortedMapNode) {
// Find the insertion index for the key.
idx := n.indexOf(key, c)
+ exists := idx < len(n.entries) && c.Compare(n.entries[idx].key, key) == 0
+
+ // Update in-place, if mutable.
+ if mutable {
+ if !exists {
+ *resized = true
+ n.entries = append(n.entries, mapEntry{})
+ copy(n.entries[idx+1:], n.entries[idx:])
+ }
+ n.entries[idx] = mapEntry{key: key, value: value}
+
+ // If the key doesn't exist and we exceed our max allowed values then split.
+ if len(n.entries) > sortedMapNodeSize {
+ splitIdx := len(n.entries) / 2
+ newNode := &sortedMapLeafNode{entries: n.entries[:splitIdx:splitIdx]}
+ splitNode := &sortedMapLeafNode{entries: n.entries[splitIdx:]}
+ return newNode, splitNode
+ }
+ return n, nil
+ }
// If the key matches then simply return a copy with the entry overridden.
// If there is no match then insert new entry and mark as resized.
var newEntries []mapEntry
- if idx < len(n.entries) && c.Compare(n.entries[idx].key, key) == 0 {
+ if exists {
newEntries = make([]mapEntry, len(n.entries))
copy(newEntries, n.entries)
newEntries[idx] = mapEntry{key: key, value: value}
@@ -1836,8 +1955,9 @@ func (n *sortedMapLeafNode) set(key, value interface{}, c Comparer, resized *boo
// If the key doesn't exist and we exceed our max allowed values then split.
if len(newEntries) > sortedMapNodeSize {
- newNode := &sortedMapLeafNode{entries: newEntries[:len(newEntries)/2]}
- splitNode := &sortedMapLeafNode{entries: newEntries[len(newEntries)/2:]}
+ splitIdx := len(newEntries) / 2
+ newNode := &sortedMapLeafNode{entries: newEntries[:splitIdx:splitIdx]}
+ splitNode := &sortedMapLeafNode{entries: newEntries[splitIdx:]}
return newNode, splitNode
}
@@ -1847,19 +1967,28 @@ func (n *sortedMapLeafNode) set(key, value interface{}, c Comparer, resized *boo
// delete returns a copy of node with key removed. Returns the original node if
// the key does not exist. Returns nil if the removed key is the last remaining key.
-func (n *sortedMapLeafNode) delete(key interface{}, c Comparer) sortedMapNode {
+func (n *sortedMapLeafNode) delete(key interface{}, c Comparer, mutable bool, resized *bool) sortedMapNode {
idx := n.indexOf(key, c)
// Return original node if key is not found.
if idx >= len(n.entries) || c.Compare(n.entries[idx].key, key) != 0 {
return n
}
+ *resized = true
// If this is the last entry then return nil.
if len(n.entries) == 1 {
return nil
}
+ // Update in-place, if mutable.
+ if mutable {
+ copy(n.entries[idx:], n.entries[idx+1:])
+ n.entries[len(n.entries)-1] = mapEntry{}
+ n.entries = n.entries[:len(n.entries)-1]
+ return n
+ }
+
// Return copy of node with entry removed.
other := &sortedMapLeafNode{entries: make([]mapEntry, len(n.entries)-1)}
copy(other.entries[:idx], n.entries[:idx])
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 15:25:30 +0000