代码

#include "router.h"

#include <stdint.h>

struct RoutingTable
{
	bool isleaf;
	uint32_t if_index;
	uint32_t nexthop;
	RoutingTable *ch[2];
	RoutingTable()
	{
		isleaf=false;
		if_index=0;
		nexthop=0;
		ch[0]=nullptr;
		ch[1]=nullptr;
	}
	void insert(uint32_t depth,uint32_t adr,uint32_t len,uint32_t ifidx,uint32_t nxt)
	{
		if(depth+len==32)
		{
			isleaf=true;
			if_index=ifidx;
			nexthop=nxt;
			return;
		}
		if((adr&(1u<<(depth-1))))
		{
			if(ch[1]==nullptr)ch[1]=new RoutingTable();
			ch[1]->insert(depth-1,adr,len,ifidx,nxt);
		}
		else
		{
			if(ch[0]==nullptr)ch[0]=new RoutingTable();
			ch[0]->insert(depth-1,adr,len,ifidx,nxt);
		}
	}
	void erase(uint32_t depth,uint32_t adr,uint32_t len)
	{
		if(depth+len==32)
		{
			isleaf=false;
		}
		else
		{
			if((adr&(1u<<(depth-1))))
			{
				if(ch[1]==nullptr)return;
				ch[1]->erase(depth-1,adr,len);
				if(!(ch[1]->isleaf))
				{
					if((ch[1]->ch[0])==nullptr&&(ch[1]->ch[1])==nullptr)
					{
						delete ch[1];
						ch[1]=nullptr;
					}
				}
			}
			else
			{
				if(ch[0]==nullptr)return;
				ch[0]->erase(depth-1,adr,len);
				if(!(ch[0]->isleaf))
				{
					if((ch[0]->ch[0])==nullptr&&(ch[0]->ch[1])==nullptr)
					{
						delete ch[0];
						ch[0]=nullptr;
					}
				}
			}
		}
	}
	bool query(uint32_t depth,uint32_t adr,uint32_t *nxt,uint32_t *ifidx,bool bypass)
	{
		if(isleaf)
		{
			*nxt=nexthop;
			*ifidx=if_index;
			bypass=true;
		}
		if(depth==0)return bypass;
		if((adr&(1u<<(depth-1))))
		{
			if(ch[1]==nullptr)return bypass;
			return ch[1]->query(depth-1,adr,nxt,ifidx,bypass);
		}
		else
		{
			if(ch[0]==nullptr)return bypass;
			return ch[0]->query(depth-1,adr,nxt,ifidx,bypass);
		}
	}
}RtTb;


uint32_t changeEndian(uint32_t x)
{
	return ((x&(255u<<24))>>24)|((x&(255u<<16))>>8)|((x&(255u<<8))<<8)|((x&255u)<<24);
}

void init(int n, int q, const RoutingTableEntry *a) {
	for (int i=0;i<n;i++)
	{
		RtTb.insert(32,changeEndian(a[i].addr),a[i].len,0,a[i].nexthop);
	}
}

unsigned query(unsigned addr) {
	unsigned res=0,tmp=0;
	bool tmp2=RtTb.query(32,changeEndian(addr),&res,&tmp,false);
	return res;
}

评测结果