代码

#include "router.h"
#include "memory.h"
#include <arpa/inet.h>

struct pp {pp* left, *right; unsigned refer;} pool[9999999]; int ppcnt=0;
struct { pp* gp; unsigned gres; void set(unsigned addr) {
	unsigned res=0;pp* p=pool;
	for (int i=0; i<16; ++i) {
		if(p->refer)res=p->refer;p=addr&0x8000?p->right:p->left;
addr<<=1;
}
	while(p);gres=res;gp=p;

}} *cache;
pp* insert(pp*& pos) {if(!pos)pos=pool+ ++ppcnt; return pos;}
pp& insert(int depth, unsigned pos) {pp* p=pool; for(int i=0; i<depth;++i) {
p=insert(pos&0x80000000?p->right:p->left), pos<<=1;
}
return *p;
}
void init(int n, int q, const RoutingTableEntry *a) {
	for(int i=0; i<n; ++i) insert(a[i].len,htonl(a[i].addr)).refer=a[i].nexthop;
cache = n<60000?malloc(655360):a;
for(int i=0; i<65536; ++i) a[i].set(i);
}

unsigned query(unsigned addr) {addr=htonl(addr);
	unsigned res=cache[addr>>16].gres;pp* p=cache[addr>>16].gp;
	do {
		if(p->refer)res=p->refer;p=addr&0x8000?p->right:p->left;
addr<<=1;
}
	while(p);return res;
}

评测结果