README
¶
package bart
Overview
package bart provides a Balanced-Routing-Table (BART) for very fast IP to CIDR lookups and more.
BART is balanced in terms of memory usage and lookup time for the longest-prefix match.
BART is a multibit-trie with fixed stride length of 8 bits, using a fast mapping function (based on Donald E. Knuths ART algorithm) to map the 256 prefixes in each level node to form a complete-binary-tree.
This complete binary tree is implemented with popcount compressed sparse arrays together with path compression. This reduces storage consumption by almost two orders of magnitude in comparison to ART, with even better lookup times for the longest prefix match.
The BART algorithm is based on fixed size bit vectors and precalculated lookup tables. The lookup is performed entirely by fast, cache-friendly bitmask operations, which in modern CPUs are performed by advanced bit manipulation instruction sets (POPCNT, LZCNT, TZCNT, ...).
You should specify the CPU feature set when compiling, e.g. GOAMD64=v2 for maximum performance, see also https://go.dev/wiki/MinimumRequirements#architectures
The algorithm was specially developed so that it can always work with a fixed length of 256 bits. This means that the bitset fit very well in a cache line and that loops over the bitset in hot paths can be accelerated by loop unrolling, e.g.
func (b *BitSet256) popcnt() (cnt int) {
cnt += bits.OnesCount64(b[0])
cnt += bits.OnesCount64(b[1])
cnt += bits.OnesCount64(b[2])
cnt += bits.OnesCount64(b[3])
return
}
A future Go version that supports SIMD intrinsics for the [4]uint64 vectors will
probably allow the algorithm to be made even faster on suitable hardware.
The BART algorithm is also excellent for determining whether two tables contain overlapping IP addresses, just in a few nanoseconds.
There is an example demonstrating how to use bart concurrently with multiple readers and writers.
Readers can access the table lock-free, while writers synchronize using a mutex to ensure
that only one writer can modify the table persistent at a time.
See the ExampleTable_concurrent test for a concrete example of this pattern.
A bart.Lite wrapper is also included, this is ideal for simple IP
ACLs (access-control-lists) with plain true/false results and no payload.
Example
func ExampleLite_Contains() {
lite := new(bart.Lite)
// Insert some prefixes
prefixes := []string{
"192.168.0.0/16",
"192.168.1.0/24",
"2001:7c0:3100::/40",
"2001:7c0:3100:1::/64",
"fc00::/7",
}
for _, s := range prefixes {
pfx := netip.MustParsePrefix(s)
lite.Insert(pfx)
}
// Test some IP addresses for black/whitelist containment
ips := []string{
"192.168.1.100", // must match
"192.168.2.1", // must match
"2001:7c0:3100:1::1", // must match
"2001:7c0:3100:2::1", // must match
"fc00::1", // must match
//
"172.16.0.1", // must NOT match
"2003:dead:beef::1", // must NOT match
}
for _, s := range ips {
ip := netip.MustParseAddr(s)
ok := lite.Contains(ip)
fmt.Printf("%-20s is contained: %t\n", ip, ok)
}
// Output:
// 192.168.1.100 is contained: true
// 192.168.2.1 is contained: true
// 2001:7c0:3100:1::1 is contained: true
// 2001:7c0:3100:2::1 is contained: true
// fc00::1 is contained: true
// 172.16.0.1 is contained: false
// 2003:dead:beef::1 is contained: false
}
API
From release v0.18.x on, bart requires at least go1.23, the iter.Seq2[netip.Prefix, V] types for iterators
are used.
import "github.com/gaissmai/bart"
type Table[V any] struct {
// Has unexported fields.
}
// Table is an IPv4 and IPv6 routing table with payload V. The zero value is
// ready to use.
// The Table is safe for concurrent readers but not for concurrent readers
// and/or writers. Either the update operations must be protected by an
// external lock mechanism or the various ...Persist functions must be used
// which return a modified routing table by leaving the original unchanged
// A Table must not be copied by value.
func (t *Table[V]) Contains(ip netip.Addr) bool
func (t *Table[V]) Lookup(ip netip.Addr) (val V, ok bool)
func (t *Table[V]) LookupPrefix(pfx netip.Prefix) (val V, ok bool)
func (t *Table[V]) LookupPrefixLPM(pfx netip.Prefix) (lpm netip.Prefix, val V, ok bool)
func (t *Table[V]) Insert(pfx netip.Prefix, val V)
func (t *Table[V]) Delete(pfx netip.Prefix)
func (t *Table[V]) Update(pfx netip.Prefix, cb func(val V, ok bool) V) (newVal V)
func (t *Table[V]) InsertPersist(pfx netip.Prefix, val V) *Table[V]
func (t *Table[V]) DeletePersist(pfx netip.Prefix) *Table[V]
func (t *Table[V]) UpdatePersist(pfx netip.Prefix, cb func(val V, ok bool) V) (pt *Table[V], newVal V)
func (t *Table[V]) Get(pfx netip.Prefix) (val V, ok bool)
func (t *Table[V]) GetAndDelete(pfx netip.Prefix) (val V, ok bool)
func (t *Table[V]) GetAndDeletePersist(pfx netip.Prefix) (pt *Table[V], val V, ok bool)
func (t *Table[V]) Union(o *Table[V])
func (t *Table[V]) Clone() *Table[V]
func (t *Table[V]) OverlapsPrefix(pfx netip.Prefix) bool
func (t *Table[V]) Overlaps(o *Table[V]) bool
func (t *Table[V]) Overlaps4(o *Table[V]) bool
func (t *Table[V]) Overlaps6(o *Table[V]) bool
func (t *Table[V]) Subnets(pfx netip.Prefix) iter.Seq2[netip.Prefix, V]
func (t *Table[V]) Supernets(pfx netip.Prefix) iter.Seq2[netip.Prefix, V]
func (t *Table[V]) All() iter.Seq2[netip.Prefix, V]
func (t *Table[V]) All4() iter.Seq2[netip.Prefix, V]
func (t *Table[V]) All6() iter.Seq2[netip.Prefix, V]
func (t *Table[V]) AllSorted() iter.Seq2[netip.Prefix, V]
func (t *Table[V]) AllSorted4() iter.Seq2[netip.Prefix, V]
func (t *Table[V]) AllSorted6() iter.Seq2[netip.Prefix, V]
func (t *Table[V]) Size() int
func (t *Table[V]) Size4() int
func (t *Table[V]) Size6() int
func (t *Table[V]) String() string
func (t *Table[V]) Fprint(w io.Writer) error
func (t *Table[V]) MarshalText() ([]byte, error)
func (t *Table[V]) MarshalJSON() ([]byte, error)
func (t *Table[V]) DumpList4() []DumpListNode[V]
func (t *Table[V]) DumpList6() []DumpListNode[V]
benchmarks
Please see the extensive benchmarks comparing bart with other IP routing table implementations.
Just a teaser, Contains and Lookup against the Tier1 full Internet routing table with
random IP address probes:
$ GOAMD64=v2 go test -run=xxx -bench=FullM/Contains -cpu=1
goos: linux
goarch: amd64
pkg: github.com/gaissmai/bart
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
BenchmarkFullMatch4/Contains 83951143 14.15 ns/op
BenchmarkFullMatch6/Contains 62731105 19.14 ns/op
BenchmarkFullMiss4/Contains 74333276 16.17 ns/op
BenchmarkFullMiss6/Contains 142984221 8.610 ns/op
$ GOAMD64=v2 go test -run=xxx -bench=FullM/Lookup -skip=/x -cpu=1
goos: linux
goarch: amd64
pkg: github.com/gaissmai/bart
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
BenchmarkFullMatch4/Lookup 54066939 22.09 ns/op
BenchmarkFullMatch6/Lookup 27839944 44.13 ns/op
BenchmarkFullMiss4/Lookup 55061455 21.80 ns/op
BenchmarkFullMiss6/Lookup 100000000 11.21 ns/op
Compatibility Guarantees
The package is currently released as a pre-v1 version, which gives the author the freedom to break backward compatibility to help improve the API as he learns which initial design decisions would need to be revisited to better support the use cases that the library solves for.
These occurrences are expected to be rare in frequency and the API is already quite stable.
CONTRIBUTION
Please open an issue for discussion before sending a pull request.
CREDIT
Standing on the shoulders of giants.
Credits for many inspirations go to
- the clever guys at tailscale,
- to Daniel Lemire for his inspiring blog,
- to Donald E. Knuth for the ART routing algorithm and
- to Yoichi Hariguchi who deciphered it for us mere mortals
And last but not least to the Go team who do a wonderful job!
LICENSE
MIT
Documentation
¶
Overview ¶
Package bart provides a Balanced-Routing-Table (BART).
BART is balanced in terms of memory usage and lookup time for the longest-prefix match.
BART is a multibit-trie with fixed stride length of 8 bits, using a fast mapping function (taken from the ART algorithm) to map the 256 prefixes in each level node to form a complete-binary-tree.
This complete binary tree is implemented with popcount compressed sparse arrays together with path compression. This reduces storage consumption by almost two orders of magnitude in comparison to ART, with even better lookup times for the longest prefix match.
The BART algorithm is based on bit vectors and precalculated lookup tables. The search is performed entirely by fast, cache-friendly bitmask operations, which in modern CPUs are performed by advanced bit manipulation instruction sets (POPCNT, LZCNT, TZCNT).
The algorithm was specially developed so that it can always work with a fixed length of 256 bits. This means that the bitsets fit well in a cache line and that loops in hot paths (4x uint64 = 256) can be accelerated by loop unrolling.
Index ¶
- type Cloner
- type DumpListNode
- type Lite
- func (l *Lite) Clone() *Lite
- func (l *Lite) DeletePersist(pfx netip.Prefix) *Lite
- func (l *Lite) Exists(pfx netip.Prefix) bool
- func (l *Lite) GetAndDelete()deprecated
- func (l *Lite) GetAndDeletePersist()deprecated
- func (l *Lite) Insert(pfx netip.Prefix)
- func (l *Lite) InsertPersist(pfx netip.Prefix) *Lite
- func (l *Lite) Overlaps(o *Lite) bool
- func (l *Lite) Overlaps4(o *Lite) bool
- func (l *Lite) Overlaps6(o *Lite) bool
- func (l *Lite) Union(o *Lite)
- func (l *Lite) Update()deprecated
- func (l *Lite) UpdatePersist()deprecated
- type Table
- func (t *Table[V]) All() iter.Seq2[netip.Prefix, V]
- func (t *Table[V]) All4() iter.Seq2[netip.Prefix, V]
- func (t *Table[V]) All6() iter.Seq2[netip.Prefix, V]
- func (t *Table[V]) AllSorted() iter.Seq2[netip.Prefix, V]
- func (t *Table[V]) AllSorted4() iter.Seq2[netip.Prefix, V]
- func (t *Table[V]) AllSorted6() iter.Seq2[netip.Prefix, V]
- func (t *Table[V]) Clone() *Table[V]
- func (t *Table[V]) Contains(ip netip.Addr) bool
- func (t *Table[V]) Delete(pfx netip.Prefix)
- func (t *Table[V]) DeletePersist(pfx netip.Prefix) *Table[V]
- func (t *Table[V]) DumpList4() []DumpListNode[V]
- func (t *Table[V]) DumpList6() []DumpListNode[V]
- func (t *Table[V]) Fprint(w io.Writer) error
- func (t *Table[V]) Get(pfx netip.Prefix) (val V, ok bool)
- func (t *Table[V]) GetAndDelete(pfx netip.Prefix) (val V, ok bool)
- func (t *Table[V]) GetAndDeletePersist(pfx netip.Prefix) (pt *Table[V], val V, ok bool)
- func (t *Table[V]) Insert(pfx netip.Prefix, val V)
- func (t *Table[V]) InsertPersist(pfx netip.Prefix, val V) *Table[V]
- func (t *Table[V]) Lookup(ip netip.Addr) (val V, ok bool)
- func (t *Table[V]) LookupPrefix(pfx netip.Prefix) (val V, ok bool)
- func (t *Table[V]) LookupPrefixLPM(pfx netip.Prefix) (lpmPfx netip.Prefix, val V, ok bool)
- func (t *Table[V]) MarshalJSON() ([]byte, error)
- func (t *Table[V]) MarshalText() ([]byte, error)
- func (t *Table[V]) Overlaps(o *Table[V]) bool
- func (t *Table[V]) Overlaps4(o *Table[V]) bool
- func (t *Table[V]) Overlaps6(o *Table[V]) bool
- func (t *Table[V]) OverlapsPrefix(pfx netip.Prefix) bool
- func (t *Table[V]) Size() int
- func (t *Table[V]) Size4() int
- func (t *Table[V]) Size6() int
- func (t *Table[V]) String() string
- func (t *Table[V]) Subnets(pfx netip.Prefix) iter.Seq2[netip.Prefix, V]
- func (t *Table[V]) Supernets(pfx netip.Prefix) iter.Seq2[netip.Prefix, V]
- func (t *Table[V]) Union(o *Table[V])
- func (t *Table[V]) Update(pfx netip.Prefix, cb func(val V, ok bool) V) (newVal V)
- func (t *Table[V]) UpdatePersist(pfx netip.Prefix, cb func(val V, ok bool) V) (pt *Table[V], newVal V)
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Cloner ¶ added in v0.12.1
type Cloner[V any] interface { Clone() V }
Cloner is an interface, if implemented by payload of type V the values are deeply copied during Table.UpdatePersist, Table.DeletePersist, Table.Clone and Table.Union.
type DumpListNode ¶ added in v0.1.6
type DumpListNode[V any] struct { CIDR netip.Prefix `json:"cidr"` Value V `json:"value"` Subnets []DumpListNode[V] `json:"subnets,omitempty"` }
DumpListNode contains CIDR, Value and Subnets, representing the trie in a sorted, recursive representation, especially useful for serialization.
type Lite ¶ added in v0.18.1
type Lite struct {
Table[struct{}]
}
Lite is just a convenience wrapper for Table, instantiated with an empty struct as payload. Lite is ideal for simple IP ACLs (access-control-lists) with plain true/false results without a payload.
Lite delegates almost all methods unmodified to the underlying Table.
Some of the Table methods make no sense without a payload. Their signature has been changed and they do not accept any arguments and if they are used anyway, they will generate a panic.
Example (Contains) ¶
package main
import (
"fmt"
"net/netip"
"github.com/gaissmai/bart"
)
var examplePrefixes = []string{
"192.168.0.0/16",
"192.168.1.0/24",
"2001:7c0:3100::/40",
"2001:7c0:3100:1::/64",
"fc00::/7",
}
// some example IP addresses for black/whitelist containment
var exampleIPs = []string{
"192.168.1.100",
"192.168.2.1",
"2001:7c0:3100:1::1",
"2001:7c0:3100:2::1",
"fc00::1",
"172.16.0.1",
"2003:dead:beef::1",
}
func main() {
lite := new(bart.Lite)
for _, s := range examplePrefixes {
pfx := netip.MustParsePrefix(s)
lite.Insert(pfx)
}
for _, s := range exampleIPs {
ip := netip.MustParseAddr(s)
ok := lite.Contains(ip)
fmt.Printf("%-20s is contained: %t\n", ip, ok)
}
}
Output: 192.168.1.100 is contained: true 192.168.2.1 is contained: true 2001:7c0:3100:1::1 is contained: true 2001:7c0:3100:2::1 is contained: true fc00::1 is contained: true 172.16.0.1 is contained: false 2003:dead:beef::1 is contained: false
func (*Lite) DeletePersist ¶ added in v0.20.0
DeletePersist is similar to Delete but the receiver isn't modified.
func (*Lite) Exists ¶ added in v0.20.0
Exists returns true if the prefix exists in the table. It's an adapter to Table.Get.
func (*Lite) GetAndDelete
deprecated
added in
v0.20.0
func (l *Lite) GetAndDelete()
Deprecated: GetAndDelete is pointless without payload and panics.
func (*Lite) GetAndDeletePersist
deprecated
added in
v0.20.0
func (l *Lite) GetAndDeletePersist()
Deprecated: GetAndDeletePersist is pointless without payload and panics.
func (*Lite) InsertPersist ¶ added in v0.20.0
InsertPersist is similar to Insert but the receiver isn't modified.
func (*Lite) Overlaps ¶ added in v0.20.0
Overlaps reports whether any IP in the table matches a route in the other table or vice versa.
func (*Lite) Overlaps4 ¶ added in v0.20.0
Overlaps4 reports whether any IPv4 in the table matches a route in the other table or vice versa.
func (*Lite) Overlaps6 ¶ added in v0.20.0
Overlaps6 reports whether any IPv6 in the table matches a route in the other table or vice versa.
func (*Lite) UpdatePersist
deprecated
added in
v0.20.0
func (l *Lite) UpdatePersist()
Deprecated: UpdatePersist is pointless without payload and panics.
type Table ¶
type Table[V any] struct { // contains filtered or unexported fields }
Table is an IPv4 and IPv6 routing table with payload V. The zero value is ready to use.
The Table is safe for concurrent readers but not for concurrent readers and/or writers. Either the update operations must be protected by an external lock mechanism or the various ...Persist functions must be used which return a modified routing table by leaving the original unchanged
A Table must not be copied by value.
Example (Concurrent) ¶
ExampleTable_concurrent demonstrates safe concurrent usage of bart. This example is intended to be run with the Go race detector enabled (use `go test -race -run=ExampleTable_concurrent`) to verify that concurrent access is safe and free of data races.
package main
import (
"net/netip"
"sync"
"sync/atomic"
"github.com/gaissmai/bart"
)
// SyncTable demonstrates how to wrap a [bart.Table] for safe concurrent access in Go.
//
// This example struct allows multiple goroutines to perform lock-free, concurrent reads
// via an atomic pointer, while synchronizing writers with a mutex to ensure exclusive access.
// This concurrency pattern is useful when reads are frequent and writes are rare
// or take a long time in comparison to reads,
// providing high performance for concurrent workloads.
//
// If the payload V either contains a pointer or is a pointer,
// it must implement the [bart.Cloner] interface.
type SyncTable[V bart.Cloner[V]] struct {
// Atomic pointer to the current table version.
// Enables lock-free, concurrent reads by multiple goroutines.
atomic.Pointer[bart.Table[V]]
// Mutex for synchronizing concurrent writers.
// Writers must acquire the lock before modifying the table.
// No CAS is used for writers; only one writer at a time is allowed.
sync.Mutex
}
// NewSyncTable creates and initializes a new SyncTable.
// The underlying table is initialized and stored atomically.
func NewSyncTable[V bart.Cloner[V]]() *SyncTable[V] {
lf := new(SyncTable[V])
lf.Store(new(bart.Table[V]))
return lf
}
// Contains is a sync adapter for [bart.Table.Contains].
func (lf *SyncTable[V]) Contains(ip netip.Addr) bool {
return lf.Load().Contains(ip)
}
// Lookup is a sync adapter for [bart.Table.Lookup].
func (lf *SyncTable[V]) Lookup(ip netip.Addr) (val V, ok bool) {
return lf.Load().Lookup(ip)
}
// Insert is a sync adapter for [bart.Table.Insert].
// This method acquires a writer lock to ensure exclusive access for writers.
// It creates a new persistent table version and atomically updates the pointer.
// Concurrent readers remain lock-free and always see a consistent table.
func (lf *SyncTable[V]) Insert(pfx netip.Prefix, val V) {
lf.Lock() // acquire writer lock to exclude other writers
defer lf.Unlock()
oldPtr := lf.Load() // get current table version
newPtr := oldPtr.InsertPersist(pfx, val) // create new persistent table version
lf.Store(newPtr) // atomically publish new version for readers
}
// Update is a sync adapter for [bart.Table.Update].
func (lf *SyncTable[V]) Update(pfx netip.Prefix, cb func(val V, ok bool) V) (newVal V) {
lf.Lock()
defer lf.Unlock()
oldPtr := lf.Load()
newPtr, val := oldPtr.UpdatePersist(pfx, cb)
lf.Store(newPtr)
return val
}
// Delete is a sync adapter for [bart.Table.Delete].
func (lf *SyncTable[V]) Delete(pfx netip.Prefix) {
lf.Lock()
defer lf.Unlock()
oldPtr := lf.Load()
newPtr := oldPtr.DeletePersist(pfx)
lf.Store(newPtr)
}
// #######################################
// just a very stupid example of a payload
// #######################################
// testVal is a sample value type.
// We use *testVal as the generic type V, which is a pointer type,
// so it must implement Cloner[*testVal].
type testVal struct {
data int
}
// Clone ensures deep copying for use with ...Persist.
func (v *testVal) Clone() *testVal {
if v == nil {
return nil
}
return &testVal{data: v.data}
}
// example callback for Update, just decrement data
var cb = func(p *testVal, ok bool) *testVal {
if ok && p != nil {
p.data--
return p
}
return &testVal{data: -1}
}
// #######################################
// ExampleTable_concurrent demonstrates safe concurrent usage of bart.
// This example is intended to be run with the Go race detector enabled
// (use `go test -race -run=ExampleTable_concurrent`)
// to verify that concurrent access is safe and free of data races.
func main() {
wg := sync.WaitGroup{}
syncTbl := NewSyncTable[*testVal]()
wg.Add(1)
go func() {
defer wg.Done()
for range 1_000_000 {
for _, s := range exampleIPs {
ip := netip.MustParseAddr(s)
_, _ = syncTbl.Lookup(ip)
}
}
}()
wg.Add(1)
go func() {
defer wg.Done()
for range 10_000 {
for _, s := range examplePrefixes {
pfx := netip.MustParsePrefix(s)
syncTbl.Insert(pfx, &testVal{data: 0})
}
}
}()
wg.Add(1)
go func() {
defer wg.Done()
for range 10_000 {
for _, s := range examplePrefixes {
pfx := netip.MustParsePrefix(s)
syncTbl.Update(pfx, cb)
}
}
}()
wg.Add(1)
go func() {
defer wg.Done()
for range 10_000 {
for _, s := range examplePrefixes {
pfx := netip.MustParsePrefix(s)
syncTbl.Delete(pfx)
}
}
}()
wg.Wait()
}
Output:
func (*Table[V]) All ¶ added in v0.6.0
All returns an iterator over key-value pairs from Table. The iteration order is not specified and is not guaranteed to be the same from one call to the next.
func (*Table[V]) AllSorted ¶ added in v0.11.0
AllSorted returns an iterator over key-value pairs from Table in natural CIDR sort order.
func (*Table[V]) AllSorted4 ¶ added in v0.12.6
AllSorted4 is like Table.AllSorted but only for the v4 routing table.
Example (Rangeoverfunc) ¶
package main
import (
"fmt"
"net/netip"
"github.com/gaissmai/bart"
)
var (
a = netip.MustParseAddr
p = netip.MustParsePrefix
)
var input = []struct {
cidr netip.Prefix
nextHop netip.Addr
}{
{p("fe80::/10"), a("::1%eth0")},
{p("172.16.0.0/12"), a("8.8.8.8")},
{p("10.0.0.0/24"), a("8.8.8.8")},
{p("::1/128"), a("::1%lo")},
{p("192.168.0.0/16"), a("9.9.9.9")},
{p("10.0.0.0/8"), a("9.9.9.9")},
{p("::/0"), a("2001:db8::1")},
{p("10.0.1.0/24"), a("10.0.0.0")},
{p("169.254.0.0/16"), a("10.0.0.0")},
{p("2000::/3"), a("2000::")},
{p("2001:db8::/32"), a("2001:db8::1")},
{p("127.0.0.0/8"), a("127.0.0.1")},
{p("127.0.0.1/32"), a("127.0.0.1")},
{p("192.168.1.0/24"), a("127.0.0.1")},
}
func main() {
rtbl := new(bart.Table[netip.Addr])
for _, item := range input {
rtbl.Insert(item.cidr, item.nextHop)
}
for pfx, val := range rtbl.AllSorted4() {
fmt.Printf("%v\t%v\n", pfx, val)
}
}
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
func (*Table[V]) AllSorted6 ¶ added in v0.12.6
AllSorted6 is like Table.AllSorted but only for the v6 routing table.
func (*Table[V]) Clone ¶ added in v0.4.0
Clone returns a copy of the routing table. The payload of type V is shallow copied, but if type V implements the Cloner interface, the values are cloned.
func (*Table[V]) Contains ¶ added in v0.15.1
Contains does a route lookup for IP and returns true if any route matched.
Contains does not return the value nor the prefix of the matching item, but as a test against a black- or whitelist it's often sufficient and even few nanoseconds faster than Table.Lookup.
func (*Table[V]) DeletePersist ¶ added in v0.18.0
DeletePersist is similar to Delete but the receiver isn't modified. All nodes touched during delete are cloned and a new Table is returned.
This is orders of magnitude slower than Delete (μsec versus nsec).
func (*Table[V]) DumpList4 ¶ added in v0.5.0
func (t *Table[V]) DumpList4() []DumpListNode[V]
DumpList4 dumps the ipv4 tree into a list of roots and their subnets. It can be used to analyze the tree or build the text or json serialization.
func (*Table[V]) DumpList6 ¶ added in v0.5.0
func (t *Table[V]) DumpList6() []DumpListNode[V]
DumpList6 dumps the ipv6 tree into a list of roots and their subnets. It can be used to analyze the tree or build custom json representation.
func (*Table[V]) Fprint ¶
Fprint writes a hierarchical tree diagram of the ordered CIDRs with default formatted payload V to w.
The order from top to bottom is in ascending order of the prefix address and the subtree structure is determined by the CIDRs coverage.
▼ ├─ 10.0.0.0/8 (V) │ ├─ 10.0.0.0/24 (V) │ └─ 10.0.1.0/24 (V) ├─ 127.0.0.0/8 (V) │ └─ 127.0.0.1/32 (V) ├─ 169.254.0.0/16 (V) ├─ 172.16.0.0/12 (V) └─ 192.168.0.0/16 (V) └─ 192.168.1.0/24 (V) ▼ └─ ::/0 (V) ├─ ::1/128 (V) ├─ 2000::/3 (V) │ └─ 2001:db8::/32 (V) └─ fe80::/10 (V)
func (*Table[V]) Get ¶
Get returns the associated payload for prefix and true, or false if prefix is not set in the routing table.
func (*Table[V]) GetAndDelete ¶ added in v0.13.0
GetAndDelete deletes the prefix and returns the associated payload for prefix and true, or the zero value and false if prefix is not set in the routing table.
func (*Table[V]) GetAndDeletePersist ¶ added in v0.18.0
GetAndDeletePersist is similar to GetAndDelete but the receiver isn't modified. All nodes touched during delete are cloned and a new Table is returned.
If the payload V is a pointer or contains a pointer, it should implement the cloner interface.
This is orders of magnitude slower than GetAndDelete (μsec versus nsec).
func (*Table[V]) Insert ¶
Insert adds a pfx to the tree, with given val. If pfx is already present in the tree, its value is set to val.
func (*Table[V]) InsertPersist ¶ added in v0.18.0
InsertPersist is similar to Insert but the receiver isn't modified.
All nodes touched during insert are cloned and a new Table is returned. This is not a full Table.Clone, all untouched nodes are still referenced from both Tables.
If the payload V is a pointer or contains a pointer, it should implement the cloner interface.
This is orders of magnitude slower than Insert (μsec versus nsec).
The bulk table load should be done with Table.Insert and then you can use InsertPersist, Table.UpdatePersist and Table.DeletePersist for lock-free updates.
func (*Table[V]) Lookup ¶
Lookup does a route lookup (longest prefix match) for IP and returns the associated value and true, or false if no route matched.
Example ¶
package main
import (
"fmt"
"net/netip"
"os"
"github.com/gaissmai/bart"
)
var (
a = netip.MustParseAddr
p = netip.MustParsePrefix
)
var input = []struct {
cidr netip.Prefix
nextHop netip.Addr
}{
{p("fe80::/10"), a("::1%eth0")},
{p("172.16.0.0/12"), a("8.8.8.8")},
{p("10.0.0.0/24"), a("8.8.8.8")},
{p("::1/128"), a("::1%lo")},
{p("192.168.0.0/16"), a("9.9.9.9")},
{p("10.0.0.0/8"), a("9.9.9.9")},
{p("::/0"), a("2001:db8::1")},
{p("10.0.1.0/24"), a("10.0.0.0")},
{p("169.254.0.0/16"), a("10.0.0.0")},
{p("2000::/3"), a("2000::")},
{p("2001:db8::/32"), a("2001:db8::1")},
{p("127.0.0.0/8"), a("127.0.0.1")},
{p("127.0.0.1/32"), a("127.0.0.1")},
{p("192.168.1.0/24"), a("127.0.0.1")},
}
func main() {
rtbl := new(bart.Table[netip.Addr])
for _, item := range input {
rtbl.Insert(item.cidr, item.nextHop)
}
rtbl.Fprint(os.Stdout)
fmt.Println()
ip := a("42.0.0.0")
value, ok := rtbl.Lookup(ip)
fmt.Printf("Lookup: %-20v next-hop: %11v, ok: %v\n", ip, value, ok)
ip = a("10.0.1.17")
value, ok = rtbl.Lookup(ip)
fmt.Printf("Lookup: %-20v next-hop: %11v, ok: %v\n", ip, value, ok)
ip = a("2001:7c0:3100:1::111")
value, ok = rtbl.Lookup(ip)
fmt.Printf("Lookup: %-20v next-hop: %11v, ok: %v\n", ip, 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%lo) ├─ 2000::/3 (2000::) │ └─ 2001:db8::/32 (2001:db8::1) └─ fe80::/10 (::1%eth0) Lookup: 42.0.0.0 next-hop: invalid IP, ok: false Lookup: 10.0.1.17 next-hop: 10.0.0.0, ok: true Lookup: 2001:7c0:3100:1::111 next-hop: 2000::, ok: true
func (*Table[V]) LookupPrefix ¶ added in v0.5.0
LookupPrefix does a route lookup (longest prefix match) for pfx and returns the associated value and true, or false if no route matched.
func (*Table[V]) LookupPrefixLPM ¶ added in v0.5.0
LookupPrefixLPM is similar to Table.LookupPrefix, but it returns the lpm prefix in addition to value,ok.
This method is about 20-30% slower than LookupPrefix and should only be used if the matching lpm entry is also required for other reasons.
If LookupPrefixLPM is to be used for IP address lookups, they must be converted to /32 or /128 prefixes.
func (*Table[V]) MarshalJSON ¶ added in v0.1.6
MarshalJSON dumps the table into two sorted lists: for ipv4 and ipv6. Every root and subnet is an array, not a map, because the order matters.
func (*Table[V]) MarshalText ¶ added in v0.1.5
MarshalText implements the encoding.TextMarshaler interface, just a wrapper for Table.Fprint.
func (*Table[V]) Overlaps ¶ added in v0.2.0
Overlaps reports whether any IP in the table is matched by a route in the other table or vice versa.
func (*Table[V]) Overlaps4 ¶ added in v0.10.1
Overlaps4 reports whether any IPv4 in the table matches a route in the other table or vice versa.
func (*Table[V]) Overlaps6 ¶ added in v0.10.1
Overlaps6 reports whether any IPv6 in the table matches a route in the other table or vice versa.
func (*Table[V]) OverlapsPrefix ¶ added in v0.1.5
OverlapsPrefix reports whether any IP in pfx is matched by a route in the table or vice versa.
func (*Table[V]) String ¶
String returns a hierarchical tree diagram of the ordered CIDRs as string, just a wrapper for Table.Fprint. If Fprint returns an error, String panics.
func (*Table[V]) Subnets ¶ added in v0.5.0
Subnets returns an iterator over all CIDRs covered by pfx. The iteration is in natural CIDR sort order.
Example (Rangeoverfunc) ¶
package main
import (
"fmt"
"net/netip"
"github.com/gaissmai/bart"
)
var (
a = netip.MustParseAddr
p = netip.MustParsePrefix
)
var input = []struct {
cidr netip.Prefix
nextHop netip.Addr
}{
{p("fe80::/10"), a("::1%eth0")},
{p("172.16.0.0/12"), a("8.8.8.8")},
{p("10.0.0.0/24"), a("8.8.8.8")},
{p("::1/128"), a("::1%lo")},
{p("192.168.0.0/16"), a("9.9.9.9")},
{p("10.0.0.0/8"), a("9.9.9.9")},
{p("::/0"), a("2001:db8::1")},
{p("10.0.1.0/24"), a("10.0.0.0")},
{p("169.254.0.0/16"), a("10.0.0.0")},
{p("2000::/3"), a("2000::")},
{p("2001:db8::/32"), a("2001:db8::1")},
{p("127.0.0.0/8"), a("127.0.0.1")},
{p("127.0.0.1/32"), a("127.0.0.1")},
{p("192.168.1.0/24"), a("127.0.0.1")},
}
func main() {
rtbl := new(bart.Table[netip.Addr])
for _, item := range input {
rtbl.Insert(item.cidr, item.nextHop)
}
cidr := netip.MustParsePrefix("0.0.0.0/1")
for pfx := range rtbl.Subnets(cidr) {
fmt.Printf("%v\n", pfx)
}
}
Output: 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
func (*Table[V]) Supernets ¶ added in v0.5.0
Supernets returns an iterator over all CIDRs covering pfx. The iteration is in reverse CIDR sort order, from longest-prefix-match to shortest-prefix-match.
Example (Rangeoverfunc) ¶
package main
import (
"fmt"
"net/netip"
"github.com/gaissmai/bart"
)
var (
a = netip.MustParseAddr
p = netip.MustParsePrefix
)
var input = []struct {
cidr netip.Prefix
nextHop netip.Addr
}{
{p("fe80::/10"), a("::1%eth0")},
{p("172.16.0.0/12"), a("8.8.8.8")},
{p("10.0.0.0/24"), a("8.8.8.8")},
{p("::1/128"), a("::1%lo")},
{p("192.168.0.0/16"), a("9.9.9.9")},
{p("10.0.0.0/8"), a("9.9.9.9")},
{p("::/0"), a("2001:db8::1")},
{p("10.0.1.0/24"), a("10.0.0.0")},
{p("169.254.0.0/16"), a("10.0.0.0")},
{p("2000::/3"), a("2000::")},
{p("2001:db8::/32"), a("2001:db8::1")},
{p("127.0.0.0/8"), a("127.0.0.1")},
{p("127.0.0.1/32"), a("127.0.0.1")},
{p("192.168.1.0/24"), a("127.0.0.1")},
}
func main() {
rtbl := new(bart.Table[netip.Addr])
for _, item := range input {
rtbl.Insert(item.cidr, item.nextHop)
}
cidr := netip.MustParsePrefix("2001:db8::/32")
counter := 0
for pfx := range rtbl.Supernets(cidr) {
fmt.Printf("%v\n", pfx)
counter++
if counter >= 2 {
break
}
}
}
Output: 2001:db8::/32 2000::/3
func (*Table[V]) Union ¶ added in v0.3.0
Union combines two tables, changing the receiver table. If there are duplicate entries, the payload of type V is shallow copied from the other table. If type V implements the Cloner interface, the values are cloned, see also Table.Clone.
func (*Table[V]) Update ¶ added in v0.5.0
Update or set the value at pfx with a callback function. The callback function is called with (value, ok) and returns a new value.
If the pfx does not already exist, it is set with the new value.
func (*Table[V]) UpdatePersist ¶ added in v0.18.0
func (t *Table[V]) UpdatePersist(pfx netip.Prefix, cb func(val V, ok bool) V) (pt *Table[V], newVal V)
UpdatePersist is similar to Update but the receiver isn't modified.
All nodes touched during update are cloned and a new Table is returned. This is not a full Table.Clone, all untouched nodes are still referenced from both Tables.
If the payload V is a pointer or contains a pointer, it should implement the cloner interface.
This is orders of magnitude slower than Update (μsec versus nsec).
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
internal
|
|
|
allot
Package allot contains the precalculated bitsets of all baseIndices, which for a given prefix contain all longer prefixes covered by it.
|
Package allot contains the precalculated bitsets of all baseIndices, which for a given prefix contain all longer prefixes covered by it. |
|
art
Package art summarizes the functions and inverse functions for mapping between a prefix and a baseIndex.
|
Package art summarizes the functions and inverse functions for mapping between a prefix and a baseIndex. |
|
bitset
Package bitset implements bitsets, a mapping between non-negative integers and boolean values.
|
Package bitset implements bitsets, a mapping between non-negative integers and boolean values. |
|
lpm
Package lpm (longest-prefix-match) contains the lookup table with which the backtracking for the lpm in the complete binary tree of the prefixes can be replaced by a fast bitset operation.
|
Package lpm (longest-prefix-match) contains the lookup table with which the backtracking for the lpm in the complete binary tree of the prefixes can be replaced by a fast bitset operation. |
|
sparse
Package sparse implements a special sparse array with popcount compression for max.
|
Package sparse implements a special sparse array with popcount compression for max. |