persistent

Documentation

Overview

The persistent package defines various persistent data structures; that is, data structures that can be efficiently copied and modified in sublinear time.

Index

• type Map
  • func NewMap(less func(a, b interface{}) bool) *Map
  • func (pm *Map) Clear()
  • func (pm *Map) Clone() *Map
  • func (pm *Map) Delete(key interface{})
  • func (pm *Map) Destroy()
  • func (pm *Map) Get(key interface{}) (interface{}, bool)
  • func (pm *Map) Range(f func(key, value interface{}))
  • func (pm *Map) Set(key, value interface{}, release func(key, value interface{}))
  • func (pm *Map) SetAll(other *Map)
  • func (m *Map) String() string

Types

type Map

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

Map is an associative mapping from keys to values, both represented as interface{}. Key comparison and iteration order is defined by a client-provided function that implements a strict weak order.

Maps can be Cloned in constant time. Get, Store, and Delete operations are done on average in logarithmic time. Maps can be Updated in O(m log(n/m)) time for maps of size n and m, where m < n.

Values are reference counted, and a client-supplied release function is called when a value is no longer referenced by a map or any clone.

Internally the implementation is based on a randomized persistent treap: https://en.wikipedia.org/wiki/Treap.

func NewMap

func NewMap(less func(a, b interface{}) bool) *Map

NewMap returns a new map whose keys are ordered by the given comparison function (a strict weak order). It is the responsibility of the caller to Destroy it at later time.

func (*Map) Clear

func (pm *Map) Clear()

Clear removes all entries from the map.

func (*Map) Clone

func (pm *Map) Clone() *Map

Clone returns a copy of the given map. It is a responsibility of the caller to Destroy it at later time.

func (*Map) Delete

func (pm *Map) Delete(key interface{})

Delete deletes the value for a key.

func (*Map) Destroy

func (pm *Map) Destroy()

Destroy destroys the map.

After Destroy, the Map should not be used again.

func (*Map) Get

func (pm *Map) Get(key interface{}) (interface{}, bool)

Get returns the map value associated with the specified key, or nil if no entry is present. The ok result indicates whether an entry was found in the map.

func (*Map) Range

func (pm *Map) Range(f func(key, value interface{}))

Range calls f sequentially in ascending key order for all entries in the map.

func (*Map) Set

func (pm *Map) Set(key, value interface{}, release func(key, value interface{}))

Set updates the value associated with the specified key. If release is non-nil, it will be called with entry's key and value once the key is no longer contained in the map or any clone.

func (*Map) SetAll

func (pm *Map) SetAll(other *Map)

SetAll updates the map with key/value pairs from the other map, overwriting existing keys. It is equivalent to calling Set for each entry in the other map but is more efficient. Both maps must have the same comparison function, otherwise behavior is undefined.

func (*Map) String

func (m *Map) String() string