tlpm

README

Go lpm trie package

Tree-bitmap longest prefix match (LPM) implementation in GoLang. The information about this algorithm can be found here It supports both Ipv4/Ipv6 lookups and user-defined data types to be associated with prefixes

How to use in your project

Kindly check tlpm_test.go in this repository which has all the necessary examples

To add a route -

route = "10.10.10.10/32"
// Data can be any user-defined type 
data = 12
res = trieR.AddTrie(route, data)
if res != 0 {
  fmt.Printf("Trie add failed\n")
}

To delete a route -

route = "10.10.10.10/32"
res = trieR.DelTrie(route)
if res != 0 {
  fmt.Printf("Trie delete failed\n")
}

To find a route -

ret, ipn, rdata := trieR.FindTrie("192.41.3.1")
if ret != 0 {
  fmt.Printf("Matched prefix %s\n", (*ipn).String())
}

Performance

Go benchmark currently gives this implementation the following score :

llb@nd2:~/lpm$ go test -bench=.
goos: linux
goarch: amd64
pkg: lpm
cpu: Intel(R) Xeon(R) Silver 4210R CPU @ 2.40GHz
BenchmarkTrie-40    	  845660	      1345 ns/op
PASS
ok  	lpm	2.156s

Documentation

Overview

SPDX-License-Identifier: Apache 2.0 Copyright Copyright (c) 2022 NetLOX Inc <dipj@netlox.io>

Index

• Constants
• type TrieData
• type TrieIterIntf
• type TrieRoot
  • func TrieInit(v6 bool) *TrieRoot
  • func (t *TrieRoot) AddTrie(cidr string, data TrieData) int
  • func (t *TrieRoot) DelTrie(cidr string) int
  • func (t *TrieRoot) FindTrie(IP string) (int, *net.IPNet, TrieData)
  • func (t *TrieRoot) Trie2String(tf TrieIterIntf)

Constants

const (
	TRIE_SUCCESS    = 0
	TRIE_ERR_GEN    = -1
	TRIE_ERR_EXISTS = -2
	TRIE_ERR_NOENT  = -3
	TRIE_ERR_NOMEM  = -4
	TRIE_ERR_UNK    = -5
	TRIE_ERR_PREFIX = -6
)

const (
	TRIE_JMP_LENGTH  = 8
	PREFIX_ARR_LEN   = (1 << (TRIE_JMP_LENGTH + 1)) - 1
	PREFIX_ARR_NBITS = ((PREFIX_ARR_LEN + TRIE_JMP_LENGTH) & ^TRIE_JMP_LENGTH) / TRIE_JMP_LENGTH
	PTR_ARR_LEN      = (1 << TRIE_JMP_LENGTH)
	PTR_ARR_NBITS    = ((PTR_ARR_LEN + TRIE_JMP_LENGTH) & ^TRIE_JMP_LENGTH) / TRIE_JMP_LENGTH
)

Types

type TrieData

type TrieData interface {
}

type TrieIterIntf

type TrieIterIntf interface {
	TrieNodeWalker(b string)
	TrieData2String(d TrieData) string
}

type TrieRoot

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

func TrieInit

func TrieInit(v6 bool) *TrieRoot

func (*TrieRoot) AddTrie

func (t *TrieRoot) AddTrie(cidr string, data TrieData) int

func (*TrieRoot) DelTrie

func (t *TrieRoot) DelTrie(cidr string) int

func (*TrieRoot) FindTrie

func (t *TrieRoot) FindTrie(IP string) (int, *net.IPNet, TrieData)

func (*TrieRoot) Trie2String

func (t *TrieRoot) Trie2String(tf TrieIterIntf)