/** fill data into result */
static int
fill_res(struct ub_result* res, struct ub_packed_rrset_key* answer,
	uint8_t* finalcname, struct query_info* rq)
{
	size_t i;
	struct packed_rrset_data* data;
	if(!answer) {
		if(finalcname) {
			if(!fill_canon(res, finalcname))
				return 0; /* out of memory */
		}
		res->data = (char**)calloc(1, sizeof(char*));
		res->len = (int*)calloc(1, sizeof(int));
		return (res->data && res->len);
	}
	data = (struct packed_rrset_data*)answer->entry.data;
	if(query_dname_compare(rq->qname, answer->rk.dname) != 0) {
		if(!fill_canon(res, answer->rk.dname))
			return 0; /* out of memory */
	} else	res->canonname = NULL;
	res->data = (char**)calloc(data->count+1, sizeof(char*));
	res->len = (int*)calloc(data->count+1, sizeof(int));
	if(!res->data || !res->len)
		return 0; /* out of memory */
	for(i=0; i<data->count; i++) {
		/* remove rdlength from rdata */
		res->len[i] = (int)(data->rr_len[i] - 2);
		res->data[i] = memdup(data->rr_data[i]+2, (size_t)res->len[i]);
		if(!res->data[i])
			return 0; /* out of memory */
	}
	res->data[data->count] = NULL;
	res->len[data->count] = 0;
	return 1;
}

/* nsec3_cache_compare for rbtree */
int
nsec3_hash_cmp(const void* c1, const void* c2) 
{
	struct nsec3_cached_hash* h1 = (struct nsec3_cached_hash*)c1;
	struct nsec3_cached_hash* h2 = (struct nsec3_cached_hash*)c2;
	uint8_t* s1, *s2;
	size_t s1len, s2len;
	int c = query_dname_compare(h1->dname, h2->dname);
	if(c != 0)
		return c;
	/* compare parameters */
	/* if both malformed, its equal, robustness */
	if(nsec3_get_algo(h1->nsec3, h1->rr) !=
		nsec3_get_algo(h2->nsec3, h2->rr)) {
		if(nsec3_get_algo(h1->nsec3, h1->rr) <
			nsec3_get_algo(h2->nsec3, h2->rr))
			return -1;
		return 1;
	}
	if(nsec3_get_iter(h1->nsec3, h1->rr) !=
		nsec3_get_iter(h2->nsec3, h2->rr)) {
		if(nsec3_get_iter(h1->nsec3, h1->rr) <
			nsec3_get_iter(h2->nsec3, h2->rr))
			return -1;
		return 1;
	}
	(void)nsec3_get_salt(h1->nsec3, h1->rr, &s1, &s1len);
	(void)nsec3_get_salt(h2->nsec3, h2->rr, &s2, &s2len);
	if(s1len != s2len) {
		if(s1len < s2len)
			return -1;
		return 1;
	}
	return memcmp(s1, s2, s1len);
}

int 
ub_rrset_compare(void* k1, void* k2)
{
	struct ub_packed_rrset_key* key1 = (struct ub_packed_rrset_key*)k1;
	struct ub_packed_rrset_key* key2 = (struct ub_packed_rrset_key*)k2;
	int c;
	if(key1 == key2)
		return 0;
	if(key1->rk.type != key2->rk.type) {
		if(key1->rk.type < key2->rk.type)
			return -1;
		return 1;
	}
	if(key1->rk.dname_len != key2->rk.dname_len) {
		if(key1->rk.dname_len < key2->rk.dname_len)
			return -1;
		return 1;
	}
	if((c=query_dname_compare(key1->rk.dname, key2->rk.dname)) != 0)
		return c;
	if(key1->rk.rrset_class != key2->rk.rrset_class) {
		if(key1->rk.rrset_class < key2->rk.rrset_class)
			return -1;
		return 1;
	}
	if(key1->rk.flags != key2->rk.flags) {
		if(key1->rk.flags < key2->rk.flags)
			return -1;
		return 1;
	}
	return 0;
}

void local_zones_del_data(struct local_zones* zones, 
	uint8_t* name, size_t len, int labs, uint16_t dclass)
{
	/* find zone */
	struct local_zone* z;
	struct local_data* d;
	lock_rw_rdlock(&zones->lock);
	z = local_zones_lookup(zones, name, len, labs, dclass);
	if(!z) {
		/* no such zone, we're done */
		lock_rw_unlock(&zones->lock);
		return;
	}
	lock_rw_wrlock(&z->lock);
	lock_rw_unlock(&zones->lock);

	/* find the domain */
	d = lz_find_node(z, name, len, labs);
	if(d) {
		/* no memory recycling for zone deletions ... */
		d->rrsets = NULL;
		/* did we delete the soa record ? */
		if(query_dname_compare(d->name, z->name) == 0)
			z->soa = NULL;

		/* cleanup the empty nonterminals for this name */
		del_empty_term(z, d, name, len, labs);
	}

	lock_rw_unlock(&z->lock);
}

int
iter_ds_toolow(struct dns_msg* msg, struct delegpt* dp)
{
	/* if for query example.com, there is example.com SOA or a subdomain
	 * of example.com, then we are too low and need to fetch NS. */
	size_t i;
	/* if we have a DNAME or CNAME we are probably wrong */
	/* if we have a qtype DS in the answer section, its fine */
	for(i=0; i < msg->rep->an_numrrsets; i++) {
		struct ub_packed_rrset_key* s = msg->rep->rrsets[i];
		if(ntohs(s->rk.type) == LDNS_RR_TYPE_DNAME ||
			ntohs(s->rk.type) == LDNS_RR_TYPE_CNAME) {
			/* not the right answer, maybe too low, check the
			 * RRSIG signer name (if there is any) for a hint
			 * that it is from the dp zone anyway */
			uint8_t* sname;
			size_t slen;
			val_find_rrset_signer(s, &sname, &slen);
			if(sname && query_dname_compare(dp->name, sname)==0)
				return 0; /* it is fine, from the right dp */
			return 1;
		}
		if(ntohs(s->rk.type) == LDNS_RR_TYPE_DS)
			return 0; /* fine, we have a DS record */
	}
	for(i=msg->rep->an_numrrsets;
		i < msg->rep->an_numrrsets + msg->rep->ns_numrrsets; i++) {
		struct ub_packed_rrset_key* s = msg->rep->rrsets[i];
		if(ntohs(s->rk.type) == LDNS_RR_TYPE_SOA) {
			if(dname_subdomain_c(s->rk.dname, msg->qinfo.qname))
				return 1; /* point is too low */
			if(query_dname_compare(s->rk.dname, dp->name)==0)
				return 0; /* right dp */
		}
		if(ntohs(s->rk.type) == LDNS_RR_TYPE_NSEC ||
			ntohs(s->rk.type) == LDNS_RR_TYPE_NSEC3) {
			uint8_t* sname;
			size_t slen;
			val_find_rrset_signer(s, &sname, &slen);
			if(sname && query_dname_compare(dp->name, sname)==0)
				return 0; /* it is fine, from the right dp */
			return 1;
		}
	}
	/* we do not know */
	return 1;
}

/** print root forwards */
static int
print_root_fwds(SSL* ssl, struct iter_forwards* fwds, uint8_t* root)
{
	struct delegpt* dp;
	dp = forwards_lookup(fwds, root, LDNS_RR_CLASS_IN);
	if(!dp)
		return ssl_printf(ssl, "off (using root hints)\n");
	/* if dp is returned it must be the root */
	log_assert(query_dname_compare(dp->name, root)==0);
	return ssl_print_name_dp(ssl, NULL, root, LDNS_RR_CLASS_IN, dp);
}

/** Test dname_get_shared_topdomain */
static void
dname_test_topdomain(void)
{
	unit_show_func("util/data/dname.c", "dname_get_shared_topdomain");
	unit_assert( query_dname_compare(
		dname_get_shared_topdomain(
			(uint8_t*)"",
			(uint8_t*)""), 
		(uint8_t*)"") == 0);
	unit_assert( query_dname_compare(
		dname_get_shared_topdomain(
			(uint8_t*)"\003www\007example\003com",
			(uint8_t*)"\003www\007example\003com"), 
		(uint8_t*)"\003www\007example\003com") == 0);
	unit_assert( query_dname_compare(
		dname_get_shared_topdomain(
			(uint8_t*)"\003www\007example\003com",
			(uint8_t*)"\003bla\007example\003com"), 
		(uint8_t*)"\007example\003com") == 0);
}

/**
 * Answer CH class queries.
 * @param w: worker
 * @param qinfo: query info. Pointer into packet buffer.
 * @param edns: edns info from query.
 * @param pkt: packet buffer.
 * @return: true if a reply is to be sent.
 */
static int
answer_chaos(struct worker* w, struct query_info* qinfo, 
	struct edns_data* edns, sldns_buffer* pkt)
{
	struct config_file* cfg = w->env.cfg;
	if(qinfo->qtype != LDNS_RR_TYPE_ANY && qinfo->qtype != LDNS_RR_TYPE_TXT)
		return 0;
	if(query_dname_compare(qinfo->qname, 
		(uint8_t*)"\002id\006server") == 0 ||
		query_dname_compare(qinfo->qname, 
		(uint8_t*)"\010hostname\004bind") == 0)
	{
		if(cfg->hide_identity) 
			return 0;
		if(cfg->identity==NULL || cfg->identity[0]==0) {
			char buf[MAXHOSTNAMELEN+1];
			if (gethostname(buf, MAXHOSTNAMELEN) == 0) {
				buf[MAXHOSTNAMELEN] = 0;
				chaos_replystr(pkt, buf, edns, w);
			} else 	{
				log_err("gethostname: %s", strerror(errno));
				chaos_replystr(pkt, "no hostname", edns, w);
			}
		}
		else 	chaos_replystr(pkt, cfg->identity, edns, w);
		return 1;
	}
	if(query_dname_compare(qinfo->qname, 
		(uint8_t*)"\007version\006server") == 0 ||
		query_dname_compare(qinfo->qname, 
		(uint8_t*)"\007version\004bind") == 0)
	{
		if(cfg->hide_version) 
			return 0;
		if(cfg->version==NULL || cfg->version[0]==0)
			chaos_replystr(pkt, PACKAGE_STRING, edns, w);
		else 	chaos_replystr(pkt, cfg->version, edns, w);
		return 1;
	}
	return 0;
}

/** fill data into result */
static int
fill_res(struct ub_result* res, struct ub_packed_rrset_key* answer,
	uint8_t* finalcname, struct query_info* rq, struct reply_info* rep)
{
	size_t i;
	struct packed_rrset_data* data;
	res->ttl = 0;
	if(!answer) {
		if(finalcname) {
			if(!fill_canon(res, finalcname))
				return 0; /* out of memory */
		}
		if(rep->rrset_count != 0)
			res->ttl = (int)rep->ttl;
		res->data = (char**)calloc(1, sizeof(char*));
		res->len = (int*)calloc(1, sizeof(int));
		return (res->data && res->len);
	}
	data = (struct packed_rrset_data*)answer->entry.data;
	if(query_dname_compare(rq->qname, answer->rk.dname) != 0) {
		if(!fill_canon(res, answer->rk.dname))
			return 0; /* out of memory */
	} else	res->canonname = NULL;
	res->data = (char**)calloc(data->count+1, sizeof(char*));
	res->len = (int*)calloc(data->count+1, sizeof(int));
	if(!res->data || !res->len)
		return 0; /* out of memory */
	for(i=0; i<data->count; i++) {
		/* remove rdlength from rdata */
		res->len[i] = (int)(data->rr_len[i] - 2);
		res->data[i] = memdup(data->rr_data[i]+2, (size_t)res->len[i]);
		if(!res->data[i])
			return 0; /* out of memory */
	}
	/* ttl for positive answers, from CNAME and answer RRs */
	if(data->count != 0) {
		size_t j;
		res->ttl = (int)data->ttl;
		for(j=0; j<rep->an_numrrsets; j++) {
			struct packed_rrset_data* d =
				(struct packed_rrset_data*)rep->rrsets[j]->
				entry.data;
			if((int)d->ttl < res->ttl)
				res->ttl = (int)d->ttl;
		}
	}
	/* ttl for negative answers */
	if(data->count == 0 && rep->rrset_count != 0)
		res->ttl = (int)rep->ttl;
	res->data[data->count] = NULL;
	res->len[data->count] = 0;
	return 1;
}

int 
rate_compfunc(void* key1, void* key2)
{
	struct rate_key* k1 = (struct rate_key*)key1;
	struct rate_key* k2 = (struct rate_key*)key2;
	if(k1->namelen != k2->namelen) {
		if(k1->namelen < k2->namelen)
			return -1;
		return 1;
	}
	return query_dname_compare(k1->name, k2->name);
}

struct delegpt_ns*
delegpt_find_ns(struct delegpt* dp, uint8_t* name, size_t namelen)
{
	struct delegpt_ns* p = dp->nslist;
	while(p) {
		if(namelen == p->namelen && 
			query_dname_compare(name, p->name) == 0) {
			return p;
		}
		p = p->next;
	}
	return NULL;
}

/** check that there is no data element that matches the RRSIG */
static int
no_data_for_rrsig(struct reply_info* rep, struct ub_packed_rrset_key* rrsig)
{
	size_t i;
	for(i=0; i<rep->rrset_count; i++) {
		if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_RRSIG)
			continue;
		if(query_dname_compare(rep->rrsets[i]->rk.dname, 
			rrsig->rk.dname) == 0)
			/* only name is compared right now */
			return 0;
	}
	return 1;
}

int iter_dp_cangodown(struct query_info* qinfo, struct delegpt* dp)
{
	/* no delegation point, do not see how we can go down,
	 * robust check, it should really exist */
	if(!dp) return 0;

	/* see if dp equals the qname, then we cannot go down further */
	if(query_dname_compare(qinfo->qname, dp->name) == 0)
		return 0;
	/* if dp is one label above the name we also cannot go down further */
	if(dname_count_labels(qinfo->qname) == dp->namelabs+1)
		return 0;
	return 1;
}

int 
query_info_compare(void* m1, void* m2)
{
	struct query_info* msg1 = (struct query_info*)m1;
	struct query_info* msg2 = (struct query_info*)m2;
	int mc;
	/* from most different to least different for speed */
	COMPARE_IT(msg1->qtype, msg2->qtype);
	if((mc = query_dname_compare(msg1->qname, msg2->qname)) != 0)
		return mc;
	log_assert(msg1->qname_len == msg2->qname_len);
	COMPARE_IT(msg1->qclass, msg2->qclass);
	return 0;
#undef COMPARE_IT
}

int 
infra_compfunc(void* key1, void* key2)
{
	struct infra_key* k1 = (struct infra_key*)key1;
	struct infra_key* k2 = (struct infra_key*)key2;
	int r = sockaddr_cmp(&k1->addr, k1->addrlen, &k2->addr, k2->addrlen);
	if(r != 0)
		return r;
	if(k1->namelen != k2->namelen) {
		if(k1->namelen < k2->namelen)
			return -1;
		return 1;
	}
	return query_dname_compare(k1->zonename, k2->zonename);
}

struct ub_packed_rrset_key* reply_find_rrset(struct reply_info* rep,
	uint8_t* name, size_t namelen, uint16_t type, uint16_t dclass)
{
	size_t i;
	for(i=0; i<rep->rrset_count; i++) {
		struct ub_packed_rrset_key* s = rep->rrsets[i];
		if(ntohs(s->rk.type) == type && 
			ntohs(s->rk.rrset_class) == dclass && 
			namelen == s->rk.dname_len &&
			query_dname_compare(name, s->rk.dname) == 0) {
			return s;
		}
	}
	return NULL;
}

/** see if rrset has signer name as one of the rrsig signers */
static int
rrset_has_signer(struct ub_packed_rrset_key* rrset, uint8_t* name, size_t len)
{
	struct packed_rrset_data* d = (struct packed_rrset_data*)rrset->
		entry.data;
	size_t i;
	for(i = d->count; i< d->count+d->rrsig_count; i++) {
		if(d->rr_len[i] > 2+18+len) {
			/* at least rdatalen + signature + signame (+1 sig)*/
			if(query_dname_compare(name, d->rr_data[i]+2+18) == 0)
			{
				return 1;
			}
		}
	}
	return 0;
}

/** check if negative cache is still valid */
static void check_zone_invariants(struct val_neg_cache* neg, 
	struct val_neg_zone* zone)
{
	unit_assert(zone->nsec3_hash == 0);
	unit_assert(zone->tree.cmp == &val_neg_data_compare);
	unit_assert(zone->count != 0);

	if(zone->tree.count == 0)
		unit_assert(!zone->in_use);
	else {
		if(!zone->in_use) {
			/* details on error */
			log_nametypeclass(0, "zone", zone->name, 0, 0);
			log_err("inuse %d count=%d tree.count=%d",
				zone->in_use, zone->count, 
				(int)zone->tree.count);
			if(negverbose)
				print_neg_cache(neg);
		}
		unit_assert(zone->in_use);
	}
	
	if(zone->parent) {
		unit_assert(zone->parent->count >= zone->count);
		if(zone->parent->in_use) {
			unit_assert(zone->parent->count > zone->count);
		}
		unit_assert(zone->parent->labs == zone->labs-1);
		/* and parent must be one label shorter */
		unit_assert(zone->name[0] == (zone->len-zone->parent->len-1));
		unit_assert(query_dname_compare(zone->name + zone->name[0]+1,
			zone->parent->name) == 0);
	} else {
		/* must be apex */
		unit_assert(dname_is_root(zone->name));
	}
	/* tree property: */
	unit_assert(zone->count == sum_zone_subtree_inuse(neg, zone));

	/* check structure of zone data tree */
	checkzonetree(zone);
}

uint8_t* 
reply_find_final_cname_target(struct query_info* qinfo, struct reply_info* rep)
{
	uint8_t* sname = qinfo->qname;
	size_t snamelen = qinfo->qname_len;
	size_t i;
	for(i=0; i<rep->an_numrrsets; i++) {
		struct ub_packed_rrset_key* s = rep->rrsets[i];
		/* follow CNAME chain (if any) */
		if(ntohs(s->rk.type) == LDNS_RR_TYPE_CNAME && 
			ntohs(s->rk.rrset_class) == qinfo->qclass && 
			snamelen == s->rk.dname_len &&
			query_dname_compare(sname, s->rk.dname) == 0) {
			get_cname_target(s, &sname, &snamelen);
		}
	}
	if(sname != qinfo->qname)
		return sname;
	return NULL;
}

int
val_chase_cname(struct query_info* qchase, struct reply_info* rep,
	size_t* cname_skip) {
	size_t i;
	/* skip any DNAMEs, go to the CNAME for next part */
	for(i = *cname_skip; i < rep->an_numrrsets; i++) {
		if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_CNAME &&
			query_dname_compare(qchase->qname, rep->rrsets[i]->
				rk.dname) == 0) {
			qchase->qname = NULL;
			get_cname_target(rep->rrsets[i], &qchase->qname,
				&qchase->qname_len);
			if(!qchase->qname)
				return 0; /* bad CNAME rdata */
			(*cname_skip) = i+1;
			return 1;
		}
	}
	return 0; /* CNAME classified but no matching CNAME ?! */
}