代码

#include "router.h"

#include <vector>

/*
  RoutingTable Entry 的定义如下：
typedef struct {
    unsigned addr;
    unsigned char len;
    char pad[3];  // Padding for memory alignment
    unsigned nexthop;
} __attribute__((packed)) RoutingTableEntry;

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

#define MASK(bit) ((uint64_t)(1ULL << (bit)) - 1ULL)

typedef struct {
  uint32_t begin, end;
  RoutingTableEntry entry;
} TableEntry;

std::vector<TableEntry> rt;

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

    TableEntry te {begin, end, entry};
    rt.push_back(te);
  } else {
    for(auto e = rt.begin(); e != rt.end(); e++) {
      if(e->begin == begin && e->end == end) {
        rt.erase(e);
        break;
      }
    }
  }
}

/**
 * @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 qa = __builtin_bswap32(addr);

  uint32_t maxlen = 0;
  for(auto e : rt) {
    if(qa >= e.begin && qa <= e.end) {
      if(e.entry.len > maxlen) {
        maxlen = e.entry.len;
        *nexthop = e.entry.nexthop;
      }
    }
  }

  return maxlen > 0 ? true : 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) {
	unsigned nexthop;
  bool ret = prefix_query(addr, &nexthop);

  return ret ? nexthop : 0;
}

评测结果