aboutsummaryrefslogtreecommitdiff
path: root/middleware/file/tree/tree.go
diff options
context:
space:
mode:
Diffstat (limited to 'middleware/file/tree/tree.go')
-rw-r--r--middleware/file/tree/tree.go455
1 files changed, 0 insertions, 455 deletions
diff --git a/middleware/file/tree/tree.go b/middleware/file/tree/tree.go
deleted file mode 100644
index ed33c09a4..000000000
--- a/middleware/file/tree/tree.go
+++ /dev/null
@@ -1,455 +0,0 @@
-// Copyright ©2012 The bíogo Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found at the end of this file.
-
-// 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.
-package tree
-
-import "github.com/miekg/dns"
-
-const (
- td234 = iota
- bu23
-)
-
-// Operation mode of the LLRB tree.
-const mode = bu23
-
-func init() {
- if mode != td234 && mode != bu23 {
- panic("tree: unknown mode")
- }
-}
-
-// A Color represents the color of a Node.
-type Color bool
-
-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
-)
-
-// A Node represents a node in the LLRB tree.
-type Node struct {
- Elem *Elem
- Left, Right *Node
- Color Color
-}
-
-// A Tree manages the root node of an LLRB tree. Public methods are exposed through this type.
-type Tree struct {
- Root *Node // Root node of the tree.
- Count int // Number of elements stored.
-}
-
-// Helper methods
-
-// color returns the effect color of a Node. A nil node returns black.
-func (n *Node) color() Color {
- if n == nil {
- return black
- }
- return n.Color
-}
-
-// (a,c)b -rotL-> ((a,)b,)c
-func (n *Node) rotateLeft() (root *Node) {
- // Assumes: n has two children.
- root = n.Right
- n.Right = root.Left
- root.Left = n
- root.Color = n.Color
- n.Color = red
- return
-}
-
-// (a,c)b -rotR-> (,(,c)b)a
-func (n *Node) rotateRight() (root *Node) {
- // Assumes: n has two children.
- root = n.Left
- n.Left = root.Right
- root.Right = n
- root.Color = n.Color
- n.Color = red
- return
-}
-
-// (aR,cR)bB -flipC-> (aB,cB)bR | (aB,cB)bR -flipC-> (aR,cR)bB
-func (n *Node) flipColors() {
- // Assumes: n has two children.
- n.Color = !n.Color
- n.Left.Color = !n.Left.Color
- n.Right.Color = !n.Right.Color
-}
-
-// fixUp ensures that black link balance is correct, that red nodes lean left,
-// and that 4 nodes are split in the case of BU23 and properly balanced in TD234.
-func (n *Node) fixUp() *Node {
- if n.Right.color() == red {
- if mode == td234 && n.Right.Left.color() == red {
- n.Right = n.Right.rotateRight()
- }
- n = n.rotateLeft()
- }
- if n.Left.color() == red && n.Left.Left.color() == red {
- n = n.rotateRight()
- }
- if mode == bu23 && n.Left.color() == red && n.Right.color() == red {
- n.flipColors()
- }
- return n
-}
-
-func (n *Node) moveRedLeft() *Node {
- n.flipColors()
- if n.Right.Left.color() == red {
- n.Right = n.Right.rotateRight()
- n = n.rotateLeft()
- n.flipColors()
- if mode == td234 && n.Right.Right.color() == red {
- n.Right = n.Right.rotateLeft()
- }
- }
- return n
-}
-
-func (n *Node) moveRedRight() *Node {
- n.flipColors()
- if n.Left.Left.color() == red {
- n = n.rotateRight()
- n.flipColors()
- }
- return n
-}
-
-// Len returns the number of elements stored in the Tree.
-func (t *Tree) Len() int {
- return t.Count
-}
-
-// Search returns the first match of qname in the Tree.
-func (t *Tree) Search(qname string) (*Elem, bool) {
- if t.Root == nil {
- return nil, false
- }
- n, res := t.Root.search(qname)
- if n == nil {
- return nil, res
- }
- return n.Elem, res
-}
-
-// search searches the tree for qname and type.
-func (n *Node) search(qname string) (*Node, bool) {
- for n != nil {
- switch c := Less(n.Elem, qname); {
- case c == 0:
- return n, true
- case c < 0:
- n = n.Left
- default:
- n = n.Right
- }
- }
-
- return n, false
-}
-
-// Insert inserts rr into the Tree at the first match found
-// with e or when a nil node is reached.
-func (t *Tree) Insert(rr dns.RR) {
- var d int
- t.Root, d = t.Root.insert(rr)
- t.Count += d
- t.Root.Color = black
-}
-
-// insert inserts rr in to the tree.
-func (n *Node) insert(rr dns.RR) (root *Node, d int) {
- if n == nil {
- return &Node{Elem: newElem(rr)}, 1
- } else if n.Elem == nil {
- n.Elem = newElem(rr)
- return n, 1
- }
-
- if mode == td234 {
- if n.Left.color() == red && n.Right.color() == red {
- n.flipColors()
- }
- }
-
- switch c := Less(n.Elem, rr.Header().Name); {
- case c == 0:
- n.Elem.Insert(rr)
- case c < 0:
- n.Left, d = n.Left.insert(rr)
- default:
- n.Right, d = n.Right.insert(rr)
- }
-
- if n.Right.color() == red && n.Left.color() == black {
- n = n.rotateLeft()
- }
- if n.Left.color() == red && n.Left.Left.color() == red {
- n = n.rotateRight()
- }
-
- if mode == bu23 {
- if n.Left.color() == red && n.Right.color() == red {
- n.flipColors()
- }
- }
-
- root = n
-
- return
-}
-
-// DeleteMin deletes the node with the minimum value in the tree.
-func (t *Tree) DeleteMin() {
- if t.Root == nil {
- return
- }
- var d int
- t.Root, d = t.Root.deleteMin()
- t.Count += d
- if t.Root == nil {
- return
- }
- t.Root.Color = black
-}
-
-func (n *Node) deleteMin() (root *Node, d int) {
- if n.Left == nil {
- return nil, -1
- }
- if n.Left.color() == black && n.Left.Left.color() == black {
- n = n.moveRedLeft()
- }
- n.Left, d = n.Left.deleteMin()
-
- root = n.fixUp()
-
- return
-}
-
-// DeleteMax deletes the node with the maximum value in the tree.
-func (t *Tree) DeleteMax() {
- if t.Root == nil {
- return
- }
- var d int
- t.Root, d = t.Root.deleteMax()
- t.Count += d
- if t.Root == nil {
- return
- }
- t.Root.Color = black
-}
-
-func (n *Node) deleteMax() (root *Node, d int) {
- if n.Left != nil && n.Left.color() == red {
- n = n.rotateRight()
- }
- if n.Right == nil {
- return nil, -1
- }
- if n.Right.color() == black && n.Right.Left.color() == black {
- n = n.moveRedRight()
- }
- n.Right, d = n.Right.deleteMax()
-
- root = n.fixUp()
-
- return
-}
-
-// Delete removes rr from the tree, is the node turns empty, that node is deleted with DeleteNode.
-func (t *Tree) Delete(rr dns.RR) {
- if t.Root == nil {
- return
- }
-
- el, _ := t.Search(rr.Header().Name)
- if el == nil {
- t.deleteNode(rr)
- return
- }
- // Delete from this element.
- empty := el.Delete(rr)
- if empty {
- t.deleteNode(rr)
- return
- }
-}
-
-// DeleteNode deletes the node that matches rr according to Less().
-func (t *Tree) deleteNode(rr dns.RR) {
- if t.Root == nil {
- return
- }
- var d int
- t.Root, d = t.Root.delete(rr)
- t.Count += d
- if t.Root == nil {
- return
- }
- t.Root.Color = black
-}
-
-func (n *Node) delete(rr dns.RR) (root *Node, d int) {
- if Less(n.Elem, rr.Header().Name) < 0 {
- if n.Left != nil {
- if n.Left.color() == black && n.Left.Left.color() == black {
- n = n.moveRedLeft()
- }
- n.Left, d = n.Left.delete(rr)
- }
- } else {
- if n.Left.color() == red {
- n = n.rotateRight()
- }
- if n.Right == nil && Less(n.Elem, rr.Header().Name) == 0 {
- return nil, -1
- }
- if n.Right != nil {
- if n.Right.color() == black && n.Right.Left.color() == black {
- n = n.moveRedRight()
- }
- if Less(n.Elem, rr.Header().Name) == 0 {
- n.Elem = n.Right.min().Elem
- n.Right, d = n.Right.deleteMin()
- } else {
- n.Right, d = n.Right.delete(rr)
- }
- }
- }
-
- root = n.fixUp()
- return
-}
-
-// Min returns the minimum value stored in the tree.
-func (t *Tree) Min() *Elem {
- if t.Root == nil {
- return nil
- }
- return t.Root.min().Elem
-}
-
-func (n *Node) min() *Node {
- for ; n.Left != nil; n = n.Left {
- }
- return n
-}
-
-// Max returns the maximum value stored in the tree.
-func (t *Tree) Max() *Elem {
- if t.Root == nil {
- return nil
- }
- return t.Root.max().Elem
-}
-
-func (n *Node) max() *Node {
- for ; n.Right != nil; n = n.Right {
- }
- return n
-}
-
-// Prev returns the greatest value equal to or less than the qname according to Less().
-func (t *Tree) Prev(qname string) (*Elem, bool) {
- if t.Root == nil {
- return nil, false
- }
-
- n := t.Root.floor(qname)
- if n == nil {
- return nil, false
- }
- return n.Elem, true
-}
-
-func (n *Node) floor(qname string) *Node {
- if n == nil {
- return nil
- }
- switch c := Less(n.Elem, qname); {
- case c == 0:
- return n
- case c <= 0:
- return n.Left.floor(qname)
- default:
- if r := n.Right.floor(qname); r != nil {
- return r
- }
- }
- return n
-}
-
-// Next returns the smallest value equal to or greater than the qname according to Less().
-func (t *Tree) Next(qname string) (*Elem, bool) {
- if t.Root == nil {
- return nil, false
- }
- n := t.Root.ceil(qname)
- if n == nil {
- return nil, false
- }
- return n.Elem, true
-}
-
-func (n *Node) ceil(qname string) *Node {
- if n == nil {
- return nil
- }
- switch c := Less(n.Elem, qname); {
- case c == 0:
- return n
- case c > 0:
- return n.Right.ceil(qname)
- default:
- if l := n.Left.ceil(qname); l != nil {
- return l
- }
- }
- return n
-}
-
-/*
-Copyright ©2012 The bíogo Authors. All rights reserved.
-
-Redistribution and use in source and binary forms, with or without
-modification, are permitted provided that the following conditions are met:
-
-* Redistributions of source code must retain the above copyright
- notice, this list of conditions and the following disclaimer.
-* Redistributions in binary form must reproduce the above copyright
- notice, this list of conditions and the following disclaimer in the
- documentation and/or other materials provided with the distribution.
-* Neither the name of the bíogo project nor the names of its authors and
- contributors may be used to endorse or promote products derived from this
- software without specific prior written permission.
-
-THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
-ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
-WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
-DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
-FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
-DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
-SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
-OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-*/