#include "router.h"
#define LENGTH 676
#define MAX_CHUNK 16
#define DEFAULT ((1 << 30) - 1)
typedef unsigned short ushort; // 16
typedef unsigned int uint; // 32
/*
* TrieNode.t: node type
* 0: this is empty node
* 1: p is dest index value
* 2: this is a level8 pointer
* 3:
*/
typedef struct{
uint p:30;
uint t:2 ;
}TrieNode;
typedef TrieNode Level16[1<<17];
typedef TrieNode Level8[1<<9];
typedef struct {
ushort inx :10;
ushort offset : 6;
}uword;
typedef uword codeword16[1<<12];
typedef uword codeword8[1<<4];
typedef ushort baseindex16[1<<10];
typedef ushort baseindex8[1<<2];
typedef unsigned long long ull;
typedef ull maptable[LENGTH]; // 4 bit every element
typedef struct {
uint ipnet; // 32
uint port; // 32
ushort length; // 16
}RouterEntry;
typedef struct {
uword * codeword;
ushort * baseindex;
TrieNode * lookup;
}LookupEntry;
typedef LookupEntry LookupTable[1 << MAX_CHUNK];
void start(char * file);
int lookup(uint ipaddr);
void freeMemory();
/*
============================================================================
Name : Lulea.c
Author : ***
Version :
Copyright : Your copyright notice
Description : Hello World in C, Ansi-style
============================================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
maptable mt;
static LookupTable ltb;
static ushort ltbcsr = 0;
ushort val[] = { 0, 128, 136, 138, 139, 142, 143, 168, 170, 171, 174, 175, 184,
186, 187, 190, 191, 232, 234, 235, 238, 239, 248, 250, 251, 254, 255 };
struct {
TrieNode * v16;
TrieNode ** v16ptr;
} trie;
// get maptable[ten][bit]
int triveMap(ushort n, ushort loc) {
if (n == 676)
return -1;
else if (n == 677)
return 0;
else {
ull x = mt[n];
x = (x << (loc * 4)) >> 60;
return x;
}
}
void writeTo(int k, ushort temp) { // save maptable[k]
ull result = 0;
ushort count = 0;
int i;
ushort bit[16];
for (i = 0; i < 16; i++) {
bit[i] = temp & 1;
temp = temp >> 1;
}
for (i = 14; i >= 0; i--) {
count += bit[i]; // prefix sum
result = (result << 4) + count;
}
mt[k] = result;
}
void generate() { // generate maptable
int i, j, k = 0;
ushort temp;
ushort map4[6] = { 0, 8, 10, 11, 14, 15 };
int map8len = 27;
ushort *map8 = (ushort*) malloc(sizeof(ushort) * map8len);
ushort * m8ptr = map8 + 1;
*m8ptr++ = 1 << 7;
for (i = 1; i < 6; i++) {
for (j = 1; j < 6; j++) {
*m8ptr++ = (map4[i] << 4) + map4[j];
}
}
memset(mt, 0, sizeof(maptable));
for (i = 1; i < map8len; i++) {
for (j = 1; j < map8len; j++) {
temp = (map8[i] << 8) + map8[j];
writeTo(k, temp);
k++;
}
}
}
void traverse(TrieNode *v16, uint i, uint limit) { // post-order traverse
uint j = (i << 1);
uint k;
if (i < limit && v16[i].t != 0) {
traverse(v16, j, limit);
traverse(v16, j + 1, limit);
if (j >= limit)
return;
switch (v16[i].t) {
case 1:
if (v16[j].t == 0 && v16[j + 1].t != 0) {
v16[j].t = 1;
v16[j].p = v16[i].p;
v16[i].t = 3;
} else if (v16[j].t != 0 && v16[j + 1].t == 0) {
v16[j + 1].t = 1;
v16[j + 1].p = v16[i].p;
v16[i].t = 3;
} else if (v16[j].t != 0 && v16[j + 1].t != 0) {
v16[i].t = 3;
}
break;
case 3:
if (v16[j].t == 0 && v16[j + 1].t != 0) {
k = i >> 1;
while (v16[k].t != 1) { // find ancestor
k >>= 1;
}
v16[j].t = 1;
v16[j].p = v16[k].p;
} else if (v16[j].t != 0 && v16[j + 1].t == 0) {
k = i >> 1;
while (v16[k].t != 1) {
k >>= 1;
}
v16[j + 1].t = 1;
v16[j + 1].p = v16[k].p;
}
break;
default: {
}
}
}
}
/*
* height: value 8, 16
*/
void completeTrie(TrieNode * v16, uint height) {
int level, i, k;
for (i = (1 << height); i < (1 << (height + 1)); i++) {
if (v16[i].t == 1 || v16[i].t == 2) {
k = i >> 1;
while (k > 0 && v16[k].t == 0) { // update ancestor
v16[k].t = 3;
k >>= 1;
}
}
}
for (level = height - 1; level >= 0; level--) {
for (i = (1 << level); i < (1 << (level + 1)); i++) {
if (v16[i].t == 1) {
k = i >> 1;
while (k > 0 && v16[k].t == 0) {
v16[k].t = 3;
k >>= 1;
}
}
}
}
traverse(v16, 1, (1 << (height + 1)));
}
uint findtoUpdate(TrieNode * v16, int temp) { // find ancestor's pointer
while (v16[temp].t != 1) {
temp >>= 1;
}
return v16[temp].p;
}
/*
* make level 2/3 Trie, or 16+7 ?
*/
void makeTrie23(TrieNode * v16, TrieNode ** v16ptr) {
int level, i, j, k, n;
TrieNode * chunk;
for (i = (1 << 8); i < (1 << 9); i++) {
if (v16[i].t == 2) {
chunk = v16ptr[v16[i].p];
if (chunk[1].t == 0) {
chunk[1].t = 1;
chunk[1].p = findtoUpdate(v16, i >> 1);
}
makeTrie23(v16ptr[v16[i].p], v16ptr);
}
}
completeTrie(v16, 8);
for (level = 7; level >= 0; level--) {
for (i = (1 << level); i < (1 << (level + 1)); i++) {
if (v16[i].t == 1) {
k = (i << (8 - level));
n = k + (1 << (8 - level));
v16[k].t = 1;
v16[k].p = v16[i].p;
for (j = k + 1; j < n; j++) {
v16[j].t = 1; // t = 0
v16[j].p = 0;
}
}
}
}
}
void makeTrie(TrieNode * v16, TrieNode ** v16ptr) {
int level, i, j, k, n;
TrieNode * chunk;
for (i = (1 << 16); i < (1 << 17); i++) {
if (v16[i].t == 2) {
chunk = v16ptr[v16[i].p];
if (chunk[1].t == 0) {
chunk[1].t = 1;
chunk[1].p = findtoUpdate(v16, i >> 1);
}
makeTrie23(v16ptr[v16[i].p], v16ptr);
}
}
completeTrie(v16, 16);
for (level = 15; level >= 0; level--) {
for (i = (1 << level); i < (1 << (level + 1)); i++) {
if (v16[i].t == 1) {
k = (i << (16 - level));
n = k + (1 << (16 - level));
v16[k].t = 1;
v16[k].p = v16[i].p;
for (j = k + 1; j < n; j++) {
v16[j].t = 1;
v16[j].p = 0;
}
}
}
}
}
ushort find(ushort k) {
int low = 0, mid, high = 26;
while (low <= high) {
mid = (low + high) / 2;
if (val[mid] == k)
return mid;
else if (val[mid] < k)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
void put(uword * thd, int i, ushort f8, ushort e8) {
ushort gf8 = find(f8);
ushort ge8 = find(e8);
if (gf8 == 0 && ge8 == 0)
thd[i].inx = 676;
else if (gf8 == 1 && ge8 == 0)
thd[i].inx = 677;
else
thd[i].inx = (gf8 - 1) * 26 + (ge8 - 1);
}
ushort trive(TrieNode * v16, uword * thd, int j, int k) {
ushort f8 = 0u, e8 = 0u;
ushort x = 0u;
int m;
for (m = k; m < k + 8; m++) {
f8 <<= 1;
if ((v16[m].t == 1 && v16[m].p != 0) || (v16[m].t == 2)) {
x++;
f8++;
}
}
for (m = k + 8; m < k + 16; m++) {
e8 <<= 1;
if ((v16[m].t == 1 && v16[m].p != 0) || (v16[m].t == 2)) {
x++;
e8++;
}
}
put(thd, j, f8, e8);
return x;
}
void makeLtb23(TrieNode * v16, TrieNode ** v16ptr) {
int i, j, k;
uint x, y, z, h;
ushort leave = 0;
int allOne = 0;
int all16;
ushort index;
int the = ltbcsr;
ltbcsr++;
ushort * thx; // base index array pointer
uword * thd; // 10:6 codeword array pointer
TrieNode * ptr;
TrieNode * tptr;
for (ptr = v16 + (1 << 8); ptr < (v16 + (1 << 9)); ptr++) {
if (ptr->t == 1 && ptr->p != 0)
allOne++;
else if (ptr->t == 2)
allOne++;
}
if (allOne <= 8) {
ltb[the].codeword = NULL;
/*
thx = ltb[the].baseindex = (ushort *) malloc(sizeof(ushort) * (allOne
+ 1));
thx[allOne] = 257;
tptr = ltb[the].lookup = (TrieNode *) malloc(sizeof(TrieNode) * allOne);*/
thx = ltb[the].baseindex = (ushort *) malloc(sizeof(ushort) * 8);
for(i = 0; i < 8; i++){
ltb[the].baseindex[i] = 257;
}
tptr = ltb[the].lookup = (TrieNode *) malloc(sizeof(TrieNode) * 8);
for (ptr = v16 + (1 << 8), index = 0u; ptr < (v16 + (1 << 9)); index++, ptr++) {
if (ptr->t == 1 && ptr->p != 0) {
*thx = index;
thx++;
tptr -> t = 1u;
tptr -> p = ptr->p;
tptr++;
} else if (ptr->t == 2) {
*thx = index;
thx++;
tptr -> t = 2u;
tptr -> p = ltbcsr;
tptr++;
makeLtb23(v16ptr[ptr->p], v16ptr);
}
}
} else if (allOne < 64) {
leave = 0;
ltb[the].baseindex = NULL;
thd = ltb[the].codeword = (uword *) malloc(sizeof(codeword8));
for (i = 0, k = (1 << 8); i < (1 << 4); i++, k += 16) {
x = trive(v16, thd, i, k);
thd[i].offset = leave;
leave += x;
}
ltb[the].lookup = (TrieNode *) malloc(sizeof(TrieNode) * allOne);
tptr = ltb[the].lookup;
for (ptr = v16 + (1 << 8); ptr < (v16 + (1 << 9)); ptr++) {
if (ptr->t == 1 && ptr->p != 0) {
tptr->p = ptr->p;
tptr->t = ptr->t;
tptr++;
} else if (ptr->t == 2) {
tptr->p = ltbcsr;
tptr->t = 2;
tptr++;
makeLtb23(v16ptr[ptr->p], v16ptr);
}
}
} else {
thd = ltb[the].codeword = (uword *) malloc(sizeof(codeword8));
thx = ltb[the].baseindex = (ushort *) malloc(sizeof(baseindex8));
for (i = 0, j = 0, k = (1 << 8); i < (1 << 2); i++, j += 4, k += 64) {
x = trive(v16, thd, j, k);
y = trive(v16, thd, j + 1, k + 16);
z = trive(v16, thd, j + 2, k + 32);
h = trive(v16, thd, j + 3, k + 48);
thd[j].offset = 0;
thd[j + 1].offset = thd[j].offset + x;
thd[j + 2].offset = thd[j + 1].offset + y;
thd[j + 3].offset = thd[j + 2].offset + z;
all16 = x + y + z + h;
thx[i] = leave;
leave = all16 + thx[i];
}
tptr = ltb[the].lookup = (TrieNode *) malloc(sizeof(TrieNode) * allOne);
for (ptr = v16 + (1 << 8); ptr < (v16 + (1 << 9)); ptr++) {
if (ptr->t == 1 && ptr->p != 0) {
tptr->p = ptr->p;
tptr->t = ptr->t;
tptr++;
} else if (ptr->t == 2) {
tptr->p = ltbcsr;
tptr->t = 2;
tptr++;
makeLtb23(v16ptr[ptr->p], v16ptr);
}
}
}
}
void makeLtb(TrieNode * v16, TrieNode ** v16ptr) {
int i, j, k;
ushort x, y, z, h;
ushort leave = 0;
int allOne = 0;
int all16;
int the = ltbcsr = 0 ;
TrieNode * ptr;
TrieNode * tptr;
uword * thd;
ushort * thx;
ltbcsr++;
thd = ltb[the].codeword = (uword *) malloc(sizeof(codeword16));
thx = ltb[the].baseindex = (ushort *) malloc(sizeof(baseindex16));
for (i = 0, j = 0, k = (1 << 16); i < (1 << 10); i++, j += 4, k += 64) {
x = trive(v16, thd, j, k);
y = trive(v16, thd, j + 1, k + 16);
z = trive(v16, thd, j + 2, k + 32);
h = trive(v16, thd, j + 3, k + 48);
thd[j].offset = 0;
thd[j + 1].offset = thd[j].offset + x;
thd[j + 2].offset = thd[j + 1].offset + y;
thd[j + 3].offset = thd[j + 2].offset + z;
all16 = x + y + z + h;
thx[i] = leave;
leave = all16 + thx[i];
allOne += all16;
}
tptr = ltb[the].lookup = (TrieNode *) malloc(sizeof(TrieNode) * allOne);
for (k = (1 << 16), ptr = &v16[k]; k < (1 << 17); k++, ptr++) {
if (ptr->t == 1 && ptr->p != 0) {
tptr->p = ptr->p;
tptr->t = ptr->t;
tptr++;
} else if (ptr->t == 2) {
tptr->p = ltbcsr;
tptr->t = 2;
tptr++;
makeLtb23(v16ptr[ptr->p], v16ptr);
}
}
}
ushort search(ushort n, ushort * base) {
int i = 0, j = 7;
while(i <= j){
int middle = (i + j)/2;
if(base[middle] > n){
j = middle - 1;
}else if(base[middle] < n){
i = middle + 1;
}else{
return (ushort)middle;
}
}
return j;
}
int lookup3(uint ipaddr, ushort cur) {
ushort ip;
uword code;
ushort ix, bix, bit, ten, six, pter;
int pix;
ip = (ushort) ((ipaddr & 0xff));
if (ltb[cur].codeword == NULL) {
pter = search(ip, ltb[cur].baseindex);
return ltb[cur].lookup[pter].p;
} else if (ltb[cur].baseindex == NULL) {
ix = ip >> 4;
bit = ip & 0xf;
code = ltb[cur].codeword[ix];
ten = code.inx;
six = code.offset;
pix = six + triveMap(ten, bit);
return ltb[cur].lookup[pix].p;
} else {
ix = ip >> 4;
bit = ip & 0xf;
bix = ip >> 6;
code = ltb[cur].codeword[ix];
ten = code.inx;
six = code.offset;
pix = ltb[cur].baseindex[bix] + six + triveMap(ten, bit);
return ltb[cur].lookup[pix].p;
}
}
int lookup2(uint ipaddr, ushort cur) {
ushort ip;
uword code;
ushort ix, bix, bit, ten, six, pter;
int pix;
ip = (ushort) ((ipaddr & 0xff00) >> 8);
if (ltb[cur].codeword == NULL) {
pter = search(ip, ltb[cur].baseindex);
if (ltb[cur].lookup[pter].t == 1)
return ltb[cur].lookup[pter].p;
else
return lookup3(ipaddr, ltb[cur].lookup[pter].p);
} else if (ltb[cur].baseindex == NULL) {
ix = ip >> 4;
bit = ip & 0xf;
code = ltb[cur].codeword[ix];
ten = code.inx;
six = code.offset;
pix = six + triveMap(ten, bit);
if (ltb[cur].lookup[pix].t == 1)
return ltb[cur].lookup[pix].p;
else {
return lookup3(ipaddr, ltb[cur].lookup[pix].p);
}
} else {
ix = ip >> 4;
bit = ip & 0xf;
bix = ip >> 6;
code = ltb[cur].codeword[ix];
ten = code.inx;
six = code.offset;
pix = ltb[cur].baseindex[bix] + six + triveMap(ten, bit);
if (ltb[cur].lookup[pix].t == 1)
return ltb[cur].lookup[pix].p;
else {
return lookup3(ipaddr, ltb[cur].lookup[pix].p);
}
}
}
int lookup(uint ipaddr) {
uint cur = 0;
ushort ix, bix, bit, ten, six;
int pix;
uword code;
ipaddr=ntohl(ipaddr);
ix = (ushort) (ipaddr >> 20);
bix = (ushort) (ipaddr >> 22);
bit = (ushort) ((ipaddr >> 16) & 0xf);
code = ltb[cur].codeword[ix];
ten = code.inx;
six = code.offset;
pix = ltb[cur].baseindex[bix] + six + triveMap(ten, bit);
if (ltb[cur].lookup[pix].t == 1)
return ltb[cur].lookup[pix].p;
else {
cur = ltb[cur].lookup[pix].p;
return lookup2(ipaddr, cur);
}
}
void freeMemory() {
TrieNode * ptr;
TrieNode * ptr2;
TrieNode * arr;
TrieNode * v16 = trie.v16;
TrieNode ** v16ptr = trie.v16ptr;
for (ptr = v16 + (1 << 16); ptr < v16 + (1 << 17); ptr++) {
if (ptr->t == 2) {
arr = v16ptr[ptr->p];
for (ptr2 = arr + (1 << 8); ptr2 < arr + (1 << 9); ptr2++) {
if (ptr2->t == 2) {
free(v16ptr[ptr2->p]);
}
}
free(arr);
}
}
free(v16);
int i;
LookupEntry * entry;
for (i = 0, entry = <b[0]; i < ltbcsr; i++, entry++) {
if (entry->codeword)
free(entry->codeword);
if (entry->baseindex)
free(entry->baseindex);
if (entry->lookup)
free(entry->lookup);
}
}
#define BTOL32(x) \
((__uint32_t)((((__uint32_t)(x) & 0xff000000) >> 24) | \
(((__uint32_t)(x) & 0x00ff0000) >> 8) | \
(((__uint32_t)(x) & 0x0000ff00) << 8) | \
(((__uint32_t)(x) & 0x000000ff) << 24)))
void construct(TrieNode * v16, TrieNode ** v16ptr, const RoutingTableEntry * a, int nentry) {
RouterEntry rentry;
int count = 0; // count v16ptr elements
int ctemp;
uint temp, temp2, temp3;
memset(v16, 0, sizeof(Level16));
v16[1].t = 1;
v16[1].p = DEFAULT;
int i = 0;
const RoutingTableEntry* cur = a;
while (i < nentry) {
cur = a+i;
i++;
rentry.ipnet = ntohl(cur->addr);
rentry.port = cur->nexthop;
rentry.length = cur->len;
//printf("%X/%d\t%d\n", rentry.ipnet, rentry.length, rentry.port);
if (rentry.length < 16) {
temp = (1 << rentry.length)
+ (rentry.ipnet >> (32 - rentry.length));
v16[temp].t = 1;
v16[temp].p = rentry.port;
} else if (rentry.length == 16) {
temp = (1 << 16) + (rentry.ipnet >> 16);
switch (v16[temp].t) {
case 0:
v16[temp].t = 1;
v16[temp].p = rentry.port;
break;
case 1:
v16[temp].p = rentry.port;
break;
default:
v16ptr[v16[temp].p][1].t = 1;
v16ptr[v16[temp].p][1].p = rentry.port;
}
} else if (rentry.length < 24) {
temp = (1 << 16) + (rentry.ipnet >> 16);
temp2 = (1 << (rentry.length - 16)) + ((rentry.ipnet & 0xffff)
>> (32 - rentry.length));
switch (v16[temp].t) {
case 0: {
v16ptr[count] = (TrieNode *) malloc(sizeof(Level8));
memset(v16ptr[count], 0, sizeof(Level8));
v16[temp].t = 2;
v16[temp].p = count;
v16ptr[count][temp2].t = 1;
v16ptr[count][temp2].p = rentry.port;
count++;
break;
}
case 1: {
v16ptr[count] = (TrieNode *) malloc(sizeof(Level8));
memset(v16ptr[count], 0, sizeof(Level8));
v16ptr[count][1].t = 1;
v16ptr[count][1].p = v16[temp].p;
v16[temp].t = 2;
v16[temp].p = count;
v16ptr[count][temp2].t = 1;
v16ptr[count][temp2].p = rentry.port;
count++;
break;
}
default: {
v16ptr[v16[temp].p][temp2].t = 1;
v16ptr[v16[temp].p][temp2].p = rentry.port;
}
}
} else if (rentry.length == 24) {
temp = (1 << 16) + (rentry.ipnet >> 16);
temp2 = (1 << 8) + ((rentry.ipnet & 0xffff) >> 8);
switch (v16[temp].t) {
case 0: {
v16ptr[count] = (TrieNode *) malloc(sizeof(Level8));
memset(v16ptr[count], 0, sizeof(Level8));
v16[temp].t = 2;
v16[temp].p = count;
v16ptr[count][temp2].t = 1;
v16ptr[count][temp2].p = rentry.port;
count++;
break;
}
case 1: {
v16ptr[count] = (TrieNode *) malloc(sizeof(Level8));
memset(v16ptr[count], 0, sizeof(Level8));
v16ptr[count][1].t = 1;
v16ptr[count][1].p = v16[temp].p;
v16[temp].t = 2;
v16[temp].p = count;
v16ptr[count][temp2].t = 1;
v16ptr[count][temp2].p = rentry.port;
count++;
break;
}
default: {
switch (v16ptr[v16[temp].p][temp2].t) {
case 0: {
v16ptr[v16[temp].p][temp2].t = 1;
v16ptr[v16[temp].p][temp2].p = rentry.port;
break;
}
case 1: {
v16ptr[v16[temp].p][temp2].t = 1;
v16ptr[v16[temp].p][temp2].p = rentry.port;
break;
}
default: {
v16ptr[v16ptr[v16[temp].p][temp2].p][1].t = 1;
v16ptr[v16ptr[v16[temp].p][temp2].p][2].p = rentry.port;
}
}
}
}
} else { // length > 24
temp = (1 << 16) + (rentry.ipnet >> 16);
temp2 = (1 << 8) + ((rentry.ipnet & 0xffff) >> 8);
temp3 = (1 << (rentry.length - 24)) + ((rentry.ipnet & 0xff) >> (32
- rentry.length));
switch (v16[temp].t) {
case 0: {
v16ptr[count] = (TrieNode *) malloc(sizeof(Level8));
memset(v16ptr[count], 0, sizeof(Level8));
v16[temp].t = 2;
v16[temp].p = count;
ctemp = count;
count++;
v16ptr[count] = (TrieNode *) malloc(sizeof(Level8));
memset(v16ptr[count], 0, sizeof(Level8));
v16ptr[ctemp][temp2].t = 2;
v16ptr[ctemp][temp2].p = count;
v16ptr[count][temp3].t = 1;
v16ptr[count][temp3].p = rentry.port;
count++;
break;
}
case 1: {
v16ptr[count] = (TrieNode *) malloc(sizeof(Level8));
memset(v16ptr[count], 0, sizeof(Level8));
v16ptr[count][1].t = 1;
v16ptr[count][1].p = v16[temp].p;
v16[temp].t = 2;
v16[temp].p = count;
ctemp = count;
count++;
v16ptr[count] = (TrieNode *) malloc(sizeof(Level8));
memset(v16ptr[count], 0, sizeof(Level8));
v16ptr[ctemp][temp2].t = 2;
v16ptr[ctemp][temp2].p = count;
v16ptr[count][temp3].t = 1;
v16ptr[count][temp3].p = rentry.port;
count++;
break;
}
default: {
switch (v16ptr[v16[temp].p][temp2].t) {
case 0: {
v16ptr[count] = (TrieNode *) malloc(sizeof(Level8));
memset(v16ptr[count], 0, sizeof(Level8));
v16ptr[v16[temp].p][temp2].t = 2;
v16ptr[v16[temp].p][temp2].p = count;
v16ptr[count][temp3].t = 1;
v16ptr[count][temp3].p = rentry.port;
count++;
break;
}
case 1: {
v16ptr[count] = (TrieNode *) malloc(sizeof(Level8));
memset(v16ptr[count], 0, sizeof(Level8));
v16ptr[count][1].t = 1;
v16ptr[count][1].p = v16ptr[v16[temp].p][temp2].p;
v16ptr[v16[temp].p][temp2].t = 2;
v16ptr[v16[temp].p][temp2].p = count;
v16ptr[count][temp3].t = 1;
v16ptr[count][temp3].p = rentry.port;
count++;
break;
}
default: {
v16ptr[v16ptr[v16[temp].p][temp2].p][temp3].t = 1;
v16ptr[v16ptr[v16[temp].p][temp2].p][temp3].p = rentry.port;
}
}
}
}
}
}
}
void start(const RoutingTableEntry *a, int nentry) {
TrieNode * v16 = trie.v16 = (TrieNode *) malloc(sizeof(Level16));
TrieNode ** v16ptr = trie.v16ptr = (TrieNode **) malloc(sizeof(TrieNode *)
* (1 << MAX_CHUNK));
generate();
construct(v16, v16ptr, a, nentry);
// printf("Trie has been created....\n");
makeTrie(v16, v16ptr);
// printf("comp has been created....\n");
makeLtb(v16, v16ptr);
// printf("ltb has been created....\n");
}
void init(int n, int q, const RoutingTableEntry *a) {
start(a, n);
}
unsigned query(unsigned addr) {
return lookup(addr);
}
| Compilation | N/A | N/A | Compile Error | Score: N/A | 显示更多 |