source: trash/old-modules/transport/protlib/address.h @ 5641

/// ----------------------------------------*- mode: C++; -*--
/// @file address.h
/// GIST address objects
/// ----------------------------------------------------------
/// $Id: address.h 3063 2008-07-02 08:02:45Z bless $
/// $HeadURL: https://svn.ipv6.tm.uka.de/nsis/protlib/trunk/include/address.h $
// ===========================================================
//
// 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
 */

#ifndef PROTLIB__ADDRESS_H
#define PROTLIB__ADDRESS_H

#include "protlib_types.h"
#include "ie.h"

#include <ext/hash_map>
#include <netinet/in.h>
#include <set>

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

namespace protlib {
  using namespace log;

/// Address base class
/** This is the base class for IP host and application addresses, router,
 * interface and user identification and AS numbers.
 */
class address {
  public:
        virtual address* new_instance() const = 0;
        virtual address* copy() const = 0;
        virtual bool operator==(const address& address) const = 0;

        inline bool operator!=(const address& address) const {
                return (!(*this==address));
        }


        enum subtype_t {
                /** 255 is not a valid subtype and is used to register for all
                 * subtypes.
                 * @note This is no valid subtype because it is not in 0..64.
                 */
                all_subtypes          = 255,
                // @{
                /// address subtypes
                /** These are the address-specific subtypes. */
                IPv4HostAddress       =   1,
                IPv6HostAddress       =   2,
                IPv4NetAddress        =   3,
                IPv6NetAddress        =   4,
                IPv4ApplAddress       =   5,
                IPv6ApplAddress       =   6,
                IPv6Unspecified       =   7,
                UDSAddress            =   8,
                FlowAddressSpec       =  12,
                AS16                  =  14,
                AS32                  =  15,
                IEEE48                =  16,
                EUI48                 =  17,
                EUI64                 =  18,
                NAI                   =  32,
                X509                  =  33
                // @}
        }; // end subtype_t

        virtual ~address() {};

  subtype_t get_type() const { return subtype; };

  protected:
        /// constructor with subtype
        address(subtype_t st);
        /// virtual destructor

        void throw_nomem_error() const;

        subtype_t subtype;
};

// forward declaration
class netaddress;

/// IP Host Address
/** This class can hold IPv4 and IPv6 Host Addresses. */
class hostaddress : public address {

  public:
        virtual hostaddress* new_instance() const;
        virtual hostaddress* copy() const;
        virtual bool operator==(const address& ie) const;

        /// constructor
        hostaddress();
        /// copy constructor
        hostaddress(const hostaddress& h);
        /// assignment
        hostaddress& operator=(const hostaddress& h);
        /// constructor from string
        hostaddress(const char *str, bool *res = NULL);
        /// constructor from in6_addr
        hostaddress(const struct in6_addr& ipv6addr);
        /// destructor
        virtual ~hostaddress();
        /// set IPv4 from string
        bool set_ipv4(const char *str);
        /// set IPv4 from in_addr
        void set_ip(const struct in_addr &in);
        /// set IPv6 from string
        bool set_ipv6(const char *str);
        /// set IPv6 from in6_addr
        void set_ip(const struct in6_addr &in);
        /// set IPv4 or IPv6 from string
        bool set_ip(const char *str);
        bool set_ip(const string& str);
        /// set IP from hostaddress
        void set_ip(const hostaddress& h);
        /// is IP unspecified
        bool is_ip_unspec() const;
        /// get ip address as string
        const char *get_ip_str() const;
        /// get ip address as string
        const char *get_ip_str(char *str) const;
        /// is it IPv4
        bool is_ipv4() const;
        /// is it IPv6
        bool is_ipv6() const;
        /// is bogus source (e.g. localhost, multicast)
        bool is_bogus_source() const;
        /// is it a 4to6-mapped address?
        bool is_mapped_ip() const;
        /// get as in_addr?
        bool get_ip(struct in_addr& in) const;
        /// get as in6_addr?
        bool get_ip(struct in6_addr& in) const;
        /// get as in6_addr?
        const struct in6_addr *get_ip() const { return ipv4flag ? 0 : &ipv6addr; };
        /// convert to iPv6
        virtual void convert_to_ipv6();
        /// are they equivalent
        virtual bool equiv(const hostaddress& h) const;
        /// lookup host name
        string get_host_name(bool *res = NULL) const;
        /// hash function
        virtual size_t get_hash() const;
        /// match against IP address
        virtual int match_against(const hostaddress& ha) const;
        /// match against network prefix
        virtual int match_against(const netaddress& na) const;
protected:
        /// IPv4 flag
        bool ipv4flag;
        /// set subtype and IPv4 flag
        virtual void set_subtype(bool ipv4);
        /// IP buffer
        /** I in protected and NOT private scope because subclasses have to
         * (de)serialize it.
         */
        union {
                /// IPv4 address
                struct in_addr ipv4addr;
                /// IPv6 address
                struct in6_addr ipv6addr;
        }; // end union
public:
        /// clear IP buffer (sets IP address to undefined/any and deletes any outstring)
        void clear_ip();
private:
        /// pointer to IP string representation
        mutable char *outstring;
}; // end hostaddress

inline ostream &operator<<(ostream &out, const hostaddress &addr) {
     return out << addr.get_ip_str();
}

inline
hostaddress::hostaddress(const struct in6_addr& ipv6addr)
  : address(IPv6HostAddress),
    ipv4flag(false),
    ipv6addr(ipv6addr),
    outstring(NULL)
{ set_subtype(false); }


/// ========================================================
/// IP Application Address
/// ========================================================
/** Consists of a IP Host Address and a port number. */
class appladdress : public hostaddress {
    public:
        virtual appladdress* new_instance() const;
        virtual appladdress* copy() const;
        virtual bool operator==(const address& ie) const;

        /// hash function
        virtual size_t get_hash() const;

    protected:
        /// set subtype and IPv4 flag
        virtual void set_subtype(bool ipv4);

    public:
        /// constructor
        appladdress();
        /// copy constructor
        appladdress(const appladdress& app);
        ///constructor for use as Unix Domain Address
        appladdress(string socket);
        ///constructor for use to specify a explicit socket number (used when no addressing for peer can be derived)
        appladdress(int socket);
        /// constructor from hostaddress, protocol ID and port
        appladdress(const hostaddress& h, protocol_t prot, port_t p);
        /// constructor from sockaddr_in6 sockaddr
        appladdress(const sockaddr_in6& sockaddr,  protocol_t prot);
        /// constructor from hostaddress, protocol name and port
        appladdress(const hostaddress& h, const char* pname, port_t p, bool *res = NULL);
        /// constructor from string, protocol ID and port
        appladdress(const char* str, protocol_t prot, port_t p, bool *res = NULL);
        /// constructor from string, protocol name and port
        appladdress(const char* str, const char* pname, port_t p, bool *res = NULL);
        /// constructor from string, protocol name and port name
        appladdress(const char* str, const char* pname, const char* portname, bool *res = NULL);
        /// assignment
        appladdress& operator=(const appladdress& app);
        /// virtual destructor
        virtual ~appladdress() {};


        /// are they equivalent
        ///virtual bool equiv(const appladdress& h) const { return hostaddress::equiv(h); }

        /// set port
        port_t set_port(port_t p);
        /// set port
        port_t set_port(const char* pname, bool *res = NULL);
        /// set port
        port_t set_port(const string& pname, bool *res = NULL);
        /// get port
        port_t get_port() const;

        /// get sockaddr_in6
        void get_sockaddr(struct sockaddr_in6& sockaddr) const;
        /// get port name
        string get_port_name(bool *res = NULL) const;
        /// set protocol by ID
        protocol_t set_protocol(protocol_t p);
        /// set protocol by name
        protocol_t set_protocol(const char* pname, bool *res = NULL);
        /// set protocol by name
        protocol_t set_protocol(const string& pname, bool *res = NULL);
        /// get protocol ID
        protocol_t get_protocol() const;
        /// get protocol name
        string get_protocol_name(bool *res = NULL) const;
        /// get prefix
        inline
        uint8 get_prefix() const {
            return prefix;
        }

        /// set prefix
        inline
        void set_prefix(uint8 prfx) {
            prefix=prfx;
        }

        /// set IP TTL
        inline
        void set_ip_ttl(uint16 ttl) {
            ip_ttl = ttl;
        }


        /// unset IP TTL
        inline
        void unset_ip_ttl() {
            ip_ttl = 0;
        }


        /// get IP TTL, if == 0, no IP TTL should be set
        inline
        uint16 get_ip_ttl() const {
        return ip_ttl;
        }


        /// set RAO value
        inline
        void set_rao(uint16 value) {
            rao_presence = true;
            rao = value;
        }

        /// unset RAO value
        inline
        void unset_rao() {
            rao_presence = false;
            rao = 0;
        }

        /// get RAO value
        inline
        uint16 get_rao() const {
            return rao;
        }


        /// test if RAO present
        inline
        bool rao_present() const {
        return rao_presence;
        }

        /// set outgoing Interface index
        inline
        void set_if_index(uint16 value) {
        if_index = value;
        }

        /// get outgoing Interface index
        inline
        uint16 get_if_index() const {
            return if_index;
        }

        /// unset outgoing Interface index
        inline
        void unset_if_index() {
            if_index = 0;
        }





    private:
        protocol_t proto;
        port_t port;
        uint8 prefix;

        uint16 rao;
        uint16 ip_ttl;
        bool rao_presence;
        uint16 if_index;

    }; // end appladdress


inline
appladdress::appladdress(const sockaddr_in6& sockaddr, protocol_t prot)
    : hostaddress(sockaddr.sin6_addr), proto(prot), port(ntohs(sockaddr.sin6_port)), rao(0), ip_ttl(0), rao_presence(false), if_index(0)
{
  //Log(DEBUG_LOG,LOG_NORMAL,"address","address constructor called for sockaddr_in6");
}

/** Constructor sets address type and clears port sets prefix to 32 (ipv4). */
inline
appladdress::appladdress() : hostaddress(),
                             proto(0),
                             port(0),
                             prefix(32),
                             rao(0),
                             ip_ttl(0),
                             rao_presence(false),
                             if_index(0)

{
  //Log(DEBUG_LOG,LOG_NORMAL,"address","address constructor called for bool ipv4=" << ipv4);
  set_subtype(ipv4flag);
} // end constructor

inline
appladdress::appladdress(const appladdress& app) : hostaddress(app),
                                                   proto(app.proto),
                                                   port(app.port),
                                                   prefix(app.prefix),
                                                   rao(app.rao),
                                                   ip_ttl(app.ip_ttl),
                                                   rao_presence(app.rao_presence),
                                                   if_index(app.if_index)

{
    //Log(DEBUG_LOG,LOG_NORMAL,"appladdress", "Copy address constructor called for appladdress& app:" << app);
    //DLog("appladdress", "UDSsocket copied: " << uds_socket);
  //DLog("appladdress", "ip_ttl: " << ip_ttl << " if_index: " << if_index);


    set_subtype(ipv4flag);
} // end copy constructor

/** Initialize with the given host address, protocol ID and port number. */
inline
appladdress::appladdress(const hostaddress& h, protocol_t prot, port_t p)
    : hostaddress(h),
      proto(prot),
      port(p),
      prefix(0),
      rao(0),
      ip_ttl(0),
      rao_presence(false),
      if_index(0)
{
  //Log(DEBUG_LOG,LOG_NORMAL,"address","address constructor called for (const hostaddress& h, protocol_t prot, port_t p)");

  set_subtype(ipv4flag);
} // end constructor(hostaddress,prot,port)

/** Initialize with the given host address, protocol name and port number.
 * If no protocol ID can be found in the protocol database, it is set to 0.
 */
inline
appladdress::appladdress(const hostaddress& h, const char* pname, port_t p, bool *res)
  : hostaddress(h),
    proto(tsdb::getprotobyname(pname,res)),
    port(p),
    prefix(0),
    rao(0),
    ip_ttl(0),
    rao_presence(false),
    if_index(0)

{
  //Log(DEBUG_LOG,LOG_NORMAL,"address","address constructor called for (const hostaddress& h, const char* pname, port_t p, bool *res)");

    set_subtype(ipv4flag);
} // end constructor(hostaddress,pname,port)

/** Initialize from string, protocol ID and port.
 * If the string does not contain a vaild IP address, it is set to all 0 by
 * the hostaddress constructor.
 */
inline
appladdress::appladdress(const char* str, protocol_t prot, port_t p, bool *res)
  : hostaddress(str,res),
    proto(prot),
    port(p),
    prefix(0),
    rao(0),
    ip_ttl(0),
    rao_presence(false),
    if_index(0)
{
    set_subtype(ipv4flag);
} // end constructor(string,prot,port)

/** Initialize from string, protocol name and port.
 * If the string does not contain a vaild IP address, it is set to all 0 by
 * the hostaddress constructor.
 * If no protocol ID can be found in the protocol database, it is set to 0.
 */
inline
appladdress::appladdress(const char* str, const char* pname, port_t p, bool *res)
  : hostaddress(str,res),
    port(p),
    prefix(0),
    rao(0),
    ip_ttl(0),
    rao_presence(false),
    if_index(0)
{
  //Log(DEBUG_LOG,LOG_NORMAL,"address","address constructor called for (const char* str, const char* pname, port_t p, bool *res)");

    register bool tmpres = false;
    proto = tsdb::getprotobyname(pname,&tmpres);
    if (res) *res = ((*res) && tmpres);
    set_subtype(ipv4flag);
} // end constructor(string,pname,port)

/** Initialize from string, protocol name and port name.
 * If the string does not contain a vaild IP address, it is set to all 0 by
 * the hostaddress constructor.
 * If no protocol ID can be found in the protocol database, it is set to 0.
 * If no port number can be found in the service database, it is set to 0.
 */
inline
appladdress::appladdress(const char* str, const char* pname, const char* portname, bool *res)
    : hostaddress(str,res),
      prefix(0),
      rao(0),
      ip_ttl(0),
      rao_presence(false),
      if_index(0)
{
  //Log(DEBUG_LOG,LOG_NORMAL,"address","address constructor called for (const char* str, const char* pname, const char* portname, bool *res)");

    bool res1 = false;
    bool res2 = false;
    proto = tsdb::getprotobyname(pname,&res1);
    port = tsdb::get_portnumber(portname,proto,&res2);
    if (res) *res = ((*res) && res1 && res2);
    set_subtype(ipv4flag);
    prefix = 0;
} // end constructor(string,pname,portname)

/** Assigns the given application address by using hostaddress::operator=(). */
inline
appladdress&
appladdress::operator=(const appladdress& app)
{
        hostaddress::operator=(app);
        proto = app.proto;
        port = app.port;
        prefix = app.prefix;
        ip_ttl = app.ip_ttl;
        rao_presence = app.rao_presence;
        rao = app.rao;
        if_index = app.if_index;
        return *this;
} // end operator=


/** Set port and return old value. */
inline
port_t appladdress::set_port(port_t p) {
        register port_t op = port;
        port = p;
        return op;
} // end set_port



/** Set port and return old value.
 * If the port name is not found in the service database, port is set to 0.
 */
inline
port_t appladdress::set_port(const char* pname, bool *res) {
        register port_t op = port;
        port = tsdb::get_portnumber(pname,proto,res);
        return op;
} // end set_port

/** Set port and return old value.
 * If the port name is not found in the service database, port is set to 0.
 */
inline
port_t appladdress::set_port(const string& pname, bool *res) {
        register port_t op = port;
        port = tsdb::get_portnumber(pname,proto,res);
        return op;
} // end set_port

inline
port_t appladdress::get_port() const { return port; }

inline
string appladdress::get_port_name(bool *res) const {
        return tsdb::get_portname(port,proto,res);
} // end get_port_name

/** Set protocol ID and return old value. */
inline
protocol_t appladdress::set_protocol(protocol_t p) {
        register protocol_t o = proto;
        proto = p;
        return o;
} // end set_protocol

/** Set protocol ID and return old value.
 * If no protocol ID can be found in the protocol database, it is set to 0.
 */
inline
protocol_t appladdress::set_protocol(const char* pname, bool *res) {
        register protocol_t o = proto;
        proto = tsdb::getprotobyname(pname,res);
        return o;
} // end set_protocol

/** Set protocol ID and return old value.
 * If no protocol ID can be found in the protocol database, it is set to 0.
 */
inline
protocol_t appladdress::set_protocol(const string& pname, bool *res) {
        register protocol_t o = proto;
        proto = tsdb::getprotobyname(pname,res);
        return o;
} // end set_protocol

inline
protocol_t appladdress::get_protocol() const { return proto; }

inline
string appladdress::get_protocol_name(bool *res) const {
        return tsdb::getprotobynumber(proto,res);
} // end get_protocol_name

inline
size_t appladdress::get_hash() const {
        uint32 tmp = (proto<<16)+port;
        return (hostaddress::get_hash() ^ tmp);
} // end get_hash

inline
void
appladdress::get_sockaddr(struct sockaddr_in6& sa) const
{
  if (!ipv4flag)
  {
    sa.sin6_family= PF_INET6;
    sa.sin6_port  = htons(port);
    sa.sin6_addr  = ipv6addr;
  }
}

/// Network Prefix (or net address)
/** Holds an IP address and a prefix length in bits. */
class netaddress : public hostaddress {
/***** inherited from IE ****/
public:
        virtual netaddress* new_instance() const;
        virtual netaddress* copy() const;
        virtual bool operator==(const address& ie) const;

        /// convert to iPv6
        virtual void convert_to_ipv6();
        /// hash function
        virtual size_t get_hash() const;
        virtual int match_against(const netaddress& na) const;
protected:
        /// set subtype and IPv4 flag
        virtual void set_subtype(bool ipv4);
/***** new members *****/
public:
        /// constructor
        netaddress();
        /// copy constructor
        netaddress(const netaddress& na);
        /// constructor from hostaddress and prefix length
        netaddress(const hostaddress& h, prefix_length_t len = 128);
        /// constructor from string
        netaddress(const char* str, bool *res = NULL);
        /// constructor from string and prefix length
        netaddress(const char* str, prefix_length_t len, bool *res = NULL);
        /// assignment
        netaddress& operator=(const netaddress& na);
        /// assignment
        netaddress& operator=(const hostaddress& ha);

        // set prefix length
        prefix_length_t set_pref_len(prefix_length_t len);
        // get prefix length
        prefix_length_t get_pref_len() const;
        /// comparison for prefixmap
        bool operator<(const netaddress& na) const;

        int rdx_cmp(const netaddress *na, int *pos) const;
private:
        prefix_length_t prefix_length;
}; // end netaddress

inline ostream &operator<<(ostream &out, const netaddress &addr) {
     return out << addr.get_ip_str() << "/" << (int)addr.get_pref_len();
}

/// Unix Domain Socket Address
/** This class can hold a Unix Domain Socket Address OR a Socket Number. */
class udsaddress : public address {

  public:
    virtual udsaddress* new_instance() const;
    virtual udsaddress* copy() const;
    virtual bool operator==(const address& ie) const;

    /// constructor
    udsaddress() : address(UDSAddress) { uds_socket = ""; socknum=0;};
    /// copy constructor
    udsaddress(const udsaddress& h) : address(UDSAddress) { uds_socket = string(h.uds_socket.c_str()); socknum = h.socknum; };
    /// assignment
    udsaddress& operator=(const udsaddress& uds) {
        uds_socket = string(uds.uds_socket);
        socknum = uds.socknum;
        return *this;
    };
    /// constructor from string
    udsaddress(string sockstring): address(UDSAddress) { uds_socket = string(sockstring.c_str()); socknum=0; };
    /// constructor from int
    udsaddress(int num): address(UDSAddress) { socknum = num; uds_socket=""; };
    /// constructor from both
    udsaddress(string sockstring, int num): address(UDSAddress) { socknum = num; uds_socket=string(sockstring.c_str()); };
    /// destructor
    virtual ~udsaddress() {};

    /// hash function
    virtual size_t get_hash() const;

private:
    /// uds socket string
    string uds_socket;
    /// socket number
    int socknum;

public:

/** Set UDS socket path. */
inline
void set_udssocket(string socket) {
    uds_socket = socket;
} // end set_uds socket path


/** Get UDS socket path. */
inline
const string get_udssocket() const {
    return uds_socket;
} // end get_udspath


/** Set Socket Number */
inline
void set_socknum(int socket) {
    socknum = socket;
} // end set_socknum

/** Get Socket Number */
inline
const int get_socknum() const {
    return socknum;
} // end get_socknum



}; // end udsaddress

template <typename _dT>
class RadixTrie {
public:
        typedef _dT     data_type;

        struct node {
                node(netaddress *k, data_type *d) : key(k), data(d) {
                        left = right = this;
                        index = 0;
                }
                ~node() {
                        if (data)
                                delete data;
                        if (key)
                                delete key;
                        if (left != 0 && left->index > index)
                                delete left;
                        if (right != 0 && right->index > index)
                                delete right;
                }
                node                    *left;
                node                    *right;
                netaddress              *key;
                data_type               *data;
                int                      index;
        };

        RadixTrie() {
                netaddress *def;
                def = new netaddress("0.0.0.0", (prefix_length_t)0);
                v4head = new node(def, 0);
                def = new netaddress("::", (prefix_length_t)0);
                v6head = new node(def, 0);
        }

        ~RadixTrie() {
                delete v4head;
                delete v6head;
        }

        node *insert(netaddress &key, data_type &dat) {
                node *a, *b, *c, *n, *m;
                int cmp, pos = 0;

                c = a = key.is_ipv4() ? v4head : v6head;

                // search the tree as long as there are bits left in key
                while (key.get_pref_len() > a->index) {

                        // compare key to key in node a from position a->index
                        pos = a->index - 1;
                        cmp = key.rdx_cmp(a->key, &pos);
                        if (pos < 0)
                                abort();

                        // in case of a perfect match
                        if ((cmp == 0) &&
                            (a->key->get_pref_len() == key.get_pref_len())) {
                            // replace data in node
                                if (a->data)
                                        delete a->data;
                                a->data = &dat;
                                return a;
                        }

                        if (cmp == 0)
                                break;

                        // select node to continue the search based on the
                        // first different bit between a and key
                        b = cmp < 0 ? a->left : a->right;

                        // we reached a dead end
                        if (b->index <= a->index)
                                break;

                        // the first difference was before a's bitmask ended
                        // we must not make any more progress
                        if (pos <= a->key->get_pref_len())
                                break;

                        c = a;
                        a = b;
                }

                // first check if a and key share a common prefix
                if ((key.get_pref_len() == a->key->get_pref_len()) ||
                   (pos > a->index && pos <= a->key->get_pref_len())) {
                        int opos = pos;

                        // make sure we didn't just miss the perfect match
                        pos = a->index;
                        cmp = key.rdx_cmp(a->key, &pos);
                        if (cmp == 0 &&
                            (a->key->get_pref_len() == key.get_pref_len())) {
                            // replace data in node
                                if (a->data)
                                        delete a->data;
                                a->data = &dat;
                                return a;
                        }

                        // create a node with that prefix
                        pos = opos;
                        n = new node(new netaddress(key), 0);
                        n->key->set_pref_len(pos - 1);

                        // hook it to the previous node(c)
                        pos = c->index;
                        cmp = n->key->rdx_cmp(c->key, &pos);
                        n->index = pos;
                        if (n->index <= c->index) {
                                cout << "DEAD NODE INSERTION!!!" << endl;
                                abort();
                        }
                        if (cmp < 0) {
                                if (c->left != a) {
                                        cout << "TREE CORRUPTION!!!" << endl;
                                        abort();
                                }
                                c->left = n;
                        } else {
                                if (c->right != a) {
                                        cout << "TREE CORRUPTION!!!" << endl;
                                        abort();
                                }
                                c->right = n;
                        }

                        // hook the current node(a) to the common prefix
                        // node(n)
                        pos = n->index;
                        cmp = a->key->rdx_cmp(n->key, &pos);
                        a->index = pos;
                        if (a->index <= n->index) {
                                cout << "DEAD NODE INSERTION!!!" << endl;
                                abort();
                        }
                        if (cmp < 0)
                                n->left = a;
                        else
                                n->right = a;

                        // create a new node(m) for the insert
                        m = new node(new netaddress(key), &dat);
                        // hook node(m) to the common prefix node(n)
                        pos = n->index;
                        cmp = m->key->rdx_cmp(n->key, &pos);
                        m->index = pos;
                        if (cmp < 0) {
                                if (n->left == a) {
                                        cout << "OVERWRITE!!!" << endl;
                                        abort();
                                }
                                n->left = m;
                        } else {
                                if (n->right == a) {
                                        cout << "OVERWRITE!!!" << endl;
                                        abort();
                                }
                                n->right = m;
                        }

                        return m;
                }

                // c is a prefix of key, key is a prefix of a
                if (a->index >= pos) {
                        // create a new node for the key
                        n = new node(new netaddress(key), &dat);
                        // hook it to the previous node(c)
                        n->index = pos;
                        if (n->index <= c->index) {
                                cout << "DEAD NODE INSERTION!!!" << endl;
                                abort();
                        }
                        if (cmp < 0) {
                                if (c->left != a) {
                                        cout << "TREE CORRUPTION!!!" << endl;
                                        abort();
                                }
                                c->left = n;
                        } else {
                                if (c->right != a) {
                                        cout << "TREE CORRUPTION!!!" << endl;
                                        abort();
                                }
                                c->right = n;
                        }

                        // hook the current node(a) to the newly created
                        // node(n)
                        pos = n->index;
                        cmp = a->key->rdx_cmp(n->key, &pos);
                        a->index = pos;
                        if (a->index <= c->index) {
                                cout << "DEAD NODE INSERTION!!!" << endl;
                                abort();
                        }
                        if (cmp < 0)
                                n->left = a;
                        else
                                n->right = a;

                        return n;
                }

                // reached a deadend, simply add a new node
                n = new node(new netaddress(key), &dat);
                n->index = pos;
                if (n->index <= a->index) {
                        cout << "DEAD NODE INSERTION!!!" << endl;
                        abort();
                }
                if (b->index <= a->index) {
                        if (cmp < 0)
                                a->left = n;
                        else
                                a->right = n;
                } else {
                        cout << "TREE CORRUPTION!!!" << endl;
                        abort();
                }

                return n;
        }

        node *lookup_node(netaddress &key, bool lpfm = true,
            bool with_data = true) {
                node *a, *b, *c, *lpfn;
                int cmp, pos = 0;

                lpfn = 0;
                c = b = a = key.is_ipv4() ? v4head : v6head;
                if (lpfm) {
                        if (!with_data)
                                lpfn = a;
                        else if (a->data)
                                lpfn = a;
                }

                // search the tree as long as there are bits left in key
                while (key.get_pref_len() > a->index) {

                        // compare key to key in node a from pos
                        pos--;
                        cmp = key.rdx_cmp(a->key, &pos);

                        // all of key consumed
                        if (cmp == 0) {
                                // key is less specific than a
                                if (key.get_pref_len() <
                                    a->key->get_pref_len())
                                        return lpfm ? lpfn : NULL;

                                // key is an exact match for a
                                if (key.get_pref_len() >=
                                    a->key->get_pref_len()) {
                                        if (!with_data)
                                                return a;
                                        if (a->data)
                                                return a;
                                        return lpfm ? lpfn : NULL;
                                }
                        }

                        // all of a consumed -> a is a prefix of key
                        if (pos > a->key->get_pref_len()) {
                                if (!with_data)
                                        lpfn = a;
                                else if (a->data)
                                        lpfn = a;
                        }

                        // select node to continue the search based on the
                        // first different bit between a and key
                        b = cmp < 0 ? a->left : a->right;

                        // we reached a dead end
                        if (b->index <= a->index)
                                break;

                        c = a;
                        a = b;
                }

                return lpfm ? lpfn : NULL;
        }

        data_type *lookup(netaddress &key, bool lpfm = true) {
                node *n = lookup_node(key, lpfm);

                return n ? n->data : NULL;
        }

        bool remove(netaddress &key) {
                node *n = lookup_node(key);

                if (n && n->data) {
                        delete n->data;
                        n->data = NULL;
                }

                return (n != 0);
        }

        bool remove_all(netaddress &key) {
                node *n = lookup_node(key, false, false);

                if (n == 0)
                        return false;

                if (n->data) {
                        delete n->data;
                        n->data = NULL;
                }

                if (n->left->index > n->index) {
                        delete n->left;
                        n->left = n;
                }
                if (n->right->index > n->index) {
                        delete n->right;
                        n->right = n;
                }

                return true;
        }

        void print() {
                cout << "v4_TREE: " << endl;
                print_node(v4head);
                cout << "v6_TREE: " << endl;
                print_node(v6head);
        }

        void print_node(node *x, bool decent = true) {
                if (x && x->key) {
                        cout << "node: " << x << " key: " <<  *x->key;
                        if (x->data != 0)
                                cout << " data: " << x->data;
                        else
                                cout << " data: NULL";
                        cout << " index: " << x->index << endl;
                        cout << "\tleft: " << x->left << " right: " << x->right << endl;
                        if (decent) {
                                if (x->left->index > x->index)
                                        print_node(x->left);
                                if (x->right->index > x->index)
                                        print_node(x->right);
                        }
                }
        }

private:
        struct node *v4head;
        struct node *v6head;
};


/*
 * AddressList
 */

class AddressList {
public:
        class AddrProperty {
                public:
                        AddrProperty(const char *name) {
                                pname = new string(name);
                        }
                        ~AddrProperty() {
                                delete pname;
                        };

                        string *pname;
        };

        // Default properties, N.B. Ignore will remove all other properties
        static AddrProperty *LocalAddr_P;
        static AddrProperty *ConfiguredAddr_P;

private:
        // This is special
        static AddrProperty *IgnoreAddr_P;
        static AddrProperty *AnyAddr_P;

public:
        struct ltstr {
                bool operator()(const char* s1, const char* s2) const
                { return strcmp(s1, s2) < 0; }
        };
        struct ltna {
                bool operator()(const netaddress &s1, const netaddress &s2)
                    const {
                        if (s1.is_ipv4() != s2.is_ipv4())
                                return (s1.is_ipv4());
                        int cmp, pos = 0;
                        cmp = s1.rdx_cmp(&s2, &pos);
                        return (cmp < 0);
                }

        };
        typedef set<char *, ltstr>      iflist_t;
        typedef set<netaddress, ltna>   addrlist_t;

        AddressList();
        ~AddressList();

        // Configure by interfaces
        // Return a list of all local interfaces, which are monitored
        iflist_t *get_interfaces();
        // Begin interface list (otherwise the following have no effect)
        // If start_empty is true use an empty list, otherwise add all
        // currently configured interfaces
        bool by_interface(bool start_empty = true);
        // Add interface to monitoring
        bool add_interface(char *name);
        // Remove interface from monitoring
        bool del_interface(char *name);

        // Manage properties
        // If 'all' is true operate on all matching addresses as well
        bool add_property(netaddress &na, AddrProperty *p = ConfiguredAddr_P,
            bool propagate = true);
        bool del_property(netaddress &na, AddrProperty *p = ConfiguredAddr_P,
            bool propagate = true);
        inline bool purge_properties(netaddress &na, bool prop = true) {
                return del_property(na, AnyAddr_P, prop);
        };
        bool add_host_prop(const char *name, AddrProperty *p = ConfiguredAddr_P);
        bool del_host_prop(const char *name, AddrProperty *p = ConfiguredAddr_P);
        inline bool purge_host_prop(const char *name) {
                return del_host_prop(name, AnyAddr_P);
        }

        // Special property
        bool ignore(netaddress &na, bool propagate = true);
        bool unignore(netaddress &na, bool propagate = true);
        bool ignore_bogons(void);
        bool ignore_locals(void);
        bool ignore_loopback(void);

        // Check if the given address has the given property
        bool addr_is(netaddress &na, AddrProperty *prop);
        bool addr_is(const hostaddress &ha, AddrProperty *prop) {
                netaddress na(ha);
                return addr_is(na, prop);
        }
        // Check if the given address is in a network with the given property
        bool addr_is_in(netaddress &na, AddrProperty *prop);
        bool addr_is_in(const hostaddress &ha, AddrProperty *prop) {
                netaddress na(ha);
                return addr_is_in(na, prop);
        }

        addrlist_t *get_addrs(AddrProperty *prop = LocalAddr_P);
        netaddress *get_first(AddrProperty *p = LocalAddr_P, bool IPv4 = true);

        netaddress *get_src_addr(const netaddress &dest, uint32_t *prefs);
private:
        typedef map<AddrProperty *, bool>       propmap_t;
        typedef RadixTrie<propmap_t>            addr2prop_t;

        iflist_t *interfaces;
        addr2prop_t prop_trie;

        // Backends for public functions
        void getifaddrs_iflist(iflist_t &list);
        bool getifaddrs_is_local(netaddress &na);
        void getifaddrs_get_addrs(addrlist_t &list);

        void bequeath(addr2prop_t::node *head, AddrProperty *p,
            bool add = true);
        void collect(addr2prop_t::node *head, AddrProperty *p,
            addrlist_t &list);
        addr2prop_t::node *collect_first(addr2prop_t::node *head,
            AddrProperty *p);
};

inline ostream &operator<<(ostream &out, const AddressList::AddrProperty &prop) {
        return out << *prop.pname;
}


/************************************* inline methods ***********************************/

inline
size_t
hostaddress::get_hash() const
{
        return (ipv6addr.s6_addr32[0] ^ ipv6addr.s6_addr32[1] ^ ipv6addr.s6_addr32[2] ^ ipv6addr.s6_addr32[3]);
} // end get_hash

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


/** Initialize a hostaddress object.
 * This calls virtual member set_subtype and therefore sets subtype in all
 * derived class which overwrite this member function correctly.
 */
inline
hostaddress::hostaddress()
        : address(IPv6HostAddress),
          ipv4flag(false),
          outstring(NULL)
{
  clear_ip();
  set_subtype(false);
} // end constructor hostaddress


/** Assign h to this object. */
inline
hostaddress&
hostaddress::operator=(const hostaddress& h) {
        address::operator=(h);
        this->set_ip(h);
        if (outstring)
          delete outstring;
        outstring= 0;
        return *this;
} // end operator=

/** Copy constructor for hostaddress objects */
inline
hostaddress::hostaddress(const hostaddress& h) :
  address(h),
  outstring(NULL)
{
  this->set_ip(h);

  //Log(DEBUG_LOG,LOG_NORMAL,"hostaddress","hostaddress constructor called for const hostaddress& h:"); // << h << " outstring:" << static_cast<void*>(outstring) << " h.outstring:" << static_cast<void*>(h.outstring));

} // end copy constructor hostaddress

/** Check if this is an IPv4 address. */
inline
bool
hostaddress::is_ipv4() const {
        return ipv4flag;
} // end is_ipv4

/** Check if this is an IPv6 address. */
inline
bool
hostaddress::is_ipv6() const {
        return (!ipv4flag);
} // end is_ipv6

/** Check if this is a 6to4 mapped address. */
inline
bool
hostaddress::is_mapped_ip() const
{
  return (ipv4flag) ? false : IN6_IS_ADDR_V4MAPPED(ipv6addr.s6_addr);
} // end is_mapped_ip

inline
bool
hostaddress::set_ip(const string& str) { return set_ip(str.c_str()); }

inline
/** Delete outstring if it exists. */
hostaddress::~hostaddress() {
        if (outstring)
        {
          delete[] outstring;
          outstring= 0;
        }
} // end destructor hostaddress

/** Set IPv4 or IPv6 from string or leave object unchanged.
 * This changes object type.
 * @return true on success.
 */
inline
bool
hostaddress::set_ip(const char *str)
{
  return (!str) ? false :
                 ( strchr(str,':') ? set_ipv6(str) : set_ipv4(str));    // which IP version?

} // end set_ipv


/** Lookup the host name associated with the current IP address. */
inline
string hostaddress::get_host_name(bool *res) const
{
  return  ipv4flag ? tsdb::get_hostname(ipv4addr,res) : tsdb::get_hostname(ipv6addr,res);
} // end get_host_name

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

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

inline
prefix_length_t netaddress::get_pref_len() const { return prefix_length; }

inline
size_t netaddress::get_hash() const {
        return (hostaddress::get_hash() ^ prefix_length);
} // end get_hash

inline
int
netaddress::match_against(const netaddress& na) const
{
        // compare prefix lengths
  return (prefix_length<na.prefix_length) ? -1 : hostaddress::match_against(na);
} // end match_against


inline
ostream &operator<<(ostream &out, const appladdress &addr) {
     if (addr.is_mapped_ip()) return out << "[IPv4-mapped address]: "  << addr.get_ip_str() << ":" << (int)addr.get_port() << ", " << addr.get_protocol_name();
    return out << "[IP address]: " << addr.get_ip_str() << ":" << (int)addr.get_port() << ", " << addr.get_protocol_name();
}

inline
ostream &operator<<(ostream &out, const udsaddress &addr) {
    if (addr.get_socknum()) return out << "[Socketnumber]: " << addr.get_socknum();
    return out << "[Unix Domain Socket]: " << addr.get_udssocket();
}






inline
size_t udsaddress::get_hash() const {
    size_t tmp2 = 1;
        for (unsigned int i = 0; i<uds_socket.size(); i++) {
            tmp2 = tmp2 * (int) uds_socket[i];
        }
        return (tmp2 ^ socknum);
} // end get_hash



} // end namespace protlib

/*********************************** hash functions ***********************************/

namespace __gnu_cxx {
/// hostaddress hasher
template <> struct hash<protlib::hostaddress> {
        inline size_t operator()(const protlib::hostaddress& addr) const { return addr.get_hash(); }
}; // end hostaddress hasher

/// appladdress hasher
template <> struct hash<protlib::appladdress> {
        inline size_t operator()(const protlib::appladdress& addr) const { return addr.get_hash(); }
}; // end appladdress hasher

/// udsaddress hasher
template <> struct hash<protlib::udsaddress> {
        inline size_t operator()(const protlib::udsaddress& addr) const { return addr.get_hash(); }
}; // end udsaddress hasher




/// netaddress hasher
template <> struct hash<protlib::netaddress> {
        inline size_t operator() (const protlib::netaddress& addr) const { return addr.get_hash(); }
}; // end netaddress hasher

} // end namespace __gnu_cxx


namespace std {

/// hostaddress equal_to
template <> struct equal_to<protlib::hostaddress> {
        inline bool operator()(const protlib::hostaddress& addr1, const protlib::hostaddress& addr2) const { return addr1.equiv(addr2); }
}; // end hostaddress equal_to

/// appladdress equal_to
template <> struct equal_to<protlib::appladdress> {
        inline bool operator()(const protlib::appladdress& addr1, const protlib::appladdress& addr2) const { return addr1.equiv(addr2); }
}; // end appladdress equal_to

/// netaddress equal_to
template <> struct equal_to<protlib::netaddress> {
        inline bool operator()(const protlib::netaddress& addr1, const protlib::netaddress& addr2) const { return addr1.equiv(addr2); }

}; // end netaddress equal_to

} // end namespace std
#endif // PROTLIB__ADDRESS_H