nodes

func (*BartNode[V]) AllChildren ¶

func (n *BartNode[V]) AllChildren() iter.Seq2[uint8, any]

AllChildren returns an iterator over all child nodes. Each iteration yields the child's address (uint8) and the child node (any).

func (*BartNode[V]) AllIndices ¶

func (n *BartNode[V]) AllIndices() iter.Seq2[uint8, V]

AllIndices returns an iterator over all prefix entries. Each iteration yields the prefix index (uint8) and its associated value (V).

func (*BartNode[V]) AllRec ¶

func (n *BartNode[V]) AllRec(path StridePath, depth int, is4 bool, yield func(netip.Prefix, V) bool) bool

AllRec recursively traverses the trie starting at the current node, applying the provided yield function to every stored prefix and value.

For each route entry (prefix and value), yield is invoked. If yield returns false, the traversal stops immediately, and false is propagated upwards, enabling early termination.

The function handles all prefix entries in the current node, as well as any children - including sub-nodes, leaf nodes with full prefixes, and fringe nodes representing path-compressed prefixes. IP prefix reconstruction is performed on-the-fly from the current path and depth.

The traversal order is not defined. This implementation favors simplicity and runtime efficiency over consistency of iteration sequence.

func (*BartNode[V]) AllRecSorted ¶

func (n *BartNode[V]) AllRecSorted(path StridePath, depth int, is4 bool, yield func(netip.Prefix, V) bool) bool

AllRecSorted recursively traverses the trie in prefix-sorted order and applies the given yield function to each stored prefix and value.

Unlike AllRec, this implementation ensures that route entries are visited in canonical prefix sort order. To achieve this, both the prefixes and children of the current node are gathered, sorted, and then interleaved during traversal based on logical octet positioning.

The function first sorts relevant entries by their prefix index and address value, using a comparison function that ranks prefixes according to their mask length and position. Then it walks the trie, always yielding child entries that fall before the current prefix, followed by the prefix itself. Remaining children are processed once all prefixes have been visited.

Prefixes are reconstructed on-the-fly from the traversal path, and iteration includes all child types: inner nodes (recursive descent), leaf nodes, and fringe (compressed) prefixes.

The order is stable and predictable, making the function suitable for use cases like table exports, comparisons or serialization.

Parameters:

• path: the current traversal path through the trie
• depth: current depth in the trie (0-based)
• is4: true for IPv4 processing, false for IPv6
• yield: callback function invoked for each prefix/value pair

Returns false if yield function requests early termination.

func (*BartNode[V]) ChildCount ¶

func (n *BartNode[V]) ChildCount() int

ChildCount returns the number of slots used in this node.

func (*BartNode[V]) CloneFlat ¶

func (n *BartNode[V]) CloneFlat(cloneFn func(V) V) *BartNode[V]

CloneFlat returns a shallow copy of the current node, optionally performing deep copies of values.

If cloneFn is nil, the stored values in prefixes are copied directly without modification. Otherwise, cloneFn is applied to each stored value for deep cloning. Child nodes are cloned shallowly: LeafNode and FringeNode children are cloned via their clone methods, but child nodes of type *BartNode[V] (subnodes) are assigned as-is without recursive cloning. This method does not recursively clone descendants beyond the immediate children.

Note: The returned node is a new instance with copied slices but only shallow copies of nested nodes, except for LeafNode and FringeNode children which are cloned according to cloneFn.

func (*BartNode[V]) CloneRec ¶

func (n *BartNode[V]) CloneRec(cloneFn func(V) V) *BartNode[V]

CloneRec performs a recursive deep copy of the node and all its descendants.

If cloneFn is nil, the stored values are copied directly without modification. Otherwise cloneFn is applied to each stored value for deep cloning.

This method first creates a shallow clone of the current node using CloneFlat, applying cloneFn to values as described there. Then it recursively clones all child nodes of type *BartNode[V], performing a full deep clone down the subtree.

Child nodes of type *LeafNode[V] and *FringeNode[V] are already cloned by CloneFlat.

Returns a new instance of BartNode[V] which is a complete deep clone of the receiver node with all descendants.

func (*BartNode[V]) Contains ¶

func (n *BartNode[V]) Contains(idx uint8) bool

Contains returns true if an index (idx) has any matching longest-prefix in the current node’s prefix table.

This function performs a presence check without retrieving the associated value. It is faster than a full lookup, as it only tests for intersection with the backtracking bitset for the given index.

The prefix table is structured as a complete binary tree (CBT), and LPM testing is done via a bitset operation that maps the traversal path from the given index toward its possible ancestors.

func (*BartNode[V]) Delete ¶

func (n *BartNode[V]) Delete(pfx netip.Prefix) (exists bool)

Delete removes the prefix from the trie rooted at n and returns true if the prefix existed, false if it was not found. The prefix must be in canonical (masked) form.

The trie uses path compression, so a prefix may be stored in one of three ways:

• In the current node's prefix table when the prefix length aligns exactly with the stride boundary at this depth (depth == strideCount).
• As a path-compressed FringeNode in a child slot for stride-aligned prefixes (e.g. /8, /16, /24); occurs at depth == strideCount-1.
• As a path-compressed LeafNode in a child slot for prefixes otherwise.

After a successful deletion, PurgeAndCompress walks the ancestor stack to prune now-empty nodes and restore path compression upward.

func (*BartNode[V]) DeleteChild ¶

func (n *BartNode[V]) DeleteChild(addr uint8) (exists bool)

DeleteChild removes the child node at the specified address. This operation is idempotent - removing a non-existent child is safe.

func (*BartNode[V]) DeletePersist ¶

func (n *BartNode[V]) DeletePersist(cloneFn func(V) V, pfx netip.Prefix) (exists bool)

DeletePersist removes the prefix from the trie rooted at n using Copy-On-Write (COW) semantics. It returns true if the prefix existed, false if it was not found. The prefix must be in canonical (masked) form.

Like [Delete], this method uses path compression. However, DeletePersist ensures the structural integrity of the existing tree by cloning internal nodes along the descent path (COW) before mutation.

After a successful deletion, PurgeAndCompress walks the ancestor stack to prune now-empty nodes and restore path compression upward.

func (*BartNode[V]) DeletePrefix ¶

func (n *BartNode[V]) DeletePrefix(idx uint8) (exists bool)

DeletePrefix removes the prefix at the specified index. Returns true if the prefix existed, otherwise false.

func (*BartNode[V]) DirectItemsRec ¶

func (n *BartNode[V]) DirectItemsRec(parentIdx uint8, path StridePath, depth int, is4 bool) (directItems []TrieItem[V])

DirectItemsRec, returns the direct covered items by parent. It's a complex recursive function, you have to know the data structure by heart to understand this function!

func (*BartNode[V]) DumpRec ¶

func (n *BartNode[V]) DumpRec(w io.Writer, path StridePath, depth int, is4 bool)

DumpRec recursively descends the trie rooted at n and writes a human-readable representation of each visited node to w.

It returns immediately if n is nil or empty. For each visited internal node it calls dump to write the node's representation, then iterates its child addresses and recurses into children of type *BartNode[V] (internal subnodes). The path slice and depth together represent the byte-wise path from the root to the current node; depth is incremented for each recursion. The is4 flag controls IPv4/IPv6 formatting used by dump.

func (*BartNode[V]) DumpString ¶

func (n *BartNode[V]) DumpString(octets []uint8, depth int, is4 bool) string

DumpString traverses the trie to the node at the specified depth along the given octet path and returns its string representation via Dump.

If the path is invalid or encounters an unexpected node type during traversal, it returns an error message string instead.

Parameters:

• octets: The path of octets to follow from the root
• depth: Target depth to reach before dumping (0-based byte index)
• is4: True for IPv4 formatting, false for IPv6

Returns a formatted string representation of the target node or an error message.

func (*BartNode[V]) EachLookupPrefix ¶

func (n *BartNode[V]) EachLookupPrefix(ip netip.Addr, depth int, pfxIdx uint8, yield func(netip.Prefix, V) bool) (ok bool)

EachLookupPrefix performs a hierarchical lookup of all matching prefixes in the current node’s 8-bit stride-based prefix table.

The function walks up the trie-internal complete binary tree (CBT), testing each possible prefix length mask (in decreasing order of specificity), and invokes the yield function for every matching entry.

The given idx refers to the position for this stride's prefix and is used to derive a backtracking path through the CBT by repeatedly halving the index. At each step, if a prefix exists in the table, its corresponding CIDR is reconstructed and yielded. If yield returns false, traversal stops early.

This function is intended for internal use during supernet traversal and does not descend the trie further.

func (*BartNode[V]) EachSubnet ¶

func (n *BartNode[V]) EachSubnet(octets []byte, depth int, is4 bool, pfxIdx uint8, yield func(netip.Prefix, V) bool) bool

EachSubnet yields all prefix entries and child nodes covered by a given parent prefix, sorted in natural CIDR order, within the current node.

The function iterates through all prefixes and children from the node’s stride tables. Only entries that fall within the address range defined by the parent prefix index (pfxIdx) are included. Matching entries are buffered, sorted, and passed through to the yield function.

Child entries (nodes, leaves, fringes) that fall under the covered address range are processed recursively via AllRecSorted to ensure sorted traversal.

This function is intended for internal use by Subnets(), and it assumes the current node is positioned at the point in the trie corresponding to the parent prefix.

func (*BartNode[V]) EqualRec ¶

func (n *BartNode[V]) EqualRec(o *BartNode[V]) bool

EqualRec performs recursive structural equality comparison between two nodes. Compares prefix and child bitsets, then recursively compares all stored values and child nodes. Returns true if the nodes and their entire subtrees are structurally and semantically identical, false otherwise.

The comparison handles different node types (internal nodes, leafNodes, fringeNodes) and uses the equal function for value comparisons to support custom equality logic.

func (*BartNode[V]) FprintRec ¶

func (n *BartNode[V]) FprintRec(w io.Writer, parent TrieItem[V], pad string) error

FprintRec recursively prints a hierarchical CIDR tree representation starting from this node to the provided writer. The output shows the routing table structure in human-readable format for debugging and analysis.

func (*BartNode[V]) Get ¶

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

Get retrieves the value associated with the given network prefix. Traversal descends through the trie using the prefix's octets.

The lookup handles path compression transparently:

• If the path matches an internal node at the target stride, the value is retrieved from the node's prefix table.
• If the path leads to a compressed LeafNode or FringeNode, the function verifies the prefix match before returning the value.

Parameters:

• pfx: The network prefix to look up (must be in canonical form).

Returns:

• val: The value associated with the prefix (zero value if not found).
• exists: True if the prefix was found, false otherwise.

func (*BartNode[V]) GetChild ¶

func (n *BartNode[V]) GetChild(addr uint8) (any, bool)

GetChild retrieves the child node at the specified address. Returns the child and true if found, or nil and false if not present.

func (*BartNode[V]) GetPrefix ¶

func (n *BartNode[V]) GetPrefix(idx uint8) (val V, exists bool)

GetPrefix retrieves the value associated with the prefix at the given index. Returns the value and true if found, or zero value and false if not present.

func (*BartNode[V]) Insert ¶

func (n *BartNode[V]) Insert(pfx netip.Prefix, val V, depth int) (exists bool)

Insert adds or updates a network prefix and its associated value in the trie. Traversal begins at the specified byte depth.

The trie utilizes path compression to conserve memory. A prefix is inserted:

• Uncompressed into a node's prefix table at depth == strideCount.
• As a path-compressed FringeNode if it qualifies as fringe IsFringe.
• As a path-compressed LeafNode otherwise.

When a new prefix collides with an existing compressed node (Leaf or Fringe), Insert resolves the collision by creating a new intermediate node, pushing the existing entry down to the next level, and continuing traversal.

Parameters:

• pfx: The network prefix to insert (must be in canonical/masked form).
• val: The value to associate with the prefix.
• depth: The current depth in the trie (0-based byte index).

Returns true if an existing prefix was updated, false if a new insertion occurred.

func (*BartNode[V]) InsertChild ¶

func (n *BartNode[V]) InsertChild(addr uint8, child any) (exists bool)

InsertChild adds a child node at the specified address (0-255). The child can be a *BartNode[V], *LeafNode[V], or *FringeNode[V]. Returns true if a child already existed at that address.

func (*BartNode[V]) InsertPersist ¶

func (n *BartNode[V]) InsertPersist(cloneFn func(V) V, pfx netip.Prefix, val V, depth int) (exists bool)

InsertPersist adds or updates a network prefix and its associated value in the trie using Copy-On-Write (COW) semantics. Traversal begins at the specified byte depth.

Unlike [Insert], InsertPersist ensures structural integrity of the existing tree by cloning internal nodes along the descent path (Copy-On-Write) before mutation.

Parameters:

• cloneFn: The function used to clone values (V).
• pfx: The network prefix to insert (must be in canonical/masked form).
• val: The value to associate with the prefix.
• depth: The current depth in the trie (0-based byte index).

Returns true if an existing prefix was updated, false if a new insertion occurred.

func (*BartNode[V]) InsertPrefix ¶

func (n *BartNode[V]) InsertPrefix(idx uint8, val V) (exists bool)

InsertPrefix adds or updates a routing entry at the specified index with the given value. It returns true if a prefix already existed at that index (indicating an update), false if this is a new insertion.

func (*BartNode[V]) IsEmpty ¶

func (n *BartNode[V]) IsEmpty() bool

IsEmpty returns true if the node contains no routing entries (prefixes) and no child nodes. Empty nodes are candidates for compression or removal during trie optimization.

func (*BartNode[V]) Lookup ¶

func (n *BartNode[V]) Lookup(idx uint8) (val V, ok bool)

Lookup is just a simple wrapper for LookupIdx.

func (*BartNode[V]) LookupIdx ¶

func (n *BartNode[V]) LookupIdx(idx uint8) (top uint8, val V, ok bool)

LookupIdx performs a longest-prefix match (LPM) lookup for the given index (idx) within the 8-bit stride-based prefix table at this trie depth.

The function returns the matched base index, associated value, and true if a matching prefix exists at this level; otherwise, ok is false.

Internally, the prefix table is organized as a complete binary tree (CBT) indexed via the baseIndex function. Unlike the original ART algorithm, this implementation does not use an allotment-based approach. Instead, it performs CBT backtracking using a bitset-based operation with a precomputed backtracking pattern specific to idx.

func (*BartNode[V]) Modify ¶

func (n *BartNode[V]) Modify(pfx netip.Prefix, cb func(val V, found bool) (_ V, del bool)) (delta int)

Modify performs an in-place modification of a prefix using the provided callback function. The callback receives the current value (if found) and existence flag, and returns a new value and deletion flag.

Modify returns the size delta (-1, 0, +1). This method handles path traversal, node creation for new paths, and automatic purge/compress operations after deletions.

Parameters:

• pfx: The network prefix to modify (must be in canonical form)
• cb: Callback function that receives (currentValue, exists) and returns (newValue, deleteFlag)

Returns:

• delta: Size change (-1 for delete, 0 for update/noop, +1 for insert)

func (*BartNode[V]) MustGetChild ¶

func (n *BartNode[V]) MustGetChild(addr uint8) any

MustGetChild retrieves the child at the specified address, panicking if not found. This method should only be used when the caller is certain the child exists.

func (*BartNode[V]) MustGetPrefix ¶

func (n *BartNode[V]) MustGetPrefix(idx uint8) (val V)

MustGetPrefix retrieves the value at the specified index, panicking if not found. This method should only be used when the caller is certain the index exists.

func (*BartNode[V]) Overlaps ¶

func (n *BartNode[V]) Overlaps(o *BartNode[V], depth int) bool

Overlaps recursively compares two trie nodes and returns true if any of their prefixes or descendants overlap.

The implementation checks for: 1. Direct overlapping prefixes on this node level 2. Prefixes in one node overlapping with children in the other 3. Matching child addresses in both nodes, which are recursively compared

All 12 possible type combinations for child entries (node, leaf, fringe) are supported.

The function is optimized for early exit on first match and uses heuristics to choose between set-based and loop-based matching for performance.

func (*BartNode[V]) OverlapsChildrenIn ¶

func (n *BartNode[V]) OverlapsChildrenIn(o *BartNode[V]) bool

OverlapsChildrenIn checks whether the prefixes in node n overlap with any children (by address range) in node o.

Uses bitset intersection or manual iteration heuristically, depending on prefix and child count.

Bitset-based matching uses precomputed coverage tables to avoid per-address looping. This is critical for high fan-out nodes.

func (*BartNode[V]) OverlapsIdx ¶

func (n *BartNode[V]) OverlapsIdx(idx uint8) bool

OverlapsIdx returns true if the given prefix index overlaps with any entry in this node.

The overlap detection considers three categories:

1. Whether any stored prefix in this node covers the requested prefix (LPM test)
2. Whether the requested prefix covers any stored route in the node
3. Whether the requested prefix overlaps with any fringe or child entry

Internally, it leverages precomputed bitsets from the allotment model, using fast bitwise set intersections instead of explicit range comparisons. This enables high-performance overlap checks on a single stride level without descending further into the trie.

func (*BartNode[V]) OverlapsPrefixAtDepth ¶

func (n *BartNode[V]) OverlapsPrefixAtDepth(pfx netip.Prefix, depth int) bool

OverlapsPrefixAtDepth returns true if any route in the subtree rooted at this node overlaps with the given pfx, starting the comparison at the specified depth.

This function supports structural overlap detection even in compressed or sparse paths within the trie, including fringe and leaf nodes. Matching is directional: it returns true if a route fully covers pfx, or if pfx covers an existing route.

At each step, it checks for visible prefixes and children that may intersect the target prefix via stride-based longest-prefix test. The walk terminates early as soon as a structural overlap is found.

This function underlies the top-level OverlapsPrefix behavior and handles details of trie traversal across varying prefix lengths and compression levels.

func (*BartNode[V]) OverlapsRoutes ¶

func (n *BartNode[V]) OverlapsRoutes(o *BartNode[V]) bool

OverlapsRoutes compares the prefix sets of two nodes (n and o).

It first checks for direct bitset intersection (identical indices), then walks both prefix sets using the Contains method to detect if any of the n-prefixes is contained in o, or vice versa.

func (*BartNode[V]) OverlapsSameChildren ¶

func (n *BartNode[V]) OverlapsSameChildren(o *BartNode[V], depth int) bool

OverlapsSameChildren compares all matching child addresses (octets) between node n and node o recursively.

For each shared address, the corresponding child nodes (of any type) are compared using BartNodeOverlapsTwoChildren, which handles all node/leaf/fringe combinations.

func (*BartNode[V]) OverlapsTwoChildren ¶

func (n *BartNode[V]) OverlapsTwoChildren(nChild, oChild any, depth int) bool

OverlapsTwoChildren handles all 3x3 combinations of node kinds (node, leaf, fringe).

3x3 possible different combinations for n and o

node, node    --> overlaps rec descent
node, leaf    --> overlapsPrefixAtDepth
node, fringe  --> true

leaf, node    --> overlapsPrefixAtDepth
leaf, leaf    --> netip.Prefix.Overlaps
leaf, fringe  --> true

fringe, node    --> true
fringe, leaf    --> true
fringe, fringe  --> true

func (*BartNode[V]) PrefixCount ¶

func (n *BartNode[V]) PrefixCount() int

PrefixCount returns the number of prefixes stored in this node.

func (*BartNode[V]) PurgeAndCompress ¶

func (n *BartNode[V]) PurgeAndCompress(stack []*BartNode[V], octets []uint8, is4 bool)

PurgeAndCompress performs bottom-up trie maintenance to restore path compression after a deletion. It unwinds the provided stack of parent nodes, identifying nodes that have become sparse (i.e., containing only a single prefix or a single child node) and prunes them by promoting the underlying entries to the parent level.

This ensures the trie remains memory-efficient by collapsing redundant intermediate nodes back into path-compressed LeafNodes or FringeNodes whenever possible.

Parameters:

• stack: Array of parent nodes to process during bottom-up unwinding.
• octets: The full path of octets leading to the current node.
• is4: True for IPv4 processing, false for IPv6.

func (*BartNode[V]) Stats ¶

func (n *BartNode[V]) Stats() (s StatsT)

Stats returns immediate statistics for n: counts of prefixes and children, and a classification of each child into nodes, leaves, or fringes. It inspects only the direct children of n (not the whole subtree). Panics if a child has an unexpected concrete type.

func (*BartNode[V]) StatsRec ¶

func (n *BartNode[V]) StatsRec() (s StatsT)

StatsRec returns aggregated statistics for the subtree rooted at n.

It walks the node tree recursively and sums immediate counts (prefixes and child slots) plus the number of nodes, leaves, and fringe nodes in the subtree. If n is nil or empty, a zeroed stats is returned. The returned SubNodes count includes the current node. The function will panic if a child has an unexpected concrete type.

func (*BartNode[V]) Subnets ¶

func (n *BartNode[V]) Subnets(pfx netip.Prefix, yield func(netip.Prefix, V) bool)

Subnets yields all subnet prefixes covered by pfx that exist in the trie, in CIDR sort order.

It first locates the trie node corresponding to pfx, then recursively yields all prefixes and child entries contained within that subtree. The traversal uses sorted iteration to maintain canonical CIDR ordering.

The function handles various node types (internal nodes, leaves, and fringes) and uses EachSubnet and AllRecSorted for sorted traversal of covered prefixes.

Parameters:

• pfx: The parent prefix whose subnets should be yielded
• yield: Callback function invoked for each subnet prefix/value pair

The yield function receives prefix/value pairs and returns false to stop the iteration early. If pfx doesn't exist in the trie, no prefixes are yielded.

func (*BartNode[V]) Supernets ¶

func (n *BartNode[V]) Supernets(pfx netip.Prefix, yield func(netip.Prefix, V) bool)

Supernets yields all supernet prefixes of pfx that exist in the trie, in reverse order (most-specific first, least-specific last).

It traverses upward from the given prefix toward the root, collecting matching prefixes along the path. The traversal uses a stack to yield results in reverse order, so that more-specific supernets appear before less-specific ones.

The function handles all node types (internal nodes, leaves, and fringes) and stops early if the yield callback returns false.

Parameters:

• pfx: The prefix for which to find supernets
• yield: Callback function invoked for each supernet prefix/value pair

The yield function receives prefix/value pairs and returns false to stop the iteration early.

func (*BartNode[V]) UnionRec ¶

func (n *BartNode[V]) UnionRec(cloneFn func(V) V, o *BartNode[V], depth int) (duplicates int)

UnionRec recursively merges another node o into the receiver node n.

All prefix and child entries from o are cloned and inserted into n. If a prefix already exists in n, its value is overwritten by the value from o, and the duplicate is counted in the return value. This count can later be used to update size-related metadata in the parent trie.

The union handles all possible combinations of child node types (node, leaf, fringe) between the two nodes. Structural conflicts are resolved by creating new intermediate *BartNode[V] objects and pushing both children further down the trie. Leaves and fringes are also recursively relocated as needed to preserve prefix semantics.

The merge operation is destructive on the receiver n, but leaves the source node o unchanged.

Returns the number of duplicate prefixes that were overwritten during merging.

func (*BartNode[V]) UnionRecPersist ¶

func (n *BartNode[V]) UnionRecPersist(cloneFn func(V) V, o *BartNode[V], depth int) (duplicates int)

UnionRecPersist is similar to unionRec but performs an immutable union of nodes.

func (*FastNode[V]) AllChildren ¶

func (n *FastNode[V]) AllChildren() iter.Seq2[uint8, any]

AllChildren returns an iterator over all child nodes. Each iteration yields the child's address (uint8) and the child node (any).

func (*FastNode[V]) AllIndices ¶

func (n *FastNode[V]) AllIndices() iter.Seq2[uint8, V]

AllIndices returns an iterator over all prefix entries. Each iteration yields the prefix index (uint8) and its associated value (V).

func (*FastNode[V]) AllRec ¶

func (n *FastNode[V]) AllRec(path StridePath, depth int, is4 bool, yield func(netip.Prefix, V) bool) bool

AllRec recursively traverses the trie starting at the current node, applying the provided yield function to every stored prefix and value.

For each route entry (prefix and value), yield is invoked. If yield returns false, the traversal stops immediately, and false is propagated upwards, enabling early termination.

The function handles all prefix entries in the current node, as well as any children - including sub-nodes, leaf nodes with full prefixes, and fringe nodes representing path-compressed prefixes. IP prefix reconstruction is performed on-the-fly from the current path and depth.

The traversal order is not defined. This implementation favors simplicity and runtime efficiency over consistency of iteration sequence.

func (*FastNode[V]) AllRecSorted ¶

func (n *FastNode[V]) AllRecSorted(path StridePath, depth int, is4 bool, yield func(netip.Prefix, V) bool) bool

AllRecSorted recursively traverses the trie in prefix-sorted order and applies the given yield function to each stored prefix and value.

Unlike AllRec, this implementation ensures that route entries are visited in canonical prefix sort order. To achieve this, both the prefixes and children of the current node are gathered, sorted, and then interleaved during traversal based on logical octet positioning.

The function first sorts relevant entries by their prefix index and address value, using a comparison function that ranks prefixes according to their mask length and position. Then it walks the trie, always yielding child entries that fall before the current prefix, followed by the prefix itself. Remaining children are processed once all prefixes have been visited.

Prefixes are reconstructed on-the-fly from the traversal path, and iteration includes all child types: inner nodes (recursive descent), leaf nodes, and fringe (compressed) prefixes.

The order is stable and predictable, making the function suitable for use cases like table exports, comparisons or serialization.

Parameters:

• path: the current traversal path through the trie
• depth: current depth in the trie (0-based)
• is4: true for IPv4 processing, false for IPv6
• yield: callback function invoked for each prefix/value pair

Returns false if yield function requests early termination.

func (*FastNode[V]) ChildCount ¶

func (n *FastNode[V]) ChildCount() int

ChildCount returns the number of slots used in this node.

func (*FastNode[V]) CloneFlat ¶

func (n *FastNode[V]) CloneFlat(cloneFn func(V) V) *FastNode[V]

CloneFlat returns a shallow copy of the current node, optionally performing deep copies of values.

If cloneFn is nil, the stored values in prefixes are copied directly without modification. Otherwise, cloneFn is applied to each stored value for deep cloning. Child nodes are cloned shallowly: LeafNode and FringeNode children are cloned via their clone methods, but child nodes of type *FastNode[V] (subnodes) are assigned as-is without recursive cloning. This method does not recursively clone descendants beyond the immediate children.

Note: The returned node is a new instance with copied slices but only shallow copies of nested nodes, except for LeafNode and FringeNode children which are cloned according to cloneFn.

func (*FastNode[V]) CloneRec ¶

func (n *FastNode[V]) CloneRec(cloneFn func(V) V) *FastNode[V]

CloneRec performs a recursive deep copy of the node and all its descendants.

If cloneFn is nil, the stored values are copied directly without modification. Otherwise cloneFn is applied to each stored value for deep cloning.

This method first creates a shallow clone of the current node using CloneFlat, applying cloneFn to values as described there. Then it recursively clones all child nodes of type *FastNode[V], performing a full deep clone down the subtree.

Child nodes of type *LeafNode[V] and *FringeNode[V] are already cloned by CloneFlat.

Returns a new instance of FastNode[V] which is a complete deep clone of the receiver node with all descendants.

func (*FastNode[V]) Contains ¶

func (n *FastNode[V]) Contains(idx uint8) bool

Contains returns true if an index (idx) has any matching longest-prefix in the current node’s prefix table.

This function performs a presence check without retrieving the associated value. It is faster than a full lookup, as it only tests for intersection with the backtracking bitset for the given index.

The prefix table is structured as a complete binary tree (CBT), and LPM testing is done via a bitset operation that maps the traversal path from the given index toward its possible ancestors.

func (*FastNode[V]) Delete ¶

func (n *FastNode[V]) Delete(pfx netip.Prefix) (exists bool)

Delete removes the prefix from the trie rooted at n and returns true if the prefix existed, false if it was not found. The prefix must be in canonical (masked) form.

The trie uses path compression, so a prefix may be stored in one of three ways:

• In the current node's prefix table when the prefix length aligns exactly with the stride boundary at this depth (depth == strideCount).
• As a path-compressed FringeNode in a child slot for stride-aligned prefixes (e.g. /8, /16, /24); occurs at depth == strideCount-1.
• As a path-compressed LeafNode in a child slot for prefixes otherwise.

After a successful deletion, PurgeAndCompress walks the ancestor stack to prune now-empty nodes and restore path compression upward.

func (*FastNode[V]) DeleteChild ¶

func (n *FastNode[V]) DeleteChild(addr uint8) (exists bool)

DeleteChild removes the child node at the specified address. This operation is idempotent - removing a non-existent child is safe.

func (*FastNode[V]) DeletePersist ¶

func (n *FastNode[V]) DeletePersist(cloneFn func(V) V, pfx netip.Prefix) (exists bool)

DeletePersist removes the prefix from the trie rooted at n using Copy-On-Write (COW) semantics. It returns true if the prefix existed, false if it was not found. The prefix must be in canonical (masked) form.

Like [Delete], this method uses path compression. However, DeletePersist ensures the structural integrity of the existing tree by cloning internal nodes along the descent path (COW) before mutation.

After a successful deletion, PurgeAndCompress walks the ancestor stack to prune now-empty nodes and restore path compression upward.

func (*FastNode[V]) DeletePrefix ¶

func (n *FastNode[V]) DeletePrefix(idx uint8) (exists bool)

DeletePrefix removes the prefix at the specified index. Returns true if the prefix existed, otherwise false.

func (*FastNode[V]) DirectItemsRec ¶

func (n *FastNode[V]) DirectItemsRec(parentIdx uint8, path StridePath, depth int, is4 bool) (directItems []TrieItem[V])

DirectItemsRec, returns the direct covered items by parent. It's a complex recursive function, you have to know the data structure by heart to understand this function!

func (*FastNode[V]) DumpRec ¶

func (n *FastNode[V]) DumpRec(w io.Writer, path StridePath, depth int, is4 bool)

DumpRec recursively descends the trie rooted at n and writes a human-readable representation of each visited node to w.

It returns immediately if n is nil or empty. For each visited internal node it calls dump to write the node's representation, then iterates its child addresses and recurses into children of type *FastNode[V] (internal subnodes). The path slice and depth together represent the byte-wise path from the root to the current node; depth is incremented for each recursion. The is4 flag controls IPv4/IPv6 formatting used by dump.

func (*FastNode[V]) DumpString ¶

func (n *FastNode[V]) DumpString(octets []uint8, depth int, is4 bool) string

DumpString traverses the trie to the node at the specified depth along the given octet path and returns its string representation via Dump.

If the path is invalid or encounters an unexpected node type during traversal, it returns an error message string instead.

Parameters:

• octets: The path of octets to follow from the root
• depth: Target depth to reach before dumping (0-based byte index)
• is4: True for IPv4 formatting, false for IPv6

Returns a formatted string representation of the target node or an error message.

func (*FastNode[V]) EachLookupPrefix ¶

func (n *FastNode[V]) EachLookupPrefix(ip netip.Addr, depth int, pfxIdx uint8, yield func(netip.Prefix, V) bool) (ok bool)

EachLookupPrefix performs a hierarchical lookup of all matching prefixes in the current node’s 8-bit stride-based prefix table.

The function walks up the trie-internal complete binary tree (CBT), testing each possible prefix length mask (in decreasing order of specificity), and invokes the yield function for every matching entry.

The given idx refers to the position for this stride's prefix and is used to derive a backtracking path through the CBT by repeatedly halving the index. At each step, if a prefix exists in the table, its corresponding CIDR is reconstructed and yielded. If yield returns false, traversal stops early.

This function is intended for internal use during supernet traversal and does not descend the trie further.

func (*FastNode[V]) EachSubnet ¶

func (n *FastNode[V]) EachSubnet(octets []byte, depth int, is4 bool, pfxIdx uint8, yield func(netip.Prefix, V) bool) bool

EachSubnet yields all prefix entries and child nodes covered by a given parent prefix, sorted in natural CIDR order, within the current node.

The function iterates through all prefixes and children from the node’s stride tables. Only entries that fall within the address range defined by the parent prefix index (pfxIdx) are included. Matching entries are buffered, sorted, and passed through to the yield function.

Child entries (nodes, leaves, fringes) that fall under the covered address range are processed recursively via AllRecSorted to ensure sorted traversal.

This function is intended for internal use by Subnets(), and it assumes the current node is positioned at the point in the trie corresponding to the parent prefix.

func (*FastNode[V]) EqualRec ¶

func (n *FastNode[V]) EqualRec(o *FastNode[V]) bool

EqualRec performs recursive structural equality comparison between two nodes. Compares prefix and child bitsets, then recursively compares all stored values and child nodes. Returns true if the nodes and their entire subtrees are structurally and semantically identical, false otherwise.

The comparison handles different node types (internal nodes, leafNodes, fringeNodes) and uses the equal function for value comparisons to support custom equality logic.

func (*FastNode[V]) FprintRec ¶

func (n *FastNode[V]) FprintRec(w io.Writer, parent TrieItem[V], pad string) error

FprintRec recursively prints a hierarchical CIDR tree representation starting from this node to the provided writer. The output shows the routing table structure in human-readable format for debugging and analysis.

func (*FastNode[V]) Get ¶

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

Get retrieves the value associated with the given network prefix. Traversal descends through the trie using the prefix's octets.

The lookup handles path compression transparently:

• If the path matches an internal node at the target stride, the value is retrieved from the node's prefix table.
• If the path leads to a compressed LeafNode or FringeNode, the function verifies the prefix match before returning the value.

Parameters:

• pfx: The network prefix to look up (must be in canonical form).

Returns:

• val: The value associated with the prefix (zero value if not found).
• exists: True if the prefix was found, false otherwise.

func (*FastNode[V]) GetChild ¶

func (n *FastNode[V]) GetChild(addr uint8) (any, bool)

GetChild retrieves the child node at the specified address. Returns the child and true if found, or nil and false if not present.

func (*FastNode[V]) GetPrefix ¶

func (n *FastNode[V]) GetPrefix(idx uint8) (val V, exists bool)

GetPrefix retrieves the value associated with the prefix at the given index. Returns the value and true if found, or zero value and false if not present.

func (*FastNode[V]) Insert ¶

func (n *FastNode[V]) Insert(pfx netip.Prefix, val V, depth int) (exists bool)

Insert adds or updates a network prefix and its associated value in the trie. Traversal begins at the specified byte depth.

The trie utilizes path compression to conserve memory. A prefix is inserted:

• Uncompressed into a node's prefix table at depth == strideCount.
• As a path-compressed FringeNode if it qualifies as fringe IsFringe.
• As a path-compressed LeafNode otherwise.

When a new prefix collides with an existing compressed node (Leaf or Fringe), Insert resolves the collision by creating a new intermediate node, pushing the existing entry down to the next level, and continuing traversal.

Parameters:

• pfx: The network prefix to insert (must be in canonical/masked form).
• val: The value to associate with the prefix.
• depth: The current depth in the trie (0-based byte index).

Returns true if an existing prefix was updated, false if a new insertion occurred.

func (*FastNode[V]) InsertChild ¶

func (n *FastNode[V]) InsertChild(addr uint8, child any) (exists bool)

InsertChild adds a child node at the specified address (0-255). The child can be a *FastNode[V], *LeafNode[V], or *FringeNode[V]. Returns true if a child already existed at that address.

func (*FastNode[V]) InsertPersist ¶

func (n *FastNode[V]) InsertPersist(cloneFn func(V) V, pfx netip.Prefix, val V, depth int) (exists bool)

InsertPersist adds or updates a network prefix and its associated value in the trie using Copy-On-Write (COW) semantics. Traversal begins at the specified byte depth.

Unlike [Insert], InsertPersist ensures structural integrity of the existing tree by cloning internal nodes along the descent path (Copy-On-Write) before mutation.

Parameters:

• cloneFn: The function used to clone values (V).
• pfx: The network prefix to insert (must be in canonical/masked form).
• val: The value to associate with the prefix.
• depth: The current depth in the trie (0-based byte index).

Returns true if an existing prefix was updated, false if a new insertion occurred.

func (*FastNode[V]) InsertPrefix ¶

func (n *FastNode[V]) InsertPrefix(idx uint8, val V) (exists bool)

InsertPrefix adds or updates a routing entry at the specified index with the given value. It returns true if a prefix already existed at that index (indicating an update), false if this is a new insertion.

func (*FastNode[V]) IsEmpty ¶

func (n *FastNode[V]) IsEmpty() bool

IsEmpty returns true if the node contains no routing entries (prefixes) and no child nodes. Empty nodes are candidates for compression or removal during trie optimization.

func (*FastNode[V]) Lookup ¶

func (n *FastNode[V]) Lookup(idx uint8) (val V, ok bool)

Lookup is just a simple wrapper for LookupIdx.

func (*FastNode[V]) LookupIdx ¶

func (n *FastNode[V]) LookupIdx(idx uint8) (top uint8, val V, ok bool)

LookupIdx performs a longest-prefix match (LPM) lookup for the given index (idx) within the 8-bit stride-based prefix table at this trie depth.

The function returns the matched base index, associated value, and true if a matching prefix exists at this level; otherwise, ok is false.

Internally, the prefix table is organized as a complete binary tree (CBT) indexed via the baseIndex function. Unlike the original ART algorithm, this implementation does not use an allotment-based approach. Instead, it performs CBT backtracking using a bitset-based operation with a precomputed backtracking pattern specific to idx.

func (*FastNode[V]) Modify ¶

func (n *FastNode[V]) Modify(pfx netip.Prefix, cb func(val V, found bool) (_ V, del bool)) (delta int)

Modify performs an in-place modification of a prefix using the provided callback function. The callback receives the current value (if found) and existence flag, and returns a new value and deletion flag.

Modify returns the size delta (-1, 0, +1). This method handles path traversal, node creation for new paths, and automatic purge/compress operations after deletions.

Parameters:

• pfx: The network prefix to modify (must be in canonical form)
• cb: Callback function that receives (currentValue, exists) and returns (newValue, deleteFlag)

Returns:

• delta: Size change (-1 for delete, 0 for update/noop, +1 for insert)

func (*FastNode[V]) MustGetChild ¶

func (n *FastNode[V]) MustGetChild(addr uint8) any

MustGetChild retrieves the child at addr using the pre-cached rank stored in childRankCache[addr] for a direct O(1) array access without an existence check.

The caller must guarantee that addr is present (Children.Test(addr) == true). If addr is absent, childRankCache[addr] contains the number of occupied addresses less than addr (maintained by InsertChild/DeleteChild), so the behaviour is undefined: either a wrong child is returned silently, or the call panics with an index-out-of-range error.

func (*FastNode[V]) MustGetPrefix ¶

func (n *FastNode[V]) MustGetPrefix(idx uint8) (val V)

MustGetPrefix retrieves the value at the specified index, panicking if not found. This method should only be used when the caller is certain the index exists.

func (*FastNode[V]) Overlaps ¶

func (n *FastNode[V]) Overlaps(o *FastNode[V], depth int) bool

Overlaps recursively compares two trie nodes and returns true if any of their prefixes or descendants overlap.

The implementation checks for: 1. Direct overlapping prefixes on this node level 2. Prefixes in one node overlapping with children in the other 3. Matching child addresses in both nodes, which are recursively compared

All 12 possible type combinations for child entries (node, leaf, fringe) are supported.

The function is optimized for early exit on first match and uses heuristics to choose between set-based and loop-based matching for performance.

func (*FastNode[V]) OverlapsChildrenIn ¶

func (n *FastNode[V]) OverlapsChildrenIn(o *FastNode[V]) bool

OverlapsChildrenIn checks whether the prefixes in node n overlap with any children (by address range) in node o.

Uses bitset intersection or manual iteration heuristically, depending on prefix and child count.

Bitset-based matching uses precomputed coverage tables to avoid per-address looping. This is critical for high fan-out nodes.

func (*FastNode[V]) OverlapsIdx ¶

func (n *FastNode[V]) OverlapsIdx(idx uint8) bool

OverlapsIdx returns true if the given prefix index overlaps with any entry in this node.

The overlap detection considers three categories:

1. Whether any stored prefix in this node covers the requested prefix (LPM test)
2. Whether the requested prefix covers any stored route in the node
3. Whether the requested prefix overlaps with any fringe or child entry

Internally, it leverages precomputed bitsets from the allotment model, using fast bitwise set intersections instead of explicit range comparisons. This enables high-performance overlap checks on a single stride level without descending further into the trie.

func (*FastNode[V]) OverlapsPrefixAtDepth ¶

func (n *FastNode[V]) OverlapsPrefixAtDepth(pfx netip.Prefix, depth int) bool

OverlapsPrefixAtDepth returns true if any route in the subtree rooted at this node overlaps with the given pfx, starting the comparison at the specified depth.

This function supports structural overlap detection even in compressed or sparse paths within the trie, including fringe and leaf nodes. Matching is directional: it returns true if a route fully covers pfx, or if pfx covers an existing route.

At each step, it checks for visible prefixes and children that may intersect the target prefix via stride-based longest-prefix test. The walk terminates early as soon as a structural overlap is found.

This function underlies the top-level OverlapsPrefix behavior and handles details of trie traversal across varying prefix lengths and compression levels.

func (*FastNode[V]) OverlapsRoutes ¶

func (n *FastNode[V]) OverlapsRoutes(o *FastNode[V]) bool

OverlapsRoutes compares the prefix sets of two nodes (n and o).

It first checks for direct bitset intersection (identical indices), then walks both prefix sets using the Contains method to detect if any of the n-prefixes is contained in o, or vice versa.

func (*FastNode[V]) OverlapsSameChildren ¶

func (n *FastNode[V]) OverlapsSameChildren(o *FastNode[V], depth int) bool

OverlapsSameChildren compares all matching child addresses (octets) between node n and node o recursively.

For each shared address, the corresponding child nodes (of any type) are compared using FastNodeOverlapsTwoChildren, which handles all node/leaf/fringe combinations.

func (*FastNode[V]) OverlapsTwoChildren ¶

func (n *FastNode[V]) OverlapsTwoChildren(nChild, oChild any, depth int) bool

OverlapsTwoChildren handles all 3x3 combinations of node kinds (node, leaf, fringe).

3x3 possible different combinations for n and o

node, node    --> overlaps rec descent
node, leaf    --> overlapsPrefixAtDepth
node, fringe  --> true

leaf, node    --> overlapsPrefixAtDepth
leaf, leaf    --> netip.Prefix.Overlaps
leaf, fringe  --> true

fringe, node    --> true
fringe, leaf    --> true
fringe, fringe  --> true

func (*FastNode[V]) PrefixCount ¶

func (n *FastNode[V]) PrefixCount() int

PrefixCount returns the number of prefixes stored in this node.

func (*FastNode[V]) PurgeAndCompress ¶

func (n *FastNode[V]) PurgeAndCompress(stack []*FastNode[V], octets []uint8, is4 bool)

PurgeAndCompress performs bottom-up trie maintenance to restore path compression after a deletion. It unwinds the provided stack of parent nodes, identifying nodes that have become sparse (i.e., containing only a single prefix or a single child node) and prunes them by promoting the underlying entries to the parent level.

This ensures the trie remains memory-efficient by collapsing redundant intermediate nodes back into path-compressed LeafNodes or FringeNodes whenever possible.

Parameters:

• stack: Array of parent nodes to process during bottom-up unwinding.
• octets: The full path of octets leading to the current node.
• is4: True for IPv4 processing, false for IPv6.

func (*FastNode[V]) Stats ¶

func (n *FastNode[V]) Stats() (s StatsT)

Stats returns immediate statistics for n: counts of prefixes and children, and a classification of each child into nodes, leaves, or fringes. It inspects only the direct children of n (not the whole subtree). Panics if a child has an unexpected concrete type.

func (*FastNode[V]) StatsRec ¶

func (n *FastNode[V]) StatsRec() (s StatsT)

StatsRec returns aggregated statistics for the subtree rooted at n.

It walks the node tree recursively and sums immediate counts (prefixes and child slots) plus the number of nodes, leaves, and fringe nodes in the subtree. If n is nil or empty, a zeroed stats is returned. The returned SubNodes count includes the current node. The function will panic if a child has an unexpected concrete type.

func (*FastNode[V]) Subnets ¶

func (n *FastNode[V]) Subnets(pfx netip.Prefix, yield func(netip.Prefix, V) bool)

Subnets yields all subnet prefixes covered by pfx that exist in the trie, in CIDR sort order.

It first locates the trie node corresponding to pfx, then recursively yields all prefixes and child entries contained within that subtree. The traversal uses sorted iteration to maintain canonical CIDR ordering.

The function handles various node types (internal nodes, leaves, and fringes) and uses EachSubnet and AllRecSorted for sorted traversal of covered prefixes.

Parameters:

• pfx: The parent prefix whose subnets should be yielded
• yield: Callback function invoked for each subnet prefix/value pair

The yield function receives prefix/value pairs and returns false to stop the iteration early. If pfx doesn't exist in the trie, no prefixes are yielded.

func (*FastNode[V]) Supernets ¶

func (n *FastNode[V]) Supernets(pfx netip.Prefix, yield func(netip.Prefix, V) bool)

Supernets yields all supernet prefixes of pfx that exist in the trie, in reverse order (most-specific first, least-specific last).

It traverses upward from the given prefix toward the root, collecting matching prefixes along the path. The traversal uses a stack to yield results in reverse order, so that more-specific supernets appear before less-specific ones.

The function handles all node types (internal nodes, leaves, and fringes) and stops early if the yield callback returns false.

Parameters:

• pfx: The prefix for which to find supernets
• yield: Callback function invoked for each supernet prefix/value pair

The yield function receives prefix/value pairs and returns false to stop the iteration early.

func (*FastNode[V]) UnionRec ¶

func (n *FastNode[V]) UnionRec(cloneFn func(V) V, o *FastNode[V], depth int) (duplicates int)

UnionRec recursively merges another node o into the receiver node n.

All prefix and child entries from o are cloned and inserted into n. If a prefix already exists in n, its value is overwritten by the value from o, and the duplicate is counted in the return value. This count can later be used to update size-related metadata in the parent trie.

The union handles all possible combinations of child node types (node, leaf, fringe) between the two nodes. Structural conflicts are resolved by creating new intermediate *FastNode[V] objects and pushing both children further down the trie. Leaves and fringes are also recursively relocated as needed to preserve prefix semantics.

The merge operation is destructive on the receiver n, but leaves the source node o unchanged.

Returns the number of duplicate prefixes that were overwritten during merging.

func (*FastNode[V]) UnionRecPersist ¶

func (n *FastNode[V]) UnionRecPersist(cloneFn func(V) V, o *FastNode[V], depth int) (duplicates int)

UnionRecPersist is similar to unionRec but performs an immutable union of nodes.

func (*FringeNode[V]) CloneFringe ¶

func (l *FringeNode[V]) CloneFringe(cloneFn func(V) V) *FringeNode[V]

CloneFringe creates and returns a copy of the FringeNode receiver. If cloneFn is nil, the value is copied directly without modification. Otherwise, cloneFn is applied to the value for deep cloning.

func (*LeafNode[V]) CloneLeaf ¶

func (l *LeafNode[V]) CloneLeaf(cloneFn func(V) V) *LeafNode[V]

CloneLeaf creates and returns a copy of the leafNode receiver. If cloneFn is nil, the value is copied directly without modification. Otherwise, cloneFn is applied to the value for deep cloning. The prefix field is always copied as is.

func (*LiteNode[V]) AllChildren ¶

func (n *LiteNode[V]) AllChildren() iter.Seq2[uint8, any]

AllChildren returns an iterator over all child nodes. Each iteration yields the child's address (uint8) and the child node (any).

func (*LiteNode[V]) AllIndices ¶

func (n *LiteNode[V]) AllIndices() iter.Seq2[uint8, V]

AllIndices returns an iterator over all prefix entries. Each iteration yields the prefix index (uint8) and its associated value (V).

func (*LiteNode[V]) AllRec ¶

func (n *LiteNode[V]) AllRec(path StridePath, depth int, is4 bool, yield func(netip.Prefix, V) bool) bool

AllRec recursively traverses the trie starting at the current node, applying the provided yield function to every stored prefix and value.

For each route entry (prefix and value), yield is invoked. If yield returns false, the traversal stops immediately, and false is propagated upwards, enabling early termination.

The function handles all prefix entries in the current node, as well as any children - including sub-nodes, leaf nodes with full prefixes, and fringe nodes representing path-compressed prefixes. IP prefix reconstruction is performed on-the-fly from the current path and depth.

The traversal order is not defined. This implementation favors simplicity and runtime efficiency over consistency of iteration sequence.

func (*LiteNode[V]) AllRecSorted ¶

func (n *LiteNode[V]) AllRecSorted(path StridePath, depth int, is4 bool, yield func(netip.Prefix, V) bool) bool

AllRecSorted recursively traverses the trie in prefix-sorted order and applies the given yield function to each stored prefix and value.

Unlike AllRec, this implementation ensures that route entries are visited in canonical prefix sort order. To achieve this, both the prefixes and children of the current node are gathered, sorted, and then interleaved during traversal based on logical octet positioning.

The function first sorts relevant entries by their prefix index and address value, using a comparison function that ranks prefixes according to their mask length and position. Then it walks the trie, always yielding child entries that fall before the current prefix, followed by the prefix itself. Remaining children are processed once all prefixes have been visited.

Prefixes are reconstructed on-the-fly from the traversal path, and iteration includes all child types: inner nodes (recursive descent), leaf nodes, and fringe (compressed) prefixes.

The order is stable and predictable, making the function suitable for use cases like table exports, comparisons or serialization.

Parameters:

• path: the current traversal path through the trie
• depth: current depth in the trie (0-based)
• is4: true for IPv4 processing, false for IPv6
• yield: callback function invoked for each prefix/value pair

Returns false if yield function requests early termination.

func (*LiteNode[V]) ChildCount ¶

func (n *LiteNode[V]) ChildCount() int

ChildCount returns the number of slots used in this node.

func (*LiteNode[V]) CloneFlat ¶

func (n *LiteNode[V]) CloneFlat(_ func(V) V) *LiteNode[V]

CloneFlat returns a shallow copy of the current node.

CloneFn is only used for interface satisfaction.

func (*LiteNode[V]) CloneRec ¶

func (n *LiteNode[V]) CloneRec(_ func(V) V) *LiteNode[V]

CloneRec performs a recursive deep copy of the node and all its descendants.

cloneFn is only used for interface satisfaction.

It first creates a shallow clone of the current node using CloneFlat. Then it recursively clones all child nodes of type *LiteNode[V], performing a full deep clone down the subtree.

Child nodes of type *LeafNode and *FringeNode are already copied by CloneFlat.

Returns a new instance of LiteNode[V] which is a complete deep clone of the receiver node with all descendants.

func (*LiteNode[V]) Contains ¶

func (n *LiteNode[V]) Contains(idx uint8) bool

Contains returns true if an index (idx) has any matching longest-prefix in the current node’s prefix table.

This function performs a presence check.

The prefix table is structured as a complete binary tree (CBT), and LPM testing is done via a bitset operation that maps the traversal path from the given index toward its possible ancestors.

func (*LiteNode[V]) Delete ¶

func (n *LiteNode[V]) Delete(pfx netip.Prefix) (exists bool)

Delete removes the prefix from the trie rooted at n and returns true if the prefix existed, false if it was not found. The prefix must be in canonical (masked) form.

The trie uses path compression, so a prefix may be stored in one of three ways:

• In the current node's prefix table when the prefix length aligns exactly with the stride boundary at this depth (depth == strideCount).
• As a path-compressed FringeNode in a child slot for stride-aligned prefixes (e.g. /8, /16, /24); occurs at depth == strideCount-1.
• As a path-compressed LeafNode in a child slot for prefixes otherwise.

After a successful deletion, PurgeAndCompress walks the ancestor stack to prune now-empty nodes and restore path compression upward.

func (*LiteNode[V]) DeleteChild ¶

func (n *LiteNode[V]) DeleteChild(addr uint8) (exists bool)

DeleteChild removes the child node at the specified address. This operation is idempotent - removing a non-existent child is safe.

func (*LiteNode[V]) DeletePersist ¶

func (n *LiteNode[V]) DeletePersist(cloneFn func(V) V, pfx netip.Prefix) (exists bool)

DeletePersist removes the prefix from the trie rooted at n using Copy-On-Write (COW) semantics. It returns true if the prefix existed, false if it was not found. The prefix must be in canonical (masked) form.

Like [Delete], this method uses path compression. However, DeletePersist ensures the structural integrity of the existing tree by cloning internal nodes along the descent path (COW) before mutation.

After a successful deletion, PurgeAndCompress walks the ancestor stack to prune now-empty nodes and restore path compression upward.

func (*LiteNode[V]) DeletePrefix ¶

func (n *LiteNode[V]) DeletePrefix(idx uint8) (exists bool)

DeletePrefix removes the prefix at the specified index. Returns true if the prefix existed, and false otherwise.

func (*LiteNode[V]) DirectItemsRec ¶

func (n *LiteNode[V]) DirectItemsRec(parentIdx uint8, path StridePath, depth int, is4 bool) (directItems []TrieItem[V])

DirectItemsRec, returns the direct covered items by parent. It's a complex recursive function, you have to know the data structure by heart to understand this function!

func (*LiteNode[V]) DumpRec ¶

func (n *LiteNode[V]) DumpRec(w io.Writer, path StridePath, depth int, is4 bool)

DumpRec recursively descends the trie rooted at n and writes a human-readable representation of each visited node to w.

It returns immediately if n is nil or empty. For each visited internal node it calls dump to write the node's representation, then iterates its child addresses and recurses into children of type *LiteNode[V] (internal subnodes). The path slice and depth together represent the byte-wise path from the root to the current node; depth is incremented for each recursion. The is4 flag controls IPv4/IPv6 formatting used by dump.

func (*LiteNode[V]) DumpString ¶

func (n *LiteNode[V]) DumpString(octets []uint8, depth int, is4 bool) string

DumpString traverses the trie to the node at the specified depth along the given octet path and returns its string representation via Dump.

If the path is invalid or encounters an unexpected node type during traversal, it returns an error message string instead.

Parameters:

• octets: The path of octets to follow from the root
• depth: Target depth to reach before dumping (0-based byte index)
• is4: True for IPv4 formatting, false for IPv6

Returns a formatted string representation of the target node or an error message.

func (*LiteNode[V]) EachLookupPrefix ¶

func (n *LiteNode[V]) EachLookupPrefix(ip netip.Addr, depth int, pfxIdx uint8, yield func(netip.Prefix, V) bool) (ok bool)

EachLookupPrefix performs a hierarchical lookup of all matching prefixes in the current node’s 8-bit stride-based prefix table.

The function walks up the trie-internal complete binary tree (CBT), testing each possible prefix length mask (in decreasing order of specificity), and invokes the yield function for every matching entry.

The given idx refers to the position for this stride's prefix and is used to derive a backtracking path through the CBT by repeatedly halving the index. At each step, if a prefix exists in the table, its corresponding CIDR is reconstructed and yielded. If yield returns false, traversal stops early.

This function is intended for internal use during supernet traversal and does not descend the trie further.

func (*LiteNode[V]) EachSubnet ¶

func (n *LiteNode[V]) EachSubnet(octets []byte, depth int, is4 bool, pfxIdx uint8, yield func(netip.Prefix, V) bool) bool

EachSubnet yields all prefix entries and child nodes covered by a given parent prefix, sorted in natural CIDR order, within the current node.

The function iterates through all prefixes and children from the node’s stride tables. Only entries that fall within the address range defined by the parent prefix index (pfxIdx) are included. Matching entries are buffered, sorted, and passed through to the yield function.

Child entries (nodes, leaves, fringes) that fall under the covered address range are processed recursively via AllRecSorted to ensure sorted traversal.

This function is intended for internal use by Subnets(), and it assumes the current node is positioned at the point in the trie corresponding to the parent prefix.

func (*LiteNode[V]) EqualRec ¶

func (n *LiteNode[V]) EqualRec(o *LiteNode[V]) bool

EqualRec performs recursive structural equality comparison between two nodes. Compares prefix and child bitsets, then recursively compares all stored values and child nodes. Returns true if the nodes and their entire subtrees are structurally and semantically identical, false otherwise.

The comparison handles different node types (internal nodes, leafNodes, fringeNodes) and uses the equal function for value comparisons to support custom equality logic.

func (*LiteNode[V]) FprintRec ¶

func (n *LiteNode[V]) FprintRec(w io.Writer, parent TrieItem[V], pad string) error

FprintRec recursively prints a hierarchical CIDR tree representation starting from this node to the provided writer. The output shows the routing table structure in human-readable format for debugging and analysis.

func (*LiteNode[V]) Get ¶

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

Get retrieves the value associated with the given network prefix. Traversal descends through the trie using the prefix's octets.

The lookup handles path compression transparently:

• If the path matches an internal node at the target stride, the value is retrieved from the node's prefix table.
• If the path leads to a compressed LeafNode or FringeNode, the function verifies the prefix match before returning the value.

Parameters:

• pfx: The network prefix to look up (must be in canonical form).

Returns:

• val: The value associated with the prefix (zero value if not found).
• exists: True if the prefix was found, false otherwise.

func (*LiteNode[V]) GetChild ¶

func (n *LiteNode[V]) GetChild(addr uint8) (any, bool)

GetChild retrieves the child node at the specified address. Returns the child and true if found, or nil and false if not present.

func (*LiteNode[V]) GetPrefix ¶

func (n *LiteNode[V]) GetPrefix(idx uint8) (_ V, exists bool)

func (*LiteNode[V]) Insert ¶

func (n *LiteNode[V]) Insert(pfx netip.Prefix, val V, depth int) (exists bool)

Insert adds or updates a network prefix and its associated value in the trie. Traversal begins at the specified byte depth.

The trie utilizes path compression to conserve memory. A prefix is inserted:

• Uncompressed into a node's prefix table at depth == strideCount.
• As a path-compressed FringeNode if it qualifies as fringe IsFringe.
• As a path-compressed LeafNode otherwise.

When a new prefix collides with an existing compressed node (Leaf or Fringe), Insert resolves the collision by creating a new intermediate node, pushing the existing entry down to the next level, and continuing traversal.

Parameters:

• pfx: The network prefix to insert (must be in canonical/masked form).
• val: The value to associate with the prefix.
• depth: The current depth in the trie (0-based byte index).

Returns true if an existing prefix was updated, false if a new insertion occurred.

func (*LiteNode[V]) InsertChild ¶

func (n *LiteNode[V]) InsertChild(addr uint8, child any) (exists bool)

InsertChild adds a child node at the specified address (0-255). The child can be a *LiteNode[V], *LeafNode, or *FringeNode. Returns true if a child already existed at that address.

func (*LiteNode[V]) InsertPersist ¶

func (n *LiteNode[V]) InsertPersist(cloneFn func(V) V, pfx netip.Prefix, val V, depth int) (exists bool)

InsertPersist adds or updates a network prefix and its associated value in the trie using Copy-On-Write (COW) semantics. Traversal begins at the specified byte depth.

Unlike [Insert], InsertPersist ensures structural integrity of the existing tree by cloning internal nodes along the descent path (Copy-On-Write) before mutation.

Parameters:

• cloneFn: The function used to clone values (V).
• pfx: The network prefix to insert (must be in canonical/masked form).
• val: The value to associate with the prefix.
• depth: The current depth in the trie (0-based byte index).

Returns true if an existing prefix was updated, false if a new insertion occurred.

func (*LiteNode[V]) InsertPrefix ¶

func (n *LiteNode[V]) InsertPrefix(idx uint8, _ V) (exists bool)

InsertPrefix adds a routing entry at the specified index. It returns true if a prefix already existed at that index, false if this is a new insertion.

func (*LiteNode[V]) IsEmpty ¶

func (n *LiteNode[V]) IsEmpty() bool

IsEmpty returns true if the node contains no routing entries (prefixes) and no child nodes. Empty nodes are candidates for compression or removal during trie optimization.

func (*LiteNode[V]) Lookup ¶

func (n *LiteNode[V]) Lookup(idx uint8) (_ V, ok bool)

Lookup is just a simple wrapper for LookupIdx.

func (*LiteNode[V]) LookupIdx ¶

func (n *LiteNode[V]) LookupIdx(idx uint8) (top uint8, _ V, ok bool)

LookupIdx performs a longest-prefix match (LPM) lookup for the given index (idx) within the 8-bit stride-based prefix table at this trie depth.

The function returns the matched index and whether a matching prefix exists at this level. The value type parameter exists only to satisfy interfaces.

Internally, the prefix table is organized as a complete binary tree (CBT) indexed via the baseIndex function. Unlike the original ART algorithm, this implementation does not use an allotment-based approach. Instead, it performs CBT backtracking using a bitset-based operation with a precomputed backtracking pattern specific to idx.

func (*LiteNode[V]) Modify ¶

func (n *LiteNode[V]) Modify(pfx netip.Prefix, cb func(val V, found bool) (_ V, del bool)) (delta int)

Modify performs an in-place modification of a prefix using the provided callback function. The callback receives the current value (if found) and existence flag, and returns a new value and deletion flag.

Modify returns the size delta (-1, 0, +1). This method handles path traversal, node creation for new paths, and automatic purge/compress operations after deletions.

Parameters:

• pfx: The network prefix to modify (must be in canonical form)
• cb: Callback function that receives (currentValue, exists) and returns (newValue, deleteFlag)

Returns:

• delta: Size change (-1 for delete, 0 for update/noop, +1 for insert)

func (*LiteNode[V]) MustGetChild ¶

func (n *LiteNode[V]) MustGetChild(addr uint8) any

MustGetChild retrieves the child at the specified address, panicking if not found. This method should only be used when the caller is certain the child exists.

func (*LiteNode[V]) MustGetPrefix ¶

func (n *LiteNode[V]) MustGetPrefix(idx uint8) (_ V)

func (*LiteNode[V]) Overlaps ¶

func (n *LiteNode[V]) Overlaps(o *LiteNode[V], depth int) bool

Overlaps recursively compares two trie nodes and returns true if any of their prefixes or descendants overlap.

The implementation checks for: 1. Direct overlapping prefixes on this node level 2. Prefixes in one node overlapping with children in the other 3. Matching child addresses in both nodes, which are recursively compared

All 12 possible type combinations for child entries (node, leaf, fringe) are supported.

The function is optimized for early exit on first match and uses heuristics to choose between set-based and loop-based matching for performance.

func (*LiteNode[V]) OverlapsChildrenIn ¶

func (n *LiteNode[V]) OverlapsChildrenIn(o *LiteNode[V]) bool

OverlapsChildrenIn checks whether the prefixes in node n overlap with any children (by address range) in node o.

Uses bitset intersection or manual iteration heuristically, depending on prefix and child count.

Bitset-based matching uses precomputed coverage tables to avoid per-address looping. This is critical for high fan-out nodes.

func (*LiteNode[V]) OverlapsIdx ¶

func (n *LiteNode[V]) OverlapsIdx(idx uint8) bool

OverlapsIdx returns true if the given prefix index overlaps with any entry in this node.

The overlap detection considers three categories:

1. Whether any stored prefix in this node covers the requested prefix (LPM test)
2. Whether the requested prefix covers any stored route in the node
3. Whether the requested prefix overlaps with any fringe or child entry

Internally, it leverages precomputed bitsets from the allotment model, using fast bitwise set intersections instead of explicit range comparisons. This enables high-performance overlap checks on a single stride level without descending further into the trie.

func (*LiteNode[V]) OverlapsPrefixAtDepth ¶

func (n *LiteNode[V]) OverlapsPrefixAtDepth(pfx netip.Prefix, depth int) bool

OverlapsPrefixAtDepth returns true if any route in the subtree rooted at this node overlaps with the given pfx, starting the comparison at the specified depth.

This function supports structural overlap detection even in compressed or sparse paths within the trie, including fringe and leaf nodes. Matching is directional: it returns true if a route fully covers pfx, or if pfx covers an existing route.

At each step, it checks for visible prefixes and children that may intersect the target prefix via stride-based longest-prefix test. The walk terminates early as soon as a structural overlap is found.

This function underlies the top-level OverlapsPrefix behavior and handles details of trie traversal across varying prefix lengths and compression levels.

func (*LiteNode[V]) OverlapsRoutes ¶

func (n *LiteNode[V]) OverlapsRoutes(o *LiteNode[V]) bool

OverlapsRoutes compares the prefix sets of two nodes (n and o).

It first checks for direct bitset intersection (identical indices), then walks both prefix sets using the Contains method to detect if any of the n-prefixes is contained in o, or vice versa.

func (*LiteNode[V]) OverlapsSameChildren ¶

func (n *LiteNode[V]) OverlapsSameChildren(o *LiteNode[V], depth int) bool

OverlapsSameChildren compares all matching child addresses (octets) between node n and node o recursively.

For each shared address, the corresponding child nodes (of any type) are compared using LiteNodeOverlapsTwoChildren, which handles all node/leaf/fringe combinations.

func (*LiteNode[V]) OverlapsTwoChildren ¶

func (n *LiteNode[V]) OverlapsTwoChildren(nChild, oChild any, depth int) bool

OverlapsTwoChildren handles all 3x3 combinations of node kinds (node, leaf, fringe).

3x3 possible different combinations for n and o

node, node    --> overlaps rec descent
node, leaf    --> overlapsPrefixAtDepth
node, fringe  --> true

leaf, node    --> overlapsPrefixAtDepth
leaf, leaf    --> netip.Prefix.Overlaps
leaf, fringe  --> true

fringe, node    --> true
fringe, leaf    --> true
fringe, fringe  --> true

func (*LiteNode[V]) PrefixCount ¶

func (n *LiteNode[V]) PrefixCount() int

PrefixCount returns the number of prefixes stored in this node.

func (*LiteNode[V]) PurgeAndCompress ¶

func (n *LiteNode[V]) PurgeAndCompress(stack []*LiteNode[V], octets []uint8, is4 bool)

PurgeAndCompress performs bottom-up trie maintenance to restore path compression after a deletion. It unwinds the provided stack of parent nodes, identifying nodes that have become sparse (i.e., containing only a single prefix or a single child node) and prunes them by promoting the underlying entries to the parent level.

This ensures the trie remains memory-efficient by collapsing redundant intermediate nodes back into path-compressed LeafNodes or FringeNodes whenever possible.

Parameters:

• stack: Array of parent nodes to process during bottom-up unwinding.
• octets: The full path of octets leading to the current node.
• is4: True for IPv4 processing, false for IPv6.

func (*LiteNode[V]) Stats ¶

func (n *LiteNode[V]) Stats() (s StatsT)

Stats returns immediate statistics for n: counts of prefixes and children, and a classification of each child into nodes, leaves, or fringes. It inspects only the direct children of n (not the whole subtree). Panics if a child has an unexpected concrete type.

func (*LiteNode[V]) StatsRec ¶

func (n *LiteNode[V]) StatsRec() (s StatsT)

StatsRec returns aggregated statistics for the subtree rooted at n.

It walks the node tree recursively and sums immediate counts (prefixes and child slots) plus the number of nodes, leaves, and fringe nodes in the subtree. If n is nil or empty, a zeroed stats is returned. The returned SubNodes count includes the current node. The function will panic if a child has an unexpected concrete type.

func (*LiteNode[V]) Subnets ¶

func (n *LiteNode[V]) Subnets(pfx netip.Prefix, yield func(netip.Prefix, V) bool)

Subnets yields all subnet prefixes covered by pfx that exist in the trie, in CIDR sort order.

It first locates the trie node corresponding to pfx, then recursively yields all prefixes and child entries contained within that subtree. The traversal uses sorted iteration to maintain canonical CIDR ordering.

The function handles various node types (internal nodes, leaves, and fringes) and uses EachSubnet and AllRecSorted for sorted traversal of covered prefixes.

Parameters:

• pfx: The parent prefix whose subnets should be yielded
• yield: Callback function invoked for each subnet prefix/value pair

The yield function receives prefix/value pairs and returns false to stop the iteration early. If pfx doesn't exist in the trie, no prefixes are yielded.

func (*LiteNode[V]) Supernets ¶

func (n *LiteNode[V]) Supernets(pfx netip.Prefix, yield func(netip.Prefix, V) bool)

Supernets yields all supernet prefixes of pfx that exist in the trie, in reverse order (most-specific first, least-specific last).

It traverses upward from the given prefix toward the root, collecting matching prefixes along the path. The traversal uses a stack to yield results in reverse order, so that more-specific supernets appear before less-specific ones.

The function handles all node types (internal nodes, leaves, and fringes) and stops early if the yield callback returns false.

Parameters:

• pfx: The prefix for which to find supernets
• yield: Callback function invoked for each supernet prefix/value pair

The yield function receives prefix/value pairs and returns false to stop the iteration early.

func (*LiteNode[V]) UnionRec ¶

func (n *LiteNode[V]) UnionRec(cloneFn func(V) V, o *LiteNode[V], depth int) (duplicates int)

UnionRec recursively merges another node o into the receiver node n.

All prefix and child entries from o are cloned and inserted into n. If a prefix already exists in n, its value is overwritten by the value from o, and the duplicate is counted in the return value. This count can later be used to update size-related metadata in the parent trie.

The union handles all possible combinations of child node types (node, leaf, fringe) between the two nodes. Structural conflicts are resolved by creating new intermediate *LiteNode[V] objects and pushing both children further down the trie. Leaves and fringes are also recursively relocated as needed to preserve prefix semantics.

The merge operation is destructive on the receiver n, but leaves the source node o unchanged.

Returns the number of duplicate prefixes that were overwritten during merging.

func (*LiteNode[V]) UnionRecPersist ¶

func (n *LiteNode[V]) UnionRecPersist(cloneFn func(V) V, o *LiteNode[V], depth int) (duplicates int)

UnionRecPersist is similar to unionRec but performs an immutable union of nodes.