Help us shape the future of Go! Take the 2026 Go Developer Survey

bart

package module
v0.22.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 22, 2025 License: MIT Imports: 17 Imported by: 66

README

package bart

GitHub release (latest SemVer) Go Reference Mentioned in Awesome Go CI Coverage Status Go Report Card Stand With Ukraine

Overview

package bart provides a Balanced-Routing-Table (BART) for very fast IP to CIDR lookups and more.

BART is balanced in terms of memory usage and lookup time for the longest-prefix match.

BART is a multibit-trie with fixed stride length of 8 bits, using a fast mapping function (based on Donald E. Knuths ART algorithm) to map the 256 prefixes in each level node to form a complete-binary-tree.

This complete binary tree is implemented with popcount compressed sparse arrays together with path compression. This reduces storage consumption by almost two orders of magnitude in comparison to ART, with even better lookup times for the longest prefix match.

The BART algorithm is based on fixed size bit vectors and precalculated lookup tables. The lookup is performed entirely by fast, cache-friendly bitmask operations, which in modern CPUs are performed by advanced bit manipulation instruction sets (POPCNT, LZCNT, TZCNT, ...).

You should specify the CPU feature set when compiling, e.g. GOAMD64=v2 for maximum performance, see also https://go.dev/wiki/MinimumRequirements#architectures

The algorithm was specially developed so that it can always work with a fixed length of 256 bits. This means that the bitset fit very well in a cache line and that loops over the bitset in hot paths can be accelerated by loop unrolling, e.g.

func (b *BitSet256) popcnt() (cnt int) {
	cnt += bits.OnesCount64(b[0])
	cnt += bits.OnesCount64(b[1])
	cnt += bits.OnesCount64(b[2])
	cnt += bits.OnesCount64(b[3])
	return
}

A future Go version that supports SIMD intrinsics for the [4]uint64 vectors will probably allow the algorithm to be made even faster on suitable hardware.

The BART algorithm is also excellent for determining whether two tables contain overlapping IP addresses, just in a few nanoseconds.

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, low memory consumption, and optional internal data structure pooling 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

From release v0.18.x on, bart requires at least go1.23, the iter.Seq2[netip.Prefix, V] types for iterators are used.

  import "github.com/gaissmai/bart"
  
  type Table[V any] struct {
  	// Has unexported fields.
  }
    // Table 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.

  func (t *Table[V]) WithPool() *Table[V]

  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]

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) WithPool() *Lite

   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) Union(o *Lite)
   func (l *Lite) Clone() *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=v2 go test -run=xxx -bench=FullM/Contains -cpu=1
goos: linux
goarch: amd64
pkg: github.com/gaissmai/bart
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
BenchmarkFullMatch4/Contains         	83951143	        14.15 ns/op
BenchmarkFullMatch6/Contains         	62731105	        19.14 ns/op
BenchmarkFullMiss4/Contains          	74333276	        16.17 ns/op
BenchmarkFullMiss6/Contains          	142984221	         8.610 ns/op

$ GOAMD64=v2 go test -run=xxx -bench=FullM/Lookup -skip=/x -cpu=1
goos: linux
goarch: amd64
pkg: github.com/gaissmai/bart
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
BenchmarkFullMatch4/Lookup         	54066939	        22.09 ns/op
BenchmarkFullMatch6/Lookup         	27839944	        44.13 ns/op
BenchmarkFullMiss4/Lookup          	55061455	        21.80 ns/op
BenchmarkFullMiss6/Lookup          	100000000	        11.21 ns/op

Compatibility Guarantees

The package is currently released as a pre-v1 version, which gives the author the freedom to break backward compatibility to help improve the API as he learns which initial design decisions would need to be revisited to better support the use cases that the library solves for.

These occurrences are expected to be rare in frequency and the API is already quite stable.

CONTRIBUTION

Please open an issue for discussion before sending a pull request.

CREDIT

Standing on the shoulders of giants.

Credits for many inspirations go to

  • the clever guys at tailscale,
  • to Daniel Lemire for his inspiring blog,
  • to Donald E. Knuth for the ART routing algorithm and
  • to Yoichi Hariguchi who deciphered it for us mere mortals

And last but not least to the Go team who do a wonderful job!

LICENSE

MIT

Documentation

Overview

Package bart provides a 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

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Cloner added in v0.12.1 

type Cloner[V any] interface {
	Clone() V
}

Cloner is an interface, if implemented by payload of type V the values are deeply copied during Table.UpdatePersist, Table.DeletePersist, Table.Clone and Table.Union.

type DumpListNode added in v0.1.6 

type DumpListNode[V any] struct {
	CIDR    netip.Prefix      `json:"cidr"`
	Value   V                 `json:"value"`
	Subnets []DumpListNode[V] `json:"subnets,omitempty"`
}

DumpListNode contains CIDR, Value and Subnets, representing the trie in a sorted, recursive representation, especially useful for serialization.

type Lite added in v0.18.1 

type Lite struct {
	Table[struct{}]
}

Lite is just a convenience wrapper for Table, instantiated with an empty struct as payload. Lite is ideal for simple IP ACLs (access-control-lists) with plain true/false results without a payload.

Lite delegates 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. 

package main

import (
	"net/netip"
	"sync"
	"sync/atomic"

	"github.com/gaissmai/bart"
)

// SyncLite demonstrates how to wrap a [bart.Lite] for safe concurrent access in Go.
//
// This example struct allows multiple goroutines to perform lock-free, concurrent reads
// via an atomic pointer, while synchronizing writers with a mutex to ensure exclusive access.
// This concurrency pattern is useful when reads are frequent and writes are rare
// or take a long time in comparison to reads,
// providing high performance for concurrent workloads.
type SyncLite struct {
	// Atomic pointer to the current table version.
	// Enables lock-free, concurrent reads by multiple goroutines.
	atomic.Pointer[bart.Lite]

	// Mutex for synchronizing concurrent writers.
	// Writers must acquire the lock before modifying the table.
	// No CAS is used for writers; only one writer at a time is allowed.
	sync.Mutex
}

// NewSyncLite creates and initializes a new SyncLite.
// The underlying table is initialized and stored atomically.
func NewSyncLite() *SyncLite {
	lf := new(SyncLite)
	lf.Store(new(bart.Lite))
	return lf
}

// WithPool replaces the current table version with a new version with a sync.Pool for trie nodes.
//
// WithPool acquires an exclusive writer lock, ensuring no other writer can modify the value concurrently.
// It then retrieves the current table version, creates a new version using the table's WithPool method,
// and atomically publishes this new version for concurrent readers.
//
// This method is safe for concurrent use by multiple goroutines.
func (lf *SyncLite) WithPool() *SyncLite {
	lf.Lock() // acquire writer lock to exclude other writers
	defer lf.Unlock()

	oldPtr := lf.Load()         // get current table version
	newPtr := oldPtr.WithPool() // create new persistent table version

	lf.Store(newPtr) // atomically publish new version for readers
	return lf
}

// Contains is a sync adapter for [bart.Lite.Contains].
func (lf *SyncLite) Contains(ip netip.Addr) bool {
	return lf.Load().Contains(ip)
}

// Insert is a sync adapter for [bart.Lite.Insert].
// This method acquires a writer lock to ensure exclusive access for writers.
// It creates a new persistent table version and atomically updates the pointer.
// Concurrent readers remain lock-free and always see a consistent table.
func (lf *SyncLite) Insert(pfx netip.Prefix) {
	lf.Lock() // acquire writer lock to exclude other writers
	defer lf.Unlock()

	oldPtr := lf.Load()                 // get current table version
	newPtr := oldPtr.InsertPersist(pfx) // create new persistent table version

	lf.Store(newPtr) // atomically publish new version for readers
}

// Delete is a sync adapter for [bart.Lite.Delete].
func (lf *SyncLite) Delete(pfx netip.Prefix) {
	lf.Lock()
	defer lf.Unlock()

	oldPtr := lf.Load()
	newPtr := oldPtr.DeletePersist(pfx)

	lf.Store(newPtr)
}

// 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.
func main() {
	wg := sync.WaitGroup{}

	syncLite := NewSyncLite()
	syncLite.WithPool()

	wg.Add(1)
	go func() {
		defer wg.Done()
		for range 1_000_000 {
			for _, s := range exampleIPs {
				ip := netip.MustParseAddr(s)
				_ = syncLite.Contains(ip)
			}
		}
	}()

	wg.Add(1)
	go func() {
		defer wg.Done()
		for range 10_000 {
			for _, s := range examplePrefixes {
				pfx := netip.MustParsePrefix(s)
				syncLite.Insert(pfx)
			}
		}
	}()

	wg.Add(1)
	go func() {
		defer wg.Done()
		for range 10_000 {
			for _, s := range examplePrefixes {
				pfx := netip.MustParsePrefix(s)
				syncLite.Delete(pfx)
			}
		}
	}()

	wg.Wait()

}
Example (Contains) 
package main

import (
	"fmt"
	"net/netip"

	"github.com/gaissmai/bart"
)

var examplePrefixes = []string{
	"192.168.0.0/16",
	"192.168.1.0/24",
	"2001:7c0:3100::/40",
	"2001:7c0:3100:1::/64",
	"fc00::/7",
}

// some example IP addresses for black/whitelist containment
var exampleIPs = []string{
	"192.168.1.100",
	"192.168.2.1",
	"2001:7c0:3100:1::1",
	"2001:7c0:3100:2::1",
	"fc00::1",

	"172.16.0.1",
	"2003:dead:beef::1",
}

func main() {
	lite := new(bart.Lite)

	for _, s := range examplePrefixes {
		pfx := netip.MustParsePrefix(s)
		lite.Insert(pfx)
	}

	for _, s := range exampleIPs {
		ip := netip.MustParseAddr(s)
		ok := lite.Contains(ip)
		fmt.Printf("%-20s is contained: %t\n", ip, ok)
	}

}

Output:
192.168.1.100        is contained: true
192.168.2.1          is contained: true
2001:7c0:3100:1::1   is contained: true
2001:7c0:3100:2::1   is contained: true
fc00::1              is contained: true
172.16.0.1           is contained: false
2003:dead:beef::1    is contained: false

func (*Lite) Clone added in v0.20.0 

func (l *Lite) Clone() *Lite

Clone is an adapter for the underlying table.

func (*Lite) Contains added in v0.18.1 

func (l *Lite) Contains(ip netip.Addr) bool

Contains is a wrapper for the underlying table.

func (*Lite) Delete added in v0.18.1 

func (l *Lite) Delete(pfx netip.Prefix)

Delete is a wrapper for the underlying table.

func (*Lite) DeletePersist added in v0.20.0 

func (l *Lite) DeletePersist(pfx netip.Prefix) *Lite

DeletePersist is an adapter for the underlying table.

func (*Lite) Exists added in v0.20.0 

func (l *Lite) Exists(pfx netip.Prefix) bool

Exists returns true if the prefix exists in the table. It's an adapter to Table.Get.

func (*Lite) Insert added in v0.18.1 

func (l *Lite) Insert(pfx netip.Prefix)

Insert is an adapter for the underlying table.

func (*Lite) InsertPersist added in v0.20.0 

func (l *Lite) InsertPersist(pfx netip.Prefix) *Lite

InsertPersist is an adapter for the underlying table.

func (*Lite) Overlaps added in v0.20.0 

func (l *Lite) Overlaps(o *Lite) bool

Overlaps is an adapter for the underlying table.

func (*Lite) Overlaps4 added in v0.20.0 

func (l *Lite) Overlaps4(o *Lite) bool

Overlaps4 is an adapter for the underlying table.

func (*Lite) Overlaps6 added in v0.20.0 

func (l *Lite) Overlaps6(o *Lite) bool

Overlaps6 is an adapter for the underlying table.

func (*Lite) Union added in v0.20.0 

func (l *Lite) Union(o *Lite)

Union is an adapter for the underlying table.

func (*Lite) WithPool added in v0.22.0 

func (l *Lite) WithPool() *Lite

WithPool 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. 

package main

import (
	"net/netip"
	"sync"
	"sync/atomic"

	"github.com/gaissmai/bart"
)

// SyncTable demonstrates how to wrap a [bart.Table] for safe concurrent access in Go.
//
// This example struct allows multiple goroutines to perform lock-free, concurrent reads
// via an atomic pointer, while synchronizing writers with a mutex to ensure exclusive access.
// This concurrency pattern is useful when reads are frequent and writes are rare
// or take a long time in comparison to reads,
// providing high performance for concurrent workloads.
//
// If the payload V either contains a pointer or is a pointer,
// it must implement the [bart.Cloner] interface.
type SyncTable[V bart.Cloner[V]] struct {
	// Atomic pointer to the current table version.
	// Enables lock-free, concurrent reads by multiple goroutines.
	atomic.Pointer[bart.Table[V]]

	// Mutex for synchronizing concurrent writers.
	// Writers must acquire the lock before modifying the table.
	// No CAS is used for writers; only one writer at a time is allowed.
	sync.Mutex
}

// NewSyncTable creates and initializes a new SyncTable.
// The underlying table is initialized and stored atomically.
func NewSyncTable[V bart.Cloner[V]]() *SyncTable[V] {
	lf := new(SyncTable[V])
	lf.Store(new(bart.Table[V]))
	return lf
}

// WithPool replaces the current table version with a new version with a sync.Pool for trie nodes.
//
// WithPool acquires an exclusive writer lock, ensuring no other writer can modify the value concurrently.
// It then retrieves the current table version, creates a new version using the table's WithPool method,
// and atomically publishes this new version for concurrent readers.
//
// This method is safe for concurrent use by multiple goroutines.
func (lf *SyncTable[V]) WithPool() *SyncTable[V] {
	lf.Lock() // acquire writer lock to exclude other writers
	defer lf.Unlock()

	oldPtr := lf.Load()         // get current table version
	newPtr := oldPtr.WithPool() // create new persistent table version

	lf.Store(newPtr) // atomically publish new version for readers
	return lf
}

// Contains is a sync adapter for [bart.Table.Contains].
func (lf *SyncTable[V]) Contains(ip netip.Addr) bool {
	return lf.Load().Contains(ip)
}

// Lookup is a sync adapter for [bart.Table.Lookup].
func (lf *SyncTable[V]) Lookup(ip netip.Addr) (val V, ok bool) {
	return lf.Load().Lookup(ip)
}

// Insert is a sync adapter for [bart.Table.Insert].
// This method acquires a writer lock to ensure exclusive access for writers.
// It creates a new persistent table version and atomically updates the pointer.
// Concurrent readers remain lock-free and always see a consistent table.
func (lf *SyncTable[V]) Insert(pfx netip.Prefix, val V) {
	lf.Lock() // acquire writer lock to exclude other writers
	defer lf.Unlock()

	oldPtr := lf.Load()                      // get current table version
	newPtr := oldPtr.InsertPersist(pfx, val) // create new persistent table version

	lf.Store(newPtr) // atomically publish new version for readers
}

// Update is a sync adapter for [bart.Table.Update].
func (lf *SyncTable[V]) Update(pfx netip.Prefix, cb func(val V, ok bool) V) (newVal V) {
	lf.Lock()
	defer lf.Unlock()

	oldPtr := lf.Load()
	newPtr, val := oldPtr.UpdatePersist(pfx, cb)

	lf.Store(newPtr)
	return val
}

// Delete is a sync adapter for [bart.Table.Delete].
func (lf *SyncTable[V]) Delete(pfx netip.Prefix) {
	lf.Lock()
	defer lf.Unlock()

	oldPtr := lf.Load()
	newPtr := oldPtr.DeletePersist(pfx)

	lf.Store(newPtr)
}

// #######################################
// just a very stupid example of a payload
// #######################################

// testVal is a sample value type.
// We use *testVal as the generic type V, which is a pointer type,
// so it must implement Cloner[*testVal].
type testVal struct {
	data int
}

// Clone ensures deep copying for use with ...Persist.
func (v *testVal) Clone() *testVal {
	if v == nil {
		return nil
	}
	return &testVal{data: v.data}
}

// example callback for Update, just decrement data
var cb = func(p *testVal, ok bool) *testVal {
	if ok && p != nil {
		p.data--
		return p
	}
	return &testVal{data: -1}
}

// #######################################

// ExampleTable_concurrent demonstrates safe concurrent usage of bart.
// This example is intended to be run with the Go race detector enabled
// (use `go test -race -run=ExampleTable_concurrent`)
// to verify that concurrent access is safe and free of data races.
func main() {
	wg := sync.WaitGroup{}

	syncTbl := NewSyncTable[*testVal]()
	syncTbl.WithPool()

	wg.Add(1)
	go func() {
		defer wg.Done()
		for range 1_000_000 {
			for _, s := range exampleIPs {
				ip := netip.MustParseAddr(s)
				_, _ = syncTbl.Lookup(ip)
			}
		}
	}()

	wg.Add(1)
	go func() {
		defer wg.Done()
		for range 10_000 {
			for _, s := range examplePrefixes {
				pfx := netip.MustParsePrefix(s)
				syncTbl.Insert(pfx, &testVal{data: 0})
			}
		}
	}()

	wg.Add(1)
	go func() {
		defer wg.Done()
		for range 10_000 {
			for _, s := range examplePrefixes {
				pfx := netip.MustParsePrefix(s)
				syncTbl.Update(pfx, cb)
			}
		}
	}()

	wg.Add(1)
	go func() {
		defer wg.Done()
		for range 10_000 {
			for _, s := range examplePrefixes {
				pfx := netip.MustParsePrefix(s)
				syncTbl.Delete(pfx)
			}
		}
	}()

	wg.Wait()

}

func (*Table[V]) All added in v0.6.0 

func (t *Table[V]) All() iter.Seq2[netip.Prefix, V]

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]) All4 added in v0.6.0 

func (t *Table[V]) All4() iter.Seq2[netip.Prefix, V]

All4 is like Table.All but only for the v4 routing table.

func (*Table[V]) All6 added in v0.6.0 

func (t *Table[V]) All6() iter.Seq2[netip.Prefix, V]

All6 is like Table.All but only for the v6 routing table.

func (*Table[V]) AllSorted added in v0.11.0 

func (t *Table[V]) AllSorted() iter.Seq2[netip.Prefix, V]

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 added in v0.12.6 

func (t *Table[V]) AllSorted4() iter.Seq2[netip.Prefix, V]

AllSorted4 is like Table.AllSorted but only for the v4 routing table.

Example (Rangeoverfunc) 
package main

import (
	"fmt"
	"net/netip"

	"github.com/gaissmai/bart"
)

var (
	a = netip.MustParseAddr
	p = netip.MustParsePrefix
)

var input = []struct {
	cidr    netip.Prefix
	nextHop netip.Addr
}{
	{p("fe80::/10"), a("::1%eth0")},
	{p("172.16.0.0/12"), a("8.8.8.8")},
	{p("10.0.0.0/24"), a("8.8.8.8")},
	{p("::1/128"), a("::1%lo")},
	{p("192.168.0.0/16"), a("9.9.9.9")},
	{p("10.0.0.0/8"), a("9.9.9.9")},
	{p("::/0"), a("2001:db8::1")},
	{p("10.0.1.0/24"), a("10.0.0.0")},
	{p("169.254.0.0/16"), a("10.0.0.0")},
	{p("2000::/3"), a("2000::")},
	{p("2001:db8::/32"), a("2001:db8::1")},
	{p("127.0.0.0/8"), a("127.0.0.1")},
	{p("127.0.0.1/32"), a("127.0.0.1")},
	{p("192.168.1.0/24"), a("127.0.0.1")},
}

func main() {
	rtbl := new(bart.Table[netip.Addr])
	for _, item := range input {
		rtbl.Insert(item.cidr, item.nextHop)
	}

	for pfx, val := range rtbl.AllSorted4() {
		fmt.Printf("%v\t%v\n", pfx, val)
	}

}

Output:
10.0.0.0/8	9.9.9.9
10.0.0.0/24	8.8.8.8
10.0.1.0/24	10.0.0.0
127.0.0.0/8	127.0.0.1
127.0.0.1/32	127.0.0.1
169.254.0.0/16	10.0.0.0
172.16.0.0/12	8.8.8.8
192.168.0.0/16	9.9.9.9
192.168.1.0/24	127.0.0.1

func (*Table[V]) AllSorted6 added in v0.12.6 

func (t *Table[V]) AllSorted6() iter.Seq2[netip.Prefix, V]

AllSorted6 is like Table.AllSorted but only for the v6 routing table.

func (*Table[V]) Clone added in v0.4.0 

func (t *Table[V]) Clone() *Table[V]

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 

func (t *Table[V]) Contains(ip netip.Addr) bool

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]) Delete 

func (t *Table[V]) Delete(pfx netip.Prefix)

Delete removes pfx from the tree, pfx does not have to be present.

func (*Table[V]) DeletePersist added in v0.18.0 

func (t *Table[V]) DeletePersist(pfx netip.Prefix) *Table[V]

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 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 

func (t *Table[V]) Fprint(w io.Writer) error

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 

func (t *Table[V]) Get(pfx netip.Prefix) (val V, ok bool)

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 

func (t *Table[V]) GetAndDelete(pfx netip.Prefix) (val V, ok bool)

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 

func (t *Table[V]) GetAndDeletePersist(pfx netip.Prefix) (pt *Table[V], val V, ok bool)

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 

func (t *Table[V]) Insert(pfx netip.Prefix, val V)

Insert adds a pfx to the tree, with given val. If pfx is already present in the tree, its value is set to val.

func (*Table[V]) InsertPersist added in v0.18.0 

func (t *Table[V]) InsertPersist(pfx netip.Prefix, val V) *Table[V]

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 updates.

func (*Table[V]) Lookup 

func (t *Table[V]) Lookup(ip netip.Addr) (val V, ok bool)

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 

func (t *Table[V]) LookupPrefix(pfx netip.Prefix) (val V, ok bool)

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 

func (t *Table[V]) LookupPrefixLPM(pfx netip.Prefix) (lpmPfx netip.Prefix, val V, ok bool)

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 

func (t *Table[V]) MarshalJSON() ([]byte, error)

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 

func (t *Table[V]) MarshalText() ([]byte, error)

MarshalText implements the encoding.TextMarshaler interface, just a wrapper for Table.Fprint.

func (*Table[V]) Overlaps added in v0.2.0 

func (t *Table[V]) Overlaps(o *Table[V]) bool

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 added in v0.10.1 

func (t *Table[V]) Overlaps4(o *Table[V]) bool

Overlaps4 is like Table.Overlaps but for the v4 routing table only.

func (*Table[V]) Overlaps6 added in v0.10.1 

func (t *Table[V]) Overlaps6(o *Table[V]) bool

Overlaps6 is like Table.Overlaps but for the v6 routing table only.

func (*Table[V]) OverlapsPrefix added in v0.1.5 

func (t *Table[V]) OverlapsPrefix(pfx netip.Prefix) bool

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]) Size added in v0.8.0 

func (t *Table[V]) Size() int

Size returns the prefix count.

func (*Table[V]) Size4 added in v0.8.0 

func (t *Table[V]) Size4() int

Size4 returns the IPv4 prefix count.

func (*Table[V]) Size6 added in v0.8.0 

func (t *Table[V]) Size6() int

Size6 returns the IPv6 prefix count.

func (*Table[V]) String 

func (t *Table[V]) String() 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 

func (t *Table[V]) Subnets(pfx netip.Prefix) iter.Seq2[netip.Prefix, V]

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/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 

func (t *Table[V]) Supernets(pfx netip.Prefix) iter.Seq2[netip.Prefix, V]

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/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 

func (t *Table[V]) Union(o *Table[V])

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]) Update added in v0.5.0 

func (t *Table[V]) Update(pfx netip.Prefix, cb func(val V, ok bool) V) (newVal V)

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 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.

func (*Table[V]) WithPool added in v0.22.0 

func (t *Table[V]) WithPool() *Table[V]

WithPool initializes a multiPool for node reuse on the Table if not already set.

This method enables the Table to recycle internal, leaf, and fringe node instances, which reduces heap allocations and lowers garbage collection (GC) pressure, particularly in workloads with frequent insertions and deletions.

By pooling nodes, performance often improves for concurrent or high-throughput usage by avoiding repeated allocations and deallocations of node objects.

If the Table already has a non-nil multiPool, WithPool returns the Table unchanged. Otherwise, it creates and assigns a new multiPool managing separate pools for the different node types.

Returns the Table to allow method chaining.

Source Files

View all 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].

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.