tree

Documentation

Overview

Package tree is a minimal interval tree implementation.

All interval types implementing the tree.Interface can use this library for fast lookups and a stringified tree representation.

Application example: The author uses it mainly for fast O(log n) lookups in IP ranges where patricia-tries with O(1) are not feasible. The tree representation allows a clear overview of the IP address block nestings.

Example (Interface)

package main

import (
	"fmt"
	"log"

	"github.com/gaissmai/go-inet/v2/inet"
	"github.com/gaissmai/go-inet/v2/tree"
)

// augment inet.Block
type item struct {
	inet.Block
}

func mustNewItem(b string) item {
	bb, err := inet.ParseBlock(b)
	if err != nil {
		panic(err)
	}
	return item{bb}
}

// ###########################################
// implement the tree.Interface for inet.Block
// ###########################################

func (a item) Less(i tree.Interface) bool {
	b := i.(item)
	return a.Block.Less(b.Block)
}

func (a item) Equals(i tree.Interface) bool {
	b := i.(item)
	return a.Block == b.Block
}

func (a item) Covers(i tree.Interface) bool {
	b := i.(item)
	return a.Block.Covers(b.Block)
}

func (a item) String() string {
	return a.Block.String()
}

// #####################################################

var is = []tree.Interface{
	mustNewItem("2001:db8::/32"),
	mustNewItem("2001:db8:1:fffe::/48"),
	mustNewItem("2001:db8:1:fffe::0-2001:db8:1:fffe::7a"),
	mustNewItem("2001:db8:2:fffe::4"),
	mustNewItem("2001:db8:2:fffe::5"),
	mustNewItem("2001:db8:2::/48"),
	mustNewItem("2001:db8:2:fffe::6"),
	mustNewItem("2001:db8:1:fffe::7"),
	mustNewItem("127.0.0.1"),
	mustNewItem("127.0.0.0/8"),
	mustNewItem("::1"),
	mustNewItem("10.0.0.16-10.1.3.254"),
	mustNewItem("10.0.0.233"),
	mustNewItem("fe80::/10"),
	mustNewItem("169.254.0.0/16"),
}

func main() {

	t, err := tree.New(is)
	if err != nil {
		log.Fatal(err)
	}

	fmt.Println(t)
	fmt.Printf("Len:         %v\n", t.Len())
	fmt.Println()

	b := mustNewItem("2001:db8:1:fffe::2-2001:db8:1:fffe::3")
	fmt.Printf("Lookup:      %v => %v\n", b, t.Lookup(b))
	fmt.Printf("Superset:    %v => %v\n", b, t.Superset(b))
	fmt.Println()

	b = mustNewItem("fc00::1")
	fmt.Printf("Lookup:      %v => %v\n", b, t.Lookup(b))
	fmt.Printf("Superset:    %v => %v\n", b, t.Superset(b))

}

Output:

▼
├─ 10.0.0.16-10.1.3.254
│  └─ 10.0.0.233/32
├─ 127.0.0.0/8
│  └─ 127.0.0.1/32
├─ 169.254.0.0/16
├─ ::1/128
├─ 2001:db8::/32
│  ├─ 2001:db8:1::/48
│  │  └─ 2001:db8:1:fffe::-2001:db8:1:fffe::7a
│  │     └─ 2001:db8:1:fffe::7/128
│  └─ 2001:db8:2::/48
│     ├─ 2001:db8:2:fffe::4/128
│     ├─ 2001:db8:2:fffe::5/128
│     └─ 2001:db8:2:fffe::6/128
└─ fe80::/10

Len:         15

Lookup:      2001:db8:1:fffe::2/127 => 2001:db8:1:fffe::-2001:db8:1:fffe::7a
Superset:    2001:db8:1:fffe::2/127 => 2001:db8::/32

Lookup:      fc00::1/128 => <nil>
Superset:    fc00::1/128 => <nil>

Index

• type Interface
• type Tree
  • func New(items []Interface) (*Tree, error)
  • func (t *Tree) Duplicates() []Interface
  • func (t *Tree) Len() int
  • func (t *Tree) Lookup(item Interface) Interface
  • func (t *Tree) String() string
  • func (t *Tree) Superset(item Interface) Interface
  • func (t *Tree) Walk(fn WalkFunc) error
• type WalkFunc

Examples

• Package (Interface)

Types

type Interface

type Interface interface {
	// Covers returns true if and only if the receiver truly covers item.
	// When receiver covers item, they cannot be equal, thus Equal then will return false!
	// If Covers is true, Less also must be true.
	Covers(Interface) bool

	// Less reports whether the receiver should be sorted before the item.
	// HINT: All supersets must be ordered to the left of their subsets!
	Less(Interface) bool

	// Equals reports whether receiver and item are equal.
	Equals(Interface) bool

	// Stringer interface
	String() string
}

An Interface for various methods on intervals.

type Tree

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

Tree partially implements an interval tree.

func New

func New(items []Interface) (*Tree, error)

New builds and returns an immutable tree. Returns an error != nil on duplicate items.

func (*Tree) Duplicates

func (t *Tree) Duplicates() []Interface

Duplicates returns the conflicting items. Returns nil if there was no error during New().

func (*Tree) Len

func (t *Tree) Len() int

Len returns the number of items in tree.

func (*Tree) Lookup

func (t *Tree) Lookup(item Interface) Interface

Lookup returns the item itself or the *smallest* superset (bottom-up). If item is not covered at all by tree, then the returned item is nil.

Example: Can be used in IP-ranges or IP-CIDRs to find the so called longest-prefix-match.

func (*Tree) String

func (t *Tree) String() string

String returns the ordered tree as a directory graph. The items are stringified using their fmt.Stringer interface.

func (*Tree) Superset

func (t *Tree) Superset(item Interface) Interface

Superset returns the *biggest* superset (top-down) or the item itself. Find first interval covering item in root level. If item is not contained at all in tree, then the returned item is nil. Extremely degraded trees with heavy overlaps result in O(n).

func (*Tree) Walk

func (t *Tree) Walk(fn WalkFunc) error

Walk walks the tree, calling fn for each item in the tree.

The items are walked in natural pre-order, as presented by String(). Every error returned by fn stops the walk and is returned to the caller.

type WalkFunc

type WalkFunc func(depth int, item, parent Interface, childs []Interface) error

WalkFunc is the type of the function called by Walk to visit each item.

depth is 0 for root items.

item is the visited item.

parent is nil for root items.

childs is the slice of direct descendants, childs is nil for leaf items.

If the function returns a non-nil error, Walk stops and returns that error.