提交记录 11267
提交时间 |
评测时间 |
2019-11-11 01:53:29 |
2020-08-01 02:41:08 |
#include "router.h"
#include <stdint.h>
#include <stdlib.h>
#include <arpa/inet.h>
#include <unordered_map>
/*
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 struct {
uint32_t if_index;
uint32_t nexthop;
} SimpleEntry;
std::unordered_map<uint32_t, SimpleEntry> table_entries;
#define DUCK_OJ
#ifdef DUCK_OJ
void init(int n, int q, const RoutingTableEntry *a)
{
for(int i = 0; i < n; ++i)
{
uint32_t addr = ntohl(a[i].addr) & (0xffffffff << (32 - a[i].len));
table_entries[addr] = { 0, a[i].nexthop };
}
}
unsigned query(unsigned addr)
{
for(int i = 32; i > 0; --i) {
uint32_t addr = addr & (0xffffffff << (32 - i));
auto it = table_entries.find(addr);
if(it != table_entries.end())
return (*it).second.nexthop;
}
return 0;
}
#endif
/**
* @brief 插入/删除一条路由表表项
* @param insert 如果要插入则为 true ,要删除则为 false
* @param entry 要插入/删除的表项
*
* 插入时如果已经存在一条 addr 和 len 都相同的表项,则替换掉原有的。
* 删除时按照 addr 和 len 匹配。
*/
void update(bool isInsert, RoutingTableEntry entry)
{
}
/**
* @brief 进行一次路由表的查询,按照最长前缀匹配原则
* @param addr 需要查询的目标地址,大端序
* @param nexthop 如果查询到目标,把表项的 nexthop 写入
* @param if_index 如果查询到目标,把表项的 if_index 写入
* @return 查到则返回 true ,没查到则返回 false
*/
bool query(uint32_t addr, uint32_t *nexthop, uint32_t *if_index)
{
// TODO:
*nexthop = 0;
*if_index = 0;
return false;
}
Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
Testcase #1 | 14.94 us | 24 KB | Accepted | Score: 25 | 显示更多 |
Testcase #2 | 137.612 ms | 40 MB + 940 KB | Accepted | Score: 25 | 显示更多 |
Testcase #3 | 155.577 ms | 40 MB + 940 KB | Wrong Answer | Score: 0 | 显示更多 |
Testcase #4 | 173.154 ms | 40 MB + 940 KB | Wrong Answer | Score: 0 | 显示更多 |
Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 04:09:18 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用