rstrie

Documentation

Overview

Package rstrie provides a datatype that supports building a space-efficient summary of networks and IPs.

Index

• type RSTrie
  • func NewRSTrie() *RSTrie
  • func (t *RSTrie) Contents() []bitslice.BitSlice
  • func (t *RSTrie) InsertRoute(routeBits bitslice.BitSlice)

Types

type RSTrie

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

RSTrie is a radix-like trie of radix 2 whose stored "words" are the binary representations of networks and IPs. An optimization rstrie makes over a generic radix tree is that since routes covered by other routes don't need to be stored, each node in the trie will have either 0 or 2 children; never 1.

func NewRSTrie

func NewRSTrie() *RSTrie

NewRSTrie returns an initialized RSTrie for use

func (*RSTrie) Contents

func (t *RSTrie) Contents() []bitslice.BitSlice

Contents returns the BitSlices contained in the RSTrie.

func (*RSTrie) InsertRoute

func (t *RSTrie) InsertRoute(routeBits bitslice.BitSlice)

InsertRoute inserts a new BitSlice into the trie. Each insert results in a space-optimized trie structure representing its contents. If a route being inserted is already covered by an existing route, it's simply ignored. If a route being inserted covers one or more routes already in the trie, those nodes are removed and replaced by the new route.