trie

Documentation

Index

• type Node
• type Trie
  • func New() *Trie
  • func NewFromArray(_ []Node) *Trie
  • func (t *Trie) Add(route string, nexthop string)
  • func (t *Trie) Divide(stride uint) [][]*Trie
  • func (t *Trie) Lookup(route string) string
  • func (t *Trie) ToArray() []Node

Types

type Node

type Node struct {
	NextHop string
	Right   *Node
	Left    *Node
	// contains filtered or unexported fields
}

Node represents trie node which may contains a prefix if node has prefix it will have non-nil prefix value and otherwise it will have nil prefix value.

type Trie

type Trie struct {
	Root   *Node
	Height uint
	Prefix string // when trie is subtrie this field represents old prefix of root
}

Trie represents binary trie for IP route lookup.

func New

func New() *Trie

New creates new trie.

func NewFromArray

func NewFromArray(_ []Node) *Trie

NewFromArray creates new trie based on given node array with following structure.

   i
  / \
2i  2i+1

func (*Trie) Add

func (t *Trie) Add(route string, nexthop string)

Add adds new route into trie given route must be in binary regex format e.g. *, 11*.

func (*Trie) Divide

func (t *Trie) Divide(stride uint) [][]*Trie

Divide divides the binary trie into different levels based on these k-bit subtries. If k = 4 thus, level 0 contains from prefix length 0 to prefix length 7, and so on. Each level contains one or more subtries. nolint: funlen, gocognit, cyclop

func (*Trie) Lookup

func (t *Trie) Lookup(route string) string

Lookup lookups given route in tire and returns finded nexhop or - given route must be in binary representation e.g. 111111..

func (*Trie) ToArray

func (t *Trie) ToArray() []Node

ToArray returns node array of trie with following structure:

   i
  / \
2i  2i+1

e.g.

      1
    /  \
   2    3
 /  \  / \
4   5 6   7