tree

package

v0.0.0-...-a8fb01b Latest Latest Go to latest Published: Sep 18, 2016 License: Apache-2.0 Imports: 2 Imported by: 0

Details

Valid go.mod file

The Go module system was introduced in Go 1.11 and is the official dependency management solution for Go.
Redistributable license

Redistributable licenses place minimal restrictions on how software can be used, modified, and redistributed.
Tagged version

Modules with tagged versions give importers more predictable builds.
Stable version

When a project reaches major version v1 it is considered stable.
Learn more about best practices

Repository

github.com/shawnps/coredns

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.

Constants ¶

View Source

const (
	TD234 = iota
	BU23
)

View Source

const Mode = BU23

Operation mode of the LLRB tree.

Variables ¶

This section is empty.

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.

const (
	// Red as false give us the defined behaviour that new nodes are red. Although this
	// is incorrect for the root node, that is resolved on the first insertion.
	Red   Color = false
	Black Color = true
)

type Elem ¶

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

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) 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) []dns.RR

Types returns the RRs with type qtype from e.

type Node ¶

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

A Node represents a node in the LLRB tree.

type Result ¶

type Result int

Result is a result of a Search.

const (
	Found Result = iota
	NameError
	EmptyNonTerminal
	Delegation
)

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) DeleteNode ¶

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

DeleteNode deletes the node that matches rr according to Less().

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

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

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

func (*Tree) Search ¶

func (t *Tree) Search(qname string, qtype uint16) (*Elem, Result)

Search returns the first match of qname/qtype in the Tree.

func (*Tree) SearchGlue ¶

func (t *Tree) SearchGlue(qname string) (*Elem, Result)

SearchGlue returns the first match of qname/(A/AAAA) in the Tree.

Source Files ¶

View all Source files

?	: This menu
/	: Search site
f or F	: Jump to
y or Y	: Canonical URL