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]) ForEach(fn func(k netip.Prefix, v T) bool)
  • func (c *CIDRTrie[T]) Len() uint
  • func (c *CIDRTrie[T]) Lookup(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]
  • func NewUintTrie[K Unsigned, T any]() Trie[K, 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 prefix-key pair that contains the prefix-key argument pair.

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 prefix-key pair that is contained by the prefix-key argument pair.

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

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

Lookup 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 {
	// Lookup returns the longest prefix match for a specific
	// key.
	Lookup(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.

func NewUintTrie

func NewUintTrie[K Unsigned, T any]() Trie[K, T]

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

type Unsigned

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

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