代码

#include "router.h"
#include <stdint.h>
#include <stdlib.h>

const int M = 128;

struct Entry {
  uint32_t addr; // 大端序，IPv4 地址
  uint32_t len = M; // 小端序，前缀长度
  uint32_t if_index; // 小端序，出端口编号
  uint32_t nexthop; // 大端序，下一跳的 IPv4 地址
};

const uint32_t Mo = 10137199;

uint32_t offset[] = {
  0x41a73af1, 0xacd90c2a, 0xb782dac8, 0x8ed809fe, 0x2f43044d, 0x98983c55, 0x128cdbe2, 0xd4b33747,
  0x39174111, 0xc3984954, 0x2e2f2b11, 0x962d8b05, 0x325866f5, 0x816b9dd6, 0x77889d07, 0x6499b492,
  0x0f485133, 0xee629441, 0x4cf30f0d, 0x50236ae5, 0xf85f3530, 0x22d1f6c8, 0xf5edc561, 0x680c154b,
  0x29025435, 0x80395081, 0x648425b8, 0x65141ba2, 0x339c66b4, 0xee5a9267, 0xac2a34ca, 0xdae51248, 0x41a73af1
};

Entry e[Mo];

uint32_t getKey(uint32_t addr, uint32_t len) {
  return (addr + offset[len]) % Mo;
}

uint32_t findPos(uint32_t addr, uint32_t len) {
  uint32_t p = getKey(addr, len);
  while (e[p].len < M && (e[p].addr != addr || (e[p].len & 63) != len)) {
    if ((++p) >= Mo) p -= Mo;
  }
  return p;
}

/**
 * @brief 插入/删除一条路由表表项
 * @param insert 如果要插入则为 true ，要删除则为 false
 * @param entry 要插入/删除的表项
 *
 * 插入时如果已经存在一条 addr 和 len 都相同的表项，则替换掉原有的。
 * 删除时按照 addr 和 len **精确** 匹配。
 */
void update(bool insert, RoutingTableEntry entry) {
  uint32_t p = findPos(entry.addr, entry.len);
  if (insert && e[p].len == M) {
    e[p].addr = entry.addr;
    e[p].len = entry.len;
    // e[p].if_index = entry.if_index;
    e[p].nexthop = entry.nexthop;
  } else if (e[p].len < M && (e[p].addr == entry.addr && (e[p].len & 63) == entry.len)) {
    if (insert) {
      e[p].len &= 63;
      // e[p].if_index = entry.if_index;
      e[p].nexthop = entry.nexthop;
    } else {
      e[p].len |= 64;
    }
  }
}

/**
 * @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) {
  uint32_t mask = ~0;
  for (int i = 32; i >= 0; mask -= 1u << (--i)) {
    uint32_t addr_m = (mask & addr), len = i;
    uint32_t p = findPos(addr_m, len);
    if (addr_m == e[p].addr && len == e[p].len) {
      *if_index = e[p].if_index;
      *nexthop = e[p].nexthop;
      return true;
    }
  }
  return false;
}

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;
    }
}

评测结果