trie

README

trie

Trie is a Compressed Prefix Tree Implementation in Golang Generic.

> go test -benchmem -run=^$ -bench . github.com/wzshiming/trie -v
goos: linux
goarch: amd64
pkg: github.com/wzshiming/trie
cpu: Intel(R) Xeon(R) Platinum 8272CL CPU @ 2.60GHz
BenchmarkTrie_Get1
BenchmarkTrie_Get1-4    60400056                19.19 ns/op            0 B/op          0 allocs/op
BenchmarkTrie_Get2
BenchmarkTrie_Get2-4    64019403                19.07 ns/op            0 B/op          0 allocs/op
BenchmarkTrie_Put1
BenchmarkTrie_Put1-4     1234398               939.6 ns/op             0 B/op          0 allocs/op
BenchmarkTrie_Put2
BenchmarkTrie_Put2-4     1000000              1228 ns/op             339 B/op          3 allocs/op
BenchmarkTrie_Put3
BenchmarkTrie_Put3-4     3234558               398.5 ns/op            96 B/op          1 allocs/op
PASS
ok      github.com/wzshiming/trie       7.499s

License

Licensed under the MIT License. See LICENSE for the full license text.

Documentation

Index

• Variables
• type Mapping
  • func (m *Mapping[T]) Get(key []byte) (val T, current *Mapping[T], finish bool)
  • func (m *Mapping[T]) String() string
• type Trie
  • func NewTrie[T any]() *Trie[T]
  • func (t *Trie[T]) Depth() int
  • func (t *Trie[T]) Get(key []byte) (val T, current *Mapping[T], finish bool)
  • func (t *Trie[T]) Keys() [][]byte
  • func (t *Trie[T]) Mapping() (m *Mapping[T])
  • func (t *Trie[T]) MatchWithReader(r io.Reader) (handler T, prefix []byte, err error)
  • func (t *Trie[T]) Put(key []byte, val T) (finish bool)
  • func (t *Trie[T]) Size() int
  • func (t *Trie[T]) String() string
  • func (t *Trie[T]) Walk(f func(k []byte, v T))

Variables

var (
	ErrNotFound = fmt.Errorf("not found")
)

Types

type Mapping

type Mapping[T any] struct {
	// contains filtered or unexported fields
}

Mapping is a getter of the trie.

func (*Mapping[T]) Get

func (m *Mapping[T]) Get(key []byte) (val T, current *Mapping[T], finish bool)

Get returns the val in the trie for a key.

func (*Mapping[T]) String

func (m *Mapping[T]) String() string

type Trie

type Trie[T any] struct {
	// contains filtered or unexported fields
}

Trie is a trie tree implementation.

func NewTrie

func NewTrie[T any]() *Trie[T]

NewTrie returns a new Trie.

func (*Trie[T]) Depth

func (t *Trie[T]) Depth() int

Depth returns the depth of the trie.

func (*Trie[T]) Get

func (t *Trie[T]) Get(key []byte) (val T, current *Mapping[T], finish bool)

Get returns the val in the trie for a key.

func (*Trie[T]) Keys

func (t *Trie[T]) Keys() [][]byte

Keys returns all key of Trie.

func (*Trie[T]) Mapping

func (t *Trie[T]) Mapping() (m *Mapping[T])

Mapping gets the Mapping for get only.

func (*Trie[T]) MatchWithReader

func (t *Trie[T]) MatchWithReader(r io.Reader) (handler T, prefix []byte, err error)

MatchWithReader returns most matching handler and prefix bytes data to use for the given reader.

func (*Trie[T]) Put

func (t *Trie[T]) Put(key []byte, val T) (finish bool)

Put sets the val in the trie for a key.

func (*Trie[T]) Size

func (t *Trie[T]) Size() int

Size returns the size of the trie.

func (*Trie[T]) String

func (t *Trie[T]) String() string

String returns format trie in a friendly.

func (*Trie[T]) Walk

func (t *Trie[T]) Walk(f func(k []byte, v T))

Walk calls f sequentially for each key and value present in the trie.