lpm

package
v0.0.3 Latest Latest
Warning

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

Go to latest
Published: Nov 6, 2025 License: MIT Imports: 1 Imported by: 0

Documentation

Overview

Package lpm (longest-prefix-match) contains the lookup table with which the backtracking for the lpm in the complete binary tree of the prefixes can be replaced by a fast bitset operation.

Index

Constants

This section is empty.

Variables

View Source
var LookupTbl = [256]bitset.BitSet256{}/* 256 elements not displayed */

LookupTbl is a precomputed read‑only table used in hot paths.

It allows a one-shot bitset intersection algorithm: Each entry i encodes i and all its binary ancestors (i>>1, i>>2, ...).

idx must be the uint8 produced by art.OctetToIdx or art.PfxToIdx (0 is invalid).

Usage:

func (n *bartNode[V]) contains(idx uint8) bool {
	return n.prefixes.Intersects(&lpm.LookupTbl[idx])
}

instead of a sequence of single bitset tests:

func (n *bartNode[V]) contains(idx uint8) bool {
	for ; idx > 0; idx >>= 1 {
		if n.prefixes.Test(idx) {
			return true
		}
	}
	return false
}

DO NOT MUTATE: Precomputed read‑only table used in hot paths.

Functions

This section is empty.

Types

This section is empty.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL