代码

#include <arpa/inet.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <map>

#include "router.h"

/*
  RoutingTable Entry 的定义如下：
  typedef struct {
    uint32_t addr; // 大端序，IPv4 地址
    uint32_t len; // 小端序，前缀长度
    uint32_t if_index; // 小端序，出端口编号
    uint32_t nexthop; // 大端序，下一跳的 IPv4 地址
  } RoutingTableEntry;

  约定 addr 和 nexthop 以 **大端序** 存储。
  这意味着 1.2.3.4 对应 0x04030201 而不是 0x01020304。
  保证 addr 仅最低 len 位可能出现非零。
  当 nexthop 为零时这是一条直连路由。
  你可以在全局变量中把路由表以一定的数据结构格式保存下来。
*/

// (addr) -> (if_index || nexthop)
static std::map<uint32_t, uint32_t> route[33];

/**
 * @brief 插入/删除一条路由表表项
 * @param insert 如果要插入则为 true ，要删除则为 false
 * @param entry 要插入/删除的表项
 *
 * 插入时如果已经存在一条 addr 和 len 都相同的表项，则替换掉原有的。
 * 删除时按照 addr 和 len **精确** 匹配。
 */
void update(RoutingTableEntry entry) {
    uint32_t key = ntohl(entry.addr) & (0xffffffffL << (32 - entry.len));
    uint32_t idx = entry.len;
    uint32_t val = entry.nexthop;
    route[idx][key] = val;
}

/**
 * @brief 进行一次路由表的查询，按照最长前缀匹配原则
 * @param addr 需要查询的目标地址，大端序
 * @param nexthop 如果查询到目标，把表项的 nexthop 写入
 * @param if_index 如果查询到目标，把表项的 if_index 写入
 * @return 查到则返回 true ，没查到则返回 false
 */
bool prefix_query(uint32_t addr, uint32_t *nexthop) {
    addr = ntohl(addr);
    for (int i = 32; i >= 0; i--) {
        uint32_t key = i == 32 ? addr : addr & (0xffffffffL << (32 - i));
        if (!route[i].count(key)) {
            continue;
        }
        uint32_t val = route[i][key];
        *nexthop = val;
        return true;
    }
    *nexthop = 0;
    return false;
}

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

unsigned query(unsigned addr) {
    unsigned ret;
    prefix_query(addr, &ret);
    return ret;
}

/* using namespace std;

#define IPV4(a, b, c, d) ntohl(((a) << 24) + ((b) << 16) + ((c) << 8) + (d))

int main() {
    RoutingTableEntry a[3] = {{IPV4(128, 0, 0, 0), 2, 2, 4}, {IPV4(255, 0, 0, 0), 1, 2, 3}, {IPV4(1, 0, 0, 0), 0, 2, 6}};
    init(3, 0, a);
    cout << query(IPV4(0, 0, 0, 0)) << endl;
} */

评测结果