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) (empty bool)
  • func (e *Elem) Empty() bool
  • func (e *Elem) Insert(rr dns.RR)
  • func (e *Elem) Name() string
  • func (e *Elem) Types(qtype uint16, qname ...string) []dns.RR
• type Node
• type Tree
  • func (t *Tree) All() []*Elem
  • func (t *Tree) Delete(rr dns.RR)
  • func (t *Tree) DeleteMax()
  • func (t *Tree) DeleteMin()
  • func (t *Tree) Do(fn func(e *Elem) bool) bool
  • 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)

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) (empty bool)

Delete removes rr from e. When e is empty after the removal the returned bool is true.

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 this is a noop.

func (*Elem) Name

func (e *Elem) Name() string

Name returns the name for this node.

func (*Elem) Types

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

Types returns the RRs with type qtype from e. If qname is given (only the first one is used), the RR are copied and the owner is replaced with qname[0].

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

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

Delete removes rr from the tree, is the node turns empty, that node is deleted with DeleteNode.

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

func (t *Tree) Do(fn func(e *Elem) bool) bool

Do performs fn on all values stored in the tree. A boolean is returned indicating whether the Do traversal was interrupted by an Operation returning true. If fn alters stored values' sort relationships, future tree operation behaviors are undefined.

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.