Documentation
¶
Overview ¶
trie implements persistent Patricia trie maps.
Each Map is effectively a map from uint64 to interface{}. Patricia tries are a form of radix tree that are particularly appropriate when many maps will be created, merged together and large amounts of sharing are expected (e.g. environment abstract domains in program analysis).
This implementation closely follows the paper:
C. Okasaki and A. Gill, “Fast mergeable integer maps,” in ACM SIGPLAN Workshop on ML, September 1998, pp. 77–86.
Each Map is immutable and can be read from concurrently. The map does not guarantee that the value pointed to by the interface{} value is not updated concurrently.
These Maps are optimized for situations where there will be many maps created at with a high degree of sharing and combining of maps together. If you do not expect, significant amount of sharing, the builtin map[T]U is much better choice!
Each Map is created by a Builder. Each Builder has a unique Scope and each node is created within this scope. Maps x and y are == if they contains the same (key,value) mappings and have equal scopes.
Internally these are big endian Patricia trie nodes, and the keys are sorted.
Index ¶
- func Elems(m Map) map[uint64]interface{}
- func TakeLhs(lhs, rhs interface{}) interface{}
- func TakeRhs(lhs, rhs interface{}) interface{}
- type Builder
- func (b *Builder) Clone(m Map) Map
- func (b *Builder) Create(m map[uint64]interface{}) Map
- func (b *Builder) Empty() Map
- func (b *Builder) Insert(m Map, k uint64, v interface{}) Map
- func (b *Builder) InsertWith(c Collision, m Map, k uint64, v interface{}) Map
- func (b *Builder) Intersect(lhs, rhs Map) Map
- func (b *Builder) IntersectWith(c Collision, lhs, rhs Map) Map
- func (b *Builder) Merge(lhs, rhs Map) Map
- func (b *Builder) MergeWith(c Collision, lhs, rhs Map) Map
- func (b *Builder) MutEmpty() MutMap
- func (b *Builder) Remove(m Map, k uint64) Map
- func (b *Builder) Rescope()
- func (b *Builder) Scope() Scope
- func (b *Builder) Update(m Map, key uint64, val interface{}) Map
- type Collision
- type Map
- type MutMap
- type Scope
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Builder ¶
type Builder struct {
// contains filtered or unexported fields
}
Builder creates new Map. Each Builder has a unique Scope.
IMPORTANT: Nodes are hash-consed internally to reduce memory consumption. To support hash-consing Builders keep an internal Map of all of the Maps that they have created. To GC any of the Maps created by the Builder, all references to the Builder must be dropped. This includes MutMaps.
func (*Builder) Clone ¶
Clone returns a Map that contains the same (key, value) elements within b.Scope(), i.e. return m if m.Scope() == b.Scope() or return a deep copy of m within b.Scope() otherwise.
func (*Builder) Insert ¶
Inserts a new association from key to value into the Map m to create a new map in the current scope.
If there was a previous value mapped by key, keep the previously mapped value. This is roughly corresponds to updating a map[uint64]interface{} by:
if _, ok := m[k]; ok { m[k] = val }
This is equivalent to b.Merge(m, b.Create({k: v})).
func (*Builder) InsertWith ¶
InsertWith inserts a new association from k to v into the Map m to create a new map in the current scope and handle collisions using the collision function c.
This is roughly corresponds to updating a map[uint64]interface{} by:
if _, ok := m[k]; ok { m[k] = c(m[k], v} else { m[k] = v}
An insertion or update happened whenever Insert(m, ...) != m .
func (*Builder) Intersect ¶
Intersect Maps lhs and rhs and returns a map with all of the keys in both lhs and rhs and the value comes from lhs, i.e.
{(k, lhs[k]) | k in lhs, k in rhs}.
func (*Builder) IntersectWith ¶
IntersectWith take lhs and rhs and returns the intersection with the value coming from the collision function, i.e.
{(k, c(lhs[k], rhs[k]) ) | k in lhs, k in rhs}.
The elements of the resulting map are always { <k, c(lhs[k], rhs[k]) > } for each key k that a key in both lhs and rhs.
func (*Builder) Merge ¶
Merge two maps lhs and rhs to create a new map in the current scope.
Whenever there is a key in both maps (a collision), the resulting value mapped by the key will be the value in lhs `b.Collision(lhs[key], rhs[key])`.
func (*Builder) MergeWith ¶
Merge two maps lhs and rhs to create a new map in the current scope.
Whenever there is a key in both maps (a collision), the resulting value mapped by the key will be `c(lhs[key], rhs[key])`.
type Collision ¶
type Collision func(lhs interface{}, rhs interface{}) interface{}
Collision functions combine a left and right hand side (lhs and rhs) values the two values are associated with the same key and produces the value that will be stored for the key.
Collision functions must be idempotent:
collision(x, x) == x for all x.
Collisions functions may be applied whenever a value is inserted or two maps are merged, or intersected.
type Map ¶
type Map struct {
// contains filtered or unexported fields
}
Map is effectively a finite mapping from uint64 keys to interface{} values. Maps are immutable and can be read from concurrently.
Notes on concurrency:
- A Map value itself is an interface and assignments to a Map value can race.
- Map does not guarantee that the value pointed to by the interface{} value is not updated concurrently.
func (Map) DeepEqual ¶
DeepEqual returns true if m and other contain the same (k, v) mappings [regardless of Scope].
Equivalently m.DeepEqual(other) <=> reflect.DeepEqual(Elems(m), Elems(other))
type MutMap ¶
MutMap is a convenient wrapper for a Map and a *Builder that will be used to create new Maps from it.
func (*MutMap) Insert ¶
Insert an element into the map using the collision function for the builder. Returns true if the element was inserted.
func (*MutMap) Intersect ¶
Intersect another map into the current one using the collision function for the builder. Returns true if the map changed.
func (*MutMap) Merge ¶
Merge another map into the current one using the collision function for the builder. Returns true if the map changed.
func (*MutMap) MergeWith ¶
Merge another map into the current one using the collision function for the builder. Returns true if the map changed.
Source Files