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 value.CloneFunc[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 value.CloneFunc[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 deletes the prefix and returns true if the prefix existed, or false otherwise. The prefix must be in canonical form.

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 value.CloneFunc[V], pfx netip.Prefix) (exists bool)

DeletePersist is similar to delete but does not mutate the original trie. Assumes the caller has pre-cloned the root (COW). It clones the internal nodes along the descent path before mutating them.

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 that implement nodeDumper[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. Returns the stored value and true if the prefix exists in this node, zero value and false if the prefix is not found.

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 inserts a network prefix and its associated value into the trie starting at the specified byte depth.

The function traverses the prefix address from the given depth and inserts the value either directly into the node's prefix table or as a compressed leaf or fringe node. If a conflicting leaf or fringe exists, it creates a new intermediate node to accommodate both entries.

Parameters:

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

Returns true if a prefix already existed and was updated, false for new insertions.

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 value.CloneFunc[V], pfx netip.Prefix, val V, depth int) (exists bool)

InsertPersist is similar to insert but the receiver isn't modified. Assumes the caller has pre-cloned the root (COW). It clones the internal nodes along the descent path before mutating them.

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 lpmTest 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 compression of the trie.

The function unwinds the provided stack of parent nodes, checking each level for compression opportunities based on child and prefix count. It may convert:

• Nodes with a single prefix into leaf one level above.
• Nodes with a single leaf or fringe into leaf one level above.

Parameters:

• stack: Array of parent nodes to process during unwinding
• octets: The path of octets taken to reach the current position
• 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 stats.nodes 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 value.CloneFunc[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 value.CloneFunc[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 value.CloneFunc[V]) *FastNode[V]

CloneFlat returns a shallow copy of the current FastNode[V], Its semantics are identical to [bartNode.CloneFlat] but the implementation is more complex.

func (*FastNode[V]) CloneRec ¶

func (n *FastNode[V]) CloneRec(cloneFn value.CloneFunc[V]) *FastNode[V]

CloneRec performs a recursive deep copy of the FastNode[V] and all its descendants. Its semantics are identical to [bartNode.cloneRec].

func (*FastNode[V]) Contains ¶

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

Contains returns true if the given index has any matching longest-prefix in the current node's prefix table.

This function performs a presence check using the ART algorithm's hierarchical prefix structure. It tests whether any ancestor prefix exists for the given index by probing the slot at idx (children inherit ancestor pointers via allot).

func (*FastNode[V]) Delete ¶

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

Delete deletes the prefix and returns true if the prefix existed, or false otherwise. The prefix must be in canonical form.

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 value.CloneFunc[V], pfx netip.Prefix) (exists bool)

DeletePersist is similar to delete but does not mutate the original trie. Assumes the caller has pre-cloned the root (COW). It clones the internal nodes along the descent path before mutating them.

func (*FastNode[V]) DeletePrefix ¶

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

DeletePrefix removes the route at the given 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 that implement nodeDumper[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. Returns the stored value and true if the prefix exists in this node, zero value and false if the prefix is not found.

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 returns the child node at the specified address and true if it exists. If no child exists at addr, returns nil and false.

func (*FastNode[V]) GetPrefix ¶

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

GetPrefix returns the value for the given prefix index and true if it exists. If no prefix exists at idx, returns the zero value and false.

func (*FastNode[V]) Insert ¶

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

Insert inserts a network prefix and its associated value into the trie starting at the specified byte depth.

The function traverses the prefix address from the given depth and inserts the value either directly into the node's prefix table or as a compressed leaf or fringe node. If a conflicting leaf or fringe exists, it creates a new intermediate node to accommodate both entries.

Parameters:

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

Returns true if a prefix already existed and was updated, false for new insertions.

func (*FastNode[V]) InsertChild ¶

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

InsertChild inserts a child node at the specified address. Returns true if a child already existed at addr (overwrite case), false if this is a new insertion.

func (*FastNode[V]) InsertPersist ¶

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

InsertPersist is similar to insert but the receiver isn't modified. Assumes the caller has pre-cloned the root (COW). It clones the internal nodes along the descent path before mutating them.

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 node has neither prefixes nor children

func (*FastNode[V]) Lookup ¶

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

Lookup performs a longest-prefix match (LPM) Lookup for the given index within the current node's prefix table in O(1).

The function returns the matched value and true if a matching prefix exists; otherwise, it returns the zero value and false. The Lookup uses the ART algorithm's hierarchical structure to find the most specific matching prefix.

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.

Its semantics are identical to [node.LookupIdx].

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 returns the child node at the specified address. Panics if no child exists at addr. This method should only be called when the caller has verified the child exists.

func (*FastNode[V]) MustGetPrefix ¶

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

MustGetPrefix returns the value for the given prefix index. Panics if no prefix exists at idx. This method should only be called when the caller has verified the prefix 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 lpmTest 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 compression of the trie.

The function unwinds the provided stack of parent nodes, checking each level for compression opportunities based on child and prefix count. It may convert:

• Nodes with a single prefix into leaf one level above.
• Nodes with a single leaf or fringe into leaf one level above.

Parameters:

• stack: Array of parent nodes to process during unwinding
• octets: The path of octets taken to reach the current position
• 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 stats.nodes 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 value.CloneFunc[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 value.CloneFunc[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 value.CloneFunc[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 value.CloneFunc[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(_ value.CloneFunc[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(_ value.CloneFunc[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 deletes the prefix and returns true if the prefix existed, or false otherwise. The prefix must be in canonical form.

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 value.CloneFunc[V], pfx netip.Prefix) (exists bool)

DeletePersist is similar to delete but does not mutate the original trie. Assumes the caller has pre-cloned the root (COW). It clones the internal nodes along the descent path before mutating them.

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 that implement nodeDumper[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. Returns the stored value and true if the prefix exists in this node, zero value and false if the prefix is not found.

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)

prefix is set at the given index.

func (*LiteNode[V]) Insert ¶

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

Insert inserts a network prefix and its associated value into the trie starting at the specified byte depth.

The function traverses the prefix address from the given depth and inserts the value either directly into the node's prefix table or as a compressed leaf or fringe node. If a conflicting leaf or fringe exists, it creates a new intermediate node to accommodate both entries.

Parameters:

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

Returns true if a prefix already existed and was updated, false for new insertions.

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 value.CloneFunc[V], pfx netip.Prefix, val V, depth int) (exists bool)

InsertPersist is similar to insert but the receiver isn't modified. Assumes the caller has pre-cloned the root (COW). It clones the internal nodes along the descent path before mutating them.

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 lpmTest 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 compression of the trie.

The function unwinds the provided stack of parent nodes, checking each level for compression opportunities based on child and prefix count. It may convert:

• Nodes with a single prefix into leaf one level above.
• Nodes with a single leaf or fringe into leaf one level above.

Parameters:

• stack: Array of parent nodes to process during unwinding
• octets: The path of octets taken to reach the current position
• 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 stats.nodes 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 value.CloneFunc[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 value.CloneFunc[V], o *LiteNode[V], depth int) (duplicates int)

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