Documentation
¶
Index ¶
- type CIDRTrie
- func (c *CIDRTrie[T]) AncestorIterator(cidr netip.Prefix) ancestorIterator[cidrKey, T]
- func (c *CIDRTrie[T]) AncestorLongestPrefixFirstIterator(cidr netip.Prefix) ancestorLPFIterator[cidrKey, 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) descendantIterator[cidrKey, T]
- func (c *CIDRTrie[T]) DescendantShortestPrefixFirstIterator(cidr netip.Prefix) descendantSPFIterator[cidrKey, 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 Key
- type Trie
- type UintTrie
- 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
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
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 ¶
NewCIDRTrie creates a new CIDRTrie[T any].
func (*CIDRTrie[T]) AncestorIterator ¶ added in v1.17.0
func (*CIDRTrie[T]) AncestorLongestPrefixFirstIterator ¶ added in v1.17.0
func (*CIDRTrie[T]) Ancestors ¶
Ancestors iterates over every CIDR pair that contains the CIDR argument.
func (*CIDRTrie[T]) AncestorsLongestPrefixFirst ¶ added in v1.17.0
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]) DescendantIterator ¶ added in v1.17.0
func (*CIDRTrie[T]) DescendantShortestPrefixFirstIterator ¶ added in v1.17.0
func (*CIDRTrie[T]) Descendants ¶
Descendants iterates over every CIDR that is contained by the CIDR argument.
func (*CIDRTrie[T]) DescendantsShortestPrefixFirst ¶ added in v1.17.0
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 ¶ added in v1.16.0
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 ¶
ForEach iterates over every element of the Trie. It iterates over IPv4 keys first.
func (*CIDRTrie[T]) LongestPrefixMatch ¶ added in v1.16.0
LongestPrefixMatch returns the longest matched value for a given address.
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 }
Key is an interface that implements all the necessary methods to index and retrieve keys.
type Trie ¶
type Trie[K Key[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) ancestorIterator[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) ancestorLPFIterator[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) descendantIterator[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) descendantSPFIterator[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.
'K' must implement the Key[K] interface, and should be passed by value for optimum performance. If 'K' is a pointer type, its Key[K] methods must accept nil receivers.
Each method's comments describes the mechanism of how the method works.
type UintTrie ¶ added in v1.16.0
UintTrie uses all unsigned integer types except for uintptr and uint.
func NewUintTrie ¶
NewUintTrie represents a Trie with a key of any uint type.
func (*UintTrie[K, T]) Descendants ¶ added in v1.16.0
func (*UintTrie[K, T]) ExactLookup ¶ added in v1.16.0
func (*UintTrie[K, T]) LongestPrefixMatch ¶ added in v1.16.0
Source Files
Click to show internal directories.
Click to hide internal directories.