package trie

import "gvisor.dev/gvisor/pkg/trie"

Package trie provides a character-based prefix trie data structure for storing arbitrary payloads in an efficiently retrievable manner.

Index ¶

• type Trie
• func New() *Trie
• func (t *Trie) FindPrefixes(key string, f Visitor)
• func (t *Trie) FindSuffixes(key string, f Visitor)
• func (t *Trie) SetValue(key string, value any)
• func (t *Trie) Size() int
• type Visitor

Types ¶

type Trie ¶

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

Trie stores data at given strings in tree structure, for linear-time retrieval. Call New() to obtain a valid Trie.

func New ¶

func New() *Trie

New creates a new instance of the Trie interface.

func (*Trie) FindPrefixes ¶

func (t *Trie) FindPrefixes(key string, f Visitor)

FindPrefixes invokes the Visitor with all key-value pairs where the key is a prefix of `key`, including exact matches. It does this in increasing order of key length, and terminates early if Visitor returns false.

func (*Trie) FindSuffixes ¶

func (t *Trie) FindSuffixes(key string, f Visitor)

FindSuffixes invokes the Visitor with all key-value pairs where the key is prefixed by `key`, including exact matches. It does this in an unspecified order, and terminates early if the Visitor returns false.

Invoking FindSuffixes with the empty string as a key will iterate over all values.

func (*Trie) SetValue ¶

func (t *Trie) SetValue(key string, value any)

SetValue associates the specified key with the given value, replacing any existing value.

func (*Trie) Size ¶

func (t *Trie) Size() int

Size returns the total number of values in the Trie.

type Visitor ¶

type Visitor func(prefix string, value any) bool

Visitor accepts a prefix string and an associated value, and returns true iff searching should continue deeper into the Trie. It is used by FindMatching().

Source Files ¶

trie.go