bart

package module
v0.26.0 Latest Latest
Warning

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

 Go to latest Published: Oct 19, 2025 License: MIT Imports: 13 Imported by: 41

README

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

package bart

The bart package provides some Balanced Routing Tables (BART) for fastest IP-to-CIDR lookups and related tasks such as:

  • ACL determine extremely fast whether an IP address matches any of millions of CIDR rules.
  • RIB handle very large routing tables with low memory overhead, while keeping lookups fast.
  • FIB high-speed lookups, achieve LPM in constant-time for packet forwarding in the datapath.

BART is designed for workloads where both speed and/or memory efficiency matter, making it a best fit for firewalls, routers, or any system that needs large-scale IP prefix matching.

Overview

BART is implemented as a multibit trie with a fixed stride of 8 bits, using a fast mapping function derived from Donald E. Knuth’s Allotment Routing Table (ART) algorithm, to map the possible prefixes at each level into a complete binary tree.

BART implements three different routing tables, each optimized for specific use cases:

  • bart.Lite
  • bart.Table
  • bart.Fast

For bart.Table this binary tree is represented with popcount‑compressed sparse arrays for level compression. Combined with a novel path and fringe compression, this design reduces memory consumption by nearly two orders of magnitude compared to classical ART.

For bart.Fast this binary tree is represented with fixed arrays without level compression (classical ART), but combined with the same novel path and fringe compression from BART. This design reduces memory consumption by more than an order of magnitude compared to classical ART and thus makes ART usable in the first place for large routing tables.

bart.Lite is a special form of bart.Table, but without a payload, and therefore has the lowest memory overhead while maintaining the same lookup times.

Getting Started

Example: simple ACL with bart.Lite
package main

import (
  "net/netip"

  "github.com/gaissmai/bart"
)

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

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

  // Add allowed networks
  allowList.Insert(p("192.168.0.0/16"))
  allowList.Insert(p("2001:db8::/32"))
  allowList.Insert(p("10.0.0.0/24"))

  // Test some IPs with Contains (longest-prefix match)
  testIPs := []netip.Addr{
    a("192.168.1.100"), // allowed (matches 192.168.0.0/16)
    a("2001:db8::1"),   // allowed (matches 2001:db8::/32)
    a("172.16.0.1"),    // denied (no match)
  }

  for _, ip := range testIPs {
    if allowList.Contains(ip) {
      fmt.Printf("✅ %s is allowed\n", ip)
    } else {
      fmt.Printf("❌ %s is denied\n", ip)
    }
  }

  // Exact-prefix checks with Get (not longest-prefix match)
  exactPrefixes := []netip.Prefix{
    p("192.168.0.0/16"),  // exists exactly
    p("192.168.1.0/24"),  // doesn't exist (would be covered by /16, but not stored exactly)
    p("10.0.0.0/24"),     // exists exactly
    p("10.0.0.0/16"),     // doesn't exist (only /24 is stored)
  }

  fmt.Println("\nExact-prefix checks:")
  for _, pfx := range exactPrefixes {
    if allowList.Get(pfx) {
      fmt.Printf("✅ Exact prefix %s exists in table\n", pfx)
    } else {
      fmt.Printf("❌ Exact prefix %s not found in table\n", pfx)
    }
  }
}

Comparison

Aspect Table Lite Fast
Per-level Speed ⚡ O(1) ⚡ O(1) 🚀 O(1), 50-100% faster
Overall Lookup O(trie_depth) O(trie_depth) O(trie_depth)
IPv4 Performance ~3 level traversals ~3 level traversals ~3 level traversals
IPv6 Performance ~6 level traversals ~6 level traversals ~6 level traversals
IPv6 vs IPv4 ~2× slower ~2× slower ~2× slower
Memory efficient very efficient inefficient

A more detailed description can be found in NODETYPES.md.

When to Use Each Type

🎯 bart.Table[V] - The Balanced Choice
  • Recommended for most routing table use cases
  • Near-optimal per-level performance with excellent memory efficiency
  • Perfect balance for both IPv4 and IPv6 routing tables (use it for RIB)
🪶 bart.Lite - The Minimalist
  • Specialized for prefix-only operations, no payload
  • Same per-level performance as bart.Table[V] but 35% less memory
  • Ideal for IPv4/IPv6 allowlists and set-based operations (use it for ACL)
🚀 bart.Fast[V] - The Performance Champion
  • 50-100% faster when memory constraints allow
  • Best choice for lookup-intensive applications (use it for FIB)

Bitset Efficiency

The BART algorithm is based on fixed-size bit vectors and precomputed lookup tables. Lookups are executed entirely with fast, cache-resident bitmask operations, which modern CPUs accelerate using specialized instructions such as POPCNT, LZCNT, and TZCNT.

For maximum performance, specify the CPU feature set when compiling. See the Go minimum requirements for details.

# On ARM64, Go auto-selects CPU instructions.
# Example for AMD64, choose v2/v3/v4 to match your CPU features.
GOAMD64=v3 go build

Critical loops over these fixed-size bitsets can be unrolled for additional speed, ensuring predictable memory access and efficient use of CPU pipelines.

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
}

Future Go versions with SIMD intrinsics for uint64 vectors may unlock additional speedups on compatible hardware.

Concurrency model

There are examples demonstrating how to use bart concurrently with multiple readers and writers. Readers can always access the table lock‑free. Writers synchronize with a mutex so that only one writer modifies the persistent table at a time, without relying on CAS, which can be problematic with multiple long‑running writers.

The combination of lock-free concurrency, fast lookup and update times and low memory consumption provides clear advantages for any routing daemon.

But as always, it depends on the specific use case.

See the concurrent tests for concrete examples of this pattern:

Additional Use Cases

Beyond high-performance prefix matching, BART also excels at detecting overlaps between two routing tables. In internal benchmarks the check runs in a few nanoseconds per query with zero heap allocations on a modern CPU.

API

BART has a rich API for CRUD, lookup, comparison, iteration, serialization and persistence.

Table and Fast expose the identical API, while Lite deviates in its methods from the common API when it comes to the payload, since Lite has no payload.

import "github.com/gaissmai/bart"

type Table[V any] struct {
  // Has unexported fields.
}

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

func (t *Table[V]) LookupPrefix(netip.Prefix) (V, bool)
func (t *Table[V]) LookupPrefixLPM(netip.Prefix) (netip.Prefix, V, bool)

func (t *Table[V]) Get(netip.Prefix) (V, bool)
func (t *Table[V]) Insert(netip.Prefix, V)
func (t *Table[V]) Delete(netip.Prefix)
func (t *Table[V]) Modify(netip.Prefix, cb func(V, bool) (V, bool))

func (t *Table[V]) InsertPersist(netip.Prefix, V) *Table[V]
func (t *Table[V]) DeletePersist(netip.Prefix) *Table[V]
func (t *Table[V]) ModifyPersist(netip.Prefix, cb func(V, bool) (V, bool)) *Table[V]

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

func (t *Table[V]) OverlapsPrefix(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]) Equal(o *Table[V]) bool

func (t *Table[V]) Subnets(netip.Prefix) iter.Seq2[netip.Prefix, V]
func (t *Table[V]) Supernets(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]) 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, Fast.Lookup against the Tier1 full Internet routing table with random IP address probes:

$ GOAMD64=v3 go test -run=xxx -bench=FullFastM/Lookup$ -cpu=1
goos: linux
goarch: amd64
pkg: github.com/gaissmai/bart
cpu: Intel(R) Core(TM) i5-8250U CPU @ 1.60GHz
BenchmarkFullFastMatch4/Lookup           124476082          9.63 ns/op
BenchmarkFullFastMatch6/Lookup           91032597          13.20 ns/op
BenchmarkFullFastMiss4/Lookup            134171480          8.93 ns/op
BenchmarkFullFastMiss6/Lookup            75634396          15.79 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 folks at Tailscale,
  • to Daniel Lemire for his inspiring blog,
  • to Donald E. Knuth for the Allotment Routing Table ART 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 high-performance Balanced Routing Tables (BART) for fastest IP-to-CIDR lookups on IPv4 and IPv6 addresses.

BART offers three table variants optimized for different use cases:

  • Lite: Memory-optimized with popcount-compressed sparse arrays
  • Table: Full-featured with popcount-compressed sparse arrays
  • Fast: Speed-optimized with fixed-size 256-element arrays

The implementation is based on Knuth's ART algorithm with novel optimizations for memory efficiency and lookup speed.

`Table` and `Lite` use popcount compression for memory efficiency, while `Fast` trades memory for maximum lookup speed with uncompressed arrays.

BART excels at efficient set operations on routing tables including Union, Overlaps, Equal, Subnets, and Supernets with optimal complexity, making it ideal for large-scale IP prefix matching in ACLs, RIBs, FIBs, firewalls, and routers.

All variants also support copy-on-write persistence.

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 that enables deep cloning of values of type V. If a value implements Cloner[V], Table methods such as InsertPersist, ModifyPersist, DeletePersist, UnionPersist, Union and Clone will use its Clone method to perform deep copies.

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

type Equaler[V any] interface {
	Equal(other V) bool
}

Equaler is a generic interface for types that can decide their own equality logic. It can be used to override the potentially expensive default comparison with reflect.DeepEqual.

type Fast added in v0.26.0 

type Fast[V any] struct {
	// contains filtered or unexported fields
}

Fast follows the ART design by Knuth in using fixed arrays at each level combined with the same path and fringe compression invented for BART.

As a result Fast sacrifices memory efficiency to achieve 50-100% higher speed.

The zero value is ready to use. A Fast table must not be copied by value; always pass by pointer.

The payload type MUST NOT be a zero-sized value (for example: struct{} or [0]byte). According to the Go specification: 

"Pointers to distinct zero-size variables may or may not be equal."

However, the ART algorithm requires that different prefixes, even with identical payload V, result in distinct value pointers. This is not guaranteed for zero-sized values; thus, zero-sized types as payload V results in undefined behavior.

Performance note: Do not pass IPv4-in-IPv6 addresses (e.g., ::ffff:192.0.2.1) as input. The methods do not perform automatic unmapping to avoid unnecessary overhead for the common case where native addresses are used. Users should unmap IPv4-in-IPv6 addresses to their native IPv4 form (e.g., 192.0.2.1) before calling these methods.

Example (Concurrent)

ExampleFast_concurrent demonstrates safe concurrent usage of bart.Fast. This example is intended to be run with the Go race detector enabled (use `go test -race -run=ExampleFast_concurrent`) to verify that concurrent access is safe and free of data races.

This example demonstrates how multiple goroutines perform lock-free, concurrent reads via an atomic pointer, while synchronizing writers with a mutex to ensure exclusive access. This concurrency pattern is useful when reads are frequent and writes are rare or take a long time in comparison to reads, providing high performance for concurrent workloads.

If the payload V either contains or is a pointer, it must implement the bart.Cloner interface. 

package main

import (
	"sync"
	"sync/atomic"

	"github.com/gaissmai/bart"
)

// If the payload V either contains or is a pointer,
// it must implement the [bart.Cloner] interface.
var _ bart.Cloner[*testVal] = (*testVal)(nil)

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

// ExampleFast_concurrent demonstrates safe concurrent usage of bart.Fast.
// This example is intended to be run with the Go race detector enabled
// (use `go test -race -run=ExampleFast_concurrent`)
// to verify that concurrent access is safe and free of data races.
//
// This example demonstrates how multiple goroutines perform lock-free, concurrent reads
// via an atomic pointer, while synchronizing writers with a mutex to ensure exclusive access.
// This concurrency pattern is useful when reads are frequent and writes are rare
// or take a long time in comparison to reads,
// providing high performance for concurrent workloads.
//
// If the payload V either contains or is a pointer,
// it must implement the [bart.Cloner] interface.
func main() {
	var tblAtomicPtr atomic.Pointer[bart.Fast[*testVal]]
	var tblMutex sync.Mutex

	baseTbl := new(bart.Fast[*testVal])
	tblAtomicPtr.Store(baseTbl)

	wg := sync.WaitGroup{}

	wg.Add(1)
	go func() {
		defer wg.Done()
		for range 100_000 {
			for _, ip := range exampleIPs {
				_, _ = tblAtomicPtr.Load().Lookup(ip)
			}
		}
	}()

	wg.Add(1)
	go func() {
		defer wg.Done()
		for range 1_000 {
			tblMutex.Lock()
			cur := tblAtomicPtr.Load()

			// batch of inserts
			next := cur
			for _, pfx := range examplePrefixes {
				next = next.InsertPersist(pfx, &testVal{data: 0})
			}

			tblAtomicPtr.Store(next)
			tblMutex.Unlock()
		}
	}()

	wg.Add(1)
	go func() {
		defer wg.Done()
		for range 1_000 {
			tblMutex.Lock()
			cur := tblAtomicPtr.Load()

			// batch of deletes
			next := cur
			for _, pfx := range examplePrefixes {
				next = next.DeletePersist(pfx)
			}

			tblAtomicPtr.Store(next)
			tblMutex.Unlock()
		}
	}()

	wg.Wait()

}

func (*Fast[V]) All added in v0.26.0 

func (t *Fast[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.

IMPORTANT: Modifying or deleting entries during iteration is not allowed, as this would interfere with the internal traversal and may corrupt or prematurely terminate the iteration. If mutation of the table during traversal is required use persistent table methods, e.g. 

pt := t // shallow copy of t
for pfx, val := range t.All() {
	if cond(pfx, val) {
	  pt = pt.DeletePersist(pfx)
  }
}

func (*Fast[V]) All4 added in v0.26.0 

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

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

func (*Fast[V]) All6 added in v0.26.0 

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

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

func (*Fast[V]) AllSorted added in v0.26.0 

func (t *Fast[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.

IMPORTANT: Deleting entries during iteration is not allowed, as this would interfere with the internal traversal and may corrupt or prematurely terminate the iteration. If mutation of the table during traversal is required use persistent table methods.

func (*Fast[V]) AllSorted4 added in v0.26.0 

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

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

func (*Fast[V]) AllSorted6 added in v0.26.0 

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

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

func (*Fast[V]) Clone added in v0.26.0 

func (t *Fast[V]) Clone() *Fast[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 (*Fast[V]) Contains added in v0.26.0 

func (f *Fast[V]) Contains(ip netip.Addr) bool

Contains reports whether any stored prefix covers the given IP address. Returns false for invalid IP addresses.

This performs longest-prefix matching and returns true if any prefix in the routing table contains the IP address, regardless of the associated value.

It does not return the value nor the prefix of the matching item, but as a test against an allow-/deny-list it's often sufficient and even few nanoseconds faster than Table.Lookup.

func (*Fast[V]) Delete added in v0.26.0 

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

Delete removes the exact prefix pfx from the table in-place.

This is an exact-match operation (no LPM). If pfx exists, the entry is removed. If pfx does not exist or pfx is invalid, the table is left unchanged.

The prefix is canonicalized (Masked) before lookup.

func (*Fast[V]) DeletePersist added in v0.26.0 

func (t *Fast[V]) DeletePersist(pfx netip.Prefix) *Fast[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 Fast reflecting the change.

If the prefix is invalid or doesn't exist, the original table is returned unchanged.

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 this is significantly slower than Delete, typically taking μsec instead of nsec.

func (*Fast[V]) DumpList4 added in v0.26.0 

func (t *Fast[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 (*Fast[V]) DumpList6 added in v0.26.0 

func (t *Fast[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 (*Fast[V]) Equal added in v0.26.0 

func (t *Fast[V]) Equal(o *Fast[V]) bool

Equal checks whether two tables are structurally and semantically equal. It ensures both trees (IPv4-based and IPv6-based) have the same sizes and recursively compares their root nodes.

func (*Fast[V]) Fprint added in v0.26.0 

func (t *Fast[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 (*Fast[V]) Get added in v0.26.0 

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

Get performs an exact-prefix lookup and returns whether the exact prefix exists. The prefix is canonicalized (Masked) before lookup.

This is an exact-match operation (no LPM). The prefix must match exactly in both address and prefix length to be found. If pfx exists, the associated value (zero value for Lite) and found=true is returned. If pfx does not exist or pfx is invalid, the zero value for V and exists=false is returned.

For longest-prefix-match (LPM) lookups, use Contains(ip), Lookup(ip), LookupPrefix(pfx) or LookupPrefixLPM(pfx) instead.

func (*Fast[V]) Insert added in v0.26.0 

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

Insert adds or updates a prefix-value pair in the routing table. If the prefix already exists, its value is updated; otherwise a new entry is created. Invalid prefixes are silently ignored.

The prefix is automatically canonicalized using pfx.Masked() to ensure consistent behavior regardless of host bits in the input.

func (*Fast[V]) InsertPersist added in v0.26.0 

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

InsertPersist is similar to Insert but the receiver isn't modified.

All nodes touched during insert are cloned and a new Fast is returned. This is not a full Fast.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.

Due to cloning overhead this is significantly slower than Insert, typically taking μsec instead of nsec.

func (*Fast[V]) Lookup added in v0.26.0 

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

Lookup performs longest-prefix matching for the given IP address and returns the associated value of the most specific matching prefix. Returns the zero value of V and false if no prefix matches. Returns false for invalid IP addresses.

This is the core routing table operation used for packet forwarding decisions.

Its semantics are identical to Table.Lookup.

func (*Fast[V]) LookupPrefix added in v0.26.0 

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

LookupPrefix performs a longest prefix match lookup for any address within the given prefix. It finds the most specific routing table entry that would match any address in the provided prefix range.

This is functionally identical to LookupPrefixLPM but returns only the associated value, not the matching prefix itself.

Returns the value and true if a matching prefix is found. Returns zero value and false if no match exists.

func (*Fast[V]) LookupPrefixLPM added in v0.26.0 

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

LookupPrefixLPM performs a longest prefix match lookup for any address within the given prefix. It finds the most specific routing table entry that would match any address in the provided prefix range.

This is functionally identical to LookupPrefix but additionally returns the matching prefix (lpmPfx) itself along with the value.

This method is slower than LookupPrefix and should only be used if the matching lpm entry is also required for other reasons.

Returns the matching prefix, its associated value, and true if found. Returns zero values and false if no match exists.

func (*Fast[V]) MarshalJSON added in v0.26.0 

func (t *Fast[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 (*Fast[V]) MarshalText added in v0.26.0 

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

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

func (*Fast[V]) Modify added in v0.26.0 

func (t *Fast[V]) Modify(pfx netip.Prefix, cb func(_ V, ok bool) (_ V, del bool))

Modify applies an insert, update, or delete operation for the value associated with the given prefix. The supplied callback decides the operation: it is called with the current value (or zero if not found) and a boolean indicating whether the prefix exists. The callback must return a new value and a delete flag: del == false inserts or updates, del == true deletes the entry if it exists (otherwise no-op).

The operation is determined by the callback function, which is called with: 

val:   the current value (or zero value if not found)
found: true if the prefix currently exists, false otherwise

The callback returns: 

val: the new value to insert or update (ignored if del == true)
del: true to delete the entry, false to insert or update

Summary of callback semantics: 

| cb-input        | cb-return       | Ops    |
------------------------------------- --------
| (zero,   false) | (_,      true)  | no-op  |
| (zero,   false) | (newVal, false) | insert |
| (oldVal, true)  | (newVal, false) | update |
| (oldVal, true)  | (_,      true)  | delete |
------------------------------------- --------

func (*Fast[V]) ModifyPersist added in v0.26.0 

func (t *Fast[V]) ModifyPersist(pfx netip.Prefix, cb func(_ V, ok bool) (_ V, del bool)) *Fast[V]

ModifyPersist is similar to Modify but the receiver isn't modified and a new *Fast is returned.

func (*Fast[V]) Overlaps added in v0.26.0 

func (t *Fast[V]) Overlaps(o *Fast[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 (*Fast[V]) Overlaps4 added in v0.26.0 

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

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

func (*Fast[V]) Overlaps6 added in v0.26.0 

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

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

func (*Fast[V]) OverlapsPrefix added in v0.26.0 

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

OverlapsPrefix reports whether any prefix in the routing table overlaps with the given prefix. Two prefixes overlap if they share any IP addresses.

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 (*Fast[V]) Size added in v0.26.0 

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

Size returns the prefix count.

func (*Fast[V]) Size4 added in v0.26.0 

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

Size4 returns the IPv4 prefix count.

func (*Fast[V]) Size6 added in v0.26.0 

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

Size6 returns the IPv6 prefix count.

func (*Fast[V]) Subnets added in v0.26.0 

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

Subnets returns an iterator over all subnets of the given prefix in natural CIDR sort order. This includes prefixes of the same length (exact match) and longer (more specific) prefixes that are contained within the given prefix.

Example: 

for sub, val := range table.Subnets(netip.MustParsePrefix("10.0.0.0/8")) {
    fmt.Println("Covered:", sub, "->", val)
}

The iteration can be stopped early by breaking from the range loop. Returns an empty iterator if the prefix is invalid.

func (*Fast[V]) Supernets added in v0.26.0 

func (t *Fast[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 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.

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("Covered by:", supernet, "->", val)
}

The iteration can be stopped early by breaking from the range loop. Returns an empty iterator if the prefix is invalid.

func (*Fast[V]) Union added in v0.26.0 

func (t *Fast[V]) Union(o *Fast[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 Fast.Clone.

func (*Fast[V]) UnionPersist added in v0.26.0 

func (t *Fast[V]) UnionPersist(o *Fast[V]) *Fast[V]

UnionPersist is similar to [Union] but the receiver isn't modified.

All nodes touched during union are cloned and a new *Fast is returned. If o is nil or empty, no nodes are touched and the receiver may be returned unchanged.

type Lite added in v0.18.1 

type Lite struct {
	// contains filtered or unexported fields
}

Lite follows the BART design but with no payload. It is ideal for simple IP ACLs (access-control-lists) with plain true/false results with the smallest memory consumption.

The zero value is ready to use.

A Lite table must not be copied by value; always pass by pointer.

Performance note: Do not pass IPv4-in-IPv6 addresses (e.g., ::ffff:192.0.2.1) as input. The methods do not perform automatic unmapping to avoid unnecessary overhead for the common case where native addresses are used. Users should unmap IPv4-in-IPv6 addresses to their native IPv4 form (e.g., 192.0.2.1) before calling these methods.

Example (Concurrent)

ExampleLite_concurrent demonstrates safe concurrent usage of bart.Lite.

This example is intended to be run with the Go race detector enabled (use `go test -race -run=ExampleLite_concurrent`) to verify that concurrent access is safe and free of data races.

This example demonstrates how multiple goroutines perform lock-free, concurrent reads via an atomic pointer, while synchronizing writers with a mutex to ensure exclusive access. This concurrency pattern is useful when reads are frequent and writes are rare or take a long time in comparison to reads, providing high performance for concurrent workloads. 

var liteAtomicPtr atomic.Pointer[bart.Lite]
var liteMutex sync.Mutex

baseTbl := new(bart.Lite)
liteAtomicPtr.Store(baseTbl)

wg := sync.WaitGroup{}
wg.Add(1)
go func() {
	defer wg.Done()
	for range 10_000 {
		for _, ip := range exampleIPs {
			_ = liteAtomicPtr.Load().Contains(ip)
		}
	}
}()

wg.Add(1)
go func() {
	defer wg.Done()
	for range 1000 {
		liteMutex.Lock()
		cur := liteAtomicPtr.Load()

		// batch of inserts
		next := cur
		for _, pfx := range examplePrefixes {
			next = next.InsertPersist(pfx)
		}

		liteAtomicPtr.Store(next)
		liteMutex.Unlock()
	}
}()

wg.Add(1)
go func() {
	defer wg.Done()
	for range 1000 {
		liteMutex.Lock()
		cur := liteAtomicPtr.Load()

		// batch of deletes
		next := cur
		for _, pfx := range examplePrefixes {
			next = next.DeletePersist(pfx)
		}

		liteAtomicPtr.Store(next)
		liteMutex.Unlock()
	}
}()

wg.Wait()
Example (Contains) 
package main

import (
	"fmt"
	"net/netip"

	"github.com/gaissmai/bart"
)

var (
	mpa = netip.MustParseAddr
	mpp = netip.MustParsePrefix
)

var examplePrefixes = []netip.Prefix{
	mpp("192.168.0.0/16"),
	mpp("192.168.1.0/24"),
	mpp("2001:7c0:3100::/40"),
	mpp("2001:7c0:3100:1::/64"),
	mpp("fc00::/7"),
}

// some example IP addresses for black/whitelist containment
var exampleIPs = []netip.Addr{
	mpa("192.168.1.100"),
	mpa("192.168.2.1"),
	mpa("2001:7c0:3100:1::1"),
	mpa("2001:7c0:3100:2::1"),
	mpa("fc00::1"),

	mpa("172.16.0.1"),
	mpa("2003:dead:beef::1"),
}

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

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

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

}

Output:

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

func (*Lite) All added in v0.26.0 

func (l *Lite) All() iter.Seq[netip.Prefix]

func (*Lite) All4 added in v0.26.0 

func (l *Lite) All4() iter.Seq[netip.Prefix]

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

func (*Lite) All6 added in v0.26.0 

func (l *Lite) All6() iter.Seq[netip.Prefix]

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

func (*Lite) AllSorted added in v0.26.0 

func (l *Lite) AllSorted() iter.Seq[netip.Prefix]

AllSorted returns an iterator over all prefixes 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 := range t.AllSorted() {
    fmt.Println(prefix)
}

The traversal is stable and predictable across calls. Iteration stops early if you break out of the loop.

IMPORTANT: Deleting entries during iteration is not allowed, as this would interfere with the internal traversal and may corrupt or prematurely terminate the iteration. If mutation of the table during traversal is required use persistent table methods.

func (*Lite) AllSorted4 added in v0.26.0 

func (l *Lite) AllSorted4() iter.Seq[netip.Prefix]

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

func (*Lite) AllSorted6 added in v0.26.0 

func (l *Lite) AllSorted6() iter.Seq[netip.Prefix]

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

func (*Lite) Clone added in v0.20.0 

func (l *Lite) Clone() *Lite

Clone returns a copy of the routing table.

func (*Lite) Contains added in v0.18.1 

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

Contains reports whether any stored prefix covers the given IP address. Returns false for invalid IP addresses.

This performs longest-prefix matching and returns true if any prefix in the routing table contains the IP address, regardless of the associated value.

It does not return the value nor the prefix of the matching item, but as a test against an allow-/deny-list it's often sufficient and even few nanoseconds faster than Table.Lookup.

func (*Lite) Delete added in v0.18.1 

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

Delete removes the exact prefix pfx from the table in-place.

This is an exact-match operation (no LPM). If pfx exists, the entry is removed. If pfx does not exist or pfx is invalid, the table is left unchanged.

The prefix is canonicalized (Masked) before lookup.

func (*Lite) DeletePersist added in v0.20.0 

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

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 *Lite reflecting the change.

If the prefix is invalid or doesn't exist, the original table is returned unchanged.

Due to cloning overhead this is significantly slower than Delete, typically taking μsec instead of nsec.

func (*Lite) DumpList4 added in v0.26.0 

func (l *Lite) DumpList4() []DumpListNode[struct{}]

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 (*Lite) DumpList6 added in v0.26.0 

func (l *Lite) DumpList6() []DumpListNode[struct{}]

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 (*Lite) Equal added in v0.25.0 

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

Equal checks whether two tables are structurally and semantically equal. It ensures both trees (IPv4-based and IPv6-based) have the same sizes and recursively compares their root nodes.

func (*Lite) Fprint added in v0.26.0 

func (l *Lite) 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 (*Lite) Get added in v0.26.0 

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

Get performs an exact-prefix lookup and returns whether the exact prefix exists. The prefix is canonicalized (Masked) before lookup.

This is an exact-match operation (no LPM). The prefix must match exactly in both address and prefix length to be found. If pfx is valid and exists, true is returned, otherwise false.

For longest-prefix-match (LPM) lookups, use Contains(ip), Lookup(ip), LookupPrefix(pfx) or LookupPrefixLPM(pfx) instead.

func (*Lite) Insert added in v0.18.1 

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

Insert adds a prefix to the routing table. If the prefix already exists, it's a no-op; otherwise a new entry is created. Invalid prefixes are silently ignored.

The prefix is automatically canonicalized using pfx.Masked() to ensure consistent behavior regardless of host bits in the input.

func (*Lite) InsertPersist added in v0.20.0 

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

InsertPersist is similar to Insert but the receiver isn't modified.

All nodes touched during insert are cloned and a new *Lite is returned. This is not a full Lite.Clone, all untouched nodes are still referenced from both Tables.

This is orders of magnitude slower than Insert, typically taking μsec instead of nsec.

The bulk table load could be done with Lite.Insert and then you can use Lite.InsertPersist, Lite.ModifyPersist and Lite.DeletePersist for further lock-free ops.

func (*Lite) Lookup added in v0.26.0 

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

Lookup performs a longest-prefix-match (LPM) for addr.

Note: Lite stores no payload values, so this method is rarely useful. Prefer Contains(addr) to check whether any prefix matches the address. For exact prefix existence use Get(pfx). For prefix-based LPM use LookupPrefix or LookupPrefixLPM.

Returns true if any prefix matches addr, otherwise false.

func (*Lite) LookupPrefix added in v0.26.0 

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

LookupPrefix performs a longest prefix match lookup for any address within the given prefix.

Returns true if a matching prefix is found, otherwise false.

func (*Lite) LookupPrefixLPM added in v0.26.0 

func (l *Lite) LookupPrefixLPM(pfx netip.Prefix) (lpmPfx netip.Prefix, ok bool)

LookupPrefixLPM performs a longest prefix match lookup for any address within the given prefix. It finds the most specific routing table entry that would match any address in the provided prefix range.

This is functionally identical to LookupPrefix but returns the matching prefix (lpmPfx) itself.

This method is slower than LookupPrefix and should only be used if the matching lpm entry is also required for other reasons.

Returns the matching prefix and true if found, otherwise the zero value and false.

func (*Lite) MarshalJSON added in v0.26.0 

func (l *Lite) 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 (*Lite) MarshalText added in v0.26.0 

func (l *Lite) MarshalText() ([]byte, error)

MarshalText implements the encoding.TextMarshaler interface, just a wrapper for [liteTable.Fprint].

func (*Lite) Modify added in v0.26.0 

func (l *Lite) Modify(pfx netip.Prefix, cb func(exists bool) (del bool))

Modify applies an insert, update, or delete operation for the given prefix. The operation is determined by the callback function, which is called with: 

true:  the prefix is in table
false: the prefix is not in table

The callback returns: 

true:  delete the entry
false: insert or update

Summary of callback semantics: 

| input | return | op     |
---------------------------
| false | true   | no-op  |
| false | false  | insert |
| true  | false  | update |
| true  | true   | delete |
---------------------------

func (*Lite) ModifyPersist added in v0.26.0 

func (l *Lite) ModifyPersist(pfx netip.Prefix, cb func(exists bool) (del bool)) *Lite

ModifyPersist is similar to Modify but the receiver isn't modified and a new *Lite is returned.

func (*Lite) Overlaps added in v0.20.0 

func (l *Lite) Overlaps(o *Lite) 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.

It is intentionally not nil-receiver safe: calling with a nil receiver will panic by design.

func (*Lite) Overlaps4 added in v0.20.0 

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

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

func (*Lite) Overlaps6 added in v0.20.0 

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

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

func (*Lite) OverlapsPrefix added in v0.26.0 

func (t *Lite) OverlapsPrefix(pfx netip.Prefix) bool

OverlapsPrefix reports whether any prefix in the routing table overlaps with the given prefix. Two prefixes overlap if they share any IP addresses.

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 (*Lite) Size added in v0.26.0 

func (t *Lite) Size() int

Size returns the prefix count.

func (*Lite) Size4 added in v0.26.0 

func (t *Lite) Size4() int

Size4 returns the IPv4 prefix count.

func (*Lite) Size6 added in v0.26.0 

func (t *Lite) Size6() int

Size6 returns the IPv6 prefix count.

func (*Lite) Subnets added in v0.26.0 

func (l *Lite) Subnets(pfx netip.Prefix) iter.Seq[netip.Prefix]

Subnets returns an iterator over all subnets of the given prefix in natural CIDR sort order. This includes prefixes of the same length (exact match) and longer (more specific) prefixes that are contained within the given prefix.

Example: 

for sub := range table.Subnets(netip.MustParsePrefix("10.0.0.0/8")) {
    fmt.Println("Covered:", sub)
}

The iteration can be stopped early by breaking from the range loop. Returns an empty iterator if the prefix is invalid.

func (*Lite) Supernets added in v0.26.0 

func (l *Lite) Supernets(pfx netip.Prefix) iter.Seq[netip.Prefix]

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 := range table.Supernets(netip.MustParsePrefix("192.0.2.128/25")) {
    fmt.Println("Matched covering route:", supernet)
}

func (*Lite) Union added in v0.20.0 

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

Union merges another routing table into the receiver table, modifying it in-place.

All prefixes from the other table (o) are inserted into the receiver.

func (*Lite) UnionPersist added in v0.24.0 

func (l *Lite) UnionPersist(o *Lite) *Lite

UnionPersist is similar to [Union] but the receiver isn't modified.

All nodes touched during union are cloned and a new *Lite is returned. If o is nil or empty, no nodes are touched and the receiver may be returned unchanged.

type Table 

type Table[V any] struct {
	// contains filtered or unexported fields
}

Table represents an 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.

Performance note: Do not pass IPv4-in-IPv6 addresses (e.g., ::ffff:192.0.2.1) as input. The methods do not perform automatic unmapping to avoid unnecessary overhead for the common case where native addresses are used. Users should unmap IPv4-in-IPv6 addresses to their native IPv4 form (e.g., 192.0.2.1) before calling these methods.

Example (Concurrent)

ExampleTable_concurrent demonstrates safe concurrent usage of bart.Table. This example is intended to be run with the Go race detector enabled (use `go test -race -run=ExampleTable_concurrent`) to verify that concurrent access is safe and free of data races.

This example demonstrates how multiple goroutines perform lock-free, concurrent reads via an atomic pointer, while synchronizing writers with a mutex to ensure exclusive access. This concurrency pattern is useful when reads are frequent and writes are rare or take a long time in comparison to reads, providing high performance for concurrent workloads.

If the payload V either contains a pointer or is a pointer, it must implement the bart.Cloner interface. 

package main

import (
	"sync"
	"sync/atomic"

	"github.com/gaissmai/bart"
)

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

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

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

// ExampleTable_concurrent demonstrates safe concurrent usage of bart.Table.
// This example is intended to be run with the Go race detector enabled
// (use `go test -race -run=ExampleTable_concurrent`)
// to verify that concurrent access is safe and free of data races.
//
// This example demonstrates how multiple goroutines perform lock-free, concurrent reads
// via an atomic pointer, while synchronizing writers with a mutex to ensure exclusive access.
// This concurrency pattern is useful when reads are frequent and writes are rare
// or take a long time in comparison to reads,
// providing high performance for concurrent workloads.
//
// If the payload V either contains a pointer or is a pointer,
// it must implement the [bart.Cloner] interface.
func main() {
	var tblAtomicPtr atomic.Pointer[bart.Table[*testVal]]
	var tblMutex sync.Mutex

	baseTbl := new(bart.Table[*testVal])
	tblAtomicPtr.Store(baseTbl)

	wg := sync.WaitGroup{}

	wg.Add(1)
	go func() {
		defer wg.Done()
		for range 100_000 {
			for _, ip := range exampleIPs {
				_, _ = tblAtomicPtr.Load().Lookup(ip)
			}
		}
	}()

	wg.Add(1)
	go func() {
		defer wg.Done()
		for range 1_000 {
			tblMutex.Lock()
			cur := tblAtomicPtr.Load()

			// batch of inserts
			next := cur
			for _, pfx := range examplePrefixes {
				next = next.InsertPersist(pfx, &testVal{data: 0})
			}

			tblAtomicPtr.Store(next)
			tblMutex.Unlock()
		}
	}()

	wg.Add(1)
	go func() {
		defer wg.Done()
		for range 1_000 {
			tblMutex.Lock()
			cur := tblAtomicPtr.Load()

			// batch of deletes
			next := cur
			for _, pfx := range examplePrefixes {
				next = next.DeletePersist(pfx)
			}

			tblAtomicPtr.Store(next)
			tblMutex.Unlock()
		}
	}()

	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.

IMPORTANT: Modifying or deleting entries during iteration is not allowed, as this would interfere with the internal traversal and may corrupt or prematurely terminate the iteration. If mutation of the table during traversal is required use persistent table methods, e.g. 

pt := t // shallow copy of t
for pfx, val := range t.All() {
	if cond(pfx, val) {
	  pt = pt.DeletePersist(pfx)
  }
}

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.

IMPORTANT: Deleting entries during iteration is not allowed, as this would interfere with the internal traversal and may corrupt or prematurely terminate the iteration. If mutation of the table during traversal is required use persistent table methods.

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 (
	mpa = netip.MustParseAddr
	mpp = netip.MustParsePrefix
)

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

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

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

}

Output:

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

func (*Table[V]) AllSorted6 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 reports whether any stored prefix covers the given IP address. Returns false for invalid IP addresses.

This performs longest-prefix matching and returns true if any prefix in the routing table contains the IP address, regardless of the associated value.

It does not return the value nor the prefix of the matching item, but as a test against an allow-/deny-list 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 the exact prefix pfx from the table in-place.

This is an exact-match operation (no LPM). If pfx exists, the entry is removed. If pfx does not exist or pfx is invalid, the table is left unchanged.

The prefix is canonicalized (Masked) before lookup.

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 prefix is invalid or doesn't exist, the original table is returned unchanged.

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 this 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]) Equal added in v0.25.0 

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

Equal checks whether two tables are structurally and semantically equal. It ensures both trees (IPv4-based and IPv6-based) have the same sizes and recursively compares their root nodes.

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, exists bool)

Get performs an exact-prefix lookup and returns whether the exact prefix exists. The prefix is canonicalized (Masked) before lookup.

This is an exact-match operation (no LPM). The prefix must match exactly in both address and prefix length to be found. If pfx exists, the associated value (zero value for Lite) and found=true is returned. If pfx does not exist or pfx is invalid, the zero value for V and exists=false is returned.

For longest-prefix-match (LPM) lookups, use Contains(ip), Lookup(ip), LookupPrefix(pfx) or LookupPrefixLPM(pfx) instead.

func (*Table[V]) Insert 

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

Insert adds or updates a prefix-value pair in the routing table. If the prefix already exists, its value is updated; otherwise a new entry is created. Invalid prefixes are silently ignored.

The prefix is automatically canonicalized using pfx.Masked() to ensure consistent behavior regardless of host bits in the input.

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.

Due to cloning overhead this is significantly slower than Insert, typically taking μsec instead of nsec.

func (*Table[V]) Lookup 

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

Lookup performs a longest prefix match (LPM) lookup for the given address. It finds the most specific (longest) prefix in the routing table that contains the given address and returns its associated value.

This is the fundamental operation for IP routing decisions, finding the best matching route for a destination address.

Returns the associated value and true if a matching prefix is found. Returns zero value and false if no prefix contains the address.

Example 
package main

import (
	"fmt"
	"net/netip"
	"os"

	"github.com/gaissmai/bart"
)

var (
	mpa = netip.MustParseAddr
	mpp = netip.MustParsePrefix
)

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

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

	fmt.Println()

	ip := mpa("42.0.0.0")
	value, ok := rtbl.Lookup(ip)
	fmt.Printf("Lookup: %-20v next-hop: %11v, ok: %v\n", ip, value, ok)

	ip = mpa("10.0.1.17")
	value, ok = rtbl.Lookup(ip)
	fmt.Printf("Lookup: %-20v next-hop: %11v, ok: %v\n", ip, value, ok)

	ip = mpa("2001:7c0:3100:1::111")
	value, ok = rtbl.Lookup(ip)
	fmt.Printf("Lookup: %-20v next-hop: %11v, ok: %v\n", ip, value, ok)

}

Output:

▼
├─ 10.0.0.0/8 (9.9.9.9)
│  ├─ 10.0.0.0/24 (8.8.8.8)
│  └─ 10.0.1.0/24 (10.0.0.0)
├─ 127.0.0.0/8 (127.0.0.1)
│  └─ 127.0.0.1/32 (127.0.0.1)
├─ 169.254.0.0/16 (10.0.0.0)
├─ 172.16.0.0/12 (8.8.8.8)
└─ 192.168.0.0/16 (9.9.9.9)
   └─ 192.168.1.0/24 (127.0.0.1)
▼
└─ ::/0 (2001:db8::1)
   ├─ ::1/128 (::1%lo)
   ├─ 2000::/3 (2000::)
   │  └─ 2001:db8::/32 (2001:db8::1)
   └─ fe80::/10 (::1%eth0)

Lookup: 42.0.0.0             next-hop:  invalid IP, ok: false
Lookup: 10.0.1.17            next-hop:    10.0.0.0, ok: true
Lookup: 2001:7c0:3100:1::111 next-hop:      2000::, ok: true

func (*Table[V]) LookupPrefix added in v0.5.0 

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

LookupPrefix performs a longest prefix match lookup for any address within the given prefix. It finds the most specific routing table entry that would match any address in the provided prefix range.

This is functionally identical to LookupPrefixLPM but returns only the associated value, not the matching prefix itself.

Returns the value and true if a matching prefix is found. Returns zero value and false if no match exists.

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 performs a longest prefix match lookup for any address within the given prefix. It finds the most specific routing table entry that would match any address in the provided prefix range.

This is functionally identical to LookupPrefix but additionally returns the matching prefix (lpmPfx) itself along with the value.

This method is slower than LookupPrefix and should only be used if the matching lpm entry is also required for other reasons.

Returns the matching prefix, its associated value, and true if found. Returns zero values and false if no match exists.

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]) Modify added in v0.25.0 

func (t *Table[V]) Modify(pfx netip.Prefix, cb func(_ V, ok bool) (_ V, del bool))

Modify applies an insert, update, or delete operation for the value associated with the given prefix. The supplied callback decides the operation: it is called with the current value (or zero if not found) and a boolean indicating whether the prefix exists. The callback must return a new value and a delete flag: del == false inserts or updates, del == true deletes the entry if it exists (otherwise no-op).

The operation is determined by the callback function, which is called with: 

val:   the current value (or zero value if not found)
found: true if the prefix currently exists, false otherwise

The callback returns: 

val: the new value to insert or update (ignored if del == true)
del: true to delete the entry, false to insert or update

Summary of callback semantics: 

| cb-input        | cb-return       | Ops    |
------------------------------------- --------
| (zero,   false) | (_,      true)  | no-op  |
| (zero,   false) | (newVal, false) | insert |
| (oldVal, true)  | (newVal, false) | update |
| (oldVal, true)  | (_,      true)  | delete |
------------------------------------- --------

func (*Table[V]) ModifyPersist added in v0.25.0 

func (t *Table[V]) ModifyPersist(pfx netip.Prefix, cb func(_ V, ok bool) (_ V, del bool)) *Table[V]

ModifyPersist is similar to Modify but the receiver isn't modified and a new *Table is returned.

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 prefix in the routing table overlaps with the given prefix. Two prefixes overlap if they share any IP addresses.

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]) 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 subnets of the given prefix in natural CIDR sort order. This includes prefixes of the same length (exact match) and longer (more specific) prefixes that are contained within the given prefix.

Example: 

for sub, val := range table.Subnets(netip.MustParsePrefix("10.0.0.0/8")) {
    fmt.Println("Covered:", sub, "->", val)
}

The iteration can be stopped early by breaking from the range loop. Returns an empty iterator if the prefix is invalid.

Example (Rangeoverfunc) 
package main

import (
	"fmt"
	"net/netip"

	"github.com/gaissmai/bart"
)

var (
	mpa = netip.MustParseAddr
	mpp = netip.MustParsePrefix
)

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

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

	cidr := netip.MustParsePrefix("0.0.0.0/1")

	for pfx := range rtbl.Subnets(cidr) {
		fmt.Printf("%v\n", pfx)
	}

}

Output:

10.0.0.0/8
10.0.0.0/24
10.0.1.0/24
127.0.0.0/8
127.0.0.1/32

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

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("Covered by:", supernet, "->", val)
}

The iteration can be stopped early by breaking from the range loop. Returns an empty iterator if the prefix is invalid.

Example (Rangeoverfunc) 
package main

import (
	"fmt"
	"net/netip"

	"github.com/gaissmai/bart"
)

var (
	mpa = netip.MustParseAddr
	mpp = netip.MustParsePrefix
)

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

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

	cidr := netip.MustParsePrefix("2001:db8::/32")

	counter := 0
	for pfx := range rtbl.Supernets(cidr) {
		fmt.Printf("%v\n", pfx)
		counter++
		if counter >= 2 {
			break
		}
	}

}

Output:

2001:db8::/32
2000::/3

func (*Table[V]) Union 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]) UnionPersist added in v0.24.0 

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

UnionPersist is similar to [Union] but the receiver isn't modified.

All nodes touched during union are cloned and a new *Table is returned. If o is nil or empty, no nodes are touched and the receiver may be returned unchanged.

Source Files

View all Source files

Directories

Path Synopsis
internal
allot
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.
nodes
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].
tests/golden
tests/random

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.