代码

#include "router.h"
#include <arpa/inet.h>
#include <list>
#include <iostream>
using namespace std;

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

node nodes[16]; //17-32./checksum < data/checksum_input1.pcap
list<RoutingTableEntry> small[65547]; //1-16

void init(int n, int q, const RoutingTableEntry *a) {
	for(int i=0;i<n;i++){
		int addr = ntohl(a[i].addr);
		if(a[i].len<17){
	      int index = (addr >> (32-a[i].len));
	      for(list<RoutingTableEntry>::iterator it = small[index].begin();it!=small[index].end();++it){
	          if((*it).len == a[i].len){
	              small[index].erase(it);
	              break;
	          }
	      }
	      small[index].push_back(a[i]);
	    }
	    else{
	      int index = addr >> 16;
	      int r = (addr & 0xffff) >> (32 -a[i].len);
	      for(list<RoutingTableEntry>::iterator it = nodes[a[i].len-17].children[index].begin();it!=nodes[a[i].len-17].children[index].end();++it){
	          int taddr = (*it).addr;
	          if((a[i].len == ((*it).len & 0xff)) && ((taddr & 0xffff) >> (32-a[i].len)) == r){
	              nodes[a[i].len-17].children[index].erase(it);
	              break;
	          }
	      }
	      nodes[a[i].len-17].children[index].push_back(a[i]);
	    }
	    if(i % 10000 == 0)
		cout << i << endl;
	} 
}

unsigned query(unsigned addr) {
  int o_addr = addr;
  addr = ntohl(addr);
  //addr = ((addr & 0xff) << 24) | ((addr & 0xff00) << 8) | ((addr & 0xff0000) >> 8) | ((addr & 0xff000000) >> 24);
  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){
        return (*it).nexthop;
      }
    }
  }
  int r = 0;
  for(int i=16;i>=1;i--){
    if(r==0)
      r = addr >> (32 - i);
    else if( r == (addr >> (32 - i)))
      continue;
    r = addr >> (32 - i);
    for(list<RoutingTableEntry>::iterator it = small[r].begin();it!=small[r].end();it++){
      if((*it).len == i)
      {
        return (*it).nexthop;
      }
    }
    
  }
  return 0;
}

评测结果