提交记录 15079
提交时间 |
评测时间 |
2020-11-21 00:33:55 |
2020-11-21 00:33:57 |
#include "router.h"
#include <stdlib.h>
#include <arpa/inet.h>
/*
RoutingTable Entry 的定义如下:
typedef struct {
uint32_t addr; // 大端序,IPv4 地址
uint32_t len; // 小端序,前缀长度
uint32_t if_index; // 小端序,出端口编号
uint32_t nexthop; // 大端序,下一跳的 IPv4 地址
} RoutingTableEntry;
约定 addr 和 nexthop 以 **大端序** 存储。
这意味着 1.2.3.4 对应 0x04030201 而不是 0x01020304。
保证 addr 仅最低 len 位可能出现非零。
当 nexthop 为零时这是一条直连路由。
你可以在全局变量中把路由表以一定的数据结构格式保存下来。
*/
typedef uint32_t node_index_t;
const int N = 1 << 25;
node_index_t ch[N][2];
node_index_t rec[N];
node_index_t used = 0, rec_cnt = 0;
bool valid[N];
uint32_t if_index[N];
uint32_t nexthop[N];
node_index_t tmp[32];
node_index_t new_node() {
if (!rec_cnt) {
return ++used;
}
return rec[--rec_cnt];
}
void del_node(node_index_t p) {
if (p) rec[rec_cnt++] = p;
}
/**
* @brief 插入/删除一条路由表表项
* @param insert 如果要插入则为 true ,要删除则为 false
* @param entry 要插入/删除的表项
*
* 插入时如果已经存在一条 addr 和 len 都相同的表项,则替换掉原有的。
* 删除时按照 addr 和 len **精确** 匹配。
*/
void update(bool insert, RoutingTableEntry entry) {
uint32_t addr = htonl(entry.addr), len = entry.len;
node_index_t x = 0;
for (int i = 0; i < len; ++i) {
uint32_t c = (addr >> (i ^ 31)) & 1;
if (!ch[x][c]) {
if (!insert) return;
ch[x][c] = new_node();
}
tmp[i] = x;
x = ch[x][c];
}
if (insert) {
valid[x] = true;
// if_index[x] = entry.if_index;
nexthop[x] = entry.nexthop;
} else {
valid[x] = false;
if (ch[x][0] || ch[x][1]) return;
del_node(x);
for (int i = len - 1; i >= 0; --i) {
node_index_t f = tmp[i];
if (ch[f][0] == x) {
ch[f][0] = 0;
if (ch[f][1] || valid[f]) return;
} else {
ch[f][1] = 0;
if (ch[f][0] || valid[f]) return;
}
x = f;
del_node(x);
}
}
}
/**
* @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) {
addr = htonl(addr);
bool ok = false;
node_index_t x = 0;
if (valid[x]) {
*_nexthop = nexthop[x];
*_if_index = if_index[x];
ok = true;
}
for (int i = 0; i < 32; ++i) {
uint32_t c = (addr >> (i ^ 31)) & 1;
if (!ch[x][c]) break;
x = ch[x][c];
if (valid[x]) {
*_nexthop = nexthop[x];
// *_if_index = if_index[x];
ok = true;
}
}
return ok;
}
void init(int n, int q, const RoutingTableEntry *a) {
for (int i = 0; i < n; ++i) {
update(true, a[i]);
}
}
unsigned query(unsigned addr) {
uint32_t res, _;
if (prefix_query(addr, &res, &_)) {
return res;
} else {
return 0;
}
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 13.25 us | 40 KB | Accepted | Score: 25 | 显示更多 |
Testcase #2 | 42.708 ms | 32 MB + 540 KB | Accepted | Score: 25 | 显示更多 |
Testcase #3 | 161.544 ms | 32 MB + 540 KB | Accepted | Score: 25 | 显示更多 |
Testcase #4 | 279.49 ms | 32 MB + 540 KB | Accepted | Score: 25 | 显示更多 |
Judge Duck Online | 评测鸭在线
Server Time: 2024-12-05 10:10:30 | Loaded in 14 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠