cidrtree

README

package cidrtree

Overview

package cidrtree is an immutable datastructure for fast IP lookup (longest prefix match) in CIDR tables.

Immutability is achieved because insert/delete will return a new tree which will share some nodes with the original tree. All nodes are read-only after creation, allowing concurrent readers to operate safely with concurrent writers.

This package is a specialization of the more generic interval package of the same author, but explicit for CIDRs. It has a narrow focus with a smaller and simpler API.

API

  import "github.com/gaissmai/cidrtree"

  type Tree struct{ ... }

  func New(cidrs ...netip.Prefix) Tree
  func NewConcurrent(jobs int, cidrs ...netip.Prefix) Tree

  func (t Tree) Lookup(ip netip.Addr) (cidr netip.Prefix, ok bool)

  func (t Tree) Insert(cidrs ...netip.Prefix) Tree
  func (t Tree) Delete(cidr netip.Prefix) (Tree, bool)

  func (t *Tree) InsertMutable(cidrs ...netip.Prefix)
  func (t *Tree) DeleteMutable(cidr netip.Prefix) bool

  func (t Tree) Union(other Tree, immutable bool) Tree
  func (t Tree) Clone() Tree

  func (t Tree) String() string
  func (t Tree) Fprint(w io.Writer) error

Documentation

Overview

Package cidrtree provides fast IP to CIDR lookup (longest prefix match).

This package is a specialization of the more generic interval package of the same author, but explicit for CIDRs. It has a narrow focus with a smaller and simpler API.

Index

• type Tree
  • func New(cidrs ...netip.Prefix) Tree
  • func NewConcurrent(jobs int, cidrs ...netip.Prefix) Tree
  • func (t Tree) Clone() Tree
  • func (t Tree) Delete(cidr netip.Prefix) (Tree, bool)
  • func (t *Tree) DeleteMutable(cidr netip.Prefix) bool
  • func (t Tree) Fprint(w io.Writer) error
  • func (t Tree) Insert(cidrs ...netip.Prefix) Tree
  • func (t *Tree) InsertMutable(cidrs ...netip.Prefix)
  • func (t Tree) Lookup(ip netip.Addr) (cidr netip.Prefix, ok bool)
  • func (t Tree) String() string
  • func (t Tree) Union(other Tree, immutable bool) Tree

Types

type Tree

type Tree struct {
	// contains filtered or unexported fields
}

Tree is the public handle to the hidden implementation.

func New

func New(cidrs ...netip.Prefix) Tree

New initializes the cidr tree with zero or more netip prefixes. Duplicate prefixes are just skipped.

func NewConcurrent

func NewConcurrent(jobs int, cidrs ...netip.Prefix) Tree

NewConcurrent, splits the input data into chunks, fan-out to New and recombine the chunk trees (mutable) with [Union].

Convenience function for initializing the cidrtree for large inputs (> 100_000). A good value reference for jobs is the number of logical CPUs [runtine.NumCPU] usable by the current process.

func (Tree) Clone

func (t Tree) Clone() Tree

Clone, deep cloning of the CIDR tree.

func (Tree) Delete

func (t Tree) Delete(cidr netip.Prefix) (Tree, bool)

Delete removes the cdir if it exists, returns the new tree and true, false if not found.

func (*Tree) DeleteMutable

func (t *Tree) DeleteMutable(cidr netip.Prefix) bool

DeleteMutable removes the cidr from tree, returns true if it exists, false otherwise. If the original tree does not need to be preserved then this is much faster than the immutable delete.

func (Tree) Fprint

func (t Tree) Fprint(w io.Writer) error

Fprint writes an ordered CIDR tree diagram to w. If w is nil, Fprint panics.

The order from top to bottom is in ascending order of the start address and the subtree structure is determined by the CIDRs coverage.

▼
└─ 0.0.0.0/0
   ├─ 10.0.0.0/8
   │  ├─ 10.0.0.0/24
   │  └─ 10.0.1.0/24
   ├─ 127.0.0.0/8
   │  └─ 127.0.0.1/32
   ├─ 169.254.0.0/16
   ├─ 172.16.0.0/12
   └─ 192.168.0.0/16
      └─ 192.168.1.0/24
▼
└─ ::/0
   ├─ ::1/128
   ├─ 2000::/3
   │  └─ 2001:db8::/32
   ├─ fc00::/7
   ├─ fe80::/10
   └─ ff00::/8

func (Tree) Insert

func (t Tree) Insert(cidrs ...netip.Prefix) Tree

Insert netip prefixes into the tree, returns the new Tree. Duplicate prefixes are just skipped.

func (*Tree) InsertMutable

func (t *Tree) InsertMutable(cidrs ...netip.Prefix)

InsertMutable insert netip prefixes into the tree, changing the original tree. Duplicate prefixes are just skipped. If the original tree does not need to be preserved then this is much faster than the immutable insert.

func (Tree) Lookup

func (t Tree) Lookup(ip netip.Addr) (cidr netip.Prefix, ok bool)

Lookup returns the longest-prefix-match for ip. If the ip isn't covered by any CIDR, the zero value and false is returned. The algorithm for Lookup does NOT allocate memory.

example:

▼
├─ 10.0.0.0/8
│  ├─ 10.0.0.0/24
│  └─ 10.0.1.0/24
├─ 127.0.0.0/8
│  └─ 127.0.0.1/32
├─ 169.254.0.0/16
├─ 172.16.0.0/12
└─ 192.168.0.0/16
   └─ 192.168.1.0/24
▼
└─ ::/0
   ├─ ::1/128
   ├─ 2000::/3
   │  └─ 2001:db8::/32
   ├─ fc00::/7
   ├─ fe80::/10
   └─ ff00::/8

    tree.Lookup("42.0.0.0")             returns netip.Prefix{}, false
    tree.Lookup("10.0.1.17")            returns 10.0.1.0/24,    true
    tree.Lookup("2001:7c0:3100:1::111") returns 2000::/3,       true

func (Tree) String

func (t Tree) String() string

String returns a hierarchical tree diagram of the ordered CIDRs as string, just a wrapper for Tree.Fprint.

func (Tree) Union

func (t Tree) Union(other Tree, immutable bool) Tree

Union combines any two trees. Duplicates are skipped.

The "immutable" flag controls whether the two trees are allowed to be modified.