src/org/xbill/DNS/Cache.java - platform/external/smack - Git at Google

 // Copyright (c) 1999-2004 Brian Wellington (bwelling@xbill.org)

 package org.xbill.DNS;

 import java.io.*;
 import java.util.*;

 /**
  * A cache of DNS records.  The cache obeys TTLs, so items are purged after
  * their validity period is complete.  Negative answers are cached, to
  * avoid repeated failed DNS queries.  The credibility of each RRset is
  * maintained, so that more credible records replace less credible records,
  * and lookups can specify the minimum credibility of data they are requesting.
  * @see RRset
  * @see Credibility
  *
  * @author Brian Wellington
  */

 public class Cache {

 private interface Element {
 	public boolean expired();
 	public int compareCredibility(int cred);
 	public int getType();
 }

 private static int
 limitExpire(long ttl, long maxttl) {
 	if (maxttl >= 0 && maxttl < ttl)
 		ttl = maxttl;
 	long expire = (System.currentTimeMillis() / 1000) + ttl;
 	if (expire < 0 || expire > Integer.MAX_VALUE)
 		return Integer.MAX_VALUE;
 	return (int)expire;
 }

 private static class CacheRRset extends RRset implements Element {
 	private static final long serialVersionUID = 5971755205903597024L;

 	int credibility;
 	int expire;

 	public
 	CacheRRset(Record rec, int cred, long maxttl) {
 		super();
 		this.credibility = cred;
 		this.expire = limitExpire(rec.getTTL(), maxttl);
 		addRR(rec);
 	}

 	public
 	CacheRRset(RRset rrset, int cred, long maxttl) {
 		super(rrset);
 		this.credibility = cred;
 		this.expire = limitExpire(rrset.getTTL(), maxttl);
 	}

 	public final boolean
 	expired() {
 		int now = (int)(System.currentTimeMillis() / 1000);
 		return (now >= expire);
 	}

 	public final int
 	compareCredibility(int cred) {
 		return credibility - cred;
 	}

 	public String
 	toString() {
 		StringBuffer sb = new StringBuffer();
 		sb.append(super.toString());
 		sb.append(" cl = ");
 		sb.append(credibility);
 		return sb.toString();
 	}
 }

 private static class NegativeElement implements Element {
 	int type;
 	Name name;
 	int credibility;
 	int expire;

 	public
 	NegativeElement(Name name, int type, SOARecord soa, int cred,
 			long maxttl)
 	{
 		this.name = name;
 		this.type = type;
 		long cttl = 0;
 		if (soa != null)
 			cttl = soa.getMinimum();
 		this.credibility = cred;
 		this.expire = limitExpire(cttl, maxttl);
 	}

 	public int
 	getType() {
 		return type;
 	}

 	public final boolean
 	expired() {
 		int now = (int)(System.currentTimeMillis() / 1000);
 		return (now >= expire);
 	}

 	public final int
 	compareCredibility(int cred) {
 		return credibility - cred;
 	}

 	public String
 	toString() {
 		StringBuffer sb = new StringBuffer();
 		if (type == 0)
 			sb.append("NXDOMAIN " + name);
 		else
 			sb.append("NXRRSET " + name + " " + Type.string(type));
 		sb.append(" cl = ");
 		sb.append(credibility);
 		return sb.toString();
 	}
 }

 private static class CacheMap extends LinkedHashMap {
 	private int maxsize = -1;

 	CacheMap(int maxsize) {
 		super(16, (float) 0.75, true);
 		this.maxsize = maxsize;
 	}

 	int
 	getMaxSize() {
 		return maxsize;
 	}

 	void
 	setMaxSize(int maxsize) {
 		/*
 		 * Note that this doesn't shrink the size of the map if
 		 * the maximum size is lowered, but it should shrink as
 		 * entries expire.
 		 */
 		this.maxsize = maxsize;
 	}

 	protected boolean removeEldestEntry(Map.Entry eldest) {
 		return maxsize >= 0 && size() > maxsize;
 	}
 }

 private CacheMap data;
 private int maxncache = -1;
 private int maxcache = -1;
 private int dclass;

 private static final int defaultMaxEntries = 50000;

 /**
  * Creates an empty Cache
  *
  * @param dclass The DNS class of this cache
  * @see DClass
  */
 public
 Cache(int dclass) {
 	this.dclass = dclass;
 	data = new CacheMap(defaultMaxEntries);
 }

 /**
  * Creates an empty Cache for class IN.
  * @see DClass
  */
 public
 Cache() {
 	this(DClass.IN);
 }

 /**
  * Creates a Cache which initially contains all records in the specified file.
  */
 public
 Cache(String file) throws IOException {
 	data = new CacheMap(defaultMaxEntries);
 	Master m = new Master(file);
 	Record record;
 	while ((record = m.nextRecord()) != null)
 		addRecord(record, Credibility.HINT, m);
 }

 private synchronized Object
 exactName(Name name) {
 	return data.get(name);
 }

 private synchronized void
 removeName(Name name) {
 	data.remove(name);
 }

 private synchronized Element []
 allElements(Object types) {
 	if (types instanceof List) {
 		List typelist = (List) types;
 		int size = typelist.size();
 		return (Element []) typelist.toArray(new Element[size]);
 	} else {
 		Element set = (Element) types;
 		return new Element[] {set};
 	}
 }

 private synchronized Element
 oneElement(Name name, Object types, int type, int minCred) {
 	Element found = null;

 	if (type == Type.ANY)
 		throw new IllegalArgumentException("oneElement(ANY)");
 	if (types instanceof List) {
 		List list = (List) types;
 		for (int i = 0; i < list.size(); i++) {
 			Element set = (Element) list.get(i);
 			if (set.getType() == type) {
 				found = set;
 				break;
 			}
 		}
 	} else {
 		Element set = (Element) types;
 		if (set.getType() == type)
 			found = set;
 	}
 	if (found == null)
 		return null;
 	if (found.expired()) {
 		removeElement(name, type);
 		return null;
 	}
 	if (found.compareCredibility(minCred) < 0)
 		return null;
 	return found;
 }

 private synchronized Element
 findElement(Name name, int type, int minCred) {
 	Object types = exactName(name);
 	if (types == null)
 		return null;
 	return oneElement(name, types, type, minCred);
 }

 private synchronized void
 addElement(Name name, Element element) {
 	Object types = data.get(name);
 	if (types == null) {
 		data.put(name, element);
 		return;
 	}
 	int type = element.getType();
 	if (types instanceof List) {
 		List list = (List) types;
 		for (int i = 0; i < list.size(); i++) {
 			Element elt = (Element) list.get(i);
 			if (elt.getType() == type) {
 				list.set(i, element);
 				return;
 			}
 		}
 		list.add(element);
 	} else {
 		Element elt = (Element) types;
 		if (elt.getType() == type)
 			data.put(name, element);
 		else {
 			LinkedList list = new LinkedList();
 			list.add(elt);
 			list.add(element);
 			data.put(name, list);
 		}
 	}
 }

 private synchronized void
 removeElement(Name name, int type) {
 	Object types = data.get(name);
 	if (types == null) {
 		return;
 	}
 	if (types instanceof List) {
 		List list = (List) types;
 		for (int i = 0; i < list.size(); i++) {
 			Element elt = (Element) list.get(i);
 			if (elt.getType() == type) {
 				list.remove(i);
 				if (list.size() == 0)
 					data.remove(name);
 				return;
 			}
 		}
 	} else {
 		Element elt = (Element) types;
 		if (elt.getType() != type)
 			return;
 		data.remove(name);
 	}
 }

 /** Empties the Cache. */
 public synchronized void
 clearCache() {
 	data.clear();
 }

 /**
  * Adds a record to the Cache.
  * @param r The record to be added
  * @param cred The credibility of the record
  * @param o The source of the record (this could be a Message, for example)
  * @see Record
  */
 public synchronized void
 addRecord(Record r, int cred, Object o) {
 	Name name = r.getName();
 	int type = r.getRRsetType();
 	if (!Type.isRR(type))
 		return;
 	Element element = findElement(name, type, cred);
 	if (element == null) {
 		CacheRRset crrset = new CacheRRset(r, cred, maxcache);
 		addRRset(crrset, cred);
 	} else if (element.compareCredibility(cred) == 0) {
 		if (element instanceof CacheRRset) {
 			CacheRRset crrset = (CacheRRset) element;
 			crrset.addRR(r);
 		}
 	}
 }

 /**
  * Adds an RRset to the Cache.
  * @param rrset The RRset to be added
  * @param cred The credibility of these records
  * @see RRset
  */
 public synchronized void
 addRRset(RRset rrset, int cred) {
 	long ttl = rrset.getTTL();
 	Name name = rrset.getName();
 	int type = rrset.getType();
 	Element element = findElement(name, type, 0);
 	if (ttl == 0) {
 		if (element != null && element.compareCredibility(cred) <= 0)
 			removeElement(name, type);
 	} else {
 		if (element != null && element.compareCredibility(cred) <= 0)
 			element = null;
 		if (element == null) {
 			CacheRRset crrset;
 			if (rrset instanceof CacheRRset)
 				crrset = (CacheRRset) rrset;
 			else
 				crrset = new CacheRRset(rrset, cred, maxcache);
 			addElement(name, crrset);
 		}
 	}
 }

 /**
  * Adds a negative entry to the Cache.
  * @param name The name of the negative entry
  * @param type The type of the negative entry
  * @param soa The SOA record to add to the negative cache entry, or null.
  * The negative cache ttl is derived from the SOA.
  * @param cred The credibility of the negative entry
  */
 public synchronized void
 addNegative(Name name, int type, SOARecord soa, int cred) {
 	long ttl = 0;
 	if (soa != null)
 		ttl = soa.getTTL();
 	Element element = findElement(name, type, 0);
 	if (ttl == 0) {
 		if (element != null && element.compareCredibility(cred) <= 0)
 			removeElement(name, type);
 	} else {
 		if (element != null && element.compareCredibility(cred) <= 0)
 			element = null;
 		if (element == null)
 			addElement(name, new NegativeElement(name, type,
 							     soa, cred,
 							     maxncache));
 	}
 }

 /**
  * Finds all matching sets or something that causes the lookup to stop.
  */
 protected synchronized SetResponse
 lookup(Name name, int type, int minCred) {
 	int labels;
 	int tlabels;
 	Element element;
 	Name tname;
 	Object types;
 	SetResponse sr;

 	labels = name.labels();

 	for (tlabels = labels; tlabels >= 1; tlabels--) {
 		boolean isRoot = (tlabels == 1);
 		boolean isExact = (tlabels == labels);

 		if (isRoot)
 			tname = Name.root;
 		else if (isExact)
 			tname = name;
 		else
 			tname = new Name(name, labels - tlabels);

 		types = data.get(tname);
 		if (types == null)
 			continue;

 		/*
 		 * If this is the name, look for the actual type or a CNAME
 		 * (unless it's an ANY query, where we return everything).
 		 * Otherwise, look for a DNAME.
 		 */
 		if (isExact && type == Type.ANY) {
 			sr = new SetResponse(SetResponse.SUCCESSFUL);
 			Element [] elements = allElements(types);
 			int added = 0;
 			for (int i = 0; i < elements.length; i++) {
 				element = elements[i];
 				if (element.expired()) {
 					removeElement(tname, element.getType());
 					continue;
 				}
 				if (!(element instanceof CacheRRset))
 					continue;
 				if (element.compareCredibility(minCred) < 0)
 					continue;
 				sr.addRRset((CacheRRset)element);
 				added++;
 			}
 			/* There were positive entries */
 			if (added > 0)
 				return sr;
 		} else if (isExact) {
 			element = oneElement(tname, types, type, minCred);
 			if (element != null &&
 			    element instanceof CacheRRset)
 			{
 				sr = new SetResponse(SetResponse.SUCCESSFUL);
 				sr.addRRset((CacheRRset) element);
 				return sr;
 			} else if (element != null) {
 				sr = new SetResponse(SetResponse.NXRRSET);
 				return sr;
 			}

 			element = oneElement(tname, types, Type.CNAME, minCred);
 			if (element != null &&
 			    element instanceof CacheRRset)
 			{
 				return new SetResponse(SetResponse.CNAME,
 						       (CacheRRset) element);
 			}
 		} else {
 			element = oneElement(tname, types, Type.DNAME, minCred);
 			if (element != null &&
 			    element instanceof CacheRRset)
 			{
 				return new SetResponse(SetResponse.DNAME,
 						       (CacheRRset) element);
 			}
 		}

 		/* Look for an NS */
 		element = oneElement(tname, types, Type.NS, minCred);
 		if (element != null && element instanceof CacheRRset)
 			return new SetResponse(SetResponse.DELEGATION,
 					       (CacheRRset) element);

 		/* Check for the special NXDOMAIN element. */
 		if (isExact) {
 			element = oneElement(tname, types, 0, minCred);
 			if (element != null)
 				return SetResponse.ofType(SetResponse.NXDOMAIN);
 		}

 	}
 	return SetResponse.ofType(SetResponse.UNKNOWN);
 }

 /**
  * Looks up Records in the Cache.  This follows CNAMEs and handles negatively
  * cached data.
  * @param name The name to look up
  * @param type The type to look up
  * @param minCred The minimum acceptable credibility
  * @return A SetResponse object
  * @see SetResponse
  * @see Credibility
  */
 public SetResponse
 lookupRecords(Name name, int type, int minCred) {
 	return lookup(name, type, minCred);
 }

 private RRset []
 findRecords(Name name, int type, int minCred) {
 	SetResponse cr = lookupRecords(name, type, minCred);
 	if (cr.isSuccessful())
 		return cr.answers();
 	else
 		return null;
 }

 /**
  * Looks up credible Records in the Cache (a wrapper around lookupRecords).
  * Unlike lookupRecords, this given no indication of why failure occurred.
  * @param name The name to look up
  * @param type The type to look up
  * @return An array of RRsets, or null
  * @see Credibility
  */
 public RRset []
 findRecords(Name name, int type) {
 	return findRecords(name, type, Credibility.NORMAL);
 }

 /**
  * Looks up Records in the Cache (a wrapper around lookupRecords).  Unlike
  * lookupRecords, this given no indication of why failure occurred.
  * @param name The name to look up
  * @param type The type to look up
  * @return An array of RRsets, or null
  * @see Credibility
  */
 public RRset []
 findAnyRecords(Name name, int type) {
 	return findRecords(name, type, Credibility.GLUE);
 }

 private final int
 getCred(int section, boolean isAuth) {
 	if (section == Section.ANSWER) {
 		if (isAuth)
 			return Credibility.AUTH_ANSWER;
 		else
 			return Credibility.NONAUTH_ANSWER;
 	} else if (section == Section.AUTHORITY) {
 		if (isAuth)
 			return Credibility.AUTH_AUTHORITY;
 		else
 			return Credibility.NONAUTH_AUTHORITY;
 	} else if (section == Section.ADDITIONAL) {
 		return Credibility.ADDITIONAL;
 	} else
 		throw new IllegalArgumentException("getCred: invalid section");
 }

 private static void
 markAdditional(RRset rrset, Set names) {
 	Record first = rrset.first();
 	if (first.getAdditionalName() == null)
 		return;

 	Iterator it = rrset.rrs();
 	while (it.hasNext()) {
 		Record r = (Record) it.next();
 		Name name = r.getAdditionalName();
 		if (name != null)
 			names.add(name);
 	}
 }

 /**
  * Adds all data from a Message into the Cache.  Each record is added with
  * the appropriate credibility, and negative answers are cached as such.
  * @param in The Message to be added
  * @return A SetResponse that reflects what would be returned from a cache
  * lookup, or null if nothing useful could be cached from the message.
  * @see Message
  */
 public SetResponse
 addMessage(Message in) {
 	boolean isAuth = in.getHeader().getFlag(Flags.AA);
 	Record question = in.getQuestion();
 	Name qname;
 	Name curname;
 	int qtype;
 	int qclass;
 	int cred;
 	int rcode = in.getHeader().getRcode();
 	boolean completed = false;
 	RRset [] answers, auth, addl;
 	SetResponse response = null;
 	boolean verbose = Options.check("verbosecache");
 	HashSet additionalNames;

 	if ((rcode != Rcode.NOERROR && rcode != Rcode.NXDOMAIN) ||
 	    question == null)
 		return null;

 	qname = question.getName();
 	qtype = question.getType();
 	qclass = question.getDClass();

 	curname = qname;

 	additionalNames = new HashSet();

 	answers = in.getSectionRRsets(Section.ANSWER);
 	for (int i = 0; i < answers.length; i++) {
 		if (answers[i].getDClass() != qclass)
 			continue;
 		int type = answers[i].getType();
 		Name name = answers[i].getName();
 		cred = getCred(Section.ANSWER, isAuth);
 		if ((type == qtype || qtype == Type.ANY) &&
 		    name.equals(curname))
 		{
 			addRRset(answers[i], cred);
 			completed = true;
 			if (curname == qname) {
 				if (response == null)
 					response = new SetResponse(
 							SetResponse.SUCCESSFUL);
 				response.addRRset(answers[i]);
 			}
 			markAdditional(answers[i], additionalNames);
 		} else if (type == Type.CNAME && name.equals(curname)) {
 			CNAMERecord cname;
 			addRRset(answers[i], cred);
 			if (curname == qname)
 				response = new SetResponse(SetResponse.CNAME,
 							   answers[i]);
 			cname = (CNAMERecord) answers[i].first();
 			curname = cname.getTarget();
 		} else if (type == Type.DNAME && curname.subdomain(name)) {
 			DNAMERecord dname;
 			addRRset(answers[i], cred);
 			if (curname == qname)
 				response = new SetResponse(SetResponse.DNAME,
 							   answers[i]);
 			dname = (DNAMERecord) answers[i].first();
 			try {
 				curname = curname.fromDNAME(dname);
 			}
 			catch (NameTooLongException e) {
 				break;
 			}
 		}
 	}

 	auth = in.getSectionRRsets(Section.AUTHORITY);
 	RRset soa = null, ns = null;
 	for (int i = 0; i < auth.length; i++) {
 		if (auth[i].getType() == Type.SOA &&
 		    curname.subdomain(auth[i].getName()))
 			soa = auth[i];
 		else if (auth[i].getType() == Type.NS &&
 			 curname.subdomain(auth[i].getName()))
 			ns = auth[i];
 	}
 	if (!completed) {
 		/* This is a negative response or a referral. */
 		int cachetype = (rcode == Rcode.NXDOMAIN) ? 0 : qtype;
 		if (rcode == Rcode.NXDOMAIN || soa != null || ns == null) {
 			/* Negative response */
 			cred = getCred(Section.AUTHORITY, isAuth);
 			SOARecord soarec = null;
 			if (soa != null)
 				soarec = (SOARecord) soa.first();
 			addNegative(curname, cachetype, soarec, cred);
 			if (response == null) {
 				int responseType;
 				if (rcode == Rcode.NXDOMAIN)
 					responseType = SetResponse.NXDOMAIN;
 				else
 					responseType = SetResponse.NXRRSET;
 				response = SetResponse.ofType(responseType);
 			}
 			/* DNSSEC records are not cached. */
 		} else {
 			/* Referral response */
 			cred = getCred(Section.AUTHORITY, isAuth);
 			addRRset(ns, cred);
 			markAdditional(ns, additionalNames);
 			if (response == null)
 				response = new SetResponse(
 							SetResponse.DELEGATION,
 							ns);
 		}
 	} else if (rcode == Rcode.NOERROR && ns != null) {
 		/* Cache the NS set from a positive response. */
 		cred = getCred(Section.AUTHORITY, isAuth);
 		addRRset(ns, cred);
 		markAdditional(ns, additionalNames);
 	}

 	addl = in.getSectionRRsets(Section.ADDITIONAL);
 	for (int i = 0; i < addl.length; i++) {
 		int type = addl[i].getType();
 		if (type != Type.A && type != Type.AAAA && type != Type.A6)
 			continue;
 		Name name = addl[i].getName();
 		if (!additionalNames.contains(name))
 			continue;
 		cred = getCred(Section.ADDITIONAL, isAuth);
 		addRRset(addl[i], cred);
 	}
 	if (verbose)
 		System.out.println("addMessage: " + response);
 	return (response);
 }

 /**
  * Flushes an RRset from the cache
  * @param name The name of the records to be flushed
  * @param type The type of the records to be flushed
  * @see RRset
  */
 public void
 flushSet(Name name, int type) {
 	removeElement(name, type);
 }

 /**
  * Flushes all RRsets with a given name from the cache
  * @param name The name of the records to be flushed
  * @see RRset
  */
 public void
 flushName(Name name) {
 	removeName(name);
 }

 /**
  * Sets the maximum length of time that a negative response will be stored
  * in this Cache.  A negative value disables this feature (that is, sets
  * no limit).
  */
 public void
 setMaxNCache(int seconds) {
 	maxncache = seconds;
 }

 /**
  * Gets the maximum length of time that a negative response will be stored
  * in this Cache.  A negative value indicates no limit.
  */
 public int
 getMaxNCache() {
 	return maxncache;
 }

 /**
  * Sets the maximum length of time that records will be stored in this
  * Cache.  A negative value disables this feature (that is, sets no limit).
  */
 public void
 setMaxCache(int seconds) {
 	maxcache = seconds;
 }

 /**
  * Gets the maximum length of time that records will be stored
  * in this Cache.  A negative value indicates no limit.
  */
 public int
 getMaxCache() {
 	return maxcache;
 }

 /**
  * Gets the current number of entries in the Cache, where an entry consists
  * of all records with a specific Name.
  */
 public int
 getSize() {
 	return data.size();
 }

 /**
  * Gets the maximum number of entries in the Cache, where an entry consists
  * of all records with a specific Name.  A negative value is treated as an
  * infinite limit.
  */
 public int
 getMaxEntries() {
 	return data.getMaxSize();
 }

 /**
  * Sets the maximum number of entries in the Cache, where an entry consists
  * of all records with a specific Name.  A negative value is treated as an
  * infinite limit.
  *
  * Note that setting this to a value lower than the current number
  * of entries will not cause the Cache to shrink immediately.
  *
  * The default maximum number of entries is 50000.
  *
  * @param entries The maximum number of entries in the Cache.
  */
 public void
 setMaxEntries(int entries) {
 	data.setMaxSize(entries);
 }

 /**
  * Returns the DNS class of this cache.
  */
 public int
 getDClass() {
 	return dclass;
 }

 /**
  * Returns the contents of the Cache as a string.
  */
 public String
 toString() {
 	StringBuffer sb = new StringBuffer();
 	synchronized (this) {
 		Iterator it = data.values().iterator();
 		while (it.hasNext()) {
 			Element [] elements = allElements(it.next());
 			for (int i = 0; i < elements.length; i++) {
 				sb.append(elements[i]);
 				sb.append("\n");
 			}
 		}
 	}
 	return sb.toString();
 }

 }
	// Copyright (c) 1999-2004 Brian Wellington (bwelling@xbill.org)

	package org.xbill.DNS;

	import java.io.*;
	import java.util.*;

	/**
	* A cache of DNS records. The cache obeys TTLs, so items are purged after
	* their validity period is complete. Negative answers are cached, to
	* avoid repeated failed DNS queries. The credibility of each RRset is
	* maintained, so that more credible records replace less credible records,
	* and lookups can specify the minimum credibility of data they are requesting.
	* @see RRset
	* @see Credibility
	*
	* @author Brian Wellington
	*/

	public class Cache {

	private interface Element {
	public boolean expired();
	public int compareCredibility(int cred);
	public int getType();
	}

	private static int
	limitExpire(long ttl, long maxttl) {
	if (maxttl >= 0 && maxttl < ttl)
	ttl = maxttl;
	long expire = (System.currentTimeMillis() / 1000) + ttl;
	if (expire < 0 \|\| expire > Integer.MAX_VALUE)
	return Integer.MAX_VALUE;
	return (int)expire;
	}

	private static class CacheRRset extends RRset implements Element {
	private static final long serialVersionUID = 5971755205903597024L;

	int credibility;
	int expire;

	public
	CacheRRset(Record rec, int cred, long maxttl) {
	super();
	this.credibility = cred;
	this.expire = limitExpire(rec.getTTL(), maxttl);
	addRR(rec);
	}

	public
	CacheRRset(RRset rrset, int cred, long maxttl) {
	super(rrset);
	this.credibility = cred;
	this.expire = limitExpire(rrset.getTTL(), maxttl);
	}

	public final boolean
	expired() {
	int now = (int)(System.currentTimeMillis() / 1000);
	return (now >= expire);
	}

	public final int
	compareCredibility(int cred) {
	return credibility - cred;
	}

	public String
	toString() {
	StringBuffer sb = new StringBuffer();
	sb.append(super.toString());
	sb.append(" cl = ");
	sb.append(credibility);
	return sb.toString();
	}
	}

	private static class NegativeElement implements Element {
	int type;
	Name name;
	int credibility;
	int expire;

	public
	NegativeElement(Name name, int type, SOARecord soa, int cred,
	long maxttl)
	{
	this.name = name;
	this.type = type;
	long cttl = 0;
	if (soa != null)
	cttl = soa.getMinimum();
	this.credibility = cred;
	this.expire = limitExpire(cttl, maxttl);
	}

	public int
	getType() {
	return type;
	}

	public final boolean
	expired() {
	int now = (int)(System.currentTimeMillis() / 1000);
	return (now >= expire);
	}

	public final int
	compareCredibility(int cred) {
	return credibility - cred;
	}

	public String
	toString() {
	StringBuffer sb = new StringBuffer();
	if (type == 0)
	sb.append("NXDOMAIN " + name);
	else
	sb.append("NXRRSET " + name + " " + Type.string(type));
	sb.append(" cl = ");
	sb.append(credibility);
	return sb.toString();
	}
	}

	private static class CacheMap extends LinkedHashMap {
	private int maxsize = -1;

	CacheMap(int maxsize) {
	super(16, (float) 0.75, true);
	this.maxsize = maxsize;
	}

	int
	getMaxSize() {
	return maxsize;
	}

	void
	setMaxSize(int maxsize) {
	/*
	* Note that this doesn't shrink the size of the map if
	* the maximum size is lowered, but it should shrink as
	* entries expire.
	*/
	this.maxsize = maxsize;
	}

	protected boolean removeEldestEntry(Map.Entry eldest) {
	return maxsize >= 0 && size() > maxsize;
	}
	}

	private CacheMap data;
	private int maxncache = -1;
	private int maxcache = -1;
	private int dclass;

	private static final int defaultMaxEntries = 50000;

	/**
	* Creates an empty Cache
	*
	* @param dclass The DNS class of this cache
	* @see DClass
	*/
	public
	Cache(int dclass) {
	this.dclass = dclass;
	data = new CacheMap(defaultMaxEntries);
	}

	/**
	* Creates an empty Cache for class IN.
	* @see DClass
	*/
	public
	Cache() {
	this(DClass.IN);
	}

	/**
	* Creates a Cache which initially contains all records in the specified file.
	*/
	public
	Cache(String file) throws IOException {
	data = new CacheMap(defaultMaxEntries);
	Master m = new Master(file);
	Record record;
	while ((record = m.nextRecord()) != null)
	addRecord(record, Credibility.HINT, m);
	}

	private synchronized Object
	exactName(Name name) {
	return data.get(name);
	}

	private synchronized void
	removeName(Name name) {
	data.remove(name);
	}

	private synchronized Element []
	allElements(Object types) {
	if (types instanceof List) {
	List typelist = (List) types;
	int size = typelist.size();
	return (Element []) typelist.toArray(new Element[size]);
	} else {
	Element set = (Element) types;
	return new Element[] {set};
	}
	}

	private synchronized Element
	oneElement(Name name, Object types, int type, int minCred) {
	Element found = null;

	if (type == Type.ANY)
	throw new IllegalArgumentException("oneElement(ANY)");
	if (types instanceof List) {
	List list = (List) types;
	for (int i = 0; i < list.size(); i++) {
	Element set = (Element) list.get(i);
	if (set.getType() == type) {
	found = set;
	break;
	}
	}
	} else {
	Element set = (Element) types;
	if (set.getType() == type)
	found = set;
	}
	if (found == null)
	return null;
	if (found.expired()) {
	removeElement(name, type);
	return null;
	}
	if (found.compareCredibility(minCred) < 0)
	return null;
	return found;
	}

	private synchronized Element
	findElement(Name name, int type, int minCred) {
	Object types = exactName(name);
	if (types == null)
	return null;
	return oneElement(name, types, type, minCred);
	}

	private synchronized void
	addElement(Name name, Element element) {
	Object types = data.get(name);
	if (types == null) {
	data.put(name, element);
	return;
	}
	int type = element.getType();
	if (types instanceof List) {
	List list = (List) types;
	for (int i = 0; i < list.size(); i++) {
	Element elt = (Element) list.get(i);
	if (elt.getType() == type) {
	list.set(i, element);
	return;
	}
	}
	list.add(element);
	} else {
	Element elt = (Element) types;
	if (elt.getType() == type)
	data.put(name, element);
	else {
	LinkedList list = new LinkedList();
	list.add(elt);
	list.add(element);
	data.put(name, list);
	}
	}
	}

	private synchronized void
	removeElement(Name name, int type) {
	Object types = data.get(name);
	if (types == null) {
	return;
	}
	if (types instanceof List) {
	List list = (List) types;
	for (int i = 0; i < list.size(); i++) {
	Element elt = (Element) list.get(i);
	if (elt.getType() == type) {
	list.remove(i);
	if (list.size() == 0)
	data.remove(name);
	return;
	}
	}
	} else {
	Element elt = (Element) types;
	if (elt.getType() != type)
	return;
	data.remove(name);
	}
	}

	/** Empties the Cache. */
	public synchronized void
	clearCache() {
	data.clear();
	}

	/**
	* Adds a record to the Cache.
	* @param r The record to be added
	* @param cred The credibility of the record
	* @param o The source of the record (this could be a Message, for example)
	* @see Record
	*/
	public synchronized void
	addRecord(Record r, int cred, Object o) {
	Name name = r.getName();
	int type = r.getRRsetType();
	if (!Type.isRR(type))
	return;
	Element element = findElement(name, type, cred);
	if (element == null) {
	CacheRRset crrset = new CacheRRset(r, cred, maxcache);
	addRRset(crrset, cred);
	} else if (element.compareCredibility(cred) == 0) {
	if (element instanceof CacheRRset) {
	CacheRRset crrset = (CacheRRset) element;
	crrset.addRR(r);
	}
	}
	}

	/**
	* Adds an RRset to the Cache.
	* @param rrset The RRset to be added
	* @param cred The credibility of these records
	* @see RRset
	*/
	public synchronized void
	addRRset(RRset rrset, int cred) {
	long ttl = rrset.getTTL();
	Name name = rrset.getName();
	int type = rrset.getType();
	Element element = findElement(name, type, 0);
	if (ttl == 0) {
	if (element != null && element.compareCredibility(cred) <= 0)
	removeElement(name, type);
	} else {
	if (element != null && element.compareCredibility(cred) <= 0)
	element = null;
	if (element == null) {
	CacheRRset crrset;
	if (rrset instanceof CacheRRset)
	crrset = (CacheRRset) rrset;
	else
	crrset = new CacheRRset(rrset, cred, maxcache);
	addElement(name, crrset);
	}
	}
	}

	/**
	* Adds a negative entry to the Cache.
	* @param name The name of the negative entry
	* @param type The type of the negative entry
	* @param soa The SOA record to add to the negative cache entry, or null.
	* The negative cache ttl is derived from the SOA.
	* @param cred The credibility of the negative entry
	*/
	public synchronized void
	addNegative(Name name, int type, SOARecord soa, int cred) {
	long ttl = 0;
	if (soa != null)
	ttl = soa.getTTL();
	Element element = findElement(name, type, 0);
	if (ttl == 0) {
	if (element != null && element.compareCredibility(cred) <= 0)
	removeElement(name, type);
	} else {
	if (element != null && element.compareCredibility(cred) <= 0)
	element = null;
	if (element == null)
	addElement(name, new NegativeElement(name, type,
	soa, cred,
	maxncache));
	}
	}

	/**
	* Finds all matching sets or something that causes the lookup to stop.
	*/
	protected synchronized SetResponse
	lookup(Name name, int type, int minCred) {
	int labels;
	int tlabels;
	Element element;
	Name tname;
	Object types;
	SetResponse sr;

	labels = name.labels();

	for (tlabels = labels; tlabels >= 1; tlabels--) {
	boolean isRoot = (tlabels == 1);
	boolean isExact = (tlabels == labels);

	if (isRoot)
	tname = Name.root;
	else if (isExact)
	tname = name;
	else
	tname = new Name(name, labels - tlabels);

	types = data.get(tname);
	if (types == null)
	continue;

	/*
	* If this is the name, look for the actual type or a CNAME
	* (unless it's an ANY query, where we return everything).
	* Otherwise, look for a DNAME.
	*/
	if (isExact && type == Type.ANY) {
	sr = new SetResponse(SetResponse.SUCCESSFUL);
	Element [] elements = allElements(types);
	int added = 0;
	for (int i = 0; i < elements.length; i++) {
	element = elements[i];
	if (element.expired()) {
	removeElement(tname, element.getType());
	continue;
	}
	if (!(element instanceof CacheRRset))
	continue;
	if (element.compareCredibility(minCred) < 0)
	continue;
	sr.addRRset((CacheRRset)element);
	added++;
	}
	/* There were positive entries */
	if (added > 0)
	return sr;
	} else if (isExact) {
	element = oneElement(tname, types, type, minCred);
	if (element != null &&
	element instanceof CacheRRset)
	{
	sr = new SetResponse(SetResponse.SUCCESSFUL);
	sr.addRRset((CacheRRset) element);
	return sr;
	} else if (element != null) {
	sr = new SetResponse(SetResponse.NXRRSET);
	return sr;
	}

	element = oneElement(tname, types, Type.CNAME, minCred);
	if (element != null &&
	element instanceof CacheRRset)
	{
	return new SetResponse(SetResponse.CNAME,
	(CacheRRset) element);
	}
	} else {
	element = oneElement(tname, types, Type.DNAME, minCred);
	if (element != null &&
	element instanceof CacheRRset)
	{
	return new SetResponse(SetResponse.DNAME,
	(CacheRRset) element);
	}
	}

	/* Look for an NS */
	element = oneElement(tname, types, Type.NS, minCred);
	if (element != null && element instanceof CacheRRset)
	return new SetResponse(SetResponse.DELEGATION,
	(CacheRRset) element);

	/* Check for the special NXDOMAIN element. */
	if (isExact) {
	element = oneElement(tname, types, 0, minCred);
	if (element != null)
	return SetResponse.ofType(SetResponse.NXDOMAIN);
	}

	}
	return SetResponse.ofType(SetResponse.UNKNOWN);
	}

	/**
	* Looks up Records in the Cache. This follows CNAMEs and handles negatively
	* cached data.
	* @param name The name to look up
	* @param type The type to look up
	* @param minCred The minimum acceptable credibility
	* @return A SetResponse object
	* @see SetResponse
	* @see Credibility
	*/
	public SetResponse
	lookupRecords(Name name, int type, int minCred) {
	return lookup(name, type, minCred);
	}

	private RRset []
	findRecords(Name name, int type, int minCred) {
	SetResponse cr = lookupRecords(name, type, minCred);
	if (cr.isSuccessful())
	return cr.answers();
	else
	return null;
	}

	/**
	* Looks up credible Records in the Cache (a wrapper around lookupRecords).
	* Unlike lookupRecords, this given no indication of why failure occurred.
	* @param name The name to look up
	* @param type The type to look up
	* @return An array of RRsets, or null
	* @see Credibility
	*/
	public RRset []
	findRecords(Name name, int type) {
	return findRecords(name, type, Credibility.NORMAL);
	}

	/**
	* Looks up Records in the Cache (a wrapper around lookupRecords). Unlike
	* lookupRecords, this given no indication of why failure occurred.
	* @param name The name to look up
	* @param type The type to look up
	* @return An array of RRsets, or null
	* @see Credibility
	*/
	public RRset []
	findAnyRecords(Name name, int type) {
	return findRecords(name, type, Credibility.GLUE);
	}

	private final int
	getCred(int section, boolean isAuth) {
	if (section == Section.ANSWER) {
	if (isAuth)
	return Credibility.AUTH_ANSWER;
	else
	return Credibility.NONAUTH_ANSWER;
	} else if (section == Section.AUTHORITY) {
	if (isAuth)
	return Credibility.AUTH_AUTHORITY;
	else
	return Credibility.NONAUTH_AUTHORITY;
	} else if (section == Section.ADDITIONAL) {
	return Credibility.ADDITIONAL;
	} else
	throw new IllegalArgumentException("getCred: invalid section");
	}

	private static void
	markAdditional(RRset rrset, Set names) {
	Record first = rrset.first();
	if (first.getAdditionalName() == null)
	return;

	Iterator it = rrset.rrs();
	while (it.hasNext()) {
	Record r = (Record) it.next();
	Name name = r.getAdditionalName();
	if (name != null)
	names.add(name);
	}
	}

	/**
	* Adds all data from a Message into the Cache. Each record is added with
	* the appropriate credibility, and negative answers are cached as such.
	* @param in The Message to be added
	* @return A SetResponse that reflects what would be returned from a cache
	* lookup, or null if nothing useful could be cached from the message.
	* @see Message
	*/
	public SetResponse
	addMessage(Message in) {
	boolean isAuth = in.getHeader().getFlag(Flags.AA);
	Record question = in.getQuestion();
	Name qname;
	Name curname;
	int qtype;
	int qclass;
	int cred;
	int rcode = in.getHeader().getRcode();
	boolean completed = false;
	RRset [] answers, auth, addl;
	SetResponse response = null;
	boolean verbose = Options.check("verbosecache");
	HashSet additionalNames;

	if ((rcode != Rcode.NOERROR && rcode != Rcode.NXDOMAIN) \|\|
	question == null)
	return null;

	qname = question.getName();
	qtype = question.getType();
	qclass = question.getDClass();

	curname = qname;

	additionalNames = new HashSet();

	answers = in.getSectionRRsets(Section.ANSWER);
	for (int i = 0; i < answers.length; i++) {
	if (answers[i].getDClass() != qclass)
	continue;
	int type = answers[i].getType();
	Name name = answers[i].getName();
	cred = getCred(Section.ANSWER, isAuth);
	if ((type == qtype \|\| qtype == Type.ANY) &&
	name.equals(curname))
	{
	addRRset(answers[i], cred);
	completed = true;
	if (curname == qname) {
	if (response == null)
	response = new SetResponse(
	SetResponse.SUCCESSFUL);
	response.addRRset(answers[i]);
	}
	markAdditional(answers[i], additionalNames);
	} else if (type == Type.CNAME && name.equals(curname)) {
	CNAMERecord cname;
	addRRset(answers[i], cred);
	if (curname == qname)
	response = new SetResponse(SetResponse.CNAME,
	answers[i]);
	cname = (CNAMERecord) answers[i].first();
	curname = cname.getTarget();
	} else if (type == Type.DNAME && curname.subdomain(name)) {
	DNAMERecord dname;
	addRRset(answers[i], cred);
	if (curname == qname)
	response = new SetResponse(SetResponse.DNAME,
	answers[i]);
	dname = (DNAMERecord) answers[i].first();
	try {
	curname = curname.fromDNAME(dname);
	}
	catch (NameTooLongException e) {
	break;
	}
	}
	}

	auth = in.getSectionRRsets(Section.AUTHORITY);
	RRset soa = null, ns = null;
	for (int i = 0; i < auth.length; i++) {
	if (auth[i].getType() == Type.SOA &&
	curname.subdomain(auth[i].getName()))
	soa = auth[i];
	else if (auth[i].getType() == Type.NS &&
	curname.subdomain(auth[i].getName()))
	ns = auth[i];
	}
	if (!completed) {
	/* This is a negative response or a referral. */
	int cachetype = (rcode == Rcode.NXDOMAIN) ? 0 : qtype;
	if (rcode == Rcode.NXDOMAIN \|\| soa != null \|\| ns == null) {
	/* Negative response */
	cred = getCred(Section.AUTHORITY, isAuth);
	SOARecord soarec = null;
	if (soa != null)
	soarec = (SOARecord) soa.first();
	addNegative(curname, cachetype, soarec, cred);
	if (response == null) {
	int responseType;
	if (rcode == Rcode.NXDOMAIN)
	responseType = SetResponse.NXDOMAIN;
	else
	responseType = SetResponse.NXRRSET;
	response = SetResponse.ofType(responseType);
	}
	/* DNSSEC records are not cached. */
	} else {
	/* Referral response */
	cred = getCred(Section.AUTHORITY, isAuth);
	addRRset(ns, cred);
	markAdditional(ns, additionalNames);
	if (response == null)
	response = new SetResponse(
	SetResponse.DELEGATION,
	ns);
	}
	} else if (rcode == Rcode.NOERROR && ns != null) {
	/* Cache the NS set from a positive response. */
	cred = getCred(Section.AUTHORITY, isAuth);
	addRRset(ns, cred);
	markAdditional(ns, additionalNames);
	}

	addl = in.getSectionRRsets(Section.ADDITIONAL);
	for (int i = 0; i < addl.length; i++) {
	int type = addl[i].getType();
	if (type != Type.A && type != Type.AAAA && type != Type.A6)
	continue;
	Name name = addl[i].getName();
	if (!additionalNames.contains(name))
	continue;
	cred = getCred(Section.ADDITIONAL, isAuth);
	addRRset(addl[i], cred);
	}
	if (verbose)
	System.out.println("addMessage: " + response);
	return (response);
	}

	/**
	* Flushes an RRset from the cache
	* @param name The name of the records to be flushed
	* @param type The type of the records to be flushed
	* @see RRset
	*/
	public void
	flushSet(Name name, int type) {
	removeElement(name, type);
	}

	/**
	* Flushes all RRsets with a given name from the cache
	* @param name The name of the records to be flushed
	* @see RRset
	*/
	public void
	flushName(Name name) {
	removeName(name);
	}

	/**
	* Sets the maximum length of time that a negative response will be stored
	* in this Cache. A negative value disables this feature (that is, sets
	* no limit).
	*/
	public void
	setMaxNCache(int seconds) {
	maxncache = seconds;
	}

	/**
	* Gets the maximum length of time that a negative response will be stored
	* in this Cache. A negative value indicates no limit.
	*/
	public int
	getMaxNCache() {
	return maxncache;
	}

	/**
	* Sets the maximum length of time that records will be stored in this
	* Cache. A negative value disables this feature (that is, sets no limit).
	*/
	public void
	setMaxCache(int seconds) {
	maxcache = seconds;
	}

	/**
	* Gets the maximum length of time that records will be stored
	* in this Cache. A negative value indicates no limit.
	*/
	public int
	getMaxCache() {
	return maxcache;
	}

	/**
	* Gets the current number of entries in the Cache, where an entry consists
	* of all records with a specific Name.
	*/
	public int
	getSize() {
	return data.size();
	}

	/**
	* Gets the maximum number of entries in the Cache, where an entry consists
	* of all records with a specific Name. A negative value is treated as an
	* infinite limit.
	*/
	public int
	getMaxEntries() {
	return data.getMaxSize();
	}

	/**
	* Sets the maximum number of entries in the Cache, where an entry consists
	* of all records with a specific Name. A negative value is treated as an
	* infinite limit.
	*
	* Note that setting this to a value lower than the current number
	* of entries will not cause the Cache to shrink immediately.
	*
	* The default maximum number of entries is 50000.
	*
	* @param entries The maximum number of entries in the Cache.
	*/
	public void
	setMaxEntries(int entries) {
	data.setMaxSize(entries);
	}

	/**
	* Returns the DNS class of this cache.
	*/
	public int
	getDClass() {
	return dclass;
	}

	/**
	* Returns the contents of the Cache as a string.
	*/
	public String
	toString() {
	StringBuffer sb = new StringBuffer();
	synchronized (this) {
	Iterator it = data.values().iterator();
	while (it.hasNext()) {
	Element [] elements = allElements(it.next());
	for (int i = 0; i < elements.length; i++) {
	sb.append(elements[i]);
	sb.append("\n");
	}
	}
	}
	return sb.toString();
	}

	}