README
¶
package cidrtree
!!! ATTENTION, API HAS CHANGED
The API has changed from v0.1.4 to v0.2.0.
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 struct { // Has unexported fields. }
Table is an IPv4 and IPv6 routing table. The zero value is ready to use.
func (t Table) LookupIP(ip netip.Addr) (lpm netip.Prefix, value any, ok bool)
func (t Table) LookupCIDR(pfx netip.Prefix) (lpm netip.Prefix, value any, ok bool)
func (t Table) Insert(pfx netip.Prefix, val any) *Table
func (t Table) Delete(cidr netip.Prefix) (*Table, bool)
func (t Table) Union(other *Table) *Table
func (t Table) Clone() *Table
func (t *Table) InsertMutable(pfx netip.Prefix, val any)
func (t *Table) DeleteMutable(cidr netip.Prefix) bool
func (t *Table) UnionMutable(other *Table)
func (t Table) String() string
func (t Table) Fprint(w io.Writer) error
func (t Table) Walk(cb func(pfx netip.Prefix, val any) 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 ¶
- type Table
- func (t Table) Clone() *Table
- func (t Table) Delete(cidr netip.Prefix) (*Table, bool)
- func (t *Table) DeleteMutable(cidr netip.Prefix) bool
- func (t Table) Fprint(w io.Writer) error
- func (t Table) Insert(pfx netip.Prefix, val any) *Table
- func (t *Table) InsertMutable(pfx netip.Prefix, val any)
- func (t Table) LookupCIDR(pfx netip.Prefix) (lpm netip.Prefix, value any, ok bool)
- func (t Table) LookupIP(ip netip.Addr) (lpm netip.Prefix, value any, ok bool)
- func (t Table) String() string
- func (t Table) Union(other *Table) *Table
- func (t *Table) UnionMutable(other *Table)
- func (t Table) Walk(cb func(pfx netip.Prefix, val any) bool)
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 struct {
// contains filtered or unexported fields
}
Table is an IPv4 and IPv6 routing table. The zero value is ready to use.
func (Table) Delete ¶ added in v0.2.0
Delete removes the cdir if it exists, returns the new table and true, false if not found.
func (*Table) DeleteMutable ¶ added in v0.2.0
DeleteMutable removes the cidr from table, returns true if it exists, false otherwise. If the original table does not need to be preserved then this is much faster than the immutable delete.
func (Table) Fprint ¶ added in v0.2.0
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.
Example ¶
package main
import (
"net/netip"
"os"
"github.com/gaissmai/cidrtree"
)
var input = []netip.Prefix{
netip.MustParsePrefix("fe80::/10"),
netip.MustParsePrefix("172.16.0.0/12"),
netip.MustParsePrefix("10.0.0.0/24"),
netip.MustParsePrefix("::1/128"),
netip.MustParsePrefix("192.168.0.0/16"),
netip.MustParsePrefix("10.0.0.0/8"),
netip.MustParsePrefix("::/0"),
netip.MustParsePrefix("10.0.1.0/24"),
netip.MustParsePrefix("169.254.0.0/16"),
netip.MustParsePrefix("2000::/3"),
netip.MustParsePrefix("2001:db8::/32"),
netip.MustParsePrefix("127.0.0.0/8"),
netip.MustParsePrefix("127.0.0.1/32"),
netip.MustParsePrefix("192.168.1.0/24"),
}
func main() {
rtbl := new(cidrtree.Table)
for _, cidr := range input {
rtbl.InsertMutable(cidr, nil)
}
rtbl.Fprint(os.Stdout)
}
Output: ▼ ├─ 10.0.0.0/8 (<nil>) │ ├─ 10.0.0.0/24 (<nil>) │ └─ 10.0.1.0/24 (<nil>) ├─ 127.0.0.0/8 (<nil>) │ └─ 127.0.0.1/32 (<nil>) ├─ 169.254.0.0/16 (<nil>) ├─ 172.16.0.0/12 (<nil>) └─ 192.168.0.0/16 (<nil>) └─ 192.168.1.0/24 (<nil>) ▼ └─ ::/0 (<nil>) ├─ ::1/128 (<nil>) ├─ 2000::/3 (<nil>) │ └─ 2001:db8::/32 (<nil>) └─ fe80::/10 (<nil>)
func (Table) Insert ¶ added in v0.2.0
Insert adds pfx to the table with value val, returning a new table. If pfx is already present in the table, its value is set to val.
func (*Table) InsertMutable ¶ added in v0.2.0
InsertMutable adds pfx to the table with value val, changing the original table. If pfx is already present in the table, its value is set to val.
func (Table) LookupCIDR ¶ added in v0.2.0
LookupCIDR 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.
LookupCIDR does not allocate memory.
example:
▼
├─ 10.0.0.0/8
│ ├─ 10.0.0.0/24
│ └─ 10.0.1.0/24
├─ 127.0.0.0/8
│ └─ 127.0.0.1/32
├─ 169.254.0.0/16
├─ 172.16.0.0/12
└─ 192.168.0.0/16
└─ 192.168.1.0/24
▼
└─ ::/0
├─ ::1/128
├─ 2000::/3
│ └─ 2001:db8::/32
├─ fc00::/7
├─ fe80::/10
└─ ff00::/8
rtbl.LookupCIDR(42.0.0.0/8) returns (netip.Prefix{}, <nil>, false)
rtbl.LookupCIDR(10.0.1.0/29) returns (10.0.1.0/24, <value>, true)
rtbl.LookupCIDR(192.168.0.0/16) returns (192.168.0.0/16, <value>, true)
rtbl.LookupCIDR(2001:7c0:3100::/40) returns (2000::/3, <value>, true)
func (Table) LookupIP ¶ added in v0.2.0
LookupIP 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.
LookupIP does not allocate memory.
example:
▼
├─ 10.0.0.0/8
│ ├─ 10.0.0.0/24
│ └─ 10.0.1.0/24
├─ 127.0.0.0/8
│ └─ 127.0.0.1/32
├─ 169.254.0.0/16
├─ 172.16.0.0/12
└─ 192.168.0.0/16
└─ 192.168.1.0/24
▼
└─ ::/0
├─ ::1/128
├─ 2000::/3
│ └─ 2001:db8::/32
├─ fc00::/7
├─ fe80::/10
└─ ff00::/8
rtbl.LookupIP(42.0.0.0) returns (netip.Prefix{}, <nil>, false)
rtbl.LookupIP(10.0.1.17) returns (10.0.1.0/24, <value>, true)
rtbl.LookupIP(2001:7c0:3100:1::111) returns (2000::/3, <value>, true)
func (Table) String ¶ added in v0.2.0
String returns a hierarchical tree diagram of the ordered CIDRs as string, just a wrapper for [Tree.Fprint].
func (Table) Union ¶ added in v0.2.0
Union 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) UnionMutable ¶ added in v0.2.0
UnionMutable combines two tables, changing the receiver table. If there are duplicate entries, the value is taken from the other table.
func (Table) Walk ¶ added in v0.2.0
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"
)
var input = []netip.Prefix{
netip.MustParsePrefix("fe80::/10"),
netip.MustParsePrefix("172.16.0.0/12"),
netip.MustParsePrefix("10.0.0.0/24"),
netip.MustParsePrefix("::1/128"),
netip.MustParsePrefix("192.168.0.0/16"),
netip.MustParsePrefix("10.0.0.0/8"),
netip.MustParsePrefix("::/0"),
netip.MustParsePrefix("10.0.1.0/24"),
netip.MustParsePrefix("169.254.0.0/16"),
netip.MustParsePrefix("2000::/3"),
netip.MustParsePrefix("2001:db8::/32"),
netip.MustParsePrefix("127.0.0.0/8"),
netip.MustParsePrefix("127.0.0.1/32"),
netip.MustParsePrefix("192.168.1.0/24"),
}
func main() {
cb := func(p netip.Prefix, val any) bool {
fmt.Printf("%v (%v)\n", p, val)
return true
}
rtbl := new(cidrtree.Table)
for _, cidr := range input {
rtbl.InsertMutable(cidr, nil)
}
rtbl.Walk(cb)
}
Output: 10.0.0.0/8 (<nil>) 10.0.0.0/24 (<nil>) 10.0.1.0/24 (<nil>) 127.0.0.0/8 (<nil>) 127.0.0.1/32 (<nil>) 169.254.0.0/16 (<nil>) 172.16.0.0/12 (<nil>) 192.168.0.0/16 (<nil>) 192.168.1.0/24 (<nil>) ::/0 (<nil>) ::1/128 (<nil>) 2000::/3 (<nil>) 2001:db8::/32 (<nil>) fe80::/10 (<nil>)
Source Files