netipds

package module
v0.1.8 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 16, 2025 License: MIT Imports: 6 Imported by: 2

README

netipds

Go Reference Go Report Card codecov

This package builds on the netip/netipx family by adding two immutable, tree-based collection types for netip.Prefix:

  • PrefixMap[T] - for associating data with IPs and prefixes and fetching that data with network hierarchy awareness
  • PrefixSet - for storing sets of prefixes and combining those sets in useful ways (unions, intersections, etc)

Both are backed by a binary radix tree, which enables a rich set of efficient queries about prefix containment, hierarchy, and overlap.

Goals
  • Efficiency. This package aims to provide fast, immutable collection types for IP networks.
  • Integration with net/netip. This package is built on the shoulders of net/netip, leveraging its types and lessons both under the hood and at interfaces. See this excellent post by Tailscale about the history and benefits of net/netip.
  • Completeness. Most other IP radix tree libraries lack several of the queries provided by netipds.
Non-Goals
  • Mutability. For use cases requiring continuous mutability, try kentik/patricia or gaissmai/bart.
  • Persistence. This package is for data sets that fit in memory.
  • Other key types. The collections in this package support exactly one key type: netip.Prefix.

Usage

Usage is similar to that of netipx.IPSet: to construct a PrefixMap or PrefixSet, use the respective builder type.

Example
// Make our examples more readable
px := netip.MustParsePrefix

// Build a PrefixMap
builder := PrefixMapBuilder[string]{}
builder.Set(px("1.2.0.0/16"), "hello")
builder.Set(px("1.2.3.0/24"), "world")

// This returns an immutable snapshot of the
// builder's state. The builder remains usable.
pm := builder.PrefixMap()

// Fetch an exact entry from the PrefixMap.
val, ok := pm.Get(px("1.0.0.0/16"))              // => ("hello", true)

// Ask if the PrefixMap contains an exact
// entry.
ok = pm.Contains(px("1.2.3.4/32"))               // => false

// Ask if a Prefix has any ancestor in the
// PrefixMap.
ok = pm.Encompasses(px("1.2.3.4/32"))            // => true

// Fetch a Prefix's nearest ancestor.
p, val, ok := pm.ParentOf(px("1.2.3.4/32"))      // => (1.2.3.0/24, "world", true)

// Fetch all of a Prefix's ancestors, and
// convert the result to a map[Prefix]string.
m := pm.AncestorsOf(px("1.2.3.4/32")).ToMap()    // => map[1.2.0.0/16:"hello"
                                                 //        1.2.3.0/24:"world"]

// Fetch all of a Prefix's descendants, and
// convert the result to a map[Prefix]string.
m = pm.DescendantsOf(px("1.0.0.0/8")).ToMap()    // => map[1.2.0.0/16:"hello"
                                                 //        1.2.3.0/24:"world"]
Set Operations with PrefixSet

PrefixSet offers set-specific functionality beyond what can be done with PrefixMap.

In particular, during the building stage, you can combine sets in the following ways:

Operation Method Result
Union PrefixSetBuilder.Merge Every prefix found in either set.
Intersection PrefixSetBuilder.Intersect Every prefix that either (1) exists in both sets or (2) exists in one set and has an ancestor in the other.
Difference PrefixSetBuilder.Subtract The difference between the two sets. When a child is subtracted from a parent, the child itself is removed, and new elements are added to fill in remaining space.
kentik/patricia

This package uses a similar underlying data structure, but its goal is to provide mutability while minimizing garbage collection cost.

By contrast, netipds aims to provide immutable collection types that integrate well with the netip family and offer a comprehensive API.

gaissmai/bart

This package uses a different trie implementation based on the ART algorithm (Knuth). It provides mutability while optimizing for lookup time and memory usage. Its API also provides useful methods such as Subnets, Supernets, Union, and iterators.

By contrast, netipds uses a traditional trie implementation, provides immutable types, and offers additional set operations.

Additional Packages

See gaissmai/iprbench for more libraries and benchmarks comparing them.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type PrefixMap 

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

PrefixMap is a map of netip.Prefix to T. It is implemented as a binary radix tree.

Use PrefixMapBuilder to construct PrefixMaps.

func (*PrefixMap[T]) AncestorsOf 

func (m *PrefixMap[T]) AncestorsOf(p netip.Prefix) *PrefixMap[T]

AncestorsOf returns a PrefixMap containing all ancestors of p in m, including p itself if it has an entry.

func (*PrefixMap[T]) AncestorsOfStrict 

func (m *PrefixMap[T]) AncestorsOfStrict(p netip.Prefix) *PrefixMap[T]

AncestorsOfStrict returns a PrefixMap containing all ancestors of p in m, excluding p itself.

func (*PrefixMap[T]) Contains 

func (m *PrefixMap[T]) Contains(p netip.Prefix) bool

Contains returns true if this map includes the exact Prefix provided.

func (*PrefixMap[T]) DescendantsOf 

func (m *PrefixMap[T]) DescendantsOf(p netip.Prefix) *PrefixMap[T]

DescendantsOf returns a PrefixMap containing all descendants of p in m, including p itself if it has an entry.

func (*PrefixMap[T]) DescendantsOfStrict 

func (m *PrefixMap[T]) DescendantsOfStrict(p netip.Prefix) *PrefixMap[T]

DescendantsOfStrict returns a PrefixMap containing all descendants of p in m, excluding p itself.

func (*PrefixMap[T]) Encompasses 

func (m *PrefixMap[T]) Encompasses(p netip.Prefix) bool

Encompasses returns true if this map includes a Prefix which completely encompasses p. The encompassing Prefix may be p itself.

func (*PrefixMap[T]) EncompassesStrict 

func (m *PrefixMap[T]) EncompassesStrict(p netip.Prefix) bool

EncompassesStrict returns true if this map includes a Prefix which completely encompasses p. The encompassing Prefix must be an ancestor of p, not p itself.

func (*PrefixMap[T]) Filter 

func (m *PrefixMap[T]) Filter(s *PrefixSet) *PrefixMap[T]

Filter returns a new PrefixMap containing the entries of m that are encompassed by s.

func (*PrefixMap[T]) Get 

func (m *PrefixMap[T]) Get(p netip.Prefix) (T, bool)

Get returns the value associated with the exact Prefix provided, if any.

func (*PrefixMap[T]) OverlapsPrefix 

func (m *PrefixMap[T]) OverlapsPrefix(p netip.Prefix) bool

OverlapsPrefix returns true if this map includes a Prefix which overlaps p.

func (*PrefixMap[T]) ParentOf 

func (m *PrefixMap[T]) ParentOf(p netip.Prefix) (netip.Prefix, T, bool)

ParentOf returns the longest-prefix ancestor of p in m, if any. If p itself has an entry, then p's entry is returned.

func (*PrefixMap[T]) ParentOfStrict 

func (m *PrefixMap[T]) ParentOfStrict(p netip.Prefix) (netip.Prefix, T, bool)

ParentOfStrict returns the longest-prefix ancestor of p in m, if any. If p has no ancestors in the map, then ParentOfStrict returns zero values and false.

func (*PrefixMap[T]) RootOf 

func (m *PrefixMap[T]) RootOf(p netip.Prefix) (netip.Prefix, T, bool)

RootOf returns the shortest-prefix ancestor of p in m, if any. If p itself has an entry and has no ancestors, then p's entry is returned.

func (*PrefixMap[T]) RootOfStrict 

func (m *PrefixMap[T]) RootOfStrict(p netip.Prefix) (netip.Prefix, T, bool)

RootOfStrict returns the shortest-prefix ancestor of p in m, if any. If p has no ancestors in m, then RootOfStrict returns zero values and false.

func (*PrefixMap[T]) Size added in v0.1.1 

func (m *PrefixMap[T]) Size() int

Size returns the number of entries in m.

func (*PrefixMap[T]) String 

func (m *PrefixMap[T]) String() string

String returns a human-readable representation of m's tree structure.

func (*PrefixMap[T]) ToMap 

func (m *PrefixMap[T]) ToMap() map[netip.Prefix]T

ToMap returns a map of all Prefixes in m to their associated values.

type PrefixMapBuilder 

type PrefixMapBuilder[T any] struct {
	Lazy bool
	// contains filtered or unexported fields
}

PrefixMapBuilder builds an immutable PrefixMap.

The zero value is a valid PrefixMapBuilder representing a builder with zero Prefixes.

Call PrefixMapBuilder.PrefixMap to obtain an immutable PrefixMap from a PrefixMapBuilder.

If Lazy == true, then path compression is delayed until a PrefixMap is created. The builder itself remains uncompressed. Lazy mode can dramatically reduce the time required to build a large PrefixMap.

func (*PrefixMapBuilder[T]) Filter 

func (m *PrefixMapBuilder[T]) Filter(s *PrefixSet)

Filter removes all Prefixes that are not encompassed by s from m.

func (*PrefixMapBuilder[T]) Get 

func (m *PrefixMapBuilder[T]) Get(p netip.Prefix) (T, bool)

Get returns the value associated with the exact Prefix provided, if any.

func (*PrefixMapBuilder[T]) PrefixMap 

func (m *PrefixMapBuilder[T]) PrefixMap() *PrefixMap[T]

PrefixMap returns an immutable PrefixMap representing the current state of m.

The builder remains usable after calling PrefixMap.

func (*PrefixMapBuilder[T]) Remove 

func (m *PrefixMapBuilder[T]) Remove(p netip.Prefix) error

Remove removes p from m. Only the exact Prefix provided is removed; descendants are not.

To remove entire sections of IP space at once, see PrefixMapBuilder.Filter.

func (*PrefixMapBuilder[T]) Set 

func (m *PrefixMapBuilder[T]) Set(p netip.Prefix, v T) error

Set associates v with p.

func (*PrefixMapBuilder[T]) String 

func (s *PrefixMapBuilder[T]) String() string

type PrefixSet 

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

PrefixSet is a set of netip.Prefix values. It is implemented as a binary radix tree.

PrefixSet offers unique functionality beyond what a PrefixMap[bool] can do. In particular, during the building stage (PrefixSetBuilder) you can combine sets in useful ways using methods like PrefixSetBuilder.Merge, PrefixSetBuilder.Intersect, and PrefixSetBuilder.Subtract.

Use PrefixSetBuilder to construct PrefixSets.

func (*PrefixSet) All added in v0.1.7 

func (s *PrefixSet) All() iter.Seq[netip.Prefix]

All returns an iterator over all prefixes in s.

func (*PrefixSet) AllCompact added in v0.1.7 

func (s *PrefixSet) AllCompact() iter.Seq[netip.Prefix]

AllCompact returns an iterator over the prefixes in s that are not children of any other prefix in s.

Note: AllCompact does not merge siblings, so the result may contain complete sets of sibling prefixes, e.g. 1.2.3.0/32 and 1.2.3.1/32.

func (*PrefixSet) AncestorsOf added in v0.1.5 

func (s *PrefixSet) AncestorsOf(p netip.Prefix) *PrefixSet

AncestorsOf returns a PrefixSet containing all ancestors of p in s, including p itself if it has an entry.

func (*PrefixSet) AncestorsOfStrict added in v0.1.5 

func (s *PrefixSet) AncestorsOfStrict(p netip.Prefix) *PrefixSet

AncestorsOfStrict returns a PrefixSet containing all ancestors of p in s, excluding p itself.

func (*PrefixSet) Contains 

func (s *PrefixSet) Contains(p netip.Prefix) bool

Contains returns true if this set includes the exact Prefix provided.

func (*PrefixSet) DescendantsOf added in v0.1.5 

func (s *PrefixSet) DescendantsOf(p netip.Prefix) *PrefixSet

DescendantsOf returns a PrefixSet containing all descendants of p in s, including p itself if it has an entry.

func (*PrefixSet) DescendantsOfStrict added in v0.1.5 

func (s *PrefixSet) DescendantsOfStrict(p netip.Prefix) *PrefixSet

DescendantsOfStrict returns a PrefixSet containing all descendants of p in s, excluding p itself.

func (*PrefixSet) Encompasses 

func (s *PrefixSet) Encompasses(p netip.Prefix) bool

Encompasses returns true if this set includes a Prefix which completely encompasses p. The encompassing Prefix may be p itself.

func (*PrefixSet) EncompassesStrict 

func (s *PrefixSet) EncompassesStrict(p netip.Prefix) bool

EncompassesStrict returns true if this set includes a Prefix which completely encompasses p. The encompassing Prefix must be an ancestor of p, not p itself.

func (*PrefixSet) OverlapsPrefix 

func (s *PrefixSet) OverlapsPrefix(p netip.Prefix) bool

OverlapsPrefix returns true if this set includes a Prefix which overlaps p.

func (*PrefixSet) ParentOf added in v0.1.5 

func (s *PrefixSet) ParentOf(p netip.Prefix) (netip.Prefix, bool)

ParentOf returns the longest-prefix ancestor of p in s, if any. If p itself has an entry, then p's entry is returned.

func (*PrefixSet) ParentOfStrict added in v0.1.5 

func (s *PrefixSet) ParentOfStrict(p netip.Prefix) (netip.Prefix, bool)

ParentOfStrict returns the longest-prefix ancestor of p in s, if any. If p has no ancestors in the set, then ParentOfStrict returns zero values and false.

func (*PrefixSet) Prefixes 

func (s *PrefixSet) Prefixes() []netip.Prefix

Prefixes returns a slice of all Prefixes in s.

func (*PrefixSet) PrefixesCompact added in v0.1.1 

func (s *PrefixSet) PrefixesCompact() []netip.Prefix

PrefixesCompact returns a slice of the Prefixes in s that are not children of other Prefixes in s.

Note: PrefixCompact does not merge siblings, so the result may contain complete sets of sibling prefixes, e.g. 1.2.3.0/32 and 1.2.3.1/32.

func (*PrefixSet) RootOf added in v0.1.5 

func (s *PrefixSet) RootOf(p netip.Prefix) (netip.Prefix, bool)

RootOf returns the shortest-prefix ancestor of p in s, if any. If p itself has an entry and has no ancestors, then p's entry is returned.

func (*PrefixSet) RootOfStrict added in v0.1.5 

func (s *PrefixSet) RootOfStrict(p netip.Prefix) (netip.Prefix, bool)

RootOfStrict returns the shortest-prefix ancestor of p in s, if any. If p has no ancestors in s, then RootOfStrict returns zero values and false.

func (*PrefixSet) Size added in v0.1.1 

func (s *PrefixSet) Size() int

Size returns the number of elements in s.

func (*PrefixSet) String 

func (s *PrefixSet) String() string

String returns a human-readable representation of the s's tree structure.

type PrefixSetBuilder 

type PrefixSetBuilder struct {
	Lazy bool
	// contains filtered or unexported fields
}

PrefixSetBuilder builds an immutable PrefixSet.

The zero value is a valid PrefixSetBuilder representing a builder with zero Prefixes.

Call PrefixSet to obtain an immutable PrefixSet from a PrefixSetBuilder.

If Lazy == true, then path compression is delayed until a PrefixSet is created. The builder itself remains uncompressed. Lazy mode can dramatically improve performance when building large PrefixSets.

func (*PrefixSetBuilder) Add 

func (s *PrefixSetBuilder) Add(p netip.Prefix) error

Add adds p to s.

func (*PrefixSetBuilder) Filter 

func (s *PrefixSetBuilder) Filter(o *PrefixSet)

Filter removes all Prefixes that are not encompassed by o from s.

func (*PrefixSetBuilder) Intersect added in v0.1.5 

func (s *PrefixSetBuilder) Intersect(o *PrefixSet)

Intersect modifies s so that it contains the intersection of the entries in s and o: to be included in the result, a Prefix must either (a) exist in both sets or (b) exist in one set and have an ancestor in the other.

func (*PrefixSetBuilder) Merge added in v0.1.5 

func (s *PrefixSetBuilder) Merge(o *PrefixSet)

Merge modifies s so that it contains the union of the entries in s and o.

func (*PrefixSetBuilder) PrefixSet 

func (s *PrefixSetBuilder) PrefixSet() *PrefixSet

PrefixSet returns an immutable PrefixSet representing the current state of s.

The builder remains usable after calling PrefixSet.

func (*PrefixSetBuilder) Remove 

func (s *PrefixSetBuilder) Remove(p netip.Prefix) error

Remove removes p from s. Only the exact Prefix provided is removed; descendants are not.

To remove entire sections of IP space at once, see PrefixSetBuilder.Filter, PrefixSetBuilder.Subtract and PrefixSetBuilder.SubtractPrefix.

func (*PrefixSetBuilder) String 

func (s *PrefixSetBuilder) String() string

String returns a human-readable representation of s's tree structure.

func (*PrefixSetBuilder) Subtract 

func (s *PrefixSetBuilder) Subtract(o *PrefixSet)

Subtract modifies s so that the Prefixes in o, and all of their descendants, are removed from s, leaving behind any remaining portions of affected Prefixes. This may add elements to fill in gaps around the subtracted Prefixes.

For example, if s is {::0/126}, and we subtract ::0/128, then s will become {::1/128, ::2/127}.

func (*PrefixSetBuilder) SubtractPrefix added in v0.1.5 

func (s *PrefixSetBuilder) SubtractPrefix(p netip.Prefix) error

SubtractPrefix modifies s so that p and all of its descendants are removed, leaving behind any remaining portions of affected Prefixes. This may add elements to fill in gaps around the subtracted Prefix.

For example, if s is {::0/126}, and we subtract ::0/128, then s will become {::1/128, ::2/127}.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.