art

Documentation

Overview

Package art provides a routing table that implements the Allotment Routing Table (ART) algorithm by Donald Knuth, as described in the paper by Yoichi Hariguchi.

ART outperforms the traditional radix tree implementations for route lookups, insertions, and deletions.

For more information, see Yoichi Hariguchi's paper: https://cseweb.ucsd.edu//~varghese/TEACH/cs228/artlookup.pdf

Index

• type Table
  • func (t *Table[T]) Delete(pfx netip.Prefix)
  • func (t *Table[T]) Get(addr netip.Addr) (ret T, ok bool)
  • func (t *Table[T]) Insert(pfx netip.Prefix, val T)

Types

type Table

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

Table is an IPv4 and IPv6 routing table.

func (*Table[T]) Delete

func (t *Table[T]) Delete(pfx netip.Prefix)

Delete removes pfx from the table, if it is present.

func (*Table[T]) Get

func (t *Table[T]) Get(addr netip.Addr) (ret T, ok bool)

Get does a route lookup for addr and returns the associated value, or nil if no route matched.

func (*Table[T]) Insert

func (t *Table[T]) Insert(pfx netip.Prefix, val T)

Insert adds pfx to the table, with value val. If pfx is already present in the table, its value is set to val.