The Balanced Routing Table is an adaptation of D. Knuth's ART algorithm combined with popcount level compression and backtracking. It is somewhat slower than ART, but requires considerably less memory.
License: MIT License
When subnetwork is deleted from table lookup/get still reports individual IPs as present.
Maybe I misunderstand how to use this module correctly, below is an example test:
package main
import (
"net/netip"
"testing"
"github.com/gaissmai/bart"
"github.com/stretchr/testify/assert"
)
func mustParsePrefix(s string) netip.Prefix {
pfx, err := netip.ParsePrefix(s)
if err != nil {
panic(err)
}
return pfx
}
func mustParseAddr(s string) netip.Addr {
addr, err := netip.ParseAddr(s)
if err != nil {
panic(err)
}
return addr
}
func TestBART(t *testing.T) {
var ok bool
tbl := new(bart.Table[struct{}])
{
// 192.168.40.1 - 192.168.43.254
tbl.Insert(mustParsePrefix("192.168.42.1/22"), struct{}{})
_, _, ok = tbl.Lookup(mustParseAddr("192.168.40.1"))
assert.True(t, ok)
_, _, ok = tbl.Lookup(mustParseAddr("192.168.43.254"))
assert.True(t, ok)
_, _, ok = tbl.Lookup(mustParseAddr("192.168.42.242"))
assert.True(t, ok)
_, _, ok = tbl.Lookup(mustParseAddr("10.0.42.42"))
assert.False(t, ok)
}
{
tbl.Delete(mustParsePrefix("192.168.42.42/32"))
_, _, ok = tbl.Lookup(mustParseAddr("192.168.40.1"))
assert.True(t, ok)
_, _, ok = tbl.Lookup(mustParseAddr("192.168.43.254"))
assert.True(t, ok)
_, _, ok = tbl.Lookup(mustParseAddr("192.168.42.42"))
assert.False(t, ok)
_, _, ok = tbl.Lookup(mustParseAddr("10.0.42.42"))
assert.False(t, ok)
}
{
// 192.168.42.1 - 192.168.42.254
tbl.Delete(mustParsePrefix("192.168.42.1/24"))
_, _, ok = tbl.Lookup(mustParseAddr("192.168.40.1"))
assert.True(t, ok)
_, _, ok = tbl.Lookup(mustParseAddr("192.168.43.254"))
assert.True(t, ok)
_, _, ok = tbl.Lookup(mustParseAddr("192.168.42.242"))
assert.False(t, ok)
_, _, ok = tbl.Lookup(mustParseAddr("10.0.42.42"))
assert.False(t, ok)
}
}
(*Table).Union seems to result in shared memory between the receiving and other (*Table).
This results in unexpected side effects especially incases where some tables are computed once and then reused for the lifetime of the process. These tables end up getting mutated when unioned with other shorter lived tables.
I would have expected to not have any memory aliasing between the (*Table) apart from the values being shallow copied as described in the docs which doesn't matter for my use case as I am using Table[struct{}]
If one changes the WalkXXX() signatures to
func (t *Table[V]) Walk(cb func(pfx netip.Prefix, val V) bool)
func (t *Table[V]) Walk4(cb func(pfx netip.Prefix, val V) bool)
func (t *Table[V]) Walk6(cb func(pfx netip.Prefix, val V) bool)they will become compatible with rangefunc experiment, and if the experiment is enabled (but likely a default one day), syntactic niceties like this become possible:
for pfx, val := range t.Walk {
...
}What do you think?
I am thinking about these new functions:
// Find exact match to pfx, or insert pfx.
// Returns pointer to value, and whether pfx was inserted.
func (t *Table[V]) FetchOrInsert(pfx netip.Prefix) (*V, bool) {...}This will allow to perform modifications to existing values. Insert() can then be implemented like
func (t *Table[V]) Insert(pfx netip.Prefix, val V) {
vp, _ := t.FetchOrInsert(pfx)
*vp = val
}// Find like Lookup but by prefix
// Find does a route lookup for prefix and returns the longest prefix,
// pointer to the associated value and true for success, or false otherwise if
// no route matched.
func (t *Table[V]) Find(pfx netip.Prefix) (lpm netip.Prefix, pv *V, ok bool) {...}
// FindAll Slice of all matching prefixes and pointers to their values, longest first
func (t *Table[V]) FindAll(pfx netip.Prefix) []struct { pfx netip.Prefix, pv *V } {...}I have a ready implementation for fetchOrInsert() but not for the others.
The Table struct has a sync.Once, which when tested under sufficient load shows up in CPU profiles.
As the implementation isn't really thread safe anyways, can this be changed to a bool instead?
// Table is an IPv4 and IPv6 routing table with payload V.
@@ -15,16 +14,18 @@ type Table[V any] struct {
rootV6 *node[V]
// simple API, no constructor needed
- initOnce sync.Once
+ initOnce bool // set to true after first init
}
// init once, so no constructor is needed.
func (t *Table[V]) init() {
- t.initOnce.Do(func() {
- // BitSets have to be initialized.
- t.rootV4 = newNode[V]()
- t.rootV6 = newNode[V]()
- })
+ if t.initOnce {
+ return
+ }
+ // BitSets have to be initialized.
+ t.rootV4 = newNode[V]()
+ t.rootV6 = newNode[V]()
+ t.initOnce = true
}
// rootNodeByVersion, select root node for ip version.
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.