代码

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

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

struct rt_node
{
    const rt_entry *entry = nullptr;
    rt_node *prev = nullptr, *next[2] = { nullptr, nullptr };
    // 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 = ntohl(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->entry = e;
}

const rt_entry *rt_find(rt_node *root, uint32_t addr)
{
    rt_node *node = root;
    const rt_entry *e = nullptr;
    for (int l = 0; l < 32; ++l)
    {
        if (node->entry) e = node->entry;
        int i = (addr & 0x80000000) != 0;
        if (!node->next[i]) break;
        node = node->next[i];
        addr <<= 1;
    }
    return e;
    /*while (node)
    {
        if (node->entry) return node->entry;
        node = node->prev;
    }*/
    return nullptr;
}

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

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) {
    const rt_entry *e = rt_find(&r.root, ntohl(addr));
    if (e) return e->nexthop;
	return 0;
}

评测结果