#include "router.h"
#include <stdint.h>
#include <stdlib.h>
#include <array>
//#include <arpa/inet.h>
//#typedef unsigned int uint32_t
uint32_t htonl(uint32_t original){
uint32_t segments[4] = {((original>>24)&0xff),((original>>16)&0xff),((original>>8)&0xff),(original&0xff)};
uint32_t result = ((segments[3]<<24)|(segments[2]<<16)|(segments[1]<<8)|(segments[0]));
return result;
}
class IPinfo{
public:
RoutingTableEntry info;
IPinfo* nextIPinfo;
IPinfo(RoutingTableEntry entry){
info.addr = entry.addr;
info.len = entry.len;
//info.if_index = entry.if_index;
info.nexthop = entry.nexthop;
nextIPinfo = nullptr;
}
};
class TrieNode{
public:
TrieNode* sons[256];
IPinfo* info;// the pointer to the start IPinfo
uint8_t height; // if height==4 then hasInfo must be true
uint32_t len;
TrieNode(uint8_t _height, uint32_t _len){
for(int i = 0; i < 256; i++)
sons[i] = nullptr;
height = _height;
len = _len;
info = nullptr;
}
void addIPinfo(RoutingTableEntry entry){
IPinfo* cursorIPinfo = this->info;
// currentNode is the only node that need a new IPinfo
if(cursorIPinfo == nullptr){
// add the very first IPinfo node for this trieNode
this->info = new IPinfo(entry);
}
else{
uint32_t mask = (entry.len) ? (0xffffffff << (32-entry.len)) : 0x0;
// travle along the link to find the end
while(true){
if((cursorIPinfo->info.len==entry.len) && ((htonl(cursorIPinfo->info.addr)&mask)==(htonl(entry.addr)&mask))){
// replace the old one
cursorIPinfo->info.addr = entry.addr;
cursorIPinfo->info.len = entry.len;
//cursorIPinfo->info.if_index = entry.if_index;
cursorIPinfo->info.nexthop = entry.nexthop;
break;
}
else if(cursorIPinfo->nextIPinfo != nullptr){
// up till now, the new IPinfo can not cover any original one
cursorIPinfo = cursorIPinfo->nextIPinfo;
}
else{
//end of the already existed IPinfo, need to append a new one at the end
cursorIPinfo->nextIPinfo = new IPinfo(entry);
break;
}
}
}
}
void removeIPinfo(RoutingTableEntry entry){
IPinfo* newIPinfo = new IPinfo(entry);
IPinfo* cursorIPinfo = this->info;
if(cursorIPinfo == nullptr){
//printf("error in deleting a non-exist IPinfo of a node\n");
}
else{
uint32_t mask = (entry.len) ? (0xffffffff << (32-entry.len)) : 0x0;
while(true){
if((cursorIPinfo->info.len==entry.len) && ((htonl(cursorIPinfo->info.addr)&mask)==(htonl(entry.addr)&mask))){
// "cursorIPinfo" match and need to remove this IPinfo
IPinfo* cursorForFind = this->info;
if(cursorForFind == cursorIPinfo)
this->info = cursorIPinfo->nextIPinfo;
else{
while(cursorForFind != nullptr && cursorForFind->nextIPinfo != cursorIPinfo)
cursorForFind = cursorForFind->nextIPinfo;
if(cursorForFind != nullptr && cursorForFind->nextIPinfo == cursorIPinfo){
// end with finding the node to delete
cursorForFind->nextIPinfo = cursorIPinfo->nextIPinfo;
delete cursorIPinfo;
}
}
break;
}
else if(cursorIPinfo->nextIPinfo != nullptr){
// up till now, not match
cursorIPinfo = cursorIPinfo->nextIPinfo;
}
else{
// no one match the one to remove
//printf("error in deleting a non-exist IPinfo of a node\n");
break;
}
}
}
}
bool getPossibleIPinfo(uint32_t addr, uint32_t *nexthop, uint32_t *if_index){
IPinfo* currentIPinfo = this->info;
uint32_t max_len = 0;
bool result = false;
// if hit then renew the max_len and nexthop and if_index, else leave as it were
while(currentIPinfo != nullptr){
//printf("in TrieNode.getPossibleIPinfo, currentIPinfo = %d,%d; addr=%d\n",currentIPinfo->info.addr,currentIPinfo->info.len,addr);
uint32_t mask = (currentIPinfo->info.len) ? (0xffffffff << (32-currentIPinfo->info.len)) : 0x0;
//printf("%d,%d,%d\n",(currentIPinfo->info.len > max_len),(htonl(currentIPinfo->info.addr)&mask),(htonl(addr)&mask));
if((currentIPinfo->info.len >= max_len) && ((htonl(currentIPinfo->info.addr)&mask)==(htonl(addr)&mask))){
// addr match the curret IPinfo with a longger len
max_len = currentIPinfo->info.len;
*nexthop = currentIPinfo->info.nexthop;
//*if_index = currentIPinfo->info.if_index;
result = true;
}
// next IPinfo
currentIPinfo = currentIPinfo->nextIPinfo;
}
return result;
}
};
class RouterTrie{
public:
TrieNode* root;
RouterTrie(){
root = new TrieNode(0,0);
}
void insert(RoutingTableEntry entry){
uint32_t IP = htonl(entry.addr);
uint32_t mask = (entry.len) ? (0xffffffff << (32-entry.len)) : 0x0;
uint8_t masks[4] = {(uint8_t)((mask>>24)&0xff),(uint8_t)((mask>>16)&0xff),(uint8_t)((mask>>8)&0xff),(uint8_t)(mask&0xff)};
//printf("insert mask = %d,%d,%d,%d\n",masks[0],masks[1],masks[2],masks[3]);
TrieNode * currentNode = root;
for(int i = 0; i < 4; i++){
if(masks[i]==0xff){
//printf("insert layer i=%d with masks[i]==0xff with ", i);
// only one node on this layer need to be marked/created
uint8_t IPindex = (IP>>(8*(3-i)))&0xff; // the index of the hotNode
// uint8_t q = IPindex / 64, r = IPindex % 64; // see if the
//printf("IPindex = %d\n", IPindex);
if(currentNode->sons[IPindex]==nullptr)
currentNode->sons[IPindex] = new TrieNode(currentNode->height+1,entry.len);
currentNode = currentNode->sons[IPindex];
}
else {
// no need to create more node for trie tree
//printf("masks[%d]=%d\n",i,masks[i]);
currentNode->addIPinfo(entry);
break;
}
}
if(entry.len == 32)
currentNode->addIPinfo(entry);
}
void remove(RoutingTableEntry entry){
uint32_t IP = htonl(entry.addr);
uint32_t mask = (entry.len) ? (0xffffffff << (32-entry.len)) : 0x0;
uint8_t masks[4] = {(uint8_t)((mask>>24)&0xff),(uint8_t)((mask>>16)&0xff),(uint8_t)((mask>>8)&0xff),(uint8_t)(mask&0xff)};
TrieNode * currentNode = root;
for(int i = 0; i < 4; i++){
if(masks[i]==0xff){
// only one node on this layer need to be marked/created
uint8_t IPindex = (IP>>(8*(3-i)))&0xff; // the index of the hotNode
// uint8_t q = IPindex / 64, r = IPindex % 64; // see if the
if(currentNode->sons[IPindex]==nullptr){
//printf("error in deleting a non-exist node\n");
return;
}
currentNode = currentNode->sons[IPindex];
}
else{
// the nodes end, no need to create more node for trie tree
currentNode->removeIPinfo(entry);
break;
}
}
if(entry.len == 32)
currentNode->removeIPinfo(entry);
}
bool find(uint32_t addr, uint32_t *nexthop, uint32_t *if_index){
uint32_t IP = htonl(addr);
TrieNode * currentNode = root;
bool hit = false; // hit <= find a IP that match
for(int i = 0; i < 4; i++){
uint8_t IPindex = (IP>>(8*(3-i)))&0xff;
//record the current one
bool node_hit = currentNode->getPossibleIPinfo(addr,nexthop,if_index);
if(!hit)
hit = node_hit;
// get a step further
if(currentNode->sons[IPindex]!=nullptr){
currentNode = currentNode->sons[IPindex];
}
else{
break;
}
}
if(currentNode->height == 4){
//printf("in find, currentNode.height==4, currentNode->info=%d\n",currentNode->info);
bool node_hit = currentNode->getPossibleIPinfo(addr,nexthop,if_index);
if(!hit)
hit = node_hit;
}
return hit;
}
};
// the router table for look up
RouterTrie* RouterTable = new RouterTrie();
/**
* @brief 插入/删除一条路由表表项
* @param insert 如果要插入则为 true ，要删除则为 false
* @param entry 要插入/删除的表项
*
* 插入时如果已经存在一条 addr 和 len 都相同的表项，则替换掉原有的。
* 删除时按照 addr 和 len **精确** 匹配。
*/
void update(bool insert, RoutingTableEntry entry) {
if(insert){
//insert
RouterTable->insert(entry);
}
else{
//delete
RouterTable->remove(entry);
}
}
/**
* @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) {
*nexthop = 0;
*if_index = 0;
return RouterTable->find(addr,nexthop,if_index);
}
unsigned query(unsigned addr){
uint32_t nexthop = 0x0, if_index = 0x0;
RouterTable->find(addr,&nexthop,&if_index);
return nexthop;
}
void init(int n, int q, const RoutingTableEntry *a){
for(int in = 0; in < n; in++){
RouterTable->insert(a[in]);
}
}