代码

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

struct Node
{
  uint32_t addr;
  int len;
  uint32_t nexthop = -1;  // 大端序，下一跳的 IPv4 地址
  Node *lc = nullptr;
  Node *rc = nullptr;
  Node(uint32_t addr, int len)
  {
    this->addr = addr;
    this->len = len;
  }
  Node(RoutingTableEntry entry)
  {
    addr = entry.addr;
    len = entry.len;
    nexthop = entry.nexthop;
  }
  void set(RoutingTableEntry entry)
  {
    addr = entry.addr;
    len = entry.len;
    nexthop = entry.nexthop;
  }
};

struct DictTree
{
  Node *root = nullptr;
  int match(uint32_t addr, int len, Node *node)
  {
    if (node->len == 0)
    {
      return -1;
    }
    uint32_t result = addr ^ node->addr;
    int i;
    for (i = 0; i < node->len && i < len; ++i)
    {
      if (result & 1 << i)
      {
        return i;
      }
    }
    return i;
  }

  void insert(RoutingTableEntry entry)
  {
    if (!root)
    {
      root = new Node(0, 0);
      root->lc = new Node(entry);
      root->rc = new Node(0, 0);
      return;
    }
    Node *cur = root;
    while (1)
    {
      int lmatch = match(entry.addr, entry.len, root->lc);
      int rmatch = match(entry.addr, entry.len, root->rc);
      int match_len;
      if (lmatch > rmatch)
      {
        if (lmatch == 0) // fake rc
        {
          cur->rc->set(entry);
          return;
        }
        else
        {
          cur = cur->lc;
          match_len = lmatch;
        }
      }
      else
      {
        if (rmatch == 0) //fake lc
        {
          cur->lc->set(entry);
          return;
        }
        else
        {
          cur = cur->rc;
          match_len = rmatch;
        }
      }
      entry.addr = entry.addr >> match_len;
      entry.len -= match_len;
      if (!entry.len) //match over
      {
        if (match_len == cur->len) //exactly match
        {
          cur->nexthop = entry.nexthop;
          return;
        }
        split(cur, match_len, entry);
        return;
      }
      if (!cur->lc) //leaf node
      {
        split(cur, match_len, entry);
        return;
      }
    }
  }
  void split(Node *cur, int match_len, RoutingTableEntry entry)
  {
    uint32_t lc_addr = cur->addr >> match_len;
    int lc_len = cur->len - match_len;
    cur->lc = new Node(lc_addr, lc_len);

    cur->len = match_len;

    cur->rc = new Node(entry);

    if (lc_len > 0)
    {
      cur->if_index = -1;
      cur->nexthop = -1;
      cur->lc->nexthop = cur->nexthop;
    }
  }
  void remove(RoutingTableEntry entry)
  {
    Node *traget = query(entry.addr, entry.len, true);
    if (traget)
    {
      traget->nexthop = -1;
    }
  }
  Node *query(uint32_t addr, int len, bool is_strict)
  {
    if (!root)
      return nullptr;
    Node *cur = root;
    Node *result = nullptr;
    int match_len;
    while (1)
    {
      int lmatch = match(addr, len, cur->lc);
      int rmatch = match(addr, len, cur->rc);
      if (lmatch <= 0 && rmatch <= 0) //fake children
        return result;
      if (lmatch > rmatch)
      {
        cur = cur->lc;
        match_len = lmatch;
      }
      else
      {
        cur = cur->rc;
        match_len = rmatch;
      }
      addr = addr >> match_len;
      len -= match_len;
      if (match_len == cur->len && cur->nexthop != -1)
      {
        if (!is_strict)
          result = cur;
        else if (!len)
          result = cur;
      }
      if (!len || !cur->lc) //match over || leaf node
      {
        return result;
      }
    }
  }
};

/*
  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 **精确** 匹配。
 */
DictTree tree;
void update(bool insert, RoutingTableEntry entry)
{
  // TODO:
  if (insert)
    tree.insert(entry);
  else
    tree.remove(entry);
}

/**
 * @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:
  Node *target = tree.query(addr, 32, false);
  if (target && target->nexthop >= 0)
  {
    *nexthop = target->nexthop;
    return true;
  }
  *nexthop = 0;
  return false;
}

评测结果