/// ----------------------------------------*- mode: C++; -*--
/// @file address.cpp
/// GIST address objects
/// ----------------------------------------------------------
/// $Id: address.cpp 3046 2008-06-18 14:40:43Z hiwi-laier $
/// $HeadURL: https://svn.ipv6.tm.uka.de/nsis/protlib/trunk/src/address.cpp $
// ===========================================================
//                      
// Copyright (C) 2005-2007, all rights reserved by
// - Institute of Telematics, Universitaet Karlsruhe (TH)
//
// More information and contact:
// https://projekte.tm.uka.de/trac/NSIS
//                      
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; version 2 of the License
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License along
// with this program; if not, write to the Free Software Foundation, Inc.,
// 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
//
// ===========================================================
/** @ingroup ieaddress
 * GIST address objects
 */

#include <sys/types.h>
#include <sys/socket.h>

#include "address.h"
#include "threadsafe_db.h"
#include "logfile.h"

#include <net/if.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <ifaddrs.h>
#include <iomanip>
#include <netdb.h>

namespace protlib {

/** @addtogroup ieaddress Address Objects
 * @{
 */
  using namespace log;
/***** class address *****/

/** Set subtype. */
address::address(subtype_t st) 
	: subtype(st) 
{ 
  //Log(DEBUG_LOG,LOG_NORMAL,"address","address constructor called for " << (void *) this); 
}

/** Log and throw a nomem_error */
void address::throw_nomem_error() const {
	try {
	  ERRCLog("address", "Not enough memory for address");
	} catch(...) {}
	throw IEError(IEError::ERROR_NO_MEM);
} // end throw_nomem_error


/***** class hostaddress *****/

/***** inherited from IE *****/

hostaddress* hostaddress::new_instance() const {
	hostaddress* ha = NULL;
	catch_bad_alloc(ha = new hostaddress());
	return ha;
} // end new_instance

hostaddress* hostaddress::copy() const {
	hostaddress* ha = NULL;
	catch_bad_alloc(ha =  new hostaddress(*this));
	return ha;
} // end copy 

bool hostaddress::operator==(const address& ie) const {
	const hostaddress* haddr = dynamic_cast<const hostaddress*>(&ie);
	if (haddr) {
#ifdef DEBUG_HARD
	  Log(DEBUG_LOG,LOG_NORMAL,"hostaddress","::operator==()" << haddr->get_ip_str()<<"=="<<this->get_ip_str());
	  if (!ipv4flag)
	    Log(DEBUG_LOG,LOG_NORMAL,"hostaddress","::operator==(), v6=" << IN6_ARE_ADDR_EQUAL(ipv6addr.s6_addr, haddr->ipv6addr.s6_addr));
#endif
	  return ipv4flag ? (ipv4addr.s_addr==haddr->ipv4addr.s_addr) :
	                    IN6_ARE_ADDR_EQUAL(ipv6addr.s6_addr, haddr->ipv6addr.s6_addr);
	} else return false;
} // end operator==

/***** new in hostaddress *****/


/** Initialize hostaddress from string if possible. */
hostaddress::hostaddress(const char *str, bool *res) 
	: address(IPv6HostAddress),
	  ipv4flag(false), 
	  outstring(NULL)
{
	register bool tmpres = false;
	clear_ip();
	tmpres = set_ip(str);
	if (res) *res = tmpres;
} // end string constructor hostaddress


/** Set IPv4 from string or leave object unchanged.
 * This changes object type to IPv4.
 * @return true on success.
 */
bool 
hostaddress::set_ipv4(const char *str) {
	struct in_addr in;
	if (str && (inet_pton(AF_INET,str,&in)>0)) {
		set_ip(in);
		return true;
	} else return false;
} // end set_ipv4

/** Set IPv4 address from struct in_addr. 
 * This changes object type to IPv4. 
 */
void hostaddress::set_ip(const struct in_addr &in) {
	clear_ip();
	ipv4addr = in;	
	// set subtype to IPv4
	set_subtype(true);
	return;
} // end set_ip(in_addr)

/** Set IPv6 from string or leave object unchanged.
 * This changes object type to IPv6.
 * @return true on success.
 */
bool hostaddress::set_ipv6(const char *str) {
	struct in6_addr in;
	if (str && (inet_pton(AF_INET6,str,&in)>0)) {
		set_ip(in);
		return true;
	} else return false;
} // end set_ipv6	

/** Set IPv6 address from struct in6_addr. 
 * This changes object type to IPv6. 
 */
void 
hostaddress::set_ip(const struct in6_addr &in) {
	clear_ip();
	ipv6addr = in;	
	// set subtype to IPv6
	set_subtype(false);
	return;
} // end set_ip(in6_addr)



void hostaddress::set_ip(const hostaddress& h) {
	clear_ip();
	if (h.ipv4flag) {
		ipv4addr = h.ipv4addr;
	} else {
		ipv6addr = h.ipv6addr;
	} // end if ipv4flag
	set_subtype(h.ipv4flag);
} // end set_ip(hostaddress)

/** Check if IP address is unspecified (set to 0). */
bool hostaddress::is_ip_unspec() const {
	if (ipv4flag) return (ipv4addr.s_addr==0);
	else return IN6_IS_ADDR_UNSPECIFIED(ipv6addr.s6_addr);
	// never reached
	return true;
} // end is_unspec

/** Get IP address as a string. The output string is kept inside the
 * hostaddress object and should be copied if used for a longer time.
 */
const char* hostaddress::get_ip_str() const 
{
  // If outstring exists then it is valid.
  if (outstring) 
    return outstring;
  else
    outstring= (ipv4flag ? new(nothrow) char[INET_ADDRSTRLEN] : 
		           new(nothrow) char[INET6_ADDRSTRLEN]);

  if (hostaddress::get_ip_str(outstring)) 
    return outstring;
  else 
  {
    // error
    if (outstring) 
      delete[] outstring;

    return (outstring = NULL);
  } // end if get_ip_str()
} // end get_ip_str

/** Get IP address as a string.
 * @param str string buffer
 */
const char* hostaddress::get_ip_str(char *str) const 
{
  if (!str) return NULL;
  memset(str,0, ipv4flag ? INET_ADDRSTRLEN : INET6_ADDRSTRLEN);
  return ipv4flag ? inet_ntop(AF_INET,(void*)&ipv4addr,str,INET_ADDRSTRLEN) 
                  : inet_ntop(AF_INET6,(void*)&ipv6addr,str,INET6_ADDRSTRLEN);
} // end get_ip_str(char*)


/** Get IP address as an in_addr if possible.
 * @return true on success.
 */
bool hostaddress::get_ip(struct in_addr& in) const {
	if (ipv4flag) {
		in = ipv4addr;
		return true;
	} else if (IN6_IS_ADDR_V4MAPPED(ipv6addr.s6_addr)) {
		memcpy(&(in.s_addr),ipv6addr.s6_addr+12,4);
		return true;
	} else return false;
} // get_ip

/** Get IP address as an in6_addr.
 * If this is an IPv4 address, it is mapped to IPv6.
 * @return true since this is always possible.
 */
bool hostaddress::get_ip(struct in6_addr& in) const {
	if (ipv4flag) {
		// map to IPv6
		memset(in.s6_addr,0,10);
		memset(in.s6_addr+10,255,2);
		memcpy(in.s6_addr+12,&(ipv4addr.s_addr),4);
	} else in = ipv6addr;
	return true;
} // get_ip

/// returns false if address is not allowed to be used
/// as source address: loopback, multicast, broadcast, unspecified
bool 
hostaddress::is_bogus_source() const
{
  if (ipv4flag)
  { // IPv4
    if ( IN_MULTICAST(ipv4addr.s_addr) || 
	 ipv4addr.s_addr == INADDR_LOOPBACK  ||
         ipv4addr.s_addr == INADDR_ANY ||
         ipv4addr.s_addr == INADDR_BROADCAST
       )
    {
      return true;
    }
  }
  else
  { // IPv6
    if ( ipv6addr.s6_addr == in6addr_any.s6_addr ||
	 ipv6addr.s6_addr == in6addr_loopback.s6_addr )
      return true;
  }

  return false;
}


/** Convert the IP address to IPv6 by mapping it from IPv4 to IPv6 if
 * necessary
 */
void hostaddress::convert_to_ipv6() {
	if (ipv4flag) {
		if (is_ip_unspec()) {
			// clear IP and set to IPv6
			clear_ip();
			set_subtype(false);
		} else {
			// map to IPv6
			struct in6_addr in;
			get_ip(in);
			// set IP
			set_ip(in);
		} // end if is_ip_unspec()
	} // end if ipv4flag
} // end convert_to_ipv6

/** Two addresses are equivalent if they are equal after converting both to
 * IPv6.
 */
bool hostaddress::equiv(const hostaddress& h) const {
	bool thisipv4 = is_ipv4();
	bool result = false;
	hostaddress* ipv4haddr = NULL;
	const hostaddress* ipv6haddr = NULL;
	// if both IPv4 or both IPv6 then just test for equality
	if (thisipv4==h.is_ipv4()) return operator==(h);
	// OK, one is IPv6 and the other is IPv4 (to be converted!).
	// Allocating memory dynamically because I do not know the concrete
	// type of *this or h.
	try {
		if (thisipv4) {
			ipv6haddr = &h;
			if (h.is_mapped_ip()) ipv4haddr = this->copy();
		} else {
			ipv6haddr = this;
			if (is_mapped_ip()) ipv4haddr = h.copy();
		} // end if thisipv4
	} catch(IEError&) { ipv4haddr = NULL; }
	if (ipv4haddr) {
		ipv4haddr->convert_to_ipv6();
		result = ((*ipv4haddr)==(*ipv6haddr));
		delete ipv4haddr;
		return result;
	} else return false;
} // end equiv


/** Set subtype and IPv4 flag. This does NOT clear the outstring buffer.
 * Use clear_ip(). 
 */
void hostaddress::set_subtype(bool ipv4) {
	ipv4flag = ipv4; 
	subtype = ipv4flag ? IPv4HostAddress : IPv6HostAddress;
} // end set_subtype

/** Clear the IP address buffer and the outstring if it exists. */
void hostaddress::clear_ip() {
	// only need to clear ipv6 because of union
	ipv6addr = in6addr_any;
	if (outstring) {
		delete[] outstring;
		outstring = NULL;
	} // end if outstring
} // end clear_ip


/** Match this IP address against another IP address.
 * Two IP addresses match if they are equal.
 * @return -1 on no match or error, e.g. when IPv4 and IPv6 are matched
 * @return the length of the matched prefix.
 */
int hostaddress::match_against(const hostaddress& ha) const {
	if (ipv4flag==ha.ipv4flag) {
		if (operator==(ha)) {
			if (ipv4flag) return 32;
			else return 128;
		} else return -1;
	} else return -1;
} // end match_against(

/** Match this IP address against the given network prefix.
 * @return -1 on no match or error, e.g. when IPv4 and IPv6 are matched
 * @return the length of the matched prefix.
 */
int hostaddress::match_against(const netaddress& na) const {
	uint32 word1 = 0;
	uint32 word2 = 0;
	const prefix_length_t preflen = na.get_pref_len();
	prefix_length_t lenwords = preflen/32;
	prefix_length_t lenbits = preflen%32;
	// now 0<=lenwords<=4, 0<=lenbits<=31
	prefix_length_t i;
	const hostaddress& ha = dynamic_cast<const hostaddress&>(na);
	if (ipv4flag==na.ipv4flag) {
		if (ipv4flag) {
			if (preflen >= 32)
				lenbits = 32;
			// match IPv4
			word1 = ntohl(ipv4addr.s_addr);
			word2 = ntohl(ha.ipv4addr.s_addr);
			// shift right
			word1 >>= (32-lenbits);
			word2 >>= (32-lenbits);
			if (word1==word2) return preflen;
			else return -1;
		} else {
			if (preflen > 128)
				return -1;
			// match IPv6
			// match words
			for (i=0;i<lenwords;i++) {
			  word1 = ntohl(ipv6addr.s6_addr32[i]);    // RB: as long as both words are in same order we dont need ntohl?!
			  word2 = ntohl(ha.ipv6addr.s6_addr32[i]);
				if (word1!=word2) return -1;
			} // end for i
			// now i points to the next word to be matched
			// match bits
			if (lenbits) {
				word1 = ntohl(ipv6addr.s6_addr32[i]);
				word2 = ntohl(ha.ipv6addr.s6_addr32[i]);
				// shift right
				word1 >>= (32-lenbits);
				word2 >>= (32-lenbits);
				if (word1==word2) return preflen;
				else return -1;
			} else {
				// no extra bits to match and everything OK
				return preflen;
			} // end if lenbits
		} // end if ipv4flag
	} else return -1;
} // end match_against

/***** class appladdress *****/

/***** inherited from IE *****/

appladdress* appladdress::new_instance() const {
	appladdress* aa = NULL;
	catch_bad_alloc(aa = new appladdress());
	return aa;
} // end new_instance

appladdress* appladdress::copy() const {
	appladdress* aa = NULL;
	catch_bad_alloc(aa = new appladdress(*this));
	return aa;
} // end copy 

bool appladdress::operator==(const address& ie) const {
	const appladdress* app = dynamic_cast<const appladdress*>(&ie);
	if (app) {
		// if the IEs are equal when casted to type hostaddress, then
		// only protocols and ports have to be checked.
		// Otherwise they are not equal.
		if (hostaddress::operator==(ie)) {
		    //if (proto!=app->proto) cout << "protocols not matching" << endl;
		    //if (port !=app->port) cout << "ports not matching" << endl;

		    return ((proto==app->proto) && (port==app->port));
		} else return false;
	} else return false;
} // end operator==


/***** class netaddress *****/

/***** inherited from IE *****/

netaddress* netaddress::new_instance() const {
	netaddress* na = NULL;
	catch_bad_alloc(na = new netaddress());
	return na;
} // end new_instance

netaddress* netaddress::copy() const {
	netaddress* na = NULL;
	catch_bad_alloc(na = new netaddress(*this));
	return na;
} // end copy 

bool netaddress::operator==(const address& ie) const {
	const netaddress* na = dynamic_cast<const netaddress*>(&ie);
	if (na) {
		// if the IEs are equal when casted to type hostaddress, then
		// only prefix lengths have to be checked.
		// Otherwise they are not equal.
		if (hostaddress::operator==(ie)) {
		    if (prefix_length!=na->prefix_length) cout << "Prefix length not matching" << endl;
		    return (prefix_length==na->prefix_length);
		} else return false;
	} else return false;
} // end operator==


/***** inherited from hostaddress *****/

/** Convert the IP address to IPv6 by mapping it from IPv4 to IPv6 if
 * necessary. The prefix length is converted, too.
 */
void netaddress::convert_to_ipv6() {
	if (ipv4flag) {
		// map IP
		hostaddress::convert_to_ipv6();
		// adjust prefix length
		set_pref_len(prefix_length+96);
	} // end if ipv4flag
} // end convert_to_ipv6

/** Set subtype and IPv4 flag. This does NOT clear the outstring buffer.
 * Use clear_ip(). 
 * In addition the prefix length is checked and set to reasonable values.
 */
void netaddress::set_subtype(bool ipv4) {
	ipv4flag = ipv4; 
	if (ipv4) {
		subtype = IPv4NetAddress; 
		if (prefix_length>32) prefix_length = 32;
	} else {
		subtype = IPv6NetAddress;
		if (prefix_length>128) prefix_length = 128;
	} // end if ipv4flag
} // end set_subtype

/***** new members in netaddress *****/

/** Constructor sets address type and clears prefix length. */
netaddress::netaddress() : 
  hostaddress(),
  prefix_length(0)
 {
	set_subtype(ipv4flag);
} // end constructor

netaddress::netaddress(const netaddress& na) : hostaddress(na) {
	prefix_length = na.prefix_length;
	set_subtype(ipv4flag);
} // end copy constructor

/** Initialize with the given host address and prefix length. 
 * Prefix length is optional and set to 0 if missing.
 */
netaddress::netaddress(const hostaddress& h, prefix_length_t len) : hostaddress(h) {
  set_subtype(ipv4flag);
  set_pref_len(len); // this will cut the prefix value accordingly
} // end constructor(hostaddress,len)

/** Initialize from string which contains IP and prefix length separated by
 * '/'.
 */
netaddress::netaddress(const char* str, bool *res) : hostaddress() {
	bool tmpres = true; // MUST BE true
	bool tmpres2 = false;
	long int len = 0;
	uint32 iplen;
	char* i = NULL;
	char* errptr = NULL;
	char ipstr[INET6_ADDRSTRLEN] = {0};
	// look for /
	i = strchr((char*)str,'/');
	if (i) {
		iplen = i-str;
		i++;
		// decode prefix length
		len = strtol(i,&errptr,10);
		if ((*i) && errptr && ((*errptr)==0)) {
			// prefix OK
			prefix_length = len;
		} else {
			prefix_length = 0;
			tmpres = false;
		} // end if prefix OK
		if (iplen<=INET6_ADDRSTRLEN) {
			// copy IP string
			strncpy(ipstr,str,iplen);
			ipstr[INET6_ADDRSTRLEN-1] = 0;
			// set str to ipstr
			str = ipstr;
		} // end if iplen valid
	} else {
		// no prefix found, OK
		prefix_length = 0;
	} // end if i
	// set IP, this also sets ipvflag.
	tmpres2 = set_ip(str);
	if (res) *res = (tmpres && tmpres2);
	set_subtype(ipv4flag);
} // end constructor(string)

/** Initialize from string and prefix length.
 * If the string does not contain a valid IP address, it is set to all 0 by
 * the hostaddress constructor.
 */
netaddress::netaddress(const char* str, prefix_length_t len, bool *res) : hostaddress(str,res) {
  set_subtype(ipv4flag);
  set_pref_len(len); // this will cut the prefix value accordingly
} // end constructor(string,port)

/** Assigns the given netaddress address by using hostaddress::operator=(). */
netaddress& netaddress::operator=(const netaddress& na) {
  prefix_length = na.prefix_length;
  hostaddress::operator=(na);
  return *this;
} // end operator=


/** Assigns the given netaddress address by using hostaddress::operator=(). */
netaddress& netaddress::operator=(const hostaddress& na) {
	hostaddress::operator=(na);
	set_pref_len(128);
	return *this;
} // end operator=


/** Set prefix length and return old value.
 * will also cut prefix_length if needed (i.e., if len too large for addr type)
 */
prefix_length_t netaddress::set_pref_len(prefix_length_t len) {
	register prefix_length_t olen = prefix_length;
	prefix_length = ipv4flag ? ( (len>32) ? 32 : len ) :
	                           ( (len>128) ? 128 : len );
	return olen;
} // end set_port



/** Compare two netaddress objects. If neither a<b and b<a then a and b are
 * considered equal.
 */
bool netaddress::operator<(const netaddress& na) const {
	uint32 word1 = 0;
	uint32 word2 = 0;
	prefix_length_t lenwords = prefix_length/32;
	prefix_length_t lenbits = prefix_length%32;
	// now 0<=lenwords<=4, 0<=lenbits<=31
	prefix_length_t i;
	// IPv4 is always < IPv6
	if ((!ipv4flag) && na.ipv4flag) return false;
	else if (ipv4flag && (!na.ipv4flag)) return true;
	// now ipv4flag == na.ipv4flag
	else if (prefix_length<na.prefix_length) return true;
	else if (prefix_length>na.prefix_length) return false;
	// now prefix_length == na.prefix_length
	else if (ipv4flag) {
		// compare IPv4 with same prefix length
		word1 = ntohl(ipv4addr.s_addr);
		word2 = ntohl(na.ipv4addr.s_addr);
		// shift right
		word1 >>= (32-lenbits);
		word2 >>= (32-lenbits);
		if (word1<word2) return true;
		else return false;
	} else {
		// compare IPv6 with same prefix length
		// compare words
		for (i=0;i<lenwords;i++) {
			word1 = ntohl(ipv6addr.s6_addr32[i]);
			word2 = ntohl(na.ipv6addr.s6_addr32[i]);
			if (word1<word2) return true;
			if (word1>word2) return false;
		} // end for i
		// now i points to the next word to be compared and previous words are equal
		// compare bits
		if (lenbits) {
			word1 = ntohl(ipv6addr.s6_addr32[i]);
			word2 = ntohl(na.ipv6addr.s6_addr32[i]);
			// shift right
			word1 >>= (32-lenbits);
			word2 >>= (32-lenbits);
			if (word1<word2) return true;
			else return false;
		} else {
			// no extra bist to compare and everything equal
			return false;
		} // end if lenbits
	} // end if ipv4flag, prefox
} // end match_against

/**
 * Compare function for the radix trie:
 *
 * Compare this and na from *pos up to max(this->prefix, na->prefix)
 *
 * In pos return the position where the compare ended.
 *
 * The return value is 0 if the strings are equal and all of this' string
 * was consumed, otherwise the sign will indicate the bit in this' string
 * at pos (i.e. if the search should continue left or right of na).
 *
 * pos < 0 indicates error
 */
int
netaddress::rdx_cmp(const netaddress *na, int *pos) const
{
	if (na == NULL) {
		*pos = -1;
		return 0;
	}

	if (na->ipv4flag != ipv4flag ||
	    *pos > na->prefix_length ||
	    *pos > prefix_length) {
		*pos = -1;
		return 0;
	}

	if (na->prefix_length == 0) {
		*pos = 1;
		if (ipv4flag)
			return ((ntohl(ipv4addr.s_addr) & 0x80000000) == 0 ?
			    -1 : 1);
		else
			return ((htonl(ipv6addr.s6_addr32[0]) & 0x80000000) == 0 ?
			    -1 : 1);
	}

	if (*pos < 0)
		*pos = 0;

	uint32_t w1, w2, w3;
	int diff, i, p1, p2;

	if (ipv4flag) {
		diff = *pos;
		w1 = ntohl(ipv4addr.s_addr);
		w2 = ntohl(na->ipv4addr.s_addr);
		// in w3 store the difference
		w3 = w1 ^ w2;
		// mask out anything after prefix_length and before *pos
		w3 = (w3 >> (32 - prefix_length)) << (32 - prefix_length + diff);
		if (w3 == 0 && prefix_length <= na->prefix_length) {
			*pos = min(prefix_length, na->prefix_length);
			return 0;
		}
		// pos = 0 means start up front, so we need to fix up to that
		diff++;
		while (diff <= prefix_length && diff <= na->prefix_length) {
			if ((w3 & 0x80000000) != 0) {
				*pos = diff;
				return (((w1 & (1 << (32 - diff))) >>
				    (32 - diff)) == 0 ? -1 : 1);
			}
			w3 = w3 << 1;
			diff++;
		}
		// difference past na->prefix_length
		*pos = diff;
		return (((w1 & (1 << (32 - diff))) >>
		    (32 - diff)) == 0 ? -1 : 1);
	}

	diff = *pos;
	for (i = diff / 32; i < 4; i++) {
		diff = diff % 32;
		w1 = ntohl(ipv6addr.s6_addr32[i]);
		w2 = ntohl(na->ipv6addr.s6_addr32[i]);
		w3 = w1 ^ w2;
		p1 = (prefix_length - (i * 32));
		p1 = p1 > 32 ? 32 : p1;
		p2 = (na->prefix_length - (i * 32));
		p1 = p2 > 32 ? 32 : p2;

		w3 = (w3 >> (32 - p1)) << (32 - p1 + diff);
		if (w3 == 0 && prefix_length <= na->prefix_length) {
			*pos = min(prefix_length, na->prefix_length);
			if (prefix_length <= ((i + 1) * 32))
				return 0;
		}
		// pos = 0 means start up front, so we need to fix up to that
		diff++;
		while (diff <= p1 && diff <= p2) {
			if ((w3 & 0x80000000) != 0) {
				*pos = diff + (i * 32);
				return (((w1 & (1 << (32 - diff))) >>
				    (32 - diff)) == 0 ? -1 : 1);
			}
			w3 = w3 << 1;
			diff++;
		}
		if (diff + (32 * i) <= prefix_length &&
		    diff + (32 * i) <= na->prefix_length) {
			diff--;
			continue;
		}
		// difference past na->prefix_length
		*pos = diff + (i * 32);
		if (diff == 33) {
			diff = 1;
			if (i == 3)
				abort();
			w1 = ntohl(ipv6addr.s6_addr32[i+1]);
		}
		return (((w1 & (1 << (32 - diff))) >>
		    (32 - diff)) == 0 ? -1 : 1);
	}

	// Not reachable, but gcc complains
	return 0;
}

udsaddress* udsaddress::new_instance() const {
	udsaddress* ha = NULL;
	catch_bad_alloc(ha = new udsaddress());
	return ha;
} // end new_instance

udsaddress* udsaddress::copy() const {
        udsaddress* ha = NULL;
	catch_bad_alloc(ha =  new udsaddress(*this));
	return ha;
} // end copy 

bool udsaddress::operator==(const address& ie) const {
	const udsaddress* app = dynamic_cast<const udsaddress*>(&ie);
	if (app) {
	    return (app->socknum == socknum) && (app->uds_socket == uds_socket);
	} else return false;
} // end operator==

AddressList::AddrProperty *AddressList::LocalAddr_P;
AddressList::AddrProperty *AddressList::ConfiguredAddr_P;
AddressList::AddrProperty *AddressList::IgnoreAddr_P;
AddressList::AddrProperty *AddressList::AnyAddr_P;

AddressList::AddressList()
{
	if (LocalAddr_P == 0) {
		LocalAddr_P = new AddrProperty("local");
		ConfiguredAddr_P = new AddrProperty("configured");
		IgnoreAddr_P = new AddrProperty("ignore");
		AnyAddr_P = new AddrProperty("wildcard");
	}
	interfaces = 0;
}

AddressList::~AddressList()
{
	// Refcount AddressLists in order to GC properties?
}

AddressList::iflist_t *
AddressList::get_interfaces()
{
	iflist_t *iflist;

	if (interfaces != 0)
		iflist = new iflist_t(*interfaces);
	else {
		iflist = new iflist_t();
		getifaddrs_iflist(*iflist);
	}

	return iflist;
}

bool
AddressList::by_interface(bool start_empty)
{
	if (interfaces != 0)
		return false;

	interfaces = new iflist_t();
	if (!start_empty)
		getifaddrs_iflist(*interfaces);

	return true;
}

bool
AddressList::add_interface(char *name)
{
	if (interfaces == 0)
		return false;

	return (interfaces->insert(name)).second;
}

bool
AddressList::del_interface(char *name)
{
	if (interfaces == 0)
		return false;

	return (interfaces->erase(name) > 0);
}

bool
AddressList::add_property(netaddress &na, AddrProperty *p, bool propagate)
{
	propmap_t *props, *lpfm_props;
	propmap_t::iterator it;
	addr2prop_t::node *node;

	node = prop_trie.lookup_node(na, false, false);
	if (node != NULL) {
		props = node->data;
		if (props == NULL) {
			props = new propmap_t();
			node->data = props;
		}
		props->insert(pair<AddrProperty *, bool>(p, propagate));
		
	} else {
		props = new propmap_t();
		props->insert(pair<AddrProperty *, bool>(p, propagate));
		node = prop_trie.insert(na, *props);
	}

	if (propagate)
		bequeath(node, p, true);

	// copy lpfm properties
	lpfm_props = prop_trie.lookup(na, true);
	if (lpfm_props == NULL)
		return true;

	for (it = lpfm_props->begin(); it != lpfm_props->end(); it++) {
		if ((*it).second)
			props->insert((*it));
	}

	return true;
}

bool
AddressList::del_property(netaddress &na, AddrProperty *p, bool propagate)
{
	propmap_t *props, *lpfm_props;
	propmap_t::iterator it;
	addr2prop_t::node *node;

	node = prop_trie.lookup_node(na, false, true);
	if (node == NULL) {
		// no exact match
		if (!propagate) {
			node = prop_trie.lookup_node(na, true, true);
			if (node == NULL) {
				// no lpfm either, we're done
				return false;
			}

			props = node->data;
			it = props->find(p);
			if (it == props->end()) {
				// lpfm doesn't have p set -> done
				return false;
			}
		}
		// insert an empty propmap
		props = new propmap_t();
		node = prop_trie.insert(na, *props);

		// copy other lpfm properties
		lpfm_props = prop_trie.lookup(na, true);
		if (p != AnyAddr_P && lpfm_props != NULL) {
			for (it = lpfm_props->begin(); it != lpfm_props->end();
			    it++) {
				if ((*it).first != p && (*it).second)
					props->insert((*it));
			}
		}
	} else {
		props = node->data;
		if (p == AnyAddr_P) {
			props->clear();
		} else {
			it = props->find(p);
			if (it == props->end() && !propagate)
				return false;

			props->erase(it);
		}
	}

	if (propagate)
		bequeath(node, p, false);

	return true;
}

bool
AddressList::add_host_prop(const char *name, AddrProperty *p)
{
	netaddress na;
	sockaddr_in *sin;
	sockaddr_in6 *sin6;
	struct addrinfo hints = {0}, *res, *cur;
	int error;
	char buf[1024];

	if (name == NULL) {
		name = buf;
		if (gethostname(buf, sizeof(buf)) != 0)
			return false;
		buf[sizeof(buf) - 1] = '\0';
	}
	hints.ai_flags = AI_ADDRCONFIG | AI_CANONNAME;
	hints.ai_family = AF_UNSPEC;
	error = getaddrinfo(name, NULL, &hints, &res);
	if (error != 0)
		return false;

	for(cur = res; cur != NULL && error == 0; cur = cur->ai_next) {
		if (cur->ai_family == AF_INET) {
			sin = (struct sockaddr_in *)cur->ai_addr;
			na.set_ip(sin->sin_addr);
			na.set_pref_len(32);
		} else if (cur->ai_family == AF_INET6) {
			sin6 = (struct sockaddr_in6 *)cur->ai_addr;
			na.set_ip(sin6->sin6_addr);
			na.set_pref_len(128);
		} else
			continue;

		// cout << ++i << "XXMOB: " << na << endl;

		error += add_property(na, p) ? 0 : 1;
		// XXXMOB: for some reason we need a 'reset' here
		//         if we want to use /etc/hosts
		na.set_ip("127.0.0.1");
	}
	freeaddrinfo(res);

	return (error == 0);
}

bool
AddressList::del_host_prop(const char *name, AddrProperty *p)
{
	netaddress na;
	sockaddr_in *sin;
	sockaddr_in6 *sin6;
	struct addrinfo hints = {0}, *res, *cur;
	int error;
	char buf[1024];

	if (name == NULL) {
		name = buf;
		if (gethostname(buf, sizeof(buf)) != 0)
			return false;
		buf[sizeof(buf) - 1] = '\0';
	}
	hints.ai_flags = AI_ADDRCONFIG;
	hints.ai_family = AF_UNSPEC;
	error = getaddrinfo(name, NULL, &hints, &res);
	if (error != 0)
		return false;

	for(cur = res; cur != NULL && error == 0; cur = cur->ai_next) {
		if (cur->ai_family == AF_INET) {
			sin = (struct sockaddr_in *)cur->ai_addr;
			na.set_ip(sin->sin_addr);
			na.set_pref_len(32);
		} else if (cur->ai_family == AF_INET6) {
			sin6 = (struct sockaddr_in6 *)cur->ai_addr;
			na.set_ip(sin6->sin6_addr);
			na.set_pref_len(128);
		} else
			continue;

		error += del_property(na, p) ? 0 : 1;
	}
	freeaddrinfo(res);

	return (error == 0);
}

bool
AddressList::ignore(netaddress &na, bool propagate)
{
	del_property(na, AnyAddr_P, propagate);
	return add_property(na, IgnoreAddr_P);
}

bool
AddressList::unignore(netaddress &na, bool propagate)
{
	return del_property(na, IgnoreAddr_P, propagate);
}

bool
AddressList::ignore_bogons(void)
{
	netaddress na;

	// according to IANA Tue Apr 17 09:14:31 PDT 2007
	na.set_ip("0.0.0.0");na.set_pref_len(7);
	ignore(na);
	na.set_ip("2.0.0.0");na.set_pref_len(8);
	ignore(na);
	na.set_ip("5.0.0.0");na.set_pref_len(8);
	ignore(na);
	na.set_ip("7.0.0.0");na.set_pref_len(8);
	ignore(na);
	na.set_ip("23.0.0.0");na.set_pref_len(8);
	ignore(na);
	na.set_ip("27.0.0.0");na.set_pref_len(8);
	ignore(na);
	na.set_ip("31.0.0.0");na.set_pref_len(8);
	ignore(na);
	na.set_ip("36.0.0.0");na.set_pref_len(7);
	ignore(na);
	na.set_ip("39.0.0.0");na.set_pref_len(8);
	ignore(na);
	na.set_ip("42.0.0.0");na.set_pref_len(8);
	ignore(na);
	na.set_ip("49.0.0.0");na.set_pref_len(8);
	ignore(na);
	na.set_ip("50.0.0.0");na.set_pref_len(8);
	ignore(na);
	na.set_ip("94.0.0.0");na.set_pref_len(7);
	ignore(na);
	na.set_ip("100.0.0.0");na.set_pref_len(6);
	ignore(na);
	na.set_ip("104.0.0.0");na.set_pref_len(5);
	ignore(na);
	na.set_ip("112.0.0.0");na.set_pref_len(6);
	ignore(na);
	na.set_ip("169.254.0.0");na.set_pref_len(16);
	ignore(na);
	na.set_ip("173.0.0.0");na.set_pref_len(8);
	ignore(na);
	na.set_ip("174.0.0.0");na.set_pref_len(7);
	ignore(na);
	na.set_ip("176.0.0.0");na.set_pref_len(5);
	ignore(na);
	na.set_ip("184.0.0.0");na.set_pref_len(6);
	ignore(na);
	na.set_ip("191.0.0.0");na.set_pref_len(8);
	ignore(na);
	na.set_ip("192.0.2.0");na.set_pref_len(24);
	ignore(na);
	na.set_ip("197.0.0.0");na.set_pref_len(8);
	ignore(na);
	na.set_ip("198.18.0.0");na.set_pref_len(15);
	ignore(na);
	na.set_ip("223.0.0.0");na.set_pref_len(8);
	ignore(na);
	na.set_ip("240.0.0.0");na.set_pref_len(4);
	ignore(na);
	// according to http://www.cymru.com/Documents/bogonv6-list.html#agg
	na.set_ip("0000::");na.set_pref_len(8);
	ignore(na);
	na.set_ip("0100::");na.set_pref_len(8);
	ignore(na);
	na.set_ip("0200::");na.set_pref_len(7);
	ignore(na);
	na.set_ip("0400::");na.set_pref_len(7);
	ignore(na);
	na.set_ip("0600::");na.set_pref_len(7);
	ignore(na);
	na.set_ip("0800::");na.set_pref_len(5);
	ignore(na);
	na.set_ip("1000::");na.set_pref_len(4);
	ignore(na);
	na.set_ip("2000::");na.set_pref_len(16);
	ignore(na);
	na.set_ip("2001:1000::");na.set_pref_len(23);
	ignore(na);
	na.set_ip("2001:1600::");na.set_pref_len(23);
	ignore(na);
	na.set_ip("2001:2000::");na.set_pref_len(20);
	ignore(na);
	na.set_ip("2001:3000::");na.set_pref_len(20);
	ignore(na);
	na.set_ip("2001:4000::");na.set_pref_len(20);
	ignore(na);
	na.set_ip("2001:5000::");na.set_pref_len(20);
	ignore(na);
	na.set_ip("2001:6000::");na.set_pref_len(20);
	ignore(na);
	na.set_ip("2001:7000::");na.set_pref_len(20);
	ignore(na);
	na.set_ip("2001:8000::");na.set_pref_len(20);
	ignore(na);
	na.set_ip("2001:9000::");na.set_pref_len(20);
	ignore(na);
	na.set_ip("2001:A000::");na.set_pref_len(20);
	ignore(na);
	na.set_ip("2001:B000::");na.set_pref_len(20);
	ignore(na);
	na.set_ip("2001:C000::");na.set_pref_len(20);
	ignore(na);
	na.set_ip("2001:D000::");na.set_pref_len(20);
	ignore(na);
	na.set_ip("2001:E000::");na.set_pref_len(20);
	ignore(na);
	na.set_ip("2001:F000::");na.set_pref_len(20);
	ignore(na);
	na.set_ip("3FFF::");na.set_pref_len(16);
	ignore(na);
	na.set_ip("4000::");na.set_pref_len(3);
	ignore(na);
	na.set_ip("6000::");na.set_pref_len(3);
	ignore(na);
	na.set_ip("8000::");na.set_pref_len(3);
	ignore(na);
	na.set_ip("A000::");na.set_pref_len(3);
	ignore(na);
	na.set_ip("C000::");na.set_pref_len(3);
	ignore(na);
	na.set_ip("E000::");na.set_pref_len(4);
	ignore(na);
	na.set_ip("F000::");na.set_pref_len(5);
	ignore(na);
	na.set_ip("F800::");na.set_pref_len(6);
	ignore(na);
	na.set_ip("FC00::");na.set_pref_len(7);
	ignore(na);
	na.set_ip("FE00::");na.set_pref_len(9);
	ignore(na);

	return true;
}

bool
AddressList::ignore_locals(void)
{
	netaddress na;

	na.set_ip("10.0.0.0");na.set_pref_len(8);
	ignore(na);
	na.set_ip("172.16.0.0");na.set_pref_len(12);
	ignore(na);
	na.set_ip("192.168.0.0");na.set_pref_len(16);
	ignore(na);
	na.set_ip("FE80::");na.set_pref_len(10);
	ignore(na);
	na.set_ip("FEC0::");na.set_pref_len(10);
	ignore(na);

	return true;
}

bool
AddressList::ignore_loopback(void)
{
	netaddress na;

	na.set_ip("127.0.0.0");na.set_pref_len(8);
	ignore(na);
	na.set_ip("::1");na.set_pref_len(128);
	ignore(na);

	return true;
}

bool
AddressList::addr_is(netaddress &na, AddrProperty *prop)
{
	propmap_t *props;
	propmap_t::iterator it;

	if (addr_is_in(na, IgnoreAddr_P))
		return false;

	props = prop_trie.lookup(na, false);
	if (props != NULL) {
		it = props->find(prop);
		if (it != props->end()) {
			return true;
		}
	}

	if (prop != LocalAddr_P)
		return false;

	return getifaddrs_is_local(na);
}

bool
AddressList::addr_is_in(netaddress &na, AddrProperty *prop)
{
	addr2prop_t::node *node;
	propmap_t *props;
	propmap_t::iterator it;

	node = prop_trie.lookup_node(na, true, true);
	if (node == NULL)
		return false;

	props = node->data;
	it = props->find(prop);
	if (it == props->end())
		return false;

	if (!(*it).second && props != prop_trie.lookup(na, false))
			return false;

	return true;
}

AddressList::addrlist_t *
AddressList::get_addrs(AddrProperty *prop)
{
	addr2prop_t::node *node;
	netaddress na;
	addrlist_t *res = new addrlist_t();

	if (res == 0)
		return res;

	if (prop == LocalAddr_P || prop == AnyAddr_P)
		getifaddrs_get_addrs(*res);

	na.set_ip("0.0.0.0");
	na.set_pref_len(0);
	node = prop_trie.lookup_node(na, true, false);
	collect(node, prop, *res);

	na.set_ip("::");
	node = prop_trie.lookup_node(na, true, false);
	collect(node, prop, *res);

	return res;
}

netaddress *
AddressList::get_first(AddrProperty *p, bool IPv4)
{
	addr2prop_t::node *node;
	netaddress na;
	addrlist_t list;
	addrlist_t::iterator it;

	if (IPv4) {
		na.set_ip("0.0.0.0");
		na.set_pref_len(0);
	} else {
		na.set_ip("::");
		na.set_pref_len(0);
	}

	node = prop_trie.lookup_node(na, true, false);
	node = collect_first(node, p);
	if (node != NULL)
		return new netaddress(*node->key);

	if (p == LocalAddr_P) {
		getifaddrs_get_addrs(list);
		for (it = list.begin(); it != list.end(); it++)
			if ((*it).is_ipv4() == IPv4)
				return new netaddress(*it);
	}

	return NULL;
}

netaddress *
AddressList::get_src_addr(const netaddress &dest, uint32_t *prefs)
{
	netaddress *res;
	int sfd;

	sfd = socket(dest.is_ipv4()?AF_INET:AF_INET6, SOCK_DGRAM, 0);
	if (sfd == -1)
		return NULL;

#ifdef IPV6_ADDR_PREFERENCES
	if (prefs != NULL && setsockopt(s, IPV6_ADDR_PREFERENCES,
	    (void *)prefs, sizeof (*prefs)) == -1) {
		close(sfd);
		return NULL;
	}
#endif
	if (dest.is_ipv4()) {
		struct sockaddr_in sin = {0};
		socklen_t slen = sizeof(sin);
		sin.sin_family = AF_INET;
		sin.sin_port = htons(4);
		dest.get_ip(sin.sin_addr);
		if (connect(sfd, (struct sockaddr *)&sin, sizeof(sin)) == -1) {
			close(sfd);
			return NULL;
		}
		if (getsockname(sfd, (struct sockaddr *)&sin, &slen) == -1) {
			close(sfd);
			return NULL;
		}
		close(sfd);
		res = new netaddress();
		res->set_ip(sin.sin_addr);
		res->set_pref_len(32);
		return (res);
	} else {
		struct sockaddr_in6 sin6 = {0};
		socklen_t slen = sizeof(sin6);
		sin6.sin6_family = AF_INET6;
		sin6.sin6_port = htons(4);
		dest.get_ip(sin6.sin6_addr);
		if (connect(sfd, (struct sockaddr *)&sin6,
		    sizeof(sin6)) == -1) {
			close(sfd);
			return NULL;
		}
		if (getsockname(sfd, (struct sockaddr *)&sin6, &slen) == -1) {
			close(sfd);
			return NULL;
		}
		close(sfd);
		res = new netaddress();
		res->set_ip(sin6.sin6_addr);
		res->set_pref_len(128);
		return (res);
	}
}

void
AddressList::getifaddrs_iflist(iflist_t &list)
{
	struct ifaddrs *ifap, *cifa;

	if (::getifaddrs(&ifap) != 0)
		return;

	for (cifa = ifap; cifa != NULL; cifa = cifa->ifa_next) {
		list.insert(cifa->ifa_name);
	}

	freeifaddrs(ifap);
}

bool
AddressList::getifaddrs_is_local(netaddress &na)
{
	struct ifaddrs *ifap, *cifa;

	if (::getifaddrs(&ifap) != 0)
		return false;

	for (cifa = ifap; cifa != NULL; cifa = cifa->ifa_next) {
		hostaddress ha;

		if (cifa->ifa_addr->sa_family == AF_INET) {
			ha.set_ip(
			    ((struct sockaddr_in *)cifa->ifa_addr)->sin_addr);
		} else if (cifa->ifa_addr->sa_family == AF_INET6) {
			ha.set_ip(
			    ((struct sockaddr_in6 *)cifa->ifa_addr)->sin6_addr);
		} else {
			continue;
		}

		if (interfaces &&
		    interfaces->find(cifa->ifa_name) == interfaces->end())
			continue;

		if (ha.match_against(na) >= na.get_pref_len()) {
			freeifaddrs(ifap);
			return true;
		}
	}

	freeifaddrs(ifap);

	return false;
}

void
AddressList::getifaddrs_get_addrs(addrlist_t &list)
{
	struct ifaddrs *ifap, *cifa;

	if (::getifaddrs(&ifap) != 0)
		return;

	for (cifa = ifap; cifa != NULL; cifa = cifa->ifa_next) {
		hostaddress *ha;
		netaddress na;

		if (interfaces &&
		    interfaces->find(cifa->ifa_name) == interfaces->end())
			continue;

		if (cifa->ifa_addr->sa_family == AF_INET) {
			ha = new hostaddress;
			ha->set_ip(
			    ((struct sockaddr_in *)cifa->ifa_addr)->sin_addr);
			na.set_pref_len(32);
		} else if (cifa->ifa_addr->sa_family == AF_INET6) {
			ha = new hostaddress;
			ha->set_ip(
			    ((struct sockaddr_in6 *)cifa->ifa_addr)->sin6_addr);
			na.set_pref_len(128);
		} else {
			continue;
		}

		na.set_ip(*ha);
		if (!addr_is_in(na, IgnoreAddr_P))
			list.insert(*ha);
	}

	freeifaddrs(ifap);
}

void
AddressList::bequeath(addr2prop_t::node *head, AddrProperty *p, bool add)
{
	propmap_t *props;
	propmap_t::iterator it;

	if (p == AnyAddr_P && add)
		return;

	props = head->data;
	if (props != NULL) {
		if (p == AnyAddr_P) {
			props->clear();
		} else {
			if (add) {
				props->insert(pair<AddrProperty *, bool>
				    (p, true));
			} else {
				it = props->find(p);
				if (it != props->end())
					props->erase(it);
			}
		}
	}

	if (head->left->index > head->index)
		bequeath(head->left, p, add);
	if (head->right->index > head->index)
		bequeath(head->right, p, add);
}

void
AddressList::collect(addr2prop_t::node *head, AddrProperty *p,
    addrlist_t &list)
{
	propmap_t *props;
	propmap_t::iterator it;

	props = head->data;
	if (props != NULL) {
		if (p == AnyAddr_P) {
			it = props->begin();
		} else {
			it = props->find(p);
		}
		if (it != props->end()) {
			list.insert(*(new netaddress(*head->key)));
		}
	}

	if (head->left->index > head->index)
		collect(head->left, p, list);
	if (head->right->index > head->index)
		collect(head->right, p, list);
	
}

AddressList::addr2prop_t::node *
AddressList::collect_first(addr2prop_t::node *head, AddrProperty *p)
{
	addr2prop_t::node *res = NULL;
	propmap_t *props;
	propmap_t::iterator it;

	props = head->data;
	if (props != NULL) {
		if (p == AnyAddr_P) {
			it = props->begin();
		} else {
			it = props->find(p);
		}
		if (it != props->end()) {
			return head;
		}
	}

	if (head->left->index > head->index) {
		res = collect_first(head->left, p);
		if (res != NULL)
			return res;
	}
	if (head->right->index > head->index) {
		res = collect_first(head->right, p);
		if (res != NULL)
			return res;
	}

	return NULL;
}


} // end namespace protlib