提交记录 14379


用户 题目 状态 得分 用时 内存 语言 代码长度
t4rf9 router32. 测测你的路由器 Wrong Answer 25 496.104 ms 80208 KB C++ 7.74 KB
提交时间 评测时间
2020-09-25 18:23:09 2020-09-25 18:23:16
#include "router.h"
#include <cstdint>
#include <netinet/in.h>
#include <cstdlib>

typedef struct TrieNode {
    TrieNode *children[2] = {NULL, NULL};
    int8_t depth = 0;
    int8_t size = 0;
    bool is_entry = false;
    uint32_t addr = 0;
    uint32_t nexthop = 0;
} TrieNode;

TrieNode root;

void initialize_TrieNode(TrieNode *node, uint32_t addr, uint32_t nexthop,
                         int8_t depth, int8_t size, TrieNode *chlid0, TrieNode *child1, bool isItem) {
    node->addr = addr;
    node->nexthop = nexthop;
    node->depth = depth;
    node->size = size;
    node->is_entry = isItem;
    node->children[0] = chlid0;
    node->children[1] = child1;
}

/**
 * @brief 插入/删除一条路由表表项
 * @param insert 如果要插入则为 true ,要删除则为 false
 * @param entry 要插入/删除的表项
 *
 * 插入时如果已经存在一条 addr 和 len 都相同的表项,则替换掉原有的。
 * 删除时按照 addr 和 len **精确** 匹配。
 */
void update(bool insert, RoutingTableEntry entry) {
    uint32_t addr = ntohl(entry.addr);
    int8_t len = entry.len;
    uint32_t nexthop = entry.nexthop;

    TrieNode *prev_node;
    TrieNode *curr_node = &root;
    if (insert) {
        uint32_t mask = 0x80000000;
        for (int8_t i = 0; i < len; ++i) {
            int8_t entry_bit = (addr & mask) >> (31 - i);
            if (i == curr_node->depth + curr_node->size) { // reaching the end of a node
                prev_node = curr_node;
                curr_node = curr_node->children[entry_bit];
            }
            if (curr_node == NULL) {
                curr_node = (TrieNode *) malloc(sizeof(TrieNode));
                initialize_TrieNode(curr_node, addr, nexthop, i, len - i, NULL, NULL, true);
                prev_node->children[entry_bit] = curr_node;
                return;
            }

            int8_t curr_node_bit = (curr_node->addr & mask) >> (31 - i);
            if (entry_bit != curr_node_bit) { // split due to mismatching
                TrieNode *entry_node = (TrieNode *) malloc(sizeof(TrieNode));
                initialize_TrieNode(entry_node, addr, nexthop, i, len - i, NULL, NULL, true);

                uint32_t curr_size = i - curr_node->depth;

                TrieNode *next_node = (TrieNode *) malloc(sizeof(TrieNode));
                initialize_TrieNode(next_node, curr_node->addr, curr_node->nexthop,
                                    i, curr_node->size - curr_size, curr_node->children[0], curr_node->children[1],
                                    curr_node->is_entry);

                curr_node->children[curr_node_bit] = next_node;
                curr_node->children[entry_bit] = entry_node;

                curr_node->size = curr_size;
                curr_node->is_entry = false;
                return;
            }
            mask >>= 1;
        }
        if (len == curr_node->depth + curr_node->size) { // reaching the end of a node, unnecessary to split, replace
            curr_node->nexthop = nexthop;
            curr_node->is_entry = true;
            curr_node->addr = addr;
        } else { // node splitting: split a longer chain
            int8_t next_node_bit = (curr_node->addr & mask) >> (31 - len);
            TrieNode *next_node = (TrieNode *) malloc(sizeof(TrieNode));
            uint32_t curr_size = len - curr_node->depth;
            initialize_TrieNode(next_node, curr_node->addr, curr_node->nexthop,
                                len, curr_node->size - curr_size, curr_node->children[0], curr_node->children[1],
                                curr_node->is_entry);

            curr_node->children[next_node_bit] = next_node;
            curr_node->children[1 - next_node_bit] = NULL;

            curr_node->addr = addr;
            curr_node->nexthop = nexthop;
            curr_node->size = curr_size;
            curr_node->is_entry = true;
        }
    } else { // deletion
        uint32_t mask = 0x80000000;
        int8_t entry_bit;
        int8_t curr_node_bit;
        int8_t curr_node_rank;
        for (int8_t i = 0; i < len; ++i) {
            entry_bit = (addr & mask) >> (31 - i);
            if (i == curr_node->depth + curr_node->size) { // reaching the end of a node
                prev_node = curr_node;
                curr_node = curr_node->children[entry_bit];
                curr_node_rank = entry_bit;
                if (curr_node == NULL) {
                    return;
                }
            }

            curr_node_bit = (curr_node->addr & mask) >> (31 - i);
            if (entry_bit != curr_node_bit) {
                return;
            }

            mask >>= 1;
        }
        if (curr_node->is_entry && addr == curr_node->addr &&
            len == curr_node->depth + curr_node->size) { // found, delete
            if (curr_node == &root) {
                root.is_entry = false;
                return;
            }
            if (curr_node->children[0]) {
                if (curr_node->children[1]) { // 2 children
                    curr_node->is_entry = false;
                } else { // 1 child
                    curr_node->addr = curr_node->children[0]->addr;
                    curr_node->size += curr_node->children[0]->size;
                    curr_node->nexthop = curr_node->children[0]->nexthop;
                    curr_node->is_entry = curr_node->children[0]->is_entry;
                    free(curr_node->children[0]);
                    curr_node->children[0] = NULL;
                }
            } else {
                if (curr_node->children[1]) { // 1 child
                    curr_node->addr = curr_node->children[1]->addr;
                    curr_node->size += curr_node->children[1]->size;
                    curr_node->nexthop = curr_node->children[1]->nexthop;
                    curr_node->is_entry = curr_node->children[1]->is_entry;
                    free(curr_node->children[1]);
                    curr_node->children[1] = NULL;
                } else { // no child
                    prev_node->children[curr_node_rank] = NULL;
                    free(curr_node);

                    if (!prev_node->is_entry && prev_node != &root) {
                        TrieNode *other = prev_node->children[1 - curr_node_rank];
                        initialize_TrieNode(prev_node, other->addr, other->nexthop, prev_node->depth,
                                            prev_node->size + other->size, other->children[0], other->children[1],
                                            other->is_entry);
                        free(other);
                    }
                }
            }
        }
    }
}

/**
 * @brief 进行一次路由表的查询,按照最长前缀匹配原则
 * @param addr 需要查询的目标地址,网络字节序
 * @param nexthop 如果查询到目标,把表项的 nexthop 写入
 * @return 查到则返回 true ,没查到则返回 false
 */
bool prefix_query(uint32_t addr, uint32_t *nexthop) {
    uint32_t nexthop_tmp, is_entry_tmp = false;
    addr = ntohl(addr);
    uint32_t mask = 0x80000000;
    TrieNode *prev_node;
    TrieNode *curr_node = &root;
    for (int8_t i = 0; i < 32; ++i, mask >>= 1) {
        uint8_t entry_bit = (addr & mask) >> (31 - i);
        if (i == curr_node->depth + curr_node->size) { // reaching the end of a node
            if (curr_node->is_entry) {
                nexthop_tmp = curr_node->nexthop;
                is_entry_tmp = true;
            }

            curr_node = curr_node->children[entry_bit];
            if (curr_node == NULL) {
                *nexthop = nexthop_tmp;
                return is_entry_tmp;
            }
        }

        uint8_t curr_node_bit = (curr_node->addr & mask) >> (31 - i);
        if (entry_bit != curr_node_bit) {
            *nexthop = nexthop_tmp;
            return is_entry_tmp;
        }
    }
    *nexthop = curr_node->nexthop;
    return curr_node->is_entry;
}

void init(int n, int q, const RoutingTableEntry *a) {
	for (int i = 0; i < n; ++i) {
            update(true, a[i]);
        }
}

unsigned query(unsigned addr) {
        unsigned nexthop;
        bool res = prefix_query(addr, &nexthop);
	return res && nexthop;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #111.78 us24 KBAcceptedScore: 25

Testcase #263.782 ms78 MB + 336 KBWrong AnswerScore: 0

Testcase #3280.092 ms78 MB + 336 KBWrong AnswerScore: 0

Testcase #4496.104 ms78 MB + 336 KBWrong AnswerScore: 0


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 23:11:55 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用