trie

package
v0.0.0-...-f39ad0c Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jun 23, 2023 License: GPL-2.0 Imports: 5 Imported by: 0

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

Constants

This section is empty.

Variables

This section is empty.

Functions

func Elems

func Elems(m Map) map[uint64]interface{}

Elems are the (k,v) elements in the Map as a map[uint64]interface{}

func TakeLhs

func TakeLhs(lhs, rhs interface{}) interface{}

TakeLhs always returns the left value in a collision.

func TakeRhs

func TakeRhs(lhs, rhs interface{}) interface{}

TakeRhs always returns the right hand side in a collision.

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 NewBuilder

func NewBuilder() *Builder

NewBuilder creates a new Builder with a unique Scope.

func (*Builder) Clone

func (b *Builder) Clone(m Map) Map

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) Create

func (b *Builder) Create(m map[uint64]interface{}) Map

func (*Builder) Empty

func (b *Builder) Empty() Map

Empty is the empty map.

func (*Builder) Insert

func (b *Builder) Insert(m Map, k uint64, v interface{}) Map

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

func (b *Builder) InsertWith(c Collision, m Map, k uint64, v interface{}) Map

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

func (b *Builder) Intersect(lhs, rhs Map) Map

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

func (b *Builder) IntersectWith(c Collision, lhs, rhs Map) Map

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

func (b *Builder) Merge(lhs, rhs Map) Map

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

func (b *Builder) MergeWith(c Collision, lhs, rhs Map) Map

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])`.

func (*Builder) MutEmpty

func (b *Builder) MutEmpty() MutMap

MutEmpty is an empty MutMap for a builder.

func (*Builder) Remove

func (b *Builder) Remove(m Map, k uint64) Map

Remove a key from a Map m and return the resulting Map.

func (*Builder) Rescope

func (b *Builder) Rescope()

Rescope changes the builder's scope to a new unique Scope.

Any Maps created using the previous scope need to be Cloned before any operation.

This makes the old internals of the Builder eligible to be GC'ed.

func (*Builder) Scope

func (b *Builder) Scope() Scope

func (*Builder) Update

func (b *Builder) Update(m Map, key uint64, val interface{}) Map

Updates a (key, value) in the map. This is roughly corresponds to updating a map[uint64]interface{} by:

m[key] = val

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

func (m Map) DeepEqual(other Map) bool

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))

func (Map) Lookup

func (m Map) Lookup(k uint64) (interface{}, bool)

func (Map) Range

func (m Map) Range(cb func(uint64, interface{}) bool) bool

Range over the leaf (key, value) pairs in the map in order and applies cb(key, value) to each. Stops early if cb returns false. Returns true if all elements were visited without stopping early.

func (Map) Scope

func (m Map) Scope() Scope

func (Map) Size

func (m Map) Size() int

func (Map) String

func (m Map) String() string

Converts the map into a {<key>: <value>[, ...]} string. This uses the default %s string conversion for <value>.

type MutMap

type MutMap struct {
	B *Builder
	M Map
}

MutMap is a convenient wrapper for a Map and a *Builder that will be used to create new Maps from it.

func (*MutMap) Insert

func (mm *MutMap) Insert(k uint64, v interface{}) bool

Insert an element into the map using the collision function for the builder. Returns true if the element was inserted.

func (*MutMap) Intersect

func (mm *MutMap) Intersect(other Map) bool

Intersect another map into the current one using the collision function for the builder. Returns true if the map changed.

func (*MutMap) Merge

func (mm *MutMap) Merge(other Map) bool

Merge another map into the current one using the collision function for the builder. Returns true if the map changed.

func (*MutMap) MergeWith

func (mm *MutMap) MergeWith(c Collision, other Map) bool

Merge another map into the current one using the collision function for the builder. Returns true if the map changed.

func (*MutMap) Remove

func (mm *MutMap) Remove(k uint64) bool

Removes a key from the map. Returns true if the element was removed.

func (*MutMap) Update

func (mm *MutMap) Update(k uint64, v interface{}) bool

Updates an element in the map. Returns true if the map was updated.

type Scope

type Scope struct {
	// contains filtered or unexported fields
}

Scope represents a distinct collection of maps. Maps with the same Scope can be equal. Maps in different scopes are distinct. Each Builder creates maps within a unique Scope.

func (Scope) String

func (s Scope) String() string

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL