dtrie

Documentation

Overview

Package dtrie provides an implementation of the dtrie data structure, which is a persistent hash trie that dynamically expands or shrinks to provide efficient memory allocation. This data structure is based on the papers Ideal Hash Trees by Phil Bagwell and Optimizing Hash-Array Mapped Tries for Fast and Lean Immutable JVM Collections by Michael J. Steindorfer and Jurgen J. Vinju

Index

• type Dtrie
  • func New(hasher func(v interface{}) uint32) *Dtrie
  • func (d *Dtrie) Get(key interface{}) Entry
  • func (d *Dtrie) Insert(entry Entry) *Dtrie
  • func (d *Dtrie) Iterator(stop <-chan struct{}) <-chan Entry
  • func (d *Dtrie) Remove(key interface{}) *Dtrie
  • func (d *Dtrie) Size() (size int)
• type Entry

Types

type Dtrie

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

Dtrie is a persistent hash trie that dynamically expands or shrinks to provide efficient memory allocation.

func New

func New(hasher func(v interface{}) uint32) *Dtrie

New creates an empty DTrie with the given hashing function. If nil is passed in, the default hashing function will be used.

func (*Dtrie) Get

func (d *Dtrie) Get(key interface{}) Entry

Get returns the Entry for the associated key or returns nil if the key does not exist.

func (*Dtrie) Insert

func (d *Dtrie) Insert(entry Entry) *Dtrie

Insert adds an entry to the Dtrie, replacing the existing value if the key already exists and returns the resulting Dtrie.

func (*Dtrie) Iterator

func (d *Dtrie) Iterator(stop <-chan struct{}) <-chan Entry

Iterator returns a read-only channel of Entries from the Dtrie. If a stop channel is provided, closing it will terminate and close the iterator channel. Note that if a cancel channel is not used and not every entry is read from the iterator, a goroutine will leak.

func (*Dtrie) Remove

func (d *Dtrie) Remove(key interface{}) *Dtrie

Remove deletes the value for the associated key if it exists and returns the resulting Dtrie.

func (*Dtrie) Size

func (d *Dtrie) Size() (size int)

Size returns the number of entries in the Dtrie.

type Entry

type Entry interface {
	KeyHash() uint32
	Key() interface{}
	Value() interface{}
}

Entry defines anything held within the data structure