代码

#include "router.h"
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <arpa/inet.h>
#include <list>
using namespace std;
/*
  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 为零时这是一条直连路由。
  你可以在全局变量中把路由表以一定的数据结构格式保存下来。
*/

//tenary trie

//hash
struct node{
  list<RoutingTableEntry> children[65537];
  node(){}
};

node nodes[16]; //17-32./checksum < data/checksum_input1.pcap
list<RoutingTableEntry> small[65547]; //1-16
/**
 * @brief 插入/删除一条路由表表项
 * @param insert 如果要插入则为 true ，要删除则为 false
 * @param entry 要插入/删除的表项
 *
 * 插入时如果已经存在一条 addr 和 len 都相同的表项，则替换掉原有的。
 * 删除时按照 addr 和 len **精确** 匹配。
 */
void update(bool insert, RoutingTableEntry entry) {
  // TODO:
  unsigned addr = ntohl(entry.addr);
  //int addr = ((entry.addr & 0xff) << 24) | ((entry.addr & 0xff00) << 8) | ((entry.addr & 0xff0000) >> 8) | ((entry.addr&0xff000000) >> 24);
  //printf("%x\n",addr);
  if(insert){
    if(entry.len<17){
      int index = (addr >> (32-entry.len));
      for(list<RoutingTableEntry>::iterator it = small[index].begin();it!=small[index].end();++it){
          if((*it).len == entry.len){
              small[index].erase(it);
              break;
          }
      }
      small[index].push_back(entry);
    }
    else{
      int index = addr >> 16;
      int r = (addr & 0xffff) >> (32 -entry.len);
      for(list<RoutingTableEntry>::iterator it = nodes[entry.len-17].children[index].begin();it!=nodes[entry.len-17].children[index].end();++it){
          int taddr = (*it).addr;
          if(((taddr & 0xffff) >> (32-entry.len)) == r){
              nodes[entry.len-17].children[index].erase(it);
              break;
          }
      }
      nodes[entry.len-17].children[index].push_back(entry);
    }
  }
  else{
    if(entry.len<17){
      int index = (addr >> (32-entry.len));
      for(list<RoutingTableEntry>::iterator it = small[index].begin();it!=small[index].end();++it){
          if((*it).len == entry.len && (*it).addr == entry.addr){
              small[index].erase(it);
              break;
          }
      }      
    }
    else{
      int index = addr >> 16;
      int r = (addr & 0xffff) >> (32 -entry.len);
      for(list<RoutingTableEntry>::iterator it = nodes[entry.len-17].children[index].begin();it!=nodes[entry.len-17].children[index].end();++it){
          if((*it).addr == entry.addr){
              nodes[entry.len-17].children[index].erase(it);
              break;
          }
      }      
    }
  }
}

/**
 * @brief 进行一次路由表的查询，按照最长前缀匹配原则
 * @param addr 需要查询的目标地址，大端序
 * @param nexthop 如果查询到目标，把表项的 nexthop 写入
 * @param if_index 如果查询到目标，把表项的 if_index 写入
 * @return 查到则返回 true ，没查到则返回 false
 */
bool prefix_query(uint32_t addr, uint32_t *nexthop) {
  // TODO:
  *nexthop = 0;
  addr = ntohl(addr);
  int prefix = addr >> 16;
  int suffix = addr & 0xffff;
  for(int i=32;i>16;i--){
    int r = suffix >> (32 - i);
    //printf("%x\n",r);
    for(list<RoutingTableEntry>::iterator it = nodes[i-17].children[prefix].begin(); it != nodes[i-17].children[prefix].end();it++){
      //printf("%x\n",(*it).addr);
      int taddr = ntohl((*it).addr);
      if(((taddr & 0xffff) >> (32 - i)) == r){
        *nexthop = (*it).nexthop;
        return true;
      }
    }
  }
  int r=0;
  for(int i=16;i>=1;i--){
    r = addr >> (32 - i);
    for(list<RoutingTableEntry>::iterator it = small[r].begin();it!=small[r].end();it++){
      if((*it).len == i)
      {
        *nexthop = (*it).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 nexthop = 0;
  if(prefix_query(addr, &nexthop))
      return nexthop;
	return 0;
}

评测结果