netipds

package module
v0.1.9 Latest Latest
Warning

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

 Go to latest Published: May 11, 2025 License: MIT Imports: 5 Imported by: 2

README

netipds

Go Reference Go Report Card codecov

This package builds on the netip/netipx family by adding two immutable, trie-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. According to the benchmarks at iprbench, it is one of the fastest and most memory-efficient packages among its peers.
  • 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"]

See docs for more details.

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.
Note about Value-Copying in PrefixMap

When generating an immutable PrefixMap from a PrefixMapBuilder (using PrefixMapBuilder.PrefixMap), the builder's values are copied by assignment, so please be careful if you are storing pointers (https://github.com/aromatt/netipds/issues/27 aims to improve this).

The same warning applies to any PrefixMap method that returns a new PrefixMap.

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.

Pre-1.0 Breaking Changes

The following versions have breaking API changes:

  • v0.1.9: Removed Strict methods, removed PrefixMapBuilder.Get, moved String methods behind build tag and renamed them, removed Lazy mode

Documentation

Overview

Package netipds builds on the net/netip & go4.org/netipx family of packages by adding two immutable, trie-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.

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]) 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]) 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]) 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.

For example, if m contains 1.2.3.4/32 and 1.2.0.0/16, then filtering by a PrefixSet that includes 1.2.3.0/24 would retain 1.2.3.4/32 and remove 1.2.0.0/16.

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) (parent netip.Prefix, val T, ok 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]) RootOf 

func (m *PrefixMap[T]) RootOf(p netip.Prefix) (root netip.Prefix, val T, ok 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]) Size added in v0.1.1 

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

Size returns the number of entries in m.

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 {
	// 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.

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]) 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.

Values are copied to the PrefixMap using assignment, so use caution if you are storing pointers.

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.

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) All4 added in v0.1.9 

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

All4 returns an iterator over all IPv4 Prefixes in s.

func (*PrefixSet) All6 added in v0.1.9 

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

All6 returns an iterator over all IPv6 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. ::0/128 and ::1/128.

func (*PrefixSet) AllCompact4 added in v0.1.9 

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

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

Note: AllCompact4 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) AllCompact6 added in v0.1.9 

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

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

Note: AllCompact6 does not merge siblings, so the result may contain complete sets of sibling prefixes, e.g. ::0/128 and ::1/128.

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) 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) 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) 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) (parent netip.Prefix, ok 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) 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) (root netip.Prefix, ok 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) Size added in v0.1.1 

func (s *PrefixSet) Size() int

Size returns the number of elements in s.

type PrefixSetBuilder 

type PrefixSetBuilder struct {
	// 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.

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.

For example, if s contains 1.2.3.4/32 and 1.2.0.0/16, then filtering by a PrefixSet that includes 1.2.3.0/24 would retain 1.2.3.4/32 and remove 1.2.0.0/16.

To remove sections of Prefixes, see PrefixSetBuilder.Subtract and PrefixSetBuilder.SubtractPrefix.

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) 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.