tree

Documentation

Overview

Package tree implements Left-Leaning Red Black trees as described by Robert Sedgewick.

More details relating to the implementation are available at the following locations:

http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf http://www.cs.princeton.edu/~rs/talks/LLRB/Java/RedBlackBST.java http://www.teachsolaisgames.com/articles/balanced_left_leaning.html

Heavily modified by Miek Gieben for use in DNS zones.

Index

• func Less(a *Elem, name string) int
• type Color
• type Elem
  • func (e *Elem) All() []dns.RR
  • func (e *Elem) Delete(rr dns.RR)
  • func (e *Elem) Empty() bool
  • func (e *Elem) Insert(rr dns.RR)
  • func (e *Elem) Name() string
  • func (e *Elem) Type(qtype uint16) []dns.RR
  • func (e *Elem) TypeForWildcard(qtype uint16, qname string) []dns.RR
  • func (e *Elem) Types() []uint16
• type Node
• type Tree
  • func (t *Tree) All() []*Elem
  • func (t *Tree) AuthWalk(fn func(*Elem, map[uint16][]dns.RR, bool) error) error
  • func (t *Tree) Delete(rr dns.RR)
  • func (t *Tree) DeleteMax()
  • func (t *Tree) DeleteMin()
  • func (t *Tree) Glue(nsrrs []dns.RR, do bool) []dns.RR
  • func (t *Tree) Insert(rr dns.RR)
  • func (t *Tree) Len() int
  • func (t *Tree) Max() *Elem
  • func (t *Tree) Min() *Elem
  • func (t *Tree) Next(qname string) (*Elem, bool)
  • func (t *Tree) Prev(qname string) (*Elem, bool)
  • func (t *Tree) Print()
  • func (t *Tree) Search(qname string) (*Elem, bool)
  • func (t *Tree) Walk(fn func(*Elem, map[uint16][]dns.RR) error) error

Functions

func Less

func Less(a *Elem, name string) int

Less is a tree helper function that calls less.

Types

type Color

type Color bool

A Color represents the color of a Node.

type Elem

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

Elem is an element in the tree.

func (*Elem) All

func (e *Elem) All() []dns.RR

All returns all RRs from e, regardless of type.

func (*Elem) Delete

func (e *Elem) Delete(rr dns.RR)

Delete removes all RRs of type rr.Header().Rrtype from e.

func (*Elem) Empty

func (e *Elem) Empty() bool

Empty returns true is e does not contain any RRs, i.e. is an empty-non-terminal.

func (*Elem) Insert

func (e *Elem) Insert(rr dns.RR)

Insert inserts rr into e. If rr is equal to existing RRs, the RR will be added anyway.

func (*Elem) Name

func (e *Elem) Name() string

Name returns the name for this node.

func (*Elem) Type

func (e *Elem) Type(qtype uint16) []dns.RR

Type returns the RRs with type qtype from e.

func (*Elem) TypeForWildcard

func (e *Elem) TypeForWildcard(qtype uint16, qname string) []dns.RR

TypeForWildcard returns the RRs with type qtype from e. The ownername returned is set to qname.

func (*Elem) Types

func (e *Elem) Types() []uint16

Types returns the types of the records in e. The returned list is not sorted.

type Node

type Node struct {
	Elem        *Elem
	Left, Right *Node
	Color       Color
}

A Node represents a node in the LLRB tree.

type Tree

type Tree struct {
	Root  *Node // Root node of the tree.
	Count int   // Number of elements stored.
}

A Tree manages the root node of an LLRB tree. Public methods are exposed through this type.

func (*Tree) All

func (t *Tree) All() []*Elem

All traverses tree and returns all elements.

func (*Tree) AuthWalk

func (t *Tree) AuthWalk(fn func(*Elem, map[uint16][]dns.RR, bool) error) error

AuthWalk performs fn on all authoritative values stored in the tree in pre-order depth first. If a non-nil error is returned the AuthWalk was interrupted by an fn returning that error. If fn alters stored values' sort relationships, future tree operation behaviors are undefined.

The fn function will be called with 3 arguments, the current element, a map containing all the RRs for this element and a boolean if this name is considered authoritative.

func (*Tree) Delete

func (t *Tree) Delete(rr dns.RR)

Delete removes all RRs of type rr.Header().Rrtype from e. If after the deletion of rr the node is empty the entire node is deleted.

func (*Tree) DeleteMax

func (t *Tree) DeleteMax()

DeleteMax deletes the node with the maximum value in the tree.

func (*Tree) DeleteMin

func (t *Tree) DeleteMin()

DeleteMin deletes the node with the minimum value in the tree.

func (*Tree) Glue

func (t *Tree) Glue(nsrrs []dns.RR, do bool) []dns.RR

Glue returns any potential glue records for nsrrs.

func (*Tree) Insert

func (t *Tree) Insert(rr dns.RR)

Insert inserts rr into the Tree at the first match found with e or when a nil node is reached.

func (*Tree) Len

func (t *Tree) Len() int

Len returns the number of elements stored in the Tree.

func (*Tree) Max

func (t *Tree) Max() *Elem

Max returns the maximum value stored in the tree.

func (*Tree) Min

func (t *Tree) Min() *Elem

Min returns the minimum value stored in the tree.

func (*Tree) Next

func (t *Tree) Next(qname string) (*Elem, bool)

Next returns the smallest value equal to or greater than the qname according to Less().

func (*Tree) Prev

func (t *Tree) Prev(qname string) (*Elem, bool)

Prev returns the greatest value equal to or less than the qname according to Less().

func (*Tree) Print

func (t *Tree) Print()

Print prints a Tree. Main use is to aid in debugging.

func (*Tree) Search

func (t *Tree) Search(qname string) (*Elem, bool)

Search returns the first match of qname in the Tree.

func (*Tree) Walk

func (t *Tree) Walk(fn func(*Elem, map[uint16][]dns.RR) error) error

Walk performs fn on all authoritative values stored in the tree in in-order depth first. If a non-nil error is returned the Walk was interrupted by an fn returning that error. If fn alters stored values' sort relationships, future tree operation behaviors are undefined.