lpm

README

Go LPM Trie and Go LPM Hash Map Library

This is a standalone library that implements the longest prefix match algorithm for use with Subnets, CIDRs and IPs. It supports both IPv4 and IPv6 prefix notations.

Usage

The examples folder contains usage examples.

As pointed out in my Web Log article about LPM Tries it is heavily recommended to use the HashMap wherever possible, as it's the most efficient way to represent a longest prefix match respecting data structure.

import "github.com/cookiengineer/lpm"
import "fmt"

hashmap := lpm.NewHashMap()

hashmap.Insert("192.168.0.0/24")
hashmap.Insert("192.169.128.0/17")
hashmap.Insert("192.169.0.0/16")
hashmap.Insert("192.169.0.0/24")

fmt.Println("parent of 192.168.0.123 is:", hashmap.Search("192.168.0.123/32"))
fmt.Println("parent of 192.169.0.123 is:", hashmap.Search("192.169.0.123/32"))

fmt.Println("")
fmt.Println("hashmap:")
hashmap.Print()

License

AGPL3

Documentation

Index

• type HashMap
  • func NewHashMap() HashMap
  • func (hashmap *HashMap) Insert(value string) bool
  • func (hashmap *HashMap) InsertNode(value Node) bool
  • func (hashmap *HashMap) Print()
  • func (hashmap *HashMap) Search(value string) *Node
  • func (hashmap *HashMap) SearchNode(value Node) *Node
  • func (hashmap *HashMap) SetNodes(values []Node) bool
• type Node
  • func NewNode(address string, prefix uint8) Node
  • func ToNode(value string) Node
  • func (node *Node) Addresses() uint
  • func (node *Node) Contains(value string) bool
  • func (node *Node) ContainsNode(value Node) bool
  • func (node *Node) Hash() string
  • func (node *Node) IsValid() bool
  • func (node *Node) SetAddress(value string)
  • func (node *Node) SetName(value string)
  • func (node *Node) SetPrefix(value uint8)
  • func (node *Node) SetScope(value string)
  • func (node *Node) String() string
• type Trie
  • func NewTrie() Trie
  • func (trie *Trie) Insert(value string) bool
  • func (trie *Trie) InsertNode(value Node) bool
  • func (trie *Trie) Print()
  • func (trie *Trie) Search(value string) *Node
  • func (trie *Trie) SearchNode(value Node) *Node
  • func (trie *Trie) SetNodes(values []Node) bool

Types

type HashMap

type HashMap struct {
	Mapv4 map[uint8]map[string]*Node `json:"mapv4"`
	Mapv6 map[uint8]map[string]*Node `json:"mapv6"`
}

func NewHashMap

func NewHashMap() HashMap

func (*HashMap) Insert

func (hashmap *HashMap) Insert(value string) bool

func (*HashMap) InsertNode

func (hashmap *HashMap) InsertNode(value Node) bool

func (*HashMap) Print

func (hashmap *HashMap) Print()

func (*HashMap) Search

func (hashmap *HashMap) Search(value string) *Node

func (*HashMap) SearchNode

func (hashmap *HashMap) SearchNode(value Node) *Node

func (*HashMap) SetNodes

func (hashmap *HashMap) SetNodes(values []Node) bool

type Node

type Node struct {
	Name     string  `json:"name"`
	Address  string  `json:"address"`
	Scope    string  `json:"scope"`
	Type     string  `json:"type"`
	Prefix   uint8   `json:"prefix"`
	Children []*Node `json:"children"`
}

func NewNode

func NewNode(address string, prefix uint8) Node

func ToNode

func ToNode(value string) Node

func (*Node) Addresses

func (node *Node) Addresses() uint

func (*Node) Contains

func (node *Node) Contains(value string) bool

func (*Node) ContainsNode

func (node *Node) ContainsNode(value Node) bool

func (*Node) Hash

func (node *Node) Hash() string

func (*Node) IsValid

func (node *Node) IsValid() bool

func (*Node) SetAddress

func (node *Node) SetAddress(value string)

func (*Node) SetName

func (node *Node) SetName(value string)

func (*Node) SetPrefix

func (node *Node) SetPrefix(value uint8)

func (*Node) SetScope

func (node *Node) SetScope(value string)

func (*Node) String

func (node *Node) String() string

type Trie

type Trie struct {
	Rootv4 *Node `json:"rootv4"`
	Rootv6 *Node `json:"rootv6"`
}

func NewTrie

func NewTrie() Trie

func (*Trie) Insert

func (trie *Trie) Insert(value string) bool

func (*Trie) InsertNode

func (trie *Trie) InsertNode(value Node) bool

func (*Trie) Print

func (trie *Trie) Print()

func (*Trie) Search

func (trie *Trie) Search(value string) *Node

func (*Trie) SearchNode

func (trie *Trie) SearchNode(value Node) *Node

func (*Trie) SetNodes

func (trie *Trie) SetNodes(values []Node) bool