lpm

func BackTrackingBitset ¶

func BackTrackingBitset(idx uint) *bitset.BitSet256

BackTrackingBitset is the backtracking sequence in the complete binary tree of the prefixes (mapped by the base_index function) as bitstring.

for idx := 1; idx > 0; idx >>= 1 { b.Set(idx) }

allows a one shot bitset intersection algorithm:

func (n *node[V]) lpmTest(idx uint) bool {
	return n.prefixes.IntersectsAny(lpmbt.LookupTbl[idx])
}

instead of a sequence of single bitset tests:

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