diff options
Diffstat (limited to 'middleware/file/tree')
| -rw-r--r-- | middleware/file/tree/all.go | 48 | ||||
| -rw-r--r-- | middleware/file/tree/elem.go | 136 | ||||
| -rw-r--r-- | middleware/file/tree/less.go | 59 | ||||
| -rw-r--r-- | middleware/file/tree/less_test.go | 81 | ||||
| -rw-r--r-- | middleware/file/tree/print.go | 62 | ||||
| -rw-r--r-- | middleware/file/tree/tree.go | 455 |
6 files changed, 0 insertions, 841 deletions
diff --git a/middleware/file/tree/all.go b/middleware/file/tree/all.go deleted file mode 100644 index fd806365f..000000000 --- a/middleware/file/tree/all.go +++ /dev/null @@ -1,48 +0,0 @@ -package tree - -// All traverses tree and returns all elements -func (t *Tree) All() []*Elem { - if t.Root == nil { - return nil - } - found := t.Root.all(nil) - return found -} - -func (n *Node) all(found []*Elem) []*Elem { - if n.Left != nil { - found = n.Left.all(found) - } - found = append(found, n.Elem) - if n.Right != nil { - found = n.Right.all(found) - } - return found -} - -// 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 (t *Tree) Do(fn func(e *Elem) bool) bool { - if t.Root == nil { - return false - } - return t.Root.do(fn) -} - -func (n *Node) do(fn func(e *Elem) bool) (done bool) { - if n.Left != nil { - done = n.Left.do(fn) - if done { - return - } - } - done = fn(n.Elem) - if done { - return - } - if n.Right != nil { - done = n.Right.do(fn) - } - return -} diff --git a/middleware/file/tree/elem.go b/middleware/file/tree/elem.go deleted file mode 100644 index 6317cc912..000000000 --- a/middleware/file/tree/elem.go +++ /dev/null @@ -1,136 +0,0 @@ -package tree - -import "github.com/miekg/dns" - -// Elem is an element in the tree. -type Elem struct { - m map[uint16][]dns.RR - name string // owner name -} - -// newElem returns a new elem. -func newElem(rr dns.RR) *Elem { - e := Elem{m: make(map[uint16][]dns.RR)} - e.m[rr.Header().Rrtype] = []dns.RR{rr} - return &e -} - -// 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]. -func (e *Elem) Types(qtype uint16, qname ...string) []dns.RR { - rrs := e.m[qtype] - - if rrs != nil && len(qname) > 0 { - copied := make([]dns.RR, len(rrs)) - for i := range rrs { - copied[i] = dns.Copy(rrs[i]) - copied[i].Header().Name = qname[0] - } - return copied - } - return rrs -} - -// All returns all RRs from e, regardless of type. -func (e *Elem) All() []dns.RR { - list := []dns.RR{} - for _, rrs := range e.m { - list = append(list, rrs...) - } - return list -} - -// Name returns the name for this node. -func (e *Elem) Name() string { - if e.name != "" { - return e.name - } - for _, rrs := range e.m { - e.name = rrs[0].Header().Name - return e.name - } - return "" -} - -// Empty returns true is e does not contain any RRs, i.e. is an -// empty-non-terminal. -func (e *Elem) Empty() bool { - return len(e.m) == 0 -} - -// Insert inserts rr into e. If rr is equal to existing rrs this is a noop. -func (e *Elem) Insert(rr dns.RR) { - t := rr.Header().Rrtype - if e.m == nil { - e.m = make(map[uint16][]dns.RR) - e.m[t] = []dns.RR{rr} - return - } - rrs, ok := e.m[t] - if !ok { - e.m[t] = []dns.RR{rr} - return - } - for _, er := range rrs { - if equalRdata(er, rr) { - return - } - } - - rrs = append(rrs, rr) - e.m[t] = rrs -} - -// Delete removes rr from e. When e is empty after the removal the returned bool is true. -func (e *Elem) Delete(rr dns.RR) (empty bool) { - if e.m == nil { - return true - } - - t := rr.Header().Rrtype - rrs, ok := e.m[t] - if !ok { - return - } - - for i, er := range rrs { - if equalRdata(er, rr) { - rrs = removeFromSlice(rrs, i) - e.m[t] = rrs - empty = len(rrs) == 0 - if empty { - delete(e.m, t) - } - return - } - } - return -} - -// Less is a tree helper function that calls less. -func Less(a *Elem, name string) int { return less(name, a.Name()) } - -// Assuming the same type and name this will check if the rdata is equal as well. -func equalRdata(a, b dns.RR) bool { - switch x := a.(type) { - // TODO(miek): more types, i.e. all types. + tests for this. - case *dns.A: - return x.A.Equal(b.(*dns.A).A) - case *dns.AAAA: - return x.AAAA.Equal(b.(*dns.AAAA).AAAA) - case *dns.MX: - if x.Mx == b.(*dns.MX).Mx && x.Preference == b.(*dns.MX).Preference { - return true - } - } - return false -} - -// removeFromSlice removes index i from the slice. -func removeFromSlice(rrs []dns.RR, i int) []dns.RR { - if i >= len(rrs) { - return rrs - } - rrs = append(rrs[:i], rrs[i+1:]...) - return rrs -} diff --git a/middleware/file/tree/less.go b/middleware/file/tree/less.go deleted file mode 100644 index 3b8340088..000000000 --- a/middleware/file/tree/less.go +++ /dev/null @@ -1,59 +0,0 @@ -package tree - -import ( - "bytes" - - "github.com/miekg/dns" -) - -// less returns <0 when a is less than b, 0 when they are equal and -// >0 when a is larger than b. -// The function orders names in DNSSEC canonical order: RFC 4034s section-6.1 -// -// See http://bert-hubert.blogspot.co.uk/2015/10/how-to-do-fast-canonical-ordering-of.html -// for a blog article on this implementation, although here we still go label by label. -// -// The values of a and b are *not* lowercased before the comparison! -func less(a, b string) int { - i := 1 - aj := len(a) - bj := len(b) - for { - ai, oka := dns.PrevLabel(a, i) - bi, okb := dns.PrevLabel(b, i) - if oka && okb { - return 0 - } - - // sadly this []byte will allocate... TODO(miek): check if this is needed - // for a name, otherwise compare the strings. - ab := []byte(a[ai:aj]) - bb := []byte(b[bi:bj]) - doDDD(ab) - doDDD(bb) - - res := bytes.Compare(ab, bb) - if res != 0 { - return res - } - - i++ - aj, bj = ai, bi - } -} - -func doDDD(b []byte) { - lb := len(b) - for i := 0; i < lb; i++ { - if i+3 < lb && b[i] == '\\' && isDigit(b[i+1]) && isDigit(b[i+2]) && isDigit(b[i+3]) { - b[i] = dddToByte(b[i:]) - for j := i + 1; j < lb-3; j++ { - b[j] = b[j+3] - } - lb -= 3 - } - } -} - -func isDigit(b byte) bool { return b >= '0' && b <= '9' } -func dddToByte(s []byte) byte { return (s[1]-'0')*100 + (s[2]-'0')*10 + (s[3] - '0') } diff --git a/middleware/file/tree/less_test.go b/middleware/file/tree/less_test.go deleted file mode 100644 index ed021b66f..000000000 --- a/middleware/file/tree/less_test.go +++ /dev/null @@ -1,81 +0,0 @@ -package tree - -import ( - "sort" - "strings" - "testing" -) - -type set []string - -func (p set) Len() int { return len(p) } -func (p set) Swap(i, j int) { p[i], p[j] = p[j], p[i] } -func (p set) Less(i, j int) bool { d := less(p[i], p[j]); return d <= 0 } - -func TestLess(t *testing.T) { - tests := []struct { - in []string - out []string - }{ - { - []string{"aaa.powerdns.de", "bbb.powerdns.net.", "xxx.powerdns.com."}, - []string{"xxx.powerdns.com.", "aaa.powerdns.de", "bbb.powerdns.net."}, - }, - { - []string{"aaa.POWERDNS.de", "bbb.PoweRdnS.net.", "xxx.powerdns.com."}, - []string{"xxx.powerdns.com.", "aaa.POWERDNS.de", "bbb.PoweRdnS.net."}, - }, - { - []string{"aaa.aaaa.aa.", "aa.aaa.a.", "bbb.bbbb.bb."}, - []string{"aa.aaa.a.", "aaa.aaaa.aa.", "bbb.bbbb.bb."}, - }, - { - []string{"aaaaa.", "aaa.", "bbb."}, - []string{"aaa.", "aaaaa.", "bbb."}, - }, - { - []string{"a.a.a.a.", "a.a.", "a.a.a."}, - []string{"a.a.", "a.a.a.", "a.a.a.a."}, - }, - { - []string{"example.", "z.example.", "a.example."}, - []string{"example.", "a.example.", "z.example."}, - }, - { - []string{"a.example.", "Z.a.example.", "z.example.", "yljkjljk.a.example.", "\\001.z.example.", "example.", "*.z.example.", "\\200.z.example.", "zABC.a.EXAMPLE."}, - []string{"example.", "a.example.", "yljkjljk.a.example.", "Z.a.example.", "zABC.a.EXAMPLE.", "z.example.", "\\001.z.example.", "*.z.example.", "\\200.z.example."}, - }, - { - // RFC3034 example. - []string{"a.example.", "Z.a.example.", "z.example.", "yljkjljk.a.example.", "example.", "*.z.example.", "zABC.a.EXAMPLE."}, - []string{"example.", "a.example.", "yljkjljk.a.example.", "Z.a.example.", "zABC.a.EXAMPLE.", "z.example.", "*.z.example."}, - }, - } - -Tests: - for j, test := range tests { - // Need to lowercase these example as the Less function does lowercase for us anymore. - for i, b := range test.in { - test.in[i] = strings.ToLower(b) - } - for i, b := range test.out { - test.out[i] = strings.ToLower(b) - } - - sort.Sort(set(test.in)) - for i := 0; i < len(test.in); i++ { - if test.in[i] != test.out[i] { - t.Errorf("Test %d: expected %s, got %s\n", j, test.out[i], test.in[i]) - n := "" - for k, in := range test.in { - if k+1 == len(test.in) { - n = "\n" - } - t.Logf("%s <-> %s\n%s", in, test.out[k], n) - } - continue Tests - } - - } - } -} diff --git a/middleware/file/tree/print.go b/middleware/file/tree/print.go deleted file mode 100644 index bd86ef690..000000000 --- a/middleware/file/tree/print.go +++ /dev/null @@ -1,62 +0,0 @@ -package tree - -import "fmt" - -// Print prints a Tree. Main use is to aid in debugging. -func (t *Tree) Print() { - if t.Root == nil { - fmt.Println("<nil>") - } - t.Root.print() -} - -func (n *Node) print() { - q := newQueue() - q.push(n) - - nodesInCurrentLevel := 1 - nodesInNextLevel := 0 - - for !q.empty() { - do := q.pop() - nodesInCurrentLevel-- - - if do != nil { - fmt.Print(do.Elem.Name(), " ") - q.push(do.Left) - q.push(do.Right) - nodesInNextLevel += 2 - } - if nodesInCurrentLevel == 0 { - fmt.Println() - } - nodesInCurrentLevel = nodesInNextLevel - nodesInNextLevel = 0 - } - fmt.Println() -} - -type queue []*Node - -// newQueue returns a new queue. -func newQueue() queue { - q := queue([]*Node{}) - return q -} - -// push pushes n to the end of the queue. -func (q *queue) push(n *Node) { - *q = append(*q, n) -} - -// pop pops the first element off the queue. -func (q *queue) pop() *Node { - n := (*q)[0] - *q = (*q)[1:] - return n -} - -// empty returns true when the queue contains zero nodes. -func (q *queue) empty() bool { - return len(*q) == 0 -} 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. -*/ |