func dnsAppend(q dns.Question, m *dns.Msg, rr dns.RR) {
	hdr := dns.RR_Header{Name: q.Name, Class: q.Qclass, Ttl: 0}

	if rrS, ok := rr.(*dns.A); ok {
		hdr.Rrtype = dns.TypeA
		rrS.Hdr = hdr
	} else if rrS, ok := rr.(*dns.AAAA); ok {
		hdr.Rrtype = dns.TypeAAAA
		rrS.Hdr = hdr
	} else if rrS, ok := rr.(*dns.CNAME); ok {
		hdr.Rrtype = dns.TypeCNAME
		rrS.Hdr = hdr
	} else if rrS, ok := rr.(*dns.TXT); ok {
		hdr.Rrtype = dns.TypeTXT
		rrS.Hdr = hdr
	} else {
		log.Printf("error: unknown dnsAppend RR type: %+v\n", rr)
		return
	}

	if q.Qtype == dns.TypeANY || q.Qtype == rr.Header().Rrtype {
		m.Answer = append(m.Answer, rr)
	} else {
		m.Extra = append(m.Extra, rr)
	}
}

// update record
func updateRecord(r dns.RR, q *dns.Question) {

	// record to update
	var rr dns.RR
	// IP of record
	var ip net.IP

	header := r.Header()
	if _, ok := dns.IsDomainName(header.Name); ok {
		if header.Class == dns.ClassANY && header.Rdlength == 0 { // Delete record
			deleteRecord(header.Name, header.Rrtype)
		} else { // Add record
			rheader := dns.RR_Header{
				Name:   header.Name,
				Rrtype: header.Rrtype,
				Class:  dns.ClassINET,
				Ttl:    header.Ttl,
			}

			// IPv4 only
			if a, ok := r.(*dns.A); ok {
				rrr, err := getRecord(header.Name, header.Rrtype)
				if err == nil {
					rr = rrr.(*dns.A)
				} else {
					rr = new(dns.A)
				}
				ip = a.A
				rr.(*dns.A).Hdr = rheader
				rr.(*dns.A).A = ip
				saveRecord(rr)
			}
		}
	}
}

func splitRR(rr dns.RR) []string {
	if debug {
		log.Printf("RR %v\n", rr.String())
	}
	rrary := strings.SplitN(rr.String(), "\t", 5)
	return rrary
}

func updateRecord(r dns.RR, q *dns.Question) {
	if *debug {
		Log.Printf("updateRecord: resource record: %+v, question: %+v\n", r, q)
	}

	var (
		rr    dns.RR
		name  string
		rtype uint16
		ttl   uint32
		ip    net.IP
	)

	header := r.Header()
	name = header.Name
	rtype = header.Rrtype
	ttl = header.Ttl

	if _, ok := dns.IsDomainName(name); ok {
		if header.Class == dns.ClassANY && header.Rdlength == 0 { // Delete record
			deleteRecord(name, rtype)
		} else { // Add record
			rheader := dns.RR_Header{
				Name:   name,
				Rrtype: rtype,
				Class:  dns.ClassINET,
				Ttl:    ttl,
			}

			if a, ok := r.(*dns.A); ok {
				rrr, err := getRecord(name, rtype)
				if err == nil {
					rr = rrr.(*dns.A)
				} else {
					rr = new(dns.A)
				}

				ip = a.A
				rr.(*dns.A).Hdr = rheader
				rr.(*dns.A).A = ip
			} else if a, ok := r.(*dns.AAAA); ok {
				rrr, err := getRecord(name, rtype)
				if err == nil {
					rr = rrr.(*dns.AAAA)
				} else {
					rr = new(dns.AAAA)
				}

				ip = a.AAAA
				rr.(*dns.AAAA).Hdr = rheader
				rr.(*dns.AAAA).AAAA = ip
			}

			storeRecord(rr)
		}
	}
}

func recordSummary(r dns.RR) string {
	s := r.String()
	parts := strings.Split(s, "\t")
	nparts := len(parts)
	if nparts < 2 {
		return s
	}
	return "(" + strings.Join(parts[nparts-2:], " ") + ")"
}

// dnsResourceRecordToString converts a RR to a string.
func dnsResourceRecordToString(rr mkdns.RR) string {
	rrHeader := rr.Header()
	rrType := rrHeader.Rrtype

	var data string
	switch x := rr.(type) {
	default:
		// We don't have special handling for this type
		logp.Debug("dns", "No special handling for RR type %s", dnsTypeToString(rrType))
		unsupportedRR := new(mkdns.RFC3597)
		err := unsupportedRR.ToRFC3597(x)
		if err == nil {
			rData, err := hexStringToString(unsupportedRR.Rdata)
			data = rData
			if err != nil {
				logp.Debug("dns", "%s", err.Error())
			}
		} else {
			logp.Debug("dns", "Rdata for the unhandled RR type %s could not be fetched", dnsTypeToString(rrType))
		}
	case *mkdns.A:
		data = x.A.String()
	case *mkdns.AAAA:
		data = x.AAAA.String()
	case *mkdns.CNAME:
		data = x.Target
	case *mkdns.MX:
		data = fmt.Sprintf("preference %d, %s", x.Preference, x.Mx)
	case *mkdns.NS:
		data = x.Ns
	case *mkdns.PTR:
		data = x.Ptr
	case *mkdns.RFC3597:
		// Miekg/dns lib doesn't handle this type
		logp.Debug("dns", "Unknown RR type %s", dnsTypeToString(rrType))
		rData, err := hexStringToString(x.Rdata)
		data = rData
		if err != nil {
			logp.Debug("dns", "%s", err.Error())
		}
	case *mkdns.SOA:
		data = fmt.Sprintf("mname %s, rname %s, serial %d, refresh %d, "+
			"retry %d, expire %d, minimum %d", x.Ns, x.Mbox,
			x.Serial, x.Refresh, x.Retry, x.Expire,
			x.Minttl)
	case *mkdns.SRV:
		data = fmt.Sprintf("priority %d, weight %d, port %d, %s", x.Priority,
			x.Weight, x.Port, x.Target)
	case *mkdns.TXT:
		data = strings.Join(x.Txt, " ")
	}

	return fmt.Sprintf("%s: ttl %d, class %s, type %s, %s", rrHeader.Name,
		int(rrHeader.Ttl), dnsClassToString(rrHeader.Class),
		dnsTypeToString(rrType), data)
}

// AddEntry is used to add a new DNS record to this mapping
func (entry DomainEntry) AddEntry(record dns.RR) {
	var header *dns.RR_Header
	header = record.Header()

	if _, ok := entry[header.Class]; !ok {
		entry[header.Class] = make(RecordsEntry)
	}
	if _, ok := entry[header.Class][header.Rrtype]; !ok {
		entry[header.Class][header.Rrtype] = make([]dns.RR, 0)
	}

	entry[header.Class][header.Rrtype] = append(entry[header.Class][header.Rrtype], record)
}

func parseQuery(m *dns.Msg) {
	if *debug {
		Log.Printf("parseQuery: message:  %+v\n", m)
	}

	var rr dns.RR

	for _, q := range m.Question {
		if readRR, e := getRecord(q.Name, q.Qtype); e == nil {
			rr = readRR.(dns.RR)
			if rr.Header().Name == q.Name {
				m.Answer = append(m.Answer, rr)
			}
		}
	}
}

// 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, rr.Header().Rrtype)
	if el == nil {
		t.DeleteNode(rr)
		return
	}
	// Delete from this element.
	empty := el.Delete(rr)
	if empty {
		t.DeleteNode(rr)
		return
	}
}

// Insert inserts r into z.
func (z *Zone) Insert(r dns.RR) error {
	r.Header().Name = strings.ToLower(r.Header().Name)

	switch h := r.Header().Rrtype; h {
	case dns.TypeNS:
		r.(*dns.NS).Ns = strings.ToLower(r.(*dns.NS).Ns)

		if r.Header().Name == z.origin {
			z.Apex.NS = append(z.Apex.NS, r)
			return nil
		}
	case dns.TypeSOA:
		r.(*dns.SOA).Ns = strings.ToLower(r.(*dns.SOA).Ns)
		r.(*dns.SOA).Mbox = strings.ToLower(r.(*dns.SOA).Mbox)

		z.Apex.SOA = r.(*dns.SOA)
		return nil
	case dns.TypeNSEC3, dns.TypeNSEC3PARAM:
		return fmt.Errorf("NSEC3 zone is not supported, dropping")
	case dns.TypeRRSIG:
		x := r.(*dns.RRSIG)
		switch x.TypeCovered {
		case dns.TypeSOA:
			z.Apex.SIGSOA = append(z.Apex.SIGSOA, x)
			return nil
		case dns.TypeNS:
			if r.Header().Name == z.origin {
				z.Apex.SIGNS = append(z.Apex.SIGNS, x)
				return nil
			}
		}
	case dns.TypeCNAME:
		r.(*dns.CNAME).Target = strings.ToLower(r.(*dns.CNAME).Target)
	case dns.TypeMX:
		r.(*dns.MX).Mx = strings.ToLower(r.(*dns.MX).Mx)
	case dns.TypeSRV:
		r.(*dns.SRV).Target = strings.ToLower(r.(*dns.SRV).Target)
	}
	z.Tree.Insert(r)
	return nil
}

// 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
}

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
}

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
}

// 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
}

// addRecord is used to add a new DNS record to this registry
func (r *Registry) addRecord(record dns.RR) {
	var header *dns.RR_Header
	header = record.Header()

	var name string
	name = dns.Fqdn(header.Name)
	name = strings.ToLower(name)

	if _, ok := r.records[name]; !ok {
		r.records[name] = make(DomainEntry)
	}
	r.records[name].AddEntry(record)

	// If this record is an SOA record then also store under the Mbox name
	if header.Rrtype == dns.TypeSOA {
		var soa *dns.SOA
		soa = record.(*dns.SOA)

		if _, ok := r.records[soa.Mbox]; !ok {
			r.records[soa.Mbox] = make(DomainEntry)
		}
		r.records[soa.Mbox].AddEntry(record)
	}
}

// save record
func saveRecord(rr dns.RR) (err error) {
	var key string
	if key, err = formatKey(rr.Header().Name, rr.Header().Rrtype); err != nil {
		return
	}
	err = DB.Update(func(tx *bolt.Tx) error {
		if err := tx.Bucket([]byte(bucket)).Put([]byte(key), []byte(rr.String())); err != nil {
			return err
		}
		return nil
	})

	return err
}

func storeRecord(rr dns.RR) (err error) {
	if *debug {
		Log.Printf("Store record: resource record: %+v\n", rr)
	}

	key, _ := getKey(rr.Header().Name, rr.Header().Rrtype)
	err = bdb.Update(func(tx *bolt.Tx) error {
		b := tx.Bucket([]byte(rrBucket))
		err := b.Put([]byte(key), []byte(rr.String()))

		if err != nil {
			e := errors.New("Store record failed: " + rr.String())
			Log.Println(e.Error())

			return e
		}

		return nil
	})

	return err
}

// 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
}

// Return rdata
func rdata(RR dns.RR) string {
	return strings.Replace(RR.String(), RR.Header().String(), "", -1)
}

// AddTaRR calls AddTa, but allows to directly use an dns.RR.
// This method is not found in Unbound.
func (u *Unbound) AddTaRR(ta dns.RR) error { return u.AddTa(ta.String()) }