代码

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

struct TrieNode
{
  uint32_t next_hop;
  uint32_t child[2];
  uint32_t addr;
};

std::vector<TrieNode> trie_buffer(1);

inline bool isNodeValid(const TrieNode &n)
{
  return n.addr & 0x8000000;
}

inline void setNodeValid(TrieNode &n, bool valid)
{
  if (valid)
    n.addr |= 0x8000000;
  else
    n.addr &= 0x7fffffff;
}

inline void setNodeAddr(TrieNode &n, uint32_t addr)
{
  n.addr = (n.addr & 0x8000000) | addr;
}

inline uint32_t getNodeAddr(const TrieNode &n)
{
  return n.addr & 0x7fffffff;
}

inline void insert(const RoutingTableEntry &a)
{
  uint32_t addr = ntohl(a.addr);
  uint32_t curr = 0;
  for (uint32_t k = 0; k < a.len; ++k)
  {
    bool dir = (addr >> (31 - k)) & 1;
    if (!trie_buffer[curr].child[dir])
    {
      trie_buffer[curr].child[dir] = trie_buffer.size();
      trie_buffer.resize(trie_buffer.size() + 1);
    }
    curr = trie_buffer[curr].child[dir];
  }
  setNodeValid(trie_buffer[curr], true);
  trie_buffer[curr].next_hop = a.nexthop;
}

#define DUCK
#ifdef DUCK

const uint32_t MAX_SIZE = 827088;

void init(int n, int q, const RoutingTableEntry *a)
{
  trie_buffer.reserve(MAX_SIZE * 32);
  trie_buffer.resize(1);
  for (int i = 0; i < n; ++i)
  {
    insert(a[i]);
  }
}

unsigned query(unsigned addr)
{
  addr = ntohl(addr);
  uint32_t curr = 0, res = 0;
  for (int k = 0; k < 32; ++k)
  {
    bool dir = (addr >> (31 - k)) & 1;
    if (isNodeValid(trie_buffer[curr]))
      res = trie_buffer[curr].next_hop;
    if (trie_buffer[curr].child[dir])
    {
      curr = trie_buffer[curr].child[dir];
    }
    else
      break;
  }
  return res;
}

#else

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

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

/**
 * @brief 进行一次路由表的查询，按照最长前缀匹配原则
 * @param addr 需要查询的目标地址，大端序
 * @param nexthop 如果查询到目标，把表项的 nexthop 写入
 * @param if_index 如果查询到目标，把表项的 if_index 写入
 * @return 查到则返回 true ，没查到则返回 false
 */
bool query(uint32_t addr, uint32_t *nexthop, uint32_t *if_index)
{
  // TODO:
  *nexthop = 0;
  *if_index = 0;
  return false;
}

#endif

评测结果