代码

#define DUCK 1

#ifdef DUCK
#include "router.h"
#endif

#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <cstddef>
#include <cstring>
#include <arpa/inet.h>

#ifdef DUCK
#define DUCK_HTONL(x) htonl(x)
#else
#define DUCK_HTONL(x) (x)
#endif

struct rt_entry
{
    uint32_t net;
    uint32_t prefixlen;
    uint32_t nexthop;
};

struct rt_node
{
    rt_node *prev = nullptr, *next[2] = { nullptr, nullptr };
    uint32_t nexthop = 0;
    uint32_t reserved = 0;
    // uint8_t prefixlen;
};

struct rt
{
    rt_node root;
};

void rt_insert(rt_node *root, const rt_entry *e)
{
    rt_node *node = root;
    uint32_t net = DUCK_HTONL(e->net);
    for (int l = 0; l < e->prefixlen; ++l)
    {
        int i = (net & 0x80000000) != 0;
        if (!node->next[i])
        {
            node->next[i] = new rt_node();
            node->next[i]->prev = node;
        }
        node = node->next[i];
        net <<= 1;
    }
    node->nexthop = e->nexthop;
}

uint32_t rt_find(const rt_node *root, uint32_t addr)
{
    const rt_node *node = root;
    const rt_node *node_with_entry = root;
    for (int l = 0; l < 32; ++l)
    {
        if (node->nexthop) node_with_entry = node;
        int i = (addr & 0x80000000) != 0;
        if (!node->next[i]) break;
        node = node->next[i];
        addr <<= 1;
    }
    return node_with_entry->nexthop;
}

void print_ipv4(uint32_t addr)
{
    addr = htonl(addr);
    char str[INET6_ADDRSTRLEN];
    inet_ntop(AF_INET, &addr, str, sizeof(str));
    printf("%s", str);
}

#ifdef DUCK
rt r;

void init(int n, int q, const RoutingTableEntry *a) {
    for (size_t i = 0; i < n; ++i)
    {
        rt_insert(&r.root, (const rt_entry *)&a[i]);
    }
}

unsigned query(unsigned addr) {
    return rt_find(&r.root, htonl(addr));
}
#else
int main()
{
    FILE *f = fopen("rt.bin", "rb");
    fseek(f, 0, SEEK_END);
    size_t size = ftell(f) / sizeof(rt_entry);
    fseek(f, 0, SEEK_SET);
    rt_entry *entries = new rt_entry[size];
    fread(entries, sizeof(rt_entry), size, f);
    fclose(f);
    rt rt;
    for (size_t i = 0; i < size; ++i)
    {
        rt_insert(&rt.root, &entries[i]);
    }
    while (true)
    {
        printf("> ");
        char ip[100];
        fgets(ip, sizeof(ip), stdin);
        char &c = ip[strlen(ip) - 1];
        if (c == '\n')
        {
            c = 0;
        }
        //printf("%s\n", ip);
        uint32_t addr;
        inet_pton(AF_INET, ip, &addr);
        addr = ntohl(addr);
        //printf("%08x\n", addr);
        uint32_t nexthop = rt_find(&rt.root, addr);
        printf("Next hop is ");
        print_ipv4(nexthop);
        printf("\n");
    }
    return 0;
}
#endif

评测结果