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 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 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, ...).
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
}
The BART algorithm is also excellent for determining whether two tables contain overlapping IP addresses, just in a few nanoseconds.
A bart.Lite wrapper is 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. The lock-free versions of insert, update and delete are added, but still experimental.
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:
goos: linux
goarch: amd64
pkg: github.com/gaissmai/bart
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
BenchmarkFullMatch4/Contains 129756907 8.409 ns/op
BenchmarkFullMatch6/Contains 96855786 11.72 ns/op
BenchmarkFullMiss4/Contains 56269990 18.58 ns/op
BenchmarkFullMiss6/Contains 131779195 10.08 ns/op
goos: linux
goarch: amd64
pkg: github.com/gaissmai/bart
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
BenchmarkFullMatch4/Lookup 47039798 24.44 ns/op
BenchmarkFullMatch6/Lookup 81769753 13.61 ns/op
BenchmarkFullMiss4/Lookup 51986374 22.72 ns/op
BenchmarkFullMiss6/Lookup 100000000 11.47 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 ¶
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 ¶
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 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.
func (*Lite) DeletePersist ¶
DeletePersist is similar to Delete but the receiver isn't modified.
func (*Lite) Exists ¶
Exists returns true if the prefix exists in the table. It's an adapter to Table.Get.
func (*Lite) GetAndDelete
deprecated
func (l *Lite) GetAndDelete()
Deprecated: GetAndDelete is pointless without payload and panics.
func (*Lite) GetAndDeletePersist
deprecated
func (l *Lite) GetAndDeletePersist()
Deprecated: GetAndDeletePersist is pointless without payload and panics.
func (*Lite) InsertPersist ¶
InsertPersist is similar to Insert but the receiver isn't modified.
func (*Lite) Overlaps ¶
Overlaps reports whether any IP in the table matches a route in the other table or vice versa.
func (*Lite) Overlaps4 ¶
Overlaps4 reports whether any IPv4 in the table matches a route in the other table or vice versa.
func (*Lite) Overlaps6 ¶
Overlaps6 reports whether any IPv6 in the table matches a route in the other table or vice versa.
func (*Lite) UpdatePersist
deprecated
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.
func (*Table[V]) All ¶
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 ¶
AllSorted returns an iterator over key-value pairs from Table2 in natural CIDR sort order.
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 (
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 ¶
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 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 ¶
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 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 ¶
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/admpub/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 ¶
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 IP in the table is matched by a route in the other table or vice versa.
func (*Table[V]) Overlaps4 ¶
Overlaps4 reports whether any IPv4 in the table matches a route in the other table or vice versa.
func (*Table[V]) Overlaps6 ¶
Overlaps6 reports whether any IPv6 in the table matches a route in the other table or vice versa.
func (*Table[V]) OverlapsPrefix ¶
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 ¶
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/admpub/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 ¶
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/admpub/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 ¶
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 ¶
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 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. |