triert

Documentation

Overview

Package triert provides a routing table implemented using a XOR trie.

Index

• func BucketLimit20[K kad.Key[K], N kad.NodeID[K]](rt *TrieRT[K, N], kk K) bool
• type Config
  • func DefaultConfig[K kad.Key[K], N kad.NodeID[K]]() *Config[K, N]
• type KeyFilterFunc
• type NodeFilter
• type TrieRT
  • func New[K kad.Key[K], N kad.NodeID[K]](self N, cfg *Config[K, N]) (*TrieRT[K, N], error)
  • func (rt *TrieRT[K, N]) AddNode(node N) bool
  • func (rt *TrieRT[K, N]) Cpl(kk K) int
  • func (rt *TrieRT[K, N]) CplSize(cpl int) int
  • func (rt *TrieRT[K, N]) GetNode(kk K) (N, bool)
  • func (rt *TrieRT[K, N]) NearestNodes(target K, n int) []N
  • func (rt *TrieRT[K, N]) RemoveKey(kk K) bool
  • func (rt *TrieRT[K, N]) Self() K
  • func (rt *TrieRT[K, N]) Size() int

Functions

func BucketLimit20

func BucketLimit20[K kad.Key[K], N kad.NodeID[K]](rt *TrieRT[K, N], kk K) bool

BucketLimit20 is a filter function that limits the occupancy of buckets in the table to 20 keys.

Types

type Config

type Config[K kad.Key[K], N kad.NodeID[K]] struct {
	// KeyFilter defines the filter that is applied before a key is added to the
	// table. KeyFilter is applied before NodeFilter.
	// If nil, no filter is applied.
	KeyFilter KeyFilterFunc[K, N]
	// NodeFilter defines the filter that is applied before a node is added to
	// the table. NodeFilter is applied after KeyFilter.
	// If nil, no filter is applied.
	NodeFilter NodeFilter[K, N]
}

Config holds configuration options for a TrieRT.

func DefaultConfig

func DefaultConfig[K kad.Key[K], N kad.NodeID[K]]() *Config[K, N]

DefaultConfig returns a default configuration for a TrieRT.

type KeyFilterFunc

type KeyFilterFunc[K kad.Key[K], N kad.NodeID[K]] func(rt *TrieRT[K, N], kk K) bool

KeyFilterFunc is a function that is applied before a key is added to the table. Return false to prevent the key from being added.

type NodeFilter

type NodeFilter[K kad.Key[K], N kad.NodeID[K]] interface {
	// TryAdd is called when a node is added to the table. Return true to allow
	// the node to be added. Return false to prevent the node from being added
	// to the table. When updating its state, the NodeFilter considers that the
	// node has been added to the table if TryAdd returns true.
	TryAdd(rt *TrieRT[K, N], node N) bool
	// Remove is called when a node is removed from the table, allowing the
	// filter to update its state.
	Remove(node N)
}

NodeFilter provides a stateful way to filter nodes before they are added to the table. The filter is applied after the key filter.

type TrieRT

type TrieRT[K kad.Key[K], N kad.NodeID[K]] struct {
	// contains filtered or unexported fields
}

TrieRT is a routing table backed by a XOR Trie which offers good scalablity and performance for large networks.

func New

func New[K kad.Key[K], N kad.NodeID[K]](self N, cfg *Config[K, N]) (*TrieRT[K, N], error)

New creates a new TrieRT using the supplied key as the local node's Kademlia key. If cfg is nil, the default config is used.

func (*TrieRT[K, N]) AddNode

func (rt *TrieRT[K, N]) AddNode(node N) bool

AddNode tries to add a node to the routing table.

func (*TrieRT[K, N]) Cpl

func (rt *TrieRT[K, N]) Cpl(kk K) int

Cpl returns the longest common prefix length the supplied key shares with the table's key.

func (*TrieRT[K, N]) CplSize

func (rt *TrieRT[K, N]) CplSize(cpl int) int

CplSize returns the number of peers in the table whose longest common prefix with the table's key is of length cpl.

func (*TrieRT[K, N]) GetNode

func (rt *TrieRT[K, N]) GetNode(kk K) (N, bool)

func (*TrieRT[K, N]) NearestNodes

func (rt *TrieRT[K, N]) NearestNodes(target K, n int) []N

NearestNodes returns the n closest nodes to a given key.

func (*TrieRT[K, N]) RemoveKey

func (rt *TrieRT[K, N]) RemoveKey(kk K) bool

RemoveKey tries to remove a node identified by its Kademlia key from the routing table. It returns true if the key was found to be present in the table and was removed.

func (*TrieRT[K, N]) Self

func (rt *TrieRT[K, N]) Self() K

Self returns the local node's Kademlia key.

func (*TrieRT[K, N]) Size

func (rt *TrieRT[K, N]) Size() int

Size returns the number of peers contained in the table.