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) 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(e *Elem, rrs 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) 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(e *Elem, rrs map[uint16][]dns.RR) error) error

Walk performs fn on all values stored in the tree. 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.