代码

#include "router.h"
#include <stdint.h>
#include <stdlib.h>
#include <arpa/inet.h>
#include <unordered_map>
#include <iostream>

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

const int M = 1000003;

RoutingTableEntry table[M];

inline void setLazy(uint32_t &x) { x |= 128; }
inline bool checkLazy(uint32_t x) { return ((x >> 7) & 1) == 1; }
inline void setValid(uint32_t &x) { x |= 256; }
inline bool checkValid(uint32_t x) { return (x >> 8) == 1; }

uint32_t getHash(uint32_t addr, uint32_t len) {
  uint32_t seed = 131;
  uint32_t hash = 0;
  for(uint32_t i = 0; i < 31; i ++) {
    hash = (hash * seed) + ((addr >> i) & 1) + ((len >> i) & 1);
    hash %= M;
  }
  return hash;
}

/**
 * @brief 插入/删除一条路由表表项
 * @param insert 如果要插入则为 true ，要删除则为 false
 * @param entry 要插入/删除的表项
 *
 * 插入时如果已经存在一条 addr 和 len 都相同的表项，则替换掉原有的。
 * 删除时按照 addr 和 len **精确** 匹配。
 */
void update(bool insert, RoutingTableEntry entry) {
  // TODO:
  entry.addr = ntohl(entry.addr);
  uint32_t pos = getHash(entry.addr, entry.len);
  if (insert) {
    while (checkValid(table[pos].len) && !checkLazy(table[pos].len) && (table[pos].addr != entry.addr || table[pos].len != entry.len)) 
      pos ++;
    table[pos] = entry;
    table[pos].len |= 256;
  }
  else {
    entry.len |= 256;
    while (checkValid(table[pos].len) && (checkLazy(table[pos].len) || table[pos].addr != entry.addr || table[pos].len != entry.len)) {
      // std::cout << "### " << table[pos].addr << " " << table[pos].len << std::endl;
      pos ++;
    }
    if (checkValid(table[pos].len)) {
      // std::cout << "before: " << table[pos].len << std::endl;
      table[pos].len |= 128;    
      // std::cout << "after : " << table[pos].len << std::endl;
    }
    // else {
      // std::cout << "??????" << std::endl;
    // }
  }
} 

/**
 * @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) {
  // TODO:
  *nexthop = 0;
  *if_index = 0;
  addr = ntohl(addr);
  uint32_t len = 32;
  while (true) {
    uint32_t mask = (len == 0) ? 0 : ~((1 << (32 - len)) - 1);
    uint32_t pos = getHash(addr & mask, len);
    // std::cout << "@@@ " << len << " " << table[pos].len << " " << checkValid(table[pos].len) << " " << checkLazy(table[pos].len) << std::endl;
    while (checkValid(table[pos].len) && (checkLazy(table[pos].len) || (table[pos].addr & mask) != (addr & mask))) {
      // std::cout << "*** " << table[pos].addr << " " << table[pos].len << std::endl;
      pos ++;
    }
    if (checkValid(table[pos].len)) {
      *nexthop = table[pos].nexthop;
      *if_index = table[pos].if_index;
      return true;
    }
    if (len == 0)
      break;
    len --;
  }
  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, tmp;
    if (prefix_query(addr, &res, &tmp)) {
        return res;
    } 
    else {
        return 0;
    }
}

评测结果