6 files changed, 841 insertions, 0 deletions
diff --git a/plugin/file/tree/all.go b/plugin/file/tree/all.go
new file mode 100644
index 000000000..fd806365f
--- /dev/null
+++ b/plugin/file/tree/all.go
@@ -0,0 +1,48 @@
+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/plugin/file/tree/elem.go b/plugin/file/tree/elem.go
new file mode 100644
index 000000000..6317cc912
--- /dev/null
+++ b/plugin/file/tree/elem.go
@@ -0,0 +1,136 @@
+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/plugin/file/tree/less.go b/plugin/file/tree/less.go
new file mode 100644
index 000000000..3b8340088
--- /dev/null
+++ b/plugin/file/tree/less.go
@@ -0,0 +1,59 @@
+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/plugin/file/tree/less_test.go b/plugin/file/tree/less_test.go
new file mode 100644
index 000000000..ed021b66f
--- /dev/null
+++ b/plugin/file/tree/less_test.go
@@ -0,0 +1,81 @@
+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/plugin/file/tree/print.go b/plugin/file/tree/print.go
new file mode 100644
index 000000000..bd86ef690
--- /dev/null
+++ b/plugin/file/tree/print.go
@@ -0,0 +1,62 @@
+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/plugin/file/tree/tree.go b/plugin/file/tree/tree.go
new file mode 100644
index 000000000..ed33c09a4
--- /dev/null
+++ b/plugin/file/tree/tree.go
@@ -0,0 +1,455 @@
+// 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.
+*/