diff options
| -rw-r--r-- | README.md | 21 | ||||
| -rw-r--r-- | immutable.go | 246 | ||||
| -rw-r--r-- | immutable_test.go | 297 |
3 files changed, 448 insertions, 116 deletions
@@ -212,6 +212,27 @@ iterate in the same order. Ordering can be insertion order dependent when two keys generate the same hash. +### Efficiently building maps + +If you are executing multiple mutations on a map, it can be much more efficient +to use the `MapBuilder`. It uses nearly the same API as `Map` except that it +updates a map in-place until you are ready to use it. + +```go +b := immutable.NewMapBuilder(immutable.NewMap(nil)) +b.Set("foo", 100) +b.Set("bar", 200) +b.Set("foo", 300) + +m := b.Map() +fmt.Println(m.Get("foo")) // "300" +fmt.Println(m.Get("bar")) // "200" +``` + +Maps are safe to use even after you continue to use the builder. You can +also build on top of existing maps too. + + ### Implementing a custom Hasher If you need to use a key type besides `int`, `string`, or `[]byte` then you'll diff --git a/immutable.go b/immutable.go index ac430ea..307b324 100644 --- a/immutable.go +++ b/immutable.go @@ -687,6 +687,12 @@ func (m *Map) Len() int { return m.size } +// clone returns a shallow copy of m. +func (m *Map) clone() *Map { + other := *m + return &other +} + // Get returns the value for a given key and a flag indicating whether the // key exists. This flag distinguishes a nil value set on a key versus a // non-existent key in the map. @@ -703,6 +709,10 @@ func (m *Map) Get(key interface{}) (value interface{}, ok bool) { // This function will return a new map even if the updated value is the same as // the existing value because Map does not track value equality. func (m *Map) Set(key, value interface{}) *Map { + return m.set(key, value, false) +} + +func (m *Map) set(key, value interface{}, mutable bool) *Map { // Set a hasher on the first value if one does not already exist. hasher := m.hasher if hasher == nil { @@ -718,23 +728,24 @@ func (m *Map) Set(key, value interface{}) *Map { } } + // Generate copy if necessary. + other := m + if !mutable { + other = m.clone() + } + other.hasher = hasher + // If the map is empty, initialize with a simple array node. if m.root == nil { - return &Map{ - size: 1, - root: &mapArrayNode{entries: []mapEntry{{key: key, value: value}}}, - hasher: hasher, - } + other.size = 1 + other.root = &mapArrayNode{entries: []mapEntry{{key: key, value: value}}} + return other } // Otherwise copy the map and delegate insertion to the root. // Resized will return true if the key does not currently exist. var resized bool - other := &Map{ - size: m.size, - root: m.root.set(key, value, 0, hasher.Hash(key), hasher, &resized), - hasher: hasher, - } + other.root = m.root.set(key, value, 0, hasher.Hash(key), hasher, mutable, &resized) if resized { other.size++ } @@ -744,23 +755,32 @@ func (m *Map) Set(key, value interface{}) *Map { // Delete returns a map with the given key removed. // Removing a non-existent key will cause this method to return the same map. func (m *Map) Delete(key interface{}) *Map { + return m.delete(key, false) +} + +func (m *Map) delete(key interface{}, mutable bool) *Map { // 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, 0, m.hasher.Hash(key), m.hasher) - if newRoot == m.root { + var resized bool + newRoot := m.root.delete(key, 0, m.hasher.Hash(key), m.hasher, mutable, &resized) + if !resized { return m } - // Return copy of map with new root and decreased size. - return &Map{ - size: m.size - 1, - root: newRoot, - hasher: m.hasher, + // Generate copy if necessary. + other := m + if !mutable { + other = m.clone() } + + // Return copy of map with new root and decreased size. + other.size = m.size - 1 + other.root = newRoot + return other } // Iterator returns a new iterator for the map. @@ -770,11 +790,56 @@ func (m *Map) Iterator() *MapIterator { return itr } +// MapBuilder represents an efficient builder for creating 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 MapBuilder struct { + m *Map // current state + mutable bool // if true, next mutation will operate in-place. +} + +// NewMapBuilder returns a new instance of MapBuilder to build on a base map. +func NewMapBuilder(m *Map) *MapBuilder { + return &MapBuilder{m: m} +} + +// Map 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 *MapBuilder) Map() *Map { + m := b.m + b.mutable = false + return m +} + +// Len returns the number of elements in the underlying map. +func (b *MapBuilder) Len() int { + return b.m.Len() +} + +// Get returns the value for the given key. +func (b *MapBuilder) Get(key interface{}) (value interface{}, ok bool) { + return b.m.Get(key) +} + +// Set sets the value of the given key. See Map.Set() for additional details. +func (b *MapBuilder) Set(key, value interface{}) { + b.m = b.m.set(key, value, b.mutable) + b.mutable = true +} + +// Delete removes the given key. See Map.Delete() for additional details. +func (b *MapBuilder) Delete(key interface{}) { + b.m = b.m.delete(key, b.mutable) + b.mutable = true +} + // mapNode represents any node in the map tree. type mapNode interface { get(key interface{}, shift uint, keyHash uint32, h Hasher) (value interface{}, ok bool) - set(key, value interface{}, shift uint, keyHash uint32, h Hasher, resized *bool) mapNode - delete(key interface{}, shift uint, keyHash uint32, h Hasher) mapNode + set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode + delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode } var _ mapNode = (*mapArrayNode)(nil) @@ -820,7 +885,7 @@ func (n *mapArrayNode) get(key interface{}, shift uint, keyHash uint32, h Hasher // set inserts or updates the value for a given key. If the key is inserted and // the new size crosses the max size threshold, a bitmap indexed node is returned. -func (n *mapArrayNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, resized *bool) mapNode { +func (n *mapArrayNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { idx := n.indexOf(key, h) // Mark as resized if the key doesn't exist. @@ -833,11 +898,21 @@ func (n *mapArrayNode) set(key, value interface{}, shift uint, keyHash uint32, h if idx == -1 && len(n.entries) >= maxArrayMapSize { var node mapNode = newMapValueNode(h.Hash(key), key, value) for _, entry := range n.entries { - node = node.set(entry.key, entry.value, 0, h.Hash(entry.key), h, resized) + node = node.set(entry.key, entry.value, 0, h.Hash(entry.key), h, false, resized) } return node } + // Update in-place if mutable. + if mutable { + if idx != -1 { + n.entries[idx] = mapEntry{key, value} + } else { + n.entries = append(n.entries, mapEntry{key, value}) + } + return n + } + // Update existing entry if a match is found. // Otherwise append to the end of the element list if it doesn't exist. var other mapArrayNode @@ -855,19 +930,28 @@ func (n *mapArrayNode) set(key, value interface{}, shift uint, keyHash uint32, h // delete removes the given key from the node. Returns the same node if key does // not exist. Returns a nil node when removing the last entry. -func (n *mapArrayNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher) mapNode { +func (n *mapArrayNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { idx := n.indexOf(key, h) // Return original node if key does not exist. if idx == -1 { return n } + *resized = true // Return nil if this node will contain no nodes. 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 + } + // Otherwise create a copy with the given entry removed. other := &mapArrayNode{entries: make([]mapEntry, len(n.entries)-1)} copy(other.entries[:idx], n.entries[:idx]) @@ -895,7 +979,7 @@ func (n *mapBitmapIndexedNode) get(key interface{}, shift uint, keyHash uint32, // set inserts or updates the value for the given key. If a new key is inserted // and the size crosses the max size threshold then a hash array node is returned. -func (n *mapBitmapIndexedNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, resized *bool) mapNode { +func (n *mapBitmapIndexedNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { // Extract the index for the bit segment of the key hash. keyHashFrag := (keyHash >> shift) & mapNodeMask @@ -915,7 +999,7 @@ func (n *mapBitmapIndexedNode) set(key, value interface{}, shift uint, keyHash u // If the node doesn't exist then create a simple value leaf node. var newNode mapNode if exists { - newNode = n.nodes[idx].set(key, value, shift+mapNodeBits, keyHash, h, resized) + newNode = n.nodes[idx].set(key, value, shift+mapNodeBits, keyHash, h, mutable, resized) } else { newNode = newMapValueNode(keyHash, key, value) } @@ -935,6 +1019,19 @@ func (n *mapBitmapIndexedNode) set(key, value interface{}, shift uint, keyHash u return &other } + // Update in-place if mutable. + if mutable { + if exists { + n.nodes[idx] = newNode + } else { + n.bitmap |= bit + n.nodes = append(n.nodes, nil) + copy(n.nodes[idx+1:], n.nodes[idx:]) + n.nodes[idx] = newNode + } + return n + } + // If node exists at given slot then overwrite it with new node. // Otherwise expand the node list and insert new node into appropriate position. other := &mapBitmapIndexedNode{bitmap: n.bitmap | bit} @@ -954,7 +1051,7 @@ func (n *mapBitmapIndexedNode) set(key, value interface{}, shift uint, keyHash u // delete removes the key from the tree. If the key does not exist then the // original node is returned. If removing the last child node then a nil is // returned. Note that shrinking the node will not convert it to an array node. -func (n *mapBitmapIndexedNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher) mapNode { +func (n *mapBitmapIndexedNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { bit := uint32(1) << ((keyHash >> shift) & mapNodeMask) // Return original node if key does not exist. @@ -967,10 +1064,10 @@ func (n *mapBitmapIndexedNode) delete(key interface{}, shift uint, keyHash uint3 // Delegate delete to child node. child := n.nodes[idx] - newChild := child.delete(key, shift+mapNodeBits, keyHash, h) + newChild := child.delete(key, shift+mapNodeBits, keyHash, h, mutable, resized) // Return original node if key doesn't exist in child. - if newChild == child { + if !*resized { return n } @@ -981,6 +1078,15 @@ func (n *mapBitmapIndexedNode) delete(key interface{}, shift uint, keyHash uint3 return nil } + // Update in-place if mutable. + if mutable { + n.bitmap ^= bit + copy(n.nodes[idx:], n.nodes[idx+1:]) + n.nodes[len(n.nodes)-1] = nil + n.nodes = n.nodes[:len(n.nodes)-1] + return n + } + // Return copy with bit removed from bitmap and node removed from node list. other := &mapBitmapIndexedNode{bitmap: n.bitmap ^ bit, nodes: make([]mapNode, len(n.nodes)-1)} copy(other.nodes[:idx], n.nodes[:idx]) @@ -988,9 +1094,14 @@ func (n *mapBitmapIndexedNode) delete(key interface{}, shift uint, keyHash uint3 return other } - // Return copy with child updated. - other := &mapBitmapIndexedNode{bitmap: n.bitmap, nodes: make([]mapNode, len(n.nodes))} - copy(other.nodes, n.nodes) + // Generate copy, if necessary. + other := n + if !mutable { + other = &mapBitmapIndexedNode{bitmap: n.bitmap, nodes: make([]mapNode, len(n.nodes))} + copy(other.nodes, n.nodes) + } + + // Update child. other.nodes[idx] = newChild return other } @@ -1002,6 +1113,12 @@ type mapHashArrayNode struct { nodes [mapNodeSize]mapNode // child node slots, may contain empties } +// clone returns a shallow copy of n. +func (n *mapHashArrayNode) clone() *mapHashArrayNode { + other := *n + return &other +} + // get returns the value for the given key. func (n *mapHashArrayNode) get(key interface{}, shift uint, keyHash uint32, h Hasher) (value interface{}, ok bool) { node := n.nodes[(keyHash>>shift)&mapNodeMask] @@ -1012,7 +1129,7 @@ func (n *mapHashArrayNode) get(key interface{}, shift uint, keyHash uint32, h Ha } // set returns a node with the value set for the given key. -func (n *mapHashArrayNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, resized *bool) mapNode { +func (n *mapHashArrayNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { idx := (keyHash >> shift) & mapNodeMask node := n.nodes[idx] @@ -1023,22 +1140,27 @@ func (n *mapHashArrayNode) set(key, value interface{}, shift uint, keyHash uint3 *resized = true newNode = newMapValueNode(keyHash, key, value) } else { - newNode = node.set(key, value, shift+mapNodeBits, keyHash, h, resized) + newNode = node.set(key, value, shift+mapNodeBits, keyHash, h, mutable, resized) } - // Return a copy of node with updated child node (and updated size, if new). - other := *n + // Generate copy, if necessary. + other := n + if !mutable { + other = n.clone() + } + + // Update child node (and update size, if new). if node == nil { other.count++ } other.nodes[idx] = newNode - return &other + return other } // delete returns a node with the given key removed. Returns the same node if // the key does not exist. If node shrinks to within bitmap-indexed size then // converts to a bitmap-indexed node. -func (n *mapHashArrayNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher) mapNode { +func (n *mapHashArrayNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { idx := (keyHash >> shift) & mapNodeMask node := n.nodes[idx] @@ -1048,8 +1170,8 @@ func (n *mapHashArrayNode) delete(key interface{}, shift uint, keyHash uint32, h } // Return original node if child is unchanged. - newNode := node.delete(key, shift+mapNodeBits, keyHash, h) - if newNode == node { + newNode := node.delete(key, shift+mapNodeBits, keyHash, h, mutable, resized) + if !*resized { return n } @@ -1065,13 +1187,18 @@ func (n *mapHashArrayNode) delete(key interface{}, shift uint, keyHash uint32, h return other } + // Generate copy, if necessary. + other := n + if !mutable { + other = n.clone() + } + // Return copy of node with child updated. - other := *n other.nodes[idx] = newNode if newNode == nil { other.count-- } - return &other + return other } // mapValueNode represents a leaf node with a single key/value pair. @@ -1109,9 +1236,15 @@ func (n *mapValueNode) get(key interface{}, shift uint, keyHash uint32, h Hasher // the node's key then a new value node is returned. If key is not equal to the // node's key but has the same hash then a hash collision node is returned. // Otherwise the nodes are merged into a branch node. -func (n *mapValueNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, resized *bool) mapNode { +func (n *mapValueNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { // If the keys match then return a new value node overwriting the value. if h.Equal(n.key, key) { + // Update in-place if mutable. + if mutable { + n.value = value + return n + } + // Otherwise return a new copy. return newMapValueNode(n.keyHash, key, value) } @@ -1130,13 +1263,14 @@ func (n *mapValueNode) set(key, value interface{}, shift uint, keyHash uint32, h } // delete returns nil if the key matches the node's key. Otherwise returns the original node. -func (n *mapValueNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher) mapNode { +func (n *mapValueNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { // Return original node if the keys do not match. if !h.Equal(n.key, key) { return n } // Otherwise remove the node if keys do match. + *resized = true return nil } @@ -1174,13 +1308,24 @@ func (n *mapHashCollisionNode) get(key interface{}, shift uint, keyHash uint32, } // set returns a copy of the node with key set to the given value. -func (n *mapHashCollisionNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, resized *bool) mapNode { +func (n *mapHashCollisionNode) set(key, value interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { // Merge node with key/value pair if this is not a hash collision. if n.keyHash != keyHash { *resized = true return mergeIntoNode(n, shift, keyHash, key, value) } + // Update in-place if mutable. + if mutable { + if idx := n.indexOf(key, h); idx == -1 { + *resized = true + n.entries = append(n.entries, mapEntry{key, value}) + } else { + n.entries[idx] = mapEntry{key, value} + } + return n + } + // Append to end of node if key doesn't exist & mark resized. // Otherwise copy nodes and overwrite at matching key index. other := &mapHashCollisionNode{keyHash: n.keyHash} @@ -1200,7 +1345,7 @@ func (n *mapHashCollisionNode) set(key, value interface{}, shift uint, keyHash u // delete returns a node with the given key deleted. Returns the same node if // the key does not exist. If removing the key would shrink the node to a single // entry then a value node is returned. -func (n *mapHashCollisionNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher) mapNode { +func (n *mapHashCollisionNode) delete(key interface{}, shift uint, keyHash uint32, h Hasher, mutable bool, resized *bool) mapNode { idx := n.indexOf(key, h) // Return original node if key is not found. @@ -1208,6 +1353,9 @@ func (n *mapHashCollisionNode) delete(key interface{}, shift uint, keyHash uint3 return n } + // Mark as resized if key exists. + *resized = true + // Convert to value node if we move to one entry. if len(n.entries) == 2 { return &mapValueNode{ @@ -1217,7 +1365,15 @@ func (n *mapHashCollisionNode) delete(key interface{}, shift uint, keyHash uint3 } } - // Otherwise return copy with entry removed. + // Remove entry 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 without entry if immutable. other := &mapHashCollisionNode{keyHash: n.keyHash, entries: make([]mapEntry, len(n.entries)-1)} copy(other.entries[:idx], n.entries[:idx]) copy(other.entries[idx:], n.entries[idx+1:]) diff --git a/immutable_test.go b/immutable_test.go index c2c91d9..1512e93 100644 --- a/immutable_test.go +++ b/immutable_test.go @@ -611,7 +611,7 @@ func TestInternal_mapNode_Overwrite(t *testing.T) { var node mapNode = &mapArrayNode{} for i := 0; i < n; i++ { var resized bool - node = node.set(i, i, 0, h.Hash(i), &h, &resized) + node = node.set(i, i, 0, h.Hash(i), &h, false, &resized) if !resized { t.Fatal("expected resize") } @@ -619,7 +619,7 @@ func TestInternal_mapNode_Overwrite(t *testing.T) { // Overwrite every node. for j := 0; j <= i; j++ { var resized bool - node = node.set(j, i*j, 0, h.Hash(j), &h, &resized) + node = node.set(j, i*j, 0, h.Hash(j), &h, false, &resized) if resized { t.Fatalf("expected no resize: i=%d, j=%d", i, j) } @@ -646,7 +646,7 @@ func TestInternal_mapArrayNode(t *testing.T) { n := &mapArrayNode{} for i := 0; i < 8; i++ { var resized bool - n = n.set(i*10, i, 0, h.Hash(i*10), &h, &resized).(*mapArrayNode) + n = n.set(i*10, i, 0, h.Hash(i*10), &h, false, &resized).(*mapArrayNode) if !resized { t.Fatal("expected resize") } @@ -665,7 +665,7 @@ func TestInternal_mapArrayNode(t *testing.T) { n := &mapArrayNode{} for i := 7; i >= 0; i-- { var resized bool - n = n.set(i*10, i, 0, h.Hash(i*10), &h, &resized).(*mapArrayNode) + n = n.set(i*10, i, 0, h.Hash(i*10), &h, false, &resized).(*mapArrayNode) if !resized { t.Fatal("expected resize") } @@ -684,7 +684,7 @@ func TestInternal_mapArrayNode(t *testing.T) { var n mapNode = &mapArrayNode{} for i := 0; i < 100; i++ { var resized bool - n = n.set(i, i, 0, h.Hash(i), &h, &resized) + n = n.set(i, i, 0, h.Hash(i), &h, false, &resized) if !resized { t.Fatal("expected resize") } @@ -703,11 +703,12 @@ func TestInternal_mapArrayNode(t *testing.T) { var n mapNode = &mapArrayNode{} for i := 0; i < 8; i++ { var resized bool - n = n.set(i*10, i, 0, h.Hash(i*10), &h, &resized) + n = n.set(i*10, i, 0, h.Hash(i*10), &h, false, &resized) } for _, i := range rand.Perm(8) { - n = n.delete(i*10, 0, h.Hash(i*10), &h) + var resized bool + n = n.delete(i*10, 0, h.Hash(i*10), &h, false, &resized) } if n != nil { t.Fatal("expected nil rand") @@ -730,7 +731,7 @@ func TestInternal_mapValueNode(t *testing.T) { var h intHasher var resized bool n := newMapValueNode(h.Hash(2), 2, 3) - other := n.set(2, 4, 0, h.Hash(2), &h, &resized).(*mapValueNode) + other := n.set(2, 4, 0, h.Hash(2), &h, false, &resized).(*mapValueNode) if other == n { t.Fatal("expected new node") } else if got, exp := other.keyHash, h.Hash(2); got != exp { @@ -751,7 +752,7 @@ func TestInternal_mapValueNode(t *testing.T) { } var resized bool n := newMapValueNode(h.Hash(2), 2, 3) - other := n.set(4, 5, 0, h.Hash(4), h, &resized).(*mapHashCollisionNode) + other := n.set(4, 5, 0, h.Hash(4), h, false, &resized).(*mapHashCollisionNode) if got, exp := other.keyHash, h.Hash(2); got != exp { t.Fatalf("keyHash=%v, expected %v", got, exp) } else if got, exp := len(other.entries), 2; got != exp { @@ -777,7 +778,7 @@ func TestInternal_mapValueNode(t *testing.T) { var h intHasher var resized bool n := newMapValueNode(h.Hash(2), 2, 3) - other := n.set(4, 5, 0, h.Hash(4), &h, &resized).(*mapBitmapIndexedNode) + other := n.set(4, 5, 0, h.Hash(4), &h, false, &resized).(*mapBitmapIndexedNode) if got, exp := other.bitmap, uint32(0x14); got != exp { t.Fatalf("bitmap=0x%02x, expected 0x%02x", got, exp) } else if got, exp := len(other.nodes), 2; got != exp { @@ -813,7 +814,7 @@ func TestInternal_mapValueNode(t *testing.T) { var h intHasher var resized bool n := newMapValueNode(h.Hash(4), 4, 5) - other := n.set(2, 3, 0, h.Hash(2), &h, &resized).(*mapBitmapIndexedNode) + other := n.set(2, 3, 0, h.Hash(2), &h, false, &resized).(*mapBitmapIndexedNode) if got, exp := other.bitmap, uint32(0x14); got != exp { t.Fatalf("bitmap=0x%02x, expected 0x%02x", got, exp) } else if got, exp := len(other.nodes), 2; got != exp { @@ -852,7 +853,7 @@ func TestInternal_mapValueNode(t *testing.T) { } var resized bool n := newMapValueNode(h.Hash(2), 2, 3) - other := n.set(4, 5, 0, h.Hash(4), h, &resized).(*mapBitmapIndexedNode) + other := n.set(4, 5, 0, h.Hash(4), h, false, &resized).(*mapBitmapIndexedNode) if got, exp := other.bitmap, uint32(0x01); got != exp { // mask is zero, expect first slot. t.Fatalf("bitmap=0x%02x, expected 0x%02x", got, exp) } else if got, exp := len(other.nodes), 1; got != exp { @@ -1139,73 +1140,131 @@ func TestMap_Delete(t *testing.T) { // Ensure map works even with hash conflicts. func TestMap_LimitedHash(t *testing.T) { - h := mockHasher{ - hash: func(value interface{}) uint32 { return hashUint64(uint64(value.(int))) % 0xFF }, - equal: func(a, b interface{}) bool { return a.(int) == b.(int) }, - } - m := NewMap(&h) + t.Run("Immutable", func(t *testing.T) { + h := mockHasher{ + hash: func(value interface{}) uint32 { return hashUint64(uint64(value.(int))) % 0xFF }, + equal: func(a, b interface{}) bool { return a.(int) == b.(int) }, + } + m := NewMap(&h) - rand := rand.New(rand.NewSource(0)) - keys := rand.Perm(100000) - for _, i := range keys { - m = m.Set(i, i) // initial set - } - for i := range keys { - m = m.Set(i, i*2) // overwrite - } - if m.Len() != len(keys) { - t.Fatalf("unexpected len: %d", m.Len()) - } + rand := rand.New(rand.NewSource(0)) + keys := rand.Perm(100000) + for _, i := range keys { + m = m.Set(i, i) // initial set + } + for i := range keys { + m = m.Set(i, i*2) // overwrite + } + if m.Len() != len(keys) { + t.Fatalf("unexpected len: %d", m.Len()) + } - // Verify all key/value pairs in map. - for i := 0; i < m.Len(); i++ { - if v, ok := m.Get(i); !ok || v != i*2 { - t.Fatalf("Get(%d)=<%v,%v>", i, v, ok) + // Verify all key/value pairs in map. + for i := 0; i < m.Len(); i++ { + if v, ok := m.Get(i); !ok || v != i*2 { + t.Fatalf("Get(%d)=<%v,%v>", i, v, ok) + } } - } - // Verify iteration. - itr := m.Iterator() - for !itr.Done() { - if k, v := itr.Next(); v != k.(int)*2 { - t.Fatalf("MapIterator.Next()=<%v,%v>, expected value %v", k, v, k.(int)*2) + // Verify iteration. + itr := m.Iterator() + for !itr.Done() { + if k, v := itr.Next(); v != k.(int)*2 { + t.Fatalf("MapIterator.Next()=<%v,%v>, expected value %v", k, v, k.(int)*2) + } } - } - // Verify not found works. - if _, ok := m.Get(10000000); ok { - t.Fatal("expected no value") - } + // Verify not found works. + if _, ok := m.Get(10000000); ok { + t.Fatal("expected no value") + } - // Verify delete non-existent key works. - if other := m.Delete(10000000 + 1); m != other { - t.Fatal("expected no change") - } + // Verify delete non-existent key works. + if other := m.Delete(10000000 + 1); m != other { + t.Fatal("expected no change") + } - // Remove all keys. - for _, key := range keys { - m = m.Delete(key) - } - if m.Len() != 0 { - t.Fatalf("unexpected size: %d", m.Len()) - } + // Remove all keys. + for _, key := range keys { + m = m.Delete(key) + } + if m.Len() != 0 { + t.Fatalf("unexpected size: %d", m.Len()) + } + }) + + t.Run("Builder", func(t *testing.T) { + h := mockHasher{ + hash: func(value interface{}) uint32 { return hashUint64(uint64(value.(int))) % 0xFF }, + equal: func(a, b interface{}) bool { return a.(int) == b.(int) }, + } + b := NewMapBuilder(NewMap(&h)) + + rand := rand.New(rand.NewSource(0)) + keys := rand.Perm(100000) + for _, i := range keys { + b.Set(i, i) // initial set + } + for i := range keys { + b.Set(i, i*2) // overwrite + } + if b.Len() != len(keys) { + t.Fatalf("unexpected len: %d", b.Len()) + } + + // Verify all key/value pairs in map. + for i := 0; i < b.Len(); i++ { + if v, ok := b.Get(i); !ok || v != i*2 { + t.Fatalf("Get(%d)=<%v,%v>", i, v, ok) + } + } + + // Verify iteration. + itr := b.Map().Iterator() + for !itr.Done() { + if k, v := itr.Next(); v != k.(int)*2 { + t.Fatalf("MapIterator.Next()=<%v,%v>, expected value %v", k, v, k.(int)*2) + } + } + + // Verify not found works. + if _, ok := b.Get(10000000); ok { + t.Fatal("expected no value") + } + + // Verify delete non-existent key works. + m := b.Map() + if b.Delete(10000000 + 1); m != b.Map() { + t.Fatal("expected no change") + } + + // Remove all keys. + for _, key := range keys { + b.Delete(key) + } + if b.Len() != 0 { + t.Fatalf("unexpected size: %d", b.Len()) + } + }) } -// TestMap represents a combined immutable and stdlib map. -type TestMap struct { +// TMap represents a combined immutable and stdlib map. +type TMap struct { im, prev *Map + builder *MapBuilder std map[int]int keys []int } -func NewTestMap() *TestMap { - return &TestMap{ - im: NewMap(nil), - std: make(map[int]int), +func NewTestMap() *TMap { + return &TMap{ + im: NewMap(nil), + builder: NewMapBuilder(NewMap(nil)), + std: make(map[int]int), } } -func (m *TestMap) NewKey(rand *rand.Rand) int { +func (m *TMap) NewKey(rand *rand.Rand) int { for { k := rand.Int() if _, ok := m.std[k]; !ok { @@ -1214,16 +1273,17 @@ func (m *TestMap) NewKey(rand *rand.Rand) int { } } -func (m *TestMap) ExistingKey(rand *rand.Rand) int { +func (m *TMap) ExistingKey(rand *rand.Rand) int { if len(m.keys) == 0 { return 0 } return m.keys[rand.Intn(len(m.keys))] } -func (m *TestMap) Set(k, v int) { +func (m *TMap) Set(k, v int) { m.prev = m.im m.im = m.im.Set(k, v) + m.builder.Set(k, v) _, exists := m.std[k] if !exists { @@ -1232,9 +1292,10 @@ func (m *TestMap) Set(k, v int) { m.std[k] = v } -func (m *TestMap) Delete(k int) { +func (m *TMap) 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 { @@ -1245,20 +1306,30 @@ func (m *TestMap) Delete(k int) { } } -func (m *TestMap) Validate() error { +func (m *TMap) 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 err := m.validateIterator(m.im); err != nil { + return fmt.Errorf("basic: %s", err) + } else if err := m.validateIterator(m.builder.Map()); err != nil { + return fmt.Errorf("builder: %s", err) } - return m.validateIterator() + return nil } -func (m *TestMap) validateIterator() error { +func (m *TMap) validateIterator(mm *Map) error { other := make(map[int]int) - itr := m.im.Iterator() + itr := mm.Iterator() for !itr.Done() { k, v := itr.Next() other[k.(int)] = v.(int) @@ -1272,6 +1343,29 @@ func (m *TestMap) validateIterator() error { return nil } +func BenchmarkBuiltinMap_Set(b *testing.B) { + b.ReportAllocs() + m := make(map[int]int) + for i := 0; i < b.N; i++ { + m[i] = i + } +} + +func BenchmarkBuiltinMap_Delete(b *testing.B) { + const n = 10000000 + + m := make(map[int]int) + for i := 0; i < n; i++ { + m[i] = i + } + b.ReportAllocs() + b.ResetTimer() + + for i := 0; i < b.N; i++ { + delete(m, i%n) + } +} + func BenchmarkMap_Set(b *testing.B) { b.ReportAllocs() m := NewMap(nil) @@ -1281,15 +1375,16 @@ func BenchmarkMap_Set(b *testing.B) { } func BenchmarkMap_Delete(b *testing.B) { - const n = 10000 + const n = 10000000 - m := NewMap(nil) + builder := NewMapBuilder(NewMap(nil)) for i := 0; i < n; i++ { - m = m.Set(i, i) + builder.Set(i, i) } b.ReportAllocs() b.ResetTimer() + m := builder.Map() for i := 0; i < b.N; i++ { m.Delete(i % n) // Do not update map, always operate on original } @@ -1315,6 +1410,29 @@ func BenchmarkMap_Iterator(b *testing.B) { }) } +func BenchmarkMapBuilder_Set(b *testing.B) { + b.ReportAllocs() + builder := NewMapBuilder(NewMap(nil)) + for i := 0; i < b.N; i++ { + builder.Set(i, i) + } +} + +func BenchmarkMapBuilder_Delete(b *testing.B) { + const n = 10000000 + + builder := NewMapBuilder(NewMap(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 ExampleMap_Set() { m := NewMap(nil) m = m.Set("foo", "bar") @@ -1379,6 +1497,43 @@ func ExampleMap_Iterator() { // apple 100 } +func ExampleMapBuilder_Set() { + b := NewMapBuilder(NewMap(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 ExampleMapBuilder_Delete() { + b := NewMapBuilder(NewMap(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 +} + func TestInternalSortedMapLeafNode(t *testing.T) { RunRandom(t, "NoSplit", func(t *testing.T, rand *rand.Rand) { var cmpr intComparer |