patricia

Documentation

Index

• Constants
• Variables
• type Item
• type Option
  • func MaxChildrenPerSparseNode(value int) Option
  • func MaxPrefixPerNode(value int) Option
• type Prefix
• type Trie
  • func NewTrie(options ...Option) *Trie
  • func (trie *Trie) Delete(key Prefix) (deleted bool)
  • func (trie *Trie) DeleteSubtree(prefix Prefix) (deleted bool)
  • func (trie *Trie) Get(key Prefix) (item Item)
  • func (trie *Trie) Insert(key Prefix, item Item) (inserted bool)
  • func (trie *Trie) Item() Item
  • func (trie *Trie) Match(prefix Prefix) (matchedExactly bool)
  • func (trie *Trie) MatchSubtree(key Prefix) (matched bool)
  • func (trie *Trie) Set(key Prefix, item Item)
  • func (trie *Trie) Visit(visitor VisitorFunc) error
  • func (trie *Trie) VisitPrefixes(key Prefix, visitor VisitorFunc) error
  • func (trie *Trie) VisitSubtree(prefix Prefix, visitor VisitorFunc) error
• type VisitorFunc

Constants

const (
	DefaultMaxPrefixPerNode         = 10
	DefaultMaxChildrenPerSparseNode = 8
)

Variables

var (
	SkipSubtree  = errors.New("Skip this subtree")
	ErrNilPrefix = errors.New("Nil prefix passed into a method call")
)

Types

type Item

type Item interface{}

type Option

type Option func(*Trie)

func MaxChildrenPerSparseNode

func MaxChildrenPerSparseNode(value int) Option

func MaxPrefixPerNode

func MaxPrefixPerNode(value int) Option

type Prefix

type Prefix []byte

type Trie

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

Trie is a generic patricia trie that allows fast retrieval of items by prefix. and other funky stuff.

Trie is not thread-safe.

func NewTrie

func NewTrie(options ...Option) *Trie

Trie constructor.

func (*Trie) Delete

func (trie *Trie) Delete(key Prefix) (deleted bool)

Delete deletes the item represented by the given prefix.

True is returned if the matching node was found and deleted.

func (*Trie) DeleteSubtree

func (trie *Trie) DeleteSubtree(prefix Prefix) (deleted bool)

DeleteSubtree finds the subtree exactly matching prefix and deletes it.

True is returned if the subtree was found and deleted.

func (*Trie) Get

func (trie *Trie) Get(key Prefix) (item Item)

Get returns the item located at key.

This method is a bit dangerous, because Get can as well end up in an internal node that is not really representing any user-defined value. So when nil is a valid value being used, it is not possible to tell if the value was inserted into the tree by the user or not. A possible workaround for this is not to use nil interface as a valid value, even using zero value of any type is enough to prevent this bad behaviour.

func (*Trie) Insert

func (trie *Trie) Insert(key Prefix, item Item) (inserted bool)

Insert inserts a new item into the trie using the given prefix. Insert does not replace existing items. It returns false if an item was already in place.

func (*Trie) Item

func (trie *Trie) Item() Item

Item returns the item stored in the root of this trie.

func (*Trie) Match

func (trie *Trie) Match(prefix Prefix) (matchedExactly bool)

Match returns what Get(prefix) != nil would return. The same warning as for Get applies here as well.

func (*Trie) MatchSubtree

func (trie *Trie) MatchSubtree(key Prefix) (matched bool)

MatchSubtree returns true when there is a subtree representing extensions to key, that is if there are any keys in the tree which have key as prefix.

func (*Trie) Set

func (trie *Trie) Set(key Prefix, item Item)

Set works much like Insert, but it always sets the item, possibly replacing the item previously inserted.

func (*Trie) Visit

func (trie *Trie) Visit(visitor VisitorFunc) error

Visit calls visitor on every node containing a non-nil item in alphabetical order.

If an error is returned from visitor, the function stops visiting the tree and returns that error, unless it is a special error - SkipSubtree. In that case Visit skips the subtree represented by the current node and continues elsewhere.

func (*Trie) VisitPrefixes

func (trie *Trie) VisitPrefixes(key Prefix, visitor VisitorFunc) error

VisitPrefixes visits only nodes that represent prefixes of key. To say the obvious, returning SkipSubtree from visitor makes no sense here.

func (*Trie) VisitSubtree

func (trie *Trie) VisitSubtree(prefix Prefix, visitor VisitorFunc) error

VisitSubtree works much like Visit, but it only visits nodes matching prefix.

type VisitorFunc

type VisitorFunc func(prefix Prefix, item Item) error