代码

#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);
		int len = a[i].len;
		if(len<17){
	      int index = (addr >> (32-len));
	      for(list<RoutingTableEntry>::iterator it = small[index].begin();it!=small[index].end();++it){
	          if((*it).len == len){
	              small[index].erase(it);
	              break;
	          }
	      }
	      small[index].push_back(a[i]);
	    }
	    else{
	      int index = addr >> 16;
	      int r = (addr & 0xffff) >> (32 - len);
	      for(list<RoutingTableEntry>::iterator it = nodes[len-17].children[index].begin();it!=nodes[len-17].children[index].end();++it){
	          int taddr = (*it).addr;
	          if((len == ((*it).len & 0xff)) && ((taddr & 0xffff) >> (32-len)) == r){
	              nodes[len-17].children[index].erase(it);
	              break;
	          }
	      }
	      nodes[len-17].children[index].push_back(a[i]);
	    }
	} 
}

unsigned query(unsigned addr) {
  return 0;
}

评测结果