README
¶
package bart
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 the baseIndex function from the ART algorithm to build the complete-binary-tree (CBT) of prefixes for each stride.
The CBT is implemented as a bit-vector, backtracking is just a matter of fast cache friendly bitmask operations.
The Table 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 comparable or even better lookup times for longest prefix match.
The algorithm is also excellent for determining whether two tables contain overlapping IP addresses.
A Lite version is also included, this is ideal for simple IP access-control-lists, a.k.a. longest-prefix matches with plain true/false results.
For all other tasks the much more powerful Table must be used.
Example
func ExampleLite_Contains() {
lite := new(bart.Lite)
// Insert some prefixes
prefixes := []string{
"192.168.0.0/16", // corporate
"192.168.1.0/24", // department
"2001:7c0:3100::/40", // corporate
"2001:7c0:3100:1::/64", // department
"fc00::/7", // unique local
}
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, department
"192.168.2.1", // must match, corporate
"2001:7c0:3100:1::1", // must match, department
"2001:7c0:3100:2::1", // must match, corporate
"fc00::1", // must match, unique local
//
"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
Release v0.18 requires at least go1.23 and we use the iter.Seq2[netip.Prefix, V] types for iterators.
The lock-free versions of insert, update and delete are added, but still experimentell.
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, see Table.Clone.
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]
type Lite struct {
// Has unexported fields.
}
// Lite is the little sister of Table. Lite is ideal for simple IP
// access-control-lists, a.k.a. longest-prefix matches with plain
// true/false results.
//
// For all other tasks, the much more powerful Table must be used.
func (l *Lite) Insert(pfx netip.Prefix)
func (l *Lite) Delete(pfx netip.Prefix)
func (l *Lite) Contains(ip netip.Addr) bool
benchmarks
Please see the extensive benchmarks comparing bart with other IP routing table implementations.
Just a teaser, Contains and Lookups against the full Internet routing table with random IP address probes:
goos: linux
goarch: amd64
pkg: github.com/gaissmai/bart
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
BenchmarkFullMatchV4/Contains 55906228 21.39 ns/op 0 B/op 0 allocs/op
BenchmarkFullMatchV6/Contains 100000000 11.38 ns/op 0 B/op 0 allocs/op
BenchmarkFullMissV4/Contains 52927538 22.69 ns/op 0 B/op 0 allocs/op
BenchmarkFullMissV6/Contains 250386540 4.883 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/gaissmai/bart 11.291s
goos: linux
goarch: amd64
pkg: github.com/gaissmai/bart
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
BenchmarkFullMatchV4/Lookup 53578766 21.77 ns/op 0 B/op 0 allocs/op
BenchmarkFullMatchV6/Lookup 57054618 21.07 ns/op 0 B/op 0 allocs/op
BenchmarkFullMissV4/Lookup 48289306 25.60 ns/op 0 B/op 0 allocs/op
BenchmarkFullMissV6/Lookup 142917571 8.387 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/gaissmai/bart 10.455s
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 the _baseIndex_ function from the ART algorithm to build the complete-binary-tree (CBT) of prefixes for each stride.
The CBT is implemented as a bit-vector, backtracking is just a matter of fast cache friendly bitmask operations.
The routing table 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 similar lookup times for the longest prefix match.
Index ¶
- type Cloner
- type DumpListNode
- type 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) (lpm 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, 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 {
// contains filtered or unexported fields
}
Lite is the little sister of Table. Lite is ideal for simple IP access-control-lists, a.k.a. longest-prefix matches with plain true/false results.
For all other tasks the much more powerful Table must be used.
func (*Lite) Contains ¶ added in v0.18.1
Contains performs a longest-prefix match for the IP address and returns true if any route matches, otherwise false.
Example ¶
package main
import (
"fmt"
"net/netip"
"github.com/gaissmai/bart"
)
func main() {
lite := new(bart.Lite)
// Insert some prefixes
prefixes := []string{
"192.168.0.0/16", // corporate
"192.168.1.0/24", // department
"2001:7c0:3100::/40", // corporate
"2001:7c0:3100:1::/64", // department
"fc00::/7", // unique local
}
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, department
"192.168.2.1", // must match, corporate
"2001:7c0:3100:1::1", // must match, department
"2001:7c0:3100:2::1", // must match, corporate
"fc00::1", // must match, unique local
//
"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
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, see Table.Clone.
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 Table2 in natural CIDR sort order.
func (*Table[V]) AllSorted4 ¶ added in v0.12.6
AllSorted4, 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, 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 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
|
|
|
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. |
|
lpmbt
package lpmbt contains the backtracking lookup table for longest-prefix-match.
|
package lpmbt contains the backtracking lookup table for longest-prefix-match. |
|
sparse
package sparse implements a generic sparse array with popcount compression.
|
package sparse implements a generic sparse array with popcount compression. |