代码

#include "router.h"
#include <stdlib.h>
#include <arpa/inet.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 为零时这是一条直连路由。
  你可以在全局变量中把路由表以一定的数据结构格式保存下来。
*/

typedef uint32_t node_index_t;

const int N = 1 << 25;

node_index_t ch[N][2];
node_index_t rec[N];
node_index_t used = 0, rec_cnt = 0;
bool valid[N];
uint32_t if_index[N];
uint32_t nexthop[N];

node_index_t tmp[32];

node_index_t new_node() {
  if (!rec_cnt) {
    return ++used;
  }
  return rec[--rec_cnt];
}

void del_node(node_index_t p) {
  if (p) rec[rec_cnt++] = p;
}

/**
 * @brief 插入/删除一条路由表表项
 * @param insert 如果要插入则为 true ，要删除则为 false
 * @param entry 要插入/删除的表项
 *
 * 插入时如果已经存在一条 addr 和 len 都相同的表项，则替换掉原有的。
 * 删除时按照 addr 和 len **精确** 匹配。
 */
void update(bool insert, RoutingTableEntry entry) {
  uint32_t addr = htonl(entry.addr), len = entry.len;
  node_index_t x = 0;

  for (int i = 0; i < len; ++i) {
    uint32_t c = (addr >> (i ^ 31)) & 1;
    if (!ch[x][c]) {
      if (!insert) return;
      ch[x][c] = new_node();
    }
    tmp[i] = x;
    x = ch[x][c];
  }

  if (insert) {
    valid[x] = true;
    // if_index[x] = entry.if_index;
    nexthop[x] = entry.nexthop;
  } else {
    valid[x] = false;
    if (ch[x][0] || ch[x][1]) return;
    del_node(x);
    for (int i = len - 1; i >= 0; --i) {
      node_index_t f = tmp[i];
      if (ch[f][0] == x) {
        ch[f][0] = 0;
        if (ch[f][1] || valid[f]) return;
      } else {
        ch[f][1] = 0;
        if (ch[f][0] || valid[f]) return;
      }
      x = f;
      del_node(x);
    }
  }
}

/**
 * @brief 进行一次路由表的查询，按照最长前缀匹配原则
 * @param addr 需要查询的目标地址，网络字节序
 * @param nexthop 如果查询到目标，把表项的 nexthop 写入
 * @param if_index 如果查询到目标，把表项的 if_index 写入
 * @return 查到则返回 true ，没查到则返回 false
 */
bool prefix_query(uint32_t addr, uint32_t *_nexthop, uint32_t *_if_index) {
  addr = htonl(addr);
  bool ok = false;
  node_index_t x = 0;
  if (valid[x]) {
      *_nexthop = nexthop[x];
      *_if_index = if_index[x];
      ok = true;
  }
  for (int i = 0; i < 32; ++i) {
    uint32_t c = (addr >> (i ^ 31)) & 1;
    if (!ch[x][c]) break;
    x = ch[x][c];
    if (valid[x]) {
      *_nexthop = nexthop[x];
      // *_if_index = if_index[x];
      ok = true;
    }
  }
  return ok;
}


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

unsigned query(unsigned addr) {
    uint32_t res, _;
    if (prefix_query(addr, &res, &_)) {
        return res;
    } else {
        return 0;
    }
}

评测结果