代码

#include "router.h"
#include <cstring>
#include <arpa/inet.h>

long long nexthop_trie1[34000000];
long long nexthop_trie8[18000000];
long long nodefr8to1[18000000];
long long *sub_trie[18000000];

unsigned Reverse(unsigned a)
{
    unsigned ret = 0;
    for (int cnt = 32; cnt > 0; a >>= 1, cnt--)
    {
        ret <<= 1;
        ret |= a&1;
    }
    return ret;
}

void init(int n, int q, const RoutingTableEntry *a) {
    memset(nexthop_trie1, -1, sizeof(nexthop_trie1));
    memset(nexthop_trie8, -1, sizeof(nexthop_trie8));
    for (int i = 0; i < n; i++)
    {
        if (a[i].len > 24)
        {
            unsigned addr = a[i].addr;
            int cnt = 0;
            for (int l = 24; l > 0; l -= 8)
            {
                cnt = cnt << 8 | (addr & 255);
                cnt++;
                addr >>= 8;
            }
            if (sub_trie[cnt] == NULL)
            {
                sub_trie[cnt] = new long long[540];
                memset(sub_trie[cnt], -1, sizeof(long long) * 540);
            }
            int sub_cnt = 1;
            for (int l = a[i].len - 24; l > 0; l--)
            {
                sub_cnt = sub_cnt << 1 | (addr & 1);
                addr >>= 1;
            }
            sub_trie[cnt][sub_cnt] = a[i].nexthop;
        }
        if (a[i].len <= 24)
        {
            if (a[i].len % 8 == 0)
            {
                unsigned addr = a[i].addr;
                int cnt = 0;
                for (int l = a[i].len; l > 0; l -= 8)
                {
                    cnt = cnt << 8 | (addr & 255);
                    cnt++;
                    addr >>= 8;
                }
                nexthop_trie8[cnt] = a[i].nexthop;
            }
            else
            {
                unsigned addr = Reverse(ntohl(a[i].addr));
                int cnt = 1;
                for (int l = a[i].len; l > 0; l--)
                {
                    cnt = cnt << 1 | (addr & 1);
                    addr >>= 1;
                }
                nexthop_trie1[cnt] = a[i].nexthop;
            }
        }
    }
}

unsigned query(unsigned addr_in) {
    unsigned addr = addr_in;
    unsigned ret = 0;
    int cnt = 0;
    int len = 0;
    if (nexthop_trie8[0] != -1)
        ret = nexthop_trie1[0];
    for (int l = 24; l > 0; l -= 8)
    {
        cnt = cnt << 8 | (addr & 255);
        addr >>= 8;
        if (nexthop_trie8[cnt] != -1)
        {
            ret = nexthop_trie8[cnt];
            len = 32 - l;
        }
    }
    if (len < 24)
    {
        cnt = 1;
        for (int l = 24; l > 0; l--)
        {
            cnt = cnt << 1 | (addr & 1);
            addr >>= 1;
            if (len < 24 - l + 1 && nexthop_trie[cnt] != -1)
            {
                ret = nexthop_trie[cnt];
                len = 24 - l + 1;
            }
        }
    }
    if (sub_trie[cnt] != NULL)
    {
        int sub_cnt = 1;
        for (int l = 8; l > 0; l--)
        {
            sub_cnt = sub_cnt << 1 | (addr & 1);
            addr >>= 1;
            if (sub_trie[cnt][sub_cnt] != -1)
                ret = sub_trie[cnt][sub_cnt];
        }
    }
    return ret;
}

评测结果