/*---------------------------------------------------------------------------*/
/* dns_cache.cpp                                                             */
/* copyright (c) innovaphone 2011                                            */
/* DNS caching                                                               */
/*---------------------------------------------------------------------------*/

#include <platform.h>
#include "common/ilib/str.h"
#include "sdk/common/interface/time.h"

#include "sdk/common/lib/dns_cache.h"

USING_NAMESPACE;

#define MAX_DNS_CACHE_ENTRIES  100

const char *DnsQueryTypeName(DnsQueryType qtype)
{
    switch (qtype) {
    case UNKNOWN_QTYPE:
        return("ANY");
    case QTYPE_A:
        return("A");
    case QTYPE_NS:
        return("NS");
    case QTYPE_CNAME:
        return("CNAME");
    case QTYPE_SOA:
        return("SOA");
    case QTYPE_PTR:
        return("PTR");
    case QTYPE_MX:
        return("MX");
    case QTYPE_TXT:
        return("TXT");
    case QTYPE_AAAA:
        return("AAAA");
    case QTYPE_SRV:
        return("SRV");
    case QTYPE_NAPTR:
        return("NAPTR");
    default:
        return("?");
    }
}

/*---------------------------------------------------------------------------*/
/* class DnsBtreeTTL                                                         */
/*---------------------------------------------------------------------------*/

class DnsBtreeTTL : public btree {
    int btree_compare(void * key);
    int btree_compare(class btree * b);
};

/*---------------------------------------------------------------------------*/
/* class DnsEntry                                                            */
/*---------------------------------------------------------------------------*/

class DnsEntry : public DnsBtreeTTL, public DnsCacheResult, public istd::listElement<DnsEntry>
{
public:
    class DnsBucket	    * parent;
    dword               ttlTimestamp;
    bool                isStatic;
    dword               lastUsedFlags;
    dword               unsuitableFlags;

    void Clear();
    void SetStatic(bool on);
    const char *qname();
    unsigned ttl();
    unsigned Print(char *buf, unsigned sz);

    DnsEntry(class DnsBucket * parent, DnsQueryType qtype, word rcode);
    virtual ~DnsEntry();
};

/*---------------------------------------------------------------------------*/
/* class DnsDB                                                               */
/*---------------------------------------------------------------------------*/

class DnsDB : public IDnsCache
{
    friend class DnsEntry;
    friend class DnsBucket;

    class btree     * nameBtree;
    class btree     * ttlBtree;
    int             entryCount;
    bool            ip6Unsuitable;

    void UpdateTTL(DnsEntry *e, dword ttl);
    DnsEntry *DeleteRelatedEntries(DnsEntry * e);
    void InvalidateBucket(DnsBucket * bk);
    void DeleteBucket(DnsBucket *bk);
    void DeleteEntry(DnsEntry *e);

public:
    DnsDB();
    virtual ~DnsDB();

    void Clear();
    DnsBucket * SearchBucketByName(const char * name);
    void UpdateA(const char * qname, dword ttl, word servicePort, word rcode, IPaddr addr);
    void UpdateAAAA(const char * qname, dword ttl, word servicePort, word rcode, IPaddr addr);
    void LastUsedAddr(const char * qname, IPaddr addr, word servicePort);
    bool UnsuitableAddr(const char * qname, IPaddr addr, word servicePort);
    void ClearUnsuitableAddrs(const char * qname, word servicePort);
    void InvalidateQname(const char * qname);
    void Invalidate();
    void ExpireEntries();
    word LookupA(const char * qname, word servicePort, DnsCacheResult ***answerRRs);
    word LookupAAAA(const char * qname, word servicePort, DnsCacheResult ***answerRRs);
    word Lookup(const char * qname, dword flags, word servicePort, const char * serviceName, DnsCacheResult **answerRRs);
    void SortResults(DnsCacheResult **results);
    void List(DnsCacheResult **answerRRs);
    void ListStatic(DnsCacheResult **answerRRs);
    void ClearStatic();
};

/*---------------------------------------------------------------------------*/
/* class DnsBtreeName                                                        */
/*---------------------------------------------------------------------------*/

class DnsBtreeName : public btree {
    int btree_compare(void * key);
    int btree_compare(class btree * b);
};

/*---------------------------------------------------------------------------*/
/* class DnsBucket                                                           */
/*---------------------------------------------------------------------------*/

class DnsBucket : public DnsBtreeName
{
public:
    DnsDB		* db;
    char		* fieldName;
    istd::list<DnsEntry> rrA;
    istd::list<DnsEntry> rrAAAA;
    word		servicePortTable[sizeof(dword)*8];
    unsigned int servicePortCount;

    DnsBucket(DnsDB *db, const char *name);
    virtual ~DnsBucket();
    void Clear();
    int GetServicePortPos(word servicePort);
    DnsEntry * UpdateA(dword ttl, word servicePort, word rcode, IPaddr addr);
    DnsEntry * UpdateAAAA(dword ttl, word servicePort, word rcode, IPaddr addr);
    word LookupA(word servicePort, DnsCacheResult ***answerRRs);
    word LookupAAAA(word servicePort, DnsCacheResult ***answerRRs);
    void List(DnsCacheResult ***answerRRs);
    void ListStatic(DnsCacheResult ***answerRRs);
    bool HasEntries() { return (!rrA.empty() || !rrAAAA.empty()); }
};

DnsBucket::DnsBucket(DnsDB *db, const char *name)
{
    this->db = db;
    this->fieldName = _strdup(name);
    servicePortCount = 0;
}

DnsBucket::~DnsBucket()
{
    free(fieldName);
    Clear();
}

void DnsBucket::Clear()
{
    while (!rrA.empty()) {
        db->DeleteEntry(rrA.front());
    }
    while (!rrAAAA.empty()) {
        db->DeleteEntry(rrAAAA.front());
    }
}

int DnsBucket::GetServicePortPos(word servicePort)
{
    DnsEntry *e;
    unsigned int i;

    i = 0;
    while ((i < servicePortCount) && (servicePortTable[i] != servicePort)) {
        i++;
    }
    if (i == servicePortCount) {
        if (servicePortCount < sizeof(dword)*8) {
            servicePortCount++;
        }
        else {
            memmove (servicePortTable, &(servicePortTable[1]), (sizeof(dword)*8 - 1) * sizeof(word));
            if (!rrA.empty()) {
                for (e = rrA.front(); e; e = e->goNext()) {
                    e->lastUsedFlags >>= 1;
                    e->unsuitableFlags >>= 1;
                }
            }
            if (!rrAAAA.empty()) {
                for (e = rrAAAA.front(); e; e = e->goNext()) {
                    e->lastUsedFlags >>= 1;
                    e->unsuitableFlags >>= 1;
                }
            }
            i--;
        }
        servicePortTable[i] = servicePort;
    }
    return i;
}

DnsEntry * DnsBucket::UpdateA(dword ttl, word servicePort, word rcode, IPaddr addr)
{
    DnsEntry *e;

    if (rrA.empty()) {
        e = NULL;
    }
    else {
        e = rrA.front();
        while (e && !IP_MATCH(addr, e->u.a.addr)) {
            e = e->goNext();
        }
    }
    if (!e) {
        e = new DnsEntry(this, QTYPE_A, rcode);
        e->u.a.addr = addr;
        rrA.push_back(e);
    }
    else {
        e->rcode = rcode;
    }
    return e;
}

DnsEntry * DnsBucket::UpdateAAAA(dword ttl, word servicePort, word rcode, IPaddr addr)
{
    DnsEntry *e;

    if (rrAAAA.empty()) {
        e = NULL;
    }
    else {
        e = rrAAAA.front();
        while (e && !IP_MATCH(addr, e->u.aaaa.addr)) {
            e = e->goNext();
        }
    }
    if (!e) {
        e = new DnsEntry(this, QTYPE_AAAA, rcode);
        e->u.aaaa.addr = addr;
        rrAAAA.push_back(e);
    }
    else {
        e->rcode = rcode;
    }
    return e;
}

void DnsBucket::List(DnsCacheResult ***answerRRs)
{
    DnsEntry *e;

    if (!rrA.empty()) {
        for (e = rrA.front(); e; e = e->goNext()) {
            **answerRRs = e;
            *answerRRs = &(e->resultNext);
        }
    }
    if (!rrAAAA.empty()) {
        for (e = rrAAAA.front(); e; e = e->goNext()) {
            **answerRRs = e;
            *answerRRs = &(e->resultNext);
        }
    }
}

void DnsBucket::ListStatic(DnsCacheResult ***answerRRs)
{
    DnsEntry *e;

    if (!rrA.empty()) {
        for (e = rrA.front(); e; e = e->goNext()) {
            if (e->isStatic) {
                **answerRRs = e;
                *answerRRs = &(e->resultNext);
            }
        }
    }
    if (!rrAAAA.empty()) {
        for (e = rrAAAA.front(); e; e = e->goNext()) {
            if (e->isStatic) {
                **answerRRs = e;
                *answerRRs = &(e->resultNext);
            }
        }
    }
}

word DnsBucket::LookupA(word servicePort, DnsCacheResult ***answerRRs)
{
    word rcode = DNS_RES_CACHE_MISS;
    DnsEntry *e;

    if (!rrA.empty()) {
        for (e = rrA.front(); e; e = e->goNext()) {
            if (!IP_ANYADDR(e->u.a.addr)) {
                **answerRRs = e;
                *answerRRs = &(e->resultNext);
                dword flag = ((dword) 1) << GetServicePortPos(servicePort);
                e->resultFlags =
                    ((e->lastUsedFlags & flag) ? DNS_CACHE_FLAG_LAST_USED : 0) |
                    ((e->unsuitableFlags & flag) ? DNS_CACHE_FLAG_UNSUITABLE : 0) |
                    (e->isStatic ? DNS_CACHE_FLAG_STATIC : 0);
            }
            if ((e->rcode != DNS_RES_CACHE_UNRELATED) && (rcode != DNS_RES_SUCCESS)) {
                rcode = e->rcode;
            }
        }
    }
    return (rcode);
}

word DnsBucket::LookupAAAA(word servicePort, DnsCacheResult ***answerRRs)
{
    word rcode = DNS_RES_CACHE_MISS;
    DnsEntry *e;

    if (!rrAAAA.empty()) {
        for (e = rrAAAA.front(); e; e = e->goNext()) {
            if (!IP_ANYADDR(e->u.aaaa.addr)) {
                **answerRRs = e;
                *answerRRs = &(e->resultNext);
                dword flag = ((dword) 1) << GetServicePortPos(servicePort);
                e->resultFlags =
                    ((e->lastUsedFlags & flag) ? DNS_CACHE_FLAG_LAST_USED : 0) |
                    ((e->unsuitableFlags & flag) ? DNS_CACHE_FLAG_UNSUITABLE : 0) |
                    (e->isStatic ? DNS_CACHE_FLAG_STATIC : 0);
            }
            if ((e->rcode != DNS_RES_CACHE_UNRELATED) && (rcode != DNS_RES_SUCCESS)) {
                rcode = e->rcode;
            }
        }
    }
    return (rcode);
}

/*---------------------------------------------------------------------------*/
/* class DnsBtreeName                                                        */
/*---------------------------------------------------------------------------*/

int DnsBtreeName::btree_compare(void * key)
{
    const char *e1 = (const char *)key;
    DnsBucket *e2 = (class DnsBucket *)(class DnsBtreeName *)this;
    return str::icmp(e1, e2->fieldName);
}

int DnsBtreeName::btree_compare(class btree * b)
{
    return (btree_compare(((class DnsBucket *)(class DnsBtreeName *)b)->fieldName));
}

/*---------------------------------------------------------------------------*/
/* class DnsCache                                                            */
/*---------------------------------------------------------------------------*/

IDnsCache * IDnsCache::Create()
{
    return new DnsDB();
}

IDnsCache::~IDnsCache()
{
}

/*---------------------------------------------------------------------------*/
/* class DnsEntry                                                            */
/*---------------------------------------------------------------------------*/

DnsEntry::DnsEntry(class DnsBucket *parent, DnsQueryType qtype, word rcode)
{
    this->parent = parent;
    this->qtype = qtype;
    this->rcode = rcode;
    isStatic = false;
    lastUsedFlags = 0;
    ttlTimestamp = 0;
    unsuitableFlags = 0;
    (parent->db->entryCount)++;
}

DnsEntry::~DnsEntry()
{
    if (!isStatic) {
        (parent->db->entryCount)--;
    }
    Clear();
}

void DnsEntry::Clear()
{
    memset(&u, 0, sizeof(u));
}

void DnsEntry::SetStatic(bool on)
{
    if(on ^ isStatic) {
        if(on) {
            (parent->db->entryCount)--;
        }
        else {
            (parent->db->entryCount)++;
        }
        isStatic = on;
    }
}

const char *DnsEntry::qname()
{
    return parent->fieldName;
}

unsigned DnsEntry::ttl()
{
    if (isStatic) return DNS_CACHE_TTL_PERSIST;
    int t = (int)(ttlTimestamp - ((dword)(ITime::TimeStampMilliseconds() / 1000)));
    return ((t > 0) ? t : 1);
}

unsigned DnsEntry::Print(char *buf, unsigned sz)
{
    unsigned i;

    i = 0;
    i += _snprintf(&buf[i], sz - i, "<rr");

    i += _snprintf(&buf[i], sz - i, " rr-type=\"%u\" rr-name=\"%s\"", qtype, DnsQueryTypeName(qtype));
    i += _snprintf(&buf[i], sz - i, " name=\"%s\"", qname());
    i += _snprintf(&buf[i], sz - i, " ttl=\"%u\"", ttl());
    switch (qtype) {
    case QTYPE_A:
        i += _snprintf(&buf[i], sz - i, " address=\"");
        i += str::from_ip(&buf[i], sz - i, &u.a.addr, false);
        i += _snprintf(&buf[i], sz - i, "\"");
        break;
    case QTYPE_AAAA:
        i += _snprintf(&buf[i], sz - i, " ip6address=\"");
        i += str::from_ip(&buf[i], sz - i, &u.aaaa.addr, false);
        i += _snprintf(&buf[i], sz - i, "\"");
        break;
    default:
        break;
    }
    i += _snprintf(&buf[i], sz - i, "/>");
    return i;
}

/*---------------------------------------------------------------------------*/
/* class DnsBtreeTTL                                                         */
/*---------------------------------------------------------------------------*/

int DnsBtreeTTL::btree_compare(void * key)
{
    DnsEntry *e1 = (class DnsEntry *)key;
    DnsEntry *e2 = (class DnsEntry *)(class DnsBtreeTTL *)this;
    if (e1->ttlTimestamp != e2->ttlTimestamp) return ((int)(e1->ttlTimestamp - e2->ttlTimestamp));
    return ((e1 < e2) ? -1 : ((e1 > e2) ? 1 : 0));
}

int DnsBtreeTTL::btree_compare(class btree * b)
{
    return (btree_compare((void *)(class DnsEntry *)(class DnsBtreeTTL *)b));
}

/*---------------------------------------------------------------------------*/
/* class DnsDB                                                               */
/*---------------------------------------------------------------------------*/

DnsDB::DnsDB()
{
    nameBtree = NULL;
    ttlBtree = NULL;
    entryCount = 0;
    ip6Unsuitable = false;
}

DnsDB::~DnsDB()
{
    Clear();
}

DnsEntry *DnsDB::DeleteRelatedEntries(DnsEntry * e)
{
    DnsEntry *d, *m, *n;
    DnsBucket * bk = e->parent;
    n = (class DnsEntry *)(class DnsBtreeTTL *)(ttlBtree->btree_find_next_left(e));
    if (!e->isStatic) {
        switch (e->qtype) {
        case QTYPE_A:
        case QTYPE_AAAA:
            d = bk->rrA.front();
            while (d) {
                m = d->goNext();
                if (!d->isStatic) {
                    if (n == d) {
                        n = (class DnsEntry *)(class DnsBtreeTTL *)(ttlBtree->btree_find_next_left(n));
                    }
                    DeleteEntry(d);
                }
                d = m;
            }
            d = bk->rrAAAA.front();
            while (d) {
                m = d->goNext();
                if (!d->isStatic) {
                    if (n == d) {
                        n = (class DnsEntry *)(class DnsBtreeTTL *)(ttlBtree->btree_find_next_left(n));
                    }
                    DeleteEntry(d);
                }
                d = m;
            }
            break;
        default:
            break;
        }
        if (!bk->HasEntries()) {
            DeleteBucket(bk);
        }
    }
    return n;
}

void DnsDB::ExpireEntries()
{
    dword ts = (dword)(ITime::TimeStampMilliseconds() / 1000);
    DnsEntry * e = (class DnsEntry *)(class DnsBtreeTTL *)(ttlBtree->btree_find_next_left(NULL));
    while (e && (((int)(ts - e->ttlTimestamp)) >= 0)) {
        e = DeleteRelatedEntries(e);
    }
}

void DnsDB::Clear()
{
    while (nameBtree) {
        DeleteBucket((class DnsBucket *)(class DnsBtreeName *)nameBtree);
    }
}

void DnsDB::InvalidateBucket(DnsBucket * bk)
{
    DnsEntry *e, *d;

    e = bk->rrA.front();
    while (e) {
        d = e;
        e = e->goNext();
        if (!d->isStatic) {
            DeleteEntry(d);
        }
    }
    e = bk->rrAAAA.front();
    while (e) {
        d = e;
        e = e->goNext();
        if (!d->isStatic) {
            DeleteEntry(d);
        }
    }
    if (!bk->HasEntries()) {
        DeleteBucket(bk);
    }
}

void DnsDB::InvalidateQname(const char * qname)
{
    DnsBucket * bk = SearchBucketByName(qname);
    if (bk) {
        InvalidateBucket(bk);
    }
}

void DnsDB::Invalidate()
{
    for (DnsBucket * bk = (class DnsBucket *)(class DnsBtreeName *)(nameBtree->btree_find_next_left(NULL));
        bk;
        bk = (class DnsBucket *)(class DnsBtreeName *)(nameBtree->btree_find_next_left(bk->fieldName))) {
        InvalidateBucket(bk);
    }
}

DnsBucket * DnsDB::SearchBucketByName(const char * name)
{
    return ((class DnsBucket *)(class DnsBtreeName *)(nameBtree->btree_find(name)));
}

void DnsDB::UpdateA(const char * qname, dword ttl, word servicePort, word rcode, IPaddr addr)
{
    DnsBucket * bk = SearchBucketByName(qname);
    if (!bk) {
        bk = new DnsBucket(this, qname);
        nameBtree = nameBtree->btree_put((class btree *)(class DnsBtreeName *)bk);
    }
    DnsEntry * e = bk->UpdateA(ttl, servicePort, rcode, addr);
    UpdateTTL(e, ttl);
}

void DnsDB::UpdateAAAA(const char * qname, dword ttl, word servicePort, word rcode, IPaddr addr)
{
    DnsBucket * bk = SearchBucketByName(qname);
    if (!bk) {
        bk = new DnsBucket(this, qname);
        nameBtree = nameBtree->btree_put((class btree *)(class DnsBtreeName *)bk);
    }
    DnsEntry * e = bk->UpdateAAAA(ttl, servicePort, rcode, addr);
    UpdateTTL(e, ttl);
}

void DnsDB::LastUsedAddr(const char * qname, IPaddr addr, word servicePort)
{
    DnsBucket * bk = SearchBucketByName(qname);
    if (bk) {
        dword flag = ((dword) 1) << bk->GetServicePortPos(servicePort);
        dword clear_flags = 0;
        DnsEntry *e;
        if (!bk->rrAAAA.empty()) {
            for (e = bk->rrAAAA.front(); e; e = e->goNext()) {
                if (ip_match(e->u.aaaa.addr, addr)) {
                    clear_flags = e->lastUsedFlags & flag;
                    e->lastUsedFlags |= flag;
                }
            }
        }
        if (!bk->rrA.empty()) {
            for (e = bk->rrA.front(); e; e = e->goNext()) {
                if (ip_match(e->u.a.addr, addr)) {
                    clear_flags = e->lastUsedFlags & flag;
                    e->lastUsedFlags |= flag;
                }
            }
        }
        if (clear_flags) {
            if (!bk->rrAAAA.empty()) {
                for (e = bk->rrAAAA.front(); e; e = e->goNext()) {
                    e->lastUsedFlags &= ~clear_flags;
                    if (ip_match(e->u.aaaa.addr, addr)) {
                        e->lastUsedFlags |= flag;
                    }
                }
            }
            if (!bk->rrA.empty()) {
                for (e = bk->rrA.front(); e; e = e->goNext()) {
                    e->lastUsedFlags &= ~clear_flags;
                    if (ip_match(e->u.a.addr, addr)) {
                        e->lastUsedFlags |= flag;
                    }
                }
            }
        }
    }
}

bool DnsDB::UnsuitableAddr(const char * qname, IPaddr addr, word servicePort)
{
    bool allUnsuitable = true;

    ip6Unsuitable = !is_ip4(addr);
    DnsBucket * bk = SearchBucketByName(qname);
    if (bk) {
        dword flag = ((dword) 1) << bk->GetServicePortPos(servicePort);
        DnsEntry *e;
        if (!bk->rrAAAA.empty()) {
            for (e = bk->rrAAAA.front(); e; e = e->goNext()) {
                if (ip_match(e->u.aaaa.addr, addr)) {
                    e->unsuitableFlags |= flag;
                }
                else if (!(e->unsuitableFlags & flag)) {
                    allUnsuitable = false;
                }
            }
        }
        if (!bk->rrA.empty()) {
            for (e = bk->rrA.front(); e; e = e->goNext()) {
                if (ip_match(e->u.a.addr, addr)) {
                    e->unsuitableFlags |= flag;
                }
                else if (!(e->unsuitableFlags & flag)) {
                    allUnsuitable = false;
                }
            }
        }
    }
    return allUnsuitable;
}

void DnsDB::ClearUnsuitableAddrs(const char * qname, word servicePort)
{
    DnsBucket * bk = SearchBucketByName(qname);
    if (bk) {
        dword flag = ((dword) 1) << bk->GetServicePortPos(servicePort);
        DnsEntry *e;
        if (!bk->rrAAAA.empty()) {
            for (e = bk->rrAAAA.front(); e; e = e->goNext()) {
                e->unsuitableFlags &= ~flag;
            }
        }
        if (!bk->rrA.empty()) {
            for (e = bk->rrA.front(); e; e = e->goNext()) {
                e->unsuitableFlags &= ~flag;
            }
        }
    }
}

word DnsDB::LookupA(const char * qname, word servicePort, DnsCacheResult ***answerRRs)
{
    DnsBucket * bk = SearchBucketByName(qname);
    return (bk ? bk->LookupA(servicePort, answerRRs) : DNS_RES_CACHE_MISS);
}

word DnsDB::LookupAAAA(const char * qname, word servicePort, DnsCacheResult ***answerRRs)
{
    DnsBucket * bk = SearchBucketByName(qname);
    return (bk ? bk->LookupAAAA(servicePort, answerRRs) : DNS_RES_CACHE_MISS);
}

word DnsDB::Lookup(const char * qname, dword flags, word servicePort, const char * serviceName, DnsCacheResult **answerRRs)
{
    DnsCacheResult *r, **append;
    DnsBucket * bk;
    word resA, resAAAA, res;

    ExpireEntries();
    bk = SearchBucketByName(qname);
    if (!bk) return DNS_RES_CACHE_MISS;
    append = answerRRs;
    resA = (flags & DNS_CACHE_LOOKUP_ONLY_IPV6) ? DNS_RES_CACHE_MISS : bk->LookupA(servicePort, &append);
    resAAAA = (flags & DNS_CACHE_LOOKUP_NO_IPV6) ? DNS_RES_CACHE_MISS : bk->LookupAAAA(servicePort, &append);
    *append = NULL;
    append = answerRRs;
    r = *answerRRs;
    while (r) {
        if (((r->qtype == QTYPE_AAAA) && !IP_ANYADDR(r->u.aaaa.addr))
         || ((r->qtype == QTYPE_A) && !IP_ANYADDR(r->u.a.addr) && !ip_4_match_anyaddr(r->u.a.addr))) {
            *append = r;
            append = &r->resultNext;
        }
        r = r->resultNext;
    }
    *append = NULL;
    if (*answerRRs) {
        SortResults(answerRRs);
        if ((flags & DNS_CACHE_LOOKUP_FLAG_ALL) || !((*answerRRs)->resultFlags & DNS_CACHE_FLAG_UNSUITABLE) || !(flags & DNS_CACHE_LOOKUP_ITERATE)) {
            if ((*answerRRs)->qtype == QTYPE_AAAA) {
                LastUsedAddr(qname, (*answerRRs)->u.aaaa.addr, servicePort);
            }
            else {
                LastUsedAddr(qname, (*answerRRs)->u.a.addr, servicePort);
            }
        }
        if ((*answerRRs)->resultFlags & DNS_CACHE_FLAG_UNSUITABLE) {
            ClearUnsuitableAddrs(qname, servicePort);
            InvalidateQname(qname);
            *answerRRs = NULL;
            resA = (flags & DNS_CACHE_LOOKUP_ITERATE) ? DNS_RES_NO_RESULT : DNS_RES_CACHE_MISS;
            resAAAA = resA;
        }
    }
    res = ((resA == DNS_RES_SUCCESS) || (resAAAA == DNS_RES_SUCCESS)) ? DNS_RES_SUCCESS : ((resA != DNS_RES_CACHE_MISS) ? resA : resAAAA);
    if ((res == DNS_RES_SUCCESS) && !*answerRRs) res = DNS_RES_NO_RESULT;
    return (res);
}

void DnsDB::UpdateTTL(DnsEntry *e, dword ttl)
{
    if (!e) return;
    if (ttlBtree->btree_find(e)) {
        ttlBtree = ttlBtree->btree_get(e);
    }
    e->SetStatic(ttl == DNS_CACHE_TTL_PERSIST);
    if (ttl == DNS_CACHE_TTL_PERSIST) {
        return;
    }
    e->ttlTimestamp = (dword)(ITime::TimeStampMilliseconds() / 1000) + MIN((DNS_CACHE_TTL_PERSIST >> 2), ttl); // quarter range ensures due detection
    ttlBtree = ttlBtree->btree_put(e);

    DnsEntry * d = (class DnsEntry *)(class DnsBtreeTTL *)(ttlBtree->btree_find_next_left(NULL));
    while (entryCount > MAX_DNS_CACHE_ENTRIES) {
        d = DeleteRelatedEntries(d);
    }
}

void DnsDB::DeleteBucket(DnsBucket *bk)
{
    nameBtree = nameBtree->btree_get((class btree *)(class DnsBtreeName *)bk);
    delete bk;
}

void DnsDB::DeleteEntry(DnsEntry *e)
{
    ttlBtree = ttlBtree->btree_get((class btree *)(class DnsBtreeTTL *)e);
    delete e;
}

struct AddrSelectionTable {
    IPaddr n, m;
    byte precedence, precedence4, label;
};

static struct AddrSelectionTable addrSelectionTable[] = /* rfc6724 */
{
    {
        {{0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01}}, /* ::1/128       */
        {{0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff}}, 50, 50,  0,
    },
    {
        {{0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0xff,0xff,0x00,0x00,0x00,0x00}}, /* ::ffff:0:0/96 */
        {{0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x00,0x00,0x00,0x00}}, 35, 60,  4,
    },
    {
        {{0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}}, /* ::/96         */
        {{0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x00,0x00,0x00,0x00}},  1,  1,  3,
    },
    {
        {{0x20,0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}}, /* 2001::/32     */
        {{0xff,0xff,0xff,0xff,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}},  5,  5,  5,
    },
    {
        {{0x20,0x02,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}}, /* 2002::/16     */
        {{0xff,0xff,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}}, 30, 30,  2,
    },
    {
        {{0x3f,0xfe,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}}, /* 3ffe::/16     */
        {{0xff,0xff,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}},  1,  1, 10,
    },
    {
        {{0xfe,0xc0,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}}, /* fec0::/10     */
        {{0xff,0xc0,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}},  1,  1, 11,
    },
    {
        {{0xfc,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}}, /* fc00::/7      */
        {{0xfe,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}},  3,  3, 13,
    },
    {
        {{0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}}, /* ::/0          */
        {{0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00}}, 40, 40,  1,
    },
};


void DnsDB::SortResults(DnsCacheResult **results)
{
    DnsCacheResult *p, **pp, **qq, **rr;
    byte precedence;
    unsigned i;

    p = *results;
    do {
        i = 0;
        if (p->qtype == QTYPE_A) {
            while (!IP_MATCH_MASK(p->u.a.addr, addrSelectionTable[i].n, addrSelectionTable[i].m)) {
                i++;
            }
        }
        else if (p->qtype == QTYPE_AAAA) {
            while (!IP_MATCH_MASK(p->u.aaaa.addr, addrSelectionTable[i].n, addrSelectionTable[i].m)) {
                i++;
            }
        }
        p->precedence = ((p->resultFlags & DNS_CACHE_FLAG_STATIC) ? 63 << 1 : addrSelectionTable[i].precedence4/*(ip6Unsuitable ? addrSelectionTable[i].precedence4 : addrSelectionTable[i].precedence)*/ << 1) |
            ((p->resultFlags & DNS_CACHE_FLAG_UNSUITABLE) ? 0 : 128) | ((p->resultFlags & DNS_CACHE_FLAG_LAST_USED) ? 0 : 1);
        p = p->resultNext;
    }
    while (p);
    p = *results;
    rr = results;
    do {
        pp = &p;
        precedence = p->precedence;
        qq = pp;
        pp = &(p->resultNext);
        while (*pp) {
            if ((*pp)->precedence > precedence) {
                precedence = (*pp)->precedence;
                qq = pp;
            }
            pp = &((*pp)->resultNext);
        }
        *rr = *qq;
        rr = &((*rr)->resultNext);
        *qq = *rr;
    }
    while (p);
    *rr = p;
}

void DnsDB::List(DnsCacheResult **answerRRs)
{
    DnsCacheResult **append;

    append = answerRRs;
    for (DnsBucket * bk = (class DnsBucket *)(class DnsBtreeName *)(nameBtree->btree_find_next_left(NULL));
        bk;
        bk = (class DnsBucket *)(class DnsBtreeName *)(nameBtree->btree_find_next_left(bk->fieldName))) {
        bk->List(&append);
    }
    *append = NULL;
}

void DnsDB::ListStatic(DnsCacheResult **answerRRs)
{
    DnsCacheResult **append;

    append = answerRRs;
    for (DnsBucket * bk = (class DnsBucket *)(class DnsBtreeName *)(nameBtree->btree_find_next_left(NULL));
        bk;
        bk = (class DnsBucket *)(class DnsBtreeName *)(nameBtree->btree_find_next_left(bk->fieldName))) {
        bk->ListStatic(&append);
    }
    *append = NULL;
}

void DnsDB::ClearStatic()
{
    DnsBucket *bk, *bkNext;
    DnsEntry *e, *eNext;

    bk = (class DnsBucket *)(class DnsBtreeName *)(nameBtree->btree_find_next_left(NULL));
    while (bk) {
        bkNext = (class DnsBucket *)(class DnsBtreeName *)(nameBtree->btree_find_next_left(bk->fieldName));
        e = bk->rrA.front();
        while (e) {
            eNext = e->goNext();
            if (e->isStatic) {
                DeleteEntry(e);
            }
            e = eNext;
        }
        e = bk->rrAAAA.front();
        while (e) {
            eNext = e->goNext();
            if (e->isStatic) {
                DeleteEntry(e);
            }
            e = eNext;
        }
        if (!bk->HasEntries()) {
            DeleteBucket(bk);
        }
        bk = bkNext;
    }
}

