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) Equal(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.NewTree(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 NewTree(items []Interface) (Tree, error)
  • func (t Tree) Len() int
  • func (t Tree) Lookup(item Interface) Interface
  • func (t Tree) String() string
  • func (t Tree) Superset(item Interface) Interface

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

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

	// string representation of the item
	fmt.Stringer
}

An Interface for various methods on intervals.

type Tree

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

Tree partially implements an interval tree.

func NewTree

func NewTree(items []Interface) (Tree, error)

NewTree builds and returns an immutable tree. Bails out and returns an error on duplicate items.

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