cidrtree

package module
v0.5.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 10, 2024 License: MIT Imports: 8 Imported by: 5

README

package cidrtree

Go Reference GitHub release (latest SemVer) CI Coverage Status Stand With Ukraine

!!! ATTENTION

API is currently not stable!

Overview

package cidrtree is a datastructure for IP routing tables (IPv4/IPv6) with fast lookup (longest prefix match).

The implementation is based on treaps, which have been augmented here for CIDRs. Treaps are randomized, self-balancing binary search trees. Due to the nature of treaps the lookups (readers) and the update (writer) can be easily decoupled. This is the perfect fit for a software router or firewall.

This package is a specialization of the more generic interval package of the same author, but explicit for CIDRs. It has a narrow focus with a specialized API for IP routing tables.

API

  import "github.com/gaissmai/cidrtree"

  type Table[V any] struct { // Has unexported fields.  }
    Table is an IPv4 and IPv6 routing table. The zero value is ready to use.

  func (t Table[V]) Lookup(ip netip.Addr) (lpm netip.Prefix, value V, ok bool)
  func (t Table[V]) LookupPrefix(pfx netip.Prefix) (lpm netip.Prefix, value V, ok bool)

  func (t *Table[V]) Insert(pfx netip.Prefix, value V)
  func (t *Table[V]) Delete(pfx netip.Prefix) bool
  func (t *Table[V]) Union(other Table[V])

  func (t Table[V]) InsertImmutable(pfx netip.Prefix, value V) *Table[V]
  func (t Table[V]) DeleteImmutable(pfx netip.Prefix) (*Table[V], bool)
  func (t Table[V]) UnionImmutable(other Table[V]) *Table[V]
  func (t Table[V]) Clone() *Table[V]

  func (t Table[V]) String() string
  func (t Table[V]) Fprint(w io.Writer) error

  func (t Table[V]) Walk(cb func(pfx netip.Prefix, value V) bool)

Documentation

Overview

Package cidrtree implements fast lookup (longest-prefix-match) for IP routing tables (IPv4/IPv6).

The implementation is based on treaps, which have been augmented here for CIDRs.

Treaps are randomized, self-balancing binary search trees. Due to the nature of treaps the lookups (readers) and the update (writer) can be easily decoupled. This is the perfect fit for a software router or firewall.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Table added in v0.2.0 

type Table[V any] struct {
	// contains filtered or unexported fields
}

Table is an IPv4 and IPv6 routing table. The zero value is ready to use.

func (Table[V]) Clone added in v0.2.0 

func (t Table[V]) Clone() *Table[V]

Clone, deep cloning of the routing table.

func (*Table[V]) Delete added in v0.2.0 

func (t *Table[V]) Delete(pfx netip.Prefix) bool

Delete removes the prefix from table, returns true if it exists, false otherwise.

func (Table[V]) DeleteImmutable added in v0.3.0 

func (t Table[V]) DeleteImmutable(pfx netip.Prefix) (*Table[V], bool)

DeleteImmutable removes the prefix if it exists, returns the new table and true, false if not found.

func (Table[V]) Fprint added in v0.2.0 

func (t Table[V]) Fprint(w io.Writer) error

Fprint writes an ordered CIDR tree diagram to w. If w is nil, Fprint panics.

The order from top to bottom is in ascending order of the start address and the subtree structure is determined by the CIDRs coverage.

func (*Table[V]) Insert added in v0.2.0 

func (t *Table[V]) Insert(pfx netip.Prefix, value V)

Insert adds pfx to the routing table with value of generic type V. If pfx is already present in the table, its value is set to the new value.

func (Table[V]) InsertImmutable added in v0.3.0 

func (t Table[V]) InsertImmutable(pfx netip.Prefix, value V) *Table[V]

InsertImmutable adds pfx to the table with value of generic type V, returning a new table. If pfx is already present in the table, its value is set to the new value.

func (Table[V]) Lookup added in v0.3.0 

func (t Table[V]) Lookup(ip netip.Addr) (lpm netip.Prefix, value V, ok bool)

Lookup returns the longest-prefix-match (lpm) for given ip. If the ip isn't covered by any CIDR, the zero value and false is returned.

Lookup does not allocate memory.

Example 
package main

import (
	"fmt"
	"net/netip"
	"os"

	"github.com/gaissmai/cidrtree"
)

func mustAddr(s string) netip.Addr {
	return netip.MustParseAddr(s)
}

func mustPfx(s string) netip.Prefix {
	return netip.MustParsePrefix(s)
}

var input = []struct {
	cidr    netip.Prefix
	nextHop netip.Addr
}{
	{mustPfx("fe80::/10"), mustAddr("::1%lo")},
	{mustPfx("172.16.0.0/12"), mustAddr("8.8.8.8")},
	{mustPfx("10.0.0.0/24"), mustAddr("8.8.8.8")},
	{mustPfx("::1/128"), mustAddr("::1%eth0")},
	{mustPfx("192.168.0.0/16"), mustAddr("9.9.9.9")},
	{mustPfx("10.0.0.0/8"), mustAddr("9.9.9.9")},
	{mustPfx("::/0"), mustAddr("2001:db8::1")},
	{mustPfx("10.0.1.0/24"), mustAddr("10.0.0.0")},
	{mustPfx("169.254.0.0/16"), mustAddr("10.0.0.0")},
	{mustPfx("2000::/3"), mustAddr("2001:db8::1")},
	{mustPfx("2001:db8::/32"), mustAddr("2001:db8::1")},
	{mustPfx("127.0.0.0/8"), mustAddr("127.0.0.1")},
	{mustPfx("127.0.0.1/32"), mustAddr("127.0.0.1")},
	{mustPfx("192.168.1.0/24"), mustAddr("127.0.0.1")},
}

func main() {
	rtbl := new(cidrtree.Table[netip.Addr])
	for _, item := range input {
		rtbl.Insert(item.cidr, item.nextHop)
	}
	rtbl.Fprint(os.Stdout)

	fmt.Println()

	ip := mustAddr("42.0.0.0")
	lpm, value, ok := rtbl.Lookup(ip)
	fmt.Printf("Lookup: %-20v lpm: %-15v value: %11v, ok: %v\n", ip, lpm, value, ok)

	ip = mustAddr("10.0.1.17")
	lpm, value, ok = rtbl.Lookup(ip)
	fmt.Printf("Lookup: %-20v lpm: %-15v value: %11v, ok: %v\n", ip, lpm, value, ok)

	ip = mustAddr("2001:7c0:3100:1::111")
	lpm, value, ok = rtbl.Lookup(ip)
	fmt.Printf("Lookup: %-20v lpm: %-15v value: %11v, ok: %v\n", ip, lpm, value, ok)

}

Output:

▼
├─ 10.0.0.0/8 (9.9.9.9)
│  ├─ 10.0.0.0/24 (8.8.8.8)
│  └─ 10.0.1.0/24 (10.0.0.0)
├─ 127.0.0.0/8 (127.0.0.1)
│  └─ 127.0.0.1/32 (127.0.0.1)
├─ 169.254.0.0/16 (10.0.0.0)
├─ 172.16.0.0/12 (8.8.8.8)
└─ 192.168.0.0/16 (9.9.9.9)
   └─ 192.168.1.0/24 (127.0.0.1)
▼
└─ ::/0 (2001:db8::1)
   ├─ ::1/128 (::1%eth0)
   ├─ 2000::/3 (2001:db8::1)
   │  └─ 2001:db8::/32 (2001:db8::1)
   └─ fe80::/10 (::1%lo)

Lookup: 42.0.0.0             lpm: invalid Prefix  value:  invalid IP, ok: false
Lookup: 10.0.1.17            lpm: 10.0.1.0/24     value:    10.0.0.0, ok: true
Lookup: 2001:7c0:3100:1::111 lpm: 2000::/3        value: 2001:db8::1, ok: true

func (Table[V]) LookupPrefix added in v0.3.0 

func (t Table[V]) LookupPrefix(pfx netip.Prefix) (lpm netip.Prefix, value V, ok bool)

LookupPrefix returns the longest-prefix-match (lpm) for given prefix. If the prefix isn't equal or covered by any CIDR in the table, the zero value and false is returned.

LookupPrefix does not allocate memory.

func (Table[V]) String added in v0.2.0 

func (t Table[V]) String() string

String returns a hierarchical tree diagram of the ordered CIDRs as string, just a wrapper for [Tree.Fprint].

func (*Table[V]) Union added in v0.2.0 

func (t *Table[V]) Union(other Table[V])

Union combines two tables, changing the receiver table. If there are duplicate entries, the value is taken from the other table.

func (Table[V]) UnionImmutable added in v0.3.0 

func (t Table[V]) UnionImmutable(other Table[V]) *Table[V]

UnionImmutable combines any two tables immutable and returns the combined table. If there are duplicate entries, the value is taken from the other table.

func (Table[V]) Walk added in v0.2.0 

func (t Table[V]) Walk(cb func(pfx netip.Prefix, value V) bool)

Walk iterates the cidrtree in ascending order. The callback function is called with the prefix and value of the respective node and the depth in the tree. If callback returns `false`, the iteration is aborted.

Example 
package main

import (
	"fmt"
	"net/netip"

	"github.com/gaissmai/cidrtree"
)

func mustAddr(s string) netip.Addr {
	return netip.MustParseAddr(s)
}

func mustPfx(s string) netip.Prefix {
	return netip.MustParsePrefix(s)
}

var input = []struct {
	cidr    netip.Prefix
	nextHop netip.Addr
}{
	{mustPfx("fe80::/10"), mustAddr("::1%lo")},
	{mustPfx("172.16.0.0/12"), mustAddr("8.8.8.8")},
	{mustPfx("10.0.0.0/24"), mustAddr("8.8.8.8")},
	{mustPfx("::1/128"), mustAddr("::1%eth0")},
	{mustPfx("192.168.0.0/16"), mustAddr("9.9.9.9")},
	{mustPfx("10.0.0.0/8"), mustAddr("9.9.9.9")},
	{mustPfx("::/0"), mustAddr("2001:db8::1")},
	{mustPfx("10.0.1.0/24"), mustAddr("10.0.0.0")},
	{mustPfx("169.254.0.0/16"), mustAddr("10.0.0.0")},
	{mustPfx("2000::/3"), mustAddr("2001:db8::1")},
	{mustPfx("2001:db8::/32"), mustAddr("2001:db8::1")},
	{mustPfx("127.0.0.0/8"), mustAddr("127.0.0.1")},
	{mustPfx("127.0.0.1/32"), mustAddr("127.0.0.1")},
	{mustPfx("192.168.1.0/24"), mustAddr("127.0.0.1")},
}

func main() {
	cb := func(p netip.Prefix, val any) bool {
		fmt.Printf("%v (%v)\n", p, val)
		return true
	}

	rtbl := new(cidrtree.Table[any])
	for _, item := range input {
		rtbl.Insert(item.cidr, item.nextHop)
	}
	rtbl.Walk(cb)

}

Output:

10.0.0.0/8 (9.9.9.9)
10.0.0.0/24 (8.8.8.8)
10.0.1.0/24 (10.0.0.0)
127.0.0.0/8 (127.0.0.1)
127.0.0.1/32 (127.0.0.1)
169.254.0.0/16 (10.0.0.0)
172.16.0.0/12 (8.8.8.8)
192.168.0.0/16 (9.9.9.9)
192.168.1.0/24 (127.0.0.1)
::/0 (2001:db8::1)
::1/128 (::1%eth0)
2000::/3 (2001:db8::1)
2001:db8::/32 (2001:db8::1)
fe80::/10 (::1%lo)

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.