代码

#include "router.h"
#include <cstdint>
#include <vector>
#include <netinet/in.h>

std::vector<RoutingTableEntry> table;

/**
 * @brief 插入/删除一条路由表表项
 * @param insert 如果要插入则为 true ，要删除则为 false
 * @param entry 要插入/删除的表项
 *
 * 插入时如果已经存在一条 addr 和 len 都相同的表项，则替换掉原有的。
 * 删除时按照 addr 和 len **精确** 匹配。
 */
void update(bool insert, RoutingTableEntry entry) {
    if (insert) {
        for (auto &e:table) {
            if (e.addr == entry.addr && e.len == entry.len) {
                e.nexthop = entry.nexthop;
                return;
            }
        }
        table.push_back(entry);
    } else {
        for (auto it = table.begin(); it != table.end(); ++it) {
            if (it->addr == entry.addr && it->len == entry.len) {
                table.erase(it);
                return;
            }
        }
    }
}

/**
 * @brief 进行一次路由表的查询，按照最长前缀匹配原则
 * @param addr 需要查询的目标地址，网络字节序
 * @param nexthop 如果查询到目标，把表项的 nexthop 写入
 * @return 查到则返回 true ，没查到则返回 false
 */
bool prefix_query(uint32_t addr, uint32_t *nexthop) {
    int max_len = -1;
    uint32_t addr_q = ntohl(addr);
    for (auto &e:table) {
        uint32_t addr_e = ntohl(e.addr);
        uint32_t addr_xor = addr_q ^addr_e;
        uint32_t mask = 0x80000000;
        int i;
        for (i = 0; i < e.len; ++i) {
            if (addr_xor & mask) {
                i = -1;
                break;
            }
            mask >>= 1;
        }
        if (i > max_len) {
            max_len = i;
            *nexthop = e.nexthop;
        }
    }
    return max_len > -1;
}


void init(int n, int q, const RoutingTableEntry *a) {
	for (int i = 0; i < n; ++i) {
            update(true, a[i]);
        }
}

unsigned query(unsigned addr) {
        unsigned nexthop;
        bool res = prefix_query(addr, &nexthop);
	return res && nexthop;
}

评测结果