iptree

Documentation

Overview

Package iptree implements radix tree data structure for IPv4 and IPv6 networks. https://github.com/infobloxopen/go-trees/tree/master/iptree

Package numtree implements radix tree data structure for 32 and 64-bit unsigned integets. Copy-on-write is used for any tree modification so old root doesn't see any change happens with tree. https://github.com/infobloxopen/go-trees/tree/master/numtree

Package numtree implements radix tree data structure for 32 and 64-bit unsigned integets. Copy-on-write is used for any tree modification so old root doesn't see any change happens with tree. https://github.com/infobloxopen/go-trees/tree/master/numtree

Index

• Constants
• type Node32
  • func (n *Node32) Delete(key uint32, bits int) (*Node32, bool)
  • func (n *Node32) Dot() string
  • func (n *Node32) Enumerate() chan *Node32
  • func (n *Node32) ExactMatch(key uint32, bits int) (interface{}, bool)
  • func (n *Node32) InplaceInsert(key uint32, bits int, value interface{}) *Node32
  • func (n *Node32) Insert(key uint32, bits int, value interface{}) *Node32
  • func (n *Node32) Match(key uint32, bits int) (interface{}, bool)
• type Node64
  • func (n *Node64) Delete(key uint64, bits int) (*Node64, bool)
  • func (n *Node64) Dot() string
  • func (n *Node64) Enumerate() chan *Node64
  • func (n *Node64) ExactMatch(key uint64, bits int) (interface{}, bool)
  • func (n *Node64) InplaceInsert(key uint64, bits int, value interface{}) *Node64
  • func (n *Node64) Insert(key uint64, bits int, value interface{}) *Node64
  • func (n *Node64) Match(key uint64, bits int) (interface{}, bool)
• type Pair
• type Tree
  • func NewTree() *Tree
  • func (t *Tree) DeleteByIP(ip net.IP) (*Tree, bool)
  • func (t *Tree) DeleteByNet(n *net.IPNet) (*Tree, bool)
  • func (t *Tree) Enumerate() chan Pair
  • func (t *Tree) GetByIP(ip net.IP) (interface{}, bool)
  • func (t *Tree) GetByNet(n *net.IPNet) (interface{}, bool)
  • func (t *Tree) InplaceInsertIP(ip net.IP, value interface{})
  • func (t *Tree) InplaceInsertNet(n *net.IPNet, value interface{})
  • func (t *Tree) InsertIP(ip net.IP, value interface{}) *Tree
  • func (t *Tree) InsertNet(n *net.IPNet, value interface{}) *Tree

Constants

const Key32BitSize = 32

Key32BitSize is an alias for bitsize of 32-bit radix tree's key.

const Key64BitSize = 64

Key64BitSize is an alias for bitsize of 64-bit radix tree's key.

Types

type Node32

type Node32 struct {
	// Key stores key for current node.
	Key uint32
	// Bits is a number of significant bits in Key.
	Bits uint8
	// Leaf indicates if the node is leaf node and contains any data in Value.
	Leaf bool
	// Value contains data associated with key.
	Value interface{}
	// contains filtered or unexported fields
}

Node32 is an element of radix tree with 32-bit unsigned integer as a key.

func (*Node32) Delete

func (n *Node32) Delete(key uint32, bits int) (*Node32, bool)

Delete removes subtree which is contained by given key. The method uses copy on write strategy.

func (*Node32) Dot

func (n *Node32) Dot() string

Dot dumps tree to Graphviz .dot format

func (*Node32) Enumerate

func (n *Node32) Enumerate() chan *Node32

Enumerate returns channel which is populated by nodes with data in order of their keys.

func (*Node32) ExactMatch

func (n *Node32) ExactMatch(key uint32, bits int) (interface{}, bool)

ExactMatch locates node which exactly matches given key.

func (*Node32) InplaceInsert

func (n *Node32) InplaceInsert(key uint32, bits int, value interface{}) *Node32

InplaceInsert puts new leaf to radix tree (or replaces value in existing one). The method inserts data directly to current tree so make sure you have exclusive access to it.

func (*Node32) Insert

func (n *Node32) Insert(key uint32, bits int, value interface{}) *Node32

Insert puts new leaf to radix tree and returns pointer to new root. The method uses copy on write strategy so old root doesn't see the change.

func (*Node32) Match

func (n *Node32) Match(key uint32, bits int) (interface{}, bool)

Match locates node which key is equal to or "contains" the key passed as argument.

type Node64

type Node64 struct {
	// Key stores key for current node.
	Key uint64
	// Bits is a number of significant bits in Key.
	Bits uint8
	// Leaf indicates if the node is leaf node and contains any data in Value.
	Leaf bool
	// Value contains data associated with key.
	Value interface{}
	// contains filtered or unexported fields
}

Node64 is an element of radix tree with 64-bit unsigned integer as a key.

func (*Node64) Delete

func (n *Node64) Delete(key uint64, bits int) (*Node64, bool)

Delete removes subtree which is contained by given key. The method uses copy on write strategy.

func (*Node64) Dot

func (n *Node64) Dot() string

Dot dumps tree to Graphviz .dot format

func (*Node64) Enumerate

func (n *Node64) Enumerate() chan *Node64

Enumerate returns channel which is populated by nodes in order of their keys.

func (*Node64) ExactMatch

func (n *Node64) ExactMatch(key uint64, bits int) (interface{}, bool)

ExactMatch locates node which exactly matches given key.

func (*Node64) InplaceInsert

func (n *Node64) InplaceInsert(key uint64, bits int, value interface{}) *Node64

InplaceInsert puts new leaf to radix tree (or replaces value in existing one). The method inserts data directly to current tree so make sure you have exclusive access to it.

func (*Node64) Insert

func (n *Node64) Insert(key uint64, bits int, value interface{}) *Node64

Insert puts new leaf to radix tree and returns pointer to new root. The method uses copy on write strategy so old root doesn't see the change.

func (*Node64) Match

func (n *Node64) Match(key uint64, bits int) (interface{}, bool)

Match locates node which key is equal to or "contains" the key passed as argument.

type Pair

type Pair struct {
	Key   *net.IPNet
	Value interface{}
}

Pair represents a key-value pair returned by Enumerate method.

type Tree

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

Tree is a radix tree for IPv4 and IPv6 networks.

func NewTree

func NewTree() *Tree

NewTree creates empty tree.

func (*Tree) DeleteByIP

func (t *Tree) DeleteByIP(ip net.IP) (*Tree, bool)

DeleteByIP removes node by given IP address. The method returns new tree (old one remains unaffected) and flag indicating if deletion happens indeed.

func (*Tree) DeleteByNet

func (t *Tree) DeleteByNet(n *net.IPNet) (*Tree, bool)

DeleteByNet removes subtree which is contained by given network. The method returns new tree (old one remains unaffected) and flag indicating if deletion happens indeed.

func (*Tree) Enumerate

func (t *Tree) Enumerate() chan Pair

Enumerate returns channel which is populated by key-value pairs of tree content.

func (*Tree) GetByIP

func (t *Tree) GetByIP(ip net.IP) (interface{}, bool)

GetByIP gets value for network which is equal to or contains given IP address.

func (*Tree) GetByNet

func (t *Tree) GetByNet(n *net.IPNet) (interface{}, bool)

GetByNet gets value for network which is equal to or contains given network.

func (*Tree) InplaceInsertIP

func (t *Tree) InplaceInsertIP(ip net.IP, value interface{})

InplaceInsertIP inserts (or replaces) value using given IP address as a key in current tree.

func (*Tree) InplaceInsertNet

func (t *Tree) InplaceInsertNet(n *net.IPNet, value interface{})

InplaceInsertNet inserts (or replaces) value using given network as a key in current tree.

func (*Tree) InsertIP

func (t *Tree) InsertIP(ip net.IP, value interface{}) *Tree

InsertIP inserts value using given IP address as a key. The method returns new tree (old one remains unaffected).

func (*Tree) InsertNet

func (t *Tree) InsertNet(n *net.IPNet, value interface{}) *Tree

InsertNet inserts value using given network as a key. The method returns new tree (old one remains unaffected).