bitlpm

Documentation

Index

• type CIDRTrie
  • func NewCIDRTrie[T any]() *CIDRTrie[T]
  • func (c *CIDRTrie[T]) Ancestors(cidr netip.Prefix, fn func(k netip.Prefix, v T) bool)
  • func (c *CIDRTrie[T]) Delete(cidr netip.Prefix) bool
  • func (c *CIDRTrie[T]) Descendants(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) (T, bool)
  • func (c *CIDRTrie[T]) Upsert(cidr netip.Prefix, v T)
• 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) (T, bool)
  • func (ut *UintTrie[K, T]) Upsert(prefix uint, k K, value T)
• 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]) 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]) Delete

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

Delete removes a given prefix from the tree.

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]) 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) (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)

Upsert adds or updates the value for a given prefix.

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) (v T, ok bool)
	// Ancestors iterates over every prefix-key pair that contains
	// the prefix-key argument pair. If the Ancestors function argument
	// returns false the iteration will stop. Ancestors will iterate
	// 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)
	// Descendants iterates over every prefix-key pair that is contained
	// by the prefix-key argument pair. If the Descendants 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)
	// Upsert updates or inserts the trie with a a prefix, key,
	// and value.
	//
	// 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)
	// 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) (T, bool)

func (*UintTrie[K, T]) Upsert

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

type Unsigned

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

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