netipds

package module
v0.1.6 Latest Latest
Warning

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

 Go to latest Published: Aug 12, 2024 License: MIT Imports: 5 Imported by: 2

README

netipds

Go Reference Go Report Card codecov

This package builds on the netip/netipx family, adding two new collection types:

  • PrefixMap[T], an immutable, tree-based map with netip.Prefix keys
  • PrefixSet, an immutable set type for netip.Prefix, offering better performance and a more comprehensive feature set than netipx.IPSet

Both are backed by a binary radix tree.

Project Goals

  • Provide efficient, thread-safe, immutable collection types for IP networks
  • Integrate well with the netip and netipx packages
  • Support use cases that are not covered by other libraries

Usage

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

Example
// Build a PrefixMap
psb := netipds.PrefixMapBuilder[string]
pmb.Set(netip.MustParsePrefix("1.2.0.0/16"), "hello")
pmb.Set(netip.MustParsePrefix("1.2.3.0/24"), "world")
pm := pmb.PrefixMap()

// (Prepare some Prefixes for queries)
p8 := netip.MustParsePrefix("1.0.0.0/8")
p16 := netip.MustParsePrefix("1.2.0.0/16")
p24 := netip.MustParsePrefix("1.2.3.0/24")
p32 := netip.MustParsePrefix("1.2.3.4/32")

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

// Ask if the PrefixMap contains an exact entry.
val, ok := pm.Contains(p32) // => false

// Ask if a Prefix has any ancestor in the PrefixMap.
val, ok := pm.Encompasses(p32) // => true

// Fetch a Prefix's nearest ancestor.
prefix, val, ok := pm.ParentOf(p32) // => (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(p32).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(p8).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.
https://github.com/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 (and thus GC-friendly) collection types that integrate well with the netip family and offer a comprehensive API.

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