代码

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

//binary tree
struct node{
	//RoutingTableEntry* entry;
	bool hasentry;
	int pos;
	// static RoutingTableEntry* q_ans;
	uint32_t ntaddr;
	uint32_t nif_index;
	uint32_t nnexthop;
	node* child[2];
	static bool hasfound;
	static uint32_t len; //局部变量无法使用指针..
	static uint32_t if_index;
	static uint32_t nexthop;

	node(int p){
		hasentry = false;
		pos = p;
		//printf("%d\n",p);
		//printf("%d\n",pos);
		child[1] = NULL;
		child[2] = NULL;
	}

	~node(){

	}

	void insert(int p,RoutingTableEntry*& e){
		//printf("%d %d\n",e->len,this->pos);
		if(this->pos == e->len){ 
			//printf("%d\n",this->pos);
			this->ntaddr = e->addr;
			this->nif_index = e->if_index;
			this->nnexthop = e->nexthop;
      		this->hasentry = true;
			return;
		}
		if(p > 32){
			return;
		}
		else{
			if(e->addr & (0x80000000 >> p)){
				if(child[1] == NULL){
					child[1] = new node(p+1);
					//printf("%d\n",child[1]->hasentry);
					// printf("%s\n","???");
					// child[1] -> pos = p+1;
					//printf("%d\n",child[1]->pos);
				}
				child[1]->insert(p+1,e);
			}
			else{
				if(child[0] == NULL){
					child[0] = new node(p+1);
					// child[1] -> pos = p+1;
				}
				child[0]->insert(p+1,e);
			}
		}
	}

	bool del(int p,RoutingTableEntry*& entry){
		return false;
	}

	void query(int pos,uint32_t addr){
		if(this->hasentry){
			node::hasfound = true;
			node::if_index = this->nif_index;
			node::len = pos;
			node::metric = this->nmetric;
			node::nexthop = this->nnexthop;
    	}
   		 unsigned a = addr & (0x80000000 >> pos);
		if(pos > 32){
			return;
    	}
		else{
			if(a && child[1]){
				child[1]->query(pos+1,addr);

      		}
			else if( a == 0 && child[0]){
				child[0]->query(pos+1,addr);
      		}
		}	
	}
};

bool node::hasfound = false;
node* root = new node(0);
uint32_t node::len = 0;
uint32_t node::if_index = 0;
uint32_t node::nexthop = 0;

/**
 * @brief 插入/删除一条路由表表项
 * @param insert 如果要插入则为 true ，要删除则为 false
 * @param entry 要插入/删除的表项
 *
 * 插入时如果已经存在一条 addr 和 len 都相同的表项，则替换掉原有的。this
	// TODO:
  */
 void update(bool insert,RoutingTableEntry entry){
	unsigned addr = ntohl(entry.addr);
	RoutingTableEntry* tt = new RoutingTableEntry();
	tt->addr = addr;
	tt->len = entry.len;
	tt->if_index = entry.if_index;
	tt->nexthop = entry.nexthop;

	//int addr = ((entry.addr & 0xff) << 24) | ((entry.addr & 0xff00) << 8) | ((entry.addr & 0xff0000) >> 8) | ((entry.addr&0xff000000) >> 24);
	//printf("%x\n",addr);
	if (insert) {

      root -> insert(0,tt);
	}
  	else{
      root -> del(0,tt);
  	}
}

/**
 * @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,uint32_t* metric,uint32_t* len) {
	// TODO:q_ans
	*nexthop = 0;
  	*if_index = 0;
	*metric = 0;
	*len = 0;
	addr = ntohl(addr);
  	//node::q_ans = NULL;
	node::hasfound = false;
  	root->query(0,addr);
  	if(node::hasfound)
  	{
		*metric = node::metric;
    	*nexthop = node::nexthop;
    	*if_index = node::if_index;
		*len = node::len;
    	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) {
	node::hasfound = false;
	addr = htonl(addr);
	root->query(0,addr);
	if (node::hasfound)
		return node::nexthop;
	return 0;
}

评测结果