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=v3 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.
lock-free concurrency
There are examples demonstrating how to use bart concurrently with multiple readers and writers. Readers can access the table always lock-free, while writers may synchronize using a mutex to ensure that only one writer can modify the table persistent at a time, not using Compare-and-Swap (CAS) with all the known problems for multiple long-running writers.
The combination of lock-free concurrency, fast lookup and update times and low memory consumption provides clear advantages for any routing daemon.
But as always, it depends on the specific use case.
See the ExampleLite_concurrent and ExampleTable_concurrent tests for concrete examples of this pattern.
API
import "github.com/gaissmai/bart"
type Table[V any] struct {
// Has unexported fields.
}
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]) Clone() *Table[V]
func (t *Table[V]) Union(o *Table[V])
func (t *Table[V]) UnionPersist(o *Table[V]) *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]
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.
Lite is just a convenience wrapper for Table, instantiated with an empty
struct as payload.
Lite wraps or adapts some methods where needed and delegates almost all other methods unmodified to the underlying Table. Some delegated methods are pointless without a payload.
type Lite struct {
Table[struct{}]
}
func (l *Lite) Exists(pfx netip.Prefix) bool
func (l *Lite) Contains(pfx netip.Prefix) bool
func (l *Lite) Insert(pfx netip.Prefix)
func (l *Lite) Delete(pfx netip.Prefix)
func (l *Lite) InsertPersist(pfx netip.Prefix) *Lite
func (l *Lite) DeletePersist(pfx netip.Prefix) *Lite
func (l *Lite) Clone() *Lite
func (l *Lite) Union(o *Lite)
func (l *Lite) UnionPersist(o *Lite) *Lite
func (l *Lite) Overlaps(o *Lite) bool
func (l *Lite) Overlaps4(o *Lite) bool
func (l *Lite) Overlaps6(o *Lite) bool
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=v3 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 82013714 13.59 ns/op
BenchmarkFullMatch6/Contains 64516006 18.66 ns/op
BenchmarkFullMiss4/Contains 75341578 15.94 ns/op
BenchmarkFullMiss6/Contains 148116180 8.122 ns/op
$ GOAMD64=v3 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 54616323 22.02 ns/op
BenchmarkFullMatch6/Lookup 30073657 39.98 ns/op
BenchmarkFullMiss4/Lookup 55132899 21.90 ns/op
BenchmarkFullMiss6/Lookup 100000000 11.12 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 high-performance Balanced Routing Table (BART).
BART is balanced in terms of memory usage and lookup time for longest-prefix match (LPM) queries on IPv4 and IPv6 addresses.
Internally, BART is implemented as a multibit trie with a fixed stride of 8 bits. Each level node uses a fast mapping function (adapted from D. E. Knuths ART algorithm) to arrange all 256 possible prefixes in a complete binary tree structure.
Instead of allocating full arrays, BART uses popcount-compressed sparse arrays and aggressive path compression. This results in up to 100x less memory usage than ART, while maintaining or even improving lookup speed.
Lookup operations are entirely bit-vector based and rely on precomputed lookup tables. Because the data fits within 256-bit blocks, it allows for extremely efficient, cacheline-aligned access and is accelerated by CPU instructions such as POPCNT, LZCNT, and TZCNT.
The fixed 256-bit representation (4x uint64) permits loop unrolling in hot paths, ensuring predictable and fast performance even under high routing load.
Index ¶
- type Cloner
- type DumpListNode
- type Lite
- func (l *Lite) Clone() *Lite
- func (l *Lite) Contains(ip netip.Addr) bool
- func (l *Lite) Delete(pfx netip.Prefix)
- func (l *Lite) DeletePersist(pfx netip.Prefix) *Lite
- func (l *Lite) Exists(pfx netip.Prefix) bool
- 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) UnionPersist(o *Lite) *Lite
- 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]) UnionPersist(o *Table[V]) *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 ¶
type Cloner[V any] interface { Clone() V }
Cloner is an interface that enables deep cloning of values of type V. If a value implements Cloner[V], Table methods such as InsertPersist, UpdatePersist, DeletePersist, Clone, and Union will use its Clone method to perform deep copies.
type DumpListNode ¶
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 ¶
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 or adapts all methods to the embedded table. The following methods are pointless without a payload:
- Lookup (use Contains)
- Get (use Exists)
- GetAndDelete
- GetAndDeletePersist
- Update
- UpdatePersist
Example (Concurrent) ¶
ExampleLite_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=ExampleLite_concurrent`) to verify that concurrent access is safe and free of data races.
This example demonstrates how multiple goroutines 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.
package main
import (
"sync"
"sync/atomic"
"github.com/admpub/bart"
)
var (
liteAtomicPtr atomic.Pointer[bart.Lite]
liteMutex sync.Mutex
)
// ExampleLite_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=ExampleLite_concurrent`)
// to verify that concurrent access is safe and free of data races.
//
// This example demonstrates how multiple goroutines 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.
func main() {
baseTbl := new(bart.Lite)
liteAtomicPtr.Store(baseTbl)
wg := sync.WaitGroup{}
wg.Add(1)
go func() {
defer wg.Done()
for range 1_000_000 {
for _, ip := range exampleIPs {
_ = liteAtomicPtr.Load().Contains(ip)
}
}
}()
wg.Add(1)
go func() {
defer wg.Done()
for range 10_000 {
liteMutex.Lock()
tbl := liteAtomicPtr.Load()
// batch of inserts
for _, pfx := range examplePrefixes {
tbl = tbl.InsertPersist(pfx)
}
liteAtomicPtr.Store(tbl)
liteMutex.Unlock()
}
}()
wg.Add(1)
go func() {
defer wg.Done()
for range 10_000 {
liteMutex.Lock()
tbl := liteAtomicPtr.Load()
// batch of deletes
for _, pfx := range examplePrefixes {
tbl = tbl.DeletePersist(pfx)
}
liteAtomicPtr.Store(tbl)
liteMutex.Unlock()
}
}()
wg.Wait()
}
Example (Contains) ¶
package main
import (
"fmt"
"net/netip"
"github.com/admpub/bart"
)
var (
mpa = netip.MustParseAddr
mpp = netip.MustParsePrefix
)
var examplePrefixes = []netip.Prefix{
mpp("192.168.0.0/16"),
mpp("192.168.1.0/24"),
mpp("2001:7c0:3100::/40"),
mpp("2001:7c0:3100:1::/64"),
mpp("fc00::/7"),
}
// some example IP addresses for black/whitelist containment
var exampleIPs = []netip.Addr{
mpa("192.168.1.100"),
mpa("192.168.2.1"),
mpa("2001:7c0:3100:1::1"),
mpa("2001:7c0:3100:2::1"),
mpa("fc00::1"),
mpa("172.16.0.1"),
mpa("2003:dead:beef::1"),
}
func main() {
lite := new(bart.Lite)
for _, pfx := range examplePrefixes {
lite.Insert(pfx)
}
for _, ip := range exampleIPs {
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 ¶
DeletePersist is an adapter for the underlying table.
func (*Lite) Exists ¶
Exists returns true if the prefix exists in the table. It's an adapter to Table.Get.
func (*Lite) InsertPersist ¶
InsertPersist is an adapter for the underlying table.
func (*Lite) UnionPersist ¶ added in v0.0.2
UnionPersist is an adapter for the underlying table.
type Table ¶
type Table[V any] struct { // contains filtered or unexported fields }
Table represents a thread-safe IPv4 and IPv6 routing table with payload V.
The zero value is ready to use.
The Table is safe for concurrent reads, but concurrent reads and writes must be externally synchronized. Mutation via Insert/Delete requires locks, or alternatively, use ...Persist methods which return a modified copy without altering the original table (copy-on-write).
A Table must not be copied by value; always pass by pointer.
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.
This example demonstrates how multiple goroutines 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.
package main
import (
"sync"
"sync/atomic"
"github.com/admpub/bart"
)
// testVal is a simple sample value type.
// We use *testVal as the generic payload 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}
}
var (
tblAtomicPtr atomic.Pointer[bart.Table[*testVal]]
tblMutex sync.Mutex
)
// #######################################
// 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.
//
// This example demonstrates how multiple goroutines 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.
func main() {
baseTbl := new(bart.Table[*testVal])
tblAtomicPtr.Store(baseTbl)
wg := sync.WaitGroup{}
wg.Add(1)
go func() {
defer wg.Done()
for range 10_000_000 {
for _, ip := range exampleIPs {
_, _ = tblAtomicPtr.Load().Lookup(ip)
}
}
}()
wg.Add(1)
go func() {
defer wg.Done()
for range 10_000 {
tblMutex.Lock()
tbl := tblAtomicPtr.Load()
// batch of inserts
for _, pfx := range examplePrefixes {
tbl = tbl.InsertPersist(pfx, &testVal{data: 0})
}
tblAtomicPtr.Store(tbl)
tblMutex.Unlock()
}
}()
wg.Add(1)
go func() {
defer wg.Done()
for range 10_000 {
tblMutex.Lock()
tbl := tblAtomicPtr.Load()
// batch of deletes
for _, pfx := range examplePrefixes {
tbl = tbl.DeletePersist(pfx)
}
tblAtomicPtr.Store(tbl)
tblMutex.Unlock()
}
}()
wg.Wait()
}
func (*Table[V]) All ¶
All returns an iterator over all prefix–value pairs in the table.
The entries from both IPv4 and IPv6 subtries are yielded using an internal recursive traversal. The iteration order is unspecified and may vary between calls; for a stable order, use AllSorted.
You can use All directly in a for-range loop without providing a yield function. The Go compiler automatically synthesizes the yield callback for you:
for prefix, value := range t.All() {
fmt.Println(prefix, value)
}
Under the hood, the loop body is passed as a yield function to the iterator. If you break or return from the loop, iteration stops early as expected.
func (*Table[V]) AllSorted ¶
AllSorted returns an iterator over all prefix–value pairs in the table, ordered in canonical CIDR prefix sort order.
This can be used directly with a for-range loop; the Go compiler provides the yield function implicitly.
for prefix, value := range t.AllSorted() {
fmt.Println(prefix, value)
}
The traversal is stable and predictable across calls. Iteration stops early if you break out of the loop.
func (*Table[V]) AllSorted4 ¶
AllSorted4 is like Table.AllSorted but only for the v4 routing table.
Example (Rangeoverfunc) ¶
package main
import (
"fmt"
"net/netip"
"github.com/admpub/bart"
)
var (
mpa = netip.MustParseAddr
mpp = netip.MustParsePrefix
)
var input = []struct {
cidr netip.Prefix
nextHop netip.Addr
}{
{mpp("fe80::/10"), mpa("::1%eth0")},
{mpp("172.16.0.0/12"), mpa("8.8.8.8")},
{mpp("10.0.0.0/24"), mpa("8.8.8.8")},
{mpp("::1/128"), mpa("::1%lo")},
{mpp("192.168.0.0/16"), mpa("9.9.9.9")},
{mpp("10.0.0.0/8"), mpa("9.9.9.9")},
{mpp("::/0"), mpa("2001:db8::1")},
{mpp("10.0.1.0/24"), mpa("10.0.0.0")},
{mpp("169.254.0.0/16"), mpa("10.0.0.0")},
{mpp("2000::/3"), mpa("2000::")},
{mpp("2001:db8::/32"), mpa("2001:db8::1")},
{mpp("127.0.0.0/8"), mpa("127.0.0.1")},
{mpp("127.0.0.1/32"), mpa("127.0.0.1")},
{mpp("192.168.1.0/24"), mpa("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 ¶
AllSorted6 is like Table.AllSorted but only for the v6 routing table.
func (*Table[V]) Clone ¶
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 ¶
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 ¶
DeletePersist is similar to Delete but does not modify the receiver.
It performs a copy-on-write delete operation, cloning all nodes touched during deletion and returning a new Table reflecting the change.
If the payload type V contains pointers or requires deep copying, it must implement the bart.Cloner interface for correct cloning.
Due to cloning overhead, DeletePersist is significantly slower than Delete, typically taking μsec instead of nsec.
func (*Table[V]) DumpList4 ¶
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 ¶
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 ¶
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 ¶
GetAndDeletePersist is similar to GetAndDelete but does not modify the receiver.
It performs a copy-on-write delete operation, cloning all nodes touched during deletion and returning a new Table reflecting the change.
If the payload type V contains pointers or requires deep copying, it must implement the bart.Cloner interface for correct cloning.
Due to cloning overhead, GetAndDeletePersist is significantly slower than GetAndDelete, typically taking μsec instead of 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 ¶
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 type V contains pointers or needs deep copying, it must implement the bart.Cloner interface to support correct cloning.
This is orders of magnitude slower than Insert, typically taking μsec instead of nsec.
The bulk table load could be done with Table.Insert and then you can use InsertPersist, Table.UpdatePersist and Table.DeletePersist for lock-free lookups.
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/admpub/bart"
)
var (
mpa = netip.MustParseAddr
mpp = netip.MustParsePrefix
)
var input = []struct {
cidr netip.Prefix
nextHop netip.Addr
}{
{mpp("fe80::/10"), mpa("::1%eth0")},
{mpp("172.16.0.0/12"), mpa("8.8.8.8")},
{mpp("10.0.0.0/24"), mpa("8.8.8.8")},
{mpp("::1/128"), mpa("::1%lo")},
{mpp("192.168.0.0/16"), mpa("9.9.9.9")},
{mpp("10.0.0.0/8"), mpa("9.9.9.9")},
{mpp("::/0"), mpa("2001:db8::1")},
{mpp("10.0.1.0/24"), mpa("10.0.0.0")},
{mpp("169.254.0.0/16"), mpa("10.0.0.0")},
{mpp("2000::/3"), mpa("2000::")},
{mpp("2001:db8::/32"), mpa("2001:db8::1")},
{mpp("127.0.0.0/8"), mpa("127.0.0.1")},
{mpp("127.0.0.1/32"), mpa("127.0.0.1")},
{mpp("192.168.1.0/24"), mpa("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 := mpa("42.0.0.0")
value, ok := rtbl.Lookup(ip)
fmt.Printf("Lookup: %-20v next-hop: %11v, ok: %v\n", ip, value, ok)
ip = mpa("10.0.1.17")
value, ok = rtbl.Lookup(ip)
fmt.Printf("Lookup: %-20v next-hop: %11v, ok: %v\n", ip, value, ok)
ip = mpa("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 ¶
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 ¶
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 ¶
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 ¶
MarshalText implements the encoding.TextMarshaler interface, just a wrapper for Table.Fprint.
func (*Table[V]) Overlaps ¶
Overlaps reports whether any route in the receiver table overlaps with a route in the other table, in either direction.
The overlap check is bidirectional: it returns true if any IP prefix in the receiver is covered by the other table, or vice versa. This includes partial overlaps, exact matches, and supernet/subnet relationships.
Both IPv4 and IPv6 route trees are compared independently. If either tree has overlapping routes, the function returns true.
This is useful for conflict detection, policy enforcement, or validating mutually exclusive routing domains.
func (*Table[V]) Overlaps4 ¶
Overlaps4 is like Table.Overlaps but for the v4 routing table only.
func (*Table[V]) Overlaps6 ¶
Overlaps6 is like Table.Overlaps but for the v6 routing table only.
func (*Table[V]) OverlapsPrefix ¶
OverlapsPrefix reports whether any route in the table overlaps with the given pfx or vice versa.
The check is bidirectional: it returns true if the input prefix is covered by an existing route, or if any stored route is itself contained within the input prefix.
Internally, the function normalizes the prefix and descends the relevant trie branch, using stride-based logic to identify overlap without performing a full lookup.
This is useful for containment tests, route validation, or policy checks using prefix semantics without retrieving exact matches.
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 ¶
Subnets returns an iterator over all prefix–value pairs in the routing table that are fully contained within the given prefix pfx.
Entries are returned in CIDR sort order.
Example:
for sub, val := range table.Subnets(netip.MustParsePrefix("10.0.0.0/8")) {
fmt.Println("Covered:", sub, "->", val)
}
Example (Rangeoverfunc) ¶
package main
import (
"fmt"
"net/netip"
"github.com/admpub/bart"
)
var (
mpa = netip.MustParseAddr
mpp = netip.MustParsePrefix
)
var input = []struct {
cidr netip.Prefix
nextHop netip.Addr
}{
{mpp("fe80::/10"), mpa("::1%eth0")},
{mpp("172.16.0.0/12"), mpa("8.8.8.8")},
{mpp("10.0.0.0/24"), mpa("8.8.8.8")},
{mpp("::1/128"), mpa("::1%lo")},
{mpp("192.168.0.0/16"), mpa("9.9.9.9")},
{mpp("10.0.0.0/8"), mpa("9.9.9.9")},
{mpp("::/0"), mpa("2001:db8::1")},
{mpp("10.0.1.0/24"), mpa("10.0.0.0")},
{mpp("169.254.0.0/16"), mpa("10.0.0.0")},
{mpp("2000::/3"), mpa("2000::")},
{mpp("2001:db8::/32"), mpa("2001:db8::1")},
{mpp("127.0.0.0/8"), mpa("127.0.0.1")},
{mpp("127.0.0.1/32"), mpa("127.0.0.1")},
{mpp("192.168.1.0/24"), mpa("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 ¶
Supernets returns an iterator over all supernet routes that cover the given prefix pfx.
The traversal searches both exact-length and shorter (less specific) prefixes that overlap or include pfx. Starting from the most specific position in the trie, it walks upward through parent nodes and yields any matching entries found at each level.
The iteration order is reverse-CIDR: from longest prefix match (LPM) towards least-specific routes.
The search is protocol-specific (IPv4 or IPv6) and stops immediately if the yield function returns false. If pfx is invalid, the function silently returns.
This can be used to enumerate all covering supernet routes in routing-based policy engines, diagnostics tools, or fallback resolution logic.
Example:
for supernet, val := range table.Supernets(netip.MustParsePrefix("192.0.2.128/25")) {
fmt.Println("Matched covering route:", supernet, "->", val)
}
Example (Rangeoverfunc) ¶
package main
import (
"fmt"
"net/netip"
"github.com/admpub/bart"
)
var (
mpa = netip.MustParseAddr
mpp = netip.MustParsePrefix
)
var input = []struct {
cidr netip.Prefix
nextHop netip.Addr
}{
{mpp("fe80::/10"), mpa("::1%eth0")},
{mpp("172.16.0.0/12"), mpa("8.8.8.8")},
{mpp("10.0.0.0/24"), mpa("8.8.8.8")},
{mpp("::1/128"), mpa("::1%lo")},
{mpp("192.168.0.0/16"), mpa("9.9.9.9")},
{mpp("10.0.0.0/8"), mpa("9.9.9.9")},
{mpp("::/0"), mpa("2001:db8::1")},
{mpp("10.0.1.0/24"), mpa("10.0.0.0")},
{mpp("169.254.0.0/16"), mpa("10.0.0.0")},
{mpp("2000::/3"), mpa("2000::")},
{mpp("2001:db8::/32"), mpa("2001:db8::1")},
{mpp("127.0.0.0/8"), mpa("127.0.0.1")},
{mpp("127.0.0.1/32"), mpa("127.0.0.1")},
{mpp("192.168.1.0/24"), mpa("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 ¶
Union merges another routing table into the receiver table, modifying it in-place.
All prefixes and values from the other table (o) are inserted into the receiver. If a duplicate prefix exists in both tables, the value from o replaces the existing entry. This duplicate is shallow-copied by default, but if the value type V implements the Cloner interface, the value is deeply cloned before insertion. See also Table.Clone.
func (*Table[V]) UnionPersist ¶ added in v0.0.2
UnionPersist is similar to [Union] but the receiver isn't modified.
All nodes touched during union are cloned and a new Table is returned.
func (*Table[V]) Update ¶
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 ¶
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 does not modify the receiver.
It performs a copy-on-write update, cloning all nodes touched during the update, and returns a new Table instance reflecting the update. Untouched nodes remain shared between the original and returned Tables.
If the payload type V contains pointers or needs deep copying, it must implement the bart.Cloner interface to support correct cloning.
Due to cloning overhead, UpdatePersist is significantly slower than Update, typically taking μsec instead of nsec.
Source Files
¶
Directories
¶
| Path | Synopsis |
|---|---|
|
internal
|
|
|
allot
Package allot provides precalculated bitsets that map baseIndex values to all longer (more specific) prefixes covered within the same stride.
|
Package allot provides precalculated bitsets that map baseIndex values to all longer (more specific) prefixes covered within the same stride. |
|
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 provides a compact and efficient implementation of a fixed-length bitset for the range [0..255].
|
Package bitset provides a compact and efficient implementation of a fixed-length bitset for the range [0..255]. |
|
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 provides a compact and efficient sparse array implementation for addressable key ranges from [0..255].
|
Package sparse provides a compact and efficient sparse array implementation for addressable key ranges from [0..255]. |