bitlpm

Documentation

Index

• type CIDRTrie
  • func NewCIDRTrie[T any]() *CIDRTrie[T]
  • func (c *CIDRTrie[T]) AncestorIterator(cidr netip.Prefix) Iterator[Key[netip.Prefix], T]
  • func (c *CIDRTrie[T]) AncestorLongestPrefixFirstIterator(cidr netip.Prefix) Iterator[Key[netip.Prefix], T]
  • func (c *CIDRTrie[T]) Ancestors(cidr netip.Prefix, fn func(k netip.Prefix, v T) bool)
  • func (c *CIDRTrie[T]) AncestorsLongestPrefixFirst(cidr netip.Prefix, fn func(k netip.Prefix, v T) bool)
  • func (c *CIDRTrie[T]) Delete(cidr netip.Prefix) bool
  • func (c *CIDRTrie[T]) DescendantIterator(cidr netip.Prefix) Iterator[Key[netip.Prefix], T]
  • func (c *CIDRTrie[T]) DescendantShortestPrefixFirstIterator(cidr netip.Prefix) Iterator[Key[netip.Prefix], T]
  • func (c *CIDRTrie[T]) Descendants(cidr netip.Prefix, fn func(k netip.Prefix, v T) bool)
  • func (c *CIDRTrie[T]) DescendantsShortestPrefixFirst(cidr netip.Prefix, fn func(k netip.Prefix, v T) bool)
  • func (c *CIDRTrie[T]) ExactLookup(cidr netip.Prefix) (T, bool)
  • func (c *CIDRTrie[T]) ForEach(fn func(k netip.Prefix, v T) bool)
  • func (c *CIDRTrie[T]) Len() uint
  • func (c *CIDRTrie[T]) LongestPrefixMatch(addr netip.Addr) (netip.Prefix, T, bool)
  • func (c *CIDRTrie[T]) Upsert(cidr netip.Prefix, v T) bool
• type Iterator
• type Key
• type Trie
  • func NewTrie[K, T any](maxPrefix uint) Trie[Key[K], T]
• type UintTrie
  • func NewUintTrie[K Unsigned, T any]() *UintTrie[K, T]
  • func (ut *UintTrie[K, T]) Ancestors(prefix uint, k K, fn func(prefix uint, key K, value T) bool)
  • func (ut *UintTrie[K, T]) Delete(prefix uint, k K) bool
  • func (ut *UintTrie[K, T]) Descendants(prefix uint, k K, fn func(prefix uint, key K, value T) bool)
  • func (ut *UintTrie[K, T]) ExactLookup(prefix uint, k K) (T, bool)
  • func (ut *UintTrie[K, T]) ForEach(fn func(prefix uint, key K, value T) bool)
  • func (ut *UintTrie[K, T]) Len() uint
  • func (ut *UintTrie[K, T]) LongestPrefixMatch(k K) (K, T, bool)
  • func (ut *UintTrie[K, T]) Upsert(prefix uint, k K, value T) bool
• type Unsigned

Types

type CIDRTrie

type CIDRTrie[T any] struct {
	// contains filtered or unexported fields
}

CIDRTrie can hold both IPv4 and IPv6 prefixes at the same time.

func NewCIDRTrie

func NewCIDRTrie[T any]() *CIDRTrie[T]

NewCIDRTrie creates a new CIDRTrie[T any].

func (*CIDRTrie[T]) AncestorIterator

func (c *CIDRTrie[T]) AncestorIterator(cidr netip.Prefix) Iterator[Key[netip.Prefix], T]

func (*CIDRTrie[T]) AncestorLongestPrefixFirstIterator

func (c *CIDRTrie[T]) AncestorLongestPrefixFirstIterator(cidr netip.Prefix) Iterator[Key[netip.Prefix], T]

func (*CIDRTrie[T]) Ancestors

func (c *CIDRTrie[T]) Ancestors(cidr netip.Prefix, fn func(k netip.Prefix, v T) bool)

Ancestors iterates over every CIDR pair that contains the CIDR argument.

func (*CIDRTrie[T]) AncestorsLongestPrefixFirst

func (c *CIDRTrie[T]) AncestorsLongestPrefixFirst(cidr netip.Prefix, fn func(k netip.Prefix, v T) bool)

AncestorsLongestPrefixFirst iterates over every CIDR pair that contains the CIDR argument, longest matching prefix first, then iterating towards the root of the trie.

func (*CIDRTrie[T]) Delete

func (c *CIDRTrie[T]) Delete(cidr netip.Prefix) bool

Delete removes a given prefix from the tree.

func (*CIDRTrie[T]) DescendantIterator

func (c *CIDRTrie[T]) DescendantIterator(cidr netip.Prefix) Iterator[Key[netip.Prefix], T]

func (*CIDRTrie[T]) DescendantShortestPrefixFirstIterator

func (c *CIDRTrie[T]) DescendantShortestPrefixFirstIterator(cidr netip.Prefix) Iterator[Key[netip.Prefix], T]

func (*CIDRTrie[T]) Descendants

func (c *CIDRTrie[T]) Descendants(cidr netip.Prefix, fn func(k netip.Prefix, v T) bool)

Descendants iterates over every CIDR that is contained by the CIDR argument.

func (*CIDRTrie[T]) DescendantsShortestPrefixFirst

func (c *CIDRTrie[T]) DescendantsShortestPrefixFirst(cidr netip.Prefix, fn func(k netip.Prefix, v T) bool)

DescendantsShortestPrefixFirst iterates over every CIDR that is contained by the CIDR argument.

func (*CIDRTrie[T]) ExactLookup

func (c *CIDRTrie[T]) ExactLookup(cidr netip.Prefix) (T, bool)

ExactLookup returns the value for a given CIDR, but only if there is an exact match for the CIDR in the Trie.

func (*CIDRTrie[T]) ForEach

func (c *CIDRTrie[T]) ForEach(fn func(k netip.Prefix, v T) bool)

ForEach iterates over every element of the Trie. It iterates over IPv4 keys first.

func (*CIDRTrie[T]) Len

func (c *CIDRTrie[T]) Len() uint

Len returns the total number of ipv4 and ipv6 prefixes in the trie.

func (*CIDRTrie[T]) LongestPrefixMatch

func (c *CIDRTrie[T]) LongestPrefixMatch(addr netip.Addr) (netip.Prefix, T, bool)

LongestPrefixMatch returns the longest matched value for a given address.

func (*CIDRTrie[T]) Upsert

func (c *CIDRTrie[T]) Upsert(cidr netip.Prefix, v T) bool

Upsert adds or updates the value for a given prefix.

type Iterator

type Iterator[K, T any] interface {
	Next() (ok bool, key K, value T)
}

Iterator is an interface that can be used to produce the next key/value pair in iteration sequence. 'ok' is 'false' when the sequence ends; 'key' and 'value' are returned with empty values in that case. Iteration state is held in the implementation explicitly, rather than in Go stack/closures. Policy mapstate generation benchmark BenchmarkRegenerateCIDRDenyPolicyRules reports 25% less allocations with Iterator, even in combination with Go 1.23 Iterators on the caller side.

type Key

type Key[K any] interface {
	// CommonPrefix returns the number of bits that
	// are the same between this key and the argument
	// value, starting from MSB.
	CommonPrefix(K) uint
	// BitValueAt returns the value of the bit at an argument
	// index. MSB is 0 and LSB is n-1.
	BitValueAt(uint) uint8
	// Value returns the underlying value of the Key.
	Value() K
}

Key is an interface that implements all the necessary methods to index and retrieve keys.

type Trie

type Trie[K, T any] interface {
	// ExactLookup returns a value only if the prefix and key
	// match an entry in the Trie exactly.
	//
	// Note: If the prefix argument exceeds the Trie's maximum
	// prefix, it will be set to the Trie's maximum prefix.
	ExactLookup(prefix uint, key K) (v T, ok bool)
	// LongestPrefixMatch returns the longest prefix match for a specific
	// key.
	LongestPrefixMatch(key K) (k K, v T, ok bool)
	// Ancestors iterates over every prefix-key pair that contains
	// the prefix-key argument pair. If the function argument
	// returns false the iteration will stop. Ancestors iterates
	// keys from shortest to longest prefix match (that is, the
	// longest match will be returned last).
	//
	// Note: If the prefix argument exceeds the Trie's maximum
	// prefix, it will be set to the Trie's maximum prefix.
	Ancestors(prefix uint, key K, fn func(uint, K, T) bool)
	// AncestorIterator returns an iterator for ancestors that
	// can be used to produce the 'Next' key/value pair in sequence.
	AncestorIterator(prefix uint, key K) Iterator[K, T]
	// AncestorsLongestPrefixFirst iterates over every prefix-key pair that
	// contains the prefix-key argument pair. If the function argument
	// returns false the iteration will stop. AncestorsLongestPrefixFirst
	// iterates keys from longest to shortest prefix match (that is, the
	// longest matching prefix will be returned first).
	AncestorsLongestPrefixFirst(prefix uint, key K, fn func(uint, K, T) bool)
	// AncestorLongestPrefixFirstIterator returns an iterator for ancestors
	// that can be used to produce the 'Next' key/value pair in sequence,
	// starting from the key with the longest common prefix with 'key'.
	AncestorLongestPrefixFirstIterator(prefix uint, key K) Iterator[K, T]
	// Descendants iterates over every prefix-key pair that is contained
	// by the prefix-key argument pair. If the function argument
	// returns false the iteration will stop. Descendants does **not** iterate
	// over matches in any guaranteed order.
	//
	// Note: If the prefix argument exceeds the Trie's maximum
	// prefix, it will be set to the Trie's maximum prefix.
	Descendants(prefix uint, key K, fn func(uint, K, T) bool)
	// DescendantIterator returns an iterator for descendants
	// that can be used to produce the 'Next' key/value pair in sequence.
	DescendantIterator(prefix uint, key K) Iterator[K, T]
	// DescendantsShortestPrefixFirst iterates over every prefix-key pair that is contained by
	// the prefix-key argument pair. If the function argument returns false the iteration will
	// stop. DescendantsShortestPrefixFirst iterates keys starting from shortest prefix, and
	// progressing towards keys with longer prefixes. Keys with equal prefix lengths are not
	// iterated in any particular order.
	DescendantsShortestPrefixFirst(prefix uint, key K, fn func(uint, K, T) bool)
	// DescendantShortestPrefixFirstIterator returns an iterator for descendants
	// that can be used to produce the 'Next' key/value pair in sequence,
	// starting from the key with the shortest common prefix with 'key'.
	DescendantShortestPrefixFirstIterator(prefix uint, key K) Iterator[K, T]
	// Upsert updates or inserts the trie with a a prefix, key,
	// and value. The method returns true if the key is new, and
	// false if the key already existed.
	//
	// Note: If the prefix argument exceeds the Trie's maximum
	// prefix, it will be set to the Trie's maximum prefix.
	Upsert(prefix uint, key K, value T) bool
	// Delete removes a key with the exact given prefix and returns
	// false if the key was not found.
	//
	// Note: If the prefix argument exceeds the Trie's maximum
	// prefix, it will be set to the Trie's maximum prefix.
	Delete(prefix uint, key K) bool
	// Len returns the number of entries in the Trie
	Len() uint
	// ForEach iterates over every element of the Trie in no particular
	// order. If the function argument returns false the iteration stops.
	ForEach(fn func(uint, K, T) bool)
}

Trie is a non-preemptive binary trie that indexes arbitrarily long bit-based keys with associated prefix lengths indexed from most significant bit ("MSB") to least significant bit ("LSB") using the longest prefix match algorithm.

A prefix-length (hereafter "prefix"), in a prefix-key pair, represents the minimum number of bits (from MSB to LSB) that another comparable key must match.

Each method's comments describes the mechanism of how the method works.

func NewTrie

func NewTrie[K, T any](maxPrefix uint) Trie[Key[K], T]

NewTrie returns a Trie that accepts the Key[K any] interface as its key argument. This enables the user of this Trie to define their own bit-key.

type UintTrie

type UintTrie[K Unsigned, V any] struct {
	// contains filtered or unexported fields
}

UintTrie uses all unsigned integer types except for uintptr and uint.

func NewUintTrie

func NewUintTrie[K Unsigned, T any]() *UintTrie[K, T]

NewUintTrie represents a Trie with a key of any uint type.

func (*UintTrie[K, T]) Ancestors

func (ut *UintTrie[K, T]) Ancestors(prefix uint, k K, fn func(prefix uint, key K, value T) bool)

func (*UintTrie[K, T]) Delete

func (ut *UintTrie[K, T]) Delete(prefix uint, k K) bool

func (*UintTrie[K, T]) Descendants

func (ut *UintTrie[K, T]) Descendants(prefix uint, k K, fn func(prefix uint, key K, value T) bool)

func (*UintTrie[K, T]) ExactLookup

func (ut *UintTrie[K, T]) ExactLookup(prefix uint, k K) (T, bool)

func (*UintTrie[K, T]) ForEach

func (ut *UintTrie[K, T]) ForEach(fn func(prefix uint, key K, value T) bool)

func (*UintTrie[K, T]) Len

func (ut *UintTrie[K, T]) Len() uint

func (*UintTrie[K, T]) LongestPrefixMatch

func (ut *UintTrie[K, T]) LongestPrefixMatch(k K) (K, T, bool)

func (*UintTrie[K, T]) Upsert

func (ut *UintTrie[K, T]) Upsert(prefix uint, k K, value T) bool

type Unsigned

type Unsigned interface {
	~uint8 | ~uint16 | ~uint32 | ~uint64
}

Unsigned represents all types that have an underlying unsigned integer type, excluding uintptr and uint.